Name
Title | ||
|---|---|---|
Solving Asymmetric Traveling Salesman Problems using a generic Bee Colony Optimization framework with insertion local search |
Abstract | ||
|---|---|---|
The Asymmetric Traveling Salesman Problem (ATSP) is one of the Combinatorial Optimization Problems that has been intensively studied in computer science and operations research. Solving ATSP is NP-hard and it is harder if the problem is with large scale data. This paper intends to address the ATSP using an hybrid approach which integrates the generic Bee Colony Optimization (BCO) framework and an insertion-based local search procedure. The generic BCO framework computationally realizes the bee foraging behaviour in a typical bee colony where bees travel across different locations to discover new food sources and perform waggle dances to recruit more bees towards newly discovered food sources. Besides the bee foraging behaviour, the generic BCO framework is enriched with an initialization engine, a fragmented solution construction mechanism, a local search and a pruning strategy. When the proposed algorithm is tested on a set of 27 ATSP benchmark problem instances, 37% of the benchmark instances are constantly solved to optimum. 89% of the problem instances are optimally solved for at least once. On average, the proposed BCO algorithm is able to obtain 0.140% deviation from known optimum for all the 27 instances. In terms of the average computational time, the proposed algorithm requires 48.955s (<; 1 minutes) to obtain the best tour length for each instance. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/ISDA.2013.6920757 | ISDA |
Keywords | Field | DocType |
np-hard,pruning strategy,waggle dances,travelling salesman problems,generic bee colony optimization framework,hybrid approach,combinatorial optimization problems,fragmented solution construction mechanism,bee foraging behaviour,insertion-based local search procedure,search problems,computational complexity,operations research,initialization engine,metaheuristic,atsp benchmark problem,food source discovery,local search,computer science,insertion local search,generic framework,insertion,asymmetric traveling salesman problems | Mathematical optimization,Combinatorial optimization problem,Computer science,Forage (honey bee),Travelling salesman problem,Artificial intelligence,Initialization,Local search (optimization),Machine learning,Metaheuristic | Conference |
ISSN | ISBN | Citations |
2164-7143 | 978-1-4799-3515-4 | 3 |
PageRank | References | Authors |
0.39 | 13 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Li-Pei Wong | 1 | 109 | 8.32 |
| Ahamad Tajudin Khader | 2 | 683 | 40.71 |
| Mohammed Azmi Al-Betar | 3 | 620 | 43.69 |
| Tien-Ping Tan | 4 | 3 | 0.73 |