[發明專利]一種基于線路候選集的地鐵接駁巴士線路規劃方法

有效

• 申請號: 201711234971.2
• 申請日: 2017-11-30
• 公開（公告）號: CN107798440B
• 公開（公告）日: 2021-04-20
• 發明（設計）人: 孔祥杰;田愷琦;李夢琳;劉曉騰;萬良田;夏鋒
• 申請（專利權）人: 大連理工大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/30
• 代理公司: 大連理工大學專利中心 21200
• 代理人: 溫福雪;侯明遠

1.一種基于線路候選集的地鐵接駁巴士線路規劃方法，其特征在于，步驟如下：

S1：對原始乘客出行數據進行預處理

S1.1：數據清洗：對原始乘客出行數據進行清洗，刪除異常數據，并將數據規范化；原始乘客出行數據包括訂單數據、站點位置數據和站點時間數據；

S1.2：數據篩選：根據線路規劃目標，選定研究時間范圍，并篩選出研究時間范圍內的非現金乘客的訂單記錄；

S1.3：數據提取：根據線路規劃目標，從訂單數據中提取線路規劃信息；

S2：對預處理后的數據進行時間劃分和空間聚合

S2.1：時間劃分：根據地鐵接駁巴士行車規律，將研究時間范圍劃分為n個時間片；

S2.2：空間聚合：根據站點位置數據，將研究空間聚合到m個站點；

S2.3：基于時間劃分和空間聚合，提取站點在每個時間片的上車人數，并以客流特征矩陣形式存儲，該矩陣記為D_n*m，n表示時間片數，m表示站點數，矩陣中的每個元素D_i,j表示第i個時間片第j個站點的上車人數；每個時間片i具有起始時間start_time和終止時間end_time兩個屬性；

S3：根據站點數據生成線路候選集合

S3.1：基于站點位置數據和站點間相對位置，篩選出適合作為起點的站點，并構建起點候選集Origin_c；

S3.2：根據S3.1構建的起點候選集Origin_c，結合站點位置數據，遵從整體向前的原則，即下一個站點總是離終點更近，對每一個起點遞歸遍歷，生成所有合理的線路，并構建線路候選集Route_c；Route_c中每條線路包括線路上所有站點的信息，每個站點信息包含站點名stop_name和到達時間arrive_time；

S4：從線路候選集合中選擇最優的運行線路

S4.1：根據地鐵接駁巴士發車規律，從起點候選集Origin_c中選擇一個站點作為線路起點，該站點包含站點名stop_name和發車時間arrive_time，將其存入一個列表，記作list_route；構建一個列表，記錄本條線路在每個站點的上車人數，記為list_passengers；

S4.2：基于S4.1選擇的線路起點，結合線路候選集Route_c和站點時間數據中提取的站點間到達時間，生成下一個站點的候選站點集合和該站點的到達時間，下一個站點候選集合記為Next_c；

S4.3：根據客流特征矩陣D_n*m，從下一個站點候選集合Next_c中選出客流量最多的一個站點信息S_c，作為下一個站點追加到list_route；

S4.4：根據客流特征矩陣D_n*m，和步驟S4.3中選出的站點信息S_c，計算出上車人數num_up，并追加到list_passengers中，num_up計算公式如下：

其中，S_c[arrive_time]表示站點信息S_c的arrive_time屬性，i[start_time]表示第i個時間片的start_time屬性，i[end_time]表示第i個時間片的end_time屬性，rate表示接走的乘客數占該站點總人數的比例；

S4.5：根據步驟S4.1得到的list_passengers和研究目標車輛的最大乘客數seats，對list_passengers中各站點上車人數進行加和，其結果若不大于seats，則對客流特征矩陣 D_n*m進行如下更新：

D_{n,j(n＝0,1,2…,i-1)}←0

D_i,j←D_i,j*rate

否則，對客流特征矩陣 D_n*m進行如下更新：

D_{n,j(n＝0,1,2…,i-1)}←0

D_i,j←D_i,j*rate+(∑list_passengers-seats)

加入終點站點信息并結束該條線路；

S4.6：重復步驟S4.2-S4.5，直到選出的站點信息S_c為終點，所得list_route即為最優線路。