Inner Random Restart Genetic Algorithm to optimize delivery schedule
Yoshitaka Sakurai, Kouhei Takada, Natsuki Tsukamoto, Takashi Onoyama, Rainer Knauf, Setsuo Tsuruta · 2010
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, an Inner Random Restart Genetic Algorithm (Irr-GA) method is proposed. This method combines random restart and GA that has different types of simple heuristics such as 2-opt and NI (Nearest Insertion). 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.