[發(fā)明專利]一種基于北斗定位與客流量的公交換乘優(yōu)化方法

在審

• 申請?zhí)枺?/td>: 201711003324.0
• 申請日: 2017-10-24
• 公開（公告）號: CN107808217A
• 公開（公告）日: 2018-03-16
• 發(fā)明（設(shè)計）人: 邢建平;李東轅;董沛鑫
• 申請（專利權(quán)）人: 山東大學(xué)
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/30;G08G1/00
• 代理公司: 濟(jì)南金迪知識產(chǎn)權(quán)代理有限公司37219
• 代理人: 葉亞林

1.一種基于北斗定位與客流量的公交換乘優(yōu)化方法，其特征在于，包括步驟如下：

1)獲取公交數(shù)據(jù)：

收集并記錄公交數(shù)據(jù)；所述公交數(shù)據(jù)包括，公交線路圖、公交站點(diǎn)名稱、同一條公交線路中兩相鄰公交站點(diǎn)間的實(shí)際距離和公交刷卡次數(shù)；

2)數(shù)據(jù)預(yù)處理：

按公交車行進(jìn)順序依次對每條公交線路中的公交站點(diǎn)進(jìn)行順序編號；

計算同一對相鄰公交站點(diǎn)間通過公交線路的數(shù)量；記兩相鄰公交站點(diǎn)i與公交站點(diǎn)j之間通過的不同公交線路數(shù)為N_ij；

相鄰公交站點(diǎn)i與公交站點(diǎn)j間的距離記為L_ij；通過公交刷卡次數(shù)計算相鄰公交站點(diǎn)i與公交站點(diǎn)j的總客流量F_ij；

3)構(gòu)建公交網(wǎng)絡(luò)系統(tǒng)的復(fù)雜網(wǎng)絡(luò)；

換乘次數(shù)最少的公交乘車方案

3.1.1)在pajek中，采用依次列舉復(fù)雜網(wǎng)絡(luò)中所有邊的方式進(jìn)行數(shù)據(jù)錄入，基本格式如下所示：

*Vertices N

*Edgeslist[i j c]

*Matrix

在上述數(shù)據(jù)結(jié)構(gòu)中，N表示復(fù)雜網(wǎng)絡(luò)中全部節(jié)點(diǎn)的數(shù)量，i和j分別表示與所述邊對應(yīng)的兩個公交站點(diǎn)的編號，c表示權(quán)重，當(dāng)公交站點(diǎn)i與公交站點(diǎn)j之間有公交線路時，c＝0；當(dāng)公交站點(diǎn)i與公交站點(diǎn)j之間無公交線路時c＝1；

3.1.2)利用pajek讀取公交網(wǎng)絡(luò)系統(tǒng)的net文件，利用P空間方法生成公交換乘網(wǎng)絡(luò)的復(fù)雜網(wǎng)絡(luò)圖；以公交站點(diǎn)作為復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)；

3.1.3)根據(jù)復(fù)雜網(wǎng)絡(luò)中各個節(jié)點(diǎn)間的連接關(guān)系，構(gòu)造城市公交網(wǎng)絡(luò)系統(tǒng)的鄰接矩陣；鄰接矩陣中的元素a_ij為0或者1；1代表相應(yīng)的行數(shù)與列數(shù)的站點(diǎn)間有公交線路；0代表相應(yīng)的行數(shù)與列數(shù)的站點(diǎn)間沒有公交線路；

3.1.4)根據(jù)鄰接矩陣，利用Floyd算法計算任意兩站點(diǎn)之間的最少換乘次數(shù)；具體步驟如下：

A)設(shè)Dis(i,j)為公交站點(diǎn)i到公交站點(diǎn)j的最少換乘次數(shù)；

B)對于每一個公交站點(diǎn)k，檢查Dis(i,k)+Dis(k,j)<Dis(i,j)是否成立，如果成立，則判定從i到k再到j(luò)的路徑比i直接到j(luò)的路徑短，設(shè)置Dis(i,j)＝Dis(i,k)+Dis(k,j)；其中，k≠i，j；

C)重復(fù)步驟B)，直至遍歷所有公交站點(diǎn)k，Dis(i,j)即公交站點(diǎn)i到公交站點(diǎn)j的最少換乘次數(shù)；

用時最少的公交乘車方案

3.2.1)在pajek中，采用依次列舉復(fù)雜網(wǎng)絡(luò)中所有邊的方式進(jìn)行數(shù)據(jù)錄入，基本格式如下所示：

*Vertices N

*Edgeslist[i j c]

*Matrix

3.2.2)利用pajek讀取公交網(wǎng)絡(luò)系統(tǒng)的net文件，利用L空間方法生成公交站點(diǎn)網(wǎng)絡(luò)的復(fù)雜網(wǎng)絡(luò)圖；以公交站點(diǎn)作為復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)；連邊的權(quán)值

3.2.3)根據(jù)復(fù)雜網(wǎng)絡(luò)中各個節(jié)點(diǎn)間的連接關(guān)系，構(gòu)建城市公交網(wǎng)絡(luò)的L空間鄰接矩陣；鄰接矩陣中的元素a_ij為0或者1；1代表相應(yīng)的行數(shù)與列數(shù)的站點(diǎn)間有公交線路；0代表相應(yīng)的行數(shù)與列數(shù)的站點(diǎn)間沒有公交線路；

3.2.4)利用Floyd算法計算最省時間的公交乘車方案；具體步驟如下：

a)設(shè)dis(i,j)為公交站點(diǎn)i到公交站點(diǎn)j的最少換乘次數(shù)；

b)對于每一個公交站點(diǎn)k，檢查dis(i,k)+dis(k,j)<dis(i,j)是否成立，如果成立，則判定從i到k再到j(luò)的路徑比i直接到j(luò)的路徑短，設(shè)置dis(i,j)＝dis(i,k)+dis(k,j)；其中，k≠i，j；

c)重復(fù)步驟b)，直至遍歷所有公交站點(diǎn)k，dis(i,j)即公交站點(diǎn)i到公交站點(diǎn)j的最少換乘次數(shù)；

dis(i,j)=Σl=ijWl+n×T]]>

其中，為公交站點(diǎn)i與公交站點(diǎn)j之間所有邊的權(quán)值之和，n為轉(zhuǎn)車次數(shù)，T為每次換乘時的平均等待時間，T為經(jīng)驗值。

2.根據(jù)權(quán)利要求1所述的基于北斗定位與客流量的公交換乘優(yōu)化方法，其特征在于，所述公交數(shù)據(jù)通過車載北斗衛(wèi)星導(dǎo)航系統(tǒng)收集；同一公交線路中兩相鄰公交站點(diǎn)間的實(shí)際距離通過車載北斗定位設(shè)備獲取。