[發明專利]基于歐氏距離收費的彈性公交即時需求動態響應方法

有效

• 申請號: 202110257728.2
• 申請日: 2021-03-09
• 公開（公告）號: CN113096430B
• 公開（公告）日: 2022-04-01
• 發明（設計）人: 汪怡然;王岳平;陳景旭;劉志遠;陳文棟;史云陽
• 申請（專利權）人: 東南大學
• 主分類號: G08G1/123
• 分類號: G08G1/123;G07B15/02
• 代理公司: 南京經緯專利商標代理有限公司 32200
• 代理人: 徐爾東

1.一種基于歐氏距離收費的彈性公交即時需求動態響應方法，其特征在于：具體包括以下步驟：

第一步，輸入彈性公交網內運行中的車輛信息和即時乘客請求，車輛按照預定的線路及時刻表運行；

第二步，在運行途中，乘客出現遲到情況，該乘客行程被取消，同時車輛線路及時刻表信息進行對應更新；

第三步，接收乘客新的需求，更新彈性公交網絡內所有彈性公交車輛的運行狀態，利用車輛服務范圍以及節點插入法確定新需求的備選線路；

第四步，根據確定的備選線路中出行的歐式距離計算每位乘客的票價，從而獲取每條備選線路的預期收益，選取收益最大的備選線路為最佳服務方案；

第一步中，彈性公交網中的線路信息包括途徑站點順序、運行時刻表和服務乘客信息，每位乘客的需求p包括五個要素，分別為乘客發出該需求的時間t^p、上車站點o_p、下車站點d_p、乘客到達上車站點的時間和乘客到達下車站點的時間

乘客能接受的最長等待時間為w，即若車輛早于時刻到達上車站點需等待，但不可晚于時刻到達，乘客的實際送達時間是不晚于的任何時間，乘客上下車和車輛重新啟動的耗時為t₀，車輛的額定載客容量為cap；

所有處于運營狀態的彈性公交車輛集為L，每輛車的運行軌跡與實時需求緊密相關，即每輛車與車輛運行線路是唯一對應關系；彈性公交車輛在線路各站點的時刻表與乘客時間窗應滿足如下關系：

⑴車輛到達線路l上某站點j的時間計算如下：

其中表示車輛到達某公交站點j的時刻，為0,1變量，取1表示線路l經過路段A_i,j，表示車輛離開某公交站點i的時刻，t_i,j表示車輛從站點i到站點j的運行時長；

⑵車輛在線路l的接乘站點i處的到達和離開時間應滿足：

⑶車輛在線路l的送達站點i處的到達和離開時間應滿足：

⑷當線路l的同一站點i有多位乘客上車或下車時，車輛的離開時間應滿足:

若乘客遲到，則到達o_p的實際時間為若早于車輛到達o_p的時間，則乘客仍然能夠乘車；若乘客出現遲到情況，該乘客的行程將被取消，并將乘客下車站點d_p從原定線路中刪去，然后按照式(1)-(6)更新后續線路時刻表；

第三步中接收乘客新的需求，更新彈性公交網絡內所有彈性公交線路的運行狀態，利用車輛服務范圍以及節點插入法確定新需求的備選線路的具體步驟包括：

第3.1步，將新需求記為p，能夠為需求p提供服務的線路集記為L_p，逐一比對所有在途車輛的后續運行線路與新需求p的上、下車站點，若某線路l即將經過的站點中同時存在與乘客的上、下車站點間距小于R的車站，轉入第3.2步，否則取下一條線路繼續嘗試，其中，R表示以車輛所在位置為圓心，車輛服務范圍區域的半徑；

第3.2步，利用節點插入算法將新需求的上車站點、下車站點插入到線路l中，并記錄所有可行方案，具體包括：

⑴上車站點o_p和下車站點d_p已在線路l中，分別記為點i和點j：

車輛到達o_p的時間若則按照式(1)-(6)更新點i和其之后的線路時刻表；否則當前線路l無法為需求p提供服務，取下一條線路繼續嘗試；

車輛到達d_p的時間若則按照式(1)-(6)更新點j和其之后的線路時刻表；否則當前線路l無法為需求p提供服務，取下一條線路繼續嘗試；

若更新后線路l的時刻表滿足該線路中所有乘客的時間窗約束，且任意時刻車上乘客數不超過額定容量，則記錄線路l更新后的信息，包括：時刻表，途徑站點順序和車輛載客情況，并將線路l計入集合L_p；否則當前線路l無法為需求p提供服務，取下一條線路繼續嘗試；

⑵下車站點d_p不在線路l中，上車站點o_p已在線路l中并記為點i：

車輛到達o_p的時間若則按照式(1)-(6)更新點i和其之后的線路時刻表；否則當前線路l無法為需求p提供服務，取下一條線路繼續嘗試；

遍歷線路l在點i之后的所有路段A_m,n，找出所有可行的下車站點d_p的插入方案：將d_p插入到站點m和站點n之間，車輛到達d_p的時間若則按照式(1)-(6)更新點d_p和其之后的線路時刻表，否則取下一路段繼續嘗試；

若更新后的時刻表滿足線路l中所有乘客的時間窗約束，且任意時刻車上乘客數不超過額定容量，則記錄線路l更新后的信息，包括：時刻表，途徑站點順序和車輛載客情況，并將線路l計入集合L_p，否則取下一路段繼續嘗試；

⑶上車站點o_p不在線路l中，下車站點d_p已在線路l中并記為點j：

遍歷線路l在點j之前的所有路段A_m,n，找出所有可行的上車站點o_p的插入方案：將o_p插入到站點m和站點n之間，車輛到達o_p的時間若則按照式(1)-(6)更新點o_p和其之后的線路時刻表，否則取下一路段繼續嘗試；

車輛到達d_p的時間若則按照式(1)-(6)更新點j和其之后的線路時刻表；否則當前線路l無法為需求p提供服務，取下一條線路繼續嘗試；

若更新后線路l的時刻表滿足該線路中所有乘客的時間窗約束，且任意時刻車上乘客數不超過額定容量，則記錄線路l更新后的信息，包括：時刻表，途徑站點順序和車輛載客情況，并將線路l計入集合L_p，否則取下一路段繼續嘗試；

⑷上車站點o_p和下車站點d_p都不在線路l中：

遍歷線路l中的所有路段A_i,j，找出所有可行的上車站點o_p的插入方案：將o_p插入到站點i和站點j之間，車輛到達o_p的時間若則按照式(1)-(6)更新站點o_p和其之后的線路時刻表，否則取下一路段繼續嘗試；

遍歷線路l中在點o_p之后的所有路段A_m,n，找出所有可行的下車站點d_p的插入方案：將d_p插入到站點m和站點n之間，車輛到達d_p的時間若則按照式(1)-(6)更新點d_p和其之后的線路時刻表，否則取下一路段繼續嘗試；

若更新后的時刻表滿足線路l中所有乘客的時間窗約束，且任意時刻車上乘客數不超過額定容量，則記錄線路l更新后的信息，包括：時刻表，途徑站點順序和車輛載客情況，并將線路l計入集合L_p，否則取下一路段繼續嘗試；

第3.3步，記錄并輸出上述過程產生的所有可行方案。

2.根據權利要求1所述的基于歐氏距離收費的彈性公交即時需求動態響應方法，其特征在于：第四步中，車票價格是出行需求中上車站點與下車站點間歐氏距離的線性函數，若乘客出現遲到，則無需支付票價，但是需要支付取消服務的手續費，乘客出行費用計算具體為：

其中，為乘客上下車站點間的歐氏距離，每公里票價為α₁，票價向上取整，α₂為乘客因遲到取消服務需要支付的手續費；

每條線路的運營收益為該條線路的乘客出行費用總和減去運營成本，運營成本與車輛運行距離成正比，線路l的運營收益計算如下：

其中，為0,1變量，取1表示由線路l為乘客提供服務，β為車輛每公里的運行成本，為0,1變量，取1表示線路l經過路段A_i,j，D_i,j為從i站點駛向j站點的距離；當線路尚未向乘客提供服務時，f_p按乘客正常乘車計，若線路已經過乘客的上車點，f_p按實際情況計算；

按上述方法計算出所有可行方案的收益，選取收益最大的作為最佳服務方案并更新路網信息。