|
Research Review of Close Enough Traveling Salesman Problem
SHI Fengyuan, OUYANG Dantong, ZHANG Liming
Journal of Jilin University Science Edition. 2025, 63 (1):
114-0123.
We consider a variant of the classic problem of the traveling salesman problem (TSP) in combinatorial optimization problem:
the close enough traveling salesman problem (CETSP). Firstly, we comprehensively introduce the history, solving methods, and algorithms for both TSP and CETSP, including exact algorithms (such as branch and bound method, linear programming) and heuristic algorithms (such as particle swarm optimization, greedy algorithms, etc.). The TSP requires finding the shortest path to visit each city once and return to the starting point given a list of cities and distances. CETSP is a generalization of TSP, allowing the visiting point for each target to be chosen from within a specified neighborhood, rather than exact location. It is suitable for practical applications that can tolerate errors, such as logistics distribution, intelligent transportation, and wireless sensor networks, etc. CETSP has higher flexibility and adaptability, which can significantly reduce computational resources and time consumption, particularly for large-scale problems with greater advantages. Secondly, we introduce the potential of CETSP in practical applications, especially in logistics, industrial manufacturing, traffic planning, information and communication, offering effective solutions for improving efficiency, reducing costs, and promoting intelligent decision-making. Finally, we have identified some future research directions for CETSP.
Related Articles |
Metrics
|