Hide/Show Apps

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

SAKA, Onur Can
Gürel, Sinan
Van Woensel, Tom
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.