第十一届中国研究生电子设计竞赛技术论文论文题目：面向互联网+旅游的智能路线规划系统Intelligent route planning system for Tourism参赛单位：南京邮电大学队伍名称：蓝色梦想指导老师：徐小龙参赛队员：袁豪 谌运 杨春春完成时间：2016/5/20目录第一章 作品难点与创新 21、研究目的与意义 22、技术背景 23、技术难点 24、技术创新 4第二章 方案论证与设计 51、MTSP描述及建模 52、二阶段启发式算法（TSHA） 62.1聚类算法(基于改进K-means的景点聚类) 62.2 遗传算法 7第三章 算法测试与误差分析 121、 数据选取 122、 实验验证： 13第四章 软件设计与流程 161、基于Android平台的原型系统的构建 162、配置环境及发布Android SDK 173、开发指南 183.1地图类型 183.2定位图层 193.3 POI检索 203.4线路规划 223.5旅游路线规划的实现 24第五章 总结 28参考文献 29面向互联网+旅游的智能路线规划系统摘要：为了给游客提供更好的景点推送服务，本项目针对经典的旅行商问题（Traveling Salesman Problem，TSP）进行延伸研究了多旅行商问题（Multiple Traveling Salesman Problem，MTSP），MTSP具有更高的复杂性及更广泛的实际价值。
并根据实际的旅游情况在MTSP的基础上延伸研究了一种任务均分的MTSP，提出了一种二阶段启发式算法（Two Stage Heuristic Algorithm，TSHA）进行求解该算法阶段一通过加入容量限制的改进k-means算法根据景点位置和容量限制约束将景点分区聚类形成m个景点集合，阶段二采用遗传算法对m个景点集合进行路线规划特别对遗传算法的选择操作采用保留最佳结合轮盘赌策略，在保留最优个体的同时，保证了适应度较大的个体进入下一代为了验证所提出算法的可行性以及优越性，通过百度地图拾取南京市各景点的经纬度坐标作为实验数据在Matlab平台上进行实验验证，实验结果表明本文所提出的TSHA在求解均衡节点的MTSP和系统开销方面比基于遗传算法的路线规划具有更优秀的性能表现最后借助百度地图SDK构建原型系统，在系统中利用算法推荐旅游路线，其中系统中的功能还包括定位服务、图层展示、导航功能、路线规划、兴趣点搜索等功能关键词：多环旅行商问题、路径优化、k均值聚类、遗传算法Keywords—multiple-traveling salesman problem; NP-problem; route planning; heuristic Algorithm第一章 作品难点与创新1、研究目的与意义 随着科技的进步和社会的发展,旅游已成为人们的一种生活方式,是提高人们生活质量的重要活动，其中，旅游线路的规划是连接旅游客源地与旅游目的地的重要环节。
项目目的：设计合理的旅游线路既有利于旅游者有目的的选择、安排自己的旅游活动,避免“漫游”,又有利于发挥各旅游点的功能以及旅游者合理利用时间,还有利于旅游者有计划地支配旅游费用等等项目意义：通过为游客设计合理的旅游线路，使得大多数旅游者在感觉舒适和体力充沛的情况下,走较短的路程、花费较少费用和较短时间来游览更多的旅游景区，其中涉及的技术性和经验性都非常的强2、技术背景旅行商问题（Traveling Salesman Problem，TSP）作为NP-难题[1]之一，自从1950年被提出之后，迄今没有得到很好地解决TSP问题的目标是寻找一条距离最短的闭合回路，这条回路要求旅行商从一个城市出发，遍历每个城市有且只访问一次后，再返回到出发城市，确定一条最短路径该问题在图论的意义下就是所谓最小的Hamiltom圈的问题该问题目前被应用于网络路由布设、电气布线、交通诱导等方面，因其应用的广泛性和经济上的重大价值一直受到广大的学者的关注世界各地的学者们从经典的TSP问题出发，引申出了许多变形的旅行商问题，他们虽然有不同的目标函数或者不同的约束条件，但是都是为了找到最小的Hamilton回路，例如智能交通系统的旅行商问题、时间窗的旅行商问题、和最小比率旅行商问题等。
3、技术难点经典的TSP问题的目标是寻求单一旅行商由起点出发，遍历所有节点之后，再回到原点的最小路线成本但是一些实际应用问题却不能归纳为经典的TSP，如人员调度问题[2]、巡查问题[3]、物资配送[4][5]等问题，涉及到多个任务的分派与优化，问题演变为多旅行商问题（Multiple Traveling Salesman Problem，MTSP）MTSP比TSP更复杂，求解更为困难，所以目前MTSP的研究成果远比TSP少得多而今社会发展的需求变更以及经典TSP方面研究成果不断积累，使得MTSP研究逐渐成为了新的研究热点目前对于TSP问题的求解主要分为精确算法和近似算法精确算法主要包括动态规划法（Dynamic Programming）[8]、分支定界法（Branch and Bound）[9]、线性规划法（Integer Linear Programming）[10]等这些算法都是基于搜索的确定性算法，当节点规模很大时，算法的时间和空间复杂度会随着节点规模的增加呈指数倍增长，只能处理较小规模的TSP问题，求解的局限性比较大为了更好地解决大规模TSP问题，学者们受自然界生物群体活动或者自然现象的启发，在近几十年来开始关注群智能算法的研究，并且不断地提出新的启发式算法，它们凭着易实现及良好的并行性得到了广泛的应用。
比较经典的启发式算法包括：蚁群算法[11](Ant Colony Optimization,ACO)、粒子群算法[12]（Particle Swarm Optimization,PSO）、遗传算法（Genetic Algorithm）[13]等这些算法凭借着求解速度快，能在合理时间内找到较优解而得到学者的青睐但是它们也有各自的不足之处，蚁群算法的收敛速度较慢,粒子群算法容易陷入局部最优，遗传算法容易出现早熟的现象并且对于初始种群的依赖性较大所以对于启发式算法的改进以及和其他算法的融合一直都有学者在研究Pham D T et al.[14]提出了两种新的交叉算子的求解机制来增加了算法全局遍历性，这种方法对于经典的TSP问题有较好的求解结果，但是对于一些多约束的TSP问题，求解还是比较局限的Chen et al.[15]针对大规模的TSP问题，对数据集先进行划分，然后采用动态规划法对数据进行处理，得到一个较优的序列，然后采用遗传算法进行求解该方法对于大规模的TSP求解有较好的效果Atif A K et al. [16]采用分而治之的思想来求解TSP问题，对于TSP问题的划分，采用的是首先通过k-means聚类算法[17]对TSP，这是一种基于距离的聚类算法，以欧式距离做为适应度函数将所要求解的TSP问题分成若干个子集，然后分别采用贪心算法，对其进行求解，最后采用Lin- Kernighan Algorithm[18]将各子集求解的结果整合成最终解，该方法受子集划分大小的影响比较大。
目前对于TSP求解已经取得了较好的研究成果, 目前将MTSP问题转化为TSP求解是比较常用的策略，这样用于解决TSP的很多方法都可以用来解决MTSP将MTSP转化为TSP的基本策略最早是由Gorenstein提出[19]，其主要思想是对于一个有m个旅行商的mTSP，增加m-1个虚拟城市，用来对不同的旅行商访问的城市进行间隔，并且将这些虚拟城市之间的直达距离设为无穷大，以阻止旅行商访问的城市序列中出现不合理的排列Yuan et al .[20]提出了将染色体分为城市序列以及旅行商序列的染色体，通过两部分染色体的交叉减少了搜寻解的范围然而这种方法容易出现局部最优以及对于增加了染色体长度，增加了求解开销Kaliaperumal R et al. [21]提出将遗传算法的染色体分为城市序列以及旅行商序列，通过对两部分染色体进行交叉为每个旅行商安排路径，这种方法为每个旅行商安排访问节点的个数是不同的，所以不能满足访问任务均衡的MTSPOsaba E er al.[22]将拨号叫车服务抽象成非对称的MTSP，并且采用了改进的遗传算法进行求解，该算法根据适应度函数来自适应交叉概率生成下一代，逐代择优。
Alves R M F et al. [23]考虑了工作量平衡的MTSP，并且设计了两种GA，一个多目标的GA设法取得一个较好的解，一个单目标的GA通过适应度函数调节多目标的平衡性然而这种算法很难取得一个平衡，往往有一个目标占主导因素同样，目前大多数的研究主要局限于研究算法的性能以及算法的融合等，对于算法的实验验证也主要是通过数学计算或者仿真平台进行验证，很少有在真是的实际地图中，进行算法的实现，实际的地图中，由于地势更加复杂，操作起来更加困难4、技术创新MTSP是指给出n个节点的集合，m个旅行商从相同的起点出发，分别走一条旅行路线，使得每个节点有且只有一个旅行商走过，最后回到起点，且总行程最短可见TSP是MTSP的一个特例（m=1），MTSP是TSP的一般形式目前研究的MTSP主要考虑了总路程和最短，没有考虑每个旅行商任务均衡的问题本文研究了一种任务均分的MTSP，提出了一种二阶段启发式算法（Two Stage Heuristic Algorithm，TSHA），主要贡献包括 ：（1）对MTSP问题进行了平均任务分配，使得每个旅行商的工作量相当，更加符合实际情况均分访问顾客数的MTSP问题实际上是一个多目标规划问 题。
目标函数有两个: 一是 M 个旅行商所走的总路程最短 ; 二是M个旅行商的访问点数之差最小化 （2）对任务均分的MTSP问题，提出TSHA算法，分为两个阶段：阶段一采用加入容量限制的改进K-means算法进行任务平均分配，使得每个旅行商的工作量相当阶段二采用遗传算法进行路径的规划并且对遗传算法的选择操作采用精英策略结合轮盘赌策略，在保留了最优个体的同时，保证了适应度较大的个体进入下一代交叉操作选择前置交叉基因段的顺序交叉方法，即使两个父代相同，也能产生新的子代进行迭代优化，克服了局部最优和“早熟收敛”的缺点3）以旅游路线规划为典型应用背景，将南京市景点的经纬度作为实验数据在Matlab平台上将所提出的TSHA与GA性能比较，验证所提出的算法的性能优越性4）借助百度地图SDK构建路线规划的原型系统，首先通过GPS模块定位游客所在的位置，然后通过路线规划模块将游客所选择的景点进行分区聚类以及路线规划，为游客几天的行程安排一套游玩计划Android客户端核心功能主要包括：定位服务、图层展示、导航功能、路线规划、兴趣点搜索等功能第二章 方案论证与设计1、MTSP描述及建模结合旅游路线规划为典型背景研究了节点均衡的MTSP，给定n个旅游景点，受每天的游玩时间的限制，一天的时间不足以游玩所有的景点，这就要求对每天景点游玩的个数均衡化。
分m天将这n个景点全部游玩，即m个旅行商将n个景点规划出m条景点路线提供给游客一套完整的m天旅游行程，并且使其每天在景点之间路径上的开销尽可能小；由于游客在一个城市旅游通常不会因为每天游玩的景点不同而更换住宿酒店，因此m天旅游的每天起点和终点均为相同的酒店均衡节点的MTSP在图论下表示为一个完备图，V是顶点集，A是弧集其中，0是起点，1,2，…,n是待遍历的节点，为两点之间距离，为每天游玩的最大时间量， 为每个。