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 100 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 100-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.
s: Detailed solution provided by SAM::OPT
* The value 585.56 reported by Li & Lim and also here earlier does not seem compatible with the optimal solution value 591.2 reported in Røpke's PhD Thesis (see R below). We thank Richard Kelly at Monash University for pointing this out.
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).
Q - Quintiq. http://www.quintiq.com/optimization-world-records.aspx.
R - Ropke S. Heuristic and exact algorithms for vehicle routing problems. (2005) . Ph.D. thesis, Computer Science Department, University of Copenhagen (DIKU), Copenhagen