Arc routing problems with time-dependent service costs

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. © 2006 Elsevier B.V. All rights reserved.

https://doi.org/10.1016/j.ejor.2006.06.028

Cite as:

@article{Tagmouti_2007,
	doi = {10.1016/j.ejor.2006.06.028},
	url = {https://doi.org/10.1016%2Fj.ejor.2006.06.028},
	year = 2007,
	month = {aug},
	publisher = {Elsevier {BV}},
	volume = {181},
	number = {1},
	pages = {30--39},
	author = {Mariam Tagmouti and Michel Gendreau and Jean-Yves Potvin},
	title = {Arc routing problems with time-dependent service costs},
	journal = {European Journal of Operational Research}
}