Updates

Solution Updates

Any person or group can submit improving solutions to one of the authors of Uchoa et al. (2017). After the solutions are checked, they will be included in CVRPLIB.  On the other hand, claims of new optimal solutions will only be accepted if a citable reference (like a technical report) for the used method is provided. Each update in the status of an instance will be recorded chronologically in this tab.

  • November, 14 2020 - Improved solutions by Vinícius R. Máximo and Mariá C.V. Nascimento (Universidade Federal de São Paulo) with a hybrid adaptive Iterated Local Search with diversification control: X-n384-k52 (65938), X-n641-k35 (63692), X-n716-k35 (43379).
  • November, 6 2020 - Improved solutions by Eduardo Queiroga, Eduardo Uchoa, and Ruslan Sadykov through a POPMUSIC matheuristic: X-n401-k29 (66154), X-n491-k59 (66483), X-n536-k96 (94846), X-n733-k159 (136187), X-n749-k98 (77269), X-n766-k71 (114418), X-n783-k48 (72393), X-n936-k151 (132715), X-n979-k58 (118976), X-n1001-k43 (72355), Antwerp1 (477277), Brussels1 (501771), Flanders1 (7240874), Ghent1 (469532), Leuven1 (192848).
  • October, 12 2020 - Improved solutions by Thibaut Vidal using a modern implementation of the Hybrid Genetic Search of Vidal et al. (2012), specialized to the CVRP, with one additional neighborhood: Golden_3 (10997.8), Golden_4 (13588.6), Golden_6 (8400.33), Li_25 (16665.7), Li_27 (17320).
  • October, 10 2020 - Improved solutions reported by Francesco Cavaliere, Emilio Bendotti, and Matteo Fischetti (University of Padova): Antwerp2 (291400), Brussels1 (501854), Brussels2 (345565), Flanders1 (7241290), Flanders2 (4377626), Ghent1 (469586), Ghent2 (257958), Leuven2 (111489).
  • October, 3 2020 - Improved solution by Eduardo Queiroga, Eduardo Uchoa, and Ruslan Sadykov through a POPMUSIC heuristic using exact VRPSolver, starting from a solution with value 1611.70 provided by Luca Accorsi and Daniele Vigo: Golden_16 (1611.28).
  • October, 1 2020 - Improved solutions reported by Luca Accorsi and Daniele Vigo (University of Bologna): Golden_9 (579.70), Golden_10 (735.43), Golden_11 (911.98), Golden_15 (1337.27).
  • September, 24 2020 - Improved solutions by Thibaut Vidal using a modern implementation of the Hybrid Genetic Search of Vidal et al. (2012), specialized to the CVRP, with one additional neighborhood: Antwerp1 (477306), Antwerp2 (291410), Brussels1 (501856), Brussels2 (345585), Flanders1 (7241335), Flanders2 (4377928), Ghent1 (469587), Ghent2 (257972), Leuven2 (111490).
  • September, 21 2020 - Improved solutions by Thibaut Vidal using a modern implementation of the Hybrid Genetic Search of Vidal et al. (2012), specialized to the CVRP, with one additional neighborhood: X-n303-k21 (21736), X-n401-k29 (66163), X-n429-k61 (65449), X-n449-k29 (55233), X-n459-k26 (24139), X-n613-k62 (59535), X-n627-k43 (62164), X-n641-k35 (63694), X-n685-k75 (68205), X-n766-k71 (114454), X-n856-k95 (88965), X-n876-k59 (99299), X-n895-k37 (53860), X-n936-k151 (132725), X-n957-k87 (85465), X-n979-k58 (118987), X-n1001-k43 (72359).
  • September, 7 2020 - Improved solutions by Eduardo Queiroga, Eduardo Uchoa, and Ruslan Sadykov through a POPMUSIC heuristic using exact VRPSolver: Brussels1 (501868), Flanders1 (7241397), Ghent1 (469599).
  • August, 20 2020 - Improved solutions reported by Francesco Cavaliere, Emilio Bendotti, and Matteo Fischetti (University of Padova): X-n459-k26 (24140), X-n801-k40 (73305), X-n895-k37 (53870), Antwerp2 (291450), Brussels1 (501916), Brussels2 (345616), Flanders1 (7242182), Flanders2 (4377986), Ghent1 (469602), Ghent2 (258002).
  • August, 12 2020 - Improved solutions by Eduardo Queiroga, Eduardo Uchoa, and Ruslan Sadykov through a POPMUSIC heuristic using exact VRPSolver: X-n313-k71 (94043), Antwerp1 (477323), Brussels1 (501934), Flanders1 (7242464), Ghent1 (469604), Leuven1 (192851).
  • August, 8 2020 - Improved solutions reported by Francesco Cavaliere, Emilio Bendotti, and Matteo Fischetti (University of Padova): Antwerp1 (477535), Antwerp2 (291468), Brussels1 (502144), Brussels2 (345627), Flanders1 (7245214), Flanders2 (4378434), Ghent1 (469838), Ghent2 (258010), Leuven1 (192894), Leuven2 (111499).
  • July, 31 2020 - Improved solutions reported by Luca Accorsi and Daniele Vigo (University of Bologna): X-n459-k26 (24141), X-n801-k40 (73311), X-n895-k37 (53906), X-n957-k87 (85467), Antwerp1 (477618), Antwerp2 (291526), Brussels1 (502273), Brussels2 (345743), Flanders1 (7248395), Flanders2 (4382022), Ghent1 (469891), Ghent2 (258116), Leuven1 (192915), Leuven2 (111544).
  • July, 30 2020 - Improved solutions reported by Francesco Cavaliere, Emilio Bendotti, and Matteo Fischetti (University of Padova): Antwerp1 (478019), Antwerp2 (292511), Brussels1 (503350), Brussels2 (348740), Flanders1 (7256400), Flanders2 (4402841), Ghent1 (470306), Ghent2 (259486), Leuven1 (193059), Leuven2 (111794).
  • July, 25 2020 - Improved solution reported by Ben Johnson (Canfield Research):  Brussels2 (348861).
  • July, 24 2020 - Improved solution reported by Ben Johnson (Canfield Research):  Brussels1 (503377).
  • July, 23 2020 - Improved solutions reported by Ben Johnson (Canfield Research):  Flanders1 (7256462), Ghent2 (259594).
  • July, 17 2020 - Improved solution reported by Ben Johnson (Canfield Research): Leuven2 (111810).
  • July, 2 2020 - Improved solutions by Eduardo Queiroga, Eduardo Uchoa, and Ruslan Sadykov through a POPMUSIC heuristic using exact VRPSolver: X-n303-k21 (21738), X-n344-k43 (42050), X-n351-k40 (25896), X-n384-k52 (65940), X-n536-k96 (94868), X-n586-k159 (190316), X-n599-k92 (108451), X-n627-k43 (62173).
  • June, 17 2020 - Improved solutions reported by Francesco Cavaliere, Emilio Bendotti, and Matteo Fischetti (University of Padova): Antwerp1 (478091), Antwerp2 (292597), Brussels1 (503407), Brussels2 (349602), Flanders1 (7256529), Flanders2 (4405678), Ghent1 (470329), Ghent2 (259712), Leuven1 (193092), Leuven2 (111860).
  • June, 5 2020 - Improved solutions reported by Ante Galic from Mireo d.d. (Croatia): Antwerp1 (478286), Antwerp2 (293083), Brussels1 (503998), Brussels2 (351518), Flanders1 (7261371), Flanders2 (4417165), Ghent1 (470554), Ghent2 (260467), Leuven1 (193201), Leuven2 (112261).
  • May, 18 2020 - Improved solutions reported by Francesco Cavaliere, Emilio Bendotti, and Matteo Fischetti (University of Padova): Antwerp1 (478674), Antwerp2 (293802), Brussels1 (504023), Brussels2 (352012), Flanders1 (7270362), Flanders2 (4455217), Ghent1 (470818), Ghent2 (260553), Leuven1 (193220), Leuven2 (112280), X-n573-k30 (50673), X-n766-k71 (114456), X-n876-k59 (99303), X-n895-k37 (53928), X-n936-k151 (132812), X-n1001-k43 (72369).
  • May, 8 2020 - Improved solutions by Eduardo Queiroga, Eduardo Uchoa, and Ruslan Sadykov through a POPMUSIC heuristic using exact VRPSolver: X-n303-k21 (21739), X-n351-k40 (25917), X-n411-k19 (19712), X-n429-k61 (65467), X-n449-k29 (55254), X-n480-k70 (89449), X-n491-k59 (66487), X-n536-k96 (94872), X-n573-k30 (50678), X-n586-k159 (190357), X-n627-k43 (62178), X-n641-k35 (63705), X-n685-k75 (68225), X-n701-k44 (81923), X-n716-k35 (43387), X-n749-k98 (77314), X-n766-k71 (114487), X-n783-k48 (72394), X-n819-k171 (158121), X-n837-k142 (193737), X-n856-k95 (88990), X-n876-k59 (99309), X-n895-k37 (53930), X-n936-k151 (132813), X-n957-k87 (85469), X-n979-k58 (118988), X-n1001-k43 (72370).
  • May, 5 2020 - Improved solution reported by Van Hanh Pham (VNU-UET, ORLab team), Duc Dong Do (VNU-UET, ORLab team), and Minh Hoàng Hà (Phenikaa University, ORLab team): Flanders1 (7272223).
  • May, 3 2020 - Improved solutions reported by Francesco Cavaliere, Emilio Bendotti, and Matteo Fischetti (University of Padova): Antwerp1 (478775), Antwerp2 (293953), Brussels1 (504175), Brussels2 (352658), Flanders1 (7272444), Flanders2 (4469477), Ghent1 (470902), Ghent2 (260987), Leuven1 (193244), Leuven2 (112378), X-n351-k40 (25919), X-n384-k52 (65941), X-n536-k96 (94921), X-n561-k42 (42717), X-n573-k30 (50708), X-n641-k35 (63723), X-n670-k130 (146332), X-n685-k75 (68245), X-n716-k35 (43412), X-n819-k171 (158247), X-n876-k59 (99330), X-n895-k37 (53935), X-n936-k151 (132881), X-n957-k87 (85474), X-n979-k58 (118996), X-n1001-k43 (72397).
  • January, 17 2020 -  Improved solutions by Eduardo Queiroga through a POPMUSIC heuristic using exact VRPSolver: X-n336-k84 (139111), X-n480-k70 (89457), X-n491-k59 (66503), X-n502-k39 (69226), X-n536-k96 (94950), X-n586-k159 (190368), X-n599-k92 (108455), X-n613-k62 (59545), X-n670-k130 (146446), X-n685-k75 (68252), X-n733-k159 (136190), X-n749-k98 (77353), X-n766-k71 (114501), X-n819-k171 (158249), X-n837-k142 (193752), X-n856-k95 (88997), X-n916-k207 (329179), X-n936-k151 (132907).
  • July, 14 2019 -  Improved solutions to the very large Belgium instances by Ante Galic: Antwerp1 (479021), Antwerp2 (294319), Brussels1 (504392), Brussels2 (353285), Flanders1 (7273695), Flanders2 (4480972), Ghent1 (471084), Ghent2 (261676), Leuven1 (193343), Leuven2 (112751).
  • April, 10 2019 - Improved solutions to the very large Belgium instances by Keld Helsgaun using LKH-3: Antwerp1 (480140), Antwerp2 (294940), Brussels1 (505755), Brussels2 (354789), Flanders1 (7279086), Flanders2 (4499188), Ghent1 (472202), Ghent2 (263506), Leuven1 (194095), Leuven2 (112998).
  • March, 1st 2019 - Improved and proven optimal solutions by Pessoa et al. (2019): X-n284-k15 (20215), X-n322-k28 (29834), X-n393-k38 (38260), X-n469-k138 (221824) and X-n548-k50 (86700).
  • February, 28th 2019 - Proved optimal DCVRP solutions by Sadykov et al. (2017): CMT6 (555.43), CMT7 (909.68), CMT8 (865.94), CMT9 (1162.55), CMT10 (1395.85), CMT14 (866.37).
  • January, 22th 2019- New set of very large instances (3,000 to 30,000 customers, from Belgium) by Arnold, Gendreau and Sörensen.
  • September, 15th 2018- Improved solutions reported by Vu Hoang Vuong Nguyen, Duc Dong Do, Hoang Duc Nguyen, and Minh Hoàng Hà (Vietnam National University ORLab): X-n573-k30(50717), X-670-k130(146476), X-837-k142(193809) and X-n1001-k43(72402).
  • February, 23rd 2018- Improved solutions reported by Keld Helsgaun using LKH-3: X-n524-k153 (154593), X-n573-k30 (50718), X-n599-k92 (108489), X-n819-k171 (158265), X-n837-k142 (193810), X-n856-k95 (89002), X-n936-k151 (132923), X-n957-k87 (85478) and X-n1001-k43 (72403).
  • August, 14th 2017 - Improved solutions reported (Toffolo, Vidal, Wauters (2017), Heuristics for vehicle routing problems: Sequence or set optimization?, to appear as a working paper): X-n294-k50 (47161), X-n322-k28 (29834), X-n327-k20 (27532), X-n344-k43 (42056), X-n393-k38 (38260) and X-n459-k26 (24145).
  • November, 23rd 2016 - Improved solutions reported by Jan Christiaens obtained using ASB-RRX-n359-k29 (51505), X-n384-k52 (65943), X-n401-k29 (66187), X-n449-k29 (55269), X-n459-k26 (24173), X-n491-k59 (66510), X-n502-k39 (69230), X-n536-k96 (94988), X-n561-k42 (42722), X-n599-k92 (108490), X-n627-k43 (62210), X-n670-k130 (146451), X-n685-k75 (68261), X-n701-k44 (81934), X-n716-k35 (43414), X-n749-k98 (77365), X-n766-k71 (114525), X-n783-k48 (72445), X-n801-k40 (73331), X-n837-k142 (193813), X-n876-k59 (99331), X-n895-k37 (53946), X-n916-k207 (329247), X-n936-k151 (132926) and X-n957-k87 (85482).
  • November, 6th 2016 - Improved solution to X-n256-k16 (18839) reported by Túlio Toffolo and Thibaut Vidal. This contradicts a previous claim that a solution with value 18880 was optimal. After investigation, it was found that a typo in a script made the BCP method (Pecin et al., 2014) to be run with a minimum of 17 routes. The improving solution has 16 routes. The status of that instance is also corrected to "open".
  • April, 25th 2016 - Proven optimal solutions by the BCP method (Pecin et al., 2014): X-n214-k11 (10856) and X-n233-k16 (19230).
  • April, 4th 2016 -Improved and proven optimal solutions by the BCP method (Pecin et al., 2014): X-n331-k15 (31102) and X-n439-k37 (36391).
  • April, 1st 2016 - Improved solutions reported by Jan Christiaens: X-n322-k28 (29848), X-n336-k84 (139135), X-n344-k43 (42068), X-n351-k40 (25928), X-n384-k52 (65981), X-n401-k29 (66202), X-n449-k29 (55302), X-n459-k26 (24179), X-n480-k70 (89458), X-n491-k59 (66520), X-n502-k39 (69232), X-n536-k96 (94991), X-n548-k50 (86701), X-n573-k30 (50719), X-n586-k159 (190423), X-n599-k92 (108541), X-n613-k62 (59556), X-n627-k43 (62217), X-n641-k35 (63737), X-n670-k130 (146477), X-n685-k75 (68276), X-n701-k44 (81962), X-n716-k35 (43441), X-n733-k159 (136250), X-n749-k98 (77402), X-n766-k71 (114534), X-n783-k48 (72453), X-n801-k40 (73344), X-n819-k171 (158267), X-n837-k142 (193836), X-n856-k95 (89007), X-n876-k59 (99360), X-n895-k37 (53948), X-n916-k207 (329299), X-n957-k87 (85517), X-n979-k58 (119008) and X-n1001-k43 (72404).
  • June, 22nd 2015 - Improved solutions reported by Jan Christiaens: X-n322-k28 (29854), X-n336-k84 (139165), X-n344-k43 (42073), X-n351-k40 (25936), X-n384-k52 (66021), X-n401-k29 (66219), X-n480-k70 (89488), X-n491-k59 (66523), X-n536-k96 (95062), X-n561-k42 (42754), X-n573-k30 (50726), X-n586-k159 (190454), X-n599-k92 (108600), X-n627-k43 (62264), X-n641-k35 (63760), X-n670-k130 (146570), X-n685-k75 (68291), X-n701-k44 (81997), X-n716-k35 (43491), X-n733-k159 (136313), X-n749-k98 (77423), X-n766-k71 (114566), X-n783-k48 (72547), X-n801-k40 (73367), X-n819-k171 (158298), X-n837-k142 (193933), X-n856-k95 (89040), X-n876-k59 (99424), X-n895-k37 (54030), X-n916-k207 (329394), X-n936-k151 (132946), X-n957-k87 (85566), X-n979-k58 (119072) and X-n1001-k43 (72477).
  • April, 10th 2015 - Proven optimal solutions by the BCP method (Pecin et al., 2014): G13 (857.19), X-n190-k8 (16980).
  • January, 5th 2015 - Improved and proven optimal BKSs by the BCP method (Pecin et al., 2014): G20 (1817.59), X-n289-k60 (95151).
  • January, 5th 2015 - Improved solutions by the UHGS method (Vidal et al., 2014): X-n327-k20 (27546), X-n336-k84 (139172), X-n344-k43 (42092), X-n429-k61 (65483), X-n449-k29(55355), X-n586-k159 (190491), X-n599-k92 (108736), X-n613-k62 (59584), X-n685-k75 (68415), X-n701-k44 (82254), X-n716-k35 (43517), X-n783-k48 (72715), X-n801-k40 (73564), X-n819-k171 (158558), X-n837-k142 (194187), X-n876-k59 (99653), X-n895-k37 (54071), X-n916-k207 (329752), X-n936-k151 (133046), X-n957-k87 (85663) and X-n1001-k43 (72719).
  • November, 20th 2014 - Improved solution values by the CPM method from the paper (Jin et al., 2014): G4 (590.00), G10 (735.66), G11 (912.03), G12 (1101.50), G15 (1337.87) and G16 (1611.56). We could not obtain those solutions yet!
  • October, 16th 2014 - Official release of CVRPLIB. The status of each instance was obtained either from the literature or from new experiments with state-of-the-art algorithms, as described in Uchoa et al. (2017).