Cyclic Transfer Algorithm for Multivehicle Routing and Scheduling Problems

Paul M. Thompson and Harilaos N. Psaraftis
Additional contact information
Paul M. Thompson: Santa Clara University, Santa Clara, California
Harilaos N. Psaraftis: National Technical University of Athens, Athens, Greece

Operations Research, 1993, vol. 41, issue 5, 935-946

Abstract: This paper investigates the application of a new class of neighborhood search algorithms—cyclic transfers—to multivehicle routing and scheduling problems. These algorithms exploit the two-faceted decision structure inherent to this problem class: First, assigning demands to vehicles and, second, routing each vehicle through its assigned demand stops. We describe the application of cyclic transfers to vehicle routing and scheduling problems. Then we determine the worst-case performance of these algorithms for several classes of vehicle routing and scheduling problems. Next, we develop computationally efficient methods for finding negative cost cyclic transfers. Finally, we present computational results for three diverse vehicle routing and scheduling problems, which collectively incorporate a variety of constraint and objective function structures. Our results show that cyclic transfer methods are either comparable to or better than the best published heuristic algorithms for several complex and important vehicle routing and scheduling problems. Most importantly, they represent a novel approach to solution improvement which holds promise in many vehicle routing and scheduling problem domains.

Keywords: programming; integer; heuristic: cyclic transfer algorithms for fleet planning problems; transportation; vehicle routing: cyclic transfer algorithms for multivehicle problems (search for similar items in EconPapers)
Date: 1993
References: Add references at CitEc
Citations: View citations in EconPapers (23)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.41.5.935 (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:oropre:v:41:y:1993:i:5:p:935-946

Access Statistics for this article

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