Scandinavian Working Papers in Business Administration
Discussion Papers,
Norwegian School of Economics, Department of Business and Management Science
No 2007/7: A branch and price algorithm for the combined vehicle routing and scheduling problem with synchronization constraints
David Bredström () and Mikael Rönnqvist ()
Additional contact information
David Bredström: Dept. of Mathematics, Linköpings universitet, Postal: Linköpings universitet, Department of Mathematics, SE-581 83 Linköping, Sweden
Mikael Rönnqvist: Dept. of Finance and Management Science, Norwegian School of Economics and Business Administration, Postal: NHH , Department of Finance and Management Science, Helleveien 30, N-5045 Bergen, Norway
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
JEL-codes: L91
21 pages, February 13, 2007
Full text files
164114
- Norwegian School of Economics, Department of Business and Management Science
- Ordering Working Papers
- Home page for this series
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 ().
RePEc:hhs:nhhfms:2007_007This page generated on 2024-11-12 04:36:00.