The vehicle routing problem: Algorithms and applications

The Vehicle Routing Problem (VRP) is a hard and very well-known combinatorial optimization problem which finds many practical applications in the design and management of distribution systems. The VRP is concerned with the design of optimal routes used by a set of identical vehicles stationed at a central depot to serve a set of customers with known demands. In the basic version of the problem, known as Capacitated VRP (CVRP), only the capacity restrictions for the vehicles are considered and the objective is to minimize the total cost (or length) of the routes. CVRP is one of the most studied problems in the combinatorial optimization field and it has served as a benchmark for almost all exact and heuristic solution techniques: a recent complete survey on CVRP can be found in the first six chapters of the book edited by Toth and Vigo [1]. The aim of the first part of this talk is to provide a comprehensive overview of the techniques available for the exact and heuristic solution of CVRP, most of which have been also used to solve other important variants of the VRP, as the VRP with Time Windows or the VRP with Backhauls. The large majority of solutions approaches for the CVRP have been developed for the so-called symmetric version, i.e., where the traveling cost between any pair of customers is the same in both directions. Therefore, we mainly concentrate on the symmetric CVRP and just mention the most relevant results available for the asymmetric version. The exact approaches presented in the last two decades for the solution of CVRP were algorithms based on branch-and-bound, including those that make use of the set partitioning formulation and column generation schemes, and algorithms based on branch-and-cut. However, despite the great effectiveness reached in the solution of other related problems as the Traveling Salesman Problem (TSP), for which we can now solve huge instances to optimality, the exact methods currently available for the CVRP are still far from being able to consistently solve large instances. Indeed, the best available algorithms may now solve instances with about 50 customers within a reasonable amount of time, but this is still not enough for a practical use. An impressive amount of heuristic algorithms has been developed for the solution of CVRP. In the first phase these were mainly classical route construction algorithms, whereas more recently also effective metaheuristic approaches were developed. Classical heuristics may be roughly classified into three groups: route construction methods, two-phase methods, and route improvement methods. Metaheuristic paradigms have extended simple local search approaches by devising techniques that allow escaping from local minima, and continue the search towards possibly better solutions. Almost all different metaheuristic paradigms were applied for the solution of CVRP: Simulated Annealing, Deterministic Annealing, Tabu Search, Genetic Algorithms, Ant Systems, Neural Networks, ... All these approaches proved able to improve classical methods at the expense of larger computing requirements. In the second part of this talk we discuss some practical applications we recently faced in the design and optimization of distribution systems. The aim of the presentation is twofold. On the one hand, we want to highlight some relevant characteristics of real-world routing applications, as the aggregation of multiple trips within working days, that may lead to new interesting and difficult extensions of basic VRPs. On the other hand, we want to illustrate the benefits that may be achieved by introducing optimization algorithms within route planning support systems. References: [1] P. Toth, D. Vigo (editors), The Vehicle Routing Problem. Monographs on Discrete Mathematics and Applications. S.I.A.M., Philadelpia, PA, 2002.