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

Best Known Results for PDPTW 600-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_6_1 60 14095.64* RP 14-jul-03
lc1_6_2 57 15048.16 CLS 13-jan-16
lc1_6_3 49 14874.68 SCR 31-Mar-20
lc1_6_4 47 13300.55 HW 11-Jun-21
lc1_6_5s 60 14086.30 Li & Lim 2001
lc1_6_6s 60 14090.79 RP 14-jul-03
lc1_6_7 60 14083.76 SAM::OPT 13-jul-03
lc1_6_8 58 14880.70 CLS 08-dec-15
lc1_6_9 53 15207.58 SCR 31-Dec-19
lc1_6_10 51 15432.55 SCR 19-Dec-21
 
lc2_6_1 19 7977.98 SAM::OPT 14-jul-03
lc2_6_2 18 9900.48 SCR 31-Dec-19
lc2_6_3 17 8512.94 SCR 01-Dec-20
lc2_6_4 17 7860.38 SCR 05-Nov-19
lc2_6_5 18 9051.53 CVB2 17-jan-19
lc2_6_6 18 8775.55 SCR 05-Nov-19
lc2_6_7 18 9376.58 SCR 05-Nov-19
lc2_6_8q 18 7579.93 RP 14-jul-03
lc2_6_9 18 8714.22 SCR 19-Dec-21
lc2_6_10 17 7946.60 SCR 05-Nov-19
 
lr1_6_1 59 22821.65 CLS 17-mar-17
lr1_6_2 45 20137.22 SB 30-jan-19
lr1_6_3 37 17846.17 SCR 05-Nov-19
lr1_6_4 28 13127.56 SCR 05-Nov-19
lr1_6_5 37 23623.52 HW 26-Feb-21
lr1_6_6 30 23084.50 SCR 19-Dec-21
lr1_6_7 24 16963.37 SCR 22-Apr-21
lr1_6_8 18 11917.70 SCR 19-Dec-21
lr1_6_9 31 21835.87 SCR 05-Nov-19
lr1_6_10 25 19298.25 SCR 19-Dec-21
 
lr2_6_1 11 21759.33 SB 30-jan-19
lr2_6_2 9 21289.70 HW 26-Feb-21
lr2_6_3 7 17480.06 SCR 22-Apr-21
lr2_6_4 6 10639.08 SCR 05-Nov-19
lr2_6_5 8 22625.89 HW 26-Feb-21
lr2_6_6 7 19099.49 SCR 01-Dec-20
lr2_6_7 6 14645.32 SCR 19-Dec-21
lr2_6_8 4 12341.90 SCR 19-Dec-21
lr2_6_9 8 18259.20 SCR 05-Nov-19
lr2_6_10 7 16390.64 SCR 05-Nov-19
 
lrc1_6_1 52 18288.90 SB 30-jan-19
lrc1_6_2 43 16515.41 SB 30-jan-19
lrc1_6_3 36 13975.98 SCR 05-Nov-19
lrc1_6_4 25 10800.44 SCR 05-Nov-19
lrc1_6_5 45 17463.94 HW 30-Nov-20
lrc1_6_6 41 19025.36 HW 30-Nov-20
lrc1_6_7 37 15914.85 HW 30-Nov-20
lrc1_6_8 33 15317.63 SCR 05-Nov-19
lrc1_6_9 33 15344.64 HW 30-Nov-20
lrc1_6_10 29 13963.66 SCR 05-Nov-19
 
lrc2_6_1 16 14578.92 SCR 05-Nov-19
lrc2_6_2 13 13850.22 SCR 05-Nov-19
lrc2_6_3 10 12432.91 SCR 05-Nov-19
lrc2_6_4 7 9833.92 SCR 05-Nov-19
lrc2_6_5 13 14380.37 HW 05-Dec-20
lrc2_6_6 12 14962.08 HW 30-Nov-20
lrc2_6_7 10 14094.26 HW 02-Dec-20
lrc2_6_8 9 13179.58 SCR 19-Dec-21
lrc2_6_9 8 16309.78 SCR 19-Dec-21
lrc2_6_10 7 13054.50 SCR 05-Nov-19
       
k: Detailed solution provided by K
q: Detailed solution provided by Q
s: Detailed solution provided by SAM::OPT
*: Li & Lim report  60/14095.60, maybe due to a rounding error. 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). 
CAINIAO - Zhu He, Longfei Wang, Haoyuan Hu (haoyuan.huhy@cainiao.com), 
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 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.
HW - Zhu He, Weibo Lin (linweibo@huawei.com), 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.
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).
SCR - Piotr Sielski (piotr.sielski@wmii.uni.lodz.pl), Piotr Cybula, Marek Rogalski (marek.rogalski@wmii.uni.lodz.pl), 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.
Shobb - http://shobb.narod.ru/vrppd.html

 

Published April 18, 2008