A Novel Dynamic Program and Relaxations: Dual Bounds for the Capacitated Vehicle Routing Problem
State-of-the-art exact methods for solving vehicle routing problems rely on a dynamic program that enumerates the set of feasible routes and their distances. Using relaxations of the dynamic program improves these exact methods. This work is motivated by two observations. First, the dynamic program enumerates some routes with a suboptimal permutation of the locations. Second, … Read more