Cyclic Transfer Algorithm for Multivehicle Routing and Scheduling Problems

Paul M. Thompson, Harilaos N. Psaraftis

Research output: Contribution to journalJournal articleResearchpeer-review

166 Downloads (Pure)

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.
Original languageEnglish
JournalOperations Research
Volume41
Issue number5
Pages (from-to)935-946
Number of pages12
ISSN0030-364X
DOIs
Publication statusPublished - 1993
Externally publishedYes

Fingerprint Dive into the research topics of 'Cyclic Transfer Algorithm for Multivehicle Routing and Scheduling Problems'. Together they form a unique fingerprint.

Cite this