400 tasks
Due to the way Li & Lim generated the test instances, the number of tasks in these instances are different and slightly higher than the nominal value.

Here you find instance definitions and the best known solutions (to our knowledge) for the 400 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. Hyperlinks in the 'Instance' column point to text files with specification of the best known solution for the given instance.

For instance definitions, click here.

Best Known Results for PDPTW 400-cases

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.

Instance Vehicles Distance Reference

Date

lc1_4_1 40 7152.06 SAM::OPT 16-jun-03
lc1_4_2 38 8007.79 Q 08-oct-15
lc1_4_3 32 8736.63 SB 30-jan-19
lc1_4_4 30 6451.68 Li & Lim 2001
lc1_4_5 40 7150.00 SAM::OPT 19-apr-03
lc1_4_6s 40 7154.02 Li & Lim 2001
lc1_4_7 40 7149.43 SAM::OPT 15-mar-03
lc1_4_8 38 8305.42 CVB2 17-jan-19
lc1_4_9 36 7451.20 Q 09-oct-15
lc1_4_10 34 8010.54 CVB2 17-jan-19
 
lc2_4_1s 12 4116.33 Li & Lim 2001
lc2_4_2 12 4144.29 SAM::OPT 15-may-03
lc2_4_3 12 4401.08 CVB2 17-jan-19
lc2_4_4 12 3743.95 Li & Lim 2001
lc2_4_5s 12 4030.63 TS 01-may-2003 
lc2_4_6 12 3900.29 SAM::OPT 20-apr-03
lc2_4_7s 12 3962.51 BVH 27-jun-03
lc2_4_8s 12 3844.45 Li & Lim 2001
lc2_4_9sh 12 4188.93 RP 08-jul-03
lc2_4_10s 12 3828.44 BVH 27-jun-03
 
lr1_4_1s 40 10639.75 TS 2003
lr1_4_2 30 11009.51 SB 30-jan-19
lr1_4_3 22 9251.13 SB 30-jan-19
lr1_4_4 15 7077.05 CVB2 17-jan-19
lr1_4_5 28 11374.06 CLS 23-jan-16
lr1_4_6 23 11778.11 CVB2 17-jan-19
lr1_4_7 18 8771.76 CVB2 17-jan-19
lr1_4_8 14 5842.41 CVB2 17-jan-19
lr1_4_9 24 9862.65 CLS 23-jan-16
lr1_4_10 20 8245.87 CVB2 17-jan-19
 
lr2_4_1s 8 9726.88 BVH 27-jun-03
lr2_4_2 7 9426.78 CVB2 17-jan-19
lr2_4_3 5 10597.89 CVB2 17-jan-19
lr2_4_4 4 6397.04 CVB2 17-jan-19
lr2_4_5 6 9931.76 CVB2 17-jan-19
lr2_4_6 5 8979.78 CVB2 17-jan-19
lr2_4_7 4 8086.60 CVB2 17-jan-19
lr2_4_8 4 5303.74 H 15-aug-16
lr2_4_9 6 7930.55 Q 04-jan-16
lr2_4_10 5 7715.93 CVB2 17-jan-19
 
lrc1_4_1 36 9124.52 CLS 02-des-15
lrc1_4_2sb 31 8346.06 RP 08-jul-03
lrc1_4_3 24 7805.16 SB 30-jan-19
lrc1_4_4 19 5803.31 SB 30-jan-19
lrc1_4_5 32 8847.40 SB 30-jan-19
lrc1_4_6 30 8394.47 CVB2 17-jan-19
lrc1_4_7 28 8037.87 DK 30-jun-11
lrc1_4_8 26 7930.15 SB 30-jan-19
lrc1_4_9 25 8030.98 SB 30-jan-19
lrc1_4_10 23 7064.36 SCR 14-may-19
 
lrc2_4_1 11 10104.29 SB 30-jan-19
lrc2_4_2 10 7159.95 SB 30-jan-19
lrc2_4_3 8 6431.43 CVB2 17-jan-19
lrc2_4_4 5 5251.77 CVB2 17-jan-19
lrc2_4_5 10 7381.91 CVB2 17-jan-19
lrc2_4_6 9 6337.08 Q 21-jan-16
lrc2_4_7 8 6308.93 SB 30-jan-19
lrc2_4_8 7 5776.31 CVB2 17-jan-19
lrc2_4_9 6 6480.65 CVB2 17-jan-19
lrc2_4_10 6 5551.07 H 15-aug-16
    
s: Detailed solution provided by SAM::OPT
sb: Detailed solution provided by SB
sh: detailed solution provided by Shobb

 

References

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.

DK - Dirk Koning. Using Column Generation for the Pickup and Delivery Problem with Disturbances, Technical Report, Department of Computer Science, Utrecht University, 2011.

EOE - Eirik Krogen Hagen, EOE Koordinering DA. Exploring infeasible and feasible regions of the PDPTW through penalty based tabu search. Working paper.

H - Keld Helsgaun, Working paper, Roskilde University, Denmark (2016).

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.

NB1 - J. Nalepa and M. Blocho. "Enhanced Guided Ejection Search for the Pickup and Delivery Problem with Time Windows", Intelligent Information and Database Systems: Proc. 8th Asian Conference, ACIIDS 2016, pages 388–398. Springer, Heidelberg, 2016.

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.
SCR - Piotr Sielski (psielski@emapa.pl), Piotr Cybula, Marek Rogalski, 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.
SB - Carlo Sartori, Luciana Buriol. A matheuristic approach to the PDPTW (to be submitted).
Shobb - http://shobb.narod.ru/vrppd.html

TS - TetraSoft A/S: MapBooking Algoritm for Pickup and Delivery Solutions with Time Windows and Capacity restraints.

Published April 18, 2008