Instance definitions (text)

Here is a zip file with the 200 customer instances.

Best known results for Gehring & Homberger's 200 customer instances

The instance names in blue are hyperlinks to files with corresponding detailed solutions. They have all been checked by our solution checker. Note that many best known solutions do not have a reference to a peer reviewed publication. For these, important details on the solution algorithm, the computing time, and the experimental platform are probably not available. Further, there is no guarantee that the solutions have been produced without using external information, such as detailed solutions published earlier. We may later introduce two categories: 'properly published' and 'freestyle', the latter with no restrictions.   

NB!

The C1_2_8 and R1_2_1 entries have been changed to inferior values. The previous entries were based on reports without detailed solutions. Later, it appeared that the solutions are infeasible, see reference NBD.

Similarly, the original C1_2_9 result of Mester & Bräysy 18/2642.82 turned out to represent an infeasible solution, given the double precision requirement.

The updated entries are based on detailed solutions that have been checked by our solution checker.

References

B - O. Bräysy, "A Reactive Variable Neighborhood Search Algorithm for the Vehicle Routing Problem with Time Windows," Working Paper, University of Vaasa, Finland, 2001.

BC4, Mirosław BŁOCHO, Zbigniew J. CZECH, "A parallel memetic algorithm for the vehicle routing problem with time windows".  3PGCIC 2013, 8th International Conference on P2P, Parallel, Grid, Cloud and Internet Computing.

BSJ2 - Bjørn Sigurd Johansen, , DSolver version2 05-2005.

BVH - R. Bent and P. Van Hentenryck, "A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows," Technical Report CS-01-06, Department of Computer Science, Brown University, 2001.

G - Tomasz Gandor: "Approximate Solutions for the Vehicle Routing Problem with Time Windows for a Large Number of Customers". "Systemy Wspomagania Decyzji" (Decision Support Systems), 2008, Zakopane, Poland.

GH - H. Gehring and J. Homberger, "A Parallel Two-phase Metaheuristic for Routing Problems with Time Windows," Asia-Pacific Journal of Operational Research, 18, 35-47, (2001).

H - Keld Helsgaun: Unpublished Technical Report, Roskilde University, 2017.

MB - Mester, D. and O. Bräysy (2005), “Active Guided Evolution Strategies for Large Scale Vehicle Routing Problems with Time Windows”. Computers & Operations Research 32, 1593-1614.

MB2 - Mester, D & O. Bräysy (2012). "A new powerful metaheuristic for the VRPTW”, working paper, University of Haifa, Israel.

NBD - Yuichi Nagata, Olli Bräysy, and Wout Dullaert (2010). A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows. Comput. Oper. Res. 37, 4 (April 2010), 724-737.

PGDR - Eric Prescott-Gagnon, Guy Desaulniers and Louis-Martin Rousseau. A Branch-and-Price-Based Large Neighborhood Search Algorithm for the Vehicle Routing Problem with Time Windows. (2007).

RP - S. Ropke & D.Pisinger. "A general heuristic for vehicle routing problems",  technical report, Department of Computer Science, University of Copenhagen.

SAM::OPT - Hasle G., O. Kloster: Industrial Vehicle Routing Problems. Chapter in Hasle G., K-A Lie, E. Quak (eds): Geometric Modelling, Numerical Simulation, and Optimization. ISBN 978-3-540-68782-5, Springer 2007.

SCR - Piotr Sielski (), Piotr Cybula, Marek Rogalski (), Mariusz Kok, Piotr Beling, Andrzej Jaszkiewicz, Przemysław Pełka. Emapa S.A (http://www.emapa.pl), "New methods of VRP problem optimization", unpublished research funded by The National Centre for Research and Development. project number: POIR.01.01.01.-00-0222/16.

VCGP - T. Vidal, T. G. Crainic, M. Gendreau, C. Prins. "A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows", Computers & Operations Research, Vol. 40, No. 1. (January 2013), pp. 475-489.