《走遍全中国的最优路线问题.doc》由会员分享，可在线阅读，更多相关《走遍全中国的最优路线问题.doc（12页珍藏版）》请在三一办公上搜索。
1、走遍全中国的最优路线问题摘要：针对周先生旅游最短路线的设计，首先，将周先生的旅游视为生活享受游，其次，一个城市的经纬度为坐标，并运用Hopfeild神经网络算法求解出最短旅行路线，之后，参考网上订票的具体信息，并结合周先生的年龄问题，选取了空航、动车、快车卧铺三种较舒适的旅行方式，以经济性，省时省钱为指标进行建模分析，最后通过各部分加权比重进行综合评价，拟定出最佳订票方案，见下文。并且进行了算法的适当分析与模型的优化。关键词：经纬度、最短路线、订票方案、算法分析一：问题重述：周游先生退休后想到各地旅游。计划走遍全国的省会城市、直辖市、香港、澳门、台北。请你为他按下面要求制定出行方案：1按地理位
2、置（经纬度）设计最短路旅行方案；2如果2010年5月1日周先生从哈尔滨市出发，每个城市停留3天，可选择航空、铁路（快车卧铺或动车），设计最经济的旅行互联网上订票方案；3 要综合考虑省钱、省时又方便，设定你的评价准则，建立数学模型，修订你的方案；4对你的算法作复杂性、可行性及误差分析；5关于旅行商问题提出对你自己所采用的算法的理解及评价。二：基本假设：在旅途中旅游车的准时出发到达,且不考虑突发事件干扰车子的行程;在旅游的过程中,当天旅游目的地附近都有宾馆,且第一天的目的地就是第二天的出发点；在每个城市的吃饭、购物、在城市中观光景点等所需的费用费用视为相同；三：评价标准、基本符号、变量。【1】 根
3、据旅客要求，寻找按经纬度最短的旅行途径，故先将各省会、直辖市、特别行政区的经纬度列在下面表格中：城市名称经度纬度北京e11628n3954上海e12129n3114天津e11711n3909重庆e10632 n2932哈尔滨e12641 n4545长春e12519 n4352沈阳e12324 n4150呼和浩特e11148 n4049石家庄e11428n3802太原e11234 n3752济南e117 n3638郑州e11342 n3448西安e10854 n3416兰州e10349 n3603银川e10616 n3820西宁e10145 n3638乌鲁木齐e 8736 n4348合肥e117
4、18 n3151南京e11850 n3202杭州e12009n3014长沙e113 n2811南昌e11552n2841武汉e11421 n3037成都e10405 n3039贵阳e10642 n2635福州e11918 n2605台北e12131n2503广州e11315 n2308海口e11020n2002南宁e10820 n2248昆明e10241 n25拉萨e 9110 n2940香港e11410n2218澳门e113.5n22.2【2】 在以经纬度为基础上算出的行程最短路线上，进行网上订票，本题中，考虑到周先生年龄问题，又是退休后旅游，是以归为生活享受游，为了使其有精力地更长时间参观
5、景点，在乘车方式的选取上进行如下考虑：在不同的乘车方式上，若距离较远，可考虑空航、动车、快车卧铺三种方式；若为较短距离旅行可考虑动车、快车卧铺和硬座；在很短的距离可考虑快车硬座和公交车。而在相同的乘车方式上（例如：均为快车卧铺，应先考虑哪辆车次），考虑到票价、乘车所需时间均基本相同，是以优先考虑列车的起始和终止时刻，考虑到旅游的观光目的和精力问题，是以列出两个优先原则。第一优先原则：尽量晚上到站，可在当地宾馆休息一晚，次日即可旅游；第二优先原则：在不能满足第一优先原则的前提下，若为短途，则可考虑早出发早到原则；优先原则三：在有些情况下，某些列车的票价较低、乘车所需时间较短，是以可优先考虑。【3
6、】 根据体重提出的几个要素指标，现在归纳如下：1、乘车费用（即票费，用Y表示在各因素中所占权重）2、旅行中交通方便性（乘车方式，用B表示在各因素中所占权重）3、旅行时间（尽量使在景点停留时间长，乘车时间短，这是旅游本来的目的，符合旅客的要求，用T表示在各因素中所占权重），【4】 在评价模型的建立与求解过程中，各个因素的指标均选取模糊集为衡量标准，票价和乘车时间可按比例选取优、良、中、差四个等级；旅行方便程度可按乘车方式飞机、动车、快车卧铺划分为好、中、差三个等级；最后进行整合，进行权重计算。四：模型建立路线设计：按经纬度距离最短的行程路线模型假设：运用Hopfeild神经网络算法来解决旅行路线
7、最佳问题。首先将问题映射到Hopfeild网络上，故将33个城市视为神经元，任何一个城市在最终路径上的访问次序可用一个N维向量来表示，因此每个城市需要33个神经元表示，我们不妨规定第i个城市为Ai（x、y），xy表示城市的经纬度，如果访问从第i个城市开始，则第i个神经元（城市）视为1，其余神经元视为0，为了表示所有城市，可以用个33*33的矩阵表示，必须保证每行每列只有一个1，这样的矩阵称为换位矩阵。构造函数，这里选取的是能量函数，其最小值对应最短路径。现借鉴Hopfield模拟结果得到最短旅行路线。最短旅行路线为： Hopfield 模拟结果起点：哈尔滨长春沈阳天津济南石家庄太原西安郑州合肥
8、南京上海杭州台北福州南昌武汉长沙广州香港澳门海口南宁贵阳昆明重庆成都拉萨乌鲁木齐西宁兰州银川呼和浩特北京哈尔滨四、互联网上订票方案基于上述路线，现在以互联网上订票的经济性为基础，对航空、铁路（快车卧铺或动车）旅行方式进行选取。查阅每两地间的列车、飞机时刻表，现归纳如下：出发点终点快车卧铺、动车、飞机车次出发到站时刻票价哈尔滨-长春T15808：45-11：1087硬卧D288：58-10：4876软座长春-沈阳T530206：12-09:0793硬卧D2617：26-19：31111软座沈阳-天津130209：54-19：36160硬卧D19806：32-11：08254软座3U886213：
9、05-14：25620天津-济南103606：10-11：0092硬卧D16412：17-14：51133软座BK282107：00-08：50910济南-石家庄K37209:12-14:1793硬卧石家庄-太原K86805:35-07:2884硬卧太原-西安GS758118:00-19:05404西安-郑州108607：41-14：29122软卧G200208:03-11:05390软座郑州-合肥219422：22-06：39138软卧合肥-上海K836512:48-20:21116硬卧D547707:58-11:15170软座MU546808:45-09:45133上海-杭州K837106
10、：04-08：2175硬卧D552306：10-07：4270软座杭州-台北无列车或者飞机台北-福州福州-南昌K66608:04-18:02153硬卧3U896013:00-14:10403南昌-武汉无直达列车、无空航，只能转站武汉-长沙G102107:30-08:53175硬座长沙-广州CZ337508:00-08:55217G600108:00-10:46333硬座T25306：24-13：43172硬卧广州-香港无列车，无飞机，可坐公交车香港-澳门澳门-海口无直达列车或者飞机海口-南宁GS652112:30-13:20573南宁-贵阳K14212:57-00:07201硬卧CZ32750
11、8：10-09：10428贵阳-昆明K47105:00-17:29164硬卧MU588609:50-10:50392昆明-重庆K16812：20-07：28246硬卧CZ695015:10-16:20467重庆-成都K57705:03-09:0093硬卧D510108：00-09：5998硬座成都-拉萨T2220：59-16：40557硬卧CA40707：40-09：451364拉萨-乌鲁木齐无直达列车或者飞机乌鲁木齐-西宁CZ688109:15-11:201075西宁-兰州K91808:00-10:1379硬卧兰州-银川263609：56-18：30115软卧银川-呼和浩特K88612：50
12、-21：38161软卧呼和浩特-北京K4409：18-19：37244软卧CA110607：00-07：55327北京-哈尔滨T15706：45-17：11411软卧D2507:15-15:19464软座经过网上订票发现，我们理想中的乘车路线在很多方面是行不通的，有些城市之间是没有列车和飞机通过的，需要中转站进行倒车，这是很不方便的，并且，有些城市与其他城市之间的交通是非常少的，例如台北（最佳去台北的路线是从香港出发去台北，一般包机会在香港转机，或者依靠香港中国旅行社进入台湾旅游）。因此需要我们进行模型优化，并且，将其中的最佳订票方式确定出来。五：模型优化针对上述某些城市之间无列车直达或飞机直
13、航，甚至某些城市交通与外界很闭塞。考虑到省时、省钱、方便的原则，是以我们要对路线进行修改，根据网上订票的可能性，我们整合出如下订票方案：出发点终点快车卧铺、动车、飞机车次出发到站时刻票价哈尔滨-长春T15808：45-11：1087硬卧D288：58-10：4876软座长春-沈阳T530206：12-09:0793硬卧D2617：26-19：31111软座沈阳-天津130209：54-19：36160硬卧D19806：32-11：08254软座3U886213：05-14：25620天津-济南103606：10-11：0092硬卧D16412：17-14：51133软座BK282107：00-
14、08：50910济南-石家庄K37209:12-14:1793硬卧D552306：10-07：4258硬座石家庄-太原K86805:35-07:2884硬卧太原-西安GS758118:00-19:05404西安-郑州108607：41-14：29122软卧G200208:03-11:05390软座郑州-合肥219422：22-06：39138软卧合肥-上海K836512:48-20:21116硬卧D547707:58-11:15170软座MU546808:45-09:45133上海-杭州K837106：04-08：2175硬卧D552306：10-07：4270软座杭州-福州D31707:06
15、-11:20183硬座MF86508:10-09:10409福州-南昌K66608:04-18:02153硬卧3U896013:00-14:10403南昌-武汉无直达列车、无空航，但可在九江转站，方便省事可行武汉-长沙G102107:30-08:53175硬座长沙-广州CZ337508:00-08:55217G600108:00-10:46333硬座T25306：24-13：43172硬卧广州-香港坐客车即可香港-台北可选择包机直航或选取香港旅行社旅游台北-香港可选择包机直航或选取香港旅行社旅游香港-澳门坐客车即可澳门-海口无直达列车或者飞机，可先乘车后渡轮海口-南宁GS652112:30-1
16、3:20573南宁-贵阳K14212:57-00:07201硬卧CZ327508：10-09：10428贵阳-昆明K47105:00-17:29164硬卧MU588609:50-10:50392昆明-重庆K16812：20-07：28246硬卧CZ695015:10-16:20467重庆-成都K57705:03-09:0093硬卧D510108：00-09：5998硬座成都-拉萨T2220：59-16：40557硬卧CA40707：40-09：451364拉萨-西宁K91808：00-07：40600软卧西宁-乌鲁木齐CZ362916:15-18:351075乌鲁木齐-西宁CZ688109:1
17、5-11:201075西宁-兰州K91808:00-10:1379硬卧兰州-银川263609：56-18：30115软卧银川-呼和浩特K88612：50-21：38161软卧呼和浩特-北京K4409：18-19：37244软卧CA110607：00-07：55327北京-哈尔滨T15706：45-17：11411软卧D2507:15-15:19464软座针对此订票方案，我们将旅行路线优化为：起点：哈尔滨长春沈阳天津济南石家庄太原西安郑州合肥南京上海杭州福州南昌武汉长沙广州香港台北澳门海口南宁贵阳昆明重庆成都拉萨西宁乌鲁木齐西宁兰州银川呼和浩特北京哈尔滨六：模型求解与算法的分析我们充分考虑省时、
18、省钱、方便三方面的指标，对上表的数据进行归一化处理,针对每两个城市之间的两种或者三种乘车方式，为选出适当的方式，我们需要比较，因此规定如下算法：因为票价、方便程度度三者之间难以直接比较，是以我们以票价与票价进行比较，同因素之间的比较比较精准，归一化公式如下：Y1=（Y1+Y2+Y3）/3;Y1=(Y1+Y2)/2。而方便程度我们考虑乘车、座位形式的方便性，为简化计算难度同时考虑到实际情况应将其分为比较集中且相差不大的几组系数如下：飞机座位为0.4，快车软卧为0.5，快车硬卧为0.6，动车软座为0.7，动车硬座为0.8。所需时间我们考虑乘车时间的长度，而T=h/10,h代表所需时间的小时数。最后
19、权重的计算，为比较方便，我们将Y、B、T在权重中所占分量理解为如下关系：W=在此处键入公式。得到如下结果：起止点列车、飞机号票价Y方便程度B所需时间T权重W哈尔滨-长春T1580.5340.60.250.841D280.4660.50.180.706长春-沈阳T53020.4560.60.300.811D260.5340.70.200.903沈阳-天津13020.1550.60.971.141D1980.2460.60.460.7953U88620.6000.40.130.733天津-济南10360.0810.60.480.772D1640.1170.70.260.756BK28210.802
20、0.40.180.914济南-石家庄K3720.6160.60.500.955D55230.3840.80.150.899西安-郑州10860.2380.50.680.876G20020.6620.70.301.009合肥-上海K83650.2770.60.750.999D54770.4060.70.330.873MU54680.3170.40.100.520上海-杭州K83710.5170.60.230.824D55230.4830.70.150.863杭州-福州D3170.3090.80.420.954MF8650.6910.40.100.805福州-南昌K6660.2750.61.001
21、.1983U89600.7250.40.120.837长沙-广州CZ33750.3010.40.100.510G60010.4610.80.280.964T2530.2380.60.730.974南宁-贵阳K1420.3200.61.121.310CZ32750.6800.40.100.795贵阳-昆明K4710.2950.61.251.417MU58860.7050.40.100.931昆明-重庆K1680.3450.61.882.00CZ69500.6550.40.120.776重庆-成都K5770.4870.60.400.870D51010.5130.80.200.971成都-拉萨T22
22、0.2900.61.972.079CA4070.7100.40.200.839呼和浩特-北京K440.4270.51.031.222CA11060.5730.40.100.706北京-哈尔滨T1570.4700.51.041.246D250.5300.70.801.188根据以上的W进行比较，W小的即为最经济、省时、省钱、方便可行的订票方案，现已表格的形式列于下面：出发点终点乘车方式时间哈尔滨-长春D28软座座8：58-10：48长春-沈阳T5302硬卧06：12-09:07沈阳-天津3U8862飞机13：05-14：25天津-济南D164软座12：17-14：51济南-石家庄D5523硬座0
23、6：10-07：42石家庄-太原K868硬卧05:35-07:28太原-西安GS7581飞机18:00-19:05西安-郑州1086软卧07：41-14：29郑州-合肥2194软卧22：22-06：39合肥-上海MU5468飞机08:45-09:45上海-杭州K8371硬卧06：04-08：21杭州-福州MF865飞机08:10-09:10福州-南昌3U8960飞机13:00-14:10南昌-武汉无直达列车、无空航，但可在九江转站，方便省事可行武汉-长沙G1021硬座07:30-08:53长沙-广州CZ3375飞机08:00-08:55广州-香港坐客车即可香港-台北可选择包机直航或选取香港旅行
24、社旅游台北-香港香港-澳门坐客车即可澳门-海口无直达列车或者飞机，可先乘车后渡轮海口-南宁GS6521飞机12:30-13:20南宁-贵阳CZ3275飞机08：10-09：10贵阳-昆明MU5886飞机09:50-10:50昆明-重庆CZ6950飞机15:10-16:20重庆-成都K577硬卧05:03-09:00成都-拉萨CA407飞机07：40-09：45拉萨-西宁K918软卧08：00-07：40西宁-乌鲁木齐CZ3629飞机16:15-18:35乌鲁木齐-西宁CZ6881飞机09:15-11:20西宁-兰州K918硬卧08:00-10:13兰州-银川2636软卧09：56-18：30银
25、川-呼和浩特K886软卧12：50-21：38呼和浩特-北京CA1106飞机07：00-07：55北京-哈尔滨D25软座07:15-15:19六：算法的可行性、复杂性及误差的分析在按经纬度制定最短旅行路线过程中我们采用了Hopfeild神经网络算法来求解，并且模拟出来最终的行程路线，算的的最短路线行径总路程约为15408km,与很多其他算法算出的结果是很接近的。如用遗传算法算出的是15404km，可见，其误差是很小的。在查询网上订票的旅行方式后发现有些路线是行不通的（拉萨到乌鲁木齐中隔昆仑山），甚至个别城市的特殊性（台湾）我们又对其行程最佳路线进行修改，这也充分考虑了现实情况；另外，在优化行程
26、路线后，我们在制定订票方案时，考虑到周先生是生活享受游，并且，充分考虑其年龄和旅游目的，在乘车的起止时刻选取上我们尽量选取了比较适合的时间乘车，尽量在白天乘车，晚上到站可进行休息，劳逸结合。旅行方式上，我们尽量多的列出，然后给出算法比较。而同类乘车方式中考虑省钱省时方便舒适，对较长路程我们选取卧铺（软卧和硬卧之间主要考虑省钱），较短的我们选取硬、软座（软卧硬卧之间主要考虑省钱）制定出如上的乘车方式，具有较强可行性。在算法选取上，票价、方便程度、所需时间之间的联系难以理清，我们选取了痛着之间的比较，所以有了上述票价的归一化公式，而方便程度、所需时间的公式是根据数据的特点来的，有较大误差，最后，针
27、对票价、方便性、所需时间并无明确的联系，我们可将三者的综合权重视为先平方再开方的关系，尽量减小误差。是一堆数据进行了如上处理，丛结果可以看出：此方法对于时间较为敏感，一般在存在空航的多数选择了空航，是省时的倾向；而在快车与动车之间其选择还是比较满意的。而实际中，选择的几个飞机票价还是可以接受的（均有不少打折）并且相当省时、方便。所以，这也是比较满意的选择。七、自己对此算法的理解评价由于本小组的知识能力有限，在算法选择上有些简单化处理的倾向，但是，这样避免了很多的繁琐过程，可以说是有利有弊。但是结合实际情况，从结果中我们看出，此算法得到的结果与周先生的实际情况是很吻合的，作为生活享受游，乘车时间适当减少，才能有更多的旅游放松时间，优先选择空航是个不错选择。当然此算法有很多不足，需要名家进行修改。
