Premium
On the worst‐case performance of some heuristics for the vehicle routing and scheduling problem with time window constraints
Author(s) -
Solomon Marius M.
Publication year - 1986
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230160205
Subject(s) - heuristics , vehicle routing problem , scheduling (production processes) , computer science , mathematical optimization , job shop scheduling , schedule , routing (electronic design automation) , mathematics , computer network , operating system
We consider the vehicle routing and scheduling problem with time window constraints. Analytical results concerning the behavior of approximation methods for this problem class are derived through worst‐case analysis. For a variety of heuristics, it is shown that their worst‐case behavior on n customer problems is at least order of n for minimizing the number of vehicles used, the total distance traveled, and the total schedule time.