BRKGA algorithm for the Capacitated Arc Routing Problem
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 metaheuri...
Guardado en:
Autores principales: | , , , |
---|---|
Formato: | Artículo publishedVersion |
Publicado: |
2011
|
Materias: | |
Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_15710661_v281_n_p69_Martinez http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_15710661_v281_n_p69_Martinez_oai |
Aporte de: |
id |
I28-R145-paper_15710661_v281_n_p69_Martinez_oai |
---|---|
record_format |
dspace |
spelling |
I28-R145-paper_15710661_v281_n_p69_Martinez_oai2020-10-19 Martinez, C. Loiseau, I. Resende, M.G.C. Rodriguez, S. 2011 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. Fil:Loiseau, I. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf http://hdl.handle.net/20.500.12110/paper_15710661_v281_n_p69_Martinez info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar Electron. Notes Theor. Comput. Sci. 2011;281:69-83 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 BRKGA algorithm for the Capacitated Arc Routing Problem info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_15710661_v281_n_p69_Martinez_oai |
institution |
Universidad de Buenos Aires |
institution_str |
I-28 |
repository_str |
R-145 |
collection |
Repositorio Digital de la Universidad de Buenos Aires (UBA) |
topic |
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 |
spellingShingle |
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 Martinez, C. Loiseau, I. Resende, M.G.C. Rodriguez, S. BRKGA algorithm for the Capacitated Arc Routing Problem |
topic_facet |
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 |
description |
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. |
format |
Artículo Artículo publishedVersion |
author |
Martinez, C. Loiseau, I. Resende, M.G.C. Rodriguez, S. |
author_facet |
Martinez, C. Loiseau, I. Resende, M.G.C. Rodriguez, S. |
author_sort |
Martinez, C. |
title |
BRKGA algorithm for the Capacitated Arc Routing Problem |
title_short |
BRKGA algorithm for the Capacitated Arc Routing Problem |
title_full |
BRKGA algorithm for the Capacitated Arc Routing Problem |
title_fullStr |
BRKGA algorithm for the Capacitated Arc Routing Problem |
title_full_unstemmed |
BRKGA algorithm for the Capacitated Arc Routing Problem |
title_sort |
brkga algorithm for the capacitated arc routing problem |
publishDate |
2011 |
url |
http://hdl.handle.net/20.500.12110/paper_15710661_v281_n_p69_Martinez http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_15710661_v281_n_p69_Martinez_oai |
work_keys_str_mv |
AT martinezc brkgaalgorithmforthecapacitatedarcroutingproblem AT loiseaui brkgaalgorithmforthecapacitatedarcroutingproblem AT resendemgc brkgaalgorithmforthecapacitatedarcroutingproblem AT rodriguezs brkgaalgorithmforthecapacitatedarcroutingproblem |
_version_ |
1766026786109390848 |