Complexity of vehicle routing and scheduling problems

1981/06/01 by Jan Karel Lenstra, J. K. Lenstra, A. H. G. Rinnooy Kan · 8 citations
Engineering · #Optimization and Packing Problems #Scheduling and Optimization Algorithms #Vehicle Routing Optimization Methods

paper · doi:10.1002/net.3230110211

crossref issued 1981/06/01 · crossref published 1981/06/01 · crossref published-print 1981/06/01 · openalex publication_date 1981/06/01 · crossref published-online 2006/10/11 · crossref created 2007/05/11 · crossref deposited 2023/11/12 · openalex created_date 2025/10/10 · crossref indexed 2026/07/31 · openalex updated_date 2026/07/31

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.

Citations

• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• An Analysis of Several Heuristics for the Traveling Salesman Problem

Cited by

• On some matching problems arising in vehicle scheduling models
• Intelligent Control of Interchangeable Loading Bridge for the Logistics of Tomorrow
• Applying quantum approximate optimization to the heterogeneous vehicle routing problem
• Closed form distance formula for the balanced multiple travelling salesmen
• The Period Vehicle Routing Problem with Service Choice
• Quantum Computing based Hybrid Solution Strategies for Large-scale Discrete-Continuous Optimization Problems
• Graph Edit Distance Formulation for the Vehicle Routing Problem: Theory and Analysis
• Continuous relaxations for the traveling salesman problem