Knowledge Acquisition issues for intelligent route optimization by evolutionary computation
Masaki Suzuki, Setsuo Tsuruta, Rainer Knauf, Yoshitaka Sakurai · 2014
The paper introduces a Knowledge Acquisition and Maintenance concept for a Case Based Approximation method to solve large scale Traveling Salesman Problems in a short time (around 3 seconds) with an error rate below 3 %. This method is based on the insight, that most solutions are very similar to solutions that have been created before. Thus, in many cases a solution can be derived from former solutions by (1) selecting a most similar TSP from a library of former TSP solutions, (2) removing the locations that are not part of the current TSP and (3) adding the missing locations of the current TSP by mutation, namely Nearest Insertion (NI). This way of creating solutions by Case Based Reasoning (CBR) avoids the computational costs to create new solutions from scratch.