Using cost change estimates in a local search heuristic for the pollution routing problem

SAKA O. C. , GÜREL S., Van Woensel T.

OR SPECTRUM, vol.39, no.2, pp.557-587, 2017 (Peer-Reviewed Journal) identifier identifier

  • Publication Type: Article / Article
  • Volume: 39 Issue: 2
  • Publication Date: 2017
  • Doi Number: 10.1007/s00291-016-0464-9
  • Journal Name: OR SPECTRUM
  • Journal Indexes: Science Citation Index Expanded, Scopus
  • Page Numbers: pp.557-587
  • Keywords: Pollution routing problem, Optimality properties, Speed control, Local search heuristics, GREEN LOGISTICS, ALGORITHM, EMISSIONS


We consider 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 properties which relate the marginal speedup costs for each leg on the tour. We use the derived optimality properties and marginal speedup costs to evaluate possible search moves and choose the most promising ones to implement in local search heuristic. Computational results show that this approach improves solution times significantly while improving solution quality for large instances.