Complexity of vehicle routing and scheduling problems

Abstract

Abstract The complexity of a class of vehicle routing and scheduling problems is investigated. We review known NP‐hardness results and compile the results on the worst‐case performance of approximation algorithms. Some directions for future research are suggested. The presentation is based on two discussion sessions during the Workshop to Investigate Future Directions in Routing and Scheduling of Vehicles and Crews, held at the University of Maryland at College Park, June 4–6, 1979.