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, http://www.nhh.no/for/cv/ronnqvist-mikael.htm

No 2007/7, Discussion Papers from Norwegian School of Economics, Department of Business and Management Science

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 (search for similar items in EconPapers)
JEL-codes: L91 (search for similar items in EconPapers)
Pages: 21 pages
Date: 2007-02-13
New Economics Papers: this item is included in nep-cmp
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://hdl.handle.net/11250/164114 (application/pdf)
Our link check indicates that this URL is bad, the error code is: 404 Not Found (http://hdl.handle.net/11250/164114 [302 Found]--> https://www.unit.no/brage-denne-lenken-er-ikke-lenger-gyldig [301 Moved Permanently]--> https://sikt.no/brage-denne-lenken-er-ikke-lenger-gyldig)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hhs:nhhfms:2007_007

Access Statistics for this paper

More papers in Discussion Papers from Norwegian School of Economics, Department of Business and Management Science NHH, Department of Business and Management Science, Helleveien 30, N-5045 Bergen, Norway. Contact information at EDIRC.
Bibliographic data for series maintained by Stein Fossen ().