【文章內(nèi)容簡(jiǎn)介】 17 0 16 3 鄰接 2 67 2903 1784 15 485 167 0 9 3 鄰接 2 67 2903 1784 15 485 217 0 9 3 表 二線 S1557→ S0481 部分出行方案列表 求解方法 轉(zhuǎn)乘 總時(shí) 間 轉(zhuǎn)站點(diǎn) 1 轉(zhuǎn)站點(diǎn) 2 車輛 1 車輛 2 車輛 3 轉(zhuǎn)站點(diǎn)始 發(fā)數(shù) 總負(fù) 載 總費(fèi) 用 Lingo 3 102 1919,3186,903 L84,L189,L91,L239 4 Lingo/鄰接 2 109 1919 3186 84 189 460 0 113 3 鄰接 2 109 1919 3186 363 189 460 0 113 3 鄰接 2 115 1919 2424 84 417 254 0 112 3 鄰接 2 115 1919 2424 84 417 312 0 112 3 鄰接 2 118 1919 992 84 417 460 0 126 3 鄰接 2 118 1919 992 363 417 460 0 126 3 鄰接 2 130 1919 417 84 497 460 1 90 4 鄰接 2 130 1919 417 363 497 460 1 90 4 鄰接 2 133 3389 1427 84 454 447 1 77 4 表 三線 S0971→ S0485 部分 出行方案列表 求解方法 轉(zhuǎn)乘 總時(shí) 間 轉(zhuǎn)站點(diǎn) 1 轉(zhuǎn)站點(diǎn) 2 車輛 1 車輛 2 車輛 3 轉(zhuǎn)站點(diǎn)始發(fā) 數(shù) 總負(fù) 載 總費(fèi) 用 鄰接 1 131 2184 13 417 0 6 3 鄰接 1 146 2119 13 395 0 11 3 鄰接 1 152 1739 119 417 0 1 3 Lingo/鄰接 2 106 2517 2159 13 290 469 0 2 3 鄰接 2 109 1609 2654 13 140 469 0 33 3 鄰接 2 109 1609 2654 24 140 469 0 33 3 鄰接 2 124 2324 2482 13 132 417 1 17 4 鄰接 2 124 2324 2482 13 242 417 1 17 4 鄰接 2 124 2324 2480 13 132 417 1 24 4 鄰接 2 124 1520 2265 119 8 469 0 52 3 表 四線 S0008→ S0073 部分出行方案列表 求解方法 轉(zhuǎn)乘 時(shí)間 轉(zhuǎn)站點(diǎn) 1 轉(zhuǎn)站點(diǎn) 2 車輛 1 車輛 2 車輛 3 始發(fā)數(shù) 負(fù)載 總費(fèi)用 Lingo 4 62 3766,2085,483,525 L198,L476,L17,L328,L103 5 鄰接 1 86 2263 355 345 0 48 2 鄰接 1 89 2302 355 57 0 16 2 鄰接 1 113 3415 463 118 0 46 2 鄰接 1 131 3915 463 118 1 9 2 Lingo/鄰接 2 70 1691 2184 198 290 345 0 0 3 鄰接 2 70 1383 2184 43 290 345 0 37 3 鄰接 2 79 630 1659 159 231 459 1 83 3 鄰接 2 79 630 1659 159 381 459 1 83 3 鄰接 2 79 854 1659 159 231 459 1 60 3 表 五線 S0148→ S0485 部分出行方案列表 求解方法 轉(zhuǎn)乘 總時(shí) 間 轉(zhuǎn)站點(diǎn) 1 轉(zhuǎn)站點(diǎn) 2 車輛 1 車輛 2 車輛 3 轉(zhuǎn)站點(diǎn)始發(fā)數(shù) 總負(fù) 載 總費(fèi) 用 Lingo 3 105 3604,2361,2210 L308,L81,L156,L417 4 Lingo/鄰接 2 109 36 2210 308 156 417 1 29 3 鄰接 2 112 36 2482 308 157 417 1 47 3 鄰接 2 118 3604 1381 308 129 469 0 21 3 鄰接 2 118 3604 2026 308 123 469 0 14 3 鄰接 2 118 3604 1383 308 129 469 0 24 3 鄰接 2 121 3604 2840 308 454 417 0 22 3 鄰接 2 121 302 2027 308 427 469 0 13 3 鄰接 2 121 3604 1321 308 129 469 0 3 3 鄰接 2 124 3604 2079 308 206 417 0 73 3 表 六線 S0087→ S3676 部分出行方案列表 求解方法 轉(zhuǎn)乘 總時(shí) 間 轉(zhuǎn)站點(diǎn) 1 轉(zhuǎn)站點(diǎn) 2 車輛 1 車輛 2 車輛 3 轉(zhuǎn)站點(diǎn)始發(fā) 數(shù) 總負(fù) 載 總費(fèi) 用 Lingo/鄰接 1 68 3496 454 209 0 36 2 Lingo/鄰接 2 49 88 427 21 231 97 0 52 3 鄰接 2 49 88 427 206 231 97 0 52 3 鄰接 2 49 88 427 454 231 97 0 52 3 鄰接 2 52 630 427 21 381 97 0 44 3 鄰接 2 52 854 427 293 231 97 0 21 3 鄰接 2 52 1427 427 21 381 97 0 12 3 鄰接 2 55 541 2336 454 120 462 0 68 3 鄰接 2 61 3874 280 21 68 462 1 13 3 鄰接 2 73 3874 274 21 68 462 1 12 3 用戶選線指南： 上面表中已按多目標(biāo)分層序列法的默認(rèn)目標(biāo)排序（分別是表中轉(zhuǎn)乘次數(shù)、總時(shí)間、轉(zhuǎn)車站點(diǎn)是否始發(fā)、轉(zhuǎn)車站點(diǎn)總負(fù)載量、總費(fèi)用五個(gè)字段） ，一般用戶只需要從上到下選取即可，但如果用戶希望在轉(zhuǎn)站時(shí)乘坐始發(fā)車（有座位）那么可以挑選始發(fā)字段為 2 的方案，若希望轉(zhuǎn)站時(shí)人較少的地方則可以考慮選則站點(diǎn)負(fù)載較小的方案。綜述，本模型 I 求解的方案集使用于所有用戶，具有很強(qiáng)的實(shí)用價(jià)值。 模型Ⅰ的評(píng)價(jià) 鄰接算法評(píng)價(jià) 1) 建立在圖論基礎(chǔ)下能夠求解出轉(zhuǎn)乘次數(shù)不超過(guò)兩次時(shí)的所有可行方案，并可根據(jù)公眾的不同需求，給出最佳需要方案，從此角度考慮，模型實(shí)用性較強(qiáng)； 2) 模型求解基于直達(dá)隊(duì)列 Q ，采用空間換取時(shí)間思想，適合查詢系統(tǒng)設(shè)計(jì)標(biāo)準(zhǔn)能夠較強(qiáng)的適應(yīng)工程應(yīng)用； 3) 在轉(zhuǎn)乘次數(shù)超過(guò)兩次的情況下，運(yùn)用本模型求解計(jì)算過(guò)程復(fù)雜，計(jì)算量過(guò)大；故本模型存在一定的局限性。 01? 規(guī)劃 Lingo 求解方案評(píng)價(jià) 1) 在不限制最小轉(zhuǎn)乘數(shù)時(shí)可以求得全局最優(yōu)解，這是其他所有算法無(wú)法達(dá)到的，例如在第 5 條線路上其轉(zhuǎn)車次數(shù)為 3，但是耗時(shí)相對(duì)轉(zhuǎn) 2 次的要節(jié)省許多； 2)在限制最小轉(zhuǎn)乘數(shù)時(shí)可以求得與鄰接算法同樣的方案，表明模型的通用性較強(qiáng)，但無(wú)法像鄰接算法一樣求解多種方案是用戶所不能接受的； 3) 從理論角度分析，最優(yōu)化模型規(guī)劃角度可解具有很強(qiáng)的實(shí)際意義，例如從全國(guó)范圍考慮求解，那么轉(zhuǎn)車 3~4 次也是可以接受的，只要耗時(shí)足夠短； 4) 從計(jì)算 時(shí)間來(lái)分析，盡管需要 20 分鐘，但大部分時(shí)間為數(shù)據(jù)導(dǎo)入，只有 1%的時(shí)間是真正計(jì)算耗時(shí)，如果將所需數(shù)據(jù)存放入內(nèi)存不變，其求解速度將超越鄰接算法； 5) 但 Lingo 不能求解出多種方案，實(shí)用性不如鄰接算法。 6 同時(shí)考慮公汽與地鐵最佳線路選擇模型（問(wèn)題二） 本問(wèn)為綜合考慮公汽與地鐵線路的情況，解決查詢系統(tǒng)中混合最佳路徑選擇問(wèn)題的 模型與算法。 數(shù)據(jù)處理 —— 公交網(wǎng)簡(jiǎn)化模型 1）將可互換站點(diǎn)抽象處理為一個(gè)站點(diǎn) 題中給出了地鐵換乘公汽的數(shù)據(jù)文件，由地 鐵與公汽互換的時(shí)間來(lái)看，可互換的兩站間地理位置應(yīng)非常接近且容易換乘，定義這些站點(diǎn)為緊鄰站點(diǎn)，可將這些可互換的緊鄰站點(diǎn)抽象為一個(gè)站點(diǎn)，使問(wèn)題得到簡(jiǎn)化。 例 ：信息數(shù)據(jù)第一行為“ 01 : 05 67 , 00 42 , 00 25D S S S” ,則可認(rèn)為這四個(gè)站點(diǎn)實(shí)際距離非常近，為緊鄰站點(diǎn)，所以可看做一個(gè)點(diǎn)處理，示意圖如下： 基于這種思想，根據(jù)題目中給出關(guān)于地鐵換乘公交的信息數(shù)據(jù)，可以將各地鐵站點(diǎn) 及其緊鄰站點(diǎn)在整個(gè)交通網(wǎng)絡(luò)中抽象為一個(gè)點(diǎn)處理。 2）兩種地鐵線路抽象處理 基于 對(duì)三種公汽線路的抽象方 法，以相同的方法對(duì)兩地鐵線路 1T 、 2T 進(jìn)行抽象處理如下： 1T ：為雙向線路，故可以根據(jù)不同的方向?qū)⑵涑橄鬄閮蓷l單向行駛線路。 2T ：為環(huán)行線路，實(shí)際中環(huán)形路線一般是對(duì)開，故該種線路可以抽象成兩條線路處理。 “公汽、地鐵直達(dá)數(shù)據(jù)庫(kù) DQ ”的建立 將緊鄰站點(diǎn)處理為一個(gè)新站點(diǎn)，則當(dāng)綜合考慮公汽與地鐵時(shí)，建立的 DQ 實(shí)質(zhì)上是新站點(diǎn)與新站點(diǎn)間的直達(dá)路線集。認(rèn)為在新站點(diǎn)所代表的站點(diǎn)集中的任意站點(diǎn)可通過(guò)步行到達(dá)，且時(shí)間忽略。則當(dāng)用戶輸入起、訖點(diǎn)后，系統(tǒng)內(nèi)部首先自動(dòng)查找這兩點(diǎn)所屬的新站點(diǎn)，再查找新站點(diǎn)間可直達(dá)的線路，并給出起點(diǎn)及其附近站點(diǎn)可直達(dá)訖點(diǎn)及其附近站點(diǎn)的路線。 采用與 相同的思路及方法，把已知公汽線路到達(dá) ()iRs 都映射到 kS ，計(jì)算新直達(dá)數(shù)據(jù)庫(kù) DQ ，再結(jié)合地鐵的費(fèi)用與地汽換乘等待時(shí)間就可以把地鐵線與公汽線結(jié)合。 具體元胞結(jié)構(gòu)設(shè)計(jì)圖如下： Cell{1,1} Cell{1,2} 車號(hào) 費(fèi)用 耗時(shí) L001 2 27 T001 3 Cell{1,3} Cell{2,1} Cell{2,2} Cell{2,3} 圖 元胞結(jié)構(gòu)示意圖 上圖中 Cell{1,2}代表直達(dá)隊(duì)列表中第 1 行第 2 個(gè)元胞（即從站點(diǎn) S0001 到站點(diǎn)S0002 的直達(dá)混合線路信息） ，元胞中隊(duì)列的每一行代表一輛直達(dá)車信息。 模型Ⅱ的分析與建立 經(jīng)過(guò)數(shù)據(jù)處理后，緊鄰站點(diǎn)被處理為一個(gè)新站點(diǎn)，該站點(diǎn)可等同看作問(wèn)題一中的公汽站點(diǎn)，當(dāng)用戶輸入起、訖點(diǎn)后，系統(tǒng)內(nèi)部通過(guò)直達(dá)線路隊(duì)列表查詢無(wú)結(jié)果時(shí)，則搜尋轉(zhuǎn)乘路線方案。同時(shí)，系統(tǒng)向查詢者推薦不同目標(biāo)下的最佳路線及轉(zhuǎn)乘方案。 最少換乘次數(shù)的確定 采用與 相同的建模思路及方法，統(tǒng)計(jì) DQ 中各元素長(zhǎng)度，可得任意兩站點(diǎn)的直達(dá)線路數(shù)。由此可構(gòu)造表示兩 兩站點(diǎn)間直達(dá)路線數(shù)目的直達(dá)線路數(shù)矩陣 39。A ，可確定換乘線路數(shù)矩陣： 39。39。 39。 1 39。1Nnnij ik kjkA A A????? （ ） 其中，元素 39。nijA 為通過(guò) ( 1)n? 次換乘從站點(diǎn) ij? 的線路數(shù)。其換乘站點(diǎn)可通過(guò)運(yùn)算參數(shù)記錄得到。 進(jìn)而確定最少換乘次數(shù)矩陣： ? ?39。39。m in { 0 , 1 , } ( )0 ( )nijijn A n i jbij? ? ? ? ??? ?? ?? （ ） 39。39。1CB?? （ ） 表 最少換乘次數(shù)表 線路編號(hào) 1 2 3 4 5 6 起始站 S3359 S1557 S0971 S0008 S0148 S0087 終到站 S1828 S0481 S0485 S0073 S0485 S3676 最少換乘 1 2 1 1 2 0 模型分析 采用與 相同的建模思路及方法， 這里在考慮地鐵后仍按目標(biāo)的重要程度將 “換 乘次數(shù)最少”、“行程時(shí)間最短”、“行程費(fèi)用最少”、“轉(zhuǎn)乘車輛始發(fā)最多”、“站點(diǎn)負(fù)載壓力最小”分設(shè)為第一到五層目標(biāo)，基于 對(duì)各目標(biāo)的分析與建立，這里不再?gòu)?fù)述分析，僅在模型建立時(shí)給出具體表達(dá)式，這里由于對(duì)站點(diǎn)的定義與第一問(wèn)不同，所以對(duì) 時(shí)間 及 費(fèi)用 的計(jì)算與第一問(wèn)有所不同。 我們結(jié)合實(shí)際主要考慮用戶如下幾個(gè)因素： 目標(biāo)一：換乘次數(shù)最少； 目標(biāo)二：行程時(shí)間最短； 目標(biāo)三：行程費(fèi)用最少； 目標(biāo)四：轉(zhuǎn)乘車輛始發(fā)最多； 目標(biāo) 五：站點(diǎn)負(fù)載壓力最小。 公汽地鐵混合網(wǎng)絡(luò)圖的賦權(quán) 通過(guò) 的簡(jiǎn)化，結(jié)合圖論相關(guān)知識(shí)，將第二問(wèn)公汽、地鐵混合網(wǎng)絡(luò)抽象成一個(gè)有向賦權(quán)圖 39。 39。 39。 39。( , , )G V E W? , 39。G 中的每個(gè)頂點(diǎn)為每個(gè)不同的站點(diǎn) , 如果從 39。G 中的頂點(diǎn) 39。iV 到 39。jV有直達(dá)路線，那么這兩點(diǎn)之間就用有向邊相連 , 記做 39。(, )i j E? ，賦權(quán)圖中的權(quán)可根據(jù)不同的目標(biāo)進(jìn)行定義 ： 39。 ( , )39。39。39。() vvijijijt n n ij t v vW t t? ???? ?????站 點(diǎn) 至 站 點(diǎn) 的 直 達(dá) 時(shí) 間時(shí) 間 ： 其 分 量 為無(wú) 直 達(dá) 線 路 39。 ( , )39。39。39。() vvijij ijijp nn P v vW P P? ???? ?????站 點(diǎn) 至 站 點(diǎn) 的 直 達(dá) 費(fèi) 用費(fèi) 用 ： 其 分 量 為無(wú) 直 達(dá) 線 路 39。 ( , )39。39。39。() vvijij ijijf nn f v vW f f? ???? ?????站 點(diǎn) 至 站 點(diǎn) 的 直 達(dá) 線 路 是 否 始 發(fā)始 發(fā) ： 其 分 量 為無(wú) 直 達(dá) 線 路 39。()39。39