Faculty of Economics and Business Administration Publications Database

Graph Sparsification for the Vehicle Routing Problem with Time Windows

Schneider, Michael
Stenger, Andreas
Sand, Bastian
Vigo, Daniele
Schwind, Michael
Pages: 227 - 232
Link External Source: Online Version
Year: 2011

The Vehicle Routing Problem with TimeWindows (VRPTW) is one of the most important and widely studied NP-hard combinatorial optimization problems in the operations research literature. The problem calls for the determination of a minimumcost set of routes for a fleet of identical vehicles with limited capacities to serve a set of customers that have a given demand and an associated time window in which they can be visited. Due to its computational complexity, VRPTW can only be solved by exact methods for instances of moderate size. However, a large number of successful metaheuristic solution methods have been proposed, which are able to produce high-quality solutions for reasonably-sized instances in limited time.