[發明專利]基于快速響應乘車請求的非定線公共交通控制系統

有效

• 申請號: 201911092256.9
• 申請日: 2019-11-11
• 公開（公告）號: CN110782651B
• 公開（公告）日: 2021-06-29
• 發明（設計）人: 伍民友;孔令和;李寧;舒葦
• 申請（專利權）人: 上海交通大學
• 主分類號: G08G1/00
• 分類號: G08G1/00;G08G1/123
• 代理公司: 上海交達專利事務所 31201
• 代理人: 王毓理;王錫麟

1.一種基于快速響應乘車請求的非定線公共交通控制系統，其特征在于，包括：通信模塊、數據模塊、請求分配和路徑規劃模塊和轉乘規劃模塊，其中：通信模塊分別從乘客終端收集乘車請求信息、從公交車的車載控制系統收集車輛的實時未行駛路徑信息并更新至數據模塊、從數據模塊獲取更新的路徑信息并發送至受影響的乘客和車輛；請求分配和路徑規劃模塊從數據模塊中抽取未分配的請求信息并分配至不同的公交車的同時，為其規劃更新的路徑信息后更新至數據模塊；轉乘規劃模塊從數據模塊的路徑信息中掃描得到最新分配的乘客，為其中乘車距離最長的乘客安排最優的后車及轉乘站點的同時，為對應的前車和后車規劃更新的路徑信息并更新至數據模塊；

所述的乘車請求信息包括乘客的出發地點和目標地點、乘客所能容忍的繞路比上限、等車時間上限和走路距離上限等由乘客設定的信息以及發出請求時的時間戳；

所述的請求分配是指：將一批乘客的乘車請求分配給不同的公交車，并使對應的公交車路徑的新增長度總和最小，其優化目標和限制條件分別為：

優化目標：最小化∑(D′_i-D_i)，其中D_i和D′_i分別為算法執行前后第i輛公交車的未行駛路徑總長度；

限制條件包括：

1)公交車的載客人數C≤C_M，其中C_M為所有公交車一致的載客人數上限；

2)每個乘客的繞路比(d_j-sd_j)/sd_j≤δ_j，其中d_j和sd_j分別為第j個乘客實際乘車距離和上下車站點間的最短距離，δ_j為乘客在乘車請求中設定的繞路比上限；

3)等待時間t_j≤σ_j，其中σ_j為乘客在乘車請求中設定的等待時間上限；

4)走路距離wd_j≤ω_j，其中ω_j為乘客在乘車請求中設定的走路距離上限，wd_j＝a_j+z_j，上車前的走路距離a_j和下車后的走路距離z_j；

5)轉乘次數k_j≤K，其中K為轉乘次數上限；

6)保證原路徑的接送點順序不變；

所述的請求分配和路徑規劃模塊采用基于依照貪心策略設計的矩陣值選擇方法對于所有待分配的乘車請求，分別計算該請求分配給每輛公交車導致其路徑新增長度的最小值，即請求對該公交車的分配代價；當該公交車接送該乘客的所有路徑規劃方案都會導致上述任意限制條件失效，則分配代價為無窮大，以此分配代價構造一個分配代價矩陣，其行對應每個乘車請求，其列對應每輛公交車，每次在矩陣中選擇最小的分配代價，然后將該代價對應的乘車請求分配給對應的公交車，并構造該公交車的最優路徑；在此之后，將該乘車請求對應的行從矩陣中刪除并更新剩余的所有請求對該公交車的分配代價；不斷執行上述選擇、分配并構造路徑、刪除和更新操作，直到所有行均被刪除，所有乘客都以局部最小代價實現分配。

2.根據權利要求1所述的系統，其特征是，所述的分配代價具體為：根據接送點確定可供插入的位置，即乘客上車站點和下車站點，并確定插入方案的個數，在插入該乘客的上下車站點時確定滿足：

①包括該乘客在內的所有乘客的限制條件不被破壞，否則將該插入方案判定為無效；

②當所有插入方案都被判定為無效時，設置該乘客對該公交車的分配代價設為無窮大；否則：

③對于所有有效的插入方案，插入后得到的新路徑長度減去插入前的長度即為該插入方案的插入代價，從所有的插入代價中選擇最小值，作為該乘客對該公交車的分配代價；

所述的插入是指在公交車現有路徑的兩個相鄰站點間或路徑末尾新增一個需要訪問的站點，從而改變公交車的站點訪問順序。