2005/02/01 by Olli Bräysy, Michel Gendreau · 4 citations
Computer Science · Engineering · #Robotic Path Planning Algorithms #Transportation and Mobility Innovations #Vehicle Routing Optimization Methods
paper · doi:10.1287/trsc.1030.0056
crossref issued 2005/02/01 · crossref published 2005/02/01 · crossref published-print 2005/02/01 · openalex publication_date 2005/02/01 · crossref created 2005/03/01 · crossref deposited 2024/01/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31 · crossref indexed 2026/07/31
This paper presents a survey of the research on the vehicle routing problem with time windows (VRPTW). The VRPTW can be described as the problem of designing least cost routes from one depot to a set of geographically scattered points. The routes must be designed in such a way that each point is visited only once by exactly one vehicle within a given time interval, all routes start and end at the depot, and the total demands of all points on one particular route must not exceed the capacity of the vehicle. Both traditional heuristic route construction methods and recent local search algorithms are examined. The basic features of each method are described, and experimental results for Solomon’s benchmark test problems are presented and analyzed. Moreover, we discuss how heuristic methods should be evaluated and propose using the concept of Pareto optimality in the comparison of different heuristic approaches. The metaheuristic methods are described in the second part of this article.