Knowledge-embedded multi-stage genetic algorithm for interactively optimizing a large-scale distribution network

摘要

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 is 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.