This paper investigates the computational complexity of a class of vehicle routing and scheduling problems. It reviews known NP-hardness results and compiles the worst-case performance of approximation algorithms for these problems. The paper also suggests directions for future research. The results were presented at a workshop on vehicle and crew scheduling held at the University of Maryland at College Park in 1979. The paper defines a general single vehicle routing problem (VRP) and its extensions, including the m-vehicle routing problem (mVRP) and the single depot vehicle scheduling problem (VSP). It also discusses the ℓ-depot vehicle scheduling problem (ℓVSP). The paper reviews NP-hardness results for these problems, noting that they are unlikely to be solvable in polynomial time unless P=NP. It also discusses the worst-case performance of approximation algorithms for these problems, noting that some approximation algorithms do not exist unless P=NP. The paper also discusses the complexity of the traveling salesman problem (TSP) and the Chinese postman problem (CPP), noting that even the geometric TSP is NP-hard. It also discusses the performance of approximation algorithms for the TSP and the results of local search methods for the TSP. The paper concludes that there are considerable differences in complexity within the class of NP-hard problems. It also notes that the worst-case approach is pessimistic, as approximation algorithms rarely achieve their maximum performance ratio in practice. The paper also discusses the importance of complexity theory in the study of vehicle routing and scheduling problems.This paper investigates the computational complexity of a class of vehicle routing and scheduling problems. It reviews known NP-hardness results and compiles the worst-case performance of approximation algorithms for these problems. The paper also suggests directions for future research. The results were presented at a workshop on vehicle and crew scheduling held at the University of Maryland at College Park in 1979. The paper defines a general single vehicle routing problem (VRP) and its extensions, including the m-vehicle routing problem (mVRP) and the single depot vehicle scheduling problem (VSP). It also discusses the ℓ-depot vehicle scheduling problem (ℓVSP). The paper reviews NP-hardness results for these problems, noting that they are unlikely to be solvable in polynomial time unless P=NP. It also discusses the worst-case performance of approximation algorithms for these problems, noting that some approximation algorithms do not exist unless P=NP. The paper also discusses the complexity of the traveling salesman problem (TSP) and the Chinese postman problem (CPP), noting that even the geometric TSP is NP-hard. It also discusses the performance of approximation algorithms for the TSP and the results of local search methods for the TSP. The paper concludes that there are considerable differences in complexity within the class of NP-hard problems. It also notes that the worst-case approach is pessimistic, as approximation algorithms rarely achieve their maximum performance ratio in practice. The paper also discusses the importance of complexity theory in the study of vehicle routing and scheduling problems.