An Approach to Solving the General Traveling Salesman Problem Based on Generating and Combining Cycles

The general traveling salesman problem (GTSP) is defined and studied in this paper. GTSP is to search a minimum-travel-time closed tour for salesman traversing a given part of nodes in a network at least once. GTSP is an extension of the standard TSP and belongs to the NP-hard problems. In comparison with the standard TSP, GTSP has more real-world applications including goods distribution, meter reading, design of tourist route, etc. To solve GTSP effectively, we propose an exact algorithm using the classic assignment problem as its key mechanism to generate and combine cycles. The new algorithm will at first transform GTSP into a standard TSP in a constructed network. Then a specified assignment problem with required cities as its agents and tasks at the same time will be constructed and solved. The result of the above assignment problem will be formed into some cycles that are viewed as new required elements. Based on the new required elements, a new assignment problem is constructed and solved. The above operation will continue until just one final closed tour is obtained covering all the required cities. Numerical examples were investigated with our new algorithm. By comparing with the commercial optimization software Lingo, genetic algorithm, and simulated annealing algorithm, we verified the validity of our new model of GTSP and demonstrated that our new algorithm is very effective to solve GTSPs with different scales