[發(fā)明專利]一種候選公交線路計算方法、系統(tǒng)及電子設(shè)備

在審

• 申請?zhí)枺?/td>: 201710701148.1
• 申請日: 2017-08-16
• 公開（公告）號: CN107657330A
• 公開（公告）日: 2018-02-02
• 發(fā)明（設(shè)計）人: 肖露艷;范小朋;須成忠
• 申請（專利權(quán)）人: 深圳先進技術(shù)研究院
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06N3/00
• 代理公司: 深圳市科進知識產(chǎn)權(quán)代理事務所(普通合伙)44316
• 代理人: 趙勍毅

1.一種候選公交線路計算方法，其特征在于，包括：

步驟a：根據(jù)篩選規(guī)則對候選公交站點集合進行篩選，根據(jù)篩選后的候選公交站點構(gòu)建初始候選公交線路圖；

步驟b：對所述初始候選公交線路圖進行剪枝，得到最終候選公交線路圖；

步驟c：基于公交線路生成算法，計算出所述最終候選公交線路圖中在最大行駛時間內(nèi)達到最大客流量的公交線路，得到最優(yōu)候選公交線路。

2.根據(jù)權(quán)利要求1所述的候選公交線路計算方法，其特征在于，在所述步驟a中，所述根據(jù)篩選規(guī)則對候選公交站點集合進行篩選具體包括：

步驟a1：計算候選公交站點集合中任意兩個相鄰公交站點間的距離，并篩選出站點間距離不超過DistanceLimit的候選公交站點；其中，DistanceLimit表示任意兩個相鄰公交站點間的最遠距離不能超過的值；

步驟a2：篩選出候選公交站點集合中線路朝終點站方向前進的候選公交站點作為當前站點的下一站點；

步驟a3：計算所述下一站點與起始站間的距離，并篩選出滿足公式dist(G_i+1,G₁)>dist(G_i,G₁)(i＝1,2,3,…,n-1)的候選公交站點；其中，G₁為起始站，G_i為當前站點，G_i+1為當前站點的下一站點；

步驟a4：計算所述下一站點與終點站間的距離，并篩選出滿足公式dist(G_i+1,G_n)<dist(G_i,G_n)(i＝1,2,3,…,n-1)的候選公交站點；其中，G_n為終點站。

3.根據(jù)權(quán)利要求2所述的候選公交線路計算方法，其特征在于，在所述步驟a中，所述根據(jù)篩選后的候選公交站點構(gòu)建初始候選公交線路圖具體為：根據(jù)篩選后的候選公交站點生成候選公交線路，從生成的候選公交線路中篩選出滿足公式的優(yōu)選候選公交線路，并根據(jù)所述優(yōu)選候選公交線路生成初始候選公交線路圖。

4.根據(jù)權(quán)利要求1至3任一項所述的候選公交線路計算方法，其特征在于，在所述步驟b中，所述對初始候選公交線路圖進行剪枝具體包括：

步驟b1：計算初始候選公交線路圖中除起始站和終點站之外的所有候選公交站點的入度，并迭代刪除入度是零的候選公交站點及對應的邊；

步驟a2：計算初始候選公交線路圖中除起始站和終點站之外的所有候選公交站點的出度，并迭代刪除出度是零的候選公交站點及對應的邊。

5.根據(jù)權(quán)利要求1所述的候選公交線路計算方法，其特征在于，在所述步驟c中，所述基于公交線路生成算法計算出最終候選公交線路圖中在最大行駛時間內(nèi)達到最大客流量的公交線路具體包括：

步驟c1：初始化候選公交線路集合為空集；

步驟c2：初始化當前線路所經(jīng)過的前驅(qū)站點集合為空集；

步驟c3：初始化起始點為當前站點，并將當前站點加入當前線路的前驅(qū)站點集合中；

步驟c4：計算當前站點的所有可能選擇的下一站點被選擇的概率；

步驟c5：根據(jù)步驟c4的計算結(jié)果，使用輪盤賭概率選擇算法選取當前站點的下一站點；

步驟c6：設(shè)所述下一站點為當前站點，并將當前站點加入當前線路的前驅(qū)站點集合中；

步驟c7：重復執(zhí)行步驟c4至步驟c6，直到當前站點為終點站；

步驟c8：將能夠到達終點站的前驅(qū)站點集合添加到候選公交線路集合中；

步驟c9：重復執(zhí)行步驟c2至步驟c8，直到所述候選公交線路集合中不再添加新的前驅(qū)站點集合；

步驟c10：根據(jù)最大行駛時間過濾所述候選公交線路集合；

步驟c11：按照總客流量對過濾后的候選公交線路集合進行排序，獲得候選公交線路集合中具有最大客流量的候選公交線路。