Multi-type ant colony system for solving the multiple traveling salesman problem.
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 just once. Furthermore, the formulation of the mTSP seem more relevant for real-life applications, an...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Universidad del Zulia
2013-03-01
|
| Series: | Revista Técnica de la Facultad de Ingeniería |
| Subjects: | |
| Online Access: | https://www.produccioncientificaluz.org/index.php/tecnica/article/view/6866 |
| _version_ | 1811296925800988672 |
|---|---|
| author | Yasel José Costa Salas René Abreu Ledón Norge Isaías Coello Machado Ann Nowé |
| author_facet | Yasel José Costa Salas René Abreu Ledón Norge Isaías Coello Machado Ann Nowé |
| author_sort | Yasel José Costa Salas |
| collection | DOAJ |
| description | 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 just once. Furthermore, the formulation of the mTSP seem more relevant for real-life applications, and also can be extended to a wide variety of Vehicle Routing Problems (VRPs) by incorporating some additional side constraints, such as the vehicle capacity and customer demands. Although the literature for the TSP and the VRP is definitely wide, the mTSP has not received the same amount of attention. In that sense, this paper proposes a new algorithm based on Ant Colony Optimization (ACO) for the mTSP, specifically Multi-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 competitive solution for the mTSP. The algorithm performance has been compared with one of the most efficient local search algorithms for mTSP, the Lin-Kernighan algorithm. Computational results confirm the competitiveness and efficiency of the strategy we propose.
|
| first_indexed | 2024-04-13T05:55:42Z |
| format | Article |
| id | doaj.art-32c7652d43c143d884a7d8d45ad9af25 |
| institution | Directory Open Access Journal |
| issn | 0254-0770 2477-9377 |
| language | English |
| last_indexed | 2024-04-13T05:55:42Z |
| publishDate | 2013-03-01 |
| publisher | Universidad del Zulia |
| record_format | Article |
| series | Revista Técnica de la Facultad de Ingeniería |
| spelling | doaj.art-32c7652d43c143d884a7d8d45ad9af252022-12-22T02:59:37ZengUniversidad del ZuliaRevista Técnica de la Facultad de Ingeniería0254-07702477-93772013-03-01353Multi-type ant colony system for solving the multiple traveling salesman problem.Yasel José Costa Salas0René Abreu Ledón1Norge Isaías Coello Machado2Ann Nowé3Universidad Central “Marta Abreu” de Las Villas-CubaUniversidad Central “Marta Abreu” de Las Villas-CubaUniversidad Central “Marta Abreu” de Las Villas-CubaVrije Universiteit Brusse-Bélgica 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 just once. Furthermore, the formulation of the mTSP seem more relevant for real-life applications, and also can be extended to a wide variety of Vehicle Routing Problems (VRPs) by incorporating some additional side constraints, such as the vehicle capacity and customer demands. Although the literature for the TSP and the VRP is definitely wide, the mTSP has not received the same amount of attention. In that sense, this paper proposes a new algorithm based on Ant Colony Optimization (ACO) for the mTSP, specifically Multi-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 competitive solution for the mTSP. The algorithm performance has been compared with one of the most efficient local search algorithms for mTSP, the Lin-Kernighan algorithm. Computational results confirm the competitiveness and efficiency of the strategy we propose. https://www.produccioncientificaluz.org/index.php/tecnica/article/view/6866ant colony optimization (aco)multiple traveling salesman problem (mtsp) |
| spellingShingle | Yasel José Costa Salas René Abreu Ledón Norge Isaías Coello Machado Ann Nowé Multi-type ant colony system for solving the multiple traveling salesman problem. Revista Técnica de la Facultad de Ingeniería ant colony optimization (aco) multiple traveling salesman problem (mtsp) |
| title | Multi-type ant colony system for solving the multiple traveling salesman problem. |
| title_full | Multi-type ant colony system for solving the multiple traveling salesman problem. |
| title_fullStr | Multi-type ant colony system for solving the multiple traveling salesman problem. |
| title_full_unstemmed | Multi-type ant colony system for solving the multiple traveling salesman problem. |
| title_short | Multi-type ant colony system for solving the multiple traveling salesman problem. |
| title_sort | multi type ant colony system for solving the multiple traveling salesman problem |
| topic | ant colony optimization (aco) multiple traveling salesman problem (mtsp) |
| url | https://www.produccioncientificaluz.org/index.php/tecnica/article/view/6866 |
| work_keys_str_mv | AT yaseljosecostasalas multitypeantcolonysystemforsolvingthemultipletravelingsalesmanproblem AT reneabreuledon multitypeantcolonysystemforsolvingthemultipletravelingsalesmanproblem AT norgeisaiascoellomachado multitypeantcolonysystemforsolvingthemultipletravelingsalesmanproblem AT annnowe multitypeantcolonysystemforsolvingthemultipletravelingsalesmanproblem |