[發明專利]一種用于城市交通網絡應急疏散規劃的新型啟發式算法

在審

• 申請號: 201710670436.5
• 申請日: 2017-08-08
• 公開（公告）號: CN107341580A
• 公開（公告）日: 2017-11-10
• 發明（設計）人: 謝馳;萬炎杰;劉海洋
• 申請（專利權）人: 上海交通大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/06;G06Q50/26
• 代理公司: 上海伯瑞杰知識產權代理有限公司31227
• 代理人: 孟旭彤

1.一種用于城市交通網絡應急疏散規劃的新型啟發式算法，其特征在于，包括如下步驟：

1)建立城市應急疏散網絡

首先針對特定的建筑或公共場所做好疏散預案，確定進行疏散的區域范圍，并依據區域范圍建立應急疏散網絡；所述應急疏散網絡具有若干起點和終點，疏散人員通過起點通行至終點，逃離出疏散的區域范圍；

2)建立適用于應急疏散網絡的優化模型

針對應急疏散網絡建立雙層模型，雙層模型包括上層模型和下層模型；

所述上層模型用于優化整體疏散時間，其過程如下：

目標函數：

對道路同行容量的約束：

對連接體的約束條件：

連接體與道路數量關系約束：

所述下層模型為動態交通分配模型，其過程如下：

目標函數：

約束條件

上述公式中集合、參數和變量的含義如下：

集合

C表示路段元胞集合，在動態交通分配中，設每個路段或路口為一個元胞；C_S表示元胞集合；C_R表示源元胞集合，交通流由源元胞產生；E表示連接體集合；E_S表示終點連接體集合；E_R表示路段連接體集合；E_I表示交叉口連接體集合；表示指向元胞ρ的連接體集合；表示從元胞ρ出發的連接體集合；表示指向元胞ρ的上游元胞集合；表示從元胞ρ出發的連接器指向的下游元胞集合；T表示進行疏散規劃的分段時間區間集合；

參數

c_ρ表示元胞ρ內允許的最大車輛數；q_ρ表示元胞ρ允許進出的最大車輛數；在一個路段兩個方向ι→κ和θ→ρ上的路段數量；表示在時間區間t內元胞ρ的自然流速率；M_t表示時間區間t內產生用戶最優交通流的成本；ζ_ρ表示元胞ρ內初始車輛數；表示時間區間t內從元胞ρ產生的疏散需求；

變量

n_ρ表示元胞ρ內路段數；n_ικ表示在元胞序列ι→κ上的路段數量；表示時間區間t內元胞ρ內的車輛數；表示時間區間t內從元胞θ向元胞ρ移動的車輛數；y_ηι代表連接體η→ι之間連接狀態的變量(y_ηι＝1或0)；z_ικ代表元胞ι→κ之間連接狀態的變量(z_ικ＝1或0)；

3)采用拉格朗日松弛-禁忌搜索算法急疏散規劃問題進行優化

首先使用拉格朗日松弛技術進行松弛，上層模型變為：

where(y_ηι+y_ρσ-1)⁺＝max(0，y_ηι+y_ρσ-1)

s.t.constraints 2-4,9-21

其中，是拉格朗日乘子，y_ηι+y_ρσ-1代表了在每個交叉口處的交點數，是基于交點的成本；

4)求解拉格朗日松弛問題

從一個疏散網絡可行解開始，通過搜索更新迭代網絡狀態，直到滿足停止準則，輸出最終結果，其過程如下：

4.1)在可行解空間S中隨機選擇一個初始可行解g，令g^*＝g，i＝0，j＝0，在迭代過程中，用g^*來表示當前獲得最好的解，i代表迭代次數，j代表局部搜索次數；

4.2)從上一步得到的g^*出發，進行一次多樣化移動：即隨機改變g^*的一個交叉口的連接，得到當前可行解g；

4.3)在第二步當前可行解的附近生成一個鄰域N(g)，依據藐視準則和近因記憶在鄰域N(g)中生成一個子集S^*；

4.4)在S^*中選擇一個精英子集，在精英子集中進行局部移動，并更新藐視準則、拉格朗日乘子、近因記憶、頻率記憶、當前可行解g和歷史最優解g^*；

4.5)如果鄰域搜索的停止準則被滿足，那么進行下一步；否則，重復4.4)；

4.6)如果停止準則被滿足，那么停止搜索；否則，跳到4.1)。