走遍全中国的最优路线(旅游必备)

1、走遍全中国的最优路线问题摘要：针对周先生旅游最短路线的设计，首先，将周先生的旅游视为 生活享受游，其次，一个城市的经纬度为坐标，并运用 Hopfeild 神经 网络算法求解出最短旅行路线，之后，参考网上订票的具体信息，并 结合周先生的年龄问题，选取了空航、动车、快车卧铺三种较舒适的 旅行方式，以经济性，省时省钱为指标进行建模分析，最后通过各部 分加权比重进行综合评价，拟定出最佳订票方案，见下文。并且进行 了算法的适当分析与模型的优化。关键词：经纬度、最短路线、订票方案、算法分析 一：问题重述：周游先生退休后想到各地旅游。计划走遍全国的省会城市、直辖市、香港、澳门、台北。请你为他按下面要求制定出

2、 行方案：1按地理位置（经纬度）设计最短路旅行方案；2如果 2010年5月 1日周先生从哈尔滨市出发，每个城市停 留 3 天，可选择航空、铁路（快车卧铺或动车） ，设计最经济的旅行 互联网上订票方案；3 要综合考虑省钱、省时又方便，设定你的评价准则，建立 数学模型，修订你的方案；4对你的算法作复杂性、可行性及误差分析； 5关于旅行商问题提出对你自己所采用的算法的理解及评价。 二：基本假设：在旅途中旅游车的准时出发到达 ,且不考虑突发事件干扰车子的行程 ; 在旅游的过程中 ,当天旅游目的地附近都有宾馆 ,且第一天的目的地就 是第二天的出发点；在每个城市的吃饭、购物、在城市中观光景点等 所需的费用

3、费用视为相同；三：评价标准、基本符号、变量。 【1】根据旅客要求，寻找按经纬度最短的旅行途径，故先将各 省会、直辖市、特别行政区的经纬度列在下面表格中：城市名称经度纬度北京e116 ° 28 'n39 ° 54 '上海e121 ° 29 'n31 ° 14 '天津e117 ° 11 'n39 ° 09 '重庆e106 ° 32 'n29 ° 32 '哈尔滨e126 ° 41 'n45 ° 45 '长春e125

4、76; 19 'n43 ° 52 '沈阳e123 ° 24 'n41 ° 50 '呼和浩特e111 ° 48 'n40 ° 49 '石家庄e114 ° 28 'n38 ° 02 '太原e112 ° 34 'n37 ° 52 '济南e117 °n36 ° 38 '郑州e113 ° 42 'n34 ° 48 '西安e108 ° 54 'n34

5、76; 16 '兰州e103 ° 49 'n36 ° 03 '银川e106 ° 16 'n38 ° 20 '西宁e101 ° 45 'n36 ° 38 '乌鲁木齐e 87 ° 36 'n43 ° 48 '合肥e117 ° 18 'n31 ° 51 '南京e118 ° 50 'n32 ° 02 '杭州e120 ° 09 'n30 ° 14 '

6、;长沙e113 °n28 ° 11 '南昌e115 ° 52 'n28 ° 41 '武汉e114 ° 21 'n30 ° 37 '成都e104 ° 05 'n30 ° 39 '贵阳e106 ° 42 'n26 ° 35 '福州e119 ° 18 'n26 ° 05 '台北e121 ° 31 'n25 ° 03 '广州e113 ° 15 '

7、;n23 ° 08'海口e110 ° 20 'n20 ° 02 '南宁e108 ° 20 'n22 ° 48 '昆明e102 ° 41 'n25 °拉萨e 91 ° 10 'n29 ° 40 '香港e114 ° 10 'n22 ° 18 '澳门e113.5n 22.22】在以经纬度为基础上算出的行程最短路线上， 进行网上订票， 本 题中， 考虑到周先生年龄问题， 又是退休后旅游， 是以归为生活 享受游， 为

8、了使其有精力地更长时间参观景点， 在乘车方式的选 取上进行如下考虑：在不同的乘车方式上， 若距离较远， 可考虑 空航、动车、快车卧铺三种方式； 若为较短距离旅行可考虑动车、 快车卧铺和硬座； 在很短的距离可考虑快车硬座和公交车。 而在 相同的乘车方式上 （例如： 均为快车卧铺，应先考虑哪辆车次） ， 考虑到票价、 乘车所需时间均基本相同， 是以优先考虑列车的起 始和终止时刻， 考虑到旅游的观光目的和精力问题， 是以列出两 个优先原则。 第一优先原则：尽量晚上到站，可在当地宾馆休息 一晚， 次日即可旅游；第二优先原则： 在不能满足第一优先原则 的前提下，若为短途，则可考虑早出发早到原则；优先原则

9、三： 在有些情况下，某些列车的票价较低、乘车所需时间较短，是以 可优先考虑。【3】 根据体重提出的几个要素指标，现在归纳如下： 1、乘车费用 （即票费，用Y表示在各因素中所占权重）2、旅行中交通方 便性（乘车方式，用B表示在各因素中所占权重）3、旅行时 间（尽量使在景点停留时间长， 乘车时间短， 这是旅游本来的 目的，符合旅客的要求，用 T表示在各因素中所占权重）， 【4】在评价模型的建立与求解过程中， 各个因素的指标均选取模糊 集为衡量标准，票价和乘车时间可按比例选取优、良、中、 差四个等级；旅行方便程度可按乘车方式飞机、动车、快车 卧铺划分为好、中、差三个等级；最后进行整合，进行权 重计算

10、。四：模型建立 路线设计：按经纬度距离最短的行程路线 模型假设：运用 Hopfeild 神经网络算法来解决旅行路线最佳问 题。首先将问题映射到 Hopfeild 网络上，故将 33 个城市视为神 经元，任何一个城市在最终路径上的访问次序可用一个N 维向量来表示，因此每个城市需要 33个神经元表示，我们不妨规定 第i个城市为Ai （x、y）, xy表示城市的经纬度，如果访问从第i 个城市开始，则第 i 个神经元（城市）视为 1，其余神经元视为 0,为了表示所有城市,可以用个 33*33 的矩阵表示,必须保证 每行每列只有一个 1,这样的矩阵称为换位矩阵。构造函数,这 里选取的是能量函数,其最小值

11、对应最短路径。现借鉴 Hopfield 模拟结果得到最短旅行路线。 最短旅行路线为：Hopfield模拟结果起点：哈尔滨长春沈阳天津济南石家庄太原西安一一郑州一一合肥一一南京一一上海一一杭州一一台北一一福州南昌武汉沙广州香港澳门海口 南宁贵阳昆明重庆成都拉萨乌鲁木齐西宁兰州银川呼和浩特北京哈尔滨四、互联网上订票方案基于上述路线，现在以互联网上订票的经济性为基础，对航空、 铁路（快车卧铺或动车）旅行方式进行选取。查阅每两地间的列 车、飞机时刻表，现归纳如下：出发点一终占八、快车卧铺、 动车、飞机 车次出发到站时刻票价哈尔滨-长春T15808: 45-11 : 1087硬卧D28：8: 58-10

12、: 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-08: 50910济南-石家庄K37209:12-14:1793硬卧石家庄-太原K86805:35-07:2884硬卧太原-西安GS7581P 18:00-19:05404西安-郑州108607: 41-14: 29122

13、软卧G200208:03-11:05390软座郑州-合肥219422： 22-06: 39138软卧合肥-上海K836512:48-20:21116硬卧D547707:58-11:15170软座MU5468P 08:45-09:45133上海-杭州K837106： 04-08: 2175硬卧D552306： 10-07： 4270软座杭州-台北无列车或者飞机台北-福州福州-南昌K66608:04-18:02153硬卧3U8960P 13:00-14:10403南昌-武汉无直达列车、无空航，只能转站武汉-长沙G102107:30-08:53175硬座长沙-广州CZ337508:00-08:552

14、17G600108:00-10:46333硬座T25306： 24-13 : 43172硬卧广州-香港无列车，无飞机，可坐公交车香港-澳门澳门-海口无直达列车或者飞机海口 -南宁GS652112:30-13:20573南宁-贵阳K14212:57-00:07201硬卧CZ3275：08: 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硬座成都-拉萨

15、T22：20: 59-16: 40557硬卧CA40707: 40-09: 451364拉萨-乌鲁木 齐无直达列车或者飞机乌鲁木齐-西CZ688109:15-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软座经过网上订票发现，我们理想中的乘车路线在很多方面是行不通的， 有些

16、城市之间是没有列车和飞机通过的， 需要中转站进行倒车，这是 很不方便的，并且，有些城市与其他城市之间的交通是非常少的，例 如台北（最佳去台北的路线是从香港出发去台北， 一般包机会在香港 转机，或者依靠香港中国旅行社进入台湾旅游）。因此需要我们进行 模型优化，并且，将其中的最佳订票方式确定出来。五：模型优化针对上述某些城市之间无列车直达或飞机直航，甚至某些城市交通与外界很闭塞。考虑到省时、省钱、方便的原则，是以我们要对路线进行修改，根据网上订票的可能性，我们整合出如下订票方案：出发点一终点快车卧铺、动车、 飞机车次出发到站时刻价哈尔滨-长春T15808： 45-11 : 1087硬卧D288：

17、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-08: 50910济南-石家庄K37209:12-14:1793硬卧D552306: 10-07: 4258硬座石家庄-太原K86805:35-07:2884硬卧太原-西安GS758118:00-19:05404

18、西安-郑州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-11:20183硬座MF86508:10-09:10409福州-南昌K66608:04-18:02153硬卧3U896013:00-14:10403南昌-武汉无直达列车、无空航，但可在九

19、江转站，方便省事可 行武汉-长沙G102107:30-08:53175硬座长沙-广州CZ337508:00-08:55217G600108:00-10:46333硬座T25306: 24-13: 43172硬卧广州-香港坐客车即可香港-台北可选择包机直航或选取香港旅行社旅游台北-香港可选择包机直航或选取香港旅行社旅游香港-澳门坐客车即可澳门-海口无直达列车或者飞机，可先乘车后渡轮海口 -南宁GS652112:30-13:20573南宁-贵阳K14212:57-00:07201硬卧CZ327508： 10-09: 10428贵阳-昆明K47105:00-17:29164硬卧MU588609:50

20、-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:15-11:201075西宁-兰州K91808:00-10:1379硬卧兰州-银川263609: 56-18: 30115软卧银川-呼和浩特K88612: 5

21、0-21 : 38161软卧呼和浩特-北京K4409: 18-19: 37244软卧CA110607: 00-07: 55327北京-哈尔滨T15706: 45-17: 11411软卧D2507:15-15:19464软座针对此订票方案，我们将旅行路线优化为：起点：哈尔滨长春沈阳天津济南石家庄太原 西安一一郑州一一合肥一一南京一一上海一一杭州一一福州一一南 昌 武汉 长沙 广州 香港 台北 澳门 海口 一一 南宁一一贵阳一一昆明一一重庆一一成都一一拉萨一一西宁一一乌鲁 木齐 西宁 兰州 银川 呼和浩特 北京 哈尔滨六：模型求解与算法的分析我们充分考虑省时、省钱、方便三方面的指标，对上表的数据进

22、 行归一化处理，针对每两个城市之间的两种或者三种乘车方式，为选出适当的方式，我们需要比较，因此规定如下算法：因为票价、方便程度度三者之间难以直接比较， 是以我们以票价 与票价进行比较，同因素之间的比较比较精准，归一化公式如下：Y仁（Y1+Y2+Y3 /3;Y仁（Y1+ Y22。而方便程度我们考虑乘车、座位形式的方便性，为简化计算难度同时考虑到实际情况应将其分为比较集中且相差不大的几组系数如下：飞机座位为0.4,快车软卧为0.5，快车硬卧为0.6，动车软座为0.7，动车硬座为0.8。所需时间我们考虑乘车时间的长度，而T=h/10,h代表所需时间的 小时数。最后权重的计算，为比较方便，我们将 Y、

23、B、T在权重 中所占分量理解为如下关系： W二在此处键入公式。得到如下结果：起止点列车、飞机号票价丫方便程度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.8020.40.180.914济南

24、-石家圧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.1983U89600.72

25、50.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成都-拉萨T220.2900.61.972.

26、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硬座06：

27、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广州-香港坐客车即可香港-台北 台北-香港可选

28、择包机直航或选取香港旅行社旅游香港-澳门坐客车即可澳门-海口无直达列车或者飞机，可先乘车后渡轮海口 -南宁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西宁-兰州P K918硬卧08:00-10:13兰州-银川2636软卧09: 56-18: 30银川-呼和浩特K886软卧12: 50-21 : 38呼和浩特-北京CA1106飞