A Branch-and-Price Algorithm For The Time-Dependent Polution Routing Problem

The time-dependent pollution routing problem(TDPRP)is an extention of the pollution routing problem(PRP).It consists of routing a fleet of vehicles in order to serve a set of customers and determining the speeds on each leg of the routes.The cost function includes emissions and driver costs,taking into account traffic congestion which,at peak periods,significantly restricts vehicle speeds and increases emissions.To our knowledge,all solution methods to the TDPRP are based on heuristics.In this paper,we propose an exact branch-and-price algorithm for the TDPRP.An arc-flow formulation can be decomposed into a set-partitioning problem as the master problem,and a time-dependent shortest path problem with resource constraints as the pricing problem.The master problem is solved by means of column generation,and a tailored label algorithm is used to solve the pricing problem.We introduce a set of new dominance rules in the label-setting algorithm for solving the pricing problem.In opposite to the traditional dominance rules,ours consider a set of labels to dominate a label,hence significantly increasing the chance for a successful dominance.Finally,using benchmark instances,we present results on the computational performance.Our approach optimally solves all of the instances with 10,15 and 20 customers,and its computational time is substantially better than cplex.In particular,with the increasing of the size of instance,the computational performance is better and better.