A Network Flow-Based Tabu Search Heuristic for the Vehicle Routing Problem

Jiefeng Xu and James P. Kelly
Additional contact information
Jiefeng Xu: Graduate School of Business, University of Colorado at Boulder, Boulder, Colorado 80309-0419
James P. Kelly: Graduate School of Business, University of Colorado at Boulder, Boulder, Colorado 80309-0419

Transportation Science, 1996, vol. 30, issue 4, 379-393

Abstract: We develop a new local search approach based on a network flow model that is used to simultaneously evaluate several customer ejection and insertion moves. We use this approach and a direct customer swap procedure to solve the well-known Vehicle Routing Problem. The capacity constraints are relaxed using penalty terms whose parameter values are adjusted according to time and search feedback. Tabu Search is incorporated into the procedure to overcome local optimality. More advanced issues such as intensification and diversification strategies are developed to provide effective enhancements to the basic tabu search algorithm. Computational experience on standard test problems is discussed and comparisons with best-known solutions are provided.

Date: 1996
References: Add references at CitEc
Citations: View citations in EconPapers (15)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.30.4.379 (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:ortrsc:v:30:y:1996:i:4:p:379-393

Access Statistics for this article

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