A Multi-world Intelligent Genetic Algorithm to Interactively Optimize Large-scale TSP

Author

Sakurai, Yoshitaka ; Onoyama, Takashi ; Kubota, Sen ; Nakamura, Yoshihiro ; Tsuruta, Setsuo

Author_Institution

Sch. of Inf. Environ., Tokyo Denki Univ.

fYear

2006

fDate

16-18 Sept. 2006

Firstpage

248

Lastpage

255

Abstract

To optimize large-scale distribution networks, solving about 1000 middle scale (around 40 cities) TSPs (traveling salesman problems) within an interactive length of time (max. 30 seconds) is required. Yet, expert-level (less than 3% of errors) accuracy is necessary. To realize the above requirements, a multi-world intelligent GA method was developed. This method combines a high-speed GA with an intelligent GA holding problem-oriented knowledge that is effective for some special location patterns. If conventional methods were applied, solutions for more than 20 out of 20,000 cases were below expert-level accuracy. However, the developed method could solve all of 20,000 cases at expert-level

Keywords

genetic algorithms; travelling salesman problems; large-scale TSP; large-scale distribution network; multiworld intelligent genetic algorithm; problem-oriented knowledge; traveling salesman problem; Cities and towns; Costs; Delay; Genetic algorithms; Humans; Intelligent networks; Large-scale systems; Production facilities; Software engineering; Traveling salesman problems;

fLanguage

English

Publisher

ieee

Conference_Titel

Information Reuse and Integration, 2006 IEEE International Conference on

Conference_Location

Waikoloa Village, HI

Print_ISBN

0-7803-9788-6

Type

conf

DOI

10.1109/IRI.2006.252421

Filename

4018498