A joint vehicle routing and speed optimization problem

Ricardo Fukasawa, Qie He, Fernando Santos, Yongjia Song

Research output: Contribution to journalArticlepeer-review

18 Scopus citations


Classic vehicle routing models usually treat fuel cost as input data, but fuel consumption heavily depends on the travel speed, which leads to the study of optimizing speeds over a route to improve fuel efficiency. In this paper, we propose a joint vehicle routing and speed optimization problem to minimize the total operating cost including fuel cost. The only assumption made on the dependence between fuel cost and travel speed is that it is a strictly convex differentiable function. This problem is very challenging, with medium-sized instances already difficult for a general mixed-integer convex optimization solver. We propose a novel set-partitioning formulation and a branch-cut-and-price algorithm to solve this problem. We introduce new dominance rules for the labeling algorithm so that the pricing problem can be solved efficiently. Our algorithm clearly outperforms the off-the-shelf optimization solver, and is able to solve some benchmark instances to optimality for the first time.

Original languageEnglish (US)
Pages (from-to)694-709
Number of pages16
JournalINFORMS Journal on Computing
Issue number4
StatePublished - Sep 2018

Bibliographical note

Funding Information:
R. Fukasawa was supported by NSERC Discovery [Grant RGPIN-2014-05623]. The authors thank the area editor, the associate editor, and two anonymous referees for their constructive comments that helped significantly improve the quality of the paper.

Publisher Copyright:
© 2018 INFORMS.


  • Branch and price
  • Green transportation
  • Mixed-integer convex optimization
  • Speed optimization
  • Vehicle routing problem


Dive into the research topics of 'A joint vehicle routing and speed optimization problem'. Together they form a unique fingerprint.

Cite this