A multi-path traffic-covering pollution routing model with simultaneous pickup and delivery

Urban traffic in many developing countries has affected travel time and fuel costs, causing disturbances in the transportation schedule of companies dealing with logistic issues. The resulting environmental impact is another driver forcing these companies to reconsider their transportation schedule. Conventional pollution routing problems (PRPs) try to achieve a balance among greenhouse gas (GHG) emissions, fuel consumption, travel time, and distance. These models are not developed to cover traffic congestion and optimize speed on each route, while such factors affect the routing costs. To fill this gap, we propose a multi-path traffic-covering PRP with simultaneous pickup and delivery, which finds alternative paths in case of traffic congestion and determines the lowest-cost routes. Accordingly, we contribute to the multi-path vehicle routing models, which have mainly considered predetermined alternative routes between the nodes instead of providing algorithms for finding alternative low-traffic routes. We apply a four-phase metaheuristic algorithm to solve the model, containing a Clustering-based Floyd-Warshall (CFW) algorithm developed through the K-means method to create a network graph around the high-traffic path and find the alternative paths. The results of analyzing the model indicated that the total costs decreased by about 25% compared to the model without alternative paths. This improved level of much more than the typical range of 2–5% improvement showed the model contributions to the prior research using the same initial conditions but different solution methods.