旅游线路的优化设计.doc

《旅游线路的优化设计.doc》由会员分享，可在线阅读，更多相关《旅游线路的优化设计.doc（21页珍藏版）》请在三一办公上搜索。

1、2011年第八届苏北数学建模联赛题 目 B题 旅游线路的优化设计摘要随着社会的发展，旅游日益成为现实社会的热点，为了得到一个比较实惠的旅游方案，我们需要有一套比较完善的预算体系，建立这样一套体系是一个多目标的决策问题。这一问题的重点在于将经济、时间等因素融入预算体系，使得预算的一个旅游方案更完善、更合理。本文主要研究最佳旅游路线的设计问题。在满足相关约束条件的情况下，花最少的钱游览尽可能多的景点是我们追求的目标。基于对此的研究，建立数学模型，设计出最佳的旅游路线。为了提出合适的旅游路线，本文选择了合适的模型，得到合适的路线，并给出了一些结果。第一问游完10个景点，且要费用最少。为此，我们建立旅

2、行商模型，以消费最低为目标，再辅以LINGO软件编程对模型求解，从而推出旅游路线，再根据具体的旅游路线计算出总费用。推荐方案为: 徐州-青岛-北京-太原-西安-洛阳-九江-常州-舟山-黄山-徐州.由此计算出总消费为：2689元第二问要在费用不限，且需的最短时间的方案。该问题可以以运筹学有关最优化和图论的相关知识为基础，建立基于蚁群模型为基础的优化模型。辅以MATLAB编程得到最佳路线为：徐州洛阳舟山九江黄山青岛武汉祁县西安北京徐州。按此路线，总共费用为：9908。旅游最短时间为6天零十个小时45分。 第三问时间充裕，要求费用低于2000元，把各景点看成纯数学中的点，利用应用图论中的思想，尤其是

3、Dijkstra算法模型求解。在建模中，把各景点间的路费和门票作为巡回图边的邻接矩阵权，使原题变图论中的求最短连通图问题，利用LINGO软件求解得到旅游路线应为：徐州-青岛-北京-太原-洛阳-西安-武汉-黄山-徐州。最少费用为:1945元。第四问给定五天的时间约束，我们借助于层次分析法的思想，先找出适合游览的景点，在确定最终旅游方案。利用LINGO编程进行求解，从而得到旅游路线为：徐州-洛阳-青岛-武汉-祁县乔家-西安-常州-八达岭-徐州。由此计算出总费用为:6775元第五问是在双重限定条件下，求最多能游览景点数目并确定旅游方案。此问题属于多目标函数的最优化问题。同样借助LINGO编程对模型进

4、行求解，得到最优的旅游路线为: 徐州-北京-太原-西安-洛阳-汉口-常州-徐州花费时间为：5.1号5.5号20:39，在五天内， 总共费用为：1765元。关键字：旅行商 TSP 层次分析法 图论 蚁群算法 Dijkstra算法一、问题重述随着人们的生活不断提高，旅游已成为提高人们生活质量的重要活动。江苏徐州有一位旅游爱好者打算现在的今年的五月一日早上8点之后出发，到全国一些著名景点旅游，最后回到徐州。由于跟团旅游会受到若干限制，他(她)打算自己作为背包客出游。他预选了十个省市旅游景点，如表1所示。表1. 预选的十个省市旅游景点省市景点名称在景点的最短停留时间江苏常州市恐龙园4小时山东青岛市崂山

5、6小时北京八达岭长城3小时山西祁县乔家大院3小时河南洛阳市龙门石窟3小时安徽黄山市黄山7小时湖北武汉市黄鹤楼2小时陕西西安市秦始皇兵马俑2小时江西九江市庐山7小时浙江舟山市普陀山6小时假设：(A) 城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机），并且车票或机票可预订到。(B) 市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车。(C) 旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)。晚上20：00至次日早晨7：00之间，如果在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。吃饭等其它费用60元/天。(D) 假设景点的开放时间为8:00

6、至18:00。问题：根据以上要求，针对如下的几种情况，为该旅游爱好者设计详细的行程表，该行程表应包括具体的交通信息(车次、航班号、起止时间、票价等)、宾馆地点和名称，门票费用，在景点的停留时间等信息。(1) 如果时间不限，游客将十个景点全游览完，至少需要多少旅游费用？请建立相关数学模型并设计旅游行程表。(2) 如果旅游费用不限，游客将十个景点全游览完，至少需要多少时间？请建立相关数学模型并设计旅游行程表。(3) 如果这位游客准备2000元旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。(4) 如果这位游客只有5天的时间，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。

7、(5) 如果这位游客只有5天的时间和2000元的旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。二、问题分析这其实是一个旅行商问题。此类问题又常被描述为旅行推销员问题，货郎担问题，简称TSP问题。是最典型的最短路径问题。该问题要求寻求旅行商从某一点出发，经过所给定的点以后，再回到出发点的最短路径。题目中所要求的费用最少、时间最短，从本质上来讲，都是此类问题的简单推广。三、问题假设1、火车票价与火车行驶里程成正比；2、天气良好，至少不会对列车运行造成影响；3、最短旅游路径是一个回路4、乘坐公交车去一旅游景点游玩，一般情况下，所需公交运费为5元；5、不考虑旅游者满意度问题。6.每

8、天伙食费达到最高标准60元/天。四、符号说明符号符号意义符号符号意义Ni第1个城市到第i个城市的中间城市集合S到达i城之前中途所经过的城市集合（i，S）描述过程的状态变量k(i,S)从1城市开始由k各中间城市的S集到第i城市的最短路线上紧相邻着第i城市前面那个城市。Vi第i个城市Xk(i)=Pk(i,S)决策函数Dij从i到j城的距离T旅行的总耗时T0乘坐旅行工具所耗费时间TP在旅游景点停留所花费时间TW1等待旅游景点开放所花费时间TW2等待列车所花费时间minf(x)|XSf为目标函数，S为可行解集合m算法中蚂蚁的数量d（i，j=1,2,3，n）表示边（i，j）之间的距离(此处表示两城市之间

9、乘坐飞机所需的近似最短时间)n城市个数 t时刻在（i，j）上残留的信息素量更新后边上的信息素量更新前边上的信息素量第只蚂蚁本次循环中留在边上的信息素量本次循环中边上的信息量增量常数第只蚂蚁在本次循环中所走过的路径长度GAi,j=maxintVi，Vj是不关联的，否则为权值（大于0的实数）DIST1.n当前求得的最短路径pay各景点门票Cost各城市间路费Time各城市交通所花时间五、模型建立与求解5.1 问题一模型：旅行商动态规划模型5.1.1模型分析：问题一需要确定在时间不限的情况下,游客要想把十个景点全浏览完，至少需要的旅游费用。这个问题属于组合优化问题，此处采用动态规划的递推方法求解是比

10、较方便的。该游客是从第一个城市开始的，设游客走到第i个城市，记作：Ni=2,3,4,、,i-1,i+1,、n表示由第1个城市到第i个城市的中间城市集合。S表示到达i城之前中途所经过的城市集合，则有SUi因此，可选取（i，S）作为描述过程的状态变量，决策为由一个城市走到另一个城市，并定义最优值函数k(i,S)为从1城市开始经由k个中间城市的S集到i城的最短路线的距离，则可写出动态规划的推递关系为：k(i,S)=mink-1(j,sj)+dji （式5.1.1）(k=1,2,n-1；i=2,3,n.) SUi边界条件为0(i,)=d1i，这里为空集。设Pk（i，S）为最优决策函数，它表示从第一个城

11、市开始经k个中间城市的S集到第i城市的最短路线上紧相邻着第i个城市前面的那个城市。5.1.2 模型假设查资料得火车(含高铁)、长途汽车或飞机，三种交通工具。其单位定价标准为飞机0.75元每公里（数据来源：中国民航局网站）;火车基本票价0.05861元每公里，对于加快票部分，普快十几本票价的20%，快速是40%，空调是基本票价的25%，硬卧价上中下分别是基本票价的110%,120%,130%,软卧上下是基本票价的175%，195%，再加30%的综合费用，动车票价为0.375元每公里。（数据来源:2000年11月实施的铁路旅客票价表数据显示，单位旅程三种基本交通工具的基本费用为飞机最贵，其次是长途

12、汽车，最便宜的是火车硬座。为了实现费用最省，我们采用全程均用火车（硬座）为交通工具的方案。基于以上资料我们做了如下假设; 1.火车票价与火车行驶里程成正比,由求解最短路径求得最省钱方案；2.城市间来回里程相同。5.1.3 模型求解在铁道部的网站上可以查询出题目所给定的城市之间的距离里程（如表5.1.1）旅游城市距离（单位：公里）（表5.1.1）根据上表的距离，并基于我们所提出的假设。在具体实现上，根据图论和组合最优化中的哈密顿问题，得出以下求解过程：设Vi表示第i个城市，i=1,2,3,4,5,6,7,8,9,10,11.与城市对应关系如下：V1V2V3V4V5V6V7V8V9V10V11徐州

13、常州青岛北京太原洛阳黄山汉口西安九江舟山决策函数记为Xk(i)=Pk(i,S),那么f10(V1,V2,V3,V4,V5,V6,V7,V8,V9,V10)表示从V1出发经过V2,V3,V4,V5,V6,V7,V8,V9,V10各一次，最后回到V1的最短路程，利用公式（5.1.1）:得到:f3（v1，v2，v3，v4）=mind12+f2（v2， v3， v4），d13+f2（v3； v2， v4），d14+f2（v4； v2， v3）f10（v1，v2，v3，v4，v5，v6，v7 ,v8，v9，v10，）=mind12+f9（v2， v3， v4, v5，v6, v7,v8, v9 ,v10

14、 ），d13+f9（v3, v2， v4, v5，v6， v7 v 8,v9， v10），d19+f9（v9； v2， v3, v4， v5, v6， v7, v8，v10）先从最后一个阶段求解。 f0（v2， ）=d21f0（v3， ）=d31 f0（v4， ）=d41 以上分别从v2，v3，v4，v5，v6，v7 ,v8，v9，v10，直接到v1距离。f1（v2， v3）=d23+ f0（v3， ）f1（v2， v4）=d24+ f0（v4， ）f1（v3， v2）=d32+ f0（v2， ）f1（v3， v4）=d34+ f0（v4， ）f1（v4， v2）=d42+ f0（v2， ）

15、f1（v4， v3）=d43+ f0（v3， ） 进一步求f2（v2， v3， v4）=min d23+f1（v3， v4），d24+f1（v4， v3）f2（v3， v4， v2）=min d32+f1（v2， v4），d34+f1（v4， v2）f2（v4， v2， v3）=min d42+f1（v2， v3），d43+f1（v3， v2）最后求f10（v1，v2，v3，v4，v5，v6，v7 ,v8，v9，v10，）=mind12+f9（v2， v3， v4, v5，v6, v7,v8, v9 ,v10 ），d13+f9（v3, v2， v4, v5，v6， v7 v 8,v9， v10

16、），d19+f9（v9； v2， v3, v4， v5, v6， v7, v8，v10）得出最短路长，再来求最短路程，运用以上思想和数据，辅以lingo进行运算，编程如下：MODEL:SETS:CITY/1.11/:U;LINK(CITY,CITY):DIST,X;ENDSETSDATA:DIST=048471281484847371956486062211004840119512881332956506655134413661671211950888922962154315771349139418008141288888050881215331196120013141910848133292

17、250807921530109365113891848473956962812792011036403879641442719506154315331530110307511500604705564655157711961093640751010273281080860134413491200651387150010270110217206221361394131413899646043281102090511006161800191018481442705108017209050ENDDATAN=SIZE(CITY);MIN=SUM(LINK:DIST*X);FOR(CITY(K):SUM(

18、CITY(I):X(I,K)=1;);FOR(CITY(K):SUM(CITY(J):X(K,J)=1;);FOR(CITY(K):FOR(CITY(J)|J#GT#1#AND#K#GT#1:U(J)-U(K)+N*X(J,K)青岛-北京-太原-西安-洛阳-九江-常州-舟山-黄山-徐州。通过对中国铁路时刻表的查询，得出：推荐方案为: 徐州-青岛-北京-太原-西安-洛阳-九江-常州-舟山-黄山-徐州.由此计算出总共消费为：2689元如果时间不限，游客将十个景点全游览完，满足旅游费用最少，旅游行程表如下：游客旅游路线图字母顺序既是旅游顺序如下：5.2 问题二模型蚁群算法模型，TSP模型。5.2.1

19、 模型分析问题二需要确定在费用不限的情况下,游客要想把十个景点全浏览完，至少需要的旅行时间。这个问题可以以运筹学有关最优化和图论的相关知识为基础，建立基于蚁群模型为基础的优化模型。旅行的总耗时T=乘坐旅行工具所耗费时间T0+在旅游景点停留所花费时间TP+等待旅游景点开放所花费时间TW1+等待列车所花费时间TW2 式5.2.1在相互关联、相互制约的限制因素中，乘坐旅行工具所耗费时间TO，及在旅游景点停留所花费时间TP比较易于控制，基于我们所做出的假设，所以应从乘坐旅行工具所耗费时间TO尽可能短着手，以TO为自变量建立最优化模型。一般来说，此类问题可以表述为：minf(x)|XS其中，f为目标函数

20、，S为可行解集合。注意，可行解的数目必须是有限多个。显然，是可以通过枚举法求解此类问题。但在最坏的情况下，这类问题的复杂度是指数级的，在限定的时间内不能完成，因此，另辟蹊径，借助有基于蚁群的MATLAB算法求解。m表示算法中蚂蚁的数量，d（i，j=1,2,3，n）表示边（i，j）之间的距离(此处表示两城市之间乘坐飞机所需的近似最短时间)，（参见表4.2.1），n为城市个数，表示t时刻在（i，j）上残留的信息素量，初始时刻各边信息素量相等。蚂蚁k在t时刻由城市i转移到城市j的概率为 p （1）式中：为先验知识或能见度，针对具体问题根据启发式规则而定；为边上残留信息的重要程度；为启发信息的重要程度

21、；为蚂蚁的禁忌表即蚂蚁所走过的城市集。随着时间的推移，以前蚂蚁留下的信息逐渐消逝，用参数表示信息素的挥发率，当蚂蚁完成1次循环后，个路径上的信息量根据下列公式作调整 （2） （3） （4）式中：表示更新后边上的信息素量；表示更新前边上的信息素量；表示第只蚂蚁本次循环中留在边上的信息素量；表示本次循环中边上的信息量增量；为常数；表示第只蚂蚁在本次循环中所走过的路径长度。当周游次数达到设定值是算法结束。旅行时间最小表表4.2.1注：为了使实验数据更加合理，选择航班时刻表中的中位数作为去往各地的最短时间。5.2.2 模型求解 在利用蚁群算法进行旅游模型的计算式，我们利用了MATLAB软件。我们利用M

22、ATLAB进行编程，运用size函数，zeros函数等一些MATLAB常用函数，对蚁群算法进行编程实现。其中 c表示 n个城市的坐标，n2的矩阵；NC_max 最大迭代次数；m 蚂蚁个数；Alpha 表征信息素重要程度的参数；Beta 表征启发式因子重要程度的参数； Rho 信息素蒸发系数；Q 信息素增加强度系数；R_best 各代最佳路线； L_best 各代最佳路线的长度； 编写ACATSP(c,NC_max,m,Alpha,Beta,Rho,Q)函数，由蚁群算法的原理分四部分处理：m只蚂蚁按概率函数选择下一座城市，完成各自的周游 ；计算待选城市的概率分布；记录本次迭代最佳路线；更新信息素

23、。利用MATLAB软件编程程序（部分）如下：clear all close all clc m=31; C=1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556;3238 1229;4196 1004; 4312 790;4386 570;3007 1970;2562 1756;2788 1491;2381 1676;1332 695;3715 1678; 3918 2179;4061 2370;3780 2212;3676 2578;4029 2838;4263 2931;3429 1908;3507 2367; 3394 2

24、643;3439 3201;2935 3240;3140 3550;2545 2357;2778 2826;2370 2975;%城市的坐标矩阵Nc_max=200; alpha=1; beta=5; rho=0.5; Q=100; n=size(C,1);%表示TSP问题的规模，亦即城市的数量D=ones(n,n);%表示城市完全地图的赋权邻接矩阵，记录城市之间的距离for i=1:n for j=1:n if ij D(i,j)=sqrt(C(i,1)-C(j,1)2+(C(i,2)-C(j,2)2); end D(j,i)=D(i,j); endendeta=1./D; pheromon

25、e=ones(n,n); tabu_list=zeros(m,n); Nc=0;%循环次数计数器routh_best=zeros(Nc_max,n);%各次循环的最短路径length_best=ones(Nc_max,1);%各次循环最短路径的长度length_average=ones(Nc_max,1);%各次循环所有路径的平均长度while NcNc_max rand_position=; for i=1:ceil(m/n) rand_position=rand_position,randperm(n); end for j=2:n for i=1:m city_visited=tabu_

26、list(i,1:(j-1);%已访问的城市 city_remained=zeros(1,(n-j+1);%待访问的城市 probability=city_remained;%待访问城市的访问概率 cr=1; for k=1:n%for循环用于求待访问的城市。比如如果城市个数是5，而已访问的城市city_visited=2 4,则经过此for循环后city_remanied=1 3 5 if length(find(city_visited=k)=0 city_remained(cr)=k; cr=cr+1; end end 然后设置初始量m=11;Alpha=1;Beta=5;Rho=0.5

27、;NC_max=200;Q=100;得到的结果是shortest_path=8 5 9 2 4 1 6 11 10 7 3旅游的线路图Figure of length_best and ength_averageFigure of shortest path由图可以看出来旅游路线是一个闭合性的路线，不管从哪里起点，都是这样一条最短路线。而且从收敛曲线上可以看出比较平稳，没有出现局部最优解。由对式5.2.1的分析可知，在寻找花费最短时间的路径中，统筹考虑各个因素，进而寻找出可行度高的最省事旅游方案。注：费用单位（元），时间单位（小时）。通过对表的分析可知，旅游最短时间为6天零十个小时45分。5.

28、3 问题三模型：Dijkstra算法模型, 最短路径模型5.3.1 模型分析问题三需要确定在2000元旅游费用的限制条件下，最多能够游览多少景点。从对问题一及问题二的求解过程中可知，乘坐单次单程火车返回徐州所花费的费用FO基本相同，大致都可以为100元，那么可以把这个问题构建为单源点下的最短路径模型。即有11个城市，编号为1、211，每个城市之间的路径长度保存在二位数组a中，如aij表示从城市i与城市j的旅行所需的全部费用。令SUM=(ij)+F0式（5.3.1）应该求得满足SUM=2000元的情况下， j取值个数的最大值。针对这一问题，我们应用图论中的Dijkstra算法求解，对于一个含有1

29、1个顶点的完全图，从某一个顶点Vi到其余顶点Vj的最短路径。设图G用邻接矩阵的方式存储在GA中，GAi,j=maxint表示Vi，Vj是不关联的，否则为权值（大于0的实数）。设集合S用来保存已求得最短路径的终点序号，初始时S=Vi表示只有源点，以后每求出一个终点Vj，就把它加入到集合中并作为新考虑的中间顶点。设数组dist1.n用来存储当前求得的最短路径，并不断检查这些最短路径是否满足式（3.2.1）。执行时，先从源点以外的顶点（即待求出最短路径的终点）所对应的dist数组元素中，找出其值最小的元素（假设为distm），该元素值就是从源点Vi到终点Vm的最短路径长度，对应的pathm中的顶点或

30、边的序列即为最短路径。接着把Vm并入集合S中，然后以Vm作为新考虑的中间顶点，即可求得更短的路径，则用它代替distj，同时把Vj或边（Vm，Vj）并入到pathj中。重复以上过程n-2次，即可在dist数组中得到从源点到其余各终点的最段路径长度，对应的path数组中保存着相应的最段路径。5.3.2 模型假设基于以上分析作如下假设： 1一个城市中市内交通工具为公交，5元标准。 2.lingo程序中城市个数N近似看作游览了N天，去除其他费用400，得出上限值。5.3.3 模型求解。在利用Dijkstra算法进行最短连通图模型的计算，可以借助LINGO软件。利用LINGO进行编程，对该问题进行编程

31、实现。针对本问题，我们做出从城市i到城市j旅行所需的全部费用。如表（5.3.2）表（5.3.2）利用上述数据，LINGO程序如下：MODEL:SETS: CITY/1.11/:level,pay,y; Link(CITY,CITY):x,cost;ENDSETSDATA:pay= 0 160 90 45409080230180200120;cost=0627094106349939558715262015014016512573105165679570150011612012518216816517021094140116070531821501501453541061651207009416

32、710345146203341251259494011887286217199731821821671180641394591391051681501038764013751103551651651504528139137083216876717014514662455183011615295210354203171911032161160ENDDATAMAX=SUM(CITY:y);SUM(Link(i,j)|i #ne# j: cost(i,j)*x(i,j)+SUM(CITY:pay*y)=level(i)+x(i,j)-(n-2)*(1-x(i,j)+(n-3)*x(j,i); );)

33、;FOR(CITY(i)|i #gt# 1: level(i)=1+(n-2)*x(i,1););ENDLocal optimal solution found. Objective value: 8.000000 Objective bound: 8.000000 Infeasibilities: 0.000000 Extended solver steps: 136 Total solver iterations: 42429 Variable Value Reduced Cost N 8.000000 0.000000X( 1, 3) 1.000000 0.000000X( 3, 4)

34、1.000000 0.000000X( 4, 5) 1.000000 0.000000X( 5, 6) 1.000000 0.000000X( 6, 9) 1.000000 0.000000X( 7, 1) 1.000000 0.000000X( 8, 7) 1.000000 0.000000X( 9, 8) 1.000000 0.000000注：运行结果仅列出有用的那部分数据。所以路径为：V1-V3-V4-V5-V6-V9-V8-V7-V1。由结果可知该旅客的旅游路线应为：徐州-青岛-北京-太原-洛阳-西安-武汉-黄山-徐州下面给出满足要求的旅游方案。如表（5.3.2附）游客的旅游路线字母顺

35、序既是旅游顺序：5.4 问题四模型：层次分析法模型5.4.1 模型分析问题四需要确定在规定的时间限制条件下，最多能够游览多少景点。通过对第二问的分析，很明显可以看出，在五天的时间内，不可能把全部的旅游景点都游玩一边。因此，可以借助于层次分析法的思想，将此问题分为两个步骤来考虑。首先，找出在五天内所能够游览的景点，；其次，选择最优的旅游路线。5.4.2 由以上思想作如下假设： 1.五天内可利用与旅游时间小于2400分钟。5.4.2 模型求解针对本问题，结合上述的模型分析，要先从十个景点中，选择出可以游览的城市。在此，借助于LINGO程序。程序如下：MODEL:SETS: CITY/1.11/:l

36、evel,pay,y; Link(CITY,CITY):x,cost;ENDSETSDATA:pay= 0 240 360 180180 180420 120 120420 360;cost=0,280,250,70,310,195,248,225,297,250,180290,0,240,105 ,1078, 255,170,270,110,180,210240,944,0,50,697,245,180,115,115,225,24570,130,80,0,60,95,120,130,110,135,130240,1155,669,65,0,225,240,943,70,245,265210

37、,275,225,80,225,0,220,210,240,200,190170,240,160,120,220,230,0,195,110,135,225230,260,100,115,80,220,240,0,75,155,210255,115,100,100,110,230,100,70,0,240,220255,190,210,130,245,200,155,160,240,0,145180,265,250,300,300,195,200,230,230,180,0;ENDDATAMAX=SUM(CITY:y);SUM(Link(i,j)|i #ne# j: cost(i,j)*x(i,j)+SUM(CITY:pay*y)=level(i)+x(i,j)-(n-2)*(1-x(i,j)+(n-3)*x(j,i); ););FOR(CITY(i)|i #gt# 1: level(i)=1+(n-2)*x(i,1););ENDLocal optimal solution found. Objective value: