2016數(shù)學(xué)建模停車策略論文

1、自動泊車系統(tǒng)數(shù)學(xué)建模【摘要】隨著汽車產(chǎn)業(yè)及科技的高速發(fā)展，智能駕駛汽車成為了國內(nèi)外公認(rèn)的未來汽車重要發(fā)展方向之一。而在汽車智能化進(jìn)程中，自動泊車是一項非常具有挑戰(zhàn)性和實用性的技術(shù)。自動泊車系統(tǒng)可通過各類傳感器獲取車位相對汽車的距離，通過控制汽車前輪轉(zhuǎn)角和瞬時速度控制車輛行駛。若考慮系統(tǒng)控制容易性，參考人工倒車入庫，當(dāng)車輛位于與車位垂直的任意位置時，先通過前行或后退到達(dá)理想停車起始點后，再確定前進(jìn)轉(zhuǎn)角和后退轉(zhuǎn)角，使車身與車位在同一直線上后，直接倒車完成入庫，即"進(jìn)二退”。這種兩段式倒車模式提高了泊車過程中車輛行駛的緊湊性，同時減少了泊車行駛空間。考慮奇瑞汽車公司的QQ3,長3550mm

2、,寬1495mm,軸距2340mm,前輪距1295mm,后輪距1260mm,目標(biāo)車庫為小型汽車庫標(biāo)準(zhǔn)大小長6m,寬2.8m,車庫周圍情況如圖。關(guān)鍵字：轉(zhuǎn)乘次數(shù)廣度優(yōu)先算法查詢效率實時系統(tǒng)一問題的重述1）建立模型，按照車輛與車位之間的距離把車輛位置進(jìn)行分組，給出每一組對應(yīng)的倒車?yán)硐肫鹗键c，a=400mm,b=8000mm,c=300mm。2）建立模型，給出由理想起始點到倒車入庫的泊車策略，包括車速、前輪轉(zhuǎn)角、后輪行駛距離。二符號說明Li:第i條公汽線路標(biāo)號,i=1,210400，當(dāng)iE520時，L表示上行公汽路線，當(dāng)i>520時，Li表示與上行路線L-20相對應(yīng)的下行公汽路線；Si,g：經(jīng)

3、過第i條公汽路線的第g個公汽站點標(biāo)號；Tj:第j條地鐵路線標(biāo)號，j=1,2;Dj,經(jīng)過第j條地鐵線路的第h個地鐵站點標(biāo)號；LSn:轉(zhuǎn)乘n次的路線；Tk：選擇第k種路線的總時間；N1j選擇第k種路線公汽換乘公汽的換乘次數(shù)；N2k：選擇第k種路線地鐵換乘地鐵的換乘次數(shù)；N3k：選擇第k種路線地鐵換乘公汽的換乘次數(shù)；N4j選擇第k種路線公汽換乘地鐵的換乘次數(shù)；Wk,m：第k種路線、乘坐第m輛公汽的計費(fèi)方式，其中：Wk,m=1表示實行單一票價，Wk,m=2表示實行分段計價；CLk,m：第k種路線，乘坐第m輛公汽的費(fèi)用；Ck:選擇第k種路線的總費(fèi)用；MSk,m：選擇第k種路線，乘坐第m輛公汽需要經(jīng)過的公

4、汽站個點數(shù)；MDk,n：選擇第k種路線，乘坐第n路地鐵需要經(jīng)過的地鐵站個點數(shù)；FSk,m:表示對于第k種路線的第m路公汽的路線是否選擇步行，F(xiàn)Sk,m為0-1變量，F(xiàn)Sk,m=0表示不選擇步行，F(xiàn)Sk,m=1表示選擇步行；FDk,n:對于第k種路線的第n路地鐵的路線是否選擇步行，F(xiàn)Dk,n為0-1變量,FDk,n=0表示不選擇步行，F(xiàn)Dk,n=1表示選擇步行；amm2三模型假設(shè)3.2其它假設(shè)10、查詢者轉(zhuǎn)乘公交的次數(shù)不超過兩次；11、所有環(huán)行公交線路都是雙向的；12、地鐵線T2也是雙向環(huán)行的；13、各公交車都運(yùn)行正常，不會發(fā)生堵車現(xiàn)象；14、公交、列車均到站停車四問題的分析對于路線的評價，我們

5、可以分別以總行程時間，總轉(zhuǎn)乘次數(shù)，總費(fèi)用為指標(biāo)，也可以將三種指標(biāo)標(biāo)準(zhǔn)化后賦以不同權(quán)值形成一個綜合指標(biāo)。而最優(yōu)路線則應(yīng)是總行程時間最短，總費(fèi)用最少或總轉(zhuǎn)乘次數(shù)最少，或者三者皆有之。之所以這樣考慮目標(biāo)，是因為對于不同年齡階段的查詢者，他們追求的目標(biāo)會有所不同，比如青年人比較熱衷于比賽，因而他們會選擇最短時間內(nèi)到達(dá)奧運(yùn)賽場觀看比賽。而中年人則可能較傾向于綜合指標(biāo)最小，即較快、較省，轉(zhuǎn)乘次數(shù)又不多。老年人總愿意以最省的方式看到奧運(yùn)比賽。而對于殘疾人士則總轉(zhuǎn)乘次數(shù)最少為好。不同的路線查詢需求用圖4.1表示如下：圖4.1公交線路查詢目標(biāo)圖經(jīng)分析，本問題的解決歸結(jié)為一個求最短路徑的問題，但是傳統(tǒng)的Dijks

6、tra最短路徑算法并不適用于本問題，因為Dijkstra算法采用的存儲結(jié)構(gòu)和計算方法難以應(yīng)付公交線路網(wǎng)絡(luò)拓?fù)涞膹?fù)雜性，而且由于執(zhí)行效率的問題，具很難滿足實時系統(tǒng)對時間的嚴(yán)格要求。為此我們在實際求解的過程中，采用了效率高效得廣度優(yōu)先算法，其基本思路是每次搜索指定點，并將其所有未訪問過的近鄰點加入搜索隊列，循環(huán)搜索過程直到隊列為空。此方法在后文中有詳細(xì)說明。五建模前的準(zhǔn)備為了后面建模與程序設(shè)計的方便，在建立此模型前，我們有必要做一些準(zhǔn)備工作。5. 1數(shù)據(jù)的存儲由于所給的數(shù)據(jù)格式不是很規(guī)范，我們需要將其處理成我們需要的數(shù)據(jù)存儲格式。從所給文件中讀出線路上的站點信息，存入txt文檔中，其存儲格式為：兩

7、行數(shù)據(jù)，第一行表示上行線上的站點信息，第二行表示下行線的站點信息，其中下行路線標(biāo)號需要在原標(biāo)號的基礎(chǔ)上加上520,用以區(qū)分上行線和下行線。如果上行線與下行線的站點名不完全相同，那么存儲的兩行數(shù)據(jù)相應(yīng)的不完全相同，以公交線L009為例：L009:373903591477215923772211248224803439192019210180202030272981L529:298130272020018019211920343934402482221123772159147803593739L529為L009所對應(yīng)的下行線路。如果下行線是上行線原路返回，那么存儲的兩行數(shù)據(jù)中的站點信息剛好順序顛倒

8、，以公交線路L001為例：L001:061919140388034803920429043638853612081935240820391401280710L521:071001283914082035240819361238850436042903920348038819140619如果是環(huán)線的情況（如圖5,1所示），則可以等效為兩條線路：順時針方向：S1S2S3-SAS1-S2一SAS4;逆時針方向：SWS4S3-S2-SWS4-S3-S2o經(jīng)過分析，此兩條“單行路線”線路的作用等同于原環(huán)形路線圖5,1環(huán)行線路示意圖以環(huán)形公交線L158為例，此環(huán)形路線存儲數(shù)據(jù)如下：L153:5346492

9、35512128121711708112600172158581426435131215121725126042606534649235512128121711708112600172158581426435131215121725126042606L673:534260626042511217121535132648141585172260081117017181212122355649534260626042511217121535132648141585172260081117017181212122355649在這里，L153被看作成上行路線，L673被當(dāng)成下行路線。這樣對于每條公交線

10、路都可以得到兩行線路存儲信息。六模型的建立與求解6. 1模型一的建立該模型針對問題一，僅考慮公汽線路，先找出經(jīng)過任意兩個公汽站點Sjq與,gSq0最多轉(zhuǎn)乘兩次公汽的路線，然后再根據(jù)不同查詢者的需求搜尋出最優(yōu)路線。,g6.1.1公汽路線的數(shù)學(xué)表示任意兩個站點間的路線有多種情況，如果最多允許換乘兩次，則換乘路線分別對應(yīng)圖6.1的四種情況。該圖中的A、B為出發(fā)站和終點站，C、DE、F為轉(zhuǎn)乘站點。（幻<b>圖6.1公汽路線圖對于任意兩個公汽站點Sj,g與Sq,g,經(jīng)過Sj,g的公汽線路表示為Li,有Si,gwLj；經(jīng)過Sqg的公汽線路表示為L0,有SqowL0;,1,，g1）直達(dá)的路線LS

11、o（如圖6.1（a）所示）表示為：LSo=（Li1Si,gwLi1,Sq,gwLi1）2）轉(zhuǎn)乘一次的路線LG（如圖6.1（b）所示）表示為：L§=（Li1,Li2i）S,gWLi1,Sq,匕2；匕1,匕2乏La;SCWLi1且SCWLi?其中：SC為Li1,Li2的一個交點；3）轉(zhuǎn)乘兩次的路線LS2（如圖6.1（c）所示）表示為:LS2=(Li1,Li2,Li3)S,gWLi1,SWLi2；(Li1,Li3),(Li3,Li2爛L§Li1,Li2fLSj,g通過以上轉(zhuǎn)乘路線的建模過程，可以看出不同轉(zhuǎn)乘次數(shù)間可作成迭代關(guān)系，進(jìn)而對更多轉(zhuǎn)乘次數(shù)的路線進(jìn)行求尋。不過考慮到實際情況

12、，轉(zhuǎn)乘次數(shù)以不超過2次為佳，所以本文未對轉(zhuǎn)乘三次及三次以上的情形做討論。6.1.2最優(yōu)路線模型的建立找出了任意兩個公汽站點間的可行路線，就可以對這些路線按不同需求進(jìn)行選擇，找出最優(yōu)路線了：1）以時間最短作為最優(yōu)路線的模型：行程時間Tk等于乘車時間與轉(zhuǎn)車時間之和。nk+1MinTk=3'、（MSk,m1）.5N1kmW（6.1式）m1=,2,gggN1k+1;k=1,2,gggk其中，第k路線是以上轉(zhuǎn)乘路線中的一種或幾種。2）以轉(zhuǎn)乘次數(shù)最少作為最優(yōu)路線的模型：MinN1（6.2式）此模型等效為以上轉(zhuǎn)乘路線按直達(dá)、轉(zhuǎn)乘一次、兩次的優(yōu)先次序來考慮。3）以費(fèi)用最少作為最優(yōu)路線的模型：Min0=

13、£CLm（6.3式）m1Wk,m=1或Wk,m=2,0MSk,m<20其中，CLk,m=«2Wk,m=2,21MSk,m<40（6.4式）、3Wk,m=2,40MSk,m6.1.3模型的算法描述針對該問題的優(yōu)化模型，我們采用廣度優(yōu)先算法找出任意兩個站點間的可行路線，然后搜索出最優(yōu)路線?，F(xiàn)將此算法運(yùn)用到該問題中，結(jié)合圖6.2敘述如下:（該圖中的Si,g、Sq,g、S1,1、S2,1、S2,2表示公汽站點，L1、L2、L3、L4、L5、L6表示公汽線路。其中（a）、（b）、（c）圖分別表示了從點Sig到點S7直,gi,g達(dá)、轉(zhuǎn)乘一次、轉(zhuǎn)乘兩次的情況）圖6.2公交直達(dá)

14、、轉(zhuǎn)乘圖（1）首先輸入需要查詢的兩個站點Si,g與Sq&（假設(shè)Si,g為起始站，Sq®,為終點站）；（2）搜索出經(jīng)過Sjq的公汽線路Li（i=1,2，,m）和經(jīng)過Sqq的公汽線路,g1,go-q（q=1,2，n）,存入數(shù)據(jù)文件；判斷是Li與Lqi是否存在相同路線，若有則站點Si,g與Sq,g之間有直達(dá)路線（如圖6.2中的LJ,則該路線是換乘次數(shù)最少（換乘次數(shù)等于0）的路線，若有多條直達(dá)路線，則可以在此基礎(chǔ)上找出時間最省的路線；這樣可以找出所有直達(dá)路線，存入數(shù)據(jù)文件；（3）找出經(jīng)過Si,g的公汽線路Li（如圖6.2中的L2）中的另一站點Si1,g1和經(jīng)過Sq&的公汽線路

15、°_o中的另一站點S91010判斷Sii,gi與Sq10i1中是否存在相,gi7g7g同的點，若存在（如圖6.2中的S1,1）則站點Si,g與Sq,g間有一次換乘的路線（如圖6.2中的L2與L3）,該相同點即為換乘站點；這樣又找出了一次換乘路線，存入數(shù)據(jù)文件；（4）再搜索出經(jīng)過L（如圖6.2中的L4）線路上除了站點Sig的另一站點7Si2,g1（如圖6.2中的S271）的公汽線路Li6（如圖6.2中的L6）,找出公汽線路Li6上的其他站點Si2,g2；判斷，如果Si2,g2與經(jīng)過Soiq的公汽線路0,q中的其他站點17g1Sq2q2存在相同的點（如圖6.2中的S2,2）,則Si,g與

16、Sqq間有二次換乘的路線127g27g（如圖6.2中的L4、L6、L5）,該相同點和點Si2,g1是換乘站點；將此二次換乘的路線存入數(shù)據(jù)文件中；（5）對上述存儲的經(jīng)過兩個站點Sjg與Soq的不同路線，根據(jù)不同模型進(jìn)7g17g行最優(yōu)路線進(jìn)行搜索，得出查詢者滿意的最優(yōu)路線。6.1.4模型一的求解起始站S3359至IJ終至IJ站S1828的最少費(fèi)用為3元，最少費(fèi)用的最優(yōu)路線（所需時間較短，轉(zhuǎn)乘次數(shù)較少的路線）有30條，其中28條路線所需時間為64min,轉(zhuǎn)乘次數(shù)為2次，另外兩條路線所需時間為101min,轉(zhuǎn)乘次數(shù)為1次；起始站S1557到終到站S0481的最少費(fèi)用為3元，最少費(fèi)用的最優(yōu)路線有2條，所

17、需時間為106min,轉(zhuǎn)乘次數(shù)為2次；起始站S0971到終到站S0485的最少費(fèi)用為3元，最少費(fèi)用的最優(yōu)路線有3條，其中兩條所需時間為106min,轉(zhuǎn)乘次數(shù)為2次，另外一條所需時間為128min,轉(zhuǎn)乘次數(shù)為1次；起始站S0008到終到站S0073的最少費(fèi)用為2元，最少費(fèi)用的最優(yōu)路線有9條，所需時間為83min,轉(zhuǎn)乘次數(shù)為1次；起始站S0148到終到站S0485的最少費(fèi)用為3元，最少費(fèi)用的最優(yōu)路線有3條，所需時間為106min,轉(zhuǎn)乘次數(shù)為2次；起始站S0087至IJ終至IJ站S3676的最少費(fèi)用為3元，最少費(fèi)用的最優(yōu)路線有12條，所需時間為46min,轉(zhuǎn)乘次數(shù)為2次；最少費(fèi)用的最優(yōu)路線表示在表6

18、.1和表6.2中。6.2.1模型二的建立該模型針對問題二，將公汽與地鐵同時考慮，找出可行路線，然后尋找最優(yōu)路線。對于地鐵線路，也可以將其作為公交線路，本質(zhì)上沒有什么區(qū)別，只不過乘車費(fèi)用、時間，換乘時間不一樣罷了。因此地鐵站可等效為公交站，地鐵和公交的轉(zhuǎn)乘站即可作為兩者的交匯點。因此該模型的公交換乘路線模型與模型一中的基本相同?，F(xiàn)建立模型二下的最優(yōu)路線模型。1）以時間最短的路線作為最優(yōu)路線的模型：可行路線的總時間為乘公交（公汽和地鐵）時間與公汽與地鐵換乘、公汽問、地鐵間換乘時間之和。MinT3=4（MSk,n1）4.5Mz（MDk1,）/mN1mn（6.5式）4N27N36N4k其中，第k路線為

19、同時考慮公汽與地鐵的轉(zhuǎn)乘路線中的一種或幾種。2）以轉(zhuǎn)乘次數(shù)最少的路線作為最優(yōu)路線的模型：MinN電N+2Nk+3Nk4（6.6式）此模型等效為以上轉(zhuǎn)乘路線按直達(dá)、轉(zhuǎn)乘一次、兩次（包括公交與地鐵間的轉(zhuǎn)乘）的優(yōu)先次序來考慮。3）以費(fèi)用最少的路線作為最優(yōu)路線的模型：可行路線的費(fèi)用為乘公交和地鐵費(fèi)用的總和。MinCk=£QLm父3N4（6.7式）m其中，CLk,m仍滿足（6.4式）。6.2.2模型二的求解不難發(fā)現(xiàn)，問題一是問題二解的一部分。在問題二中，新產(chǎn)生的最優(yōu)解主要源于在通過換乘地鐵、換乘附近相近站點的路線上，如下圖所示：從點A到B,圖（a）表示的是通過兩公交線路上相鄰公汽站S1,S2進(jìn)

20、行一次轉(zhuǎn)乘；圖（b）表小利用地鐵站進(jìn)行二次轉(zhuǎn)乘；圖（c）表小利用另一條公汽路線為中介進(jìn)行二次轉(zhuǎn)乘。鐵路線路引入給題目的求解增加了難度，為了形象了解為數(shù)不多的兩條鐵路間的交叉關(guān)系，我們通過matlab編程（程序見附錄）作出了兩條鐵路的位置關(guān)系圖，如圖6.3所示。圖6.3T1與T2鐵路位置關(guān)系圖注：圖四中的直線表示T1鐵路線，圓表示T2鐵路線，數(shù)值表示站點，例如1表示T1鐵路線上的D1鐵路站，26表示T2鐵路線上的D26鐵路站。此圖與網(wǎng)上查詢到的北京地鐵示意圖（如圖6.4所示）相吻合。6.3.1模型三的建立該模型針對問題三，將步行方式考慮在了出行方式當(dāng)中，更符合實際。因為當(dāng)出發(fā)點與換乘點、終點站或

21、轉(zhuǎn)乘站與轉(zhuǎn)乘站之間只相隔幾個站時，當(dāng)然該段選擇步行方式更優(yōu)。因此作出如下假設(shè)：一、如果存在某段路線，其兩端點站之間相隔站點數(shù)小等于2（即至多經(jīng)過4個站點），則該段線路選擇步行方式到達(dá)目的地。其他的情況用模型二來處理。其中路線的兩端點站之間相隔站點數(shù)是根據(jù)公交直達(dá)換乘路線來確定的。二、相鄰公交站點（包括地鐵站）問平均步行時間為5分鐘。三、如果在公汽線路上選擇步行，則公汽間換乘次數(shù)減少1;如果在地鐵線路上選擇步行，則地鐵間換乘次數(shù)減少1,直達(dá)線路除外。直達(dá)和轉(zhuǎn)乘一次、兩次的路線需要步行的路段示意圖如圖6,5所示。圖中（a）表示出發(fā)點A與終點站B間能直達(dá)，相隔的站點數(shù)等于2所以選擇步行；圖中（b）表

22、示出發(fā)點A與終點站B間通過一次換乘能到達(dá)，其中路段AC的站點數(shù)等于2所以選才¥步行，同樣如果CB路段的站點數(shù)小等于2,則也采取步行的方式；圖中（c）選擇步行方式的依據(jù)類似。圖6,5步行示意圖是否選擇步行方式的函數(shù)：FD10MD行4其他(6.8式)工1MSk,m<4k，mI0其他其中FSk,m表示第m路公交路線是否步行，F(xiàn)Dk,n表示第n路地鐵線路是否步行;對于直達(dá)路線，如果出發(fā)點與終點站之間相隔站點數(shù)小等于2則步行，否則乘車。對于需要轉(zhuǎn)乘的路線的最優(yōu)路線模型討論如下：1）以時間最短的路線作為最優(yōu)路線的模型：路線總時間等于乘車時間加上步行時間，再加上轉(zhuǎn)乘時間。MinTk=3

23、9;(1-FSk,)m(MS亡1>2,5x(1-FD)珅-1)kmn(6.9式)5'FSk,m(MSk,m-1)5、FDk,n(MDk,n-1)mn5(N1-FSk,m)4(N2k-XFDk,n)7N3k6N4kmn=%(32F0,m)(MSk,m-1)、(2.525FDk,n)(MD.-1)mn5(N1k-xFSk,m)4(N2k，F(xiàn)Dk,n)7N3k6N4kmn其中，第k路線為同時考慮公汽與地鐵的轉(zhuǎn)乘路線中的一種或幾種。2）以轉(zhuǎn)乘次數(shù)最少的路線作為最優(yōu)路線的模型：每步行一次就少換乘一次車。MinN1k-£FSk,%N2FD+kN3n+N4k（6.20式）mn此模型等

24、效為以上轉(zhuǎn)乘路線按直達(dá)、轉(zhuǎn)乘一次、兩次、三次（包括公交與地鐵問的轉(zhuǎn)乘）的優(yōu)先次序來考慮。3）以費(fèi)用最少的路線作為最優(yōu)路線的模型：（6.21式）MinkC-（1卜5上）Ck,mL3N4m其中，CLk,m仍滿足（6.4式）。七模型的優(yōu)缺點及改進(jìn)7.1 模型的評價7.1.1 模型優(yōu)點1、模型是由簡單到復(fù)雜一步步建立的，使得更貼近實際。2、本文的模型簡單，其算法直觀，容易編程實現(xiàn)。3、本文模型比較注重數(shù)據(jù)的處理和存儲方式，大大提高了查詢效率。4、本文模型注重效率的提高，通過大量的特征信息的提取，并結(jié)合有效的算法,使其完全可以滿足實時系統(tǒng)的要求。7.1.2 模型缺點在建模與編程過程中，使用的數(shù)據(jù)只是現(xiàn)實

25、數(shù)據(jù)的一種近似，因而得出的結(jié)果可能與現(xiàn)實情況有一定的差距。7.2 模型的改進(jìn)以上模型主要是從公交線路出發(fā)，尋找公交線路的交叉站作為換乘站點，進(jìn)而找出經(jīng)過任意兩個站點的可能乘車路線。我們也可以從公交站點的角度出發(fā)，用圖論的方法建立有向賦權(quán)圖（如圖7.1所示），此向賦權(quán)圖是針對問題三建立的圖論模型，問題一、問題二只是此模型的簡化。圖7.1中Lj表示公汽線路標(biāo)號，該線路是公汽線路L的上行線或下行線，§、ggg、Sj、Sggg、Sn是公汽線路Lj上的站點標(biāo)號；Tk表示地鐵線路標(biāo)號，該地鐵線路是雙向行駛的，D1、gggDg、Dg書、ggg、Dm是地鐵線路上的站點標(biāo)號；公汽Li與地鐵Tk可以在公

26、汽站Sj和地鐵站Dg間換乘。如果圖7.1中的地鐵線路替換成公汽線路，為了表示公汽間換乘所需的時間或者費(fèi)用，應(yīng)將同一個換乘站點用兩個站點來表示。圖7.1公交線路的有向賦權(quán)圖根據(jù)不同的目標(biāo)，給不同的站點間的邊賦上不同的權(quán)值。然后利用圖論的相關(guān)算法，找出相應(yīng)的最短路徑。1）當(dāng)以時間最短為目標(biāo)時，給每條邊賦上時間的權(quán)值。給同一線路上任意兩個站點間的邊賦值時，其權(quán)值等于站點間的公交線路段數(shù)與平均時間的乘積。10當(dāng)某段線路的兩段點問問隔站點數(shù)小等于3時，選擇步行，該線路的權(quán)值等于步行時間。不同公汽和地鐵間進(jìn)行換乘時需要賦給不同的權(quán)值，以表示換乘時間。例如(如圖7.1):當(dāng)j>4時，Si到Sj的邊權(quán)值

27、§$=(>1)父3從Sj1到Sj不需要的轉(zhuǎn)車，但根據(jù)假設(shè)應(yīng)選擇步行，其邊權(quán)值Sj,Sj)=5;,從Sj°到Dj要么乘公交，然后轉(zhuǎn)車，要么步行，根據(jù)步行的假設(shè)條件，Sj到Dj的站點間隔數(shù)小于2,因此選擇步行，其邊權(quán)值t：Sj,Dg)=5;,當(dāng)g>4時，Di與Dg之間的邊權(quán)值(Di,Dg>=<Dg,Di>=(g-1)x2.5;,Sj到Dg的邊權(quán)值(Sj,Dg>=6;Dg到Sj的邊權(quán)值<D,Sj>=7;Jgj當(dāng)j>4、g>4時，Si到Di的路徑長度為：(S,Di)=4S,Sj>+<Sj,Dg>+<

28、Dg,Di>=(j-i)x3+6+(g-i)x2.5;當(dāng)jW4、g>4時，則從Si到Dg選擇步行，再乘地鐵到Di,其路徑長度為；(§,Di)=Si，DgDg,Di=(j-i)5(g-i)2.5；找出任意兩點間可行路線的路徑長度后，再搜索出其中的最短路徑的的可行路線作為時間的最優(yōu)路線。2)當(dāng)以費(fèi)用最省為目標(biāo)時，則給每條邊賦上費(fèi)用的權(quán)值。公汽站點間的邊權(quán)按(6.4式)賦值。當(dāng)公汽線路J按單一票價計費(fèi)，對于J上任意兩個公汽站點Sj和S)問，若j-j+i<4,則選擇步行<'Sj>=0;若j-j+i>4,WJSjSj)=i;當(dāng)公汽線路Li按分段計價，

29、若j-j+i<4,則Sj,Sj)=0;若3<1-j2，貝卜SjSj)=i;若20<j-j<40,則<SjSj)=2;若j-j>40,則S,Sj)=3;地鐵線路Tk上任意兩個站點Dg和Dg間，若j-j+i<4,則選擇步行«Dg,D古)=<Dq,Dg)二0；若jT巾乂，則Sg,D)=DD3=；換乘站點Sjgggg與Dg間的邊權(quán)值均為0,即Dg,Sj)=Sj,Dg)=0；則從通過站點Sj換乘Dg到Di的一條可行路線的路徑長度為:ii若j«4,g>4,則從S1到Sj選擇步行，(Si,Di)=:Dg,D1=3;若j>4,g&

30、gt;4,WJ(Si,Di)=(S,Sj)Dgi,D)=3+3=6;同樣可以找出任意兩點間可行路線的路徑長度，然后再搜索出最短路徑作為費(fèi)用的最優(yōu)路線。以上從公交站點出發(fā)，將公交站點作為網(wǎng)絡(luò)圖中頂點，得出公交的拓?fù)浣Y(jié)構(gòu)，進(jìn)而尋求不同目標(biāo)下的最短路徑，為我們提供了另外一種思路。但是從以上圖形的結(jié)構(gòu)，我們已經(jīng)看得出其復(fù)雜程度是不可預(yù)知的，尤其隨著數(shù)據(jù)的增多，圖的復(fù)雜度隨之上升。如果不尋求一個好的算法，而用常規(guī)的Dijkstra算法，將有可能在可以忍受的時間范圍內(nèi)得不出有效結(jié)果。經(jīng)過參考相關(guān)資料，我們發(fā)現(xiàn)用螞蟻算法可能比較有效。該算法利用了螞蟻尋食出行路徑選擇的行為特點，通過線路激素強(qiáng)度的更新機(jī)制，實現(xiàn)了以換乘次數(shù)最少和公交出行站點最少的公交出行路徑選擇優(yōu)化目標(biāo)。八參考文獻(xiàn)1 344000溫小文臧德彥，城市公交信息查詢系統(tǒng)設(shè)計初探，江西測繪，第65期，20062 龔劭圖論與網(wǎng)絡(luò)最優(yōu)化算法重慶大學(xué)出版社，20003 1671-4512(2003)Sl-0