2-Path Cuts for the Vehicle Routing Problem with Time Windows

摘要

This paper introduces a strong valid inequality, the 2-path cut, to produce better lower bounds for the vehicle routing problem with time windows. It also develops an effective separation algorithm to find such inequalities. We next incorporate them as needed in the master problem of a Dantzig-wolfe decomposition approach. In this enhanced optimization algorithm, the coupling construints requints that each sustomer be serviced. The subproblem is a shortest path problem with time window and capacity constaints.