TY - JOUR
T1 - A disjunctive convex programming approach to the pollution-routing problem
AU - Fukasawa, Ricardo
AU - He, Qie
AU - Song, Yongjia
N1 - Publisher Copyright:
© 2016 Elsevier Ltd
PY - 2016/12/1
Y1 - 2016/12/1
N2 - 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. Some instances are solved to optimality for the first time.
AB - 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. Some instances are solved to optimality for the first time.
KW - Green transportation
KW - Mixed-integer convex programming
KW - Pollution-routing problem
KW - Speed optimization
UR - http://www.scopus.com/inward/record.url?scp=84995600695&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84995600695&partnerID=8YFLogxK
U2 - 10.1016/j.trb.2016.09.006
DO - 10.1016/j.trb.2016.09.006
M3 - Article
AN - SCOPUS:84995600695
SN - 0191-2615
VL - 94
SP - 61
EP - 79
JO - Transportation Research Part B: Methodological
JF - Transportation Research Part B: Methodological
ER -