# Tag Info

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. ...
• 5,873
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, ...) ...
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 ...
• 5,873

### 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,839

### 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 ...
• 511

### 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,667

### 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"...
• 28.9k
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 ...
• 11.1k

### 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 ...
• 5,347

### 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 ...
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,194

### 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,313

### 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,499
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,641
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,010

### 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 ...
• 5,347

### 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 ...
• 4,377

### 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,577

### 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 ...
• 603

### 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/...

### 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,244
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 ...
• 28.9k
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)
• 1,421

### 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,194
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 ...
• 5,873

### 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,042

### 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 ...
• 5,873
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,641
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 ...
• 21.8k