Takashi Onoyama, Sen Kubota, and Kazuko Oyanagi, Hitachi Software Engineering Co., Ltd., Japan; Setsuo Tsuruta, Hitachi, Ltd., Japan
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%) accuracy necessary. To realize the above requirements, a knowledge-embedded multi-stage GA method was developed. This method combines a high-speed GA with a knowledge-embedded GA having problem-oriented knowledge effective for some special location patterns. When conventional methods were applied, solutions for more than 20 cases out of 20000 cases were below expert-level accuracy. But the developed method could solve all of 20000 cases at expert-level.