An Exact Approach for a Variant of the Pollution-Routing Problem

Said Dabia (), Emrah Demir () and Tom Van Woensel ()
Additional contact information
Said Dabia: Department of Economics and Business Administration, VU University Amsterdam, 1081 HV Amsterdam, Netherlands; and Eyefreight BV, 3981 AJ Bunnik, Netherlands
Emrah Demir: School of Industrial Engineering, Eindhoven University of Technology, 5600 MB Eindhoven, Netherlands
Tom Van Woensel: School of Industrial Engineering, Eindhoven University of Technology, 5600 MB Eindhoven, Netherlands

Transportation Science, 2017, vol. 51, issue 2, 607-628

Abstract: The pollution-routing problem (PRP) is a recently introduced green vehicle routing problem in the field of green logistics. It concerns routing a number of vehicles to serve a set of geographically dispersed customers within their time windows, jointly with determining their speed on each arc so as to minimize fuel and driving costs. Because of its complexity, all known solution methods are based on (meta-)heuristics. This paper presents an exact solution based on a branch-and-price algorithm for a variant of the PRP. The master problem is a set-partitioning problem, and the pricing problem is a speed- and start-time elementary shortest path problem with resource constraints, in which the speed and start time at the depot needs to be decided on for each individual route. The master problem is solved by means of column generation, and a tailored labeling algorithm is used to solve the pricing problem. New dominance criteria are developed to discard unpromising labels by exploiting the structure of the ready time and the fuel consumption functions. Extensive computational experiments show the value of the proposed algorithm.

Keywords: green; vehicle; routing; •; fuel; consumption; •; vehicle; routing; problem; •; branch; and; price (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (13)

Downloads: (external link)
https://doi.org/10.1287/trsc.2015.0651 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:51:y:2017:i:2:p:607-628

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().