Finding the Shortest Hamiltonian Circuit of Selected Places in Penang Using a Generic Bee Colony Optimization Framework

摘要

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.