Cyclic transfer algorithms for multivehicle routing and scheduling problems

Cyclic transfer algorithms for multivehicle routing and scheduling problems

0.00 Avg rating0 Votes
Article ID: iaor19941753
Country: United States
Volume: 41
Issue: 5
Start Page Number: 935
End Page Number: 946
Publication Date: Sep 1993
Journal: Operations Research
Authors: ,
Keywords: programming: integer
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. The authors describe the application of cyclic transfers to vehicle routing and scheduling problems. Then the authors determine the worst-case performance of these algorithms for several classes of vehicle routing and scheduling problems. Next, they develop computationally efficient methods for finding negative cost cyclic transfers. Finally, they present computational results for three diverse vehicle routing and scheduling problems, which collectively incorporate a variety of constraint and objective function structures. The present 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.

Reviews

Required fields are marked *. Your email address will not be published.