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

Ricardo Fukasawa, Qie He, Yongjia Song

Research output: Contribution to journalArticlepeer-review

40 Scopus citations


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
Issue number1
StatePublished - Feb 2016

Bibliographical note

Funding Information:
The authors wish to thank the associate editor and two anonymous referees for their helpful comments. The first author was supported by the NSERC Discovery Council [Grant RGPIN-05623].

Publisher Copyright:
© 2016 INFORMS.


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


Dive into the research topics of 'A branch-cut-and-price algorithm for the energy minimization vehicle routing problem'. Together they form a unique fingerprint.

Cite this