Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

An exact approach for a variant of the pollution-routing problem

Dabia, Said, Demir, Emrah ORCID: and Woensel, Tom Van 2017. An exact approach for a variant of the pollution-routing problem. Transportation Science 51 (2) , pp. 607-628. 10.1287/trsc.2015.0651

Full text not available from this repository.


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.

Item Type: Article
Date Type: Publication
Status: Published
Schools: Business (Including Economics)
Uncontrolled Keywords: green vehicle routing; fuel consumption; vehicle routing problem; branch and price
Publisher: Institute for Operations Research and Management Sciences
ISSN: 0041-1655
Date of Acceptance: 22 July 2015
Last Modified: 02 Nov 2022 09:45

Citation Data

Cited 43 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item Edit Item