Optimization Online


A joint routing and speed optimization problem

Ricardo Fukasawa (rfukasawa***at***uwaterloo.ca)
Qie He (qhe***at***umn.edu)
Fernando Santos (fasantos***at***uwaterloo.ca)
Yongjia Song (ysong3***at***vcu.edu)

Abstract: Fuel cost contributes to a significant portion of operating cost in cargo transportation. Though classic routing models usually treat fuel cost as input data, fuel consumption heavily depends on the travel speed, which has led to the study of optimizing speeds over a given fixed route. In this paper, we propose a joint routing and speed optimization problem to minimize the total cost, which includes the fuel consumption cost. The only assumption made on the dependence between the 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. Our algorithm clearly outperforms the off-the-shelf optimization solver, and is able to solve some benchmark instances to optimality for the first time.

Keywords: vehicle routing; speed optimization; branch-cut-and-price; mixed-integer convex programming; green transportation

Category 1: Applications -- OR and Management Sciences (Transportation )

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 3: Other Topics (Dynamic Programming )


Download: [PDF]

Entry Submitted: 02/26/2016
Entry Accepted: 02/26/2016
Entry Last Modified: 03/05/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society