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飛