A Branch-and-Price Algorithm for the Multi-Depot Vehicle Routing Problem with Inter-Depot Routes

Ibrahim Muter, Jean-Francois Cordeau, Gilbert Laporte

Research output: Contribution to journalArticle

27 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)425-441
JournalTransportation Science
Volume48
Issue number3
Publication statusPublished - 2014

Fingerprint

Vehicle routing
pricing
Costs
Linear programming
customer
programming
Experiments
experiment
resources

Cite this

A Branch-and-Price Algorithm for the Multi-Depot Vehicle Routing Problem with Inter-Depot Routes. / Muter, Ibrahim; Cordeau, Jean-Francois; Laporte, Gilbert.

In: Transportation Science, Vol. 48, No. 3, 2014, p. 425-441.

Research output: Contribution to journalArticle

Muter, Ibrahim ; Cordeau, Jean-Francois ; Laporte, Gilbert. / A Branch-and-Price Algorithm for the Multi-Depot Vehicle Routing Problem with Inter-Depot Routes. In: Transportation Science. 2014 ; Vol. 48, No. 3. pp. 425-441.
@article{960e3be710604655bacdcef487d800d9,
title = "A Branch-and-Price Algorithm for the Multi-Depot Vehicle Routing Problem with Inter-Depot Routes",
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.",
author = "Ibrahim Muter and Jean-Francois Cordeau and Gilbert Laporte",
year = "2014",
language = "English",
volume = "48",
pages = "425--441",
journal = "Transportation Science",
issn = "0041-1655",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",
number = "3",

}

TY - JOUR

T1 - A Branch-and-Price Algorithm for the Multi-Depot Vehicle Routing Problem with Inter-Depot Routes

AU - Muter, Ibrahim

AU - Cordeau, Jean-Francois

AU - Laporte, Gilbert

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

UR - http://dx.doi.org/10.1287/trsc.2013.0489

M3 - Article

VL - 48

SP - 425

EP - 441

JO - Transportation Science

JF - Transportation Science

SN - 0041-1655

IS - 3

ER -