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.

Abstract

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.


Actions:
Download: [img] Postscript - Preprinted Version
Download (203kB) | Preview
Export as: [error in script]
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Proceedings article
Citations: [error in script] 5 (Google Scholar) | [error in script]
Uncontrolled Keywords: [error in script]
Subjects:
  • 05-XX Combinatorics > 05Cxx Graph theory > 05C90 Applications

  • 05-XX Combinatorics > 05Cxx Graph theory > 05C85 Graph algorithms

  • 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C35 Programming involving graphs or networks

  • 68-XX Computer science > 68Rxx Discrete mathematics in relation to computer science > 68R10 Graph theory

  • 05-XX Combinatorics > 05Cxx Graph theory > 05C05 Trees

  • 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C27 Combinatorial optimization

  • 90-XX Operations research, mathematical programming > 90Bxx Operations research and management science > 90B06 Transportation, logistics

  • Uncontrolled Keywords: greedy algorithm, minimal spanning tree, time windows, tree partition, vehicle routing
    Subjects: 05-XX Combinatorics > 05Cxx Graph theory > 05C90 Applications
    05-XX Combinatorics > 05Cxx Graph theory > 05C85 Graph algorithms
    90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C35 Programming involving graphs or networks
    68-XX Computer science > 68Rxx Discrete mathematics in relation to computer science > 68R10 Graph theory
    05-XX Combinatorics > 05Cxx Graph theory > 05C05 Trees
    90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C27 Combinatorial optimization
    90-XX Operations research, mathematical programming > 90Bxx Operations research and management science > 90B06 Transportation, logistics
    Divisions: Mathematical Institute
    Depositing User: Archive Admin
    Date Deposited: 02 Apr 2001 00:00
    Last Modified: 19 Jan 2012 09:46
    Deposit Information:
    ZAIK Number: [error in script]
    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