An exact approach for a variant of the pollution-routing problem
| Autor: | Said Dabia, Emrah Demir, Tom Van Woensel |
|---|---|
| Přispěvatelé: | Operations Planning Acc. & Control, Information, Logistics and Innovation, Logistics, Amsterdam Business Research Institute |
| Jazyk: | angličtina |
| Rok vydání: | 2017 |
| Předmět: |
050210 logistics & transportation
Mathematical optimization Engineering 021103 operations research business.industry 05 social sciences 0211 other engineering and technologies Transportation 02 engineering and technology Green vehicle routing Function problem Cutting stock problem Branch and price Fuel consumption Vehicle routing problem 0502 economics and business Shortest path problem Column generation Destination-Sequenced Distance Vector routing Routing (electronic design automation) Heuristics business Civil and Structural Engineering |
| Zdroj: | Transportation Science, 51(2), 607-628. INFORMS Institute for Operations Research and the Management Sciences Transportation Science, 51(2), 607-628. INFORMS Inst.for Operations Res.and the Management Sciences Dabia, S, Demir, E & Woensel, T V 2017, ' An Exact Approach for a Variant of the Pollution-Routing Problem ', Transportation Science, vol. 51, no. 2, pp. 607-628 . https://doi.org/10.1287/trsc.2015.0651 |
| ISSN: | 0041-1655 |
| DOI: | 10.1287/trsc.2015.0651 |
| Popis: | The pollution-routing problem (PRP) is a recently introduced green vehicle routing problem in the field of green logistics. It concerns routing a number of vehicles to serve a set of geographically dispersed customers within their time windows, jointly with determining their speed on each arc so as to minimize fuel and driving costs. Because of its complexity, all known solution methods are based on (meta-)heuristics. This paper presents an exact solution based on a branch-and-price algorithm for a variant of the PRP. The master problem is a set-partitioning problem, and the pricing problem is a speed- and start-time elementary shortest path problem with resource constraints, in which the speed and start time at the depot needs to be decided on for each individual route. The master problem is solved by means of column generation, and a tailored labeling algorithm is used to solve the pricing problem. New dominance criteria are developed to discard unpromising labels by exploiting the structure of the ready time and the fuel consumption functions. Extensive computational experiments show the value of the proposed algorithm. Keywords: green vehicle routing; fuel consumption; vehicle routing problem; branch and price |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|