Double-horizon based heuristics for the dynamic pickup and delivery problem with time windows

The dynamic Pickup and Delivery Problem with Time Windows (PDPTW) is faced by courier companies serving same-day pickup and delivery requests for the transport of letters and small parcels. This article focuses on the dynamic PDPTW for which future requests are not stochastically modelled or predict...

Full description

Saved in:
Bibliographic Details
Published in:Transportation research. Part B: methodological 2004-09, Vol.38 (8), p.669-685
Main Authors: Mitrović-Minić, Snežana, Krishnamurti, Ramesh, Laporte, Gilbert
Format: Article
Language:English
Subjects:
Applied sciences
Dynamic pickup and delivery problem with time windows
Exact sciences and technology
Ground, air and sea transportation, marine construction
On-line heuristic
Rolling time horizon
Short-term and long-term time horizons
Transportation planning, management and economics
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The dynamic Pickup and Delivery Problem with Time Windows (PDPTW) is faced by courier companies serving same-day pickup and delivery requests for the transport of letters and small parcels. This article focuses on the dynamic PDPTW for which future requests are not stochastically modelled or predicted. The standard solution methodology for the dynamic PDPTW is the use of a rolling time horizon as proposed by Psaraftis. When assigning a new request to a vehicle it may be preferable to consider the impact of a decision both on a short-term and on a long-term horizon. In particular, better managing slack time in the distant future may help reduce routing cost. This paper describes double-horizon based heuristics for the dynamic PDPTW. Computational results show the advantage of using a double-horizon in conjunction with insertion and improvement heuristics.
ISSN:0191-2615
1879-2367
DOI:10.1016/j.trb.2003.09.001