景点缆车设计问题.docx

《景点缆车设计问题.docx》由会员分享，可在线阅读，更多相关《景点缆车设计问题.docx（20页珍藏版）》请在三一办公上搜索。

1、景点缆车设计问题摘要本文解决了游客周游各景点所乘电缆的最短路线问题，制定了既满足游客短时间内 游览更多景点的愿望，又达到了景区缆车制造最经济的条件。对于问题（1）考虑到问题二的解决优化程度，需要建立合适的坐标系，在此首先 使用的是MATLAB中的gnput函数，以所给的整张图片为坐标定义域，把它们平均分为 786份和564份，后来由于这种原点在图片左上角的坐标系并不符合我们日常使用的坐 标系，因此，考虑到坐标的直观性和计算的方便，把坐标转换为原点在左下方，然后分 别给出各景点具体的坐标值。对于问题（2）考虑到从47个景点中制定最短的旅游路线，这是一个对称的旅行商 问题（TSP），如果采用动态规

2、划进行求解，空间复杂性及时间复杂性都十分庞大。因此， 为解决此问题，本文采用人工蚁群算法进行求解，即利用MATLAB进行计算机求解，得 出全景区47个景点点到点最短路径的最优解，此方法节约计算资源，具有良好的可扩 展性和健壮性。最后对本模型进行了可行性论证，并得出了景区的缆车票价定价区间。部分结果：总路线长度：34.722km 初次总投入：347220万元最低缆车票价174.65元乘缆车减少n天的条件下的定价区间为p=174.65,（158+225*n）关键词：TSP ；人工蚁群；最短路径； 决策树；问题重述与分析11问题重述随着人们的生活不断提高，旅游已成为提高人们生活质量的重要活动。但时间

3、往往是限制人们旅游一个难题，为了满足旅游者的需要，张家界景区打算造高空浏览车方便人们短时间内游览更多的景点，假定游览车的起点在张家界国家森林公园，造价为每米10万元，为了使时间最短和总造价最少，需要解决以下问题：1、针对附件所给地图，自建适当坐标系标出各个景点坐标2、设计最佳的缆车运行路线贺龙会将军岩五女拜师双龟探溪九重仙阁童琦露布广 采药麻 空中田酎*豉,天悬白练光1家*E知一插珀神兵聚会ij人桥里张家界旅游至黄龙掴1.2问题分析随着人们生活水平的不断提高，旅游已经成为人们忠爱的休闲方式之一。在制定旅游计划的同时需要考虑很多方面的问题，比如：旅游路线的选择、旅途用 时、经济花销等等。游客为了

4、在完成旅游计划的基础上实现省时、方便、经济的目标， 需要一个最优的旅游方案。在此情况下，风景区为了给游客更人性化的服务，和吸引更 多的游客，就要为游客们制定一个更合理的路线，以满足游客的期望。本文给游客的旅游计划一在一定时间内游玩更多景点，要求达到旅途最短、省时又 方便和景区造价最经济的目的。为了实现这一目标，需要制定一个最优的旅游方案。首 先要实现在固定时间内可看景点最多，旅途最短，本问题属于一个对称旅行商（TSP） 问题。很显然，如果利用传统的动态规划解法在N为47的情况下，解法的空间复杂性 及时间复杂性都十分庞大，不利于旅行方案的确定。因此，本文采用人了工蚁群算法， 通过计算机编程可以得

5、到最优以及次优的旅行路线。得到优化后的旅游路径后，本文需要考虑另外的条件，经济问题、时间问题、方便 问题等，为了综合考虑这几方面的因素，需要制定一个决策模型，设计决策树与问卷调 查，通过问卷调查可以得到人们对于出发时间、各景点的期望值、游玩时间的选择标准， 再通过合理的计算，得出满意的路线方案。二 模型的基本假设和符号说明2.1模型假设（1）假设景点与景点之间的距离为平面最短距离；（2）假设每个景点的吸引游客的量一样，都有进行投资的价值；（3）假设2.2符号说明JDi气分别代表以下景点：九天洞，将军岩，天子峰，天台，御笔峰，贺龙公园， 仙女献花，雄狮回首，仙人桥，采药老人，龙泉飞瀑，鸳鸯瀑布，

6、空中田园，老屋场， 天波府，天悬白练，神兵聚会，张良墓，水绕四门，天下第一桥，空中走廊，迷魂台， 后花园，重欢树，跳鱼潭，五女拜师，紫草潭，千里相会，天桥遗墩，黑枞脑，双 龟探溪，黄狮寨，南天一柱，定海神针，天桥，花果山，南天门，劈山救母， 天书宝匣，鸳鸯泉，九重仙阁，金鞭岩，闺门岩，护鞭神鹰，夫妻岩，国家森 林公园，鹰窝寨要经过的景点总数;d:任意两景点之间的距离；L(s):表示蚂蚁s行走的景点集合;f (w):表示景点12n的一个排列;七:信息值；P k :挥发因子；W :景点坐标值；S 1 :最短路径最优解；S 2:最短路径次优解；P :投建缆车初次投资P :投建缆车平均年投资三模型的建

7、立与求解3.1问题(1)模型的建立及求解3.1.1模型的建立在本文中，由于景区面积并不大，在给出图形比例1 ： 10万的具体景区分布图上提 取各景点坐标值，相对误差不大。所以为了问题二的解决，必须首先确定各个景点的具 体坐标，再求出它们之间的距离。在本问题中的主要任务就是建立适当的坐标系，并确定各个具体景点的坐标值，在 此，我们应用MATLAB中的ginput函数。在把图片载入MATLAB的前提下选取47个具体 的风景点，对其用数字标注，得到它们的具体坐标。但这种情况下确定的坐标原点在图 片的左上角，绘出的各景点的散点图并不直观反映图中所视各景点分布情况。在原先的 坐标基础上，进行了各景点的坐

8、标变换，建立了常用的坐标原点在左下角的情况，其散 点图可直观反映出景点相对具体分布的地理位置。其散点图如图一所视：图一风景区各景点地理位置坐标分布图3.1.2模型的求解景点具体坐标如表-景点XYJD 1九天洞143544将军岩262461天子峰302419天台404438御笔峰436442贺龙公园442449仙女献花473432雄狮回首440367仙人桥339388采药老人386353龙泉飞瀑182381鸳鸯瀑布299352空中田园325287老屋场342329天波府140335天悬白练220309神兵聚会340293张良墓334270水绕四门357260天下第一桥214281空中走廊1512

9、80迷魂台210266后花园254258重欢树280246跳鱼潭291237五女拜师207254紫草潭250239千里相会262235天桥遗墩171239黑枞脑181233双龟探溪245222黄狮寨198214南天一柱194195定海神针213194天桥266193花果山238179南天门189193劈山救母209184天书宝匣179185鸳鸯泉149183九重仙阁115191金鞭岩225161闺门岩209139护鞭神鹰229168夫妻岩179128国家森林公园21879JD 47鹰窝寨653170表一本坐标建立在以图片左下角为原点，以整个图片为定义域的786*564的坐标系内。按照图片转换比

10、例尺坐标中每一单位代表20.6米3.2问题（2）模型的建立及求解3.2.1模型的建立游客在旅游时一般会游览景区内所有景点，在本模型中，主要景点有47个，本文 中所提到的缆车修建问题，即为通达47个主要景点的最短距离，从而使造价成本最少。本问题属于一个对称旅行商（TSP）问题，利用传统的动态规划解法1在N为34的 情况下，解法的空间复杂性及时间复杂性都十分庞大，因此，本文采用人工蚁群算法、 进行求解。图1如图1所示，蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD 或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过9个 时间单位时的情形：走ABD的蚂蚁到达终点

11、，而走ACD的蚂蚁刚好走到C点，为一半路 程。图2图2为从开始算起，经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到 食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单位后，所有 开始一起出发的蚂蚁都经过不同路径从D点取得了食物，此时ABD的路线往返了 2趟， 每一处的信息素为4个单位，而ACD的路线往返了一趟，每一处的信息素为2个单位， 其比值为2： 1。寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD路线上增派一只蚂蚁（共 2只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素 单位积累为

12、12和4，比值为3： 1。若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共3只），而ACD路线上 仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为24和6, 比值为4： 1。若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线，而都选择ABD 路线。这就是正反馈效应。人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。同时，人工蚁群再选择 下一条路径的时候是按一定算法规律有意识地寻找最短路径，而不是盲目的。在TSP问 题中，可以预先知道当前景点到下一个景点地的距离。TSP问题表示为一个N个景点的有向图G= （N，A），其中N = 1,2,.,n，A = （i,

13、j）l i, j e N（1）景点之间的距离目标函数为：（气）nxn其中(2)f （w） = dii i=1/昌占1 9.n的一不排万n w = （i ,i ,i ） i = i为景点1，2 , n的 个排列。i 2 n，n+1 1。假设m只蚂蚁在图的相邻节点间移动，从而协作异步地得到问题的解。每只蚂蚁的步转移概率由图中的每条边上的两类参数决定：一，信息素值，也称信息素痕迹。二， 可见度，即先验值。信息素的更新方式有2种，一是挥发，也就是所有路径上的信息素以一定的比率进 行减少，模拟自然蚁群的信息素随时间挥发的过程；二是增强，给评价值“好”（有蚂 蚁走过）的边增加信息素。蚂蚁向下一个目标的运动

14、是通过一个随机原则来实现的，也就是运用当前所在节点 存储的信息，计算出下一步可达节点的概率，并按此概率实现一步移动，逐此往复，越 来越接近最优解。蚂蚁在寻找过程中，或者找到一个解后，会评估该解或解的一部分的优化程度，并 把评价信息保存在相关连接的信息素中。算法步骤如下：步骤1：对n个景点的TSP问题，N = 1,2，,n A = (i,j)l i, j e N，景点间的距离矩阵为(d.)nnn，给TSP图中的每一条弧(i，j)赋信息初始值假设m只蚂蚁在工作，所有蚂蚁都从同一景点出发。当前最好解是= (1,2,n)。步骤2：(外循环)如果满足算法的停止规则，则停止计算并输出计算得到的最好 解。否

15、则使蚂蚁s从起点i0出发，用L(s)表示蚂蚁s行走的城市集合，初始L(s)为空集， 1 s m 步骤3 (内循环)按蚂蚁1 s m的顺序分别计算。当蚂蚁在景点，若L(s) = N 或 * l(i, l) e A，l 冬 L(s) =(4)完成第s只蚂蚁的计算。否则，若L(s)丰 N 且 T = * l (i, l) e A, l 史 L(s) 一 Z 中(5)则以概率c (k 1)Pi 七 C (k 1) e T，Pj = , j 冬 T(6)ijleT到达j，L(s) = L(s)Jj i = j(7)若L (s)丰 N 且 T = l (i, j) e L(s) =中(8)则到达，L(s)

16、 = L(s)U b = io重复步骤3。步骤4：对1 s m，若L(s) = N，按L(s)中景点的计算路径程度；若L(s)。N， 路径长度置为一个无穷大值(即不可到达)。比较m只蚂蚁中的路径长度，记走最短路径的蚂蚁为t。若f (L(t) 1，满足，k K并且Up k=8，经过k次挥发，非最优路径的信息素逐渐减少至消失。 k=1最总停止计算，输出本次运行的最优路径。3.2.1模型的求解在求解时利用各个景点的具体坐标作为决策变量，运行MATLAB-M文件(详见附录-MATLAB程序1)，将47景区的坐标值143262302 404436 209229 179218653W =544461419

17、 438442 139168 12879170调入程序。运行多次后，出现多个运行结果。在此，要对多个运行结果进行筛选，即求出多个运行结果中的最优解与次优解。首 先需要知道路径中城市与城市之间的距离气。将所有城市编号得：景点九天洞将军岩天子峰. 夫妻岩国家森 林公园鹰窝寨编号JD1JD2JD3. JD45JD46JD47利用景点坐标值143262302404436 209229179218653W 二544461419438442 13916812879170用MATLAB （详见附录-MATLAB程序2）求出：坐标系中点与点之间距离为0145.1202.3 417.6471.0632.4145

18、.1058.0 343.2384.5487.4202.358.00315.9350.2430.4417.6343.2315.9 .062.6475.9471.0384.5350.2 62.60444.4632.4487.4430.4 .475.9444.40按照问题一中的比例坐标中一单位为实际距离20.6米，根据得出的数据能够直接一 02.9024.045 .8.3519.42012.6492.90201.160 .6.8647.6919.7484.0451.1600.6.3197.0048.607得到景点z到j距离，d =:,:ij:8.3516.8646.319 .01.2539.5179

19、.4207.6917.004 .1.25308.888_12.6499.7488.607 .9.5178.8880单位为千米。在此可以明显注意到，第47个景点鹰窝寨距离其他景点距离明显偏远，而在实际 地图中可以看到，其并不在主要风景区之内，考虑到缆车造价非常昂贵，通往其路径在 此排除修建缆车的计划之内。进而利用MATLAB求出了最短路径最优解（图二）*= 38.833km与次优解（图三）% = 39.078km :200200400600400300411111X._、X/.1-/r盘”绪时M 蠲一A嗑）弟、% 8540 庆 38%褂47/ -、43标11111300图二假设旅行线路的方向如图

20、3、图4所示，对路径上的城市旅游的先后顺序进行编号。路径最优解:国家森林公园6）。闺门岩43） 金鞭岩42）t护鞭神鹰4（花果山36） 天桥（5）双龟探溪3 （ t千里相会28）。紫草潭27）。后花园23）。重欢树24。跳鱼潭25）。水绕四门19）。张良墓18） 。空中花SLIt神申兵聚分成。老屋场14）t采药老人10t雄狮回首8）。仙女献花7）t贺龙公园6） 。御笔峰5）t天台4）t仙人桥9）t鸳鸯漏12）t天子峰3）。将军岩2）。九天洞1）t龙泉飞瀑11） 。天波府15） t空中走廊2L）t天悬白练1的。天下第一桥20）。迷魂台22）。五女拜师2的。天桥遗墩29） t黑枞脑30） t黄狮寨

21、32）。定海神针34）。劈山救母38）。南天一柱33）。南天门37）。天书宝匣39） t鸳鸯泉40）。九重仙阁41）。夫妻岩49）。国家森林公园6）（路径次优解：国家森林公园6）。闺门岩43）。金鞭岩42）t护鞭神鹰44）。花果山36）。天桥35）。双龟探溪3D 。千里相会28）t紫草潭27） t后花园23）。重欢树24。跳鱼潭25） t水绕四门19） t张良墓18） 。空中花园1多。神兵聚会1成。老屋场Mt鸳鸯瀑布12）t仙人桥9）。采药老人10t雄狮回首8 ） 。仙女献花7）。贺龙公园）t御笔峰5）。天台4）t天子峰3）。将军岩2）。九天洞1）t龙泉飞瀑11） 。天波府15）。空中走廊2L

22、）t天悬白练16）t天下第一桥20）。迷魂台22） t五女拜师2的。天桥遗墩29） t黑枞脑30） t黄狮寨32）。定海神车十34）。劈山救母38）。南天一柱33）。南天门37） t天书宝匣39） t鸳鸯泉40）t九重仙阁41）。夫妻岩45）。国家森林公园6）（以上为游客设计了参观张家界景区的最优路线图，但本模型要想实现并不能脱离，景区对本计划的实施，即要算出建造缆车的大致投资，在本问题中已经得出，最优路线的最短距离，由此可以容易算出景区建造缆车的第一笔投资款为：P =Sl*1000*10代入数据就可得到第一笔投资款P=388330万元四、模型优化根据观测的结果，对张家界国家森林公园出入口及园

23、内两条主要游览线的日客流时空 分布规律进行了分析，结果表明，公园大门仍是游客进出公园的主要途径，流入公园的 客流集中在一天中的0810时，流出公园的客流集中在1213时和1617时。金鞭 溪游线中间位置的紫草潭和千里相会是两个方向游客的交汇处，客流最为集中。缆车成 为游客上下黄石寨游线的主要交通手段，而夫妻岩和腰子寨两条游线的客流极少。游客 流量测量和分析是旅游地管理的重要基础工作，通过流量分析可提供进入景区的总流 量、游客流量的时间和空间分布以及简单的游客特征数值，这些数据可为旅游景区客流 量的预测、旅游基础和服务设施、环境保护设施的建设以及旅游产品的更新提供重要依 据。具体分布如表二也拥段

24、）擀-如叫-101A 1111- 1212- B13- 1414- 1?1砂T7m IS合计出利水垸四门门票站104:01?13(6-Wj1珊63249&1842-210:亏9136制12洗裁峪方向1SQ:关夷对12匕15 2%干里扣会U2-1n650U. 9%U11：1:至211?11301041珊大门门祟站1 34)514普5029921?1S；2381g扑北6&既合计1心您5451；D祯3折；4：迎京741日100比例5%4泓1盹S 6%7. 9%7.舛7. *i 2%1 5%:m表二由此表可知，不同景点的游客量有很大不同，九天洞方向的游客很少，但其路径有很远，在这儿可以考虑省去修建去其

25、方向的缆车路线，修订后的路线图如图四：550修订后路线如下 国家森林公园6）。闺门岩43）金鞭岩42）t护鞭神鹰（花果山36）天桥（5）双龟探溪Wt千里相会28）。紫草潭27）。后花园23）。重欢树24）。跳鱼潭25）。水绕四门1t张良墓18）。空中花SLIt神申兵聚分刘。老屋场14）t采药老人0。雄狮回首8）。仙女献花7）。贺龙公园6）t御笔峰5）t天台4）t仙人桥9）t鸳鸯漏12）。天子峰3）。将军岩2）t龙泉飞瀑11）。天波府1 5）t空中走廊21）t天悬白练16）。天下第一桥侦。迷魂台22）。五女拜师26）。天桥遗墩29） t黑枞脑30）。黄狮寨32）。定海神针34）。劈山救母38）。

26、南天一柱33）。南天门37） t天书宝匣39）t鸳鸯泉40） 。九重仙阁41）。夫妻岩49）。国家森林公园6）（修订后的最短总路线S； = Sl - 4.111 = 34.722km修订后的总初次投入Pf = S *1000*10=347220万元比原来减少了 41110万元。五、模型的误差分析1、本模型利用蚁群算法计算最短路径时是依据的两两景点之间的最短距离，由于各景 点海拔的不同，而实际上两景点之间的距离并不是两两景点之间的直接距离。2、本模型在选取各景点具体坐标时，由于计算方法本身存在误差，导致在计算时引用 有误差的数据导致了结果也会存在一定的误差。3、实际游览过程中，由于游客对不同景点

27、的期望值不同，会导致他们不愿按照模型中 设计的最短路线去走，会有除最短路线上缆车的修建外，其他景点之间的缆车修建。4、在修建时由于个别景点之间距离太近不去修建，还会存在一些景点由于地理环境无 法修建。六、模型复杂性分析1、模型的复杂性：（1）对于周游先生计划游遍全国的省会城市、直辖市、香港、澳门、台北这一问 题，我们运用了模型（1）来计算周游先生完成旅游计划的最短行程，采用人工蚁群算 法，利用MATLAB编程得到了最短的旅行行程以及旅游路线，相对于传统的动态规划解法，达到了省时、简便的效果，大大降低了计算的复杂性。（2）对于订票方案问题，我们给出了模型（2）、（3）的求解；为了反映决策者的 主

28、观意见，这里引入重要性程度G与满意度H，综合考虑了出行方式，出发时间，到达 时间，旅行用时，旅行路程，票价等的重要性程度G与满意度H，给出了 “决策树”， 决策者先通过打分，再通过计算程序进行处理，就能简单地选择出理想订票方案。（3）建立的模型能与实际紧密联系，结合实际情况对所提出的问题进行求解，使 模型更贴近实际，达到了运用数学知识解决实际问题的目的。七、模型可行性检验与推广由本模型可知景区要实现这一模型除此总投入为347220万元。这么大笔投资的利润是 景区所要考虑的，但如果票价太高就会导致选择乘坐缆车的游客减少，票价过低，本工 程的成本回收周期过长，就很少有人投资因此要论证其可行性，就要

29、比照，目前游客的 旅游成本，何在一定成本回收期内所定的票价。7.1 据调查一般缆车的使用时限为20年，缆车每年每米所需维修费用为30元，即 本工程所需总投入为 Q=347220+20*34.722*1000*30/10000=3.4930e+005 万元使用平均年限法每年所承受投入为Q/20=17465万元如要想在使用年限内收回成本最低票Pmin=17465/100=174.65元7.2 根据调查，张家界国家森林公园平均客流量已超过100万次/年，在此使用其下 限100万次/年各种票价如表三种类价格/元条件门票1245两天内有效门票2298一周内有效天子山索道52单程黄石寨索道50单程水绕四门

30、观光电梯56单程酒店1100三星（每天）酒店2250四星（每天）额外消费50每天表三每人游览景区所需金额（最低标准）随时间变化如表四时间具体花费二门票+天数*饮食+ （天数 1）*酒店（按平均175）+总索道费用 （158）总金额提前天所省金额1245+50+1584032245+2*50+175+1586782253298+3*50+2*175+1589562784298+4*50+3*175+15811812255298+5*50+4*100+15814062256298+6*50+5*100+15816312257298+7*50+6*100+1581856225表四7.3由以上可知如若

31、游客选择缆车，索道的总费用就可完全省去，且可乘缆车游览更多 景点，与此同时也可减少游览时间，由表四可知，每减少一天游览时间至少可节省225 元，即在此情况下景区的定价区间为p=174.65,383元同理在减少n天的条件下的定价区间为p=174.65,（158+225*n）.由此看来景区的缆车 票价定价区间还是比较宽的。即利润空间还是比较大的。同样对于游客来说，用较少的 花费，游览更多景点也是他们期望的。本案例建立的模型解决了游览路线优化问题，采用了人工蚁群算法解决了最短路径问 题。因此，本模型还可以运用于很多领域类似的关于路径优化以及经济优化的问题，如： 输油管道的铺设问题、邮递员送信问题、交通运输问题等。本模型具有较高的可行性与 应用价值。参考文献1 卢开澄.单目标、多目标与整数规划.北京：清华大学出版社.19992 吴红，王远世.搜索不同TSP最佳路径的多蚁群优化算法.中山大学报（自然科学版）.第44卷 第4期2005年7月.13203 许玖平等.运筹学：数据.模型.决策.北京：科学出版社.20064 薛定宇等.高等运用数学的MATLAB求解.北京：清华大学出版社.2008.105 amy2009win蚁群算法mat lab源程序%86%5Efield%3D%2A/12010.4.266 Yuehui Chen 蚁群算法.ppt 2010.4.27附录