Discussion Papers, Department of Business and Management Science, Norwegian School of Economics (NHH)
A branch and price algorithm for the combined vehicle routing and scheduling problem with synchronization constraints
() and Mikael Rönnqvist
Abstract: In this paper we present a branch and price algorithm for
the combined vehicle routing and scheduling problem with synchronization
constraints. The synchronization constraints are used to model situations
when two or more customers need simultaneous service. The synchronization
constraints impose a temporal dependency between vehicles, and it follows
that a classical decomposition of the vehicle routing and scheduling
problem is not directly applicable. With our algorithm, we have solved 44
problems to optimality from the 60 problems used for numerical experiments.
The algorithm performs time window branching, and the number of subproblem
calls is kept low by adjustment of the columns service times.
Keywords: Routing; Scheduling; Synchronization; Branch and Price; (follow links to similar papers)
JEL-Codes: L91; (follow links to similar papers)
21 pages, February 13, 2007
Before downloading any of the electronic versions below
you should read our statement on
for viewing Postscript files and the
Acrobat Reader for viewing and printing pdf files.
Full text versions of the paper:
Questions (including download problems) about the papers in this series should be directed to Stein Fossen ()
Report other problems with accessing this service to Sune Karlsson ()
or Helena Lundin ().
Design by Joachim Ekebom