DocumentCode :
1850198
Title :
Finding the Shortest Hamiltonian Circuit of Selected Places in Penang Using a Generic Bee Colony Optimization Framework
Author :
Wong, Li-Pei ; Low, Malcom Yoke Hean ; Chong, Chin Soon
Author_Institution :
Sch. of Comput. Sci., Univ. Sains Malaysia, Minden, Malaysia
fYear :
2011
fDate :
27-29 Sept. 2011
Firstpage :
51
Lastpage :
57
Abstract :
Identifying the shortest Hamiltonian circuit is a task which appears in various types of industrial and logistics applications. It is a NP-hard problem [1]. This paper intends to find the shortest Hamiltonian circuit of the selected 68 towns/cities in Penang state, Malaysia using the generic Bee Colony Optimization (BCO) framework [2]. The proposed BCO framework realizes computationally the foraging process and waggle dance performed by bees and it is enriched with elitism, local optimization and adaptive pruning. A modification has been applied to the framework whereby a past solutions reinforcement policy is integrated. Also, the local optimization method is enhanced with the utilization of a Tabu list. The results from this study serve as an significant input to the preparation of logistics plan when a natural disaster occurs. Aiding resources can be delivered to affected areas, one after another, in a more appropriate and systematic manner and thus leads to cost and time saving. The results show that proposed BCO framework is able to produce a circuit (based on great-circle distance) with length of 263.332016km within 1.32s. The performance of the proposed BCO framework is comparable to the Genetic Algorithm and Lin-Ker heuristic.
Keywords :
disasters; genetic algorithms; search problems; Lin-Ker heuristic; Malaysia; NP-hard problem; Penang state; adaptive pruning; foraging process; generic bee colony optimization framework; industrial applications; local optimization method; logistics applications; natural disaster; shortest Hamiltonian circuit; Approximation algorithms; Biological cells; Cities and towns; Encoding; Genetic algorithms; Optimization; Symmetric matrices; Bee colony optimization; Hamiltonian circuit; Penang; generic framework; metaheuristic;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Bio-Inspired Computing: Theories and Applications (BIC-TA), 2011 Sixth International Conference on
Conference_Location :
Penang
Print_ISBN :
978-1-4577-1092-6
Type :
conf
DOI :
10.1109/BIC-TA.2011.5
Filename :
6046872
Link To Document :
بازگشت