Split Library
A simple implementation, in C++, of Split algorithms for the vehicle routing problem is provided in this package, along with some additional test instances. The library includes a O(n) split algorithm for the CVRP, introduced in: "Vidal, T. (2016). Technical note: Split algorithm in O(n) for the capacitated vehicle routing problem. Computers & Operations Research. 69, 40–47. Available HERE. This code is distributed for research purposes. All rights reserved. The computational complexity of each algorithm in the library is listed below, for a problem with n delivery points and a limit B on the number of deliveries per route (as a consequence of capacity constraints):| Algorithm: | Complexity: |
|---|---|
| Bellman-Based Split algorithm | O(nB) |
| Bellman-Based Split algorithm with a fleet-size limit m | O(nBm) |
| Bellman-Based Split algorithm with soft capacity constraints | O(n²) |
| Linear Split algorithm | O(n) |
| Linear Split algorithm with a fleet-size limit m | O(nm) |
| Linear Split algorithm with soft capacity constraints | O(n) |
Benchmark instances
MVRPB : The instances for the multi-period VRP with workload balance (MVRPB), presented in "Nekooghadirli, N., Gendreau, M., Potvin, J.-Y., & Vidal, T. (2022). Workload equity in multi-period vehicle routing problems. Technical Report", can be found HERE along with a description of the format.
E2EVRP : The instances for the Electric Two-echelon Vehicle Routing Problem (E2EVRP), presented in "Breunig, U., Baldacci, R., Hartl, R., & Vidal, T. (2019). The Electric Two-echelon Vehicle Routing Problem. Computers & Operations Research, 103, 198-210", can be found HERE along with a description of the format.
MPDPSL : The instances for the multi-vehicle pickup-and-delivery problem with split deliveries (MPDPSL), presented in "Haddad, M. N., Martinelli, R., Vidal, T., Martins, S., Ochi, L. S., Souza, M. J. F., & Hartl (2018). Large Neighborhood-Based Metaheuristic and Branch-and-Price for the Pickup and Delivery Problem with Split Loads" European Journal of Operational Research, 270(3), 1014–1027", can be found HERE along with a description of the format.
VRP-SL : The instances for the VRP with Service Level Constraints, presented in "Bulhões, T., Hà, M. H., Martinelli, R. & Vidal, T. (2018). The Vehicle Routing Problem with Service Level Constraints" European Journal of Operational Research, 265(2), 544–558", can be found HERE along with a description of the format.
NEARP-TP : New benchmark instances for node, edge and arc routing problems with turn penalties, presented in "Vidal, T. (2017) Node, Edge, Arc Routing and Turn penalties: Multiple problems -- One Neighborhood Extension" Operations Research 65(4), 992–1010, can be found HERE along with a description of the format.
CVRP : New larger-scale instances for the classical Vehicle Routing Problem, presented in "Uchoa, E., Pecin, D., Pessoa, A., Poggi, M., Subramanian, A., and Vidal, T. (2017) New Benchmark Instances for the Capacitated Vehicle Routing Problem. European Journal of Operational Research, 257(3), 845-858" can be found on the Webpage of the CVRP-Lib.
PRP : The additional benchmark instances for the pollution routing problem, containing tighter time windows, used in "Kramer, R., Subramanian, A., Vidal, T., Cabral, L.A.F. (2015) A matheuristic approach for the Pollution-Routing Problem. European Journal of Operational Research. In Press" can be found HERE along with a description of the format. The best found solutions are listed HERE.
MDVRPTW, PVRPTW, SDVRPTW : The large-scale benchmark instances for the multi-depot VRPTW, the multi-period VRPTW and the site dependent VRPTW used in "Vidal, T., Crainic, T.G., Gendreau, M., Prins, C. (2013) A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows Computers & Operations Research., 40(1), 475-489." can be found HERE. along with a description of the format.
MDPVRP : The benchmark instances for the multi-depot periodic vehicle routing problem, used in "Vidal, T., Crainic, T.G., Gendreau, M., Lahrichi, N., Rei, W. (2012) A hybrid genetic algorithm for multi-depot and periodic vehicle routing problems Operations Research., 60(3), 611-624." can be found HERE along with a description of the format.
MLP : The instances for the Minimum Latency Problem (MLP), presented in "Silva, M. M., Subramanian, A., Vidal, T., & Ochi, L. S. (2012). A simple and effective metaheuristic for the minimum latency problem. European Journal of Operational Research", 221(3), 513–520. can be found HERE and HERE along with a description of the format.
Other repositories for vehicle routing problem benchmark instances
Other sets of instances can be found on several webpages, including Chaire de Distributique, maintainted by J.-F. Cordeau --> Including the original test instances for the CVRP, MDVRP, PVRP, DARP and many other important problem variants. Transportation Optimization Portal of SINTEF Applied Mathematics --> Very well maintained repository for VRPTW, PDPTW, and NEARP benchmark instances. Website maintained by Stefan Irnich --> All recent CARP benchmark instances in a unified solution format. Website of Stefan Ropke --> Multiple sets of benchmark instances for variants of vehicle routing problems with backhauls, as well as PDPTW and CVRP. Webpage of the VRP-Rep --> Recent collaborative repository for instances of vehicle routing problem
Supplementary article materials
The source code, instances and detailed results of the paper "Arnold, F., Santana, Í. G., Sörensen, K., & Vidal, T. (2021). PILS: Exploring high-order neighborhoods by pattern mining and injection. Pattern Recognition", are available HERE.
The detailed results of the paper "Goel, A., Vidal, T., & Kok, A. L. (2020). To team up or not: Single versus team driving in European road freight transport. Flexible Services and Manufacturing Journal", are available HERE.
The detailed results of the paper "Homsi, G., Martinelli, R., Vidal, T., & Fagerholt, K. (2020). Industrial and tramp ship routing problems: Closing the gap for real-scale instances. European Journal of Operational Research 283, 972-990", are available HERE, and the new larger benchmark instances are available HERE.
The detailed results of the paper "Bulhões, T., Hà, M. H., Martinelli, R. & Vidal, T. (2018). The Vehicle Routing Problem with Service Level Constraints European Journal of Operational Research 265(2), 544–558", are available HERE.
In the paper entitled "Vidal, T. (2017) Node, Edge, Arc Routing and Turn penalties: Multiple problems -- One Neighborhood Extension Operations Research , a summary of new experimental results has been presented for 16 benchmark instances sets, and overall 1528 problem instances. The detailed result tables are available as appendix of the technical report, located HERE. An excel file with the same results can also be found HERE.
In the paper entitled "T. Vidal, N. Maculan, L.S. Ochi, and P.H.V. Penna (2016). Large neighborhoods with implicit customer selection for vehicle routing problems with profits. Transportation Science", 50(2), 720-734, a summary of experimental results has been presented for the team-orienteering problem (TOP), the capacitated profitable tour problem (CPTP), and the VRP with private fleet and common carrier (VRPPFCC). The detailed result tables be downloaded HERE and in THIS EXCEL FILE which also provides the detailed CPU times.
The detailed results and solutions of the paper "Kramer, R., Maculan, N., Subramanian, A., Vidal, T. (2015). A speed and departure time optimization algorithm for the Pollution-Routing Problem. European Journal of Operational Research", 247(3), 782-787 are available as an electronic companion: HERE.
In the paper entitled "Vidal, T., Crainic, T. G., Gendreau, M., & Prins, C. (2014). A Unified Solution Framework for Multi-Attribute Vehicle Routing Problems. European Journal of Operational Research, 234(3), 658-673", a summary of new experimental results has been presented for 29 problems, 42 benchmark instances sets, and overall 1099 problems. The detailed result tables is available as an electronic companion. They can also be downloaded HERE.