mortar board
Vehicle Routing #001

Research and Practise.com

All you need to know, all in one place

The scientific and industrial communities are often unaware of the work of each other. We aim to provide a service where you can find all the information you require, for a specicific specialisation, all on the same web site. We would welcome suggestions for other areas.

Your advert could be here - take a look at our advertising rates
Your advert could be here - take a look at our advertising rates

Vehicle Routing: Datasets

Since its introduction there have been many benchmark datasets introduced for the vehicle routing problem. On this page we have attempted to provide links to all the datasets that we are aware of. However, this has not been easy and we could (will) have missed some, so if you know of any additional datasets, please let us know (email: admin@researchandpractise.com)

Research and Practise.com has also commissioned a survey in order to provide a much more comprehensive coverage of this area. This will take a few months to complete and we will supply a complete list (well, as complete as we can) of all the datasets (including the data), for all the vehicle routing variants, along with the best known solutions for each benchmark instance. We hope that this would be a welcome resource to the vehicle routing community.

If you would like to be informed when we update this web page, please join our mailing list.

Until the commissioned survey has been completed, below we have provided a list of relevant papers and web resources. We hope that you will find these useful.

Scientific Papers (chronological order)

Show All Abstracts Hide All Abstracts

  1. Dantzig G.B. and Ramser J.H. (1959) The Truck Dispatching Problem, Management Science, vol 6, pp 80-91.
    Show Abstract
    Abstract: The paper is concerned with the optimum routing of a fleet of gasoline delivery trucks between a bulk terminal and a large number of service stations supplied by the terminal. The shortest routes between any two points in the system are given and a demand for one or several products is specified for a number of stations within the distribution system. It is desired to find a way to assign stations to trucks in such a manner that station demands are satisfied and total mileage covered by the fleet is a minimum A procedure based on a linear programming formulation is given for obtaining a near optimal solution. The calculations may be readily performed by hand or by an automatic digital computing machine. No practical applications of the method have been made as yet. A number of trial problems have been calculated, however.

  2. Clarke G. and Wright J.W. (1964) Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations Research, 11, pp 568-581.
    Show Abstract
    Abstract: Not yet available

  3. Gaskell T.J. (1967) Cases for Vehicle Fleet Scheduling. Operational Research Quarterly, 18(3), pp 281-295.
    Show Abstract
    Abstract: Not yet available

  4. Hayes R. (1967) The Delivery Problem. Management Science Research Report 106, Carnegie Institute of Technology, Pittsburgh, PA
    Show Abstract
    Abstract: Not yet available

  5. Christofides N. and Eilon S. (1969) An Algorithm for the Vehicle Dispatching Problems. Operational Research Quarterly, 20(3), pp 309-318.
    Show Abstract
    Abstract: Not yet available

  6. Eilon S., Watson-Gandy C. and Christofides N. (1971) Distribution Management, Mathematical Modeling and Practical Analysis, Griffin, London
    Show Abstract
    Abstract: Not yet available

  7. Chrisofides N., Mingozzi A. and Toth P. (1979) The Vehicle Routing Problem. In Chrisofides N., Mingozzi A., Toth P. and Sandi C. (eds) Combinatorial Optimization, Wiley, Chichester, UK, pp 315-338.
    Show Abstract
    Abstract: Not yet available

  8. Christofides N., Mingozzi A. and Toth P. (1981) Space State Relaxation Procedures for the Computation of Bounds to Routing Problems. Networks, 11, pp 145-164. doi:10.1002/net.3230110207  (what is a doi? A doi (Document Object Identifier) is a unique identifier for journal papers. This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi))
    Show Abstract
    Abstract: It is well-known that few combinatorial optimization problems can be solved effectively by dynamic programming alone, since the number of vertices of the state space graph is enormous. What we are proposing here is a general relaxation procedure whereby the state-space associated with a given dynamic programming recursion is relaxed in such a way that the solution to the relaxed recursion provides a bound which could be embedded in general branch and bound schemes for the solution of the problem. This state space relaxation method is analogous to Langrangian relaxation in integer programming. This paper gives a survey of this new methodology, and gives, as examples, applications to the traveling salesman problem (TSP), the time-constrained TSP and the vehicle routing problem (VRP). Valid state space relaxations are discussed for these problems and several bounds are derived in each case. Subgradient optimization and state space ascent are discussed as methods of maximizing the resulting lower bounds. More details of the procedures surveyed in this paper can be found in [2, 3, 4].

  9. Christofides N., Mingozzi A. and Toth P. (1981) Exact Algorithms for the Vehicle Routing Problem based on the Spanning Tree and Shortest Path Relaxations. Mathematical Programming, 20, pp 255-282. doi:10.1007/BF01589353  (what is a doi? A doi (Document Object Identifier) is a unique identifier for journal papers. This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi))
    Show Abstract
    Abstract: We consider the problem of routing vehicles stationed at a central facility (depot) to supply customers with known demands, in such a way as to minimize the total distance travelled. The problem is referred to as the vehicle routing problem (VRP) and is a generalization of the multiple travelling salesman problem that has many practical applications. We present tree search algorithms for the exact solution of the VRP incorporating lower bounds computed from (i) shortest spanningk-degree centre tree (k-DCT), and (ii)q-routes. The final algorithms also include problem reduction and dominance tests. Computational results are presented for a number of problems derived from the literature. The results show that the bounds derived from theq-routes are superior to those fromk-DCT and that VRPs of up to about 25 customers can be solved exactly.

  10. Laporte G., Mobert Y. and Desrochers M. (1985) Optimal Routing under Capacity and Distance Restrictions. Operations Research, 33, pp 1050-1073. doi:10.1287/opre.33.5.1050  (what is a doi? A doi (Document Object Identifier) is a unique identifier for journal papers. This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi))
    Show Abstract
    Abstract: This paper describes an integer linear programming algorithm for vehicle routing problems involving capacity and distance constraints. The method uses constraint relaxation and a new class of subtour elimination constraints. Two versions of the algorithm are presented, depending upon the nature of the distance matrix. Exact solutions are obtained for problems involving up to sixty cities.

  11. Solomon M.M. (1987) Algorithms for the Vehicle Routing and Scheduling with Time Windows Constraints. Operations Research, 35, pp 45-65. doi:10.1287/opre.35.2.254  (what is a doi? A doi (Document Object Identifier) is a unique identifier for journal papers. This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi))
    Show Abstract
    Abstract: This paper considers the design and analysis of algorithms for vehicle routing and scheduling problems with time window constraints. Given the intrinsic difficulty of this problem class, approximation methods seem to offer the most promise for practical size problems. After describing a variety of heuristics, we conduct an extensive computational study of their performance. The problem set includes routing and scheduling environments that differ in terms of the type of data used to generate the problems, the percentage of customers with time windows, their tightness and positioning, and the scheduling horizon. We found that several heuristics performed well in different problem environments; in particular an insertion-type heuristic consistently gave very good results.

  12. M. L. Fisher (1994) Optimal Solution of Vehicle Routing Problems using Minimum K-trees. Operations Research, 42(4), pp 626-642. doi:10.1287/opre.42.4.626  (what is a doi? A doi (Document Object Identifier) is a unique identifier for journal papers. This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi))
    Show Abstract
    Abstract: We consider the problem of optimally scheduling a fleet of K vehicles to make deliveries to n customers subject to vehicle capacity constraints. Given a graph with n + 1 nodes, a K-tree is defined to be a set of n + K edges that span the graph. We show that the vehicle routing problem can be modeled as the problem of finding a minimum cost K-tree with two K edges incident on the depot and subject to some side constraints that impose vehicle capacity and the requirement that each customer be visited exactly once. The side constraints are dualized to obtain a Lagrangian problem that provides lower bounds in a branch-and-bound algorithm. This algorithm has produced proven optimal solutions for a number of difficult problems, including a well-known problem with 100 customers and several real problems with 2571 customers.

  13. Fischetti M., Toth P. and Vigo D. (1994) A Branch-and-bound Algorithm for the Capacitated Vehicle Routing Problem on Directed Graphs. Operations Research, 42(5), pp 846-859. doi:10.1287/opre.42.5.846  (what is a doi? A doi (Document Object Identifier) is a unique identifier for journal papers. This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi))
    Show Abstract
    Abstract: We consider the asymmetric capacitated vehicle routing problem (CVRP), a particular case of the standard asymmetric vehicle routing problem in which only the vehicle capacity constraints are imposed. CVRP is known to be NP-hard and finds practical applications in distribution and scheduling. We describe two new bounding procedures for CVRP, based on the so-called additive approach. Each procedure computes a sequence of nondecreasing lower bounds, obtained by solving different relaxations of CVRP. Effective implementations of the procedures are also outlined which considerably reduce the computational effort. The two procedures are combined into an overall bounding algorithm. A branch-and-bound exact algorithm is then proposed, whose performance is enhanced by means of reduction procedures, dominance criteria, and feasibility checks. Extensive computational results on both real-world and random test problems are presented, showing that the proposed approach favorably compares with previous algorithms from the literature.

  14. Hadjiconstantinou E., Christofides N. Mingozzi A. (1995) A new Exact Algorithm for the Vehicle Routing Problem based on q-paths and k-shortest paths relaxations. Annals of Operations Research, 61, pp 21-43. doi:10.1007/BF02098280  (what is a doi? A doi (Document Object Identifier) is a unique identifier for journal papers. This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi))
    Show Abstract
    Abstract: We consider the basic Vehicle Routing Problem (VRP) in which a fleet ofM identical vehicles stationed at a central depot is to be optimally routed to supply customers with known demands subject only to vehicle capacity constraints. In this paper, we present an exact algorithm for solving the VRP that uses lower bounds obtained from a combination of two relaxations of the original problem which are based on the computation ofq-paths andk-shortest paths. A set of reduction tests derived from the computation of these bounds is applied to reduce the size of the problem and to improve the quality of the bounds. The resulting lower bounds are then embedded into a tree-search procedure to solve the problem optimally. Computational results are presented for a number of problems taken from the literature. The results demonstrate the effectiveness of the proposed method in solving problems involving up to about 50 customers and in providing tight lower bounds for problems up to about 150 customers.

Web pages

  1. Solomon VRP Test Instances
  2. The Multi Compartment Commodity Heterogeneous Fixed Fleet Vehicle Routing Problem with Time Windows (MCCHFFVRPTW)
  3. The Vehicle Routing Problem with Intermediate Replenishment Facilities (VRPIRF)
  4. The Capacitated Vehicle Routing Problem with Three-Dimensional Loading Constraints(3L-CVRP)
  5. The Inventory Routing Problem over a finite periodic planning horizon

We hope you find these pages useful and we welcome your feedback. If you have any comments, please email us at admin@researchandpractise.com.

If you would like to be informed when changes are made to these pages please join our mailing list.