Vehicle Routing Problem with Time Windows, Part II: Metaheuristics

TLDR

The Vehicle Routing Problem with Time Windows seeks minimum‑cost routes from a depot to scattered customers, each visited once within a time window and respecting vehicle capacity, and metaheuristics are general procedures that explore the solution space to find good solutions. This paper surveys the research on metaheuristics applied to the VRPTW. The survey describes the basic features of each metaheuristic and evaluates them on Solomon’s benchmark test problems. Experimental results on Solomon’s benchmarks are presented and analyzed, illustrating the relative performance of the surveyed methods.

Abstract

This paper surveys the research on the metaheuristics for 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. Metaheuristics are general solution procedures that explore the solution space to identify good solutions and often embed some of the standard route construction and improvement heuristics described in the first part of this article. In addition to describing basic features of each method, experimental results for Solomon’s benchmark test problems are presented and analyzed.