27
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, ...)
...
22
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. ...
- 6,362
20
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 ...
- 6,362
19
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 ...
- 1,869
17
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 ...
- 521
17
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 ...
- 2,767
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"...
- 40.1k
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 ...
- 12.2k
12
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 ...
- 6,667
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 ...
- 111
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,...
- 1,569
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 ...
- 1,343
9
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/...
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 ...
- 1,574
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 ...
- 5,894
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....
- 5,452
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 ...
- 6,667
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 ...
- 5,001
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 ...
- 1,687
9
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 ...
- 1,569
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 ...
- 683
8
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 ...
- 6,362
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 ...
- 2,335
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 ...
- 40.1k
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)
- 2,673
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 ...
- 6,362
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 ...
- 2,130
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 ...
- 5,894
7
votes
Accepted
VRP benchmark instances with charging stations
E-VRP-NL has been used in The electric vehicle routing problem with capacitated
charging stations. Also authors in the paper mentioned by A.Omidi design two new sets of benchmark instances for the E-...
- 8,677
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 ...
- 33.6k
Only top scored, non community-wiki answers of a minimum length are eligible