200 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 200 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.

Best Known Results for PDPTW 200-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.

Instance Vehicles Distance Reference Date
lc1_2_1*,s 20 2704.57 Li & Lim 2001
lc1_2_2*,s 19 2764.56 Li & Lim 2001
lc1_2_3 17 3127.78 H 15-jul-16
lc1_2_4k 17 2693.41 BVH 27-jun-03
lc1_2_5*,s 20 2702.05 Li & Lim 2001
lc1_2_6*,s 20 2701.04 Li & Lim 2001
lc1_2_7*,s 20 2701.04 Li & Lim 2001
lc1_2_8 19 3354.27 SB 18-apr-18
lc1_2_9*,s 18 2724.24 Li & Lim 2001
lc1_2_10 17 2942.13 EOE 19-nov-15
 
lc2_2_1s 6 1931.44 Li & Lim 2001
lc2_2_2s 6 1881.40 Li & Lim 2001
lc2_2_3 6 1844.33 SAM::OPT 15-apr-03
lc2_2_4s 6 1767.12 Li & Lim 2001
lc2_2_5s 6 1891.21 Li & Lim 2001
lc2_2_6 6 1857.78 SAM::OPT 29-dec-03
lc2_2_7 6 1850.13 SAM::OPT 10-dec-03
lc2_2_8s 6 1824.34 Li & Lim 2001
lc2_2_9 6 1854.21 SAM::OPT 01-sep-03
lc2_2_10s 6 1817.45 Li & Lim 2001
 
lr1_2_1*,s 20 4819.12 Li & Lim 2001
lr1_2_2k 17 4621.21 RP 08-jul-03
lr1_2_3 14 4402.38 CLS 27-feb-16 
lr1_2_4 10 3027.06 SB 18-apr-18
lr1_2_5h 16 4760.18 BVH 27-jun-03
lr1_2_6 13 4800.94 CLS 26-feb-16
lr1_2_7 12 3543.36 SB 18-apr-18
lr1_2_8 9 2759.32 SB 18-apr-18
lr1_2_9 13 5050.75 CLS 16-jan-16
lr1_2_10 11 3664.08 H 13-jul-16
 
lr2_2_1 5 4073.10 SAM::OPT 09-dec-03
lr2_2_2 4 3796.00 SAM::OPT 14-feb-03
lr2_2_3s 4 3098.36 RP 08-jul-03
lr2_2_4 3 2486.00 H 13-jul-16
lr2_2_5 4 3438.39 SAM::OPT 13-dec-03
lr2_2_6 3 4457.95 SCR 05-nov-19
lr2_2_7 3 3098.35 H 15-jul-16
lr2_2_8 2 2449.36 SCR 05-nov-19
lr2_2_9 3 3922.11 SB 18-apr-18
lr2_2_10 3 3254.83 SB 18-apr-18
 
lrc1_2_1* 19 3606.06 SAM::OPT 14-dec-03
lrc1_2_2 15 3671.02 EOE 19-nov-15
lrc1_2_3 13 3154.92 CLS 27-feb-16
lrc1_2_4k 10 2631.82 RP 08-jul-03
lrc1_2_5¤,s 16 3715.81 BVH 27-jun-03
lrc1_2_6 16 3572.16 EOE 19-nov-15
lrc1_2_7 14 3666.34 K 13-apr-15
lrc1_2_8 13 3145.74 CVB 06-apr-18
lrc1_2_9 13 3157.34 EOE 19-nov-15
lrc1_2_10 12 2928.90 EOE 19-nov-15
 
lrc2_2_1 6 3595.18 K 14-apr-15
lrc2_2_2 5 3158.25 H 13-jul-16
lrc2_2_3 4 2881.99 H 13-jul-16
lrc2_2_4 3 2835.40 SCR 05-nov-19
lrc2_2_5s 5 2776.93 BVH 27-jun-03
lrc2_2_6 5 2707.96 SAM::OPT 21-dec-03
lrc2_2_7 4 3010.68 SCR 05-nov-19
lrc2_2_8 4 2399.89 EOE 17-nov-15
lrc2_2_9s 4 2208.49 RP 08-jul-03
lrc2_2_10 3 2437.88 H 13-jul-16
       
h: Detailed solution provided by Shobb
k: Detailed solution provided by K 
s: Detailed solution provided by SAM::OPT 
*: Corresponds to optimal value found by RC
¤: Corresponds to optimal value found by BBM
 

References

BBM - Baldacci, Bartolini, and Mingozzi. An Exact Algorithm for the Pickup and Delivery Problem. Operations Research 59(2), pp. 414–426 (2011).
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, T., Landa-Silva, D., Qu, Y. and Laesanklang, W., 2018. Large neighbourhood search with adaptive guided ejection search for the pickup and delivery problem with time windows. EURO Journal on Transportation and Logistics, 7(2), pp.151-192.
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.
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.
RC - Ropke S. and J.-F. Cordeau. Branch and cut and price for the pickup and delivery problem with time windows. Transportation Sci. 43(3)267–286 (2009).
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).
SCR - Piotr Sielski (), Piotr Cybula, Marek Rogalski (), Mariusz Kok, Piotr Beling, Andrzej Jaszkiewicz, Przemysław Pełka. Emapa S.A. www.emapa.pl "Development of universal methods of solving advanced VRP problems with the use of machine learning", unpublished research funded by The National Centre for Research and Development, project number: POIR.01.01.01-00-0012/19.  "Optimization of advanced VRP problem variants", unpublished. Computing grant 358 funded by Poznan Supercomputing and Networking Center.


 

Published April 18, 2008