TSP收益最大化

Search for orienteering problem or prize-collecting TSP.

You can adapt the algorithm of this paper TSPTW. It is almost the same problem. Check these other papers cited in that site:

There are a few problems in this category. They are variants of the Travelling Salesman Problem in which you don't need to visit all customers, but can choose which ones to visit. They fall under the general name of Travelling Salesman Problems with Profits.

The main variants are:

• The Orienteering Problem (OP) in which you want to maximise the profit collected at visited customers, under an upper bound on the trip length.
• The Prize-collecting TSP in which you want to minimise the trip length, under a lower bound on the amount of profit collected.
• The Profitable Tour Problem in which instead of considering travel time, you consider travel costs. In this case you can express profits collected and travel costs with the same unit of measure (say, €). The objective is to maximise the revenue (= profit collected, minus travel costs).

Most of these problems also appear in the literature with variants (multi-vehicle, time windows, etc.) which are common for other "classic" routing problems. For example, the multi-vehicle OP is called the Team Orienteering Problem (TOP). Adding time windows gives the OPTW and TOPTW. Adding vehicle capacities gives the Capacitated TOP. Some stochastic versions include the TSP with Profits and Stochastic Customers, the OP with stochastic travel times and the OP with stochastic profits.

As per the solution methods for the Orienteering Problem (which seems the one most suited for your question), as far as I know the state-of-the-art exact algorithm is still the one by Fischetti, Salazar-Gonzalez, and Toth. In the last couple of years, new heuristics have improved on previously best-known results: a genetic algorithm and an ALNS.