[發明專利]一種用于滿足出行續航要求的交通網絡均衡計算方法

有效

• 申請號: 201710492915.2
• 申請日: 2017-06-26
• 公開（公告）號: CN107103169B
• 公開（公告）日: 2020-03-24
• 發明（設計）人: 謝馳;劉海洋
• 申請（專利權）人: 上海交通大學
• 主分類號: G06F30/20
• 分類號: G06F30/20
• 代理公司: 上海伯瑞杰知識產權代理有限公司 31227
• 代理人: 孟旭彤

1.一種用于滿足出行續航要求的交通網絡均衡計算方法，包括以下計算步驟：

步驟1：建立含有滿足出行續航的充能站的道路系統抽象網絡，該網絡包括始發點、終到點、普通節點和充能節點，而出行者路徑則分為完整路徑、子路徑，以及子路徑中進一步分類為的純子路徑和可行子路徑，建立在充能站點確定情況下的各個路徑集合；

步驟2：建立滿足出行續航要求的交通網絡均衡模型，包括目標函數與約束，其中目標函數為：

(1)式中，c_ij(ω)為出行費用函數，x_ij為路段ij上的流量，∑_(i，j)表示對所有路段求和，表示對出行費用函數求積分并取值為x_ij和0，

約束包括，流量守恒約束式(2)和流量非負約束式(3)：

其中，表示起點r到訖點s間路徑k的流量，g_rs表示起點r到訖點s間的總需求量，表示對于任意的，W為起訖點集合，K_rs為起訖點rs間的路徑集合，式(1)至(3)與傳統的貝克曼用戶均衡模型構建方式保持一致，

約束還包括式(4)至式(6)：

其中，式(4)為路徑流量與路徑指示變量守恒約束，M為很大的一個常數，為起點r到訖點s間路徑k的路徑指示變量，

式(4)指出當時，

當時，則

式(5)規定了路徑與其子路徑之間的關系，為路段與路徑關系指示系數，如果則起點r到訖點s間路徑k包含路段ij，

則是將擴展到子路徑pq之間，

則是將擴展到子路徑pq之間，

如果則對于路徑上的任意路段，

這里，式(5)確保有且僅有一個子路徑覆蓋此路段，即確保了不同激活的子路徑之間不存在重疊，

式(6)限制了任意激活的子路徑的長度不能超過里程限制，為起點r到訖點s間路徑k的子路徑pq之間的出行距離，

D為車輛具有滿能量時能夠行駛的全部里程數，

為起點r到訖點s間路徑k包含的續航站點集合，

以及式(7)和式(8)：

式(7)和式(8)分別規定了變量與為0/1變量，取值為0或1，

變量x_ij和滿足式(9)和(10)約定的關系，

步驟3：在步驟1提供的抽象路網中，利用步驟2提供的模型特性，使用向量投影均衡方法求解建立的滿足出行續航要求的網絡均衡模型。

2.如權利要求1所述的用于滿足出行續航要求的交通網絡均衡計算方法，其特征在于，在步驟3中，向量投影均衡法的具體步驟如下：

步驟(1)：計算初始可行解，

首先，給出交通出行費用函數取為如式：

其中，為自由流出行時間，V_ij為最大流量數，α_ij和β_ij為方程的參數，

交通出行費用函數描述了路段出行時間隨著流量的增加而增加的關系，確定初始可行解時，將流量x_ij取為0，使用最短路算法求出網絡中的最短路，在最短路上加載全部需求后，更新路段流量x_ij，即得到了初始可行解

其中的最短路算法采用滿足續航要求的距離限制最短路算法；

步驟(2)：計算下降方向，下降方向的計算式為：

其中，d_k為向量投影方向變量，為流量不為0的路徑的平均出行費用，c_k為路徑k的出行費用，如果d_k的絕對值小于一個預設的參數，則轉入步驟(5)，

步驟(3)：計算最優迭代步長，通過求解如下子問題得到最優迭代步長λ^*，

其中，為其它起訖點間的固定流量，為附加流量；

步驟(4)：更新路徑流量和路段流量，通過下式更新路徑與路段流量：

如果路徑的流量等于0，則從路徑集中刪除該路徑；

步驟(5)：采用滿足續航要求的距離限制最短路算法再次計算最短路費用，如果該費用小于當前最小值，則將這一路徑加入到路徑集合中，并返回到步驟(2)，否則停止迭代。

3.如權利要求2所述的用于滿足出行續航要求的交通網絡均衡計算方法，其特征在于，

其中的最短路算法采用滿足續航要求的距離限制最短路算法(constrained shortestpath problem with relays，CSPP-R)，該算法的具體步驟為：

步驟①：初始化，賦值M_dj←0，nX←1，l_nX←[0，0，-，s]，X←1，

其中，M_dj為儲存具有最優目標函數值標簽的索引對于每個距離限制d和節點j，←符號表示為某一變量賦值，nX為第n次迭代的工作變量，l_nX工作變量的標簽；

步驟②：標簽處理，當X不為空集時，執行：x←X中元素，X-{x)，i←β_x，對于所有j∈N執行如下循環：如果i≠t，其中，β_x為最后的節點，為路徑的出行費用，w_ij為路段的出行距離，

如果M_0j＝0或者M_0j≠0和則nX←nX+1，M_0j＝nX，X←X∪{nX}，其中，r_j為車輛在充能站的花費，

如果M_dj＝0或者M_dj≠0和則nX←nX+1，M_dj＝nX，X←X∪{nX}；

步驟③：通過標簽M._t中最優值π^f反向追蹤出最短路p。