智能优化算法在暑假旅游路线安排中的应用

周福来

摘 要：为解决暑假旅行人员以成本最小化为目标的最佳旅行路线选择难题，基于路径优化理论（VRP）及粒子群算法，设计了以暑假旅游路线最短为优化目标的数学模型，采用计算机编程技术，设计了求解该优化模型的粒子群算法，并选择案例对模型及算法进行了验证。案例应用结果表明，该模型和算法能够有效解决最佳旅游路线选择难题，正确率达98%。基于VRP理论及粒子群算法的最短路选择模型不仅能够快速求解出最优路径方案，还能够有效降低人工经验选择最短路径中存在的误差。

关键词：智能优化算法;旅游路径规划;粒子群算法;数学建模

DOI：10. 11907/rjdk. 191498

中图分类号：TP306

文献标识码：A文章编号：1672-7800（2019）006-0021-04

Abstract： In order to solve the problem of choosing the best travel route for the travelers during the summer vacation with the goal of minimizing the cost， based on the theory of path optimization （VRP） and particle swarm optimization （PSO）， this paper studies the application of intelligent optimization algorithm in summer vacation tourism route arrangement. Firstly， a mathematical model is designed to optimize the shortest route of summer vacation tourism. Secondly， a PSO algorithm is designed to solve the optimization model by using computer programming technology. Finally， a case is selected to illustrate the model designed in this paper. The algorithm is validated. The application results show that the model and the algorithm can effectively solve the problem of travelers choosing the best tour route in summer vacation， and the correct rate is 98%. The shortest path selection model based on VRP theory and particle swarm optimization can not only solve the optimal path scheme quickly， but also effectively reduce the error in manual selection of shortest path.

Key Words： intelligent optimization algorithm; tourism path planning; particle swarm optimization; mathematical modeling

0 引言

随着人们生活水平的提高和交通设施的完善，越来越多的人开始利用节假日去往不同的地方旅游。“食、住、行、游、购、娱”是旅游过程中的六要素[1]，合理安排旅游过程中的“行”，采用合适的智能优化算法解决旅行路线有效安排问题尤为重要。陈荣虎等[2]为了提高粗粒度并行遗传算法性能，缩短对立体仓库路径优化问题的求解时间，将一种单程序多数据流（简称SPMD）并行结构运用到粗粒度并行遗传算法中，并对算法进行改进;杨乐等[3]采用改进的蚁群算法解决了迷宫路径选择问题;黎泽等[4]考虑“旅行船接触最小”因素，利用0-1规划方法建立多线通航、船只最多模型并进行了求解，给出了最佳船只行程安排;鄢栋等[5]针对动态车辆路径中出现新的客户请求时的车辆路径优化问题，提出了紧急动态客户和数据包的概念，解决了车辆路径优化问题;陈婧怡等[6]采用多温区冷藏车，构建考虑运输成本、货损成本、制冷成本的路径优化模型，利用遗传算法对算例进行求解。Manuela Graf等[7]剖析了一个包括灾难模拟中独立飞行无人机或驾驶车辆的救援路径规划特殊的动态车辆路径问题，设计算法并进行了求解;Changxi Ma等[8]以最小传输时间为目标，基于Bertsimas的鲁棒离散优化理论，建立了具有可调鲁棒性的电动汽車配电线路鲁棒优化模型;Lai Mingyong等[9]提出了考虑不确定性的车辆初始路径优化模型，考虑了车辆通行能力、客户时间窗、最大行驶距离以及道路通行能力。常朝稳等[10]对带时间约束的旅行社划分旅游景点并制定线路，同时对该路线配送车辆建模问题进行了研究;邹腊英等[11]研究了基于TPS的旅行者旅游路线安排问题;Hungerl Nder等[12]提出了一种自适应邻域搜索启发式算法，用于根据给定的交付时间表实时确定插入新客户订单的可行时段，解决了路径优化问题;Lu Han等[13]根据电子商务的特点，设计了一个求解路径优化的模型和算法;姚卫粉等[14]针对遗传算法优化车辆路径问题易陷入局部最优解以及收敛速度慢等问题，引入基于动态小生境的协同进化模型;Jing Wen等[15]建立了一个考虑二氧化碳排放、客户时间窗和拥挤的自提储物柜车辆路径优化模型;Guezouli等[16]研究了具有时间窗的多车辆段机群规模混合车辆路径问题;曹阳等[17]分析了国内外相关领域的研究现状，梳理了传统旅游线路的概念定义与旅游线路设计的方法;李进立等[18]针对旅行者的出行问题，通过分析时间、路线及旅行费用等数据，建立模型，解决旅行者出行前如何安排行程的问题;钟仪华等[19]用赋权图和近邻聚类的思想构建分块网络加权图，建立考虑旅游时间、行车时间和游览时间的改进旅行商优化模型;贾振亮等[20]采用混合整数规划方法对带时间约束的旅行社配送车辆调度问题进行了建模研究;Rogerson[21]研究了陆游路线与当地经济发展的关系。

綜上可知，当前国内外学者针对旅游中的线路选择问题进行了多方位的探讨，在一定程度上可以解决不同的商旅问题，但未能解决暑假期间以最低出行成本为首选因素的旅游路线安排问题。鉴于此，本文利用路径优化理论（VRP）及粒子群算法进行旅行路径优化求解，以节约旅行成本，提升旅游体验。

1 问题描述

某旅游爱好者计划在暑假旅游，但由于预算有限，希望以最小旅游成本完成整个旅游过程，因此，有必要提前对暑假的旅游路线进行安排。在选择交通工具时，统一选择乘坐火车出行，而火车的售价基本上与火车行驶的路程呈正比例关系，因此，求解最小化路费问题可以转化为求解最短路程问题。现假设火车每行驶1km的成本为1元，求如何合理安排出行线路可以使得总路费最小。

该问题属于典型的路径优化问题，路径优化问题一直被认为是学术界的N-P难题，本文将针对该问题应用建模理论及粒子群算法进行求解。

2 目标函数

3.3 交叉操作

交叉操作的目的是实现种群进化，本文采用两点交叉法实现粒子群的交叉进化，即在根据适应度函数选择新种群过程中，随机选择两个个体进行交叉操作。进行交叉操作时，先随机选择两个交叉位置点，两个个体的基因片段在此交叉点进行交叉操作产生新的个体，再对个体中的标号进行调整，删除重复编号，同时保证所有地点编号均被保留在个体的基因片段之内。本文设计的交叉操作如图1所示。

3.4 变异操作

与交叉操作类似，本文采用两点变异法实现粒子群的变异进化，与交叉操作不同的是，变异操作是在单个个体上的两个不同点上进行基因的互换操作，进而实现整个种群的进化。因此，在进行变异操作时，不需要对变异后的种群个体进行标号的重复性检查。其中，本文设计的变异操作如图2所示。

4 案例分析

某一旅行爱好者在暑假期间计划到国内19个城市旅行，如何选择最优旅行方案困惑了该旅行者。在该问题中，算上家乡所在地则一共有20个地点，对这20个地点进行编号，对应的坐标值如表1所示，其中编号1表示家乡所在地，其坐标值为（15，27）。

设定最大迭代次数为200，种群规模设置为1 000，借助Matlab软件，采用本文设计的方法求解出的最短旅行路径为：4 19 11 2 1 8 17 14 20 12 5 18 10 3 6 9 15 16 7 13，则暑假期间的旅行安排顺序应为：1 8 17 14 20 12 5 18 10 3 6 9 15 16 7 13 4 19 11 2 1，按照此路径安排旅行行程花费的路费最少，此时最短旅行距离为831km（即831元）。本文优化的最佳旅行路径如图4所示。

采用Matlab软件求解上述问题时，得到的算法进化迭代收敛情况如图5所示。

由图5可知，本文设计的算法在求解该问题时约在第56步时收敛到最优目标函数值，即为831，这表明本文设计的算法能够有效地解决暑假旅行安排问题。此外，图5也说明本文设计的算法能够快速寻找到最佳旅行方案，在求解该问题时具有一定的优越性。

5 结语

本文利用粒子群算法解决了旅游过程中成本最小化的最佳路线选择问题。首先，对旅游路线问题进行描述，将最小化的成本问题转换成最短的行驶路程问题;其次，建立求解该问题的数学模型，设计并求解该优化模型的粒子群算法，并从个体编码、适应度函数值设计、交叉操作、变异操作4个方面进行详细介绍;最后，选择案例，对本文设计的模型及算法进行验证。研究结果表明，本文设计的模型及算法能够有效解决旅行人员以最低成本为目标的旅游路线选择难题。

参考文献：

[1] 陈文娟. 浅议旅游线路设计中旅游景点的选择和安排[J]. 环球市场， 2015（3）：101.

[2] 陈荣虎，何运杰. 基于SPMD的粗粒度并行遗传算法在立体仓库路径优化中的应用[J]. 软件导刊，2018，17（12）：108-112.

[3] 杨乐，向凤红，毛剑琳. 基于改进蚁群算法快速求解迷宫路径问题研究[J]. 软件导刊，2018，17（7）：108-110，115.

[4] 黎泽，黄俊毅，刘冠弟，等. 基于数学建模方法的旅游船只行程安排探究[J].  科技与生活， 2012（8）：198-199.

[5] 鄢栋，陈家琪. ICP策略下带软时间窗的动态车辆路径优化问题研究[J]. 软件导刊，2018，17（3）：172-175.

[6] 陈婧怡，邱荣祖. 基于ArcGIS的多温区冷藏车辆路径优化[J]. 上海海事大学学报，2019，40（1）：8-13.

[7] GRAF M，POY M，BISCHOF S， et al. Rescue path optimization using ant colony systems[C]. 2017 IEEE Symposium Series on Computational Intelligence， 2017.

[8] MA C，HAO W，HE R，et al. Distribution path robust optimization of electric vehicle with multiple distribution centers[J]. PLoS ONE， 2018， 13（3）：e0193789.

[9] LAI M，YANG H，YANG S，et al. Cyber-physical logistics system-based vehicle routing optimization[J]. Journal of Industrial and Management Optimization，2013，10（3）：701-715.

[10] 常朝稳，李黎. 基于约束规划的旅游多车辆行程路线研究[J]. 计算机应用，2006，26（s2）：202-204.

[11] 邹腊英. 基于TSP问题的旅游路线安排[J]. 兰州文理学院学报：自然科学版，2015，29（5）.

[12] HUNGERL NDER P，RENDL A，TRUDEN C. On the slot optimization problem in on-line vehicle routing[J]. Transportation Research Procedia， 2017， 27：492-499.

[13] HAN L，HOU H，YANG J，et al. E-commerce distribution vehicle routing optimization research based on genetic algorithm[C]. 2016 International Conference on Logistics， Informatics and Service Sciences （LISS）， 2016.

[14] 姚衛粉，许峰. 求解车辆路径问题的协同进化遗传算法[J]. 软件导刊，2015，14（1）：57-59.

[15] WEN J，LI Y. Vehicle routing optimization of urban distribution with self-pick-up lockers[C]. International Conference on Logistics， 2017.

[16] GUEZOULI L，ABDELHAMID S. A multi-objective optimization of multi-depot fleet size and mix vehicle routing problem with time window[C]. International Conference on Systems & Control， 2017.

[17] 曹阳. 城市旅游规划行程链的模型构建及其应用研究[D]. 南京：南京师范大学，2014.

[18] 李进立，韦程东，刘广会，等. 旅游路线规划问题[J]. 广西师范学院学报：自然科学版，2016（1）：30-38.

[19] 钟仪华，罗仕明. 分块分层优化的旅游路线规划问题研究[J]. 运筹与管理，2017（9）：66-71.

[20] 贾振亮，司志刚. 基于混合整数规划的旅游车辆调度设计和仿真[J]. 计算机仿真，2007，24（8）：233-235.

[21] ROGERSON C M. Tourism routes as vehicles for local economic development in South Africa： the example of the magaliesberg meander[J].  Urban Forum，2007，18（2）：49-68.

（责任编辑：孙 娟）