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 .

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.

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.

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

NVIDIA - (Piotr Sielski, Akif Çördük, Nicolas Blin, Hugo Linsenmaier,  Rajesh Gandham, Alex Fender) NVIDIA cuOpt : GPU accelerated Operations Research and Optimization.

OT - Piotr Sielski, Piotr Cybula, Marek Rogalski (marek.rogalski@otimo.pro), Mariusz Kok, Przemysław Pełka, Krzysztof Chaładyn. Otimo (https://otimo.pro)

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

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

VR - Dmitriy Demin, Mikhail Diakov (msd@veeroute.com), Ivan Ilin, Nikita Ivanov, Viacheslav Sokolov (vs@veeroute.com) et al. VRt Global (https://veeroute.com/).

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.