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

The instances LRC2_10_8 and LRC2_10_9 were not present in the original data sent to us by Li  & Lim. Supposedly they forgot to include them. If you happen to have these definitions, we would very much appreciate if you could forward them to top-request@sintef.no .

 

Instance Vehicles Distance Reference Date
lc1_10_1* 100 42488.66 SAM::OPT 23-apr-03
lc1_10_2 94 44548.51 SB 30-jan-19
lc1_10_3 79 44692.86 CAINIAO 20-Apr-20
lc1_10_4 73 37515.04 SCR 31-Dec-19
lc1_10_5* 100 42477.40 SAM::OPT 10-aug-03
lc1_10_6 101 42838.39 SAM::OPT 11-aug-03
lc1_10_7s 100 42854.99 TS 2003
lc1_10_8 98 42949.56 Shobb 31-mar-18
lc1_10_9 91 42504.05 SCR 05-Nov-19
lc1_10_10 87 42008.65 SCR May-19
 
lc2_10_1s 30 16879.24 TS 2003
lc2_10_2 30 20901.56 SCR 05-Nov-19
lc2_10_3 29 19325.04 SCR 27-Feb-20
lc2_10_4 29 17886.97 SCR 05-Nov-19
lc2_10_5k 31 17137.53 RP 25-feb-05
lc2_10_6 31 17194.08 SB 30-jan-19
lc2_10_7 31 18389.37 SCR 05-Nov-19
lc2_10_8 30 17015.03 SB 30-jan-19
lc2_10_9 30 18225.30 SCR 05-Nov-19
lc2_10_10 29 17043.64 SCR 05-Nov-19
 
lr1_10_1¤ 100 56744.91 MFS 22-aug-18
lr1_10_2 80 49349.84 SCR 05-Nov-19
lr1_10_3 54 41609.41 SCR 05-Nov-19
lr1_10_4 27 30925.04 SCR 31-Dec-19
lr1_10_5 58 59894.44 WM 28-Nov-19
lr1_10_6 47 49286.15 SCR 05-Nov-19
lr1_10_7 35 38900.06 SCR 27-Feb-20
lr1_10_8 24 30101.67 CAINIAO 13-Mar-20
lr1_10_9 48 52123.26 CAINIAO 13-Mar20
lr1_10_10 38 45956.67 SCR 05-Nov-19
 
lr2_10_1 17 63318.21 WM 28-Nov-19
lr2_10_2 14 51763.32 SCR 31-Dec-19
lr2_10_3 10 42954.99 CAINIAO 23-Mar-20
lr2_10_4 8 26626.55 SCR 31-Dec-19
lr2_10_5 13 55598.25 SCR 05-Nov-19
lr2_10_6 11 46270.87 SCR 31-Dec-19
lr2_10_7 8 43212.14 CAINIAO 23-Mar-20
lr2_10_8 6 26753.61 SCR 31-Dec-19
lr2_10_9 12 51260.99 SCR 31-Dec-19
lr2_10_10 10 46602.27 SCR 05-Nov-19
 
lrc1_10_1 82 49111.78 SB 30-jan-19
lrc1_10_2 71 45548.30 CAINIAO 13-Mar-20
lrc1_10_3 53 35626.03 SCR 31-Mar-20
lrc1_10_4 40 27264.59 SCR 05-Nov-19
lrc1_10_5 72 50324.57 CAINIAO 13-Mar-20
lrc1_10_6 67 45153.83 MFS 23-feb-19
lrc1_10_7 60 41762.77 SCR 31-Dec-19
lrc1_10_8 55 41717.75 SCR 27-Feb-20
lrc1_10_9 53 39362.93 SCR 27-Feb-20
lrc1_10_10 47 36684.14 SCR 31-Dec-19
 
lrc2_10_1 22 34463.46 SCR 05-Nov-19
lrc2_10_2 19 39078.66 Shobb 14-sep-19
lrc2_10_3 16 27313.10 SCR 27-Feb-20
lrc2_10_4 11 23256.89 SCR 31-Dec-19
lrc2_10_5 16 40855.24 SCR 27-Feb-20
lrc2_10_6 17 30910.65 SCR 05-Nov-19
lrc2_10_7 15 33275.24 SCR 31-Dec-19
lrc2_10_8 - - - -
lrc2_10_9 - - - -
lrc2_10_10 11 29210.42 SCR 05-Nov-19
       

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

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.

K – Richard Kelly: Hybrid Ejection Chains and Adaptive LNS for the PDPTW. Working paper.

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

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 (psielski@emapa.pl), 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.

Shobb - http://shobb.narod.ru/vrppd.html

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

WM - Ganzhong Luo (luoganzhong@water-mirror.com), Lei Gao (gaolei@water-mirror.com), Zhixin Liu, Yaning Li, Mingxiang Chen, Qichang Chen, Nuoyi Zhu. "New Algorithms for VRPTW & PDPTW", unpublished result of WATERMIRROR AI.

Published April 18, 2008