A new assignment algorithm for the vehicle scheduling problem

A new assignment algorithm for the vehicle scheduling problem

0.00 Avg rating0 Votes
Article ID: iaor1991970
Country: Italy
Volume: 19
Issue: 51
Start Page Number: 3
End Page Number: 21
Publication Date: Sep 1989
Journal: Ricerca Operativa
Authors:
Keywords: transportation: general, vehicle routing & scheduling
Abstract:

The multiple depot vehicle scheduling problem (MD-VSP) is NP-HARD and concerns the assignment of a set of time-tabled trips to vehicles stationed at different depots in order to minimize a given cost function, considering that each vehicle returns to its depot at the end of the duty. AP-VSP is a relaxation of MD-VSP in which a vehicle is not required to return to its own depot. Such a relaxation is used in heuristic and exact algorithms. We introduce a new shortest path based algorithm for AP-VSP and show that it dominates all other known methods, both in time complexity and average computational time.

Reviews

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