Research On Time Optimal TSP Based On Hybrid PSO-GA

In order to provide a better recommended-path service for tourists, this paper proposed an outreach of the classical TSP, called Time Optimization TSP (TOTSP). It is aimed at pushing the recommended shortest time path to save tourists’ traveling time. A hybrid algorithm——article Swarm Optimization-Genetic Algorithm (PSO-GA) solves the proposed problem and regards traveling time as its objective function in simulations. The traveling time contains three parts:tourists’ walking time between scenic spots, tourists’ wait-in-queue time of every scenic spot and tourists’ visiting time at each scenic spot. Simulations have compared results of PSO-GA, GA and ACO of finding the shortest travel time and consuming of the CPU execution time. The results reveal PSO-GA has an outperformance on dealing with the proposed TOTSP.The TOTSP has studied in this research. The path for TOTSP is called Time Optimal Path (TOP), the path for TSP is called Length Optimal Path (LOP). The main works are as follows:(1) TOTSP is proposed as a kind of expansion form of TSP, and its concept and mathematical model has been introduced. Besides touists’ walking time, visiting time and waitting time has been considered into the model;(2) The simulating results of PSO-GA are in comparison with the results of GA and ACO. The results reveal that PSO-GA has better performance on solving TOTSP;(3) Study the PSO-GA performance under different density of tourists on TOTSP, and compare the simulating results to GA and ACO. The results indicate that the TOP path of TOTSP can reach shorter traveling time than LOP of TSP under different density of tourists, thus save traveling time for tourists.