Modificación del problema del agente viajero aplicado a un caso de estudio

El presente proyecto muestra la aplicación de una modificación al problema del agente viajero conocida como camino hamiltoniano, en la cual el agente debe visitar un número de ciudades una sola vez y terminar su recorrido en la última ciudad de la red. Trasladando este problema a una situación donde...

Full description

Autores:
Zapata Trocha, Miguel Maria
Rueda Vecino, Maria Jose
Palomino Mendoza, Maria Josefina
Tipo de recurso:
Fecha de publicación:
2017
Institución:
Universidad del Norte
Repositorio:
Repositorio Uninorte
Idioma:
spa
OAI Identifier:
oai:manglar.uninorte.edu.co:10584/7316
Acceso en línea:
http://hdl.handle.net/10584/7316
Palabra clave:
Heurísticas
Algoritmo
Óptima
Minimice
Distancia
Heuristic
Algorithm
Optimal
Minimizes
Rights
License
Universidad del Norte
id REPOUNORT2_dd24b78db7c82bedbb2265a3b829c420
oai_identifier_str oai:manglar.uninorte.edu.co:10584/7316
network_acronym_str REPOUNORT2
network_name_str Repositorio Uninorte
repository_id_str
spelling Yie Pinedo, Ruben DarioZapata Trocha, Miguel MariaRueda Vecino, Maria JosePalomino Mendoza, Maria Josefina2017-06-06T19:59:20Z2017-06-06T19:59:20Z2017-05-25http://hdl.handle.net/10584/7316El presente proyecto muestra la aplicación de una modificación al problema del agente viajero conocida como camino hamiltoniano, en la cual el agente debe visitar un número de ciudades una sola vez y terminar su recorrido en la última ciudad de la red. Trasladando este problema a una situación donde se tiene un vehículo con capacidad infinita, se busca determinar la ruta óptima que minimice el recorrido entre 10 de las principales ciudades de Colombia. En un caso la ciudad de origen es determinada previamente pero en el otro es escogida por el algoritmo aplicado. Con el fin de hallar la ruta óptima en ambos casos, se utilizó la herramienta Matlab para la programación del TSP modificado y de otros métodos como la heurística del vecino más cercano y el algoritmo de búsqueda tabú, donde se realizaron varias iteraciones en las cuales se iba aumentando el número de ciudades con el fin de determinar la dimensión computacional de la modificación del problema del agente viajero. Los resultados arrojados por el modelo del tsp aplicando la búsqueda exhaustiva fueron significativos al momento de compararlo con los otros métodos.The present project shows the application of a modification to the problem of the travelling salesman problem known as Hamiltonian path, in which the agent must visit a number of cities once and finish his journey in the last city of the network. Transferring this problem to a situation where there is a vehicle with infinite capacity, seeks to determine the optimal route that minimizes the travel distance between 10 of the main cities of Colombia. In one case the city of origin is previously determined but in the other it is chosen by the applied algorithm. In order to find the optimal path in both cases, it was used the Matlab tool to program the modified TSP and other methods such as the nearest neighbor heuristic and the tabu search algorithm, where several iterations were performed in which was increasing the number of cities in order to determine the computational dimension of the modification of the travelling salesman problem. The results of the TSP model applying the exhaustive search were significant when compared to the other methods.spaBarranquilla, Universidad del Norte, 2017Universidad del Nortehttp://purl.org/coar/access_right/c_abf2HeurísticasAlgoritmoÓptimaMinimiceDistanciaHeuristicAlgorithmOptimalMinimizesModificación del problema del agente viajero aplicado a un caso de estudioModification of traveler salesman problem applied to a case of studyarticlehttp://purl.org/coar/resource_type/c_6501ORIGINAL Modificación del problema del agente viajero aplicado a un caso de estudio.png Modificación del problema del agente viajero aplicado a un caso de estudio.pngimage/png1170860http://172.16.14.36:8080/bitstream/10584/7316/2/%20Modificaci%c3%b3n%20del%20problema%20del%20agente%20viajero%20aplicado%20a%20un%20caso%20de%20estudio.png4d1fb5a0b5360a3cfc4ba6bd11000391MD52 Modificación del problema del agente viajero aplicado a un caso de estudio.pdf Modificación del problema del agente viajero aplicado a un caso de estudio.pdfapplication/pdf857927http://172.16.14.36:8080/bitstream/10584/7316/5/%20Modificaci%c3%b3n%20del%20problema%20del%20agente%20viajero%20aplicado%20a%20un%20caso%20de%20estudio.pdf9d3722dd5fedd2e564bd2df3c4d1a104MD55LICENSElicense.txtlicense.txttext/plain; charset=utf-81748http://172.16.14.36:8080/bitstream/10584/7316/4/license.txt8a4605be74aa9ea9d79846c1fba20a33MD5410584/7316oai:172.16.14.36:10584/73162017-09-28 11:17:16.555Repositorio Digital de la Universidad del Nortemauribe@uninorte.edu.co
dc.title.es_ES.fl_str_mv Modificación del problema del agente viajero aplicado a un caso de estudio
dc.title.en_US.fl_str_mv Modification of traveler salesman problem applied to a case of study
title Modificación del problema del agente viajero aplicado a un caso de estudio
spellingShingle Modificación del problema del agente viajero aplicado a un caso de estudio
Heurísticas
Algoritmo
Óptima
Minimice
Distancia
Heuristic
Algorithm
Optimal
Minimizes
title_short Modificación del problema del agente viajero aplicado a un caso de estudio
title_full Modificación del problema del agente viajero aplicado a un caso de estudio
title_fullStr Modificación del problema del agente viajero aplicado a un caso de estudio
title_full_unstemmed Modificación del problema del agente viajero aplicado a un caso de estudio
title_sort Modificación del problema del agente viajero aplicado a un caso de estudio
dc.creator.fl_str_mv Zapata Trocha, Miguel Maria
Rueda Vecino, Maria Jose
Palomino Mendoza, Maria Josefina
dc.contributor.advisor.none.fl_str_mv Yie Pinedo, Ruben Dario
dc.contributor.author.none.fl_str_mv Zapata Trocha, Miguel Maria
Rueda Vecino, Maria Jose
Palomino Mendoza, Maria Josefina
dc.subject.es_ES.fl_str_mv Heurísticas
Algoritmo
Óptima
Minimice
Distancia
topic Heurísticas
Algoritmo
Óptima
Minimice
Distancia
Heuristic
Algorithm
Optimal
Minimizes
dc.subject.en_US.fl_str_mv Heuristic
Algorithm
Optimal
Minimizes
description El presente proyecto muestra la aplicación de una modificación al problema del agente viajero conocida como camino hamiltoniano, en la cual el agente debe visitar un número de ciudades una sola vez y terminar su recorrido en la última ciudad de la red. Trasladando este problema a una situación donde se tiene un vehículo con capacidad infinita, se busca determinar la ruta óptima que minimice el recorrido entre 10 de las principales ciudades de Colombia. En un caso la ciudad de origen es determinada previamente pero en el otro es escogida por el algoritmo aplicado. Con el fin de hallar la ruta óptima en ambos casos, se utilizó la herramienta Matlab para la programación del TSP modificado y de otros métodos como la heurística del vecino más cercano y el algoritmo de búsqueda tabú, donde se realizaron varias iteraciones en las cuales se iba aumentando el número de ciudades con el fin de determinar la dimensión computacional de la modificación del problema del agente viajero. Los resultados arrojados por el modelo del tsp aplicando la búsqueda exhaustiva fueron significativos al momento de compararlo con los otros métodos.
publishDate 2017
dc.date.accessioned.none.fl_str_mv 2017-06-06T19:59:20Z
dc.date.available.none.fl_str_mv 2017-06-06T19:59:20Z
dc.date.issued.none.fl_str_mv 2017-05-25
dc.type.es_ES.fl_str_mv article
dc.type.coar.fl_str_mv http://purl.org/coar/resource_type/c_6501
dc.identifier.uri.none.fl_str_mv http://hdl.handle.net/10584/7316
url http://hdl.handle.net/10584/7316
dc.language.iso.es_ES.fl_str_mv spa
language spa
dc.rights.es_ES.fl_str_mv Universidad del Norte
dc.rights.coar.fl_str_mv http://purl.org/coar/access_right/c_abf2
rights_invalid_str_mv Universidad del Norte
http://purl.org/coar/access_right/c_abf2
dc.publisher.es_ES.fl_str_mv Barranquilla, Universidad del Norte, 2017
institution Universidad del Norte
bitstream.url.fl_str_mv http://172.16.14.36:8080/bitstream/10584/7316/2/%20Modificaci%c3%b3n%20del%20problema%20del%20agente%20viajero%20aplicado%20a%20un%20caso%20de%20estudio.png
http://172.16.14.36:8080/bitstream/10584/7316/5/%20Modificaci%c3%b3n%20del%20problema%20del%20agente%20viajero%20aplicado%20a%20un%20caso%20de%20estudio.pdf
http://172.16.14.36:8080/bitstream/10584/7316/4/license.txt
bitstream.checksum.fl_str_mv 4d1fb5a0b5360a3cfc4ba6bd11000391
9d3722dd5fedd2e564bd2df3c4d1a104
8a4605be74aa9ea9d79846c1fba20a33
bitstream.checksumAlgorithm.fl_str_mv MD5
MD5
MD5
repository.name.fl_str_mv Repositorio Digital de la Universidad del Norte
repository.mail.fl_str_mv mauribe@uninorte.edu.co
_version_ 1812183100925411328

Publicaciones similares