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, cilt.39, sa.2, ss.557-587, 2017 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 39 Sayı: 2
  • Basım Tarihi: 2017
  • Doi Numarası: 10.1007/s00291-016-0464-9
  • Dergi Adı: OR SPECTRUM
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.557-587
  • Anahtar Kelimeler: Pollution routing problem, Optimality properties, Speed control, Local search heuristics, GREEN LOGISTICS, ALGORITHM, EMISSIONS
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

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.