|
|||||
|
|
A variable neighborhood descent heuristic for arc routing problems with time-dependent service costs |
|
| Authors: | Mariam Tagmouti Michel Gendreau Jean-Yves Potvin |
| Affiliation: | 1. Département d’informatique et de recherche opérationnelle, Université de Montréal, C.P. 6128, succ. Centre-Ville, Montréal, Québec, Canada H3C 3J7;2. Département de mathématiques et de génie industriel, École Polytechnique de Montréal, C.P. 6079, succ. Centre-Ville, Montréal, Québec, Canada H3C 3A7;3. Centre interuniversitaire de recherche, sur les réseaux d’entreprise, la logistique et le transport, Université de Montréal, C.P. 6128, succ. Centre-Ville, Montréal, Québec, Canada H3C 3J7 |
| Abstract: | This paper proposes a variable neighborhood descent heuristic for solving a capacitated arc routing problem with time-dependent service costs. The problem is motivated by winter gritting applications where the timing of each intervention is crucial. The variable neighborhood descent is based on neighborhood structures that manipulate arcs or sequences of arcs. Computational results are reported on problems derived from classical capacitated arc routing problem instances. A comparison is also provided with an alternative approach where the arc routing problem is solved after being transformed into an equivalent node routing problem. |
| Keywords: | Capacitated arc routing Time-dependent service costs Variable neighborhood descent |
| 本文献已被 ScienceDirect 等数据库收录！ | |