A New Heuristic for Vehicle Routing with Narrow Time Windows

Hamacher, Anja and Moll, Christoph (1997) A New Heuristic for Vehicle Routing with Narrow Time Windows.
Published In: Selected papers of the Symposium on Operations Research (SOR) : Braunschweig, September 3 - 6, 1996 Springer 1997, pp. 301-306.


This paper describes a new heuristic for vehicle routing problems with narrow time windows. The problem arises in the context of the delivery of groceries to restaurants. For most of the instances the given time window distribution does not allow solutions where no time restrictions are violated. The aim is to schedule most of the customers in time building regionally bounded tours. The few remaining customers have to be scheduled manually. If the disponent decides to serve one or more of the remaining customers in time, he has to allow out-of-time deliveries for some of the automatically planned stops. The algorithm is based on a clustering procedure where a tree with multiple node weights is divided into subtrees. Upper bounds restrict the sums of the weight functions in each subtree. This problem is NP-complete even for trees with bounded degree and more than two weight functions. A greedy algorithm is developed to determine the tree partition. For our application it is extended to a version which also checks if each subtree can be routed regarding the problem specific requirements. Although the algorithm was developed for a specific real world problem, the ideas can also be applied to other vehicle routing problems - even to those with more complicated constraints.

Download: [img] Postscript - Preprinted Version
Download (203kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr96-239
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Jan 2012 09:46
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/239