计算机科学 ›› 2024, Vol. 51 ›› Issue (11A): 231200072-8.doi: 10.11896/jsjkx.231200072
古婵, 付燕, 叶圣丽
GU Chan, FU Yan, YE Shengli
摘要： 研究旅游路线规划问题对推动城市旅游业的发展和提高游客体验至关重要,通常研究者将其抽象为着色旅行商问题进行探讨。然而,在求解大规模景点最优路线时,现有方法存在求解灵活性差和收敛速度慢等问题。因此,基于自动机探讨着色旅行商问题及其在旅游路线规划中的应用。首先,通过自动机建立景点路线图,利用分层自动机方法进行分散化讨论;其次,利用其结构性质灵活处理景点的选择并删除无效路径;最后,在简化后的模型上利用蚁群算法求解最短路线。实验选取了西安市内及周边景点作为样本数据,研究结果表明,与传统蚁群算法和模拟退火算法相比,所提算法降低了问题的复杂度,在有效范围内进行搜索,能够在20次迭代次数内收敛并求得最短路径,同时还可以根据游客个性化需求灵活规划合理的旅游路线。
中图分类号:
| [1]KE L J.Ant colony intelligence optimization method and its application[M].Beijing:Tsinghua University Press,2017. [2]WANG Z,SHEN Y,LI S,et al.A fine-grained fast parallel genetic algorithm based on a ternary optical computer for solving traveling salesman problem[J].The Journal of Supercomputing,2023,79(5):4760-4790. [3]ZHENG R,ZHANG Y,YANG K.A transfer learning-basedparticle swarm optimization algorithm for travelling salesman problem[J].Journal of Computational Design and Engineering,2022,9(3):933-948. [4]CHERABLI M,OURBIH-TARI M,BOUBALOU M.Refineddescriptive sampling simulated annealing algorithm for solving the traveling salesman problem[J].Monte Carlo Methods and Applications,2022,28(2):175-188. [5]LI S,LUO T,WANG L,et al.Tourism route optimization based on improved knowledge ant colony algorithm[J].Complex & Intelligent Systems,2022,8(5):3973-3988. [6]BORIS M,ELENA M.On the classical version of the branch and bound method[J].Computer Tools in Education,2022(2):41-58. [7]POIKONEN S,GOLDEN B,WASIL E A.A branch-and-bound approach to the traveling salesman problem with a drone[J].INFORMS Journal on Computing,2019,31(2):335-346. [8]LU B C,YANG J Y,WANG X.Urban and suburban tourism route planning based on tourist experience [J].Journal of Chongqing Jiaotong University(Natural Science Edition),2021,40(10):161-170. [9]KHAMSING N,CHINDAPRASERT K,PITAKASO R,et al.Modified ALNS algorithm for a processing application of family tourist route planning:A case study of Buriram in Thailand[J].Computation,2021,9(2):23. [10]FOROUZANDEH S,ROSTAMI M,BERAHMAND K.A hybrid method for recommendation systems based on tourism with an evolutionary algorithm and topsis model[J].Fuzzy Information and Engineering,2022,14(1):26-50. [11]CHEN C,ZHANG S,YU Q,et al.Personalized travel route recommendation algorithm based on improved genetic algorithm[J].Journal of Intelligent & Fuzzy Systems,2021,40(3):4407-4423. [12]LIANG S.Research on Route Planning of Red Tourist Attractions in Guangzhou Based on Ant Colony Algorithm[J].Automation and Machine Learning,2023,4(1):8-16. [13]LIANG S,JIAO T,DU W,et al.An improved ant colony optimization algorithm based on context for tourism route planning[J].Public Library of Science One,2021,16(9):e0257317. [14]LI S,LUO T,WANG L,et al.Tourism route optimization based on improved knowledge ant colony algorithm[J].Complex & Intelligent Systems,2022,8(5):3973-3988. [15]DORIGO M,MANIEZZO V,COLORNI A.Ant system:optimization by a colony of cooperating agents[J].IEEE Transactions on Systems,Man,and Cybernetics,Part B,1996,26(1):29-41. [16]RAMADGE P J G,WONHAM W M.The control of discreteevent systems[J].Proceedings of the IEEE,1989,77(1):81-98. [17]KHOUSSAINOV B,NERODE A.Automata theory and its applications[M].Springer Science & Business Media,2012. [18]REVELIOTIS S A,LAWLEY M A,FERREIRA P M.Polynomial-complexity deadlock avoidance policies for sequential resource allocation systems[J].IEEE transactions on automatic control,1997,42(10):1344-1357. [19]CHEN G,JIANG T H,WANG M,et al.Research and application of timed automata modeling for Internet of Things systems [J].Computer Applications and Software,2021,38(6):84-93. [20]TANG W,ZHAO J,GU C.Optimization of maze path planning solution algorithm based on automata [J].Journal of Nanjing University of Posts and Telecommunications(Natural Science Edition),2021,41(5):92-100. [21]DORIGO M,BIRATTARI M,STUTZLE T.Ant colony optimization[J].IEEE Computational Intelligence Magazine,2006,1(4):28-39. [22]WONHAM W M,RAMADGE P J.Modular supervisory control of discrete-event systems[J].Mathematics of Control,Signals and Systems,1988,1(1):13-3. [23]ZHENG D Z,ZHAO Q C.Discrete event dynamic systems[M].Beijing:Tsinghua University Press,2001. |
|
||
首页