Optimization Online


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

Ricardo Fukasawa (rfukasaw***at***math.uwaterloo.ca)
Qie He (qhe***at***umn.edu)
Yongjia Song (ysong3***at***vcu.edu)

Abstract: 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.

Keywords: vehicle routing problem; column generation; branch-cut-and-price; green transportation

Category 1: Applications -- OR and Management Sciences

Category 2: Integer Programming

Category 3: Combinatorial Optimization


Download: [PDF]

Entry Submitted: 08/11/2014
Entry Accepted: 08/11/2014
Entry Last Modified: 08/25/2014

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