Two papers got accepted recently on some new solution approaches to variants of the pollution-routing problem.
The first paper:
A metaheuristic algorithm for the time-dependent pollution-routing problem
with Anna Franceschetti, Emrah Demir, Dorothee Honhon, Gilbert Laporte and Mark Stobbe, just got accepted for the European Journal of Operational Research.
This paper deals with routing a number of vehicles to serve a set of customers and determining their speed on each route segment with the objective of minimizing the cost of driver’s wage and greenhouse gases emissions. Our algorithm is based on an adaptive large neighborhood search heuristic and uses new removal and insertion operators which significantly improve the quality of the solution. A previously developed departure time and speed optimization procedure is used as a subroutine to optimize departure times and vehicle speeds. Results from extensive computational experiments demonstrate the effectiveness of our algorithm.
The second paper:
Using cost change estimates in a local search heuristic for the Pollution Routing Problem
with Onur Can Saka and Sinan Gürel, just got accepted for OR Spectrum.
In this paper, we deal with the pollution routing problem (PRP) with deadlines and heterogeneous fleet for which we implement a local search heuristic using inter-route relocate, exchange and intra-route relocate moves. The subproblem of finding optimal speed levels of a truck for a given tour gives optimality prop- erties which relate the marginal speed-up costs for each leg on the tour. We use the derived optimality properties and marginal speed-up costs to evaluate possible search moves and choose the most promis- ing ones to implement in local search heuristic. Computational results show that this approach improves solution times significantly while improving solution quality for large instances.
Contact me if you want more information or a copy of the papers.