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

The pollution-routing problem with speed optimization and uneven topography

Lai, David, Costa, Yasel, Demir, Emrah ORCID:, Florio, Alexandre M. and Van Woensel, Tom 2024. The pollution-routing problem with speed optimization and uneven topography. Computers and Operations Research 164 , 106557. 10.1016/j.cor.2024.106557

[thumbnail of 1-s2.0-S0305054824000297-main.pdf] PDF - Published Version
Available under License Creative Commons Attribution.

Download (1MB)


This paper considers a joint pollution-routing with time windows and speed optimization problem (PRP-SO) where vehicle speed, payload, and road grade influence fuel costs and emissions. We present two advanced optimization methods (i.e., approximate and exact) for solving the PRP-SO. The approximate strategy solves large-scale instances of the problem with a Tabu search-based metaheuristic coupled with an efficient fixed-sequence speed optimization algorithm. The second strategy consists of a tailored branch-and-price (BP) algorithm to manage speed optimization within the pricing problem. We test both methods on modified Solomon benchmarks and newly constructed real-life instance sets. Our BP algorithm successfully solves the majority of instances involving up to 50 customers and many instances with 75 and 100 customers. The heuristic can find near-optimal solutions to all instances and requires less than one minute of computational time per instance. Results on real-world instances suggest several managerial insights. First, fuel savings of up to 53% can be achieved when explicitly considering arc payloads and road grades. Second, fuel savings and emission reduction can be achieved by scheduling uphill customers later along the routes. Lastly, we show that ignoring elevation information when planning routes leads to highly inaccurate fuel consumption estimates.

Item Type: Article
Date Type: Publication
Status: Published
Schools: Business (Including Economics)
Publisher: Elsevier
ISSN: 1873-765X
Date of First Compliant Deposit: 18 January 2024
Date of Acceptance: 18 January 2024
Last Modified: 05 Feb 2024 11:45

Actions (repository staff only)

Edit Item Edit Item


Downloads per month over past year

View more statistics