Pollution Routing Problem With Congestion

The Pollution-Routing Problem with Congestion(PRPC)is a variant of the Vehicle-Routing Problem in the context of emissions control and traffic congestion.We consider one general period of traffic congestion,where the start and finish times of the congestion can be set freely.The aim of the PRP-OGPC is to determine the optimal set of routes for a fleet of vehicles as well as the optimal travel speed and departure time on each route segment,to minimize the total cost including emissions cost and drivers’ wages.A two-phase method is introduced to solve this problem.First,an adaptive large neighborhood search heuristic is used to solve the routing problem considering the traffic congestion constraint.Second,a new speed-and-departure-time optimization algorithm is proposed by finding the "best" node to be served first over the congestion period along with calculating its optimal start time of service and then computing the optimal travel speed and departure time under two different drivers’ wage policies.Computational results for four real-world scenarios show the efficiency of our algorithms and show that the policy of paying drivers only after they leave the depot results in a 1%-2.5%cost reduction.