21 votes
Accepted

Solving pricing problem heuristically in column generation algorithm for VRP

Generating routes heuristically, or heuristic pricing, is very common in the vehicle routing literature. Even when the pricing problem can be solved exactly, heuristic pricing is often tried first. ...
user avatar
21 votes
Accepted

List of Implementations for common OR problems

Let's make an inventory of example code for each common OR problem? Vehicle Routing Problem OptaPlanner: explanation + videos - source code (capacitated, time windows, multiple depots, ...) ...
19 votes
Accepted

How to compare two different formulations of a problem?

Even if the decision variables differ, you may still be able to prove that one of the formulations is stronger than the other by introducing an appropriate mapping. Take for example a flow ...
user avatar
18 votes

Solving ATSP problem for large-scale problem

If you are interested in solving the TSP, the Concorde TSP solver is a very powerful and easy-to-use tool. I do not know what the licensing options are for commercial applications, but for research ...
user avatar
16 votes

List of Implementations for common OR problems

A good place to start is COIN-OR, which aims to "create for mathematical software what the open literature is for mathematical theory". You can also take a look at Google's OR-Tools. It contains many ...
user avatar
  • 511
16 votes

Solving ATSP problem for large-scale problem

If you cannot use Concorde as suggested by Albert, I'd suggest you look for an implementation of the Lin-Kerninghan-Heuristic (which is also included in Concorde). It iterates between 2-opt and 3-opt ...
user avatar
  • 2,667
15 votes

How to compare two different formulations of a problem?

I'm not sure there is a single, definitive best way to compare models, and if there is I likely have never seen it applied. I lean toward computational comparisons if properly done, but "properly done"...
user avatar
  • 28.9k
13 votes
Accepted

What's the current status of the Vehicle Routing Problem in the logistics industry?

The answer to this question is quite complicated. There are two main types of vehicle routing problems, the offline and the online problem. Solving the offline problem takes longer and is used to ...
user avatar
11 votes

List of Implementations for common OR problems

I would, for everything knapsack-like, always go to David Pisingers homepage. Here you can find very efficient codes for knapsack problems (COMBO), multiple-choice knapsack problems (Mcknap), and ...
user avatar
  • 5,347
11 votes

How to compare two different formulations of a problem?

I agree with most of the comments here; Even if the decision variables are different, you may use proof by construction, for example, with appropriate mapping to prove that a formulation is stronger ...
user avatar
11 votes
Accepted

Obtaining optimality gaps when using hybrid exact-heuristic approaches to vehicle routing problems

You are right. If you solve the pricing heuristically, you do not have a valid lower bound. One approach to obtain a lower bound would be to solve a relaxation of the pricing problem exactly. Usually,...
user avatar
10 votes

What is the following VRP?

This recent review on rich routing problems may be helpful: http://repository.psau.edu.sa/jspui/retrieve/6358c84c-e14d-4e4c-8645-c8f7320606ab/EJOR_2015.pdf A quick scan on the categories would ...
user avatar
  • 1,313
9 votes

Fast validation of time windows in a routing problem

Indeed, as you pointed out already, checking time windows feasibility is only doable in linear time for a given, static, route. However, you may exploit preprocessing techniques and partial paths ...
user avatar
9 votes
Accepted

Stochastic VRP: Sources of uncertainty and modeling approaches

The source of uncertainty is usually customer demand, travel time, service time at the location (during pick up or serving the customer), or presence of the customer (customers may not be available to ...
user avatar
  • 5,641
9 votes
Accepted

Vehicle routing benchmark instances

For a table of benchmark instances on SDVRP you can have a look at Table 4 (Benchmark on known SDVRP problem instances) of Ray et al. (2014)1. More details are provided in reference [30]2 of the paper....
user avatar
  • 5,010
9 votes

Customer clustering to solve very large-scale VRPs

You might find some interesting points in the following two papers C. Walshaw, 2002, A Multilevel Approach to the Travelling Salesman Problem, Operations Research, Vol. 50, nr. 5, pages 862-877. In ...
user avatar
  • 5,347
9 votes

VRP app as a Minimum Viable Product

For what it's worth... We have an out-of-the-box open source VRP application in Java, yet it always needs to be customized to meet a user's or customer's needs. Although many VRP variants can use the ...
user avatar
9 votes

Branch and Price Algorithm

Being a good or bad approach will depend on several factors, for example: the size of the instances time available to find a solution (this tends to be an important matter in vehicle routing ...
user avatar
  • 1,577
8 votes

Solving pricing problem heuristically in column generation algorithm for VRP

The general rule is to use dynamic programming (Labeling Algorithm) to solve the VRP pricing problem. It has some advantage over solving the mathematical model. DP can yield many columns in each ...
user avatar
  • 603
8 votes

Solving ATSP problem for large-scale problem

You could also give a try to VROOM, which can be used for commercial use. It can solve TSP and some variants of the VRP such as VRPTW and CVRP. Here is the API documentation : https://github.com/...
user avatar
8 votes

Obtaining optimality gaps when using hybrid exact-heuristic approaches to vehicle routing problems

Even if you solve the pricing heuristically, you can still obtain a valid lower bound in certain cases. However, it depends on your pricing heuristic whether this is possible. You have found the ...
user avatar
8 votes
Accepted

To calculate the time needed for a vacuum robot to cover whole area

I don't know if a closed form solution is achievable. Assuming you can quantify how the robot selects its next direction when it hits a boundary (uniform over the entire circle, uniform over ...
user avatar
  • 28.9k
8 votes
Accepted

VRP book recommendations

If there is one book to know about VRPs, it is: "Vehicle Routing: Problems, Methods, and Applications, Second Edition" (Paolo Toth and Daniele Vigo, 2014)
user avatar
  • 1,421
8 votes

Odd behavior in the branch bound and price algorithm with column generation

There can be many reasons why a branch-cut-and-price algorithm fails to solve an instance to optimality in a reasonable time. A large primal-dual gap because a heuristic solution is absent or of a ...
user avatar
7 votes
Accepted

Two-commodity flow formulation for an asymmetric cost VRP

One way to do this is as follows: for each edge $(i,j)$ introduce binary variables $z_{ij}$ and $z_{ji}$ that indicate whether a vehicle travels from $i$ to $j$ or from $j$ to $i$, and add the ...
user avatar
7 votes

Two-stage $k$-means clustering

Two stage k-means is discussed in: "Balanced K-Means Algorithm for Partitioning Areas in Large-Scale Vehicle Routing Problem" (Dec 2009), by Ruhan He, Weibin Xu, Jiaxia Sun, and Bingqiao Zu "Solving ...
user avatar
  • 2,042
7 votes

What's the current status of the Vehicle Routing Problem in the logistics industry?

I am a researcher in vehicle routing, and my answer is based on my experience as a researcher, conversations with practitioners and consultants, and seminars and conference talks I have attended. You ...
user avatar
7 votes
Accepted

Customer clustering to solve very large-scale VRPs

You can check the following papers: A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows. From the abstract: Phase I aims to ...
user avatar
  • 5,641
7 votes
Accepted

Column Generation algorithm for vehicle routing problem

Let $d_i$ be the demand for customer $i\in N$, let $V=\{1,\dots,K\}$ be the set of vehicles, and let $P$ be the set of columns, where each column corresponds to a feasible subtour starting from the ...
user avatar
  • 21.8k
7 votes

Calculate the average of the objective function values ​resulting from metaheuristics after a defined number of executions

There are multiple ways you can analyze and compare the results of heuristics/randomized search procedures. Report the average, best and worst Report the average, and standard deviation Graphically ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible