A Subpath Ejection Method for the Vehicle Routing Problem

César Rego
Additional contact information
César Rego: Faculdade de Ciências---Universidade de Lisboa, Departmento de Estatística e Investigação Operacional---DEIO, Campo Grande C/2, 1700 Lisboa, Portugal

Management Science, 1998, vol. 44, issue 10, 1447-1459

Abstract: Generically, ejection chains are methods conceived to allow solution transformations to be efficiently carried out by modifying a variable number of their components at each step of a local search algorithm. We consider a subpath ejection chain method for the vehicle routing problem (VRP) under capacity and route length restrictions. The method undertakes the identification of a substructure named the flower reference structure which, besides coordinating moves during an ejection chain construction, allows the creation of neighborhood structures with interesting combinatorial characteristics. Specifically, we base the method on a fundamental property of creating alternating paths and cycles during an ejection chain construction. A new algorithm based on a Tabu search framework is proposed, and computational results on a set of academic and real-world problems indicate that the algorithm may be a good alternative to the best heuristic algorithms for the VRP.

Keywords: Tabu Search; Ejection Chains; Vehicle Routing (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.44.10.1447 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:44:y:1998:i:10:p:1447-1459

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().