A simple optimization method based on Backtrack and GA for delivery schedule

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 (max. 1500-2000) cities Traveling Salesman Problems (TSP) within interactive response time (around 3 seconds) with expert-level accuracy (below 3% level of error rate). Moreover, as for the algorithms, understandability and flexibility are necessary because field experts and field engineers can understand and adjust it to satisfy the field conditions. To meet these requirements, a Backtrack and Restart Genetic Algorithm (Br-GA) is proposed. This method combines Backtracking and GA having simple heuristics such as 2-opt and NI (Nearest Insertion) so that, in case of stagflation, GA can restarts with the state of populations going back to the state in the generation before stagflation. Including these heuristics, field experts and field engineers can easily understand the way and use it. Using the tool applying their method, they can easily create/modify the solutions or conditions interactively depending on their field needs. Experimental results proved that the method meets the above-mentioned delivery scheduling requirements more than other methods from the viewpoint of optimality as well as simplicity.