Proposal and evaluation of 'selfish-gene with limited allowance' type GA for solving constraint TSP

摘要

For realizing large-scale distribution network simulation applicable to supply-chain management, it is required to solve hundreds of time constraint large-scale (100 cities) Traveling Salesman Problem (TSP) within interactive response time, with practicable optimality. Thus, a "selfish-gene with limited allowance" type GA is proposed. Here, each gene of an individual satisfies only its constraints selfishly, disregarding the constraints of other genes in the same individual. Further, to some extent, even individuals that violate constraints can survive over generations and are given the chance of improvement. Our experiment proves that this method gives expert-level solutions for time constraint large-scale TSPs within several seconds.