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

Onur Can Saka (), Sinan Gürel () and Tom van Woensel ()
Additional contact information
Onur Can Saka: Middle East Technical University
Sinan Gürel: Middle East Technical University

OR Spectrum: Quantitative Approaches in Management, 2017, vol. 39, issue 2, No 8, 557-587

Abstract: Abstract 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.

Keywords: Pollution routing problem; Optimality properties; Speed control; Local search heuristics (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://link.springer.com/10.1007/s00291-016-0464-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:orspec:v:39:y:2017:i:2:d:10.1007_s00291-016-0464-9

Ordering information: This journal article can be ordered from
http://www.springer. ... research/journal/291

DOI: 10.1007/s00291-016-0464-9

Access Statistics for this article

OR Spectrum: Quantitative Approaches in Management is currently edited by Rainer Kolisch

More articles in OR Spectrum: Quantitative Approaches in Management from Springer, Gesellschaft für Operations Research e.V.
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().