A Case Based Approach for an Intelligent Route Optimization Technology

Abstract

This paper introduces 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 a majority of real world problems are very often similar to previous ones at least for route scheduling. Thus, a solution can be derived from former solutions as follows: (1) selecting a most similar TSP from a library (CB: Case Base) of former TSP solutions, (2) removing the locations that are not including in the newly given problem or TSP and (3) adding the new locations by Nearest Insertion (NI) and possibly adjusting by NI incorporated GA. This way of creating solutions by Case Based Reasoning (CBR) avoids the computational costs to create new solutions from scratch. The evaluation of this method revealed remarkable results. Though even the world fastest most optimal approximate TSP solving method LKH needed more than 3 seconds or the worst error rate exceeded 3 seconds, the worst error rate of the proposed method is less than 1 % within 3 seconds. This is about 10-100 times better than that of our former approach BR-GA (Backtrack and Restart type GA).