Scandinavian Working Papers in Economics

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  

Download statistics

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 ().

This page generated on 2018-01-23 23:36:02.