A branch-cut-and-price algorithm for the energy minimization vehicle routing problem

Ricardo Fukasawa, Qie He, Yongjia Song

Research output: Contribution to journalArticle

26 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)23-34
Number of pages12
JournalTransportation Science
Volume50
Issue number1
DOIs
StatePublished - Feb 2016

    Fingerprint

Keywords

  • Branch-cut-and-price
  • Column generation
  • Green transportation
  • Integer programming
  • Vehicle routing problem

Cite this