21

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. Only when no more routes can be generated by heuristics, the exact pricing algorithm is run. When heuristic pricing is used in this way, the overall method is ...


19

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 formulation and a route formulation for a vehicle routing problem (minimization). Typically, the folllowing argument can be made: Given (fractional) values for the route ...


18

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 purposes it is free and easy to use (if you are familiar with C/C++)


16

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 to find a good solution quickly. If you are interested in the best solution or need to know a bound on the best possible solution, then Concorde is the way to ...


15

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" is in the eye of the beholder. The most obvious criteria for computational comparisons are that they use the same test problems (not selected because they ...


15

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, ...) LocalSolver: explanation + source code (same with time windows) OR-tools: explanation + source code Jsprit: source code - company website (capacitated, time windows, ...


15

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 algorithms for specific problems (like knapsack or max flow) and also generic LP and CP solvers.


13

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 make planning-level decisions. The online problem is solved as real-time information comes in, and tells us what to do at the low level (as in which vehicle should ...


11

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 quadratick knapsack problems (quadknap) among others. I don't know if it qualifies as a "common OR problem" but for linear vector optimization (and therefore also ...


11

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 than another one. When comparing two different (yet equivalent) formulation for the same problem, I often use three criteria: (1) LP relaxation/tightness, (2) ...


11

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, the faster a relaxation can be solved, the worse in the resulting bound. Another (but still similar) approach is to calculate a lower bound on the pricing ...


10

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 suggest you have: 1.3.2 Multiple Depots 2.1.1.2 Heterogeneous Vehicles 2.2.1 Restrictions on Customer Waiting Time 2.2.2 Restrictions on Road Access 2.4 ...


9

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 concatenation to achieve constant time worst-case complexity to assess time windows feasibility within a typical routing metaheuristic. Take a look at the article ...


9

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 receive their orders). As mentioned in the paper: Capacitated vehicle routing problem with stochastic demand has been by far the most studied version of the ...


9

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. References [1] Ray, S., Soeanu, A., Berger, J., Debbabi, M. (2014). The multi-depot split-delivery vehicle routing problem: Model and solution algorithm. ...


9

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 this paper they present a method which first simplifies the problem by aggregating customers until you have a very simple graph. After the simplification phase, ...


9

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 same model, many other variations don't fit the same model. For example, VRP with pickup and deliveries are fundamentally different from CVRP's (with or ...


9

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 applications) computing power what level of solution quality qualifies as good enough See this work by Yu, Nagarajan and Shen on the minimum makespan VRP with ...


8

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 iteration versus the one column that yielded by solving the model. As @Kevin Dalmeijer mentioned you need to be able to solve the pricing problem exactly even if you ...


8

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/VROOM-Project/vroom/blob/master/docs/API.md What you can is to start with the demo server to see if it can fit on small instances and then install it to use it as ...


8

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 optimal solution to the linear relaxation of the master problem if there are no more columns with negative reduced costs. Suppose you have a heuristic that always ...


8

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 directions not within some angle of its last direction, some nonuniform distribution, ...), you could fairly easily build a simulation model (starting with an empty room ...


8

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)


7

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 constraint $z_{ij} + z_{ji} \le 1$. Now $z_{ij} + z_{ji}$ is equal to 1 if edge $(i,j)$ is used in the solution and equal to 0 if edge $(i,j)$ is not used. You can ...


7

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 the Heterogeneous Capacitated Vehicle Routing Problem using K-Means Clustering and Valid Inequalities" (Apr 2017), by Noha A. Mostafa and Amr Eltawil The ...


7

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 make a very interesting observation: solving VRP's to optimality is currently only possible for hundreds of customers, while problems in practice are ...


7

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 identifying a set of cost-effective feasible clusters while Phase II assigns clusters to vehicles and sequences them on each tour by using the cluster-based MILP ...


7

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 depot, with arc variables $x_{i,j}$ and node variables $y_i$. Let $z$ be the makespan. The master problem over $z$ and $\lambda$ is as follows, with dual ...


7

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 represent the results as a boxplot. When computing the average, you need to be careful when there are instances that could not be solved by the heuristic. This ...


7

"Random solution" means the decision variables are chosen randomly. It does not usually mean ignoring feasibility constraints. So, in the case of CVRP, it would mean choosing the cities for a given route, as well as their sequence on the route, randomly. There are various ways to deal with the capacity constraint -- for example, if the next ...


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