Heuristics for vehicle routing problems: Current challenges and future prospects

Vehicle Routing Problems (VRP) involve designing least-cost delivery routes to visit a geographically-dispersed set of customers. Over the past 60 years, this class of problems has been the subject of considerable work, summing up to thousands of articles. In 2017, we can reasonably say that the classical "capacitated" VRP (with only capacity constraints) is fairly well solved by metaheuristic techniques. Yet, the research on VRPs keeps on expanding even further, as a consequence of the increasing diversity of applications, which bring forth new difficult constraints, objectives, and combined decisions to account for customer's needs, vehicle and network restrictions, and to better integrate VRP optimization in the decision chains. Moreover, with the advent of collaborative logistics, green initiatives, smart cities, multi-modal transport, in contexts where multiples stakeholders and conflicting objectives have to be considered jointly, or in the presence of dynamic problems with a short response time, the efficient resolution of these problems becomes even more critical.

In this talk, we will review some of the most challenging and recent VRP variants, and examine the heuristic solution techniques which are developed to tackle them. We will study the close connections between the structure of the problem decision sets, and the associated solution methods, showing how modern heuristics can effectively perform a search in a reduced space, defined by fewer groups of decision variables. A key challenge is to progress towards "unified" solution methods, which are not tailored for one single problem, but instead designed to solve a wide collection of problem variants with different constraints and objectives. For this purpose, we expose some of the main principles of the Unified Hybrid Genetic Search (UHGS), which has been recently extended to obtain state-of-the-art results --in a single code base-- for more than 50 difficult variants of vehicle routing and arc routing problems. Finally, in a last section of this talk, in collaboration with Piotr Matl (U. Vienna), we will review efficient extensions of UHGS to multi-objective problem settings including equity objectives, and the insights and paradoxes which arise from our computational experiments.

• To the presentations: https://w1.cirrelt.ca/~vidalt/en/publications-thibaut-vidal.html

• To the associated source code: https://github.com/vidalthi/HGS-CARP

• To the associated papers:
Part 1 -- single objective:
Vidal et al. (2012). A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research, 60(3), 611–624. https://doi.org/10.1287/opre.1120.1048
Vidal et al. (2013). Heuristics for multi-attribute vehicle routing problems: A survey and synthesis. European Journal of Operational Research, 231(1), 1–21. https://doi.org/10.1016/j.ejor.2013.02.053
Vidal et al. (2014). A unified solution framework for multi-attribute vehicle routing problems. European Journal of Operational Research, 234(3), 658–673. https://doi.org/10.1016/j.ejor.2013.09.045
Vidal, T. (2017). Node, edge, arc routing and turn penalties : Multiple problems -- One neighborhood extension. Operations Research, 65(4), 992–1010. https://doi.org/10.1287/opre.2017.1595
Toffolo, T.A.M., Vidal, T., & Wauters, T. (2018). Heuristics for vehicle routing problems: Sequence or set optimization? https://arxiv.org/pdf/1803.06062.pdf
Part 2 -- multi objective:
Matl, P., Hartl, R. F., & Vidal, T. (2018). Workload Equity in Vehicle Routing Problems: A Survey and Analysis. Transportation Science, 52(2), 239–260. https://arxiv.org/pdf/1605.08565.pdf
Matl, P., Hartl, R. F., & Vidal, T. (2018). Heuristic Rectangle Splitting: Leveraging Single-Objective Heuristics to Efficiently Solve Multi-Objective Problems. https://arxiv.org/pdf/1705.10174.pdf
Matl, P., Hartl, R., & Vidal, T. (2018). Workload Equity in Vehicle Routing : The Impact of Alternative Workload Resources. Retrieved from https://arxiv.org/pdf/1803.01795.pdf