| Revue: | Revista técnica de la Facultad de Ingeniería. Universidad del Zulia |
| Base de datos: | PERIÓDICA |
| Número de sistema: | 000447197 |
| ISSN: | 0254-0770 |
| Autores: | Costa Salas, Yasel José1 Abreu Ledón, René1 Coello Machado, Norge Isaías1 Nowé, Ann2 |
| Instituciones: | 1Universidad Central "Marta Abreu" de Las Villas, Departamento de Ingeniería Mecánica, Cuba 2Vrije Universiteit Brussel, Bruselas. Bélgica |
| Año: | 2012 |
| Volumen: | 35 |
| Número: | 3 |
| Paginación: | 311-320 |
| País: | Venezuela |
| Idioma: | Español |
| Tipo de documento: | Artículo |
| Enfoque: | Teórico |
| Resumen en español | El problema de los múltiples viajeros vendedores (Multiple Traveling Salesman Problem, mTSP) esuna extensión del bien conocido problema del viajero vendedor (Traveling Salesman Problem, TSP), en di-cha extensión se puede utilizar más de un vendedor con la finalidad de visitar un conjunto de ciudades so-lamente una vez. La formulación del mTSP se ajusta más a los problemas empresariales de la vida real,además puede ser extendida a una amplia variedad de los problemas de enrutamiento de vehículos (Vehi-cle Routing Problems, VRPs), mediante la incorporación de algunas restricciones, tales como: limitar lacapacidad del vehículo y establecer demanda cuantificable en cada cliente o ciudad. A pesar de que la lite-ratura científica para el TSP y los VRPs ha sido abundante, las investigaciones relativas al mTSP han sidolimitadas. En este sentido, la presente investigación propone un nuevo algoritmo inspirado en el compor-tamiento de las hormigas nombrado “Optimización basada en colonias de hormigas (Ant Colony Optimi-zation, ACO)” para la solución del mTSP, específicamente Sistema Multi-tipos de Colonias de Hormigas(M-ACS), donde cada colonia representa una posible solución global del problema. Las colonias cooperanmediante “frecuentes” intercambios de feromona en busca de una solución eficiente para el mTSP. El desempeño del algoritmo propuesto ha sido comparado con uno de los algoritmos de búsqueda local más efi-cientes para dicho problema, la heurística de Lin-Kernighan. Finalmente, los resultados computacionalesobtenidos confirman la competitividad y eficiencia de la estrategia de solución propuesta |
| Resumen en inglés | The Multiple Traveling Salesman problem (mTSP) is an extension of the well-known Traveling Sales-man Problem (TSP), where more than one salesman is allowed to be used in order to visit some cities justonce. Furthermore, the formulation of the mTSP seem more relevant for real-life applications, and alsocan be extended to a wide variety of Vehicle Routing Problems (VRPs) by incorporating some additionalside constraints, such as the vehicle capacity and customer demands. Although the literature for the TSPand the VRP is definitely wide, the mTSP has not received the same amount of attention. In that sense, thispaper proposes a new algorithm based on Ant Colony Optimization (ACO) for the mTSP, specificallyMulti-type Ant Colony System (M-ACS), where each colony represents a possible global solution. More-over, these colonies cooperate by means of “frequent” pheromone exchanges in order to find a competitivesolution for the mTSP. The algorithm performance has been compared with one of the most efficient localsearch algorithms for mTSP, the Lin-Kernighan algorithm. Computational results confirm the competi-tiveness and efficiency of the strategy we propose |
| Disciplinas: | Matemáticas |
| Palabras clave: | Matemáticas aplicadas, Algoritmo de procedimiento, Enrutamiento de vehículos, Problema del vendedor viajero, Sistema de colonias de hormigas |
| Keyword: | Ant colony system, Salesman algorithm, Traveling salesman problem, Vehicle routing |
| Texte intégral: | https://produccioncientificaluz.org/index.php/tecnica/article/view/6866/6855 |
