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

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

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

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

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

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

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