Updates

Improved VRPTW solutions reported by Piotr Sielski, Piotr Cybula, Mariusz Kok, Przemysław Pełka, Marek Rogalski (Otimo, and University of Łódź, Poland): C1_6_10 (13617.5), C1_8_10 (24026.7), C2_10_4 (15459.5), R1_10_1 (53046.6), R1_4_3 (7784.3), R1_6_5 (19301.3), R1_6_9 (18476.4), R1_8_1 (36380.8), R2_10_7 (23102.2), R2_8_4 (13160.8), R2_8_6 (19740.5), RC1_4_5 (8152.3), RC1_6_3 (15181.3), RC1_8_10 (28173.0), RC1_8_2 (28309.4), RC1_8_3 (27451.1), RC1_8_4 (26574.6), RC1_8_5 (29249.9), RC1_8_6 (29198.8), RC1_8_7 (28795.2), RC1_8_8 (28420.9), RC1_8_9 (28356.9), RC2_10_3 (19624.3), RC2_10_9 (22731.6), RC2_6_10 (8974.7), RC2_8_10 (14374.9), RC2_8_2 (16709.5), RC2_8_4 (10969.4).

Improved VRPTW solutions reported by Piotr Sielski, Piotr Cybula, Mariusz Kok, Przemysław Pełka, Marek Rogalski (Otimo, and University of Łódź, Poland): C1_10_2 (41352.1), C1_10_8 (41652.1), C1_8_3 (24156.1), C1_8_8 (24810.1), C2_10_9 (16075.4), C2_6_4 (6877.0), C2_6_7 (7491.3), C2_8_4 (10650.3), R1_4_2 (8873.3), R2_10_10 (29850.7), R2_10_1 (36881.0), R2_10_2 (31241.9), R2_10_3 (24399.0), R2_10_5 (34132.8), R2_10_6 (29126.5), R2_10_9 (31990.6), R2_4_8 (4000.1), R2_6_10 (11837.0), R2_6_2 (12976.3), R2_6_5 (13790.2), R2_6_6 (11847.8), R2_6_9 (12736.8), R2_8_10 (19985.6), R2_8_1 (24969.8), R2_8_3 (17235.1), R2_8_5 (22801.6), R2_8_6 (19745.2), R2_8_7 (16359.7), R2_8_9 (21282.7), RC1_4_1 (8522.9), RC2_10_1 (28122.6), RC2_10_2 (24248.6), RC2_10_3 (19624.7), RC2_10_5 (25797.5), RC2_10_6 (25782.5), RC2_10_7 (24420.5), RC2_10_8 (23281.2), RC2_6_7 (10289.4), RC2_6_8 (9779.0), RC2_8_1 (19201.3), RC2_8_2 (16710.1), RC2_8_3 (14013.6), RC2_8_6 (17196.6), RC2_8_7 (16362.2), RC2_8_8 (15528.8).

Improved VRPTW solution reported by Piotr Sielski, Piotr Cybula, Mariusz Kok, Przemysław Pełka, Marek Rogalski (Otimo, and University of Łódź, Poland): RC1_4_10 (7581.2).

Improved solution reported by The-Viet Bui (Singapore Management University): Loggi-n501-k24 (177078).

Proven optimal solution by João Marcos Pereira Silva and Eduardo Uchoa using VRPSolver with a new cluster branching strategy: X-n256-k16 (18839).

Improved solutions reported by Francesco Cavaliere (University of Bologna, Italy), Matteo Fischetti (University of Padova, Italy), and Keld Helsgaun (Roskilde University, Denmark), obtained using the solver LKHSP: Antwerp2 (291350), Brussels1 (501719), Flanders1 (7240124), Flanders2 (4373320), Loggi-n401-k23 (336903), Loggi-n501-k24 (177176), Loggi-n901-k42 (246301).

CVRPLIB now also has benchmarks for the VRP with time windows (VRPTW). The benchmarks of Solomon (1987) and Homberger and Gehring (1999) have been included. Here we assume the convention of the 12th DIMACS Implementation Challenge and recent exact algorithms (Baldacci et al, 2011, Pecin et al, 2017, Pessoa et al, 2020, Sadykov et al, 2020), which is to minimize the total distance, where Euclidean distances are obtained from the location coordinates and then truncated to one decimal place. Some of the current BKSs were found by Thibaut Vidal with UHGS, some others by VRPSolver, whereas most of them were found by participants of the DIMACS challenge in a pre-competition phase as reported here. The BKSs for the hierarchical objective (usually adopted for heuristics in the literature) are already managed by the Transportation Optimization Portal of SINTEF Applied Mathematics.

Francesco Cavaliere (University of Bologna, Italy), Matteo Fischetti (University of Padova, Italy), and Keld Helsgaun (Roskilde University, Denmark), obtained using LKH-3 code for merging the previously best solutions with solutions obtained by solver LKHSP: Antwerp2 (291351), Brussels1 (501720), Brussels2 (345481), Flanders1 (7240141), Flanders2 (4373322).

New set XML100 (all instances with 100 customers), proposed in "10,000 optimal CVRP solutions for testing machine learning based heuristics" by Queiroga et al. A single zip file contains the instances, the optimal solutions, and the instance generator Python code.

Improved solutions obtained in the DIMACS Challenge by Mariá C.V. Nascimento (Universidade Federal de São Paulo), Vinícius R. Máximo (Universidade Federal de São Paulo), and Jean-François Cordeau (HEC Montréal) with the solver AILS-II: Loggi-n401-k23 (336915), Loggi-n501-k24 ((177351)), Loggi-n901-k42 (246384), ORTEC-n455-k41 (292485), ORTEC-n701-k64 (445543). Improved solution obtained in the DIMACS Challenge by Luca Accorsi (University of Bologna), Francesco Cavaliere (University of Bologna), and Daniele Vigo (University of Bologna) with the solver FSP4D: Golden_12 (1100.67).

Proven optimal DCVRP solution by João Marcos Pereira Silva using VRPSolver: CMT13 (1541.14).

Improved solutions reported by Simen T. Vadseth, Henrik Andersson, and Magnus Stålhane from NTNU: Antwerp2 (291353), Brussels1 (501721), Brussels2 (345482), Flanders1(7240144), Flanders2 (4373329), Ghent1 (469531).

Improved solutions obtained in the DIMACS Challenge by Solver LKHSP, from Team Vavavuma! (Francesco Cavaliere (University of Bologna), Matteo Fischetti (University of Padova, Italy), and Keld Helsgaun (Roskilde University, Denmark)): Brussels1 (501734), Brussels2 (345485), Flanders1 (7240218), Flanders2 (4373346), Ghent2 (257748), Leuven2 (111391).

Improved solution reported by Luca Accorsi (University of Bologna), Francesco Cavaliere (University of Bologna), and Daniele Vigo (University of Bologna): Golden_12 (1101.24).

Improved solutions reported by Luca Accorsi (University of Bologna), Francesco Cavaliere (University of Bologna), and Daniele Vigo (University of Bologna): Loggi-n601-k19 (113155), Loggi-n1001-k31 (284356).

Improved solutions reported by Simen T. Vadseth, Henrik Andersson, and Magnus Stålhane from NTNU using an improvement matheuristic: Brussels1 (501743), Brussels2 (345496), Flanders1(7240389), Flanders2 (4373440), Ghent2 (257749), Leuven2 (111395).

New set of real-world instances contributed to the DIMACS Challenge. Instances Loggi-n401-k23, Loggi-n501-k24, Loggi-n601-k19, Loggi-n601-k42, Loggi-n901-k42, Loggi-n1001-k31, kindly contributed by Loggi, extracted from a large dataset of real vehicle routing and facility location instances. Instances ORTEC-n242-k12, ORTEC-n323-k21, ORTEC-n405-k18, ORTEC-n455-k41, ORTEC-n510-k23, ORTEC-n701-k64, kindly contributed by Wouter Kool (ORTEC).

Improved solutions reported by Simen T. Vadseth, Henrik Andersson, and Magnus Stålhane from NTNU using an improvement matheuristic: Brussels2 (345505), Flanders2 (4373569), Ghent2 (257763).

Improved solution reported by Francesco Cavaliere (University of Bologna), Emilio Bendotti, Matteo Fischetti (University of Padova, Italy), and Keld Helsgaun (Roskilde University, Denmark): Flanders2 (4375178).

Proved optimal solutions using VRPSolver: X-n261-k13 (26558) and X-n856-k95 (88965).