Resolución del problema de enrutamiento de vehículos con limitaciones de capacidad utilizando un procedimiento metaheurístico de dos fases
Este artículo presenta un procedimiento alternativo para resolver el problema de enrutamiento de vehículos con limitaciones de capacidad y flota homogénea (CVRP). Se propone un algoritmo metaheurístico que consta de la combinación de dos fases: diseño de rutas y planificación de la flota. La primera...
- Autores:
-
Daza-Escorcia, Julio Mario
Montoya-Torres, J. R. (Jairo Rafael)
Narducci-Marín, F. (Francesco)
- Tipo de recurso:
- Article of journal
- Fecha de publicación:
- 2009
- Institución:
- Universidad EIA .
- Repositorio:
- Repositorio EIA .
- Idioma:
- spa
- OAI Identifier:
- oai:repository.eia.edu.co:11190/193
- Acceso en línea:
- https://repository.eia.edu.co/handle/11190/193
- Palabra clave:
- REI00110
HEURÍSTICA
HEURISTIC
INFRAESTRUCTURA Y GESTIÓN DEL TERRITORIO
INFRAESTRUCTURE AND LAND PLANNING
PROBLEMA DE RUTEO DE VEHÍCULOS
PROBLEMA DEL AGENTE VIAJERO
OPTIMIZACIÓN COMBINATORIA
HEURÍSTICA
VEHICLE ROUTING PROBLEM
TRAVELING SALESMAN PROBLEM
COMBINATORIAL OPTIMIZATION
HEURISTIC
- Rights
- openAccess
- License
- Derechos Reservados - Universidad EIA, 2020
| id |
REIA2_81ce43a2c07662fa1efb301ced895879 |
|---|---|
| oai_identifier_str |
oai:repository.eia.edu.co:11190/193 |
| network_acronym_str |
REIA2 |
| network_name_str |
Repositorio EIA . |
| repository_id_str |
|
| dc.title.spa.fl_str_mv |
Resolución del problema de enrutamiento de vehículos con limitaciones de capacidad utilizando un procedimiento metaheurístico de dos fases |
| dc.title.alternative.spa.fl_str_mv |
Resolução do problema de roteamento de veículos com limitações de capacidade utilizando um procedimento metaheurístico de duas fases Solving the capacitated vehicle routing problem using a twophase metaheuristic procedure |
| title |
Resolución del problema de enrutamiento de vehículos con limitaciones de capacidad utilizando un procedimiento metaheurístico de dos fases |
| spellingShingle |
Resolución del problema de enrutamiento de vehículos con limitaciones de capacidad utilizando un procedimiento metaheurístico de dos fases REI00110 HEURÍSTICA HEURISTIC INFRAESTRUCTURA Y GESTIÓN DEL TERRITORIO INFRAESTRUCTURE AND LAND PLANNING PROBLEMA DE RUTEO DE VEHÍCULOS PROBLEMA DEL AGENTE VIAJERO OPTIMIZACIÓN COMBINATORIA HEURÍSTICA VEHICLE ROUTING PROBLEM TRAVELING SALESMAN PROBLEM COMBINATORIAL OPTIMIZATION HEURISTIC |
| title_short |
Resolución del problema de enrutamiento de vehículos con limitaciones de capacidad utilizando un procedimiento metaheurístico de dos fases |
| title_full |
Resolución del problema de enrutamiento de vehículos con limitaciones de capacidad utilizando un procedimiento metaheurístico de dos fases |
| title_fullStr |
Resolución del problema de enrutamiento de vehículos con limitaciones de capacidad utilizando un procedimiento metaheurístico de dos fases |
| title_full_unstemmed |
Resolución del problema de enrutamiento de vehículos con limitaciones de capacidad utilizando un procedimiento metaheurístico de dos fases |
| title_sort |
Resolución del problema de enrutamiento de vehículos con limitaciones de capacidad utilizando un procedimiento metaheurístico de dos fases |
| dc.creator.fl_str_mv |
Daza-Escorcia, Julio Mario Montoya-Torres, J. R. (Jairo Rafael) Narducci-Marín, F. (Francesco) |
| dc.contributor.author.spa.fl_str_mv |
Daza-Escorcia, Julio Mario Montoya-Torres, J. R. (Jairo Rafael) Narducci-Marín, F. (Francesco) |
| dc.subject.lcsh.spa.fl_str_mv |
REI00110 |
| topic |
REI00110 HEURÍSTICA HEURISTIC INFRAESTRUCTURA Y GESTIÓN DEL TERRITORIO INFRAESTRUCTURE AND LAND PLANNING PROBLEMA DE RUTEO DE VEHÍCULOS PROBLEMA DEL AGENTE VIAJERO OPTIMIZACIÓN COMBINATORIA HEURÍSTICA VEHICLE ROUTING PROBLEM TRAVELING SALESMAN PROBLEM COMBINATORIAL OPTIMIZATION HEURISTIC |
| dc.subject.arcmarc.spa.fl_str_mv |
HEURÍSTICA HEURISTIC |
| dc.subject.eia.spa.fl_str_mv |
INFRAESTRUCTURA Y GESTIÓN DEL TERRITORIO INFRAESTRUCTURE AND LAND PLANNING |
| dc.subject.keywords.spa.fl_str_mv |
PROBLEMA DE RUTEO DE VEHÍCULOS PROBLEMA DEL AGENTE VIAJERO OPTIMIZACIÓN COMBINATORIA HEURÍSTICA VEHICLE ROUTING PROBLEM TRAVELING SALESMAN PROBLEM COMBINATORIAL OPTIMIZATION HEURISTIC |
| description |
Este artículo presenta un procedimiento alternativo para resolver el problema de enrutamiento de vehículos con limitaciones de capacidad y flota homogénea (CVRP). Se propone un algoritmo metaheurístico que consta de la combinación de dos fases: diseño de rutas y planificación de la flota. La primera fase está compuesta de procedimientos heurísticos y metaheurísticos donde se construye una solución inicial que es mejorada mediante búsqueda tabú obteniendo soluciones no dominadas en tiempo de cálculo polinomial. Para la segunda fase, correspondiente a la planificación (scheduling) de la flota, se propone abordar el problema partiendo de una analogía con el problema de programación de máquinas paralelas idénticas. Este procedimiento tiene como función objetivo minimizar el costo fijo causado por la utilización de la capacidad instalada. Esta alternativa se aplicó sobre una instancia generada aleatoriamente y una instancia real arrojando resultados significativos al compararse con las heurísticas evaluadas |
| publishDate |
2009 |
| dc.date.created.spa.fl_str_mv |
2009-12 |
| dc.date.submitted.spa.fl_str_mv |
2009-06-27 |
| dc.date.accepted.spa.fl_str_mv |
2009-11-18 |
| dc.date.accessioned.spa.fl_str_mv |
2013-11-26T15:11:11Z |
| dc.date.available.spa.fl_str_mv |
2013-11-26T15:11:11Z |
| dc.date.issued.spa.fl_str_mv |
2013-11-26 |
| dc.type.spa.fl_str_mv |
Artículo de revista |
| dc.type.coar.fl_str_mv |
http://purl.org/coar/resource_type/c_2df8fbb1 |
| dc.type.coar.spa.fl_str_mv |
http://purl.org/coar/resource_type/c_6501 |
| dc.type.driver.spa.fl_str_mv |
info:eu-repo/semantics/article |
| dc.type.version.spa.fl_str_mv |
info:eu-repo/semantics/publishedVersion |
| dc.type.content.spa.fl_str_mv |
Text |
| dc.type.redcol.spa.fl_str_mv |
https://purl.org/redcol/resource_type/ART |
| dc.type.coarversion.spa.fl_str_mv |
http://purl.org/coar/version/c_970fb48d4fbd8a85 |
| format |
http://purl.org/coar/resource_type/c_6501 |
| status_str |
publishedVersion |
| dc.identifier.issn.spa.fl_str_mv |
ISSN 17941237 |
| dc.identifier.uri.spa.fl_str_mv |
https://repository.eia.edu.co/handle/11190/193 |
| dc.identifier.bibliographiccitation.spa.fl_str_mv |
Daza, J. M., Montoya, J. R., y Narducci, F. (2009). Resolución del problema de enrutamiento de vehículos con limitaciones de capacidad utilizando un procedimiento metaheurístico de dos fases, Revista EIA, 6 (12), 23-38. doi: http://hdl.handle.net/11190/193 |
| identifier_str_mv |
ISSN 17941237 Daza, J. M., Montoya, J. R., y Narducci, F. (2009). Resolución del problema de enrutamiento de vehículos con limitaciones de capacidad utilizando un procedimiento metaheurístico de dos fases, Revista EIA, 6 (12), 23-38. doi: http://hdl.handle.net/11190/193 |
| url |
https://repository.eia.edu.co/handle/11190/193 |
| dc.language.iso.spa.fl_str_mv |
spa |
| language |
spa |
| dc.relation.ispartof.spa.fl_str_mv |
Revista EIA |
| dc.relation.references.spa.fl_str_mv |
Aarts, E. and Lenstra, J. Local search in combinatorial optimization. John Wiley & Sons. 2003. Applegate, David L.; Bixby, Robert E.; Chvátal, Vasek and Cook, William J. “The traveling salesman problem: a computational study”. Princeton University Press, 2006, 606 p. Archetti, C.; Mansini, R. and Speranza M. G. “The split delivery vehicle routing problem with small capacity”, Technical Report n. 201, Department of Quantitative Methods, University of Brescia, 2001. Arora, S. “Polynomial time approximation schemes for euclidian traveling salesman and other geometric problems”, Journal of the ACM, vol. 45, No. 5, September 1998, pp. 753-782. Baptista, S.; Oliveira, R. C. and Zúquete, E. “A period vehicle routing case study”, European Journal of Operational Research, 139:220-229, Elsevier, 2002. |
| dc.rights.spa.fl_str_mv |
Derechos Reservados - Universidad EIA, 2020 |
| dc.rights.uri.spa.fl_str_mv |
https://creativecommons.org/licenses/by-nc/4.0/ |
| dc.rights.accessrights.spa.fl_str_mv |
info:eu-repo/semantics/openAccess |
| dc.rights.creativecommons.spa.fl_str_mv |
Atribución-NoComercial |
| dc.rights.coar.spa.fl_str_mv |
http://purl.org/coar/access_right/c_abf2 |
| rights_invalid_str_mv |
Derechos Reservados - Universidad EIA, 2020 https://creativecommons.org/licenses/by-nc/4.0/ Atribución-NoComercial http://purl.org/coar/access_right/c_abf2 |
| eu_rights_str_mv |
openAccess |
| dc.format.extent.spa.fl_str_mv |
16 p. |
| dc.format.mimetype.spa.fl_str_mv |
application/pdf |
| dc.publisher.editor.spa.fl_str_mv |
Fondo Editorial EIA |
| institution |
Universidad EIA . |
| bitstream.url.fl_str_mv |
https://repository.eia.edu.co/bitstreams/bcb6dae5-c6b1-4a5a-8b02-9dfd06736bf0/download https://repository.eia.edu.co/bitstreams/bebe5bbb-236c-4f47-bdec-f95d489de9dd/download https://repository.eia.edu.co/bitstreams/ba55453a-13ae-405e-afe7-71bca18c15eb/download https://repository.eia.edu.co/bitstreams/a01f886a-5818-45ab-bce5-894595ada232/download |
| bitstream.checksum.fl_str_mv |
72b45e05187955aa986613d714144141 9e41630f0240dc569540f430f2f142ea 66874b0b9366b748c60895d2fb6339f8 39a596294f33d5875726cd8fa190edf7 |
| bitstream.checksumAlgorithm.fl_str_mv |
MD5 MD5 MD5 MD5 |
| repository.name.fl_str_mv |
Repositorio Institucional Universidad EIA |
| repository.mail.fl_str_mv |
bdigital@metabiblioteca.com |
| _version_ |
1814100877528530944 |
| spelling |
Daza-Escorcia, Julio Mario8aa692b1a2166cf5a2dabe0267a1ba20-1Montoya-Torres, J. R. (Jairo Rafael)9b36650fe9a840aeca4a4fa1a52fe9c6-1Narducci-Marín, F. (Francesco)a321798bd44d3ab7fae1d851966fd4fc-1juliomariodaza@hotmail.comjairo.montoya@unisabana.edu.cofnarducci78@hotmail.com2013-11-26T15:11:11Z2013-11-26T15:11:11Z2009-122013-11-262009-06-272009-11-18ISSN 17941237https://repository.eia.edu.co/handle/11190/193Daza, J. M., Montoya, J. R., y Narducci, F. (2009). Resolución del problema de enrutamiento de vehículos con limitaciones de capacidad utilizando un procedimiento metaheurístico de dos fases, Revista EIA, 6 (12), 23-38. doi: http://hdl.handle.net/11190/193Este artículo presenta un procedimiento alternativo para resolver el problema de enrutamiento de vehículos con limitaciones de capacidad y flota homogénea (CVRP). Se propone un algoritmo metaheurístico que consta de la combinación de dos fases: diseño de rutas y planificación de la flota. La primera fase está compuesta de procedimientos heurísticos y metaheurísticos donde se construye una solución inicial que es mejorada mediante búsqueda tabú obteniendo soluciones no dominadas en tiempo de cálculo polinomial. Para la segunda fase, correspondiente a la planificación (scheduling) de la flota, se propone abordar el problema partiendo de una analogía con el problema de programación de máquinas paralelas idénticas. Este procedimiento tiene como función objetivo minimizar el costo fijo causado por la utilización de la capacidad instalada. Esta alternativa se aplicó sobre una instancia generada aleatoriamente y una instancia real arrojando resultados significativos al compararse con las heurísticas evaluadasThis paper presents an alternative procedure to solve the Capacitated Vehicle Routing Problem (CVRP) with homogeneous fleet. The paper proposes a two-phase metaheuristic algorithm: routes design and fleet scheduling. The first phase is based on heuristics and metaheuristics procedures in order to build an initial solution that is then improved using tabu search to obtain non-dominated solutions in polynomial computational time. For the second phase, corresponding to fleet scheduling, the problem is approached using an analogy with the identical parallel machine scheduling problem. This procedure looks for the minimization of the fixed cost of using installed capacity as the objective function. The proposed procedure was tested using both a random-generated instance and real data, giving competitive results in comparison with other heuristics tested.16 p.application/pdfspaRevista EIAAarts, E. and Lenstra, J. Local search in combinatorial optimization. John Wiley & Sons. 2003.Applegate, David L.; Bixby, Robert E.; Chvátal, Vasek and Cook, William J. “The traveling salesman problem: a computational study”. Princeton University Press, 2006, 606 p.Archetti, C.; Mansini, R. and Speranza M. G. “The split delivery vehicle routing problem with small capacity”, Technical Report n. 201, Department of Quantitative Methods, University of Brescia, 2001.Arora, S. “Polynomial time approximation schemes for euclidian traveling salesman and other geometric problems”, Journal of the ACM, vol. 45, No. 5, September 1998, pp. 753-782.Baptista, S.; Oliveira, R. C. and Zúquete, E. “A period vehicle routing case study”, European Journal of Operational Research, 139:220-229, Elsevier, 2002.Derechos Reservados - Universidad EIA, 2020https://creativecommons.org/licenses/by-nc/4.0/El autor de la obra, actuando en nombre propio, hace entrega del ejemplar respectivo y de sus anexos en formato digital o electrónico y autoriza a la ESCUELA DE INGENIERIA DE ANTIOQUIA, para que en los términos establecidos en la Ley 23 de 1982, Ley 44 de 1993, Decisión andina 351 de 1993, Decreto 460 de 1995, y demás normas generales sobre la materia, utilice y use por cualquier medio conocido o por conocer, los derechos patrimoniales de reproducción, comunicación pública, transformación y distribución de la obra objeto del presente documento. PARÁGRAFO: La presente autorización se hace extensiva no sólo a las dependencias y derechos de uso sobre la obra en formato o soporte material, sino también para formato virtual, electrónico, digital, y en red, internet, extranet, intranet, etc., y en general en cualquier formato conocido o por conocer. EL AUTOR, manifiesta que la obra objeto de la presente autorización es original y la realiza sin violar o usurpar derechos de autor de terceros, por lo tanto la obra es de exclusiva autoría y tiene la titularidad sobre la misma. PARÁGRAFO: En caso de presentarse cualquier reclamación o acción por parte de un tercero en cuanto a los derechos de autor sobre la obra en cuestión, EL AUTOR, asumirá toda la responsabilidad, y saldrá en defensa de los derechos aquí autorizados; para todos los efectos la ESCUELA DE INGENIERÍA DE ANTIOQUIA actúa como un tercero de buena fe.info:eu-repo/semantics/openAccessAtribución-NoComercialhttp://purl.org/coar/access_right/c_abf2REI00110HEURÍSTICAHEURISTICINFRAESTRUCTURA Y GESTIÓN DEL TERRITORIOINFRAESTRUCTURE AND LAND PLANNINGPROBLEMA DE RUTEO DE VEHÍCULOSPROBLEMA DEL AGENTE VIAJEROOPTIMIZACIÓN COMBINATORIAHEURÍSTICAVEHICLE ROUTING PROBLEMTRAVELING SALESMAN PROBLEMCOMBINATORIAL OPTIMIZATIONHEURISTICResolución del problema de enrutamiento de vehículos con limitaciones de capacidad utilizando un procedimiento metaheurístico de dos fasesResolução do problema de roteamento de veículos com limitações de capacidade utilizando um procedimento metaheurístico de duas fasesSolving the capacitated vehicle routing problem using a twophase metaheuristic procedureArtículo de revistahttp://purl.org/coar/resource_type/c_6501http://purl.org/coar/resource_type/c_2df8fbb1info:eu-repo/semantics/articleinfo:eu-repo/semantics/publishedVersionTexthttps://purl.org/redcol/resource_type/ARThttp://purl.org/coar/version/c_970fb48d4fbd8a85Fondo Editorial EIAPublicationTHUMBNAILREI00110.pdf.jpgREI00110.pdf.jpgGenerated Thumbnailimage/jpeg11732https://repository.eia.edu.co/bitstreams/bcb6dae5-c6b1-4a5a-8b02-9dfd06736bf0/download72b45e05187955aa986613d714144141MD54ORIGINALREI00110.pdfREI00110.pdfapplication/pdf1139221https://repository.eia.edu.co/bitstreams/bebe5bbb-236c-4f47-bdec-f95d489de9dd/download9e41630f0240dc569540f430f2f142eaMD51LICENSElicense.txtlicense.txttext/plain; charset=utf-81494https://repository.eia.edu.co/bitstreams/ba55453a-13ae-405e-afe7-71bca18c15eb/download66874b0b9366b748c60895d2fb6339f8MD52TEXTREI00110.pdf.txtREI00110.pdf.txtExtracted texttext/plain51113https://repository.eia.edu.co/bitstreams/a01f886a-5818-45ab-bce5-894595ada232/download39a596294f33d5875726cd8fa190edf7MD5311190/193oai:repository.eia.edu.co:11190/1932023-07-25 16:48:24.402https://creativecommons.org/licenses/by-nc/4.0/Derechos Reservados - Universidad EIA, 2020open.accesshttps://repository.eia.edu.coRepositorio Institucional Universidad EIAbdigital@metabiblioteca.comRWwgYXV0b3IgZGUgbGEgb2JyYSwgYWN0dWFuZG8gZW4gbm9tYnJlIHByb3BpbywgSGFjZSBlbnRyZWdhIGRlbCBlamVtcGxhciByZXNwZWN0aXZvIHkgZGUgc3VzIGFuZXhvcyBlbiBmb3JtYXRvIGRpZ2l0YWwgbyBlbGVjdHLDs25pY28uIAoKWSBhdXRvcml6YSBhIGxhIEVTQ1VFTEEgREUgSU5HRU5JRVJJQSBERSBBTlRJT1FVSUEsIHBhcmEgcXVlIGVuIGxvcyB0w6lybWlub3MgZXN0YWJsZWNpZG9zIGVuOgoKIC0gbGEgTGV5IDIzIGRlIDE5ODIKIC0gTGV5IDQ0IGRlIDE5OTMKLSBEZWNpc2nDs24gYW5kaW5hIDM1MSBkZSAxOTkzCiAtIERlY3JldG8gNDYwIGRlIDE5OTUKCiB5IGRlbcOhcyBub3JtYXMgZ2VuZXJhbGVzIHNvYnJlIGxhIG1hdGVyaWEsIHV0aWxpY2UgeSB1c2UgcG9yIGN1YWxxdWllciBtZWRpbyBjb25vY2lkbyBvIHBvciBjb25vY2VyLCBsb3MgZGVyZWNob3MgcGF0cmltb25pYWxlcyBkZSByZXByb2R1Y2Npw7NuLAogY29tdW5pY2FjacOzbiBww7pibGljYSwgdHJhbnNmb3JtYWNpw7NuIHkgZGlzdHJpYnVjacOzbiBkZSBsYSBvYnJhIG9iamV0byBkZWwgcHJlc2VudGUgZG9jdW1lbnRvLiAKCiBQQVJHUkFGTzogTGEgcHJlc2VudGUgYXV0b3JpemFjacOzbiBzZSBoYWNlIGV4dGVuc2l2YSBubyBzb2xvIGEgbGFzIGRlcGVuZGVuY2lhcyB5IGRlcmVjaG9zIGRlIHVzbyBzb2JyZSBsYSBvYnJhIGVuIGZvcm1hdG8gbyBzb3BvcnRlIG1hdGVyaWFsLCAKIHNpbm8gdGFtYmnDqW4gcGFyYSBmb3JtYXRvIHZpcnR1YWwsIGVsZWN0csOzbmljbywgZGlnaXRhbCwgeSBjdXlvIHVzbyBzZSBkZSBlbiByZWQsIGludGVybmV0LCBleHRyYW5ldCwgaW50cmFuZXQsIGV0Yy4sIHkgZW4gZ2VuZXJhbCBlbiBjdWFscXVpZXIKIGZvcm1hdG8gY29ub2NpZG8gbyBwb3IgY29ub2Nlci4gCgogRUwgQVVUT1IsIG1hbmlmaWVzdGEgcXVlIGxhIG9icmEgb2JqZXRvIGRlIGxhIHByZXNlbnRlIGF1dG9yaXphY2nDs24gZXMgb3JpZ2luYWwgeSBsYSByZWFsaXphIHNpbiB2aW9sYXIgbyB1c3VycGFyIGRlcmVjaG9zIGRlIGF1dG9yIGRlIHRlcmNlcm9zLAogcG9yIGxvIHRhbnRvIGxhIG9icmEgZXMgZGUgZXhjbHVzaXZhIGF1dG9yw61hIHkgdGllbmUgbGEgdGl0dWxhcmlkYWQgc29icmUgbGEgbWlzbWEuClBBUkFHUkFGTzogRW4gY2FzbyBkZSBwcmVzZW50YXJzZSBjdWFscXVpZXIgcmVjbGFtYWNpw7NuIG8gYWNjacOzbiBwb3IgcGFydGUgZGUgdW4gdGVyY2VybyBlbiBjdWFudG8gYSBsb3MgZGVyZWNob3MgZGUgYXV0b3Igc29icmUgbGEgb2JyYSBlbiAKY3Vlc3Rpw7NuLCBFTCBBVVRPUiwgYXN1bWlyw6HCoSB0b2RhIGxhIHJlc3BvbnNhYmlsaWRhZCwgeSBzYWxkcsOhwqEgZW4gZGVmZW5zYSBkZSBsb3MgZGVyZWNob3MgYXF1w60gYXV0b3JpemFkb3M7IHBhcmEgdG9kb3MgbG9zIGVmZWN0b3MgTGEgRVNDVUVMQSAKREUgSU5HRU5JRVJJQSBERSBBTlRJT1FVSUEgYWN0w7phIGNvbW8gdW4gdGVyY2VybyBkZSBidWVuYSBmZS4K |