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.
Published Date: May 2001
Registration: ISBN 978-1-57735-133-7
Copyright: Published by The AAAI Press, Menlo Park, California.