Arc routing problems with time-dependent service costs. (English) Zbl 1121.90031
Summary: 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.
MSC:
| 90B20 | Traffic problems in operations research |
References:
| [1] | Assad, A. A.; Golden, B. L., Arc routing methods and applications, (Ball, M. O.; etal., Network Routing (1995), Elsevier), 375-483 · Zbl 0870.90056 |
| [2] | Baldacci, R.; Maniezzo, V., Exact methods based on node routing formulations for undirected arc routing problems, Networks, 47, 52-60 (2006) · Zbl 1090.90030 |
| [3] | Campbell, J. F.; Langevin, A., Roadway snow and ice control, (Dror, M., Arc Routing: Theory, Solutions and Applications (2000), Kluwer), 389-418 · Zbl 0982.90010 |
| [4] | Christofides, N., The optimum traversal of a graph, Omega, 1, 719-732 (1973) |
| [5] | Clarke, G.; Wright, J., Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, 12, 568-581 (1964) |
| [6] | J.F. Cordeau, G. Laporte, Modeling and optimization of vehicle routing and arc routing problems, Les Cahiers du GERAD G-2002-30, Montreal, 2002.; J.F. Cordeau, G. Laporte, Modeling and optimization of vehicle routing and arc routing problems, Les Cahiers du GERAD G-2002-30, Montreal, 2002. |
| [7] | Desrosiers, J.; Dumas, Y.; Solomon, M. M.; Soumis, F., Time constrained routing and scheduling, (Ball, M. O.; etal., Network Routing (1995), Elsevier), 35-139 · Zbl 0861.90052 |
| [8] | Dror, M., Arc Routing: Theory, Solutions and Applications (2000), Kluwer · Zbl 0947.00016 |
| [9] | Eglese, R. W.; Li, L. Y.O., Efficient routeing for winter gritting, Journal of the Operational Research Society, 43, 1031-1034 (1992) |
| [10] | Eglese, R. W., Routing winter gritting vehicles, Discrete Applied Mathematics, 48, 231-244 (1994) · Zbl 0790.90031 |
| [11] | Eiselt, H. A.; Gendreau, M.; Laporte, G., Arc routing problems, Part I: The Chinese postman problem, Operations Research, 43, 231-242 (1995) · Zbl 0837.90037 |
| [12] | Eiselt, H. A.; Gendreau, M.; Laporte, G., Arc routing problems, Part II: The rural postman problem, Operations Research, 43, 399-414 (1995) · Zbl 0853.90042 |
| [13] | Feillet, D.; Dejax, P.; Gendreau, M.; Gueguen, C., An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems, Networks, 44, 216-229 (2004) · Zbl 1056.90014 |
| [14] | Ghiani, G.; Improta, G.; Laporte, G., The capacitated arc routing problem with intermediate facilities, Networks, 37, 134-143 (2001) · Zbl 0981.90059 |
| [15] | Golden, B. L.; Wong, R., Capacitated arc routing problems, Networks, 11, 305-315 (1981) · Zbl 0459.90083 |
| [16] | Golden, B. L.; DeArmmon, J. S.; Baker, E. K., Computational experiments with algorithms for a class of routing problems, Computers & Operations Research, 10, 47-52 (1983) |
| [17] | Hertz, A.; Laporte, G.; Mittaz, M., A tabu search heuristic for the capacitated arc routing problem, Operations Research, 48, 129-135 (2000) · Zbl 1106.90384 |
| [18] | Ibaraki, T.; Imahori, S.; Kubo, M.; Masuda, T.; Uno, T.; Yagiura, M., Effective local search algorithms for routing and scheduling problems with general time-window constraints, Transportation Science, 39, 206-232 (2005) |
| [19] | Ioachim, I.; Gélinas, S.; Desrosiers, J.; Soumis, F., A dynamic programming algorithm for the shortest path problem with time windows and linear node costs, Networks, 31, 193-204 (1998) · Zbl 1002.90084 |
| [20] | Lacomme, P.; Prins, C.; Ramdane-Chérif, W., A GA for the CARP and its extensions, (Boers, E. J.W., Applications of Evolutionary Computing. Applications of Evolutionary Computing, Lecture Notes in Computer Science, vol. 2037 (2001), Springer), 473-483 · Zbl 0978.68566 |
| [21] | Li, L. Y.O.; Eglese, R. W., An interactive algorithm for vehicle routeing for winter gritting, Journal of the Operational Research Society, 47, 217-228 (1996) |
| [22] | Longo, H.; de Aragão, M. P.; Uchoa, E., Solving capacitated arc routing problems using a transformation to the CVRP, Computers & Operations Research, 33, 1823-1837 (2006) · Zbl 1087.90054 |
| [23] | T. Lotan, D. Cattrysse, D. Van Oudheusden, Winter gritting in the Province of Antwerp: A combined location and routing problem, Technical Report IS-MG 96/4, Institut de Statistique, Université Libre de Bruxelles, 1996.; T. Lotan, D. Cattrysse, D. Van Oudheusden, Winter gritting in the Province of Antwerp: A combined location and routing problem, Technical Report IS-MG 96/4, Institut de Statistique, Université Libre de Bruxelles, 1996. · Zbl 0883.90084 |
| [24] | V. Maniezzo, Algorithms for large directed CARP instances: Urban solid waste collection operational support, Technical Report UBLCS-2004-16, Department of Computer Science, University of Bologna, Italy, 2004.; V. Maniezzo, Algorithms for large directed CARP instances: Urban solid waste collection operational support, Technical Report UBLCS-2004-16, Department of Computer Science, University of Bologna, Italy, 2004. |
| [25] | Pearn, W.; Assad, A.; Golden, B. L., Transforming arc routing into node routing problems, Computers & Operations Research, 14, 285-288 (1987) · Zbl 0614.90060 |
| [26] | Solomon, M. M., Algorithms for the vehicle routing and scheduling problem with time window constraints, Operations Research, 35, 254-265 (1987) · Zbl 0625.90047 |
| [27] | Taillard, E. D.; Badeau, P.; Gendreau, M.; Guertin, F.; Potvin, J.-Y., A tabu search heuristic for the vehicle routing problem with soft time windows, Transportation Science, 31, 170-186 (1997) · Zbl 0886.90070 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
