环球旅行的路线设计 20页

环球旅行的路线设计【摘要】本设计要解决的是合理给出能游览六大洲的最佳路线选择问题，即给出一条经济且省时的路线。在处理此问题之前，联系实际，对影响线路选择的因素进行筛选，最终确定了以下三个影响较大的因素：第一是换乘次数；第二是行程时间；第三是行程费用。依据各因素对路线选择的影响程度,我们按不同的权重对它们进行考虑。从实际情况分析，人们比较倾向于多种途径的旅游方式，因此每个站点的转乘给出较多权重。为了解决换乘次数最少，行程时间相对较短、行程费用相对较少的问题，经过尝试与探索，我们采用了现代分析的方法，对环球旅行相邻两城市、相邻两洲进行分类讨论，归纳出直达，换乘一次，换乘两次的情况（三次以上的情形可以类推），并通过Matlab编制程序，给出了任意两站点间的最佳行程路线以及换车的地点，最后还提出了进一步的意见和建议。关键词：现代分析换乘次数行程时间行程费用20 一、问题的重述喜欢旅游的人越来越多，而环球旅游更是很多人的梦想。首先环球旅游的概念应该是经过每个洲，而每个洲在典型的3个代表城市停留3天；另外，丰富的旅游路线应该选择不同的交通工具，包括飞机，轮船和汽车；如果能够去过北极和南极，环球旅游就更加完美；当然旅游者最后要回到自己的出发地。如果你有时间和金钱，身体又足够强壮，你能设计一条环球旅游的路线吗？七大洲典型城市和地区亚洲：北京东京曼谷北美洲：渥太华洛杉矶阿拉斯加大洋洲：悉尼苏瓦奥克兰欧洲：莫斯科斯德哥尔摩日内瓦非洲：开普敦喀土穆南极洲：南极南美洲：利马里约热内卢圣地亚哥二、模型的假设1.假设游客没有特别喜好，只根据行程和价格选择交通工具和旅游地点；2.假设乘车没有附加条件和意外，并且换乘时间算在旅行时间内，不另加；3.假设每一个城市都有飞机场、汽车站，并且靠海的都可以坐船；4.假设相邻站点间平均行驶时间一定；5.假设不出现车辆故障和交通事故；6.假设车辆、航班、船次都准备到达，不考虑中途等待时间；7.假设没有护照费用、导游费用、经济舱头等舱等个人花销。三、符号的说明符号表示意义第条包含初始站点的线路，第条包含目标站点的线路，第条中间线路，上的第个站点，上的第个站点，上的第个站点，在第段线路上坐飞机乘坐的路程20 在第j段路上坐汽车的路程在第k段路上坐轮船的路程汽车换乘汽车的次数飞机换乘汽车的次数轮船换乘汽车的次数汽车换乘的次数四、问题的分析、模型的建立及求解4.1问题4.1.1问题的分析本题主要在三种不同情况下，研究任意两站点之间的线路选择问题。联系生活实际，旅行主要考虑的是在最短的时间内可以花最少的钱来游览尽可能多的景点，除本题给出的18个基本景点城市外，其他的景点都是处于换乘方便并且便宜的情况。题目要求设计任意两站点之间线路选择问题的数学模型与算法。对于附录中的图形进行处理后，以文本文件形式导入Matlab中，找到了站点与站点之间的关系。进一步发现表明无论试图产生邻接矩阵或边权矩阵因数据太庞大而可行性极低，其运行时间长达50分钟，故考虑按题目给的路线来建立站点矩阵并对此矩阵进行处理后能够清晰有效地应用此矩阵。4.1.2模型的建立及求解模型一设为乘坐公交线路的费用函数：飞机：0.75元/公里轮船：0.22元/公里汽车：.038元/公里单位计价×路程总时间函数：（1）总费用函数：20 （2）其中表示乘客在公交线路上乘坐的站数；表示公汽换乘公汽的次数。目标：找出任意给定的两站点的乘车线路，使和相对最小。算法思路：由于人们的对换乘车次数尽量少的偏好程度总是大于对花费时间和金钱相对少的偏好程度，我们将优先考虑换乘车次数尽量少，然后再考虑花费时间相对短、花费金钱相对少，对得出的所有结果中进行筛选。换乘次数的大概思路及步骤如下：将所有包含初始站点的线路建成一个集合S，，，所有包含目标站点的线路建成一个集合G，，。，，，，，。1、直达的线路。当时，存在、，，，使得，即、为同一线路。此线路既包含初始站点又包含目标站点。若，那么，此线路为所求直达线路。若，或者当时，考虑换乘一次的线路。2、换乘一次的线路。当有和相交时，存在、，，，有及，，。使得，即、为同一站点。若，，那么，从初始站点乘坐线路，行驶至站点，即在站点，换乘线路至目标站点。即若不满足，，或者，当无任何和20 相交时，考虑换乘两次的线路。3、换乘两次的线路。记，，，有，，，且满足与、都相交时，即线路既不包含初始站点又不包含目标站点，，。但是存在及，使得，存在及，使得，即、为同一站点，且、为同一站点。，，，，，，。若，，，那么，从初始站点乘坐线路，行驶至站点，即在站点，换乘线路至站点，即在站点，换乘线路至目标站点。即若不满足，，，或者，当不存在满足条件的时，说明需要换乘三次才能够到达目标站点。换乘三次以上的线路的模型建立原理是相同的，故我们不作详细介绍。通过考虑花费的时间或金钱，在得出的多条结果中进行筛选。4.1.3问题结果由于旅游站点的固定性、重叠性和交通工具可选择性,使得出行线路选择行为具有相当的复杂性。由一般路径选择特性可知,人们总是根据个人偏好选择出行路线(或希望出行时间最少,或希望换乘次数最少,或希望出行费用最低),可称之为最短路因素。同时,由于公交网络的复杂性,使得最短路判断出现差异,而个人选择行为带有一定的随机性,所以多路径选择较为符合游客的行为特点。另外一个方面，当游客要进行一次换乘时，他会考虑到时间或者费用等问题，，所以在这种情况下我们只考虑途经站点最少的二次转乘路线。基于以上考虑,我们对每道小题都给出了多种乘车路线，以供乘客根据自己的需要选择。（程序见附录8.1、附录8.2、附录8.3）（1）北京S001→东京S00220 线路（条）初始站（换乘站换乘站)目标站时间（小时）金钱（元）1S001S0023.514002S001上海S011S002776183S001韩国S012S00246605评价说明：经Matlab运行程序，得出了3条优化线路。其中，1、2条换乘一次，3、4、5条换乘两次，3、4、5条线路比1、2条线路多换乘一次，所花的金钱相同，但是节省了7分钟时间。乘客根据自己的需要进行选择。（2）S1557→S0481线路（条）初始站换乘站(换乘站)目标站时间（分）金钱（元）1S1557S1919S2424S048111232S1557S1919S2424S048111233S1557S1919S2424S048111234S1557S1919S2424S048111235S1557S1919S2424S048111236S1557S1919S2424S048111237S1557S1919S2424S048111238S1557S1919S2424S048111239S1557S1919S2424S0481112320 评价说明：经Matlab运行程序，得出了9条优化线路。乘坐这9条线路所花费的时间和金钱都相同，且均需要换乘两次。不存在换乘一次的线路。乘客可以选择任意一条线路。（3）S0971→S0485线路初始站换乘站(换乘站)目标站时间（分）金钱（元）1S0971S2184S048512832S0971S0992S048513133S0971S3405S2515S04859434S0971S1520S2265S04859435S0971S1520S2654S04859436S0971S1520S1729S04859437S0971S1520S3766S04859438S0971S1520S2265S04859439S0971S1520S2265S0485943评价说明：经Matlab运行程序，得出了9条优化线路。其中，1条换乘一次，3~9条换乘两次，3~9条线路比1条线路多换乘一次，所花的金钱相同，但是节省了37分钟时间。乘客根据自己的需要进行选择。（4）S0008→S0073线路初始站换乘站(换乘站)目标站时间（分）金钱（元）1S0008S2083S00738322S0008S2263S00738323S0008S2683S00738324S0008S0400S007383220 5S0008S2559S00738336S0008S1383S2833S00738237S0008S1691S2833S00738238S0008S3766S2833S00738239S0008S1383S2833S007382310S0008S1383S2833S0073823评价说明：经Matlab运行程序，得出了10条优化线路。其中，1~5条换乘一次，所花费的时间相同，但是1~4条比5条节省了1元钱。6~10条换乘两次，所花的金钱比1~4条多1元，只节省了1分钟时间。所以建议乘客选择1~4条。（5）S0148→S0485线路初始站换乘站(换乘站)目标站时间（分）金钱（元）1S0148S0036S2210S048510632S0148S0036S3332S048510633S0148S0036S3351S04851063评价说明：经Matlab运行程序，得出了3条优化线路。乘坐这3条线路所花费的时间和金钱都相同，且均需要换乘两次。不存在换乘一次的线路。乘客可以选择任意一条线路。（6）S0087→S3676线路（条）初始站换乘站(换乘站)目标站时间（分）金钱（元）1S0087S3496S36766522S0087S1893S36767123S0087S0541S0236S367652320 4S0087S0541S2336S3676523评价说明：经Matlab运行程序，得出了4条优化线路。其中，1、2条换乘一次，所花费的金钱相同，但是1条比2条节省了6分钟。3、4条换乘两次，所花的金钱相同，且比1、2条多1元，但节省了时间。所以建议乘客选择1、3、4条。4.2问题二4.2.1问题二的分析已知相邻地铁站平均行驶时间(包括停站时间)：2.5分钟；地铁换乘地铁平均耗时：4分钟(其中步行时间2分钟)；地铁换乘公汽平均耗时：7分钟(其中步行时间4分钟)；公汽换乘地铁平均耗时：6分钟(其中步行时间4分钟)；地铁票价：3元（无论地铁线路间是否换乘）；其它的公汽时间信息与问题一相同。题目要求同时考虑公汽与地铁线路，设计任意两公汽站点之间线路选择问题的数学模型与算法。在此，我们考虑了总时间和总费用两个函数，讨论方法与一题类似，只是加入了地铁，分为乘坐地铁和完全不坐地铁两种。4.2.2模型的建立及求解模型二设，分别为乘坐公交和地铁线路的费用函数：总时间函数：（，）（3）总费用函数：（4）其中表示乘客在公交线路上乘坐的站数；表示乘客在一次地铁线路上乘坐的总站数；分别表示公汽换乘公汽，地铁换乘地铁，地铁换乘公汽，公汽换乘地铁的次数。目标：找出任意给定的两站点的乘车线路，使和相对最小。20 算法思路：由于假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘且无需支付地铁费，那么不妨把同一地铁站所对应的几个公汽站合并成一个站。地铁线路，。1、可以乘坐地铁的线路。（1）若初始站点和目标站点都在地铁线路或者上，那么，只乘坐地铁或者便可以直达。其中，若都在线路上，就选择经过站数最少的方向。若初始站点和目标站点分别在地铁线路和上，那么，需要进行一次地铁换乘地铁才能到达。（2）若只有初始站点或只有目标站点在地铁线路上，则需要换乘公汽才能到达目标站点。①初始站点，，目标站点且，。当有和地铁相交时，即存在，有，使得，。，。若，那么，从初始站点（记为）乘坐地铁线路，行驶至站点（记为），换乘公汽线路至目标站点。，。即（）（）其中，时需要地铁换乘地铁。若不满足，或者当没有这样的时，说明在地铁换乘公汽后，还需要进行公汽换乘公汽。由于这样的情况几乎不存在，故不作考虑。②目标站点，初始站点且，同理可得结论。（3）若初始站点和目标站点都不在地铁线路上，则先乘坐公汽，换乘地铁，再由地铁换乘公汽。地铁线路既和相交又和相交时，即地铁线路既不包含初始站点又不包含目标站点。但是存在、，，，有，使得，记为，20 ，使得，记为，，，，。若，，那么，从初始站点乘坐线路，行驶至站点（记为），换乘地铁线路至站点（记为），换乘线路至目标站点。即（）（）其中，时需要地铁换乘地铁。若不满足，，或者不存在、都与地铁线路相交，说明需要在地铁线路前或后进行公汽与公汽的换乘。由于这样的情况几乎不存在，故不作考虑。2、只乘坐公汽的线路。完全排除地铁线路，与解决问题一的方法相同。4.1.3问题二的结果（程序见附录8.4）（1）S3359→S1828应用Matlab编出的程序显示出没有在地铁站附近车站转站的的转站台，所以此时不坐地铁的结果完全和“问题一”中的第一小题的结果相同。因此在这种情况下，建议在这些站点乘客应当首先考虑坐公汽。具体情况请参照“问题一”的的结果。（2）S1557→S0481同（1）的结论。20 图1北京地铁图（3）S0971→S0485通过S0971的路线同时又能够到达地铁站的线路分别为：L160上行，L263下行，L119上行，L024下行，L119下行，L013上行，分别到达地铁的D01，D02，D26；另外一方面，与终点站S0485相连并能够到达地铁站的公交线路分别是L375上，L469下行，L051上行，L417下行，L395下行，分别到达地铁站的D21，D22和D20。可以乘坐地铁：线路（条）初始站换乘站(换乘站)目标站时间（分）金钱（元）1S0971（D26）（D21）S0485138.562S0971（D26）（D21）S0485138.563S0971（D26）（D21）S0485138.56只乘坐公汽：线路初始站换乘站(换乘站)目标站时间（分）金钱（元）1S0971S2184S0485128320 2S0971S0992S048513133S0971S3405S2515S04859434S0971S1520S2265S04859435S0971S1520S2654S04859436S0971S1520S1729S04859437S0971S1520S3766S04859438S0971S1520S2265S04859439S0971S1520S2265S0485943评价说明：经Matlab运行程序，得出了3条乘坐地铁的优化线路。但与乘坐公汽对比，如果要坐地铁，不仅需要换乘多次，还会花费大量时间。建议乘客乘坐公汽。（4）S0008→S0073同（1）的结论。（5）S0148→S0485可以乘坐地铁：线路（条）初始站换乘站(换乘站)目标站时间（分）金钱（元）1S0148S3045（D02）（D21）S048587.552S0148S3045（D02）（D21）S048587.553S0148S3045（D02）（D21）S048587.554S0148S3045（D02）（D21）87.5520 S0485只乘坐公汽：线路初始站换乘站(换乘站)目标站时间（分）金钱（元）1S0148S0036S2210S048510632S0148S0036S3332S048510633S0148S0036S3351S04851063评价说明：经Matlab运行程序，得出了4条乘坐地铁的优化线路。与乘坐公汽对比，节省的时间较多。乘客根据自己的需要进行选择。（6）S0087→S3676抽象出T1和T2的模型，如图1所示。由于S0087和S3676这两个站点都对应地铁站，又由2.2地铁T2线换乘公汽信息.txt，故把S0087合并到地铁站点D27，把S3676合并到地铁站点D36。又由图1所知，当乘客在S0087时，他有两种很快捷，方便的乘车路线到达S3676，即，。两条路线都只花3元钱，而第一条线路耗时25分钟，第二条只耗时20分钟。相比于“问题一”中的第六个小题，在花费均相等的前提下，建议乘客选乘地铁，因为这在很大程度上节约了时间，同时也免去了转车带来的麻烦。4.3问题三4.3.1问题三的分析已知所有站点间的步行时间，其余信息与问题二相同，题目要求建立任意两站点间路线选择问题的数学模型。问题三在问题二的基础上又增加了步行这种情况，在适当站点步行，可以节省交通费用而且不会消耗过多时间，比如某些乘客在一段分段计价线路上欲乘坐21或41个站点，则可以选择在第20站或第40站下车，步行一站即到达目的地，这样做可以节省1元。4.3.2模型的建立模型三设分别为乘坐公交和地铁线路的费用函数：20 根据实际情况，在地铁线路上不考虑步行。我们可以在初始站点、目标站点或换乘站点的附近考虑步行，即在任意公交线路,上最多下车一次。否则，若在某个,上下车步行两次，则在上需要多购买车票一次，同时消耗的时间更多，此做法既违反常理，又不经济实惠。设在线路，上步行的站数为，，相邻公汽站步行时间为，那么总时间函数：，（5）总费用函数：，（6）目标：找出任意给定的两站点的乘车线路，使和相对最小。五、模型的评价5.1模型的优点：1、型简单易懂，操作简单，涵盖了所有路线的选择情况。2、此模型的设计完全符合“乘公交，看奥运”的主题，解决了公交线路的选择问题，使公众的出行更加通畅便利。5.2模型的缺点：忽略了人流、车流拥挤的状况。六、模型的改进和推广6.1对于若干条从某一初始站点到目标站点的线路，我们可以设计一种带记忆功能的系统，即乘客选择某路径的次数越多，说明此路径是比较优的路径，为以后选择路径提供必要的信息。系统使用的时间越长，为乘客提供的信息越全面，越准确，系统也越智能化。这样就可以为乘客需求量最大的一条增加班次，以满足更多人的需要。6.220 在假设中提到，所有线路的开班、收班时间相同，但事实并非如此。那么可以在模型的设计中加入线路运行的时间元素，使乘客查询时只显示正在运行的线路。七、参考文献[1]姜启源，邢文训，谢金星,杨顶辉，大学数学实验，北京：清华大学出版社，2000[2]傅鹂，龚劬，刘琼荪，何中市编著,数学实验，北京:科学出版社，2000[3]王树禾，图论，北京：科学出版社，2004[4]苏金明等编，MATLAB工具箱应用八、附录8.1问题一的程序代码（直达的线路）x1=input("pleaseinputstartingstation:");y1=input("pleaseinputtheterminal:");[i1,j1]=find(a==x1);[i2,j2]=find(a==y1);[m,n]=size(i1);[p,q]=size(i2);r=0;fori=1:mforj=1:pifi1(i,n)==i2(j,q)%厉害呢！找出出发站和终点站在一条线路上的nv=find(x1==a(i1(i,n),:));nu=find(y1==a(i2(j,q),:));ifnv5000&mv(tp)<6000)tt=tt+1;mm(tt)=a(i1(p,1),1);breakendendenddisp("起点经过地铁的线路")disp(mm)ttt=0[i1,i2]=find(y1==a);t=size(i1,1);forp=1:tmv=a(i1(p,1),:);n=size(mv,2);fortp=1:nif(mv(tp)>5000&mv(tp)<6000)ttt=ttt+1;mmm(ttt)=a(i1(p,1),1);breakendendenddisp("终点经过地铁的线路")disp(mmm)20