Arc routing problems with time-dependent service costs |
| |
Authors: | Mariam Tagmouti Michel GendreauJean-Yves Potvin |
| |
Institution: | Département d’informatique et de recherche opérationnelle and Centre de recherche sur les transports, Université de Montréal, C.P. 6128, succ. Centre-Ville, Montréal, Qué., Canada H3C 3J7 |
| |
Abstract: | This paper studies an arc routing problem with capacity constraints and time-dependent service costs. This problem is motivated by winter gritting applications where the “timing” of each intervention is crucial. The exact problem-solving approach reported here first transforms the arc routing problem into an equivalent node routing problem. Then, a column generation scheme is used to solve the latter. The master problem is a classical set covering problem, while the subproblems are time-dependent shortest path problems with resource constraints. These subproblems are solved using an extension of a previously developed algorithm. Computational results are reported on problems derived from a set of classical instances of the vehicle routing problem with time windows. |
| |
Keywords: | Arc routing Column generation Elementary shortest paths Resource constraints |
本文献已被 ScienceDirect 等数据库收录! |