An Optimization Algorithm for the Vehicle Routing Problem with Time Windows Based on Lagrangian Relaxation

Our paper presents a new optimization method for the Vehicle Routing Problem with Time Windows (VRPTW). The VRPTW is a generalization of the Vehicle Routing Problem, where the service of a customer must start within a given time interval—a so-called time window. Our method is based on a Lagrangian r...

Full description

Saved in:
Bibliographic Details
Published in:Operations research 1997-05, Vol.45 (3), p.395-406
Main Authors: Kohl, Niklas, Madsen, Oli B. G
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Exact sciences and technology
Flows in networks. Combinatorial problems
Integers
Job shops
Lagrangian function
Marginal costs
Mathematical models
Methods
Minimization of cost
nondifferentiable
Objective functions
Operational research and scientific management
Operational research. Management science
Operations research
Optimal solutions
Optimization
programming
relaxation/subgradient
Routing
Studies
Time windows
transportation
Vehicle capacity
vehicle routing
Vehicles
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Our paper presents a new optimization method for the Vehicle Routing Problem with Time Windows (VRPTW). The VRPTW is a generalization of the Vehicle Routing Problem, where the service of a customer must start within a given time interval—a so-called time window. Our method is based on a Lagrangian relaxation of the constraint set requiring that each customer must be serviced. The master problem consists of finding the optimal Lagrangian multipliers and the subproblem is a Shortest Path Problem with Time Windows and Capacity Constraints. The optimal multipliers are found using a method exploiting the benefits of subgradient methods as well as a bundle method. The method has been implemented and tested on a series of well-known benchmark problems of size up to 100 customers. Our algorithm turns out to be very competitive compared to algorithms considered in the literature, and we have succeeded in solving several previously unsolved problems.
ISSN:0030-364X
1526-5463
DOI:10.1287/opre.45.3.395