This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Thompson, P. M. Articles by Psaraftis, H. N. Search for Related Content

Cyclic Transfer Algorithm for Multivehicle Routing and Scheduling Problems

Santa Clara University, Santa Clara, California
National Technical University of Athens, Athens, Greece

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.

Subject classifications: programming; integer; heuristic: cyclic transfer algorithms for fleet planning problems; transportation; vehicle routing: cyclic transfer algorithms for multivehicle problems.

This article has been cited by other articles:

				G. Laporte Fifty Years of Vehicle Routing Transportation Science, November 1, 2009; 43(4): 408 - 416. [Abstract] [PDF]

				P. Schermerhorn and M. Scheutz Investigating the Adaptiveness of Communication in Multi-Agent Behavior Coordination Adaptive Behavior, December 1, 2007; 15(4): 423 - 445. [Abstract] [PDF]

				R. K. Ahuja, A. Kumar, K. C. Jha, and J. B. Orlin Exact and Heuristic Algorithms for the Weapon-Target Assignment Problem Operations Research, November 1, 2007; 55(6): 1136 - 1146. [Abstract] [PDF]

				R. K. Ahuja, W. Huang, H. E. Romeijn, and D. R. Morales A Heuristic Approach to the Multi-Period Single-Sourcing Problem with Production and Inventory Capacities and Perishability Constraints INFORMS Journal on Computing, January 1, 2007; 19(1): 14 - 26. [Abstract] [PDF]

				R. K. Ahuja, J. Goodstein, A. Mukherjee, J. B. Orlin, and D. Sharma A Very Large-Scale Neighborhood Search Algorithm for the Combined Through-Fleet-Assignment Model INFORMS Journal on Computing, January 1, 2007; 19(3): 416 - 428. [Abstract] [PDF]

				R. K. Ahuja, K. C. Jha, J. B. Orlin, and D. Sharma Very Large-Scale Neighborhood Search for the Quadratic Assignment Problem INFORMS Journal on Computing, January 1, 2007; 19(4): 646 - 657. [Abstract] [PDF]

				T. Ibaraki, S. Imahori, M. Kubo, T. Masuda, T. Uno, and M. Yagiura Effective Local Search Algorithms for Routing and Scheduling Problems with General Time-Window Constraints Transportation Science, May 1, 2005; 39(2): 206 - 232. [Abstract] [PDF]

				O. Braysy and M. Gendreau Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms Transportation Science, February 1, 2005; 39(1): 104 - 118. [Abstract] [PDF]

				R. K. Ahuja, J. B. Orlin, S. Pallottino, M. P. Scaparra, and M. G. Scutella A Multi-Exchange Heuristic for the Single-Source Capacitated Facility Location Problem Management Science, June 1, 2004; 50(6): 749 - 760. [Abstract] [PDF]

				M. Christiansen, K. Fagerholt, and D. Ronen Ship Routing and Scheduling: Status and Perspectives Transportation Science, February 1, 2004; 38(1): 1 - 18. [Abstract] [PDF]

				O. Braysy A Reactive Variable Neighborhood Search for the Vehicle-Routing Problem with Time Windows INFORMS Journal on Computing, January 1, 2003; 15(4): 347 - 368. [Abstract] [PDF]