| Article ID: | iaor20003501 |
| Country: | United States |
| Volume: | 45 |
| Issue: | 3 |
| Start Page Number: | 488 |
| End Page Number: | 492 |
| Publication Date: | May 1997 |
| Journal: | Operations Research |
| Authors: | Fisher Marshall L., Madsen O.B.G., Jornsten K.O. |
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.