[發明專利]一種解決無限維交通分配問題的方法及裝置

有效

• 申請號: 202011601879.7
• 申請日: 2020-12-30
• 公開（公告）號: CN112687104B
• 公開（公告）日: 2021-09-28
• 發明（設計）人: 謝軍;王倩妮;聶宇;唐優華;劉曉波;馮時
• 申請（專利權）人: 西南交通大學;成都交大大數據科技有限公司
• 主分類號: G08G1/01
• 分類號: G08G1/01;G08G1/0968;G06Q10/06
• 代理公司: 北京集智東方知識產權代理有限公司 11578
• 代理人: 劉林;陳攀

本發明提供了一種解決無限維交通分配問題的方法及裝置，所述方法包括：獲取路網基本參數、主循環最大步數和內循環最大步數，基于所述路網基本參數獲得路網中各O?D對形成的各路段流量、各路徑流量和路徑集；執行主循環，得到第一結果；執行內循環，得到第二結果；基于所述第一結果和所述第二結果，計算路網收斂指標；多次連續執行主循環和內循環直至收斂，或者達到最大循環步數，所述最大循環步數為內循環最大循環步數或主循環最大循環步數，輸出最終達到均衡狀態的路徑集、路徑流量和各路段流量。基于本發明中的方法可以使無限維雙準則流量分配問題更快收斂至更高精度，求得基于路段算法無法得到的路徑流量均衡解。

技術領域

本發明涉及交通分配技術領域，具體而言，涉及一種解決無限維交通分配問題的方法及裝置。

背景技術

無限維雙準則交通分配問題可以看做是標準交通分配問題的擴展，與標準交通分配問題相比，每個用戶在選擇路徑時都會考慮自身的時間價值結合時間和金錢兩個準則選擇廣義費用最小的路徑出行，達到無限維雙準則均衡時每個用戶都不能通過更改選擇的路徑降低自身的出行廣義成本。無限維雙準則問題中使用一個連續分布描述每個用戶的時間價值，因而被稱為“無限維”。

標準交通分配問題求解算法可以按照對路網拓撲結構的分解分為：基于路段、基于路徑和基于起點三大類。其中基于路徑的算法需要存儲大量路徑，由于上世紀八九十年代計算機硬件條件的限制，基于路徑的算法一直不被看好。與此同時，由于無限維雙準則問題的復雜性，對于無限維雙準則交通分配算法的開發僅停留在基于路段的層面。目前能夠求解無限維路網問題的算法主要是基于Frank-Wolfe(F-W)算法進行改進的，該類算法求解前期收斂快，后期由于迭代方向與最速下降方向近乎垂直而下降緩慢，且收斂精度低。

發明內容

本發明的目的在于提供一種解決無限維交通分配問題的方法及裝置，以改善上述問題。

為了實現上述目的，本申請實施例提供了如下技術方案：

一方面，本申請實施例提供了一種解決無限維交通分配問題的方法，所述方法包括：獲取路網基本參數、主循環最大步數和內循環最大步數，基于所述路網基本參數獲得路網中各O-D對形成的各路段流量、各路徑流量和路徑集；執行主循環，對路網中各O-D對添加新的有效路徑至路徑集，對各O-D對執行邊界調整或流量調整，得到第一結果；執行內循環，多次對路網中收斂指標低于路網收斂指標的O-D對執行邊界調整或流量調整，刪除未被使用的路徑，得到第二結果；基于所述第一結果和所述第二結果，計算路網收斂指標；多次連續執行主循環和內循環直至收斂，或者多次連續執行主循環和內循環達到最大循環步數，所述最大循環步數為內循環最大循環步數或主循環最大循環步數，輸出最終達到均衡狀態的路徑集、路徑流量和各路段流量。

可選的，獲取路網基本參數、主循環最大步數和內循環最大步數，基于所述路網基本參數獲得路網中各O-D對形成的各路段流量、各路徑流量和路徑集，包括：

獲取路網基本參數，所述路網基本參數包括各路段自由流通行時間和路網出行需求，計算路網中每個O-D對的雙準則有效路徑及分界；

將每個O-D對對應的所述路網出行需求按當前有效路徑和分界情況分配至每個O-D對中的各路徑；

根據分配后各路段流量，更新各路段的通行時間，得到各路段流量、各路徑流量和路徑集。

可選的，根據每個路段更新后的通行時間，計算得到當前路段通行時間下的新有效路徑集，將新有效路徑集中存在且路徑集中不存在的路徑添加至路徑集中，得到新的路徑集。

可選的，所述執行邊界調整，包括：

獲取當前循環步數、各路段流量、O-D對的路徑集和所述路徑集中每個路徑的流量，將所述路徑集中的各路徑按通行費用降序排列，按該降序順序計算相鄰兩兩路徑對應的邊界變量，并將全部邊界變量選取狀態設定為未選取；