A Branch-and-Price Algorithm for the Multidepot Vehicle Routing Problem with Interdepot Routes

Ibrahim Muter (), Jean-François Cordeau () and Gilbert Laporte ()
Additional contact information
Ibrahim Muter: Bahçeşehir University, İstanbul 34353, Turkey; and Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation, Montreal, Quebec H3C 3J7, Canada
Jean-François Cordeau: Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation, Montreal, Quebec H3C 3J7, Canada; and HEC Montréal, Quebec H3T 2A7, Canada
Gilbert Laporte: Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation, Montreal, Quebec H3C 3J7, Canada; and HEC Montréal, Quebec H3T 2A7, Canada

Transportation Science, 2014, vol. 48, issue 3, 425-441

Abstract: This paper proposes a column generation algorithm for the multidepot vehicle routing problem with interdepot routes. This problem is an extension of the multidepot vehicle routing problem in which the vehicles are allowed to stop at intermediate depots along their routes to replenish. The problem can be modeled as a set covering problem in which the variables are rotations corresponding to feasible combinations of routes. We consider two pricing subproblems to generate rotations. The first one generates rotations directly by solving an elementary shortest path problem with resource constraints on a modified version of the original customer-depot network. The second one exploits the relationship between the sets of routes and rotations but results in a model with many columns. We discuss some issues related to solving this second pricing subproblem by column generation and we introduce an alternate approach to alleviate these difficulties. We show through computational experiments that the second pricing mechanism performs better than the first to compute the linear programming relaxation lower bound. We then embed it within a branch-and-bound algorithm to compute optimal integer solutions. Moreover, we assess the benefits of allowing interdepot routes in multidepot vehicle routing.

Keywords: multidepot vehicle routing problem with interdepot routes; column generation; branch and price; elementary shortest path problem with resource constraints (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (18)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2013.0489 (application/pdf)

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:inm:ortrsc:v:48:y:2014:i:3:p:425-441

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().