Optimization Online


A disjunctive convex programming approach to the pollution routing problem

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

Abstract: The pollution routing problem (PRP) aims to determine a set of routes and speed over each leg of the routes simultaneously to minimize the total operational and environmental costs. A common approach to solve the PRP exactly is through speed discretization, i.e., assuming that speed over each arc is chosen from a prescribed set of values. In this paper, we keep speed as a continuous decision variable within an interval and propose new formulations for the PRP. In particular, we build two mixed-integer convex optimization models for the PRP, by employing tools from disjunctive convex programming. These are the first arc-based formulations for the PRP with continuous speed. We also derive several families of valid inequalities to further strengthen both models. We test the proposed formulations on benchmark instances, with some instances solved to optimality for the first time. The computational results also show the solutions from speed discretization can always give the same optimal routes for the benchmark instances.

Keywords: vehicle routing problem, mixed integer second-order cone program, mixed integer convex program, green logistics

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

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

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


Download: [PDF]

Entry Submitted: 06/25/2015
Entry Accepted: 06/25/2015
Entry Last Modified: 07/04/2016

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