800 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 800 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 800-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_8_1 80 25184.38 SAM::OPT 16-jun-03
lc1_8_2 76 29735.85 HW 26-Feb-21
lc1_8_3 62 27287.80 SCR 19-Dec-21
lc1_8_4 59 22686.08 SCR 31-Dec-19
lc1_8_5 80 25211.22 SAM::OPT 12-jul-03
lc1_8_6 80 25164.25 SAM::OPT 12-jul-03
lc1_8_7 80 25158.38 SAM::OPT 13-jul-03
lc1_8_8 77 26688.17 HW 30-Nov-20
lc1_8_9 71 26975.61 SCR 19-Dec-21
lc1_8_10 68 27099.59 SCR 19-Dec-21
 
lc2_8_1 24 11687.06 SAM::OPT 19-may-03
lc2_8_2 24 13713.13 SB 30-jan-19
lc2_8_3 24 12981.37 SCR 05-Nov-19
lc2_8_4 23 12917.34 HW 15-Jan-21
lc2_8_5 25 12298.33 EOE 09-may-16
lc2_8_6 24 12645.71 SB 30-jan-19
lc2_8_7 24 14041.47 SCR 19-Dec-21
lc2_8_8 23 12924.10 SCR 19-Dec-21
lc2_8_9 24 11629.41 CLS 29-nov-15
lc2_8_10 23 12226.42 SCR 05-Nov-19
 
lr1_8_1 80 39291.32 CVB 06-apr-18
lr1_8_2 59 34071.19 NVIDIA 15-jan-24
lr1_8_3 44 29223.10 NVIDIA 15-jan-24
lr1_8_4 25 20675.70 SCR 19-Dec-21
lr1_8_5 48 39809.68 SCR 19-Dec-21
lr1_8_6 38 36244.90 SCR 19-Dec-21
lr1_8_7 30 27078.09 SCR 19-Dec-21
lr1_8_8 19 20705.45 SCR 19-Dec-21
lr1_8_9 39 38499.00 SCR 19-Dec-21
lr1_8_10 30 31091.07 SCR 19-Dec-21
 
lr2_8_1 14 41873.12 HW 30-Nov-20
lr2_8_2 11 36549.69 HW 23-Dec-20
lr2_8_3 9 26391.07 SCR 22-Apr-21
lr2_8_4 6 20618.03 SCR 19-Dec-21
lr2_8_5 11 34816.50 SCR 22-Apr-21
lr2_8_6 9 28814.65 HW 15-Jan-21
lr2_8_7 7 25502.39 SCR 19-Dec-21
lr2_8_8 5 18327.23 SCR 22-Apr-21
lr2_8_9 10 30515.50 SCR 05-Nov-19
lr2_8_10 8 30136.86 HW 15-Jan-21
 
lrc1_8_1 66 32252.28 CVB2 17-jan-19
lrc1_8_2 56 27878.89 CAINIAO 10-mar-20
lrc1_8_3 48 24371.95 SB 30-jan-19
lrc1_8_4 34 18208.51 SCR 01-Dec-20
lrc1_8_5 58 31169.16 SCR 05-Nov-19
lrc1_8_6 54 28961.66 HW 30-Nov-20
lrc1_8_7 50 28768.40 SCR 19-Dec-21
lrc1_8_8 44 26902.93 SCR 31-Dec-19
lrc1_8_9 44 24854.96 SCR 19-Dec-21
lrc1_8_10 39 24622.59 SCR 19-Dec-21
38856,21 
lrc2_8_1 20 23074.22 CVB2 17-jan-19
lrc2_8_2 17 22220.95 SCR 05-Nov-19
lrc2_8_3 14 20379.26 SCR 05-Nov-19
lrc2_8_4 11 14711.80 SCR 19-Dec-21
lrc2_8_5 16 23602.44 CAINIAO 02-Apr-20
lrc2_8_6 15 22591.26 SCR 05-Nov-19
lrc2_8_7 13 25436.79 HW 30-Nov-20
lrc2_8_8 11 22604.36 HW 15-Jan-21
lrc2_8_9 10 22594.69 SCR 19-Dec-21
lrc2_8_10 9 19604.12 SCR 19-Dec-21
       

 * Detailed solution by Shobb

References

CAINIAO - Zhu He, Longfei Wang, Haoyuan Hu (), 
Yinghui Xu & VRP Team (Yujie Chen, Lei Wen, Guotao Wu, Ying Zhang et al.), unpublished result of CAINIAO AI.

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

HW - Zhu He, Weibo Lin (), Fuda Ma et al. (Team of Scheduling Architecture and Algorithms, Huawei Cloud) and Zhipeng Lü (Huazhong University of Science and Technology). Cloud-oriented solvers for industrial planning and resource scheduling problems of Huawei Cloud (https://www.huaweicloud.com), unpublished.

MFS - Evgeny Makarov, Ilya Fiks, Eugene Sorokhtin (swatmobile.io). Unpublished.

NVIDIA - ( , ,  , ) NVIDIA cuOpt : GPU accelerated Operations Research and Optimization.

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 (), 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.

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