Reachability cuts for the vehicle routing problem with time windows

Reachability cuts for the vehicle routing problem with time windows

0.00 Avg rating0 Votes
Article ID: iaor20083820
Country: Netherlands
Volume: 175
Issue: 1
Start Page Number: 210
End Page Number: 223
Publication Date: Nov 2006
Journal: European Journal of Operational Research
Authors:
Abstract:

This paper introduces a class of cuts, called reachability cuts, for the Vehicle Routing Problem with Time Windows (VRPTW). Reachability cuts are closely related to cuts derived from precedence constraints in the Asymmetric Traveling Salesman Problem with Time Windows and to k-path cuts for the VRPTW. In particular, any reachability cut dominates one or more k-path cuts. The paper presents separation procedures for reachability cuts and reports computational experiments on well-known VRPTW instances. The computational results suggest that reachability cuts can be highly useful as cutting planes for certain VRPTW instances.

Reviews

Required fields are marked *. Your email address will not be published.