Exact and heuristic algorithms for the vehicle routing problem with multiple interdependent time windows

Karl F. Doerner*, Manfred Gronalt, Richard F. Hartl, Guenter Kiechle, Marc Reimann

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

75 Citations (Scopus)

Abstract

In this paper a model and several solution procedures for a novel type of vehicle routing problems where time windows for the pickup of perishable goods depend on the dispatching policy used in the solution process are presented. This problem is referred to as Vehicle Routing Problem with multiple interdependent time windows (VRPmiTW) and is motivated by a project carried out with the Austrian Red Cross blood program to assist their logistics department. Several variants of a heuristic constructive procedure as well as a branch-and-bound based algorithm for this problem were developed and implemented. Besides finding the expected reduction in costs when compared with the current procedures of the Austrian Red Cross, the results show that the heuristic algorithms find solutions reasonably close to the optimum in fractions of a second. Another important finding is that increasing the number of pickups at selected customers beyond the theoretical minimum number of pickups yields significantly greater potential for cost reductions.

Original languageEnglish
Pages (from-to)3034-3048
Number of pages15
JournalComputers and Operations Research
Volume35
Issue number9
Early online date28 Feb 2007
DOIs
Publication statusPublished - Sept 2008

Keywords

  • Interdependent time windows
  • Multiple time windows
  • Vehicle routing problem

Fingerprint

Dive into the research topics of 'Exact and heuristic algorithms for the vehicle routing problem with multiple interdependent time windows'. Together they form a unique fingerprint.

Cite this