CYCLIC TRANSFER ALGORITHMS FOR MULTIVEHICLE ROUTING AND SCHEDULING PROBLEMS

 
see the original item page
in the repository's web site and access all digital files if the item*
share




1993 (EN)
CYCLIC TRANSFER ALGORITHMS FOR MULTIVEHICLE ROUTING AND SCHEDULING PROBLEMS (EN)

PSARAFTIS, HN (EN)
THOMPSON, PM (EN)

N/A (EN)

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. (EN)

journalArticle

TRAVELING SALESMAN PROBLEMS (EN)
VEHICLE (EN)
Scheduling Problem (EN)
TIME WINDOW CONSTRAINTS (EN)
PERSPECTIVES (EN)
HEURISTICS (EN)

Εθνικό Μετσόβιο Πολυτεχνείο (EL)
National Technical University of Athens (EN)

OPERATIONS RESEARCH (EN)

1993


OPERATIONS RESEARCH SOC AMER (EN)



*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)