Bee Colony Optimization with local search for traveling salesman problem

Author

Wong, Li-Pei ; Low, Malcolm Yoke Hean ; Chong, Chin Soon

Author_Institution

Sch. of Comput. Eng., Nanyang Technol. Univ., Singapore

fYear

2008

fDate

13-16 July 2008

Firstpage

1019

Lastpage

1025

Abstract

Many real world industrial applications involve finding a Hamiltonian path with minimum cost. Some instances that belong to this category are transportation routing problem, scan chain optimization and drilling problem in integrated circuit testing and production. This paper presents a bee colony optimization (BCO) algorithm for traveling salesman problem (TSP). The BCO model is constructed algorithmically based on the collective intelligence shown in bee foraging behaviour. The model is integrated with 2-opt heuristic to further improve prior solutions generated by the BCO model. Experimental results comparing the proposed BCO model with existing approaches on a set of benchmark problems are presented.

Keywords

optimisation; travelling salesman problems; Hamiltonian path; bee colony optimization; collective intelligence; drilling problem; integrated circuit testing; local search; scan chain optimization; transportation routing problem; traveling salesman problem; Cities and towns; Computer aided manufacturing; Computer industry; Costs; Drives; Integrated circuit technology; Logistics; Optimized production technology; Transportation; Traveling salesman problems;

fLanguage

English

Publisher

ieee

Conference_Titel

Industrial Informatics, 2008. INDIN 2008. 6th IEEE International Conference on

Conference_Location

Daejeon

ISSN

1935-4576

Print_ISBN

978-1-4244-2170-1

Electronic_ISBN

1935-4576

Type

conf

DOI

10.1109/INDIN.2008.4618252

Filename

4618252