Intelligent Route Optimization Technology by Case Based GA

A delivery route optimization system greatly improves the real time delivery efficiency. To realize such an optimization, its distribution network requires solving several tens to hundreds (maximum 2 thousands or so) cities Traveling Salesman Problems (TSP) within interactive response time (around 3 seconds) with expert-level accuracy (below 3% level of error rate). To meet these requirements, a Case Based Genetic Algorithm (CBGA) is proposed. 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, (3) adding the missing locations of the current TSP by mutation, namely Nearest Insertion (NI), and (4) further optimizing the solution by another GA. This way of creating solutions by Case Based Reasoning (CBR) avoids the computational costs to create new solutions from scratch.