Scatter Search Applied to the Vehicle Routing Problem with Simultaneous Delivery and Pickup

Scatter Search Applied to the Vehicle Routing Problem with Simultaneous Delivery and Pickup

Gladys Maquera (Universidad Peruana Unión, Peru), Manuel Laguna (University of Colorado, USA), Dan Abensur Gandelman (Universidade Federal do Rio de Janeiro, Brasil) and Annibal Parracho Sant’Anna (Universidade Federal Fluminense, Brasil)
DOI: 10.4018/978-1-4666-2145-9.ch010
OnDemand PDF Download:
List Price: $37.50


Though its origins can be traced back to 1977, the development and application of the metaheuristic Scatter Search (SS) has stayed dormant for 20 years. However, in the last 10 years, research interest has positioned SS as one of the recognizable methodologies within the umbrella of evolutionary search. This paper presents an application of SS to the problem of routing vehicles that are required both to deliver and pickup goods (VRPSDP). This specialized version of the vehicle routing problem is particularly relevant to organizations that are concerned with sustainable and environmentally-friendly business practices. In this work, the efficiency of SS is evaluated when applied to this problem. Computational results of the application to instances in the literature are presented.
Chapter Preview


The vigorous industrialization of the modern world and the evolution of consumption habits have resulted in an increase in the demand for efficiently handling the movement of goods as well as managing a growing volume of urban waste. The importance of efficiency of distribution systems becomes evident when their impact on the environment is added to the impact on the operational costs of a firm. Managing urban waste involves a set of regulatory, planning, operational and financial activities that require the use of technology compatible with the local environment. To achieve sustainable material cycles, a philosophy commonly called 3R (reduce, reuse and recycle) is generally adopted. These concerns have introduced a new set of features to existing transportation problems that in turn motivated additional operational research work in the area.

The research in this subject focused initially on developing strategies for collecting returning goods without considering the impact on the delivery routes. Some related work appears in Breedam (1995), Carter et al. (1998) and Schultmann et al. (2006). The main issue to be addressed is that returned materials may be transported together with the orders to be delivered because combining pickup and delivery results in lower transportation costs than employing separate routes and vehicles to achieve the same tasks. We consider integrated strategies for pickup and delivery within our examination of the Vehicle Routing Problem with Simultaneous Delivery and Pickup (VRPSDP). This is a variant of the classical Vehicle Routing Problem (VRP) that is only concerned with the delivery of orders.

VRPSDP is a combinatorial optimization problem and has been shown to be NP-hard (Nagy & Salhi, 2005). Due to its computational complexity, exact solution methods become impractical for other than small-scale instances, leading to the use of various heuristics and meta-heuristics. We describe the application of scatter search (SS) to VRPSDP. SS is an evolutionary meta-heuristic that has demonstrated merit in the solution of discrete optimization problems. The concepts and basic principles of SS were proposed by Glover (1977), based on strategies to combine decision rules and restrictions. Laguna and Marti (2003) and Marti et al. (2006) are two relevant SS references where interested readers will find details on basic and advanced SS designs.

In the process applying SS to the VRPSDP, we developed a Diversification Generation Method based on the Greedy Randomized Adaptive Search Procedure (GRASP) of Feo and Resende (1995) as well as three different procedures for intensifying the search, as mandated by the Improvement Method of the SS framework. Our implementation is capable of obtaining high quality solutions even though it does not include some of the so-called advanced strategies, such as multi-tier reference sets, reference-set rebuilding, path relinking and the like. The article is organized as follows. In the following two sections, brief descriptions of SS and of VRPSDP are presented. Then, the SS approach to deal with the VRPSDP is described in detail. The experimental section presents computational results for the instances of Nagy and Salhi (2005), Dehtloff (2001), and Montané and Galvão (2006), which are an adaptation of those in Solomon (1987) and Gehring and Homberger (1999). We finish with concluding remarks in the last section.

Complete Chapter List

Search this Book: