A Joint Vehicle Routing and Speed Optimization Problem

Ricardo Fukasawa (), Qie He, Fernando Santos and Yongjia Song
Additional contact information
Ricardo Fukasawa: Department of Combinatorics and Optimization, University of Waterloo, Ontario N2L 3G1, Canada
Qie He: Department of Industrial and Systems Engineering, University of Minnesota, Minneapolis, Minnesota 55455
Fernando Santos: Department of Engineering, Campus Itabira, Federal University of Itajubá, Itajubá, Brazil
Yongjia Song: Department of Statistical Sciences and Operations Research, Virginia Commonwealth University, Richmond, Virginia 23284

INFORMS Journal on Computing, 2018, vol. 30, issue 4, 694-709

Abstract: 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. The online supplement is available at https://doi.org/10.1287/ijoc.2018.0810 .

Keywords: vehicle routing problem; speed optimization; branch and price; mixed-integer convex optimization; green transportation (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0810 (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:orijoc:v:30:y:2018:i:4:p:694-709

Access Statistics for this article

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