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

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

D. Guimarans (Universitat Autònoma de Barcelona, Spain), R. Herrero (Universitat Autònoma de Barcelona, Spain), J. J. Ramos (Universitat Autònoma de Barcelona, Spain) and S. Padrón (Universitat Autònoma de Barcelona, Spain)
Copyright: © 2013 |Pages: 21
DOI: 10.4018/978-1-4666-2461-0.ch007
OnDemand PDF Download:


This paper presents a methodology based on the Variable Neighbourhood Search metaheuristic, applied to the Capacitated Vehicle Routing Problem. The presented approach uses Constraint Programming and Lagrangean Relaxation methods in order to improve algorithm’s efficiency. The complete problem is decomposed into two separated subproblems, to which the mentioned techniques are applied to obtain a complete solution. With this decomposition, the methodology provides a quick initial feasible solution which is rapidly improved by metaheuristics’ iterative process. Constraint Programming and Lagrangean Relaxation are also embedded within this structure to ensure constraints satisfaction and to reduce the calculation burden. By means of the proposed methodology, promising results have been obtained. Remarkable results presented in this paper include a new best-known solution for a rarely solved 200-customers test instance, as well as a better alternative solution for another benchmark problem.
Chapter Preview


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.

Complete Chapter List

Search this Book:
Editorial Advisory Board
Table of Contents
John Wang, Bin Zhou
Chapter 1
Sweety Law, Jacques Verville, Nazim Taskin
The objective of this research paper is to examine the relational attributes underpinning supply chain networks, which linked firms need to manage... Sample PDF
Relational Attributes in Supply Chain Relationships
Chapter 2
Gøril Hannås, Otto Andersen
Information technology (IT) enables businesses to integrate information systems across entities without altering the firms’ legal boundaries. New... Sample PDF
B2B Relationships in Modern Times: Implications of Relation-Specific Information Systems on Governance Forms
Chapter 3
Mohd. Laeequddin, B. S. Sahay, Vinita Sahay, K. Abdul Waheed
Over many years, researchers from social science and management have argued that to develop sufficient trust between potential supply chain... Sample PDF
Supply Chain Partner’s Perceptions of Trust & Risk: The Perspectives of UAE Printing and Packaging Industry
Chapter 4
Honggeng Zhou
According to the propositions in the information processing theory, this study tests the relationship between task uncertainty and three... Sample PDF
An Empirical Test of the Information Processing Theory
Chapter 5
Álvaro García Sánchez, Miguel Ortega-Mier
This paper presents a discrete event simulation model developed with a commercial environment. A modular approach is adopted, which facilitates... Sample PDF
Discrete-Event Simulation Models for Assessing Incidents in Railway Systems
Chapter 6
Patrick Hirsch
In Central Europe transportation accounts for an estimated 30% of the total costs of round timber and is an essential element of cost. In this... Sample PDF
Minimizing Empty Truck Loads in Round Timber Transport with Tabu Search Strategies
Chapter 7
D. Guimarans, R. Herrero, J. J. Ramos, S. Padrón
This paper presents a methodology based on the Variable Neighbourhood Search metaheuristic, applied to the Capacitated Vehicle Routing Problem. The... Sample PDF
Solving Vehicle Routing Problems Using Constraint Programming and Lagrangean Relaxation in a Metaheuristics Framework
Chapter 8
Javier Faulin, Fernando Lera-López, Angel A. Juan
The object of logistic management is to optimise the whole value chain of the distribution of goods and merchandise. One of the main aspects of such... Sample PDF
Optimizing Routes with Safety and Environmental Criteria in Transportation Management in Spain: A Case Study
Chapter 9
Susanne Hohmann, Stephan Zelewski
The bullwhip effect means that demand variability increases as one moves up the supply chain. In the following article the bullwhip effect is... Sample PDF
Effects of Vendor-Managed Inventory on the Bullwhip Effect
Chapter 10
R. Rajesh, S. Pugazhendhi, K. Ganesh
Third party logistics (3PL) service providers play a growing responsibility in the management of supply chain. The global and competitive business... Sample PDF
Genetic Algorithm and Particle Swarm Optimization for Solving Balanced Allocation Problem of Third Party Logistics Providers
Chapter 11
Albert Wee Kwan Tan, Arun Kumar, Balan Sundarakani
As reverse logistics is a relatively new field in supply chain management, especially in Asia, a detailed study is conducted to understand the... Sample PDF
Analysis of Reverse Logistics Operations for a Computer Company
Chapter 12
Jairo R. Montoya-Torres, Fabián Vargas-Nieto
This paper studies the problem of production scheduling in a company belonging to the apparel industry, where textile labels are manufactured... Sample PDF
Solving a Bi-Criteria Hybrid Flowshop Scheduling Problem Occurring in Apparel Manufacturing
Chapter 13
Mehmet Savsar
Material flow in production systems can be controlled by a purely push-pull (just-in-time), or by a hybrid push-pull control mechanism. One type of... Sample PDF
Modeling of Hybrid Production Systems with Constant WIP and Unreliable Equipment
Chapter 14
B. S. Sahay, Vikram Sharma, G. D. Sardana
The automobile industry is a major contributor to India’s economy. The Indian automobile manufacturers face stiff international competition in the... Sample PDF
Supply Chain Management Practices of Indian Automobile Industry
Chapter 15
Leslie S. Hiraoka
As the industrial landscape is altered by emerging markets like China and India and the bankruptcy of Detroit automakers and their parts suppliers... Sample PDF
Reconfiguring Supply Chains for a Global Automotive Industry
Chapter 16
Sanjay Sharma, Sanjaysingh Vijaysingh Patil
Successful implementation of food supply chains in improving the productivity and operational efficiency by some companies made many other firms and... Sample PDF
Development of Holistic Framework Incorporating Collaboration, Supply-Demand Synchronization, Traceability and Vertical Integration in Agri-food Supply Chain
About the Contributors