TY - JOUR
T1 - A joint vehicle routing and speed optimization problem
AU - Fukasawa, Ricardo
AU - He, Qie
AU - Santos, Fernando
AU - Song, Yongjia
PY - 2018/9
Y1 - 2018/9
N2 - 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.
AB - 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.
KW - Branch and price
KW - Green transportation
KW - Mixed-integer convex optimization
KW - Speed optimization
KW - Vehicle routing problem
UR - http://www.scopus.com/inward/record.url?scp=85061851972&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85061851972&partnerID=8YFLogxK
U2 - 10.1287/ijoc.2018.0810
DO - 10.1287/ijoc.2018.0810
M3 - Article
AN - SCOPUS:85061851972
VL - 30
SP - 694
EP - 709
JO - ORSA journal on computing
JF - ORSA journal on computing
SN - 0899-1499
IS - 4
ER -