旅游线路优化问题

基于聚类和蚁群算法的旅游线路优化问题基于聚类和蚁群算法的旅游线路优化问题基于聚类和蚁群算法的旅游线路优化问题基于聚类和蚁群算法的旅游线路优化问题兰健，刘红星辽宁工程技术大学理学院，辽宁阜新（123000）E-mail：[e-mail]摘摘摘摘要：要：要：要：随着经济的发展，人们生活水平的提高，旅游的人越来越多，面对大量的游客，旅行社该如何制定旅游日程和规划旅游路线，来节省交通上和其他方面的开销，给旅行社带来最大利润。出于这个问题的考虑，本文将先采用聚类分析的方法对目标景区进行划分，以用来指定每日旅游计划，之后采用蚁群算法对每日的景点进行路径的优化，制定旅行线路。通过两种方法进行划分和优化，可以使旅行的行程和路线达到最优的效果，对实际应用中给出一定的方法参考。关键词：关键词：关键词：关键词：聚类分析；蚁群算法；最优路径；旅行计划中图分类号：中图分类号：中图分类号：中图分类号：U1161.1.1.1.引言假日经济的产生，促进了旅游业的发展，大大小小的旅行社面对众多的景区和景点，制定一个合理的旅游计划和旅游路线不仅能够在各种必要消费中节省很多的开支，还能够以合理的计划和线路吸引更多的游客。本文通过采用聚类分析法来科学的安排每日旅游计划，并通过蚁群算法来对每日旅游计划中的线路进行优化，以使旅游的计划和线路都达到最优的效果，同时根据一个实际问题对此方法进行验证和分析。2.2.2.2.聚类分析2.2.2.2.1111聚类分析介绍聚类分析指将物理或抽象对象的集合分组成为由类似的对象组成的多个类的分析过程。它是一种重要的人类行为，是数据挖掘领域中的一个重要分支，是一个无监督的学习过程，是一种人类认知世界的重要行为，是人们认识和探索事物之间联系的有效手段。它是一个将数据分类到不同的类或者簇这样的一个过程，所以同一个簇中的对象有很大的相似性，而不同簇间的对象有很大的相异性。聚类分析作为统计学中的一个研究分支已被广泛关注了很长时间，具有深厚的数学理论基础，其目标是在相似的基础上收集数据来分类。聚类分析的聚类源于很多领域，包括数学，计算机科学，统计学，生物学和经济学，并且已被应用到数据分析、图像处理、模式识别和市场研究等诸多领域中[5]。2.22.22.22.2聚类分析基本思想所研究的样品(网点)或指标(变量)之间存在程度不同的相似性(亲疏关系—以样品间距离衡量)。于是根据一批样品的多个观测指标,找出一些能够度量样品或指标之间相似程度的统计量,以这些统计量为划分类型的依据。把一些相似程度较大的样品(或指标)聚合为一类,把另外一些彼此之间相似程度较大的样品(或指标)又聚合为另一类,直到把所有的样品(或指标)聚合完毕。聚类分析是对统计样本进行定量分析的一种多元统计分析方法。包括谱系聚类、动态聚类、有序聚类等方法。系统聚类分析是一门多元统计分类法，对不同的要素划分类别往往反映不同目标的等级序列，能自然地、客观地得到一张完整的分类系统图。本文主要应用谱系聚类法对其数据进行聚类处理[6]。谱系聚类法谱系聚类是一种逐次合并类的方法，最后得到一个聚类的二叉树聚类图。其想法是，对于个观测，先计算其两两的距离得到一个距离矩阵，然后把离n得最近的两个观测合并为一类，于是我们现在只剩了个类（每个单独的未1−n合并的观测作为一个类）。计算这个类两两之间的距离，找到离得最近的1−n两个类将其合并，就只剩下了个类……直到剩下两个类，把它们合并为一2−n个类为止[4]。关于决定聚类个数是一个很复杂的问题。通常采用经验和直观判断结合的方法。根据问题的实际背景，在经验基础上确定类的个数k；此间，可借助直观:一是观察原始数据的散点图中点的聚集情况；二是在谱系聚类图中聚类指数跃迁较大之处进行截断。更严格的方法是借助统计量进行统计评价。在进行谱系聚类时，类与类之间的距离有不同的定义法。兰斯好威廉姆斯1967年给出了它们统一形式的递推公式：22222lplppqlpplrDDDDD−++=γβα其中对于不同的聚类方法有不同的取值见下。γβαα,,,qp表1谱系聚类方法统一公式参数表注：“*”表示样本点之间的距离必须采用欧氏距离。谱系聚类法的基本步骤如下：（1）原始数据的预处理。（2）计算距离（或相似系数）矩阵。（3）基于距离矩阵的类搜索与合并操作。（4）绘制谱系聚类图。（5）决定分类的个数及各类的成员。方法paqaβγ单键法1/21/20-1/2完全连锁法1/21/201/2中间距离法1/21/204/1≤≤−β0质心法*rpnn/rqnn/qpαα−0类平均法rpnn/rqnn/00可变类平均法rpnn/)1(β−rqnn/)1(β−10MCQ相似分析法2/)1(β−()2/1β−00Ward法*rlplnnnn++/rlqlnnnn++/)/(rllnnn+−0蚁群算法介绍蚁群算法(antcolonyoptimization,ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由MarcoDorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质.针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。是一种求解组合最优化问题的新型通用启发式方法，该方法具有正反馈、分布式计算和富于建设性的贪婪启发式搜索的特点[1]。3.23.23.23.2蚁群算法原理蚁群算法是受到对真实蚁群行为的研究的启发而提出的。生物学研究表明一群互相协作的蚂蚁能够找到食物源和巢穴之间的最短路径，而单只蚂蚁却不能。生物学家经过大量细致研究发现，蚂蚁个体之间是通过一种称之为信息素的物质进行信息传递的。蚂蚁在运动过程中，能够在它所经过的路径上留下该种物质，而且蚂蚁在运动过程中能够感知这种物质，一条路上的信息素踪迹越浓，其它蚂蚁将以越高的概率跟随此路径，从而该路径上的信息素踪迹会被加强，因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种间接的通信机制达到协同搜索食物最短路径的目的。蚂蚁觅食协作方式的本质是:①路径概率选择机制:信息素踪迹越浓的路径，被选中的概率越大;②信息素更新机制:路径越短，在上面的信息素踪迹浓度增长越快;③协同工作机制:蚂蚁之间通过信息素进行通信[1]。3.3.3.3.3333蚁群算法模型(1)状态转移概率TSP设是个城市的集合，是集合中的元素（城{}ncccC⋯,,21=n{}CcclLjiij⊂=,C市）两两连接的集合，是的距离即：()njidij,,2,1,⋯=ijl()()22jijiijyyxxd−+−=设表示时刻位于元素的蚂蚁数目，为时刻路径上的信息量，表示()tbii()tijτt()ji,nTSP模型，为蚂蚁群中蚂蚁的总数目，则；是时刻集合m()∑==niitbm1{}Cccjiij⊂=Γ,τt中元素（城市）两两连接上残留信息量的集合，在初始时刻各条路径上的信息量相等，C并设。()constij=0τ蚂蚁在运动过程中，根据各条路径上的信息量决定其转移方向，这里()mkk,,2,1⋯=用禁忌表来记录蚂蚁当前所走过的城市，集合随着进化过程()mktabuk,,2,1⋯=kktabu中国科技论文在线做动态调整。在搜索过程中，蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率。表示在时刻蚂蚁由元素（城市）转移到元素（城市）的状态转移概率。()tpkijtkij（1）()()[]()[]()[]()[]⎪⎪⎩⎪⎪⎨⎧∈⋅⋅=∑∈否则若0kallowedsisisijijkijallowedjtttttPkβαβαητητ式中：，表示蚂蚁下一步允许选择的城市，为从城市到城{}kktabuCallowed−=ijτi市的路径上的信息素；表示从到的期望程度，一般为从到的距离的倒数即jijηijij，称为启发函数；为蚂蚁从能够到达的集合；为信息启发式ijijd1=η()tallowedkkijα因子，表示轨迹的相对重要性，反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动是所起的作用，其值越大，则该蚂蚁越倾向于选择其他蚂蚁经过的路径，蚂蚁之间的协作性越强，为期望启发式因子，表示能见度的相对重要性，反映了蚂蚁在运动过程中启发信息在蚂β蚁选择路径中受重视程度，其值越大，则该状态转移概率越接近贪心规则；上式表示信息素较多且距离较短的路径被较大概率选中[2]。(2)信息素修改规则每只蚂蚁完成所有路径搜索后，都会在它爬过的路径上留下一定量的信息素，从而改变相应路径上的信息素，时刻的信息素修改公式表示为：nt+（2）()()()()ttntijijijττρτ∆+⋅−=+1（3）()()ttmkkijij∑=∆ττ式中，表示信息素挥发系数，则表示信息素残留因子，为了防止信息的无限积ρρ−1累，的取值范围为：；表示本次循环中路径上的信息增量，初始时刻ρ[)10，∈ρijτ∆()ji,，表示第k只蚂蚁在本次循环中留在路径上的信息量。()00=∆ijτ()tkijτ∆的表达形式可以不同，要根据具体问题而定，M.Dorigo给出了三种不同模型()tkijτ∆Ant-CycleSystem，Ant-QuantitySystem，Ant-DensitySystem.在Ant-CycleSystem模型中：（4）()()⎪⎪⎩⎪⎪⎨⎧=∆否则在本次循环中经过路径如果蚂蚁0,jijLQtkkijτ中国科技论文在线其中信息素强度是一个常数，是第个蚂蚁所找到的路径长度。QkLk在Ant-QuantitySystem模型中：（5）()()⎪⎪⎩⎪⎪⎨⎧=∆否则过路径只蚂蚁在本次循环中经如果第0,jikdQtijkijτ在Ant-DensitySystem模型中：（6）()⎪⎩⎪⎨⎧=∆否则过路径只蚂蚁在本次循环中经如果第0,jikQkijτ它们的区别在于：后两种模型利用的是局部信息，而前者利用的是全局信息，性能较好，因而通常采用它作为基本模型。本文将采用Ant-CycleSystem模型作为信息素修改的原则[3]。4.4.4.4.模型建立与求解4.14.14.14.1问题提出随着社会经济的发展和人们生活水平的提高，一个大众化的休闲时代已经来临，旅游产业变的越来越受欢迎。面对游客的增多，旅行社该如何制定旅游的日程和规划旅游路线，来节省交通上和其他方面的开销，给自己带来最大利润呢？考虑到这些问题，本文将采用聚类分析对景点进行区域的划分，制定每日的行程。在利用蚁群算法对各个景点进行路线优化，制定旅游路线。4.24.24.24.2数据来源本文以北京市的21个景点为例，如图1。图1旅游景点分布中国科技论文在线为了便于研究，对地图中的景点进行了简化，并对其进行了编号，依据地图所示，建立直角坐标系，测量出这21个点的坐标，如图2。图2旅游景点分布坐标图通过测量后得到各个景区的坐标数据，如下表所示：表2旅游景点分布坐标编号地点XY1故宫（住处）15.28.952颐和园1012.553国家体育场15.212.134八大处公园7.510.85北京动物园13.19.86北京游乐园16.27.17龙王庙4.711.28天山门森林公园1.87.59地坛公园15.710.610郁金香温泉花园度假村20.812.811千灵山风景区4.16.212圆明园11.813.113奥林匹克公园14.913.3514太平洋海底世界11.858.95中国科技论文