A Branch-and-Bound-Based Crossover Operator for the Traveling Salesman Problem

摘要: In this article, the new crossover operator BBX for Evolutionary Algorithms (EAs) traveling salesman problems (TSPs) is introduced. It uses branch-and-bound to find optimal combination of (directed) edges present in parent solutions. The offspring solutions created are at least as good their parents and only composed parental building blocks. closer ideal concept EAs than existing operators. This article provides most extensive study on operators TSP, comparing ten other 110 instances TSPLib benchmark set with four different population sizes. BBX, its better ability reuse combine blocks, surprisingly does not generally outperform However, it performs well certain scenarios. Besides presenting a novel approach significantly extends refines body knowledge field conclusions comparison results.