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

Date

2017-03-01

Author

SAKA, Onur Can
Gürel, Sinan
Van Woensel, Tom

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

116
views

0
downloads

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.

Subject Keywords

Pollution routing problem, Optimality properties, Speed control, Local search heuristics

URI

https://hdl.handle.net/11511/39400

Journal

OR SPECTRUM

DOI

https://doi.org/10.1007/s00291-016-0464-9

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

An iterative hub location and routing problem for postal delivery systems Çetiner, Selim; Sepil, Canan; Süral, Haldun; Department of Industrial Engineering (2003) In this study, we consider the Turkish postal delivery system and develop an effective solution approach for the combined hub location and routing problem where the location of hub nodes are determined, the nonhub regional postal offices are allocated to the hubs, and the optimal set of routes are determined for each hub. Since the realized post-routing distances between origin-destination pairs are different from those used in the hub-location model, we develop an algorithm that finds the route-compatible ...
On alternative mixed integer programming formulations and LP-based heuristics for lot-sizing with setup times Denizel, M; Süral, Haldun (Informa UK Limited, 2006-04-01) We address the multi-item, capacitated lot-sizing problem (CLSP) encountered in environments where demand is dynamic and to be met on time. Items compete for a limited capacity resource, which requires a setup for each lot of items to be produced causing unproductive time but no direct costs. The problem belongs to a class of problems that are difficult to solve. Even the feasibility problem becomes combinatorial when setup times are considered. This difficulty in reaching optimality and the practical relev...
A novel multirobot map fusion strategy for occupancy grid maps Topal, Sebahattin; Erkmen, İsmet; Erkmen, Aydan Müşerref (2013-01-01) In this paper, we consider the problem of merging partial occupancy grid environment maps, which are extracted independently by individual robot units during search and rescue (SAR) operations in complex disaster environments. Moreover, these maps are combined using intensity-based and area-based features without knowing the initial position and orientation of the robots. Our proposed approach handles the limitation of existing studies in the literature; for example, the limited overlapped area between part...
Using a Luhmannian perspective for earthquake resilience Rittersberger, Helga İda (Emerald, 2019-6-3) Purpose The purpose of this paper is to interpret Luhmann's Social Systems Theory to discuss disaster resilience, and use its functional method for creating local organizational inventories to support the trend of integration in Turkey's disaster management system. For this, the authors used a case study from Duzce province in 2013, investigating the organizational aftermath of two major earthquakes in 1999. Design/methodology/approach A purposive sample of local associations in city center of Duzce prov...
A conic quadratic formulation for a class of convex congestion functions in network flow problems Gürel, Sinan (Elsevier BV, 2011-06-01) In this paper we consider a multicommodity network flow problem with flow routing and discrete capacity expansion decisions. The problem involves trading off congestion and capacity assignment (or expansion) costs. In particular, we consider congestion costs involving convex, increasing power functions of flows on the arcs. We first observe that under certain conditions the congestion cost can be formulated as a convex function of the capacity level and the flow. Then, we show that the problem can be effici...

Citation Formats

O. C. SAKA, S. Gürel, and T. Van Woensel, “Using cost change estimates in a local search heuristic for the pollution routing problem,” OR SPECTRUM, pp. 557–587, 2017, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/39400.