Navegar

Colección

Datos Estadísticas

Artículo

Este artículo es de Acceso Abierto y puede ser descargado en su versión final desde nuestro repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We propose a new algorithm for the Capacitated Arc Routing Problem (CARP). Our motivation to deal with this problem is related to its application in several real world scenarios such as street sweeping, urban waste collection and electric meter reading just to mention a few. Based on BRKGA metaheuristic, our algorithm introduces a new random key encoding for CARP, mutation to random keys strings, a restart phase to avoid stagnation and local search. The algorithm was tested with several well-known instances from the literature. The results obtained were competitive in terms of objective function value and required computational time. © 2011 Elsevier B.V.

Registro:

Documento: Artículo
Título:BRKGA algorithm for the Capacitated Arc Routing Problem
Autor:Martinez, C.; Loiseau, I.; Resende, M.G.C.; Rodriguez, S.
Filiación:Departamento de Informática, Facultad de Ciencias Exactas, Universidad Nacional de Salta, Argentina
Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Argentina
ATandT Labs Research, Florham Park, NJ, United States
Palabras clave:BRKGA; CARP; metaheuristics; vehicle routing; BRKGA; Capacitated arc routing problem; CARP; Computational time; Local search; Meta heuristics; Metaheuristic; Meter readings; Objective function values; Random keys; Real-world scenario; Street sweeping; Urban wastes; Computer science; Vehicle routing; Algorithms
Año:2011
Volumen:281
Página de inicio:69
Página de fin:83
DOI: http://dx.doi.org/10.1016/j.entcs.2011.11.026
Título revista:Electronic Notes in Theoretical Computer Science
Título revista abreviado:Electron. Notes Theor. Comput. Sci.
ISSN:15710661
PDF:https://bibliotecadigital.exactas.uba.ar/download/paper/paper_15710661_v281_n_p69_Martinez.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710661_v281_n_p69_Martinez

Referencias:

  • Bean, J., Genetic algorithms and random keys for sequencing and optimization (1994) ORSA Journal on Computing, 6, pp. 154-160
  • Belenguer, J., Benavent, E., A Cutting Plane algorithm for the capacitated arc routing problem (2003) Computers and Operations Research, 30, pp. 705-720
  • Benavent, E., Campos, V., Corberán, A., Mota, E., The capacitated arc routing problem: Lower bounds (1992) Networks, 22, pp. 669-690
  • Beullens, P., Muyldermans, L., Cattrysse, D., Van Oudheusden, D., A Guided Local Search heuristic for the capacitated arc routing problem (2003) European Journal of Operational Research-Discrete Optimization, 147, pp. 629-643
  • Brandao, J., Eglese, R., A deterministic tabu search algorithm for the capacitated arc routing problem (2008) Computers and Operations Research, 35 (4), pp. 1112-1126. , DOI 10.1016/j.cor.2006.07.007, PII S0305054806001535
  • Pia, A., Filippi, C., A variable neighborhood descent algorithm for a real waste collection problem with mobile depots (2006) International Transactions in Operational Research, 13 (2), pp. 125-141. , DOI 10.1111/j.1475-3995.2006.00539.x
  • Dorigo, M., Stützle, T., (2004) Ant Colony Optimization, , 1st Ed. MIT Press Massachusetts
  • Eglese, R., Routing winter gritting vehicles (1994) Discrete Applied Mathematics, 48 (3), pp. 231-244
  • Ericsson, M., Resende, M.G.C., Pardalos, P.M., A genetic algorithm for the weight setting problem in OSPF routing (2002) Journal of Combinatorial Optimization, 6 (3), pp. 299-333. , DOI 10.1023/A:1014852026591
  • Goldberg, D., (1989) Genetic Algorithms in Search, Optimization and Machine Learning, , 1st Ed. Addison-Wesley Massachusetts
  • Golden, B.L., DeArmon, J.S., Baker, E.K., Computational experiments with algorithms for a class of routing problems (1983) Computers and Operations Research, 10 (1), pp. 47-59. , DOI 10.1016/0305-0548(83)90026-6
  • Golden, B., Wong, R., Capacitated arc routing problems (1981) Networks, 11, pp. 305-315
  • Goncalves, J.F., A hybrid genetic algorithm-heuristic for a two-dimensional orthogonal packing problem (2007) European Journal of Operational Research, 183 (3), pp. 1212-1229. , DOI 10.1016/j.ejor.2005.11.062, PII S0377221706003006
  • Goncalves, J.F., De Almeida, J.R., A hybrid genetic algorithm for assembly line balancing (2002) Journal of Heuristics, 8 (6), pp. 629-642. , DOI 10.1023/A:1020377910258
  • Gonçalves, J.F., Resende, M.G.C., An evolutionary algorithm for manufacturing cell formation (2004) Computers and Industrial Engineering, 47, pp. 247-273
  • Gonçalves, J.F., Resende, M.G.C., Biased random-key genetic algorithms for combinatorial optimization (2011) Journal of Heuristics, 17, pp. 487-525
  • Gonçalves, J.F., Resende, M., Almeida, J., A biased random-key genetic algorithm with forward-backward improvement for the resource constrained project scheduling problem (2010) Journal of Heuristics, , published Online
  • Haimovich, M., Rinnooy Kan, A.H.G., Bounds and heuristics for capacitated routing problems (1985) Mathematics of Operations Research, 10 (4), pp. 527-542
  • Hertz, A., Laporte, G., Mittaz, M., A Tabu Search heuristic for the capacitated arc routing problem (2000) Operations Research, 48, pp. 129-135
  • Hertz, A., Mittaz, M., A variable neighborhood descent algorithm for the undirected capacitated arc routing problem (2001) Transportation Science, 35 (4), pp. 425-434. , DOI 10.1287/trsc.35.4.425.10431
  • Hirabayashi, R., Saruwatari, Y., Nishida, N., Tour construction algorithm for the capacitated arc routing problem (1992) Asia-Pacific Journal of Operational Research, 9, pp. 155-175
  • Hoos, H., Stützle, T., (2005) Stochastic Local Search Foundations and Applications, , 1st Ed. McGraw-Hill San Francisco
  • Lacomme, P., Prins, C., Tanguy, A., First Competitive Ant Colony Scheme for the CARP (2004) Lecture Notes in Computer Science, (3172), pp. 426-427. , Ant Colony Optimization and Swarm Intelligence
  • Maniezzo, V., Algorithms for large directed CARP instances: Urban solid waste collection operational support Technical Report UBLCS-2004-16, , University of Bologna, Department of Computer Science
  • Muyldermans, L., Cattrysse, D., Van Oudheusden, D., Lotan, T., Districting for salt spreading operations (2002) European Journal of Operational Research, 139 (3), pp. 521-532. , DOI 10.1016/S0377-2217(01)00184-9, PII S0377221701001849
  • Samanlioglu, F., Ferrell, W., Kurz, M., A memetic random-key genetic algorithm for a symmetric multi-objective salesman problem (2008) Computers and Industrial Engineering, 55, pp. 439-449
  • Snyder, L.V., Daskin, M.S., A random-key genetic algorithm for the generalized traveling salesman problem (2006) European Journal of Operational Research, 174 (1), pp. 38-53. , DOI 10.1016/j.ejor.2004.09.057, PII S0377221705002523
  • Spears, W., Dejong, K., On the Virtues of Parameterized Uniform Crossover (1991) Proceedings of the Fourth International Conference on Genetic Algorithms, pp. 230-236. , San Diego-USA
  • Ulusoy Gunduz, Fleet sixe and mix problem for capacitated arc routing (1985) European Journal of Operational Research, 22 (3), pp. 329-337. , DOI 10.1016/0377-2217(85)90252-8
  • Zhu, Z., Li, X., Yang, Y., Deng, X., Xia, M., Xie, Z., A hybrid genetic algorithm for the multiple depot capacitated arc routing problem (2007) Proceedings of the IEEE International Conference on Automation and Logistics, pp. 2252-2258. , Jinan-China

Citas:

---------- APA ----------
Martinez, C., Loiseau, I., Resende, M.G.C. & Rodriguez, S. (2011) . BRKGA algorithm for the Capacitated Arc Routing Problem. Electronic Notes in Theoretical Computer Science, 281, 69-83.
http://dx.doi.org/10.1016/j.entcs.2011.11.026
---------- CHICAGO ----------
Martinez, C., Loiseau, I., Resende, M.G.C., Rodriguez, S. "BRKGA algorithm for the Capacitated Arc Routing Problem" . Electronic Notes in Theoretical Computer Science 281 (2011) : 69-83.
http://dx.doi.org/10.1016/j.entcs.2011.11.026
---------- MLA ----------
Martinez, C., Loiseau, I., Resende, M.G.C., Rodriguez, S. "BRKGA algorithm for the Capacitated Arc Routing Problem" . Electronic Notes in Theoretical Computer Science, vol. 281, 2011, pp. 69-83.
http://dx.doi.org/10.1016/j.entcs.2011.11.026
---------- VANCOUVER ----------
Martinez, C., Loiseau, I., Resende, M.G.C., Rodriguez, S. BRKGA algorithm for the Capacitated Arc Routing Problem. Electron. Notes Theor. Comput. Sci. 2011;281:69-83.
http://dx.doi.org/10.1016/j.entcs.2011.11.026