Vehicle Routing with Time Windows: Two Optimization Algorithms
Marshall L. Fisher, Kurt O. Jörnsten, Oli B. G. Madsen
Operations Research · 1997 · Volume 45 · Issue 3
Abstract
We describe two optimization methods for vehicle routing problems with time windows. These are a K-Tree relaxation with time windows added as side constraints and a Lagrangian decomposition in which variable splitting is used to divide the problem into two subproblems—a semi-assignment problem and a series of shortest path problems with time windows and capacity constraints. We present optimal solutions to problems with up to 100 customers.
Keywords
transportation, vehicle routing, networks/graphs, tree algorithms, programming, relaxation/subgradient
Enable JavaScript for citation tools and additional paper interactions.