Alternativa heurística MCM para problemas de ruteo de vehículos

El problema del ruteo de vehículos (VRP) implica una gran complejidad matemática para resolverlo. Esto dificulta su uso en organizaciones de tamaño pequeño y mediano, pues es necesario que inviertan para contar con software especializado y personal capacitado. Los métodos que se emplean para buscar...

Full description

Autores:
Flores Flores, José Luis
Alvarez-Madrigal, Manuel
Tipo de recurso:
Article of journal
Fecha de publicación:
2013
Institución:
Corporación Universidad de la Costa
Repositorio:
REDICUC - Repositorio CUC
Idioma:
spa
OAI Identifier:
oai:repositorio.cuc.edu.co:11323/2635
Acceso en línea:
https://hdl.handle.net/11323/2635
https://repositorio.cuc.edu.co/
Palabra clave:
Problema de Ruteo de vehículos
Métodos de optimización
Optimización combinatoria
Vehicle routing problem
Optimization methods
Combinatorial optimization
Rights
openAccess
License
http://purl.org/coar/access_right/c_abf2
id RCUC2_1103118cab89448c971aa75d0c37cc0e
oai_identifier_str oai:repositorio.cuc.edu.co:11323/2635
network_acronym_str RCUC2
network_name_str REDICUC - Repositorio CUC
repository_id_str
dc.title.spa.fl_str_mv Alternativa heurística MCM para problemas de ruteo de vehículos
dc.title.translated.eng.fl_str_mv MCM heuristic alternative for vehicle routing problem-solving
title Alternativa heurística MCM para problemas de ruteo de vehículos
spellingShingle Alternativa heurística MCM para problemas de ruteo de vehículos
Problema de Ruteo de vehículos
Métodos de optimización
Optimización combinatoria
Vehicle routing problem
Optimization methods
Combinatorial optimization
title_short Alternativa heurística MCM para problemas de ruteo de vehículos
title_full Alternativa heurística MCM para problemas de ruteo de vehículos
title_fullStr Alternativa heurística MCM para problemas de ruteo de vehículos
title_full_unstemmed Alternativa heurística MCM para problemas de ruteo de vehículos
title_sort Alternativa heurística MCM para problemas de ruteo de vehículos
dc.creator.fl_str_mv Flores Flores, José Luis
Alvarez-Madrigal, Manuel
dc.contributor.author.spa.fl_str_mv Flores Flores, José Luis
Alvarez-Madrigal, Manuel
dc.subject.spa.fl_str_mv Problema de Ruteo de vehículos
Métodos de optimización
Optimización combinatoria
topic Problema de Ruteo de vehículos
Métodos de optimización
Optimización combinatoria
Vehicle routing problem
Optimization methods
Combinatorial optimization
dc.subject.eng.fl_str_mv Vehicle routing problem
Optimization methods
Combinatorial optimization
description El problema del ruteo de vehículos (VRP) implica una gran complejidad matemática para resolverlo. Esto dificulta su uso en organizaciones de tamaño pequeño y mediano, pues es necesario que inviertan para contar con software especializado y personal capacitado. Los métodos que se emplean para buscar una solución óptima al problema VRP inician con una solución factible que va mejorando. Esta solución factible inicial se genera al azar, por algún otro método, o bien se puede utilizar una solución proporcionada por el usuario. En este trabajo se presenta un algoritmo para obtener una solución factible al problema de VRP, llamado Método de entros de Masa (MCM). Este método es de fácil ejecución y su desempeño difiere poco de las soluciones finales generadas por algoritmos comerciales, así que pudiera utilizarse como una aproximación a la solución del problema. Esto ayuda a extender la aplicación del VRP
publishDate 2013
dc.date.issued.none.fl_str_mv 2013-12-31
dc.date.accessioned.none.fl_str_mv 2019-02-19T22:57:12Z
dc.date.available.none.fl_str_mv 2019-02-19T22:57:12Z
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.content.spa.fl_str_mv Text
dc.type.driver.spa.fl_str_mv info:eu-repo/semantics/article
dc.type.redcol.spa.fl_str_mv http://purl.org/redcol/resource_type/ART
dc.type.version.spa.fl_str_mv info:eu-repo/semantics/acceptedVersion
format http://purl.org/coar/resource_type/c_6501
status_str acceptedVersion
dc.identifier.citation.spa.fl_str_mv Flores Flores, J., & Alvarez-Madrigal, M. (2013). Alternativa heurística MCM para problemas de ruteo de vehículos. INGE CUC, 9(2), 52-57. Recuperado a partir de https://revistascientificas.cuc.edu.co/ingecuc/article/view/6
dc.identifier.issn.spa.fl_str_mv 0122-6517, 2382-4700 electrónico
dc.identifier.uri.spa.fl_str_mv https://hdl.handle.net/11323/2635
dc.identifier.eissn.spa.fl_str_mv 2382-4700
dc.identifier.instname.spa.fl_str_mv Corporación Universidad de la Costa
dc.identifier.pissn.spa.fl_str_mv 0122-6517
dc.identifier.reponame.spa.fl_str_mv REDICUC - Repositorio CUC
dc.identifier.repourl.spa.fl_str_mv https://repositorio.cuc.edu.co/
identifier_str_mv Flores Flores, J., & Alvarez-Madrigal, M. (2013). Alternativa heurística MCM para problemas de ruteo de vehículos. INGE CUC, 9(2), 52-57. Recuperado a partir de https://revistascientificas.cuc.edu.co/ingecuc/article/view/6
0122-6517, 2382-4700 electrónico
2382-4700
Corporación Universidad de la Costa
0122-6517
REDICUC - Repositorio CUC
url https://hdl.handle.net/11323/2635
https://repositorio.cuc.edu.co/
dc.language.iso.none.fl_str_mv spa
language spa
dc.relation.ispartofseries.spa.fl_str_mv INGE CUC; Vol. 9, Núm. 2 (2013)
dc.relation.ispartofjournal.spa.fl_str_mv INGE CUC
INGE CUC
dc.relation.references.spa.fl_str_mv [1] G. B. Dantzig and J. H. Ramser, “The truck dispatchingproblem”, Management Science, Vol 6, pp. 80-91, 1959.
[2] J-.F. Courdeau, G.Laporte, J.- Y. Potvin, and F. Semet, “A guide to Vehicle Routing Heuristics”, The Journal of the Operational Research Society, vol. 53, n° 5, pp. 512- 522, 2002.
[3] J.- F. Cordeau, M. Gendreau, and G. A. Laporte, “ A tabu search heuristic for the periodic and multi-depot vehicle routing problems”, Networks, Vol. 30, pp. 105-119, 1997.
[4] F. Glover, M. Laguna, and R. Martí, “Principles of Scatter Search”, European Journal of Operational Research, Vol. 169, pp. 359-372, 2006.
[5] G. W. DePuy, G. E. Whitehouse, R. Moraga, and J. Using, The Meta-Raps Approach To Solve Combinatorial Problems. CiteSeerX, 2002.
[6] L. Rocha, C. González, and J. Orjuela, “Una revisión al estado del arte del problema de ruteo de vehículos: Evolución histórica y métodos de solución”, Ingeniería, vol. 16, n° 2, pp. 35 - 55, 2011.
[7] R. Resnick and K. S. Krane, Physics. New York: John Wiley & Sons, 2001.
[8] P. Toth and D. Vigo, “The Vehicle Routing Problem”, Monographs on discrete mathematics and applications, Philadelphia, USA, Society of Industrial and Applied Mathematics (SIAM), pp. 109-149, 2002.
[9] M. L. Balinzki and R. E. Quandt, “On an Integer Program for a Delivery Problem”, Operational Research, vol. 12, n° 2, pp. 300-304, 2002. Mencionado por J. Prawda.
[10] W. W. Garvin, H. W. Crandall, J.B. John and R. A. Spellman, “Aplications of Linear Programming in the Oil Industry”, Management Science, vol. 3, pp. 407, 1957. Mencionado por J. Prawda.
[11] G. Laporte, M. Gendreau, and A. Hertz, “An aproximation algorithm for the traveling salesman problem with time windows”, Institute for Operation Research and de Management Science – Operations Research, vol. 45, n° 4, pp. 639-641, 1998.
[12] C. A. Contardo Vera, “Formulación y solución de un problema de ruteo de vehículos con demanda variable en tiempo real, trasbordos y ventanas de tiempo”, memoria para optar al título de ingeniero civil matemático, Departamento de Ingeniería Matemática, Universidad de Chile, Santiago de Chile, Chile, 2005.
dc.relation.ispartofjournalabbrev.spa.fl_str_mv INGE CUC
dc.rights.accessrights.spa.fl_str_mv info:eu-repo/semantics/openAccess
dc.rights.coar.spa.fl_str_mv http://purl.org/coar/access_right/c_abf2
eu_rights_str_mv openAccess
rights_invalid_str_mv http://purl.org/coar/access_right/c_abf2
dc.format.mimetype.spa.fl_str_mv application/pdf
dc.publisher.spa.fl_str_mv Corporación Universidad de la Costa
dc.source.spa.fl_str_mv INGE CUC
institution Corporación Universidad de la Costa
dc.source.url.spa.fl_str_mv https://revistascientificas.cuc.edu.co/ingecuc/article/view/6
bitstream.url.fl_str_mv https://repositorio.cuc.edu.co/bitstreams/cad46504-8d22-4a98-8bbd-28252dd97df5/download
https://repositorio.cuc.edu.co/bitstreams/de6aff1d-ebe7-4251-8111-e67038d6e453/download
https://repositorio.cuc.edu.co/bitstreams/4d486d80-84d2-472b-ad39-859a1528d587/download
https://repositorio.cuc.edu.co/bitstreams/11c5cdea-7f74-4e66-beec-59d32d8452fe/download
bitstream.checksum.fl_str_mv 7aa5a8adafe4c3b5ad96005760af95ba
8a4605be74aa9ea9d79846c1fba20a33
d4b9d2093c6453b303f0b79b048cfbbb
5172bde6953c9818aa1445c2080052d8
bitstream.checksumAlgorithm.fl_str_mv MD5
MD5
MD5
MD5
repository.name.fl_str_mv Repositorio de la Universidad de la Costa CUC
repository.mail.fl_str_mv repdigital@cuc.edu.co
_version_ 1828166907589558272
spelling Flores Flores, José LuisAlvarez-Madrigal, Manuel2019-02-19T22:57:12Z2019-02-19T22:57:12Z2013-12-31Flores Flores, J., & Alvarez-Madrigal, M. (2013). Alternativa heurística MCM para problemas de ruteo de vehículos. INGE CUC, 9(2), 52-57. Recuperado a partir de https://revistascientificas.cuc.edu.co/ingecuc/article/view/60122-6517, 2382-4700 electrónicohttps://hdl.handle.net/11323/26352382-4700Corporación Universidad de la Costa0122-6517REDICUC - Repositorio CUChttps://repositorio.cuc.edu.co/El problema del ruteo de vehículos (VRP) implica una gran complejidad matemática para resolverlo. Esto dificulta su uso en organizaciones de tamaño pequeño y mediano, pues es necesario que inviertan para contar con software especializado y personal capacitado. Los métodos que se emplean para buscar una solución óptima al problema VRP inician con una solución factible que va mejorando. Esta solución factible inicial se genera al azar, por algún otro método, o bien se puede utilizar una solución proporcionada por el usuario. En este trabajo se presenta un algoritmo para obtener una solución factible al problema de VRP, llamado Método de entros de Masa (MCM). Este método es de fácil ejecución y su desempeño difiere poco de las soluciones finales generadas por algoritmos comerciales, así que pudiera utilizarse como una aproximación a la solución del problema. Esto ayuda a extender la aplicación del VRPThe Vehicle Routing Problem (VRP) involves a major mathematical complexity to solve it. This impedes its use in small and medium size organizations, because an invest-ment in specialized software and trained per-sonnel is required. The methods used to find an optimal solution to the VRP start with an improving workable solution. This initial solu-tion can be generated randomly, calculated by some other method, or even a solution provid-ed by the user can also be used. In this paper, we present an algorithm to obtain a feasible solution to the problem of VRP called Mass Center Method (MCM). The method is easy to perform and its performance differs little from the final solutions generated by commercial algorithms, therefore, it could be used as an approximation to the solution of the problem. This can help to extend the application of the V R PFlores Flores, José Luis-13014a68-2dfe-46a4-b469-471cca443910-0Alvarez-Madrigal, Manuel-87a918b0-4388-4a7e-bca1-9335440cacce-0application/pdfspaCorporación Universidad de la CostaINGE CUC; Vol. 9, Núm. 2 (2013)INGE CUCINGE CUC[1] G. B. Dantzig and J. H. Ramser, “The truck dispatchingproblem”, Management Science, Vol 6, pp. 80-91, 1959.[2] J-.F. Courdeau, G.Laporte, J.- Y. Potvin, and F. Semet, “A guide to Vehicle Routing Heuristics”, The Journal of the Operational Research Society, vol. 53, n° 5, pp. 512- 522, 2002.[3] J.- F. Cordeau, M. Gendreau, and G. A. Laporte, “ A tabu search heuristic for the periodic and multi-depot vehicle routing problems”, Networks, Vol. 30, pp. 105-119, 1997.[4] F. Glover, M. Laguna, and R. Martí, “Principles of Scatter Search”, European Journal of Operational Research, Vol. 169, pp. 359-372, 2006.[5] G. W. DePuy, G. E. Whitehouse, R. Moraga, and J. Using, The Meta-Raps Approach To Solve Combinatorial Problems. CiteSeerX, 2002.[6] L. Rocha, C. González, and J. Orjuela, “Una revisión al estado del arte del problema de ruteo de vehículos: Evolución histórica y métodos de solución”, Ingeniería, vol. 16, n° 2, pp. 35 - 55, 2011.[7] R. Resnick and K. S. Krane, Physics. New York: John Wiley & Sons, 2001.[8] P. Toth and D. Vigo, “The Vehicle Routing Problem”, Monographs on discrete mathematics and applications, Philadelphia, USA, Society of Industrial and Applied Mathematics (SIAM), pp. 109-149, 2002.[9] M. L. Balinzki and R. E. Quandt, “On an Integer Program for a Delivery Problem”, Operational Research, vol. 12, n° 2, pp. 300-304, 2002. Mencionado por J. Prawda.[10] W. W. Garvin, H. W. Crandall, J.B. John and R. A. Spellman, “Aplications of Linear Programming in the Oil Industry”, Management Science, vol. 3, pp. 407, 1957. Mencionado por J. Prawda.[11] G. Laporte, M. Gendreau, and A. Hertz, “An aproximation algorithm for the traveling salesman problem with time windows”, Institute for Operation Research and de Management Science – Operations Research, vol. 45, n° 4, pp. 639-641, 1998.[12] C. A. Contardo Vera, “Formulación y solución de un problema de ruteo de vehículos con demanda variable en tiempo real, trasbordos y ventanas de tiempo”, memoria para optar al título de ingeniero civil matemático, Departamento de Ingeniería Matemática, Universidad de Chile, Santiago de Chile, Chile, 2005.INGE CUCINGE CUChttps://revistascientificas.cuc.edu.co/ingecuc/article/view/6Problema de Ruteo de vehículosMétodos de optimizaciónOptimización combinatoriaVehicle routing problemOptimization methodsCombinatorial optimizationAlternativa heurística MCM para problemas de ruteo de vehículosMCM heuristic alternative for vehicle routing problem-solvingArtículo de revistahttp://purl.org/coar/resource_type/c_6501http://purl.org/coar/resource_type/c_2df8fbb1Textinfo:eu-repo/semantics/articlehttp://purl.org/redcol/resource_type/ARTinfo:eu-repo/semantics/acceptedVersioninfo:eu-repo/semantics/openAccesshttp://purl.org/coar/access_right/c_abf2PublicationORIGINALAlternativa Heurística MCM para Problemas de Ruteo de Vehículos.pdfAlternativa Heurística MCM para Problemas de Ruteo de Vehículos.pdfapplication/pdf558448https://repositorio.cuc.edu.co/bitstreams/cad46504-8d22-4a98-8bbd-28252dd97df5/download7aa5a8adafe4c3b5ad96005760af95baMD51LICENSElicense.txtlicense.txttext/plain; charset=utf-81748https://repositorio.cuc.edu.co/bitstreams/de6aff1d-ebe7-4251-8111-e67038d6e453/download8a4605be74aa9ea9d79846c1fba20a33MD52THUMBNAILAlternativa Heurística MCM para Problemas de Ruteo de Vehículos.pdf.jpgAlternativa Heurística MCM para Problemas de Ruteo de Vehículos.pdf.jpgimage/jpeg50666https://repositorio.cuc.edu.co/bitstreams/4d486d80-84d2-472b-ad39-859a1528d587/downloadd4b9d2093c6453b303f0b79b048cfbbbMD54TEXTAlternativa Heurística MCM para Problemas de Ruteo de Vehículos.pdf.txtAlternativa Heurística MCM para Problemas de Ruteo de Vehículos.pdf.txttext/plain25052https://repositorio.cuc.edu.co/bitstreams/11c5cdea-7f74-4e66-beec-59d32d8452fe/download5172bde6953c9818aa1445c2080052d8MD5511323/2635oai:repositorio.cuc.edu.co:11323/26352024-09-17 14:24:38.618open.accesshttps://repositorio.cuc.edu.coRepositorio de la Universidad de la Costa CUCrepdigital@cuc.edu.coTk9URTogUExBQ0UgWU9VUiBPV04gTElDRU5TRSBIRVJFClRoaXMgc2FtcGxlIGxpY2Vuc2UgaXMgcHJvdmlkZWQgZm9yIGluZm9ybWF0aW9uYWwgcHVycG9zZXMgb25seS4KCk5PTi1FWENMVVNJVkUgRElTVFJJQlVUSU9OIExJQ0VOU0UKCkJ5IHNpZ25pbmcgYW5kIHN1Ym1pdHRpbmcgdGhpcyBsaWNlbnNlLCB5b3UgKHRoZSBhdXRob3Iocykgb3IgY29weXJpZ2h0Cm93bmVyKSBncmFudHMgdG8gRFNwYWNlIFVuaXZlcnNpdHkgKERTVSkgdGhlIG5vbi1leGNsdXNpdmUgcmlnaHQgdG8gcmVwcm9kdWNlLAp0cmFuc2xhdGUgKGFzIGRlZmluZWQgYmVsb3cpLCBhbmQvb3IgZGlzdHJpYnV0ZSB5b3VyIHN1Ym1pc3Npb24gKGluY2x1ZGluZwp0aGUgYWJzdHJhY3QpIHdvcmxkd2lkZSBpbiBwcmludCBhbmQgZWxlY3Ryb25pYyBmb3JtYXQgYW5kIGluIGFueSBtZWRpdW0sCmluY2x1ZGluZyBidXQgbm90IGxpbWl0ZWQgdG8gYXVkaW8gb3IgdmlkZW8uCgpZb3UgYWdyZWUgdGhhdCBEU1UgbWF5LCB3aXRob3V0IGNoYW5naW5nIHRoZSBjb250ZW50LCB0cmFuc2xhdGUgdGhlCnN1Ym1pc3Npb24gdG8gYW55IG1lZGl1bSBvciBmb3JtYXQgZm9yIHRoZSBwdXJwb3NlIG9mIHByZXNlcnZhdGlvbi4KCllvdSBhbHNvIGFncmVlIHRoYXQgRFNVIG1heSBrZWVwIG1vcmUgdGhhbiBvbmUgY29weSBvZiB0aGlzIHN1Ym1pc3Npb24gZm9yCnB1cnBvc2VzIG9mIHNlY3VyaXR5LCBiYWNrLXVwIGFuZCBwcmVzZXJ2YXRpb24uCgpZb3UgcmVwcmVzZW50IHRoYXQgdGhlIHN1Ym1pc3Npb24gaXMgeW91ciBvcmlnaW5hbCB3b3JrLCBhbmQgdGhhdCB5b3UgaGF2ZQp0aGUgcmlnaHQgdG8gZ3JhbnQgdGhlIHJpZ2h0cyBjb250YWluZWQgaW4gdGhpcyBsaWNlbnNlLiBZb3UgYWxzbyByZXByZXNlbnQKdGhhdCB5b3VyIHN1Ym1pc3Npb24gZG9lcyBub3QsIHRvIHRoZSBiZXN0IG9mIHlvdXIga25vd2xlZGdlLCBpbmZyaW5nZSB1cG9uCmFueW9uZSdzIGNvcHlyaWdodC4KCklmIHRoZSBzdWJtaXNzaW9uIGNvbnRhaW5zIG1hdGVyaWFsIGZvciB3aGljaCB5b3UgZG8gbm90IGhvbGQgY29weXJpZ2h0LAp5b3UgcmVwcmVzZW50IHRoYXQgeW91IGhhdmUgb2J0YWluZWQgdGhlIHVucmVzdHJpY3RlZCBwZXJtaXNzaW9uIG9mIHRoZQpjb3B5cmlnaHQgb3duZXIgdG8gZ3JhbnQgRFNVIHRoZSByaWdodHMgcmVxdWlyZWQgYnkgdGhpcyBsaWNlbnNlLCBhbmQgdGhhdApzdWNoIHRoaXJkLXBhcnR5IG93bmVkIG1hdGVyaWFsIGlzIGNsZWFybHkgaWRlbnRpZmllZCBhbmQgYWNrbm93bGVkZ2VkCndpdGhpbiB0aGUgdGV4dCBvciBjb250ZW50IG9mIHRoZSBzdWJtaXNzaW9uLgoKSUYgVEhFIFNVQk1JU1NJT04gSVMgQkFTRUQgVVBPTiBXT1JLIFRIQVQgSEFTIEJFRU4gU1BPTlNPUkVEIE9SIFNVUFBPUlRFRApCWSBBTiBBR0VOQ1kgT1IgT1JHQU5JWkFUSU9OIE9USEVSIFRIQU4gRFNVLCBZT1UgUkVQUkVTRU5UIFRIQVQgWU9VIEhBVkUKRlVMRklMTEVEIEFOWSBSSUdIVCBPRiBSRVZJRVcgT1IgT1RIRVIgT0JMSUdBVElPTlMgUkVRVUlSRUQgQlkgU1VDSApDT05UUkFDVCBPUiBBR1JFRU1FTlQuCgpEU1Ugd2lsbCBjbGVhcmx5IGlkZW50aWZ5IHlvdXIgbmFtZShzKSBhcyB0aGUgYXV0aG9yKHMpIG9yIG93bmVyKHMpIG9mIHRoZQpzdWJtaXNzaW9uLCBhbmQgd2lsbCBub3QgbWFrZSBhbnkgYWx0ZXJhdGlvbiwgb3RoZXIgdGhhbiBhcyBhbGxvd2VkIGJ5IHRoaXMKbGljZW5zZSwgdG8geW91ciBzdWJtaXNzaW9uLgo=