北京市旅游线路的最优设计.doc

论文成绩： 北京市旅游线路的最优设计队 别：一队一区队 姓 名： 时 间：2016年6月25日 防化学院北京市旅游线路的最优设计摘 要：本文主要解决的是去北京旅游的最佳旅游路线的设计问题。针对一日游，二日游，三日游花最少的钱，基于对此的研究，我们建立了三个模型。 针对方案一：建立了单目标最优化模型。分别以一日游，二日游，三日游为目标，在北京市选定11个游览点，在约束条件下，建立0-1规划模型，以总费用最小为目标函数。使用 lingo 编程，最后求得的最小费用分别是：668元，1134元,1745元。具体方案为： 2111，211156，211156439针对方案二：建立了单目标最优化模型。以满意度为目标函数，在时间的约束条件下，运用lingo 编程，最后针对一日游，二日游，三日游分别求得满意度是：0.96,0.93,0.89。旅游路线为： 243, 112139, 2111910543关键词：多目标最优化模型 0-1规划模型 tsp lingo求解一、 问题重述1.1问题背景北京是全国著名旅游城市，每年接纳游客上千万人次。现假设黄金周期间，在外地读书的老同学、好朋友会过来北京游玩。根据不同游客的要求标准，对以下三种旅游：1.一日游2.二日游3.三日游设计出最佳的旅游路线。1.2需要解决的问题根据对题目的理解我们可以知道，需要解决的问题是在北京游玩天数，并且综合考虑车费，餐饮，门票 ，景点满意度等多方面因素。所以我们的目标就是针对不同游玩天数求出最少费用，以及针对满意度做出最佳旅游线路。二、模型假设假设1：旅行路线的总路程只包括在北京中观光旅游的路程；假设2：旅行者在北京的某一旅游景点游玩结束前往下一个景点时，所乘坐的交通工具都是非常顺利的，不会出现被滞留等意外情况；假设3：在乘坐交通工具的途中，不考虑除交通费用之外的其它任何费用；假设4：任意两点之间来回路程相等；假设5：每个景点游玩时间与满意度成正比，比例常数为k；假设6：定义满意度为针对本次该景点游客满意人数占总游客人数的比例；3、 符号说明符号符号说明旅游者在第i个景点的逗留时间第i个景点门票第i个景点到第j个景点的距离 =0表示景点i和景点j不连接 =1表示景点i和景点j连接景点i的满意度 四、问题分析设计路线的原则是：满足旅游者的意愿；在有限的时间内尽量游玩更多的景点；尽量使费用最低。对路线安排规划的时候时刻关注以上三个目标，从而在题目要求范围内求得最优解。4.1方案一的分析经过对题目分析，我们可以知道本题所要实现的目标是，使游客在有限时间内花最少的钱游览尽可能多的地方。显然，花费最少和游览的景点尽量多是该问题的两个目标。因此，我们的做法是在满足相应的约束条件下，计算出在这种情况下的最小花费，这样最终会得出几种推荐旅游路线。游览的总费用由3部分组成，分别为交通总费用、在旅游景点的花费和每天的餐饮费。4.2方案二的分析本方案所要实现的目标是，使游客在有限时间内游览满意度高。显然，满意度高和游览的景点尽量多是该问题的两个目标。五、数据分析数据收集如下：旅游过程都乘坐公交车，公交车时速40km/小时，价格每1元/10km；分别表示：1故宫， 2天安门广场，3天坛， 4颐和园，5长城，6十三陵水库， 7鸟巢水立方外景， 8恭王府，9清华北大， 10圆明园， 11-北海公园各景点间的距离（km） 1234567891011100.34.917.481.844.69.22.214.214.60.8620.304.612.564.437.235.47.012.00.413.1434.94.6012.576.939.74.32.79.39.73.04417.412.512.5064.427.28.215.23.22.816.54581.864.476.964.4037.272.679.667.667.280.94644.637.239.727.237.2035.442.430.430.843.7479.235.44.38.272.635.407.05.05.48.3482.27.02.715.279.642.47.0012.012.41.34914.212.09.33.267.630.45.012.000.413.141014.60.49.72.867.230.85.412.40.4013.54110.863.0426.216.5480.9443.748.341.3413.1413.540各景点客流量（万人次/天）123456789101130.3729.8721.1422.4523.6412.2524.6517.3210.3228.6526.72各景点门票（元）1234567891011601515604565804002510六、模型的建立与求解问题：比照tsp巡回旅行商问题，建立tsp模型，利用lingo和旅行商问题的结合，求出结果.6.1 方案一：6.1.1 目标函数的确立：我们定义：每个游客的旅游总花费；每个游客的交通总费用；每个游客的旅游景点的花费；每个游客的餐饮费用；从而得到目标函数： 。m为交通总花费 因为 表示从第 i个景点到第 j个景点距离，而 xij 是判断代 表们是否从第 i个景点直接到第 j个景点的 01 变量，因此我们可以很容易 的得到交通总费用为：6.1.2 约束条件：（1）时间约束由题目可知，游客在北京旅游时间应该不多于 3 天(30 小时)，而这些时间包括在路途中的时间和在旅游景点逗留的时间。因为表示在第 i个景点逗留时间，所以在景点游玩总时间为：所以路途中所需总时间为总的时间约束为：（2）01 变量约束 我们可以把所有的景点连成一个圈，而把每一个景点看做圈上一个点。 对于每个点来说，只允许最多一条边进入，同样只允许最多一条边出来， 并且只要有一条边进入就要有一条边出去。因此可得约束：j=11时，i=11时，无往返：（3）游玩景点个数限制 最多游玩11个景点从而我们可以得到目标函数为：6.1.3 模型的求解通过lingo求解，分别求出推荐路线为：2111，211156，2111564396.1.4模型的结果分析一日游，第一站天安门广场，第二站故宫，第三站北海公园。二日游第一站天安门广场，第二站故宫，第三站北海公园，第四站长城，第五站十三陵水库。三日游第一站天安门广场，第二站故宫，第三站北海公园，第四站长城，第五站十三陵水库，第六站颐和园，第七站天坛，最后到清华北大。6.2方案二：6.2.1 目标函数的确立：最高满意度 6.2.2 约束条件：（1）时间约束 景点逗留时间 所以路途中所需总时间为总的时间约束为：（2）01 变量约束 j=11时，i=11时，最多游玩11个景点：从而我们可以得到目标函数为：6.2.4 模型求解根据模型，使用 lingo 编程，分别对一日游，二日游，三日游得出结果为：243, 112139, 21119105436.2.5模型的结果分析 一日游，第一站天安门广场，第二站颐和园，第三站天坛。二日游，第一站北海公园，第二站天安门广场，第三站故宫，第四站天坛，第五站清华北大。三日游，第一站天安门广场，第二站故宫，第三站北海公园，第四站清华北大，第五站圆明园，第六站长城，第七站颐和园，第八站天坛。6 模型的评价、改进及推广6.1模型的评价 1.本文思路清晰，模型恰当，得出的方案合理； 2.本文成功的使用了 01 变量，使模型的建立和编程得以顺利进行；3.在第二问中采用了 tcp 算法，简化了模型的求解难度； 4.由于数据庞大，对程序的要求很高，尽管经过了检验，但结果依然 比较粗糙，有待进行进一步的改进。6.2模型的与推广1.实际情况中，两景点之间可能还有出公路外其他交通方式，如地铁，出租车， 增加这些考虑后，结果会更加合理。2.因数据资料搜集的不完整，准确性也有待商榷，而且没有对最终方案进行 更为细致的讨论研究