[發明專利]一種公共交通線網優化方法

有效

• 申請號: 201811107059.5
• 申請日: 2018-09-21
• 公開（公告）號: CN109118023B
• 公開（公告）日: 2022-03-01
• 發明（設計）人: 馮雪松;張路凱;朱曉靜
• 申請（專利權）人: 北京交通大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/26;G06N3/12
• 代理公司: 北京市商泰律師事務所 11255
• 代理人: 黃曉軍

1.一種公共交通線網優化方法，其特征在于，所述方法在多目標模型中同時考慮運營者與出行者的利益，在滿足運營者利益的基礎上最大化出行者利益，將模擬退火算法與遺傳算法嵌套使用，求解多目標優化模型；所述模擬退火算法以最小化運營公司一天的總運營成本為目標構建目標函數；所述嵌套的遺傳算法以最小化出了行都的總出行時間為目標構建適應度函數，將運營者與出行者的利益朝著相互協調的角度推進，平衡二者之間的利益矛盾；包括如下步驟：

步驟S1，以模擬退火算法為框架，在所述框架下以最小化運營公司全天總運營成本為目標獲得初始線網；

步驟S2，對初始線網進行打散操作，形成若干個線網單元；

步驟S3，以打散后的線網單元為輸入網絡，以最小化所有出行者總出行時間為目標構建公共交通線網優化模型，進行遺傳算法優化；

步驟S4，輸出所述公共交通線網優化模型，對公共交通線網優化模型去除冗余線路后，形成簡化后的新線網；

步驟S5，通過最大迭代次數或終止溫度判斷是否達到收斂條件；是，則輸出計算結果，為最優結果；否，則以新線網為初始線網，轉入步驟S1；所述收斂條件為：最大迭代次數限制或終止溫度限制；

其中，所述模擬退火算法，進一步包括如下步驟：

步驟S21，參數設置；

步驟S22，計算線路所需的車輛數，按照車輛配備的原則對線網進行線網單元確定及車輛配備；

步驟S23，根據線網單元及車輛配備計算線網運營成本；

步驟S24，根據所計算的運營成本判斷是否滿足終止條件；

步驟S25，把經過運營成本比較后保留的線網按照單元打散原則，對線網進行打散，重新形成單元及新線網；所述打散操作，進一步為：將公共交通線網按照經過的路段拆分成一個或者有相鄰的幾個路段，將不同線路中經過同一或幾個相同車站的路段作為一個集合；所述單元為，某條線路中一個或者幾個路段的集合；

步驟S26，使用本算法中的遺傳算法流程對線網進行優化；所述遺傳算法，包括如下步驟：

步驟S261，遺傳算法參數設置及種群初始化；

步驟S262，判斷線網是否滿足約束條件限制；若公共交通線網滿足約束條件限制，保留本次線網結構，轉步驟S263；否則，不保留本次線網結構，轉步驟S264；

步驟S263，計算個體適應度，并保留適應度最高的公共交通線網；

步驟S264，對公共交通線網進行遺傳操作優化公共交通線網；在每代中采用基于輪盤賭進行選擇操作，基于隨機概率進行交叉操作與變異操作，并產生新線網；

步驟S265，判斷算法是否滿足終止條件；若所提出的遺傳算法迭代達到最大迭代次數，則轉入步驟S266；否則，轉步驟S262；

步驟S266，終止算法中的搜索過程，輸出適應度最高的個體。

2.根據權利要求1所述的公共交通線網優化方法，其特征在于，所述參數包括：初始溫度T₀、終止溫度T_stop、最大迭代次數I₁、退火控制速率D₁、控制溫度T^c、退回溫度T^p、迭代退回速率D₂與成本差控制變量C_A。

3.根據權利要求1所述的公共交通線網優化方法，其特征在于，所述步驟S22進一步包括：

步驟S221，尋找單元，計算單元重合度；將線網中的線路打散并形成單元，尋找單元，并按照從大到小的順序在線網中計算出單元重合度；

步驟S222，按照單元重合度按照小到大的順序，給每個經過單元的線路進行車輛配備與運力配置；

步驟S223，按照單元運力不足的處置措施，重新計算并調整線網上每條線路上所配的車輛數目；

步驟S224，重新計算并調整線網上每條線路上所配的車輛數目。

4.根據權利要求1所述的公共交通線網優化方法，其特征在于，所述步驟S261中的遺傳算法參數包括：種群規模、最大迭代代數I₂、交叉概率P_c、變異概率P_m。