This document, titled "Complexity of Vehicle Routing and Scheduling Problems," is authored by J.K. Lenstra and A.H.G. Rinnooy Kan. It investigates the computational complexity of a class of vehicle routing and scheduling problems, including the general single vehicle routing problem (VRP), the m-vehicle routing problem (mVRP), the generic single depot vehicle scheduling problem (VSP), and the λ-depot vehicle scheduling problem (λVSP). The authors review known NP-hardness results and compile findings on the worst-case performance of approximation algorithms designed for these problems. They suggest directions for future research and highlight the significant differences in complexity within the class of NP-hard problems. The paper also discusses the limitations of current approximation algorithms and the potential impact of developments in mathematical programming and complexity theory on the field. The research was supported by grants from the National Science Foundation and NATO.This document, titled "Complexity of Vehicle Routing and Scheduling Problems," is authored by J.K. Lenstra and A.H.G. Rinnooy Kan. It investigates the computational complexity of a class of vehicle routing and scheduling problems, including the general single vehicle routing problem (VRP), the m-vehicle routing problem (mVRP), the generic single depot vehicle scheduling problem (VSP), and the λ-depot vehicle scheduling problem (λVSP). The authors review known NP-hardness results and compile findings on the worst-case performance of approximation algorithms designed for these problems. They suggest directions for future research and highlight the significant differences in complexity within the class of NP-hard problems. The paper also discusses the limitations of current approximation algorithms and the potential impact of developments in mathematical programming and complexity theory on the field. The research was supported by grants from the National Science Foundation and NATO.