公交最優(yōu)路線問(wèn)題

1、公交最優(yōu)路線問(wèn)題摘要針對(duì)公交系統(tǒng)的特點(diǎn)，該文把環(huán)形路線和往返路線做成上下行路線，由此構(gòu)造了1040行、100列的矩陣（矩陣的每個(gè)非零元素為對(duì)應(yīng)路線的站點(diǎn)）。K矩陣的行下標(biāo)對(duì)應(yīng)公交系統(tǒng)中的線路號(hào)（行數(shù)為偶數(shù)：線路號(hào)=行數(shù)2；行數(shù)為奇數(shù)：線路號(hào)=（行數(shù)1）2），矩陣的列下標(biāo)對(duì)應(yīng)每條路線上公汽經(jīng)過(guò)站點(diǎn)的次序，當(dāng)路線中的站點(diǎn)不足100個(gè)時(shí)，矩陣中對(duì)應(yīng)的位置以0代替。鑒于公交系統(tǒng)網(wǎng)格的復(fù)雜性，沒(méi)有采用常規(guī)的迪克斯特拉（Dijkstra）算法，而是

2、提出了一個(gè)能高效搜索任意兩站點(diǎn)之間的路線選擇的算法?；舅枷霑r(shí)從經(jīng)過(guò)起始站的路線出發(fā)，搜尋出任意兩站點(diǎn)間轉(zhuǎn)乘次數(shù)不超過(guò)兩次的可行路線，然后對(duì)可行解進(jìn)一步處理，建立了以時(shí)間最少為目標(biāo)的優(yōu)化模型。從實(shí)際情況出發(fā)，經(jīng)過(guò)嘗試與探索，為了滿足查詢者的不同需求，歸納出直達(dá)，換乘一次，換乘兩次的情況，并通過(guò)Matlab編制程序，給出了任意兩站點(diǎn)間的最佳乘車(chē)路線以及換車(chē)的站點(diǎn)，最后提出了進(jìn)一步的意見(jiàn)和建議。利用此模型和算法求解所給的6對(duì)起始站→終到站之

3、間的最佳（最省時(shí)）路線。這6對(duì)路線的具體情況如表1關(guān)鍵字：關(guān)鍵字：優(yōu)化模型，最優(yōu)路線，搜索篩選，換乘次數(shù)，乘車(chē)時(shí)間。出發(fā)站?終點(diǎn)站S3359?S1828S1557?S0481S0971?S0485S0008?S0073S0148?S0485S0087?S3676最短耗時(shí)（min）731061067010646最少轉(zhuǎn)乘次數(shù)（次）222222最佳路線（種）1062530314表16對(duì)起始站→終到站之間的最佳（最省時(shí)）路線四模型的建立與求解4

4、.1模型的分析為了研制開(kāi)發(fā)一個(gè)解決公交線路最佳選擇問(wèn)題的自主查詢計(jì)算機(jī)系統(tǒng)，只要乘客給出起點(diǎn)站和終點(diǎn)站，就能找到所有可行的路線，進(jìn)而可以找到最省時(shí)的路線和換乘次數(shù)最少的路線以滿足乘客的需求。但從實(shí)際情況出發(fā)，本文設(shè)計(jì)一個(gè)城市公交路線自主查詢系統(tǒng)。為了使線路更合理，并且滿足乘客乘車(chē)心理（乘客通常也不會(huì)因節(jié)省幾分鐘換乘多次），該系統(tǒng)不會(huì)使乘客多次轉(zhuǎn)乘到終點(diǎn)站，所以轉(zhuǎn)乘次數(shù)小于三次比較合理。為了便于建立模型及求解，對(duì)數(shù)據(jù)進(jìn)行如下處理：首先構(gòu)造

5、公交系統(tǒng)的矩陣，先將環(huán)形路線和往返路線做成上下行路線，即把原環(huán)形路線的最后一站點(diǎn)去掉后作為此路線的上行路線，再把此原環(huán)行路線的第一個(gè)站點(diǎn)去掉后作為此路線的下行路線；在往返路線中，把數(shù)據(jù)中所給的原路線作為上行路線，將此上行路線首尾翻轉(zhuǎn)作為下行路線。按照此原則處理后，可構(gòu)造一個(gè)1040行、100列的矩陣。矩陣的行下標(biāo)對(duì)應(yīng)公交系統(tǒng)中的線K路號(hào)（行數(shù)為偶數(shù)：線路號(hào)=行數(shù)2；行數(shù)為奇數(shù)：線路號(hào)=（行數(shù)1）2），矩陣的列下標(biāo)對(duì)應(yīng)每條路線上公汽經(jīng)過(guò)站

6、點(diǎn)的次序，當(dāng)路線中的站點(diǎn)不足100個(gè)時(shí)，矩陣中對(duì)應(yīng)的位置以0代替。4.2模型的建立4.2.1公汽路線的建立任意兩個(gè)站點(diǎn)間的路線有多種情況，如果最多允許轉(zhuǎn)乘兩次，則路線分別對(duì)應(yīng)圖1的三種情況。例如，圖1中的、為出發(fā)站和終點(diǎn)站所在路線為ABA，記，所在路線為，記，、、為轉(zhuǎn)乘站，即為1L1AL?B2L2BL?CDEC與的交點(diǎn)，為與的交點(diǎn)，為與的交點(diǎn)。1L2LD1L3LE2L3L（1）直達(dá)路線（如圖1（a）所示）任意兩個(gè)公汽站點(diǎn)與，利用MATL