Edge assembly combined with arc-based crossover for undirected traveling salesman with profits

In the traveling salesman problem with profit, the orienteering problem (OP) and prize-collecting traveling salesman problem (PCTSP) are two typical TSPs with profits. The PCTSP aims to minimize travel costs while satisfying a minimum profit threshold constraint. The OP objective is to maximize profit without exceeding a given maximum cost constraint. In current research, the conflicting objectives of OP and PCTSP pose challenges for designing a unified solution framework. To address this conflict, this study proposes a new genetic algorithm framework for unified solution of both OP and PCTSP. This framework innovatively combines the advantages of edge assembly crossover operators and arc crossover operators, introduces an adaptive offspring management strategy to generate high-quality offspring, and continuously optimizes the offspring solutions. Extensive experiments demonstrate that the proposed framework achieves comparable performance to existing state-of-the-art methods in terms of offspring solution quality and algorithmic efficiency.