Heuristic Algorithms For Single And Multiple Depot Vehicle Routing Problems With Pickups And Deliveries

Nagy, G. and Salhi, S. (2005) Heuristic Algorithms For Single And Multiple Depot Vehicle Routing Problems With Pickups And Deliveries. European Journal of Operational Research, 162 (1). pp. 126-141. ISSN 0377-2217 . (The full text of this publication is not available from this repository)

The full text of this publication is not available from this repository. (Contact us about this Publication)

Abstract

The Vehicle Routing Problem with Pickups and Deliveries (VRPPD) is an extension to the classical Vehicle Routing Problem (VRP), where customers may both receive and send goods. We do not make the assumption common in the VRPPD literature, that goods may only be picked up after all deliveries have been completed. We also eschew the concept of insertion and propose a method that treats pickups and deliveries in an integrated manner. This method finds a solution to the corresponding VRP problem and modifies this solution to make it feasible for the VRPPD. Such modification is achieved mainly by heuristic routines taken from VRP methodology but modified such that their aim becomes the reduction of infeasibilities, although a number of problem-specific routines are also constructed. To render our procedures efficient when checking feasibility, we built appropriate mathematical relationships to describe changes in the maximum load of routes. Furthermore, several enhancements are introduced. Our methodology is also capable of solving multi-depot problems, which has not been done before for this challenging general version of the VRPPD. The methods are tested for single and multiple depot problems with encouraging results. (C) 2003 Elsevier B.V. All rights reserved

Item Type: Article
Subjects: Q Science > Operations Research - Theory
Divisions: Faculties > Social Sciences > Kent Business School > Management Science
Depositing User: Gabor Nagy
Date Deposited: 08 Oct 2008 17:22
Last Modified: 21 May 2011 23:48
Resource URI: http://kar.kent.ac.uk/id/eprint/9937 (The current URI for this page, for reference purposes)
  • Depositors only (login required):