(434e) A Hybrid Approach for the Exact Solution of the Capacitated Vehicle Routing Problem

Efficient distribution logistics is a strategic goal of modern corporations which strive to achieve excellent customer service while maintaining their investment and operational costs to a minimum. Because of this great economic ?as well as environmental? importance, it is not surprising that the Vehicle Routing Problem (VRP) has evolved as one of the core operations research and combinatorial optimization problem classes and has received a lot of attention from the scientific community since its formal introduction in the 1950s [1]. Unlike the well-known Travelling Salesman Problem (TSP), where instances with several thousand nodes can be solved optimally on a regular basis [2,3], instances of VRP with more than one hundred customers can be intractably hard to solve to optimality and exact methods are confined to limited-size instances [4,5].

In this presentation, we address the so-called ?Capacitated Vehicle Routing Problem? (CVRP). The CVRP considers a fleet of identical finite-capacity vehicles stationed at a depot. The objective is to identify the least cost set of round-trip routes that the vehicles must follow to serve a set of geographically scattered customers. Each customer has a fixed, a priori known, demand and the routes must be designed such that each customer is visited only once by exactly one vehicle. Clearly, the CVRP can be viewed as a direct generalization of the TSP, with additional complexity arising due to need for assigning the set of customers into multiple TSP-optimal routes.

Previous efforts for the CVRP can be classified into exact and approximate methods. The former are based on standard Mathematical Programming techniques, such as branch-and-cut [6] or branch-and-cut-and-price [7,8] and, despite offering theoretical proof for reaching an optimal solution, they lack the ability to solve large scale problem instances that are of industrial interest. On the other hand, approximate methods include local search based metaheuristic algorithms, evolutionary algorithms and hybrid algorithmic schemes, such as memetic algorithms [9] and adaptive memory programming [10]. These methods have made significant contributions toward tackling industrial problems with thousands of customers, however their majority fails to provide a good compromise between quality and speed, while they offer no guarantee for the optimality (or distance there from) of their solutions.

In this work, we propose a novel intertwined hybrid solution approach that exploits synergies among exact and metaheuristic algorithms. The overall approach is exact, that is, it maintains the theoretical guarantee of reaching an optimal solution, but relies heavily on problem-specific heuristic components to accelerate the search. In particular, we propose a two-level solution framework based on the two-commodity flow representation of the CVRP [11]. During the outer level, a soft branching decomposition scheme based on Hamming distance restrictions is iteratively applied to confine and partition the solution space. This partitioning is aided by a local search-based Path-Relinking algorithm that produces high quality integer feasible solutions derived from partial solution information. At the inner level, each solution subspace is solved via a new branch-and-cut algorithm that includes new constraint lifting and sophisticated heuristic-based cut separation procedures. At each node of the solution tree, a subordinate adaptive memory programming procedure [10,12] is employed to inform branching decisions and efficiently guide the tree search process. Conversely, knowledge extracted from the relaxation solution at each node is used to identify high quality integer feasible solutions, to update the adaptive memory structures reactively and, therefore, to accelerate the updating of the incumbent. Computational experiments on benchmark data sets from the literature [13] illustrate the competitiveness of the proposed solution approach.

References

[1] Laporte G. ?Fifty years of vehicle routing?, Transportation Science, 43(4):408-416 (2009).

[2] (Gutin and Punnen, 2002)

[3] Miller D.L. and J.F. Pekny. ?Exact solution of large asymmetric travelling salesman problems?, Science, 251:754-761 (1991).

[4] Baldacci R., P. Toth and D. Vigo. ?Exact algorithms for routing problems under vehicle capacity constraints?, Annals of Operations Research, 175(1):213-245 (2010).

[5] Gendreau M. and C.D. Tarantilis. ?Solving large-scale vehicle routing problems with time windows: The state-of-the-art?, Technical Report CIRRELT?2010-04, (2010).

[6] Lysgaard J., A.N. Letchford and R.W. Eglese. ?A new branch-and-cut algorithm for the capacitated vehicle routing problem?. Mathematical Programming, Ser.A 100:423-445 (2004).

[7] Baldacci R., N. Christofides and A. Mingozzi. ?An exact algorithmfor for the vehicle routing problem based on the set partitioning formulation with additional cuts?, Mathematical Programming, Ser.A 115:351-385 (2008).

[8] Fukasawa R., H. Longo, J. Lysgaard, M.P. de Aragao, M. Reis, E. Uchoa and R.F. Werneck. ?Robust branch-and-cut-and-price for the capacitated vehicle routing problem?. Mathematical Programming, Ser.A 106:491-511 (2006).

[9] Nagata Y., Bräysy O. ?Edge assembly based memetic algorithm for the Capacitated Vehicle Routing Problem?, Networks 54(4):205-214 (2009).

[10] Tarantilis C.D. ?Solving the vehicle routing problem with adaptive memory programming methodology?, Computer and Operations Research, 32(9):2309-2327 (2005).

[11] Baldacci R., E. Hadjiconstantinou and A. Mingozzi. ?An exact algorithmfor the capacitated vehicle routing problem based on a two-commodity network flow formulation?, Operations Research, 52(5):723-738 (2004).

[12] Repoussis P.P., C.D. Tarantilis and G. Ioannou. ?Arc-guided evolutionary algorithm for the vehicle routing problem with time windows?, IEEE Transactions on Evolutionary Computation, 13(3):624-647 (2009).

[13] Ralphs T. ?Vehicle routing data sets?, online at: http://www.branchandcut.org/VRP/data (2003).