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

Introduction

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.