环球旅行的路线设计

1环球旅行的路线设计【摘要】本设计要解决的是合理给出能游览六大洲的最佳路线选择问题，即给出一条经济且省时的路线。在处理此问题之前，联系实际，对影响线路选择的因素进行筛选，最终确定了以下三个影响较大的因素：第一是换乘次数；第二是行程时间；第三是行程费用。依据各因素对路线选择的影响程度,我们按不同的权重对它们进行考虑。从实际情况分析，人们比较倾向于多种途径的旅游方式，因此每个站点的转乘给出较多权重。为了解决换乘次数最少，行程时间相对较短、行程费用相对较少的问题，经过尝试与探索，我们采用了现代分析的方法，对环球旅行相邻两城市、相邻两洲进行分类讨论，归纳出直达，换乘一次，换乘两次的情况（三次以上的情形可以类推），并通过Matlab编制程序，给出了任意两站点间的最佳行程路线以及换车的地点，最后还提出了进一步的意见和建议。关键词：现代分析换乘次数行程时间行程费用2一、问题的重述喜欢旅游的人越来越多，而环球旅游更是很多人的梦想。首先环球旅游的概念应该是经过每个洲，而每个洲在典型的3个代表城市停留3天；另外，丰富的旅游路线应该选择不同的交通工具，包括飞机，轮船和汽车；如果能够去过北极和南极，环球旅游就更加完美；当然旅游者最后要回到自己的出发地。如果你有时间和金钱，身体又足够强壮，你能设计一条环球旅游的路线吗？七大洲典型城市和地区亚洲：北京东京曼谷北美洲：渥太华洛杉矶阿拉斯加大洋洲：悉尼苏瓦奥克兰欧洲：莫斯科斯德哥尔摩日内瓦非洲：开普敦喀土穆南极洲：南极南美洲：利马里约热内卢圣地亚哥二、模型的假设1.假设游客没有特别喜好，只根据行程和价格选择交通工具和旅游地点；2.假设乘车没有附加条件和意外，并且换乘时间算在旅行时间内，不另加；3.假设每一个城市都有飞机场、汽车站，并且靠海的都可以坐船；4.假设相邻站点间平均行驶时间一定；5.假设不出现车辆故障和交通事故；6.假设车辆、航班、船次都准备到达，不考虑中途等待时间；7.假设没有护照费用、导游费用、经济舱头等舱等个人花销。三、符号的说明符号表示意义iLA第i条包含初始站点的线路，1,2,,imjLB第j条包含目标站点的线路，1,2,,jskLC第k条中间线路，1,2,,kwilaiLA上的第l个站点，1,2,,lmjrbjLB上的第r个站点，1,2,,rtkuckLC上的第u个站点，1,2,,uvix在第i段线路上坐飞机乘坐的路程3符号表示意义jy在第j段路上坐汽车的路程kr在第k段路上坐轮船的路程1z汽车换乘汽车的次数2z飞机换乘汽车的次数3z轮船换乘汽车的次数4z汽车换乘的次数四、问题的分析、模型的建立及求解4.1问题4.1.1问题的分析本题主要在三种不同情况下，研究任意两站点之间的线路选择问题。联系生活实际，旅行主要考虑的是在最短的时间内可以花最少的钱来游览尽可能多的景点，除本题给出的18个基本景点城市外，其他的景点都是处于换乘方便并且便宜的情况。题目要求设计任意两站点之间线路选择问题的数学模型与算法。对于附录中的图形进行处理后，以文本文件形式导入Matlab中，找到了站点与站点之间的关系。进一步发现表明无论试图产生邻接矩阵或边权矩阵因数据太庞大而可行性极低，其运行时间长达50分钟，故考虑按题目给的路线来建立站点矩阵并对此矩阵进行处理后能够清晰有效地应用此矩阵。4.1.2模型的建立及求解模型一设f为乘坐公交线路的费用函数：飞机：0.75元/公里轮船：0.22元/公里汽车：.038元/公里F单位计价×路程总时间函数：nkknjjniitttT000)180(n（1）总费用函数：475.0F)180(22.038.0000nzyxnkknjjnii（2）其中ix表示乘客在公交线路iL上乘坐的站数；1z表示公汽换乘公汽的次数。目标：找出任意给定的两站点的乘车线路，使T和F相对最小。算法思路：由于人们的对换乘车次数尽量少的偏好程度总是大于对花费时间和金钱相对少的偏好程度，我们将优先考虑换乘车次数尽量少，然后再考虑花费时间相对短、花费金钱相对少，对得出的所有结果中进行筛选。换乘次数的大概思路及步骤如下：将所有包含初始站点0ila的线路12,,,mLALALA建成一个集合S，01ln，1,2,,im，所有包含目标站点0jrb的线路12,,,sLBLBLB建成一个集合G，01rt，1,2,,js。12,,,mSLALALA，12,,,sGLBLBLB，12iiiinLAaaa，1,2,,im，12jjjjtLBbbb，1,2,,js。1、直达的线路。当SG时，存在iLA、jLB，1im，1js，使得ijLALB，即iLA、jLB为同一线路。此线路既包含初始站点0ila又包含目标站点0jrb。若00lr，那么，此线路为所求直达线路。若00lr，或者当SG时，考虑换乘一次的线路。2、换乘一次的线路。当有iLA和jLB相交时，存在iLA、jLB，1im，1js，有iliaLA及jrjbLB，1ln，1rt。使得iljrab，即ila、jrb为同一站点。若0lln，01rr，那么，从初始站点0ila乘坐线路iLA，行驶至站点ila，即在站点jrb，换乘线路jLB至目标站点0jrb。即00ijrjjrililaabbLALB若不满足0lln，01rr，或者，当无任何iLA和jLB相交时，考虑换乘5两次的线路。3、换乘两次的线路。记12,,,wLCLCLC，12kkkkvLCccc，1,2,,kw，有kLCS，kLCG，1,2,,kw，且满足kLC与iLA、jLB都相交时，即线路kLC既不包含初始站点0ila又不包含目标站点0jrb，01ln，01rt。但是存在1kukcLC及iliaLA，使得1kuilca，存在2kukcLC及jrjbLB，使得2kujrcb，即1kuc、ila为同一站点，且2kuc、jrb为同一站点。1kw，1im，1js，11uv，21uv，1ln，1rt。若0lln，121uuv，01rr，那么，从初始站点0ila乘坐iLA线路，行驶至站点ila，即在站点1kuc，换乘kLC线路至站点2kuc，即在站点jrb，换乘jLB线路至目标站点0jrb。即0012ijrjjrililkukkuaLAacLCcbLBb若不满足0lln，121uuv，01rr，或者，当不存在满足条件的kLC时，说明需要换乘三次才能够到达目标站点。换乘三次以上的线路的模型建立原理是相同的，故我们不作详细介绍。通过考虑花费的时间或金钱，在得出的多条结果中进行筛选。4.1.3问题结果由于旅游站点的固定性、重叠性和交通工具可选择性,使得出行线路选择行为具有相当的复杂性。由一般路径选择特性可知,人们总是根据个人偏好选择出行路线(或希望出行时间最少,或希望换乘次数最少,或希望出行费用最低),可称之为最短路因素。同时,由于公交网络的复杂性,使得最短路判断出现差异,而个人选择行为带有一定的随机性,所以多路径选择较为符合游客的行为特点。另外一个方面，当游客要进行一次换乘时，他会考虑到时间或者费用等问题，，所以在这种情况下我们只考虑途经站点最少的二次转乘路线。基于以上考虑,我们对每道小题都给出了多种乘车路线，以供乘客根据自己的需要选择。（程序见附录8.1、附录8.2、附录8.3）（1）北京S001→东京S0026线路（条）初始站错误!未找到引用源。错误!未找到引用源。线路途经站数（换乘站汽车线路途经站数换乘站轮船线路途经站数)目标站时间（小时）金钱（元）1S001错误!未找到引用源。飞机S0023.514002S001错误!未找到引用源。5h汽车上海S01172h轮船S002776183S001错误!未找到引用源。8h汽车韩国S01238h轮船S00246605评价说明：经Matlab运行程序，得出了3条优化线路。其中，1、2条换乘一次，3、4、5条换乘两次，3、4、5条线路比1、2条线路多换乘一次，所花的金钱相同，但是节省了7分钟时间。乘客根据自己的需要进行选择。（2）S1557→S0481线路（条）初始站错误!未找到引用源。错误!未找到引用源。公汽线路途经站数换乘站公汽线路途经站数(换乘站公汽线路途经站数)目标站时间（分）金钱（元）1S1错误!未找到引用源。557错误!未找到引用源。36312L下行S191941717L上行S24242545L上行S048111232S1错误!未找到引用源。557错误!未找到引用源。36312L下行S191941717L上行S24244475L上行S048111233S1错误!未找到引用源。557错误!未找到引用源。36312L下行S191941717L上行S24244605LS048111234S1错误!未找到引用源。557错误!未找到引用源。36312L下行S191941717L上行S24245165L上行S0481112375S1错误!未找到引用源。557错误!未找到引用源。36312L下行S191941717L上行S24243125L下行S048111236S1错误!未找到引用源。557错误!未找到引用源。08412L下行S191941717L上行S24242545L上行S048111237S1错误!未找到引用源。557错误!未找到引用源。08412L下行S191941717L上行S24244475L上行S048111238S1错误!未找到引用源。557错误!未找到引用源。08412L下行S191941717L上行S24245165L上行S048111239S1错误!未找到引用源。557错误!未找到引用源。08412L下行S191941717L上行S24243215L下行S04811123评价说明：经Matlab运行程序，得出了9条优化线路。乘坐这9条线路所花费的时间和金钱都相同，且均需要换乘两次。不存在换乘一次的线路。乘客可以选择任意一条线路。（3）S0971→S0485线路初始站错误!未找到引用源。错误!未找到引用源。公汽线路途经站数换乘站公汽线路途经站数(换乘站公汽线路途经站数)目标站时间（分）金钱（元）1S0971错误!未找到引用源。01320L下行S218441721L下行S048512832S0971错误!未找到引用源。01322L下行S099241720L下行S048513133S0971错误!未找到引用源。01315L下行S34050071L上行S251541722L下行S048594384S0971错误!未找到引用源。1198L上行S152000817L下行S226546913L上行S04859435S0971错误!未找到引用源。1198L上行S152000819L下行S265446911L上行S04859436S0971错误!未找到引用源。1198L上行S152000820L下行S172946910L上行S04859437S0971错误!未找到引用源。1198L上行S152000821L下行S3