A column generation approach for an emission-oriented vehicle routing problem on a multigraph |
| |
| Authors: | Martin Behnke Thomas Kirschstein Christian Bierwirth |
| |
| Institution: | 1. Operations Management, Hacettepe University, Ankara, Turkey;2. Management Science, Hacettepe University, Ankara, Turkey;3. Hacettepe University, Department of Business Administration, 06800 Beytepe, Ankara, Turkey;1. School of Management, Technical University of Munich, Arcisstraße 21, München 80333, Germany;2. Ingolstadt School of Management, Catholic University of Eichstätt-Ingolstadt, Auf der Schanz 49, Ingolstadt 85049, Germany;1. Dipartimento di Design, Politecnico di Milano, Italy;2. Dipartimento di Matematica e Informatica, Universitá di Cagliari, Italy;3. Dipartimento di Ingegneria dell’Informazione, Universitá Politecnica delle Marche, Italy |
| |
| Abstract: | In this work, an emission-minimizing vehicle routing problem with heterogeneous vehicles and a heterogeneous road and traffic network is considered as it is typical in urban areas. Depending on the load of the vehicle, there exist multiple emission-minimal arcs for traveling between two locations. To solve the vehicle routing problem efficiently, a column generation approach is presented. At the core of the procedure an emission-oriented elementary shortest path problem on a multigraph is solved by a backward labeling algorithm. It is shown that the labeling algorithm can be sped up by adjusting the dual master program and by restricting the number of labels propagated in the sub-problem. The column generation technique is used to setup a fast heuristic as well as a branch-and-price algorithm. Both procedures are evaluated based on test instances with up to 100 customers. It turns out that the heuristic approach is very effective and generates near-optimal solutions with gaps below 0.1% on average while only requiring a fraction of the runtime of the exact approach. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
