Smart and parallel general variable neighborhood search for the pollution-routing problem

Abstract

This work addresses a new approach to the Pollution-Routing Problem (PRP), a variant of the Vehicle Routing Problem (VRP) under environmental concerns, which includes costs associated with fuel, drivers, and greenhouse gas emissions. The many factors impacting the environment and, simultaneously, the real cost of the routes are usually ignored in the approaches defined to solve routing problems since the total distance traveled remains the standard objective. However, in pollution-routing problems, these elements play an essential role and each one is significantly influenced by the vehicle load and/or speed over the pathways which are followed. To contribute with methods that can provide solutions within an acceptable computational time, we explore local search and meta-heuristic based approaches, with emphasis on a Smart and Parallel General Variable Neighborhood Search algorithm for the PRP. Innovative neighborhood structures allowing continuous speed values in the arcs were a implemented. Additionally, we incorporate parallel programming strategies. To evaluate the effectiveness of these strategies, we report on the computational experiments conducted on benchmark instances, and we compare the results obtained with other studies from the literature.