Location-arc routing problem: heuristic approaches and test instances. (English) Zbl 1348.90404
Summary: Location-routing is a branch of locational analysis that takes into account distribution aspects. The location-arc routing problem (LARP) considers scenarios where the demand is on the edges rather than being on the nodes of a network (usually a road network is assumed). Examples of such scenarios include locating facilities for postal delivery, garbage collection, road maintenance, winter gritting and street sweeping. This paper presents some heuristic approaches to tackle the LARP, as well as some proposals for benchmark instances (and corresponding results). New constructive and improvement methods are presented and used within different metaheuristic frameworks. Test instances were obtained from the capacitated arc routing problem (CARP) literature and adapted to address the LARP.
MSC:
| 90B80 | Discrete location and assignment |
| 90B06 | Transportation, logistics and supply chain management |
| 90B10 | Deterministic network models in operations research |
| 90C35 | Programming involving graphs or networks |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Nagy, G.; Salhi, S., Location-routing: issues, models and methods, Eur J Oper Res, 177, 2, 649-672 (2007) · Zbl 1109.90056 |
| [2] | Lopes, R. B.; Ferreira, C.; Santos, B. S.; Barreto, S., A taxonomical analysis, current methods and objectives on location-routing problems, Intl Trans Oper Res, 20, 6, 795-822 (2013) · Zbl 1277.90015 |
| [3] | Ghiani, G.; Laporte, G., Location-arc routing problems, Opsearch, 38, 2, 151-159 (2001) |
| [4] | Golden, B. L.; Wong, R. T., Capacitated arc routing problems, Networks, 11, 3, 305-315 (1981) · Zbl 0459.90083 |
| [5] | Pearn, W. L.; Assad, A.; Golden, B. L., Transforming arc routing into node routing problems, Comput Oper Res, 14, 4, 285-288 (1987) · Zbl 0614.90060 |
| [6] | Baldacci, R.; Maniezzo, V., Exact methods based on node-routing formulations for undirected arc-routing problems, Networks, 47, 1, 52-60 (2006) · Zbl 1090.90030 |
| [7] | Longo, H.; Aragão, M. Pd.; Uchoa, E., Solving capacitated arc routing problems using a transformation to the CVRP, Comput Oper Res, 33, 6, 1823-1837 (2006) · Zbl 1087.90054 |
| [8] | Wøhlk, S., A decade of capacitated arc routing, (Golden, B. L.; Raghavan, S.; Wasil, E., The vehicle routing problem: latest advances and new challenges (2008), Springer: Springer New York), 29-48 · Zbl 1187.90064 |
| [9] | Levy, L.; Bodin, L., The arc oriented location routing problem, INFOR, 27, 1, 74-94 (1989) |
| [10] | Laporte, G., Location-routing problems, (Golden, B. L.; Assad, A. A., Vehicle routing: methods and studies (1988), North-Holland: North-Holland Amsterdam), 163-198 · Zbl 0644.90030 |
| [11] | Ghiani, G.; Laporte, G., Eulerian location problems, Networks, 34, 4, 291-302 (1999) · Zbl 0948.90085 |
| [13] | Pia, A. D.; Filippi, C., A variable neighborhood descent algorithm for a real waste collection problem with mobile depots, Intl Trans Oper Res, 13, 2, 125-141 (2006) · Zbl 1127.90391 |
| [14] | Amaya, A.; Langevin, A.; Trépanier, M., The capacitated arc routing problem with refill points, Oper Res Lett, 35, 1, 45-53 (2007) · Zbl 1278.90413 |
| [15] | (Mirchandani, P. B.; Francis, R. L., Discrete location theory (1990), Wiley: Wiley New York) · Zbl 0718.00021 |
| [16] | Hertz, A.; Widmer, M., Guidelines for the use of meta-heuristics in combinatorial optimization, Eur J Oper Res, 151, 2, 247-252 (2003) · Zbl 1053.90053 |
| [17] | Clarke, G.; Wright, J., Scheduling of vehicles from a central depot to a number of delivery points, Oper Res, 12, 4, 568-581 (1964) |
| [18] | Belenguer, J. M.; Benavent, E.; Lacomme, P.; Prins, C., Lower and upper bounds for the mixed capacitated arc routing problem, Comput Oper Res, 33, 12, 3363-3383 (2006) · Zbl 1094.90035 |
| [19] | Prins, C.; Prodhon, C.; Wolfler Calvo, R., Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking, 4OR, 4, 3, 221-238 (2006) · Zbl 1125.90316 |
| [20] | Beullens, P.; Muyldermans, L.; Cattrysse, D.; Van Oudheusden, D., A guided local search heuristic for the capacitated arc routing problem, Eur J Oper Res, 147, 3, 629-643 (2003) · Zbl 1026.90015 |
| [21] | Lin, S.; Kernighan, B. W., An effective heuristic algorithm for the traveling salesman problem, Oper Res, 21, 2, 498-516 (1973) · Zbl 0256.90038 |
| [22] | Savelsbergh, M., The vehicle routing problem with time windows: minimizing route duration, INFORMS J Comput, 4, 2, 146-154 (1992) · Zbl 0780.90105 |
| [23] | (Glover, F. W.; Kochenberger, G. A., Handbook of metaheuristics (2003), Kluwer Academic Publishers: Kluwer Academic Publishers Norwell) · Zbl 1058.90002 |
| [24] | Talbi, E. G., Metaheuristics: from design to implementation (2009), Wiley: Wiley Hoboken · Zbl 1190.90293 |
| [25] | Mladenović, N.; Hansen, P., Variable neighborhood search, Comput Oper Res, 24, 11, 1097-1100 (1997) · Zbl 0889.90119 |
| [26] | Hansen, P.; Mladenović, N., Variable neighborhood search: principles and applications, Eur J Oper Res, 130, 3, 449-467 (2001) · Zbl 0981.90063 |
| [27] | Polacek, M.; Doerner, K. F.; Hartl, R. F.; Maniezzo, V., A variable neighborhood search for the capacitated arc routing problem with intermediate facilities, J Heuristics, 14, 5, 405-423 (2008) · Zbl 1211.90314 |
| [28] | Taillard, É.; Badeau, P.; Gendreau, M.; Guertin, F.; Potvin, J. Y., A tabu search heuristic for the vehicle routing problem with soft time windows, Transp Sci, 31, 2, 170-186 (1997) · Zbl 0886.90070 |
| [29] | Filho, V. J.M. F.; Galvão, R. D., A tabu search heuristic for the concentrator location problem, Locat Sci, 6, 1, 189-209 (1998) |
| [30] | Glover, F., Future paths for integer programming and links to artificial intelligence, Comput Oper Res, 13, 5, 533-549 (1986) · Zbl 0615.90083 |
| [31] | Barreto, S.; Ferreira, C.; Paixão, J.; Santos, B. S., Using clustering analysis in a capacitated location-routing problem, Eur J Oper Res, 179, 3, 968-977 (2007) · Zbl 1163.90589 |
| [32] | Resende, M. G.C.; Ribeiro, C. C., Greedy randomized adaptive search procedures, (Glover, F. W.; Kochenberger, G. A., Handbook of metaheuristics (2003), Kluwer Academic Publishers: Kluwer Academic Publishers Norwell), 219-249 · Zbl 1102.90384 |
| [33] | Dijkstra, E. W., A note on two problems in connexion with graphs, Numerische Math, 1, 1, 269-271 (1959) · Zbl 0092.16002 |
| [34] | Golden, B. L.; DeArmon, J. S.; Baker, E. K., Computational experiments with algorithms for a class of routing problems, Comput Oper Res, 10, 1, 47-59 (1983) |
| [35] | Benavent, E.; Campos, V.; Corberán, Á.; Mota, E., The capacitated chinese postman problem: lower bounds, Networks, 22, 7, 669-690 (1992) · Zbl 0762.90077 |
| [36] | Eglese, R. W., Routeing winter gritting vehicles, Discrete Appl Math, 48, 3, 231-244 (1994) · Zbl 0790.90031 |
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.
