[發明專利]一種解決路徑選擇實時性問題以避免局部擁堵的方法

有效

• 申請號: 201711311832.5
• 申請日: 2017-12-11
• 公開（公告）號: CN108597246B
• 公開（公告）日: 2020-10-13
• 發明（設計）人: 胡文斌;聶聰;張成;邱振宇;杜博
• 申請（專利權）人: 武漢大學
• 主分類號: G08G1/0968
• 分類號: G08G1/0968;G06Q10/04
• 代理公司: 武漢科皓知識產權代理事務所(特殊普通合伙) 42222
• 代理人: 魏波

1.一種解決路徑選擇實時性問題以避免局部擁堵的方法，其特征在于，包括以下步驟：

步驟1：構建城市交通路網的實時動態多路口路徑選擇模型；

步驟1的具體實現過程是：

將真實路網映射為路網模型有向圖G(L，E)，其中，將真實路網中的路口映射為節點L，Li表示單個路口，i＝1、2、3、...、c，其中c為路口總數；將真實路網中的路段映射為節點間帶方向的矢量箭頭E，E_j包含兩個路口，表示某一側路段，j＝1、2、3、...、r，其中r為路網中路段總數；將路網中所有行駛的車輛集合用V表示，路網中單個車輛用Vk表示，其中，k＝1、2、3、...、n，n為路網中行駛的車輛總數；

對于車輛V_k，其當前位置為Ls，其目的地為Lt，則路徑用路口集合{Ls，Lj，...，Lt}表示，可行的一個路徑選擇表示為Route_s，t＝{Ls，Lj，...，Lt}；路網中每個車輛被選擇一個路徑，所有車輛的路徑構成一次路徑選擇，表示為路徑集合這樣的一個路徑集合稱為一次路徑選擇；

步驟2：構建效用值評價模型，通過效用值大小評判路徑選擇方案的優劣；

其中，效用值F的計算公式為：

F＝Z-K (1)

其中，影響路徑選擇方案效用值F的因素有很多，包括不變因素和變化因數，不變因素整合為偏好值Z，變化因素整合為成本值K；

所述偏好值Z的計算公式為：

其中，表示路段是否可抵達，取值范圍為{1，0}，1表示可達，0表示不可達；表示路段狀況，取值范圍為[0，1]，路面狀況越好，該值越大；表示速度限制，取值范圍為[0，1]，速度限制越少，取值越大；Zl表示路段照明狀況，取值范圍為[0，1]，照明條件越好，該值越大，白天設置為1；表示司機對推薦導航方案的順從程度，取值范圍為[0，1]，順從程度越大，該值越大；表示司機對路段的熟悉程度，取值范圍為[0，1]，越熟悉的道路，取值越大；

∈_i(i＝1，2......5)是偏好值Z的各影響因素對應的獨立乘法因子，其值與城市規模、決策目標的設定相關，乘法因子數值越大，其對應的影響因素越重要，計算偏好值時所占的權重比例越大，對偏好的影響越大；

所述成本值K的計算公式為：

其中，Ka表示突發的交通事故或臨時管制等帶來的道路影響，取值范圍為[0，1]∪{INF}[0，1]，影響程度越大，該值越大，INF表示無法通行；表示所選路徑耗費的時間代價，取值范圍為(0，∞)；Kd表示所選路徑耗費的距離代價，取值范圍為(0，∞)；表示所選路徑耗費的油量代價，取值范圍為(0，∞)；Kl表示交通燈的影響，取值范圍為[0，1]，所選路徑交通燈等待時間越長，該值越大；

ω_i(i＝1，2......5)是成本值K的各影響因素的獨立乘法因子，其值與城市規模、決策目標設定相關，它們的大小分別代表了各影響因素對成本值K的影響程度，也代表了其重要程度；

一個路段中的擁堵系數γ為：

其中，H為路段的閾值容量，R為路段的擁堵容量，τ為當前路段中的車輛數；一個路段中的擁堵系數確定之后，相對應路段的油量代價和時間代價也相應計算得到；

步驟3：最優路徑選擇；

步驟3中的具體實現包括以下子步驟：

步驟3.1：在對車輛道路進行量子編碼的前提下，對實際交通狀況進行轉換編碼，構建量子染色體；

其中，利用QCIS策略對實際交通狀況進行轉換編碼，具體實現包括以下子步驟：

步驟3.1.1：基于車輛對路段進行量子遺傳編碼，車輛與每一個路段的關系用一個量子位表示；對于某一確定車輛與某一路網中路段來說，其關系有兩種：該車輛經過該路段和該車輛不經過該路段，|0＞態表示車輛不經過該路段，|1＞態表示車輛經過該路段；

使用量子位編碼時，對于單獨的一輛車需要構建的量子染色體編碼規模為2r，對于一個種群的量子染色體編碼規模則為2n×r，則一次算法所需要的量子染色體編碼規模為2m×n×r；

單個車輛的量子染色體編碼記為U，表達式為：

其中，r為路網中路段編號，n為路網中車輛編號，c為路段中路口編號，m為量子種群數量；α_i表示量子態|0態的概率幅，β_i表示量子態|1態的概率幅，1≤i≤n；

步驟3.1.2：確定路網中路段編號與路口編號對應關系集E_i＝(L_s，L_t)，s，t∈{1，2，...，c}；其中，L_s表示當前位置，L_t表示目的地；

步驟3.1.3：確定車輛對應量子染色體各段的編碼方式；

對于種群P_i中的每一輛車V_j，其初始化編碼方式為：對于V_j的第到第段量子染色體，|0態的編碼為|1態的編碼為對于V_j的其他段的量子染色體，其|1態的編碼為|0態的編碼為其中，i＝1、2、......、m，j＝1、2、......、n；x表示染色體序號，L表示染色體總數；

步驟3.1.4：對量子染色體按照選擇好的編碼方式進行賦值編碼；

步驟3.1.5：編碼完成后輸出初代量子染色體Bm；

步驟3.2：將量子染色體的計算位轉化為針對不同車輛的路徑選擇結果；

步驟3.3：對當前的路徑選擇結果優劣進行評判；

步驟3.4：對種群的量子編碼進行迭代更新。