Hybrid genetic algorithm for undirected traveling salesman problems with profits

The orienteering problem (OP) and prize-collecting traveling salesman problem (PCTSP) are two typical TSPs with profits, in which each vertex has a profit and the goal is to visit several vertices to optimize the collected profit and travel costs. The OP aims to collect the maximum profit without exceeding the given travel cost. The PCTSP seeks to minimize the travel costs while ensuring a minimum profit threshold. This study introduces a hybrid genetic algorithm that addresses both the OP and PCTSP under a unified framework. The algorithm combines an extended edge-assembly crossover operator to produce promising offspring solutions, and an effective local search to ameliorate each offspring solution. The algorithm is further enforced by diversification-oriented mutation and population-diversity management. Extensive experiments demonstrate that the method competes favorably with the best existing methods in terms of both the solution quality and computational efficiency. Additional experiments provide insights into the roles of the key components of the proposed method.

Automated summary

This study presents a hybrid genetic algorithm that addresses both the orienteering problem (OP) and prize-collecting traveling salesman problem (PCTSP). The algorithm combines an extended edge-assembly crossover operator to generate promising offspring solutions, and an effective local search to improve each offspring solution. Additionally, the algorithm is enhanced by diversification-oriented mutation and population-diversity management. Extensive experiments show that the method is competitively on par with the best existing methods in terms of solution quality and computational efficiency, with additional insights provided on the roles of the key components of the proposed method.