Here you find instance definitions and the best known solutions (to our knowledge) for the 600 tasks instances of Li & Lim's PDPTW benchmark problems. The version reported here has a hierarchical objective: 1) Minimize number of vehicles 2) Minimize total distance. Distance and time should be calculated with double precision, total distance results are rounded to two decimals. Exact methods typically use a total distance objective and use integral or low precision distance and time calculations. Hence, results are not directly comparable.
For instance definitions, click here.
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.
BVH - Bent, R. and Van Hentenryck. P. A Two-Stage Hybrid Algorithm for Pickup and Delivery Vehicle Routing Problems with Time Windows. In Principles and Practice of Constraint Programming (2003).
CLS - Curtois & Landa Silva. Ejection based metaheuristic for PDPTW. Working paper, University of Nottingham.
CVB - Christiaens J. and Vanden Berghe G. A Fresh Ruin & Recreate Implementation for Capacitated Vehicle Routing Problems. To be submitted.
CVB2 - Christiaens J. and Vanden Berghe G. Preliminary title: Slack Induction by String Removals for Vehicle Routing Problems.
EMIF - Evgeny Makarov & Ilya Fiks (swatmobile.io).
EOE - Eirik Krogen Hagen, EOE Koordinering DA. Exploring infeasible and feasible regions of the PDPTW through penalty based tabu search. Working paper.
K – Richard Kelly: Hybrid Ejection Chains and Adaptive LNS for the PDPTW. Working paper.
Li & Lim - Li H. and A. Lim: A MetaHeuristic for the Pickup and Delivery Problem with Time Windows, In Proceedings of the 13th International Conference on Tools with Artificial Intelligence, Dallas, TX, USA, 2001.
Q - Quintiq. http://www.quintiq.com/optimization-world-records.aspx.
RP - S. Ropke & D. Pisinger, An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows, Technical Report, Department of Computer Science, University of Copenhagen, 2004.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.
SB - Carlo Sartori, Luciana Buriol. A matheuristic approach to the PDPTW (to be submitted).
Shobb - http://shobb.narod.ru/vrppd.html
Published April 18, 2008