旅游路线规划.doc

旅游路线的优化设计摘要本文通过查阅各景点之间的距离及时间的相关资料，运用图论中的Hamilton圈将相连后的景点看作为一个封闭的圈，参照货郎担（TSP）问题使用线性规划列出相关目标函数后运用lingo求解。对于问题一，在得到距离数据后，在假设距离短则花费少的思路下，使用0-1规划建立目标函数，建立关于时间和景点数量的约束条件，在软件求解下得到十个景点3892.5元的最小旅行花费。而在问题二中将距离数据改成时间数据，得到7.5天游玩8个景点的优化方案。关键词：图论 Hamilton圈 0-1规划 一、问题重述某背包客要独自旅游十个景点，分别是：江苏常州市恐龙园，山东青岛市崂山，北京八达岭长城，山西祁县乔家大院，河南洛阳市空门石窟，安徽黄山市黄鹤楼，陕西西安市秦始皇兵马俑，江西九江市庐山，浙江舟山市普陀山。又已知上述各个景点的最短停留时间分别是4小时，6小时，3小时，3小时，3小时，7小时，2小时，2小时，7小时，6小时。假设：1 城际交通出行可以乘火车（含高铁）、长途汽车或飞机（不允许包车或包机），并且车票或机票可预订到。2 市内交通出行可乘公交车（含专线大巴、小巴）、地铁或出租车。3 旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票（第一门票）。晚上20:00至次日早晨7:00之间，如果在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。吃饭等其他费用60元/天。1、 假设景点开放时间为8:00至18:00。问题：根据以上要求，针对如下的几种情况，为该旅游爱好者设计详细的行程表，该行程表应包括具体的交通信息（车次、航班号、起止时间、票价等）、宾馆地址和名称，门票费用，在景点的停留时间等信息。（1） 如果时间不限，游客将十个景点全旅游完，至少需要多少旅游费用？请建立相关数学模型并设计旅游行程表。（2） 如果旅游费用不限，但由于“十一”假期只有7天，为了使游客能尽可能多游览景点，请通过建立相关数学模型，为其设计该旅游行程表。如果这位游客只有7天的假期时间和5000元的旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。三、问题假设及符号约定1.模型假设：1) 问题一中尽量不考虑以飞机作为交通工具，以节省费用车次或航班在旅行途中的时间。2) 问题中不考虑城市间的公交线路拥堵等造成的特殊情况。3) 各城市的公交费用相等，皆为10元。2.符号约定：第个景点或第个景点 ；（分别代表浙江杭州、江苏常州、山东青岛、北京八达岭、山西祁县、西安兵马俑、湖北武汉、江西九江、安徽黄山、浙江舟山、河南洛阳）；：旅行者的旅游总消费；：在第个景点的逗留时间；：在第个景点的总消费；：旅游者从第个景点到第景点路途所需时间；：旅游者从第个景点到第景点路途所需的交通费用；：1表示旅游者直接从第个景点到第景点；0表示其它；：总的交通费用；：旅行所花时间二、问题分析将该背包客旅游的景点一一描点相连，不难发现旅游范围几乎囊括了大半个中国。旅游的时间段为10.1黄金周，也昭示着传统旅游旺季的来临，各大景点几乎是人满为患。因此旅游者安排一个合理的出行计划就至关重要了。对于问题一，我们知道在时间不限，费用最少的要求下，黄金周时期高昂的机票让游客可以不用考虑乘坐飞机往来景点所在城市，剩下的便是城际的长途客车和铁路线系统。生活观察中，我们发现出发地和目的地距离越远，乘坐交通工具所需的费用也就越大：参考网上的数据我们可以得到两两城市之间的大致距离，根据城际间的各种票价，我们发现不管何种交通工具，伴随着距离的增加费用也随之增长。由此可以推断出，只要求得各大旅游城市距离总和的最小值，依据这个最小值，背包客可以决定旅游城市的先后顺序，参照当天的旅游情况，选择长途客车或铁路系统；同时为了减少费用，可以有选择的安排游客在夜间的长途客车或火车（包括动车高铁）中休息，即可省去在当地住宿的费用。对于问题二，考虑旅游者费用充足且时间限定，因此我们可以极端的假设。一切都以时间最省为基准。在所有交通工具中飞机时间最省，加上登机时间，飞机较之于长途客车和铁路系统在时间的节省上也远远领先。参照网络中各个目的地之间的航班，确定出城市之间飞行所用时间。由于有些城市对另一城市不存在直达航班，此时我们考虑中途转机（或乘坐火车）到目的地邻近的城市再转动车或客车。在这样的安排下游客可以在7天内尽可能多游览景点。四、模型的建立与求解问题一：4.1.1数据准备根据两个城市之间的公路及铁路，经过数据查询，得到下表各个旅游城市之间的距离：表一：各旅游城市距离表起始目的地江苏常州山东青岛北京八达岭山西祁县西安兵马俑湖北武汉江西九江安徽黄山浙江舟山河南洛阳杭州35214241591159615588077794222301171常州973129813321344662586507385957青岛819100815721518142015439751185北京81511591200131415331430807祁县593124311681315.61569.6706西安1025110213861609387武汉2407491059638九江571779964黄山4621113舟山1200洛阳灰格子代表该景点与另一个景点距离重复在上表中，为方便统计，将浙江杭州到河南洛阳依次编排序号为111，记为 。4.1.2 算法的确定将至共11个点两两相连，利用排列组合公式得到11个景点共条线路，得到图一：图一从图中看出，11个城市之间的路线十分复杂，但必定存在一种最短路径法求解11个城市的次序。根据假设，整个旅游路线是环形，即最终旅游者要回到杭州，因此我们可以把整个路线看做一个Hamilton圈，这样该问题就归结为货郎担（TSP）问题。4.1.3 目标函数的确立： 经过对题目分析，我们可以知道本题所要实现的目标是，使旅游者在不规定时间的情况下游玩十个景点所花的费用最少。显然，花费最少是该问题的目标。因此，我们的做法是在满足相应的约束条件下，先确定游览的景点先后，然后计算出在这种情况下的最小花费。游览的总费分别为交通总费用和在旅游景点的花费等组成，其中大部分都是规定的，只有交通费用是可以选择的。所以我们定义：每个旅游者的旅游总花费；每个旅游者的交通总费用；从而得到目标函数： 因为表示从第个景点到第个景点所需的交通费用，而是判断代表们是否从第个景点直接到第个景点的01变量，因此我们可以很容易的得到交通总费用为：从而我们可以得到目标函数为：4.1.3约束条件：时间约束 问题一放宽了对时间的要求，我们不妨可以假定限制的时间为15天（360个小时），因为表示从第个景点到第个景点路途中所需时间，所以路途中所需总时间为；表示旅游者在第个景点的逗留时间，故旅游者在旅游景点的总逗留时间为。因此，总的时间约束可得：旅游景点数约束 由题目要求可知，因为旅游者的时间充裕，因此他（她）打算游览完全部11个景点。因此将其约束为： (，=1，2，11)01变量约束在已经知道了要旅游所有的景点的前提下，对于Hamilton圈中的每个点来说，只允许有一条边进入，同样，也只允许有一条边出去。用公式表示即为： （，=1，2，11）同样，当，时，根据题意不可能出现，即不可能出现游客在两地间往返旅游，因为这样显然不满足游览景点尽量多的原则。因此我们可得约束： （，=2，3，11）最后我们将其模型建立为如下所示： 运用lingo解得旅游者游行十个景点通所用的费用为1224，景点先后顺序如下所示：浙江杭州浙江舟山安徽黄山江西九江湖北武汉河南洛阳西安兵马俑山西祁县北京八达岭山东青岛江苏常州浙江杭州。如下图所示：图二4.1.4问题一所建模型结果 根据搜索出来的数据值，我们在对时间的放宽情况下，选取交通费用最少的交通工具和住宿费用来安排其的行程安排表，如下表所示：日期起终车次起止时间价格/元景点逗留时间/h住宿/价格1号杭州舟山客车 高大27：5011：30706舟山普陀港城商务酒店单人房178元/天2号不游玩舟山宁波客车 高速7：058：3032宁波黄山客车 高大一13：4018：20132世界家庭式酒店/民宿 90元/天 3号黄山8：0018：0010世界家庭式酒店/民宿 90元/天4号黄山九江大巴8：0013：00122学校招待所40元/天5号九江庐山8：0015：007九江武汉火车 k398/k39517：0020：3041武汉岭南佳园连锁酒店119元/天6号武汉黄鹤楼8：0010：002武汉洛阳火车 k864/k86115：2522：0087洛阳易国际青年旅舍40元/天7号洛阳市龙门石窟8：0011：003洛阳西安火车 k128/k125 14：5019：2055西安七贤国际青年旅舍50元/天8号西安秦始皇兵马俑8：0010：002西安太原空调普快221：486：48148太原祁县乔家大院6815次列车7：009：005.5乔家大院10：0013：003山西北京空调特快T7014：4519：49北京富山国际青年旅舍46元/天9号八达岭长城8：0018：0010北京山东青岛快速K712/k70922：0010：0819510号青岛崂山11：0018：007青岛南京快速 K416/k41320：0011：3020811号南京杭州空调普快200112：4220：0264在将其交通所用的费用，住宿所用的费用，10个景点门票所花的费用，以及11天所用的伙食费累加起来得到在时间不限的情况下至少要消费3892.5元。问题二：4.2.1模型的建立与求解在得到各个旅游城市之间的最小旅行时间后，可以同样利用问题一中所用的，将点与点之间的时间看作为它们边的权值，起点与终点相连可以构成封闭圈，采用Hamilton图的概念求最小距离（时间）的Hamilton圈。将看作为i地点到j地点之间的最少时间，（1表示连接，0表示不连），则可以建立目标函数：下表为各点之间相互往来所花时间的最小值，将表中的数据带入Lingo求解上述目标函数（程序见附录）。表二：各景点之间的最短时间值起始目的地浙江杭州江苏常州山东青岛北京八达岭山西祁县西安兵马俑湖北武汉江西九江安徽黄山浙江舟山河南洛阳杭州02.51.523.321.5522.51.8常州2.505.81.53.524.25654.2青岛1.55.801.16321.91433.53.8北京21.51.1602.51.822.2522.252.8祁县3.33.532.502.52.52.61.73.73.5西安2221.82.50141.63.53.5武汉1.54.21.9122.5102.63.32.83.2九江5542.252.642.602.34.23.2黄山26321.71.63.32.303.73.5舟山2.553.52.253.73.52.84.23.703洛阳1.84.23.82.83.53.53.23.23.530求解得到10个旅游城市旅行的先后顺序是：杭州青岛北京常州西安黄山祁县九江武汉舟山洛阳杭州图三 在上图中我们看到线路杂乱无章，这是考虑了飞机后的影响因素，在飞机的速度下，相距很近的两个景点城市所花的时间反而要大于两个相距很远的城市时间，在这样的情况下，使用软件求解线性规划的函数，得到各个城市跨度如此大的路线图，甚至可以满足7天内游玩遍所有的城市景点。得到所花时间t为22.26 ，但这个数值是仅代表该游客在飞机上乘坐所用时间。在实际游玩中，需要考虑到景点游玩时间，候机时间，上下登机时间，市内公交等，而乘坐飞机时间花费短，也断绝了在交通工具上休息的可能性，还需包括住酒店宾馆等的休息时间。4.2.2 问题二所建模型结果景点游玩最少时间=43h，上下登机总时间=221=22h，市内公交101=10h，休息时间=96=54h .全局最优解为：160.26小时，但任何时候人要服从与现实中交通的安排，所以在旅行途中还应包括各种班次的等待时间，所以最后结果会跟计算出来的时间总和以及景点顺序会与软件求出的最优解产生偏差。根据得到的顺序，我们安排游客按下列行程旅游：表三：旅途行程表（问题二）日期起终车次/航班起止时间价格行程住宿/价格1杭州 青岛山东航空SC4684 9：00-10：30749青岛崂山游玩6小时北京富山国际青年旅社/199青岛北京山东航空SC157621：15-22：40 6202北京西安东方航空MU278111:40 -13:45990北京八达岭游玩3小时至12点，2点45到达兵马俑景地欣燕都连锁西安互助路 /1353西安武汉海南航空HU7889 8：25 -9：30 48010：30点到达黄鹤楼，游玩2小时在列车中住宿4武汉祁县K522/K519中转K868/K86516：11 -6：29转7：40-8：47417+159：30到达桥架大院，游玩3小时至12点在列车终度过5祁县至常州先乘坐4626转太原，再乘坐K374/K371到常州14：55-16：14转17：51-12:287+440游玩常州恐龙园4小时至18点在列车中度过6常州黄山K8418/K8419( 上海- 黄山)23:32 -09:00252游玩黄鹤楼7小时黄山洛阳乘坐上海航空FM9266至上海18：00 -20：00370+100上海鹰都宾馆/1287黄山洛阳东方航空MU53897：50-9:40450+150游玩龙门石窟3小时洛阳杭州东方航空MU570015：35-17：151300按照上表中的顺序，最终游客的旅游路线为：杭州青岛北京西安武汉祁县常州黄山洛阳杭州所需时间t为7天，符合题目中所要求的7天内回到杭州。五、模型评价及推广 论文中的模型利用图论以及计算机进行优化，得到的旅游行进路线，游客的旅游计划得到了合理化的安排。但是由于文中各地的繁杂的车次导致变量过多，很难得到真正意义上的全局最优解，但是在短途旅行中，本模型能适用于求最短路径或最短时间下其他的约束问题。六、参考文献1王兵团，数学建模基础，北京：清华大学出版社，2004年2姜启源，数学模型（第三版），北京：高等教育出版社，2003年3刘承平，数学建模方法，北京：高等教育出版社，2002年4于义良，数学建模，北京：中国人民大学出版社，2004年5朱道元，数学建模案例精选，北京：科学出版社，2003年6吴祈宗，运筹学，北京：机械工业出版社，2004年1月程序附录：附录：费用浙江杭州江苏常州山东青岛北京八达岭山西祁县西安兵马俑湖北武汉江西九江安徽黄山浙江舟山河南洛阳浙江杭州046274330330301224877070256江苏常州46023827228828219087130180216山东青岛2022380195206221301298312430256北京八达岭330272195073256263262320604130山西祁县330288206730153.5256200250242172西安兵马俑301282221256153.5023422935835055湖北武汉22419030126325623404126026387江西九江8787298262200229410122205216安徽黄山701303123202503582601220164135浙江舟山701804306042423502632051640258河南洛阳25621625613017255872161352580时间浙江杭州江苏常州山东青岛北京八达岭山西祁县西安兵马俑湖北武汉江西九江安徽黄山浙江舟山河南洛阳浙江杭州0522.815.722.520.38.510.52.53.715江苏常州501013.520148.599.5510山东青岛22.810011.712.51920.515.8231615.7北京八达岭15.713.511.70511.51014.51628山西祁县22.52012.550121618212012西安兵马俑20.3141911.512011.21813254.5湖北武汉8.58.520.5101611.203.710117江西九江10.5915.814.518183.7051412.5安徽黄山2.59.5231621131050615浙江舟山3.75162202511146019河南洛阳151015.78124.5712.515190问题一程序：sets:jingdian/1.11/:c,t,l;!其中：1,2,.,11分别代表浙江杭州、江苏常州、山东青岛、北京八达岭、陕西祁县、西安兵马俑、湖北武汉、江西九江、安徽黄山、浙江舟山、河南洛阳；c，t分别表示旅行者在各景点的吃住消费和逗留时间；l是为了控制不出现两个以上环形回路而设的一个变量;links(jingdian,jingdian):r,cc,tt;!其中：r为0-1变量（0表示两景点不相连，1表示两景点相通）；cc为两景点之间的交通费用；tt为两景点之间的交通时间;endsetsdata:t=0 4 63 3 2 2 7 7 6 3;c=00000000000;tt=051915.722.520.38.510.52.53.715501013.520148.599.551019100612.51920.515.8231615.715.713.5605.711.51014.5162822.52012.55.7011161821201220.3141911.511011.21813254.58.58.520.5101611.203.71011710.5915.814.518183.7051412.52.59.52316211310506153.75162202511146019151015.78124.5712.515190!其中：主对角线为零,表示各景点到自身交通费用为零;cc046202330330301224877070256460238272288282190871301802162022380113206221301298312430256330272113080256263262320604130330288206800148256200250242172301282221256148023422935835055224190301263256234041260263878787298262200229410902052167013031232025035826090013913570180430604242350263205139025825621625613017255872161352580;!其中：主对角线为零,表示各景点到自身的交通时间为零;enddatamin=sum(jingdian(j):sum(jingdian(i):r(i,j)*(cc(i,j)+0.5*(c(i)+c(j);!目标函数：表示计划游玩的景点数目为n时的最小费用;for(jingdian(i):r(i,i)=0);!约束条件：表示各景点到自身没有路线相连的约束条件;for(jingdian(i)|i#ge#2:for(jingdian(j)|j#ge#2:r(i,j)+r(j,i)1);!约束条件：表示除起点（杭州）外，若旅行者从景点i到景点j去游玩（即r(i,j)=1），则不会再从景点j到景点i去游玩（即r(j,i)=0），也就是说除起点外每个景点只游玩一次;a=sum(jingdian(j):sum(jingdian(i):r(i,j)*(tt(i,j)+0.5*(t(i)+t(j);sum(jingdian(j):sum(jingdian(i):r(i,j)*(tt(i,j)+0.5*(t(i)+t(j)360;!约束条件:表示总的旅行时间（交通时间和景点逗留时间）不超过给定时间15天360小时;for(jingdian(i):sum(jingdian(j):r(i,j)=sum(jingdian(j):r(j,i);for(jingdian(i)|i#eq#1:sum(jingdian(j):r(i,j)=1);for(jingdian(i)|i#ne#1:sum(jingdian(j):r(i,j)=l(i)+r(i,j)-(n-2)*(1-r(i,j)+(n-3)*r(j,i);for(jingdian(i)|i#gt#1:l(i)1+(n-2)*r(i,1);问题二：MO