A Branch-Cut-and-Price Algorithm for the Energy Minimization Vehicle Routing Problem

Ricardo Fukasawa (), Qie He () and Yongjia Song ()
Additional contact information
Ricardo Fukasawa: Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada
Qie He: Department of Industrial and Systems Engineering, University of Minnesota, Minneapolis, Minnesota 55455
Yongjia Song: Department of Statistical Sciences and Operations Research, Virginia Commonwealth University, Richmond, Virginia 23284

Transportation Science, 2016, vol. 50, issue 1, 23-34

Abstract: We study a variant of the capacitated vehicle routing problem where the cost over each arc is defined as the product of the arc length and the weight of the vehicle when it traverses that arc. We propose two new mixed-integer linear programming formulations for the problem: an arc-load formulation and a set partitioning formulation based on q -routes with additional constraints. A family of cycle elimination constraints are derived for the arc-load formulation. We then compare the linear programming (LP) relaxations of these formulations with the two-index one-commodity flow formulation proposed in the literature. In particular, we show that the arc-load formulation with the new cycle elimination constraints gives the same LP bound as the set partitioning formulation based on 2-cycle-free q -routes, which is stronger than the LP bound given by the two-index one-commodity flow formulation. We propose a branch-and-cut algorithm for the arc-load formulation, and a branch-cut-and-price algorithm for the set partitioning formulation strengthened by additional constraints. Computational results on instances from the literature demonstrate that a significant improvement can be achieved by the branch-cut-and-price algorithm over other methods.

Keywords: vehicle routing problem; integer programming; column generation; branch-cut-and-price; green transportation (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2015.0593 (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:50:y:2016:i:1:p:23-34

Access Statistics for this article

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