Solving Vehicle Routing Problems Using Constraint Programming and Lagrangean Relaxation in a Metaheuristics Framework

Introduction

Routing vehicles to collect or delivery goods is a problem which many companies face each day, laying at the heart of many distribution systems. In practice, objectives and constraints are highly variable and, most of times, complex. In fact, real problems often require a specific modelling and solving methodology. On the other hand, most research is focused on well-known sets of academic problems including certain characteristics. However, since flexible and efficient algorithms are likely to be adapted to various practical contexts, these prototype problems become a nice reference where to test developed methodologies.

This class of logistics problems, usually known as the Vehicle Routing Problem (VRP), is among the most popular research areas in combinatorial optimization. Since it was first defined by Dantzig and Ramser (1959), several variants of the basic problem have been proposed and studied. The most basic VRP is the Capacitated Vehicle Routing Problem (CVRP) that assumes a fleet of vehicles with homogeneous capacity housed in a single depot. It is so a generalization of the Travelling Salesman Problem (TSP) and is therefore NP-hard (Savelsbergh, 1985). For such problems, finding an optimal solution requires a high computational effort.

Several formulations and exact algorithms have been proposed to solve the CVRP. However, for large instances the time required to solve them becomes absolutely prohibitive due to its NP-hardness. Thus, exact algorithms may only deal with small instances, up to 100 customers (Cordeau et al., 2007), solving them to optimality. Numerous heuristics and metaheuristics have also been studied for different VRP variants. In most cases, these methods may solve larger instances but loosing optimality guarantees. This field has deserved special attention from the research community and has stimulated the emergence and the growth of several metaheuristics of general applicability. A recent overview of available methods for different VRP variants can be found in Cordeau et al. (2007).

Compared with classical heuristics, such as route construction and improvement methods or two-phase approaches, metaheuristics are less likely to end trapped in a local optimum. Results justify community's interest in this field. As an example, the large number of Tabu Search based algorithms produced over the last years (Cordeau & Laporte, 2004) is remarkable. Among metaheuristics, Variable Neighbourhood Search (VNS), introduced for the first time in Mladenovic and Hansen (1997), is a quite recent method with far less application examples in VRP research. However, interesting results have been obtained even applying the simplest VNS algorithm, the Variable Neighbourhood Descent (VND) (Bräysy, 2003; Hasle & Kloster, 2007; Rousseau et al., 2002). For this reason, VNS has been selected as the general framework where to embed Constraint Programming (CP) and Lagrangean Relaxation (LR) approaches to the CVRP. By using these two well-known paradigms within the VNS local search process, calculation time may be reduced with respect to classical VNS schemes. Such a hybrid methodology has been adopted as a first approach, suitable to be modified and improved in order to tackle more complex VRP variants, i.e. VRP with Time Windows (VRPTW) and the Pick-Up and Delivery VRP with Time Windows (PDTW). With this objective, the CVRP has been chosen to test algorithm’s effectiveness and major efforts have been addressed to obtain good quality solutions rather than low computation times. Thus, the presented approach becomes a necessary first step to analyse other VRP categories, for which main guidelines introduced in this paper still hold.

This paper is aimed to present a general VNS structure whose local search process is based on CP and LR. The CVRP is divided into two separate subproblems which are modelled and solved using mentioned paradigms. The present paper explains the chosen decomposition and how separate problems are tackled in terms of CP and LR approaches. Promising results, both for finding a quick initial solution and for solving the whole problem, are also shown. Remarkable results presented in this paper include a new best-known solution for a rarely solved 200-customers benchmark problem, as well as an alternative solution, with a lower cost and using one vehicle less, for a well known one.