[發明專利]一種基于多目標遺傳算法的共享單車停放點分配方法

有效

• 申請號: 202010300457.X
• 申請日: 2020-04-16
• 公開（公告）號: CN111582552B
• 公開（公告）日: 2023-04-25
• 發明（設計）人: 陳觀林;施嘉偉;翁文勇;楊武劍;李甜
• 申請（專利權）人: 浙江大學城市學院
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/0631;G06Q50/30;G06N3/126
• 代理公司: 杭州九洲專利事務所有限公司 33101
• 代理人: 張羽振

1.一種基于多目標遺傳算法的共享單車停放點分配方法，其特征在于，具體包括如下步驟：

S1、服務器收集在某時間點內的若干當前用戶請求數據；將請求數據中的坐標信息經過Geohash編碼成為字符串；將時間分段為T＝{1，2，3，…，t}，請求停車的車輛集合為I＝{1，2，3，…，i}，停放點集合為J＝{1，2，3，…，j}，目的地區域集合為P＝{1，2，3，…，p}；將每個用戶的請求數據存放至用戶請求信息表中；所述請求數據包括坐標信息、車輛編號、用戶編號和目的地區域p；

S2、服務器收集用戶的請求數據后，對用戶的坐標信息、目的地信息和附近可用停放點位置信息進行統計分析；某時間點內的若干當前用戶的請求數據組成請求隊列，按照時間節點劃分請求隊列并進行標記，根據目的地信息對其周圍停放區域進行搜索并計算距離，生成用戶標號距離矩陣；

S2.1、種群初始化：生成若干條基因組成相同但排列組合不同的染色體；將請求隊列作為遺傳算法中的染色體，染色體的基因排序由請求隊列的處理順序組成；在之后的種群迭代過程中保持種群的染色體數不變；

S2.2、選擇實數編碼的NSGA-II作為遺傳算法的基因編碼方式；用適應度函數區分種群內的染色體差異，并作為篩選染色體的標準：讓種群隨著迭代朝著更符合優化目標的方向進化，最終得到最適合環境的染色體；

適應度函數由優化目標函數和約束條件組成；所述優化目標函數為距離函數f(x)和密度函數g(x)；f(x)為待停的單車到停放點的距離代價總和，g(x)為所有停放點之間的停車密度代價總和；

優化目標函數的數學模型為：

上式中，p_j為各停放點的理想停放數；I為待停的車輛集合，I＝{1，2，3，…，i}；J為停放點集合，J＝{1，2，3，…，j}；x_ij為分配標志位取值為x_ij∈{0，1}，x_ij取值為1時表示i車輛分配給j停放點，x_ij取值為0時表示i車輛未分配給j停放點；目標區域p與停放點j之間的距離用d_ij表示；其中：

首先計算距離函數f(x)的矩陣，接著根據距離函數f(x)的矩陣和約束條件按照染色體的基因組成計算密度函數g(x)的矩陣；

所述約束條件為：

x_ij∈{0，1}?(7)

上式(5)至式(7)中，I為待停的車輛集合，I＝{1，2，3，…，i}；J為停放點集合，J＝{1，2，3，…，j}；x_ij為分配標志位取值為x_ij∈{0，1}，x_ij取值為1時表示i車輛分配給j停放點，x_ij取值為0時表示i車輛未分配給j停放點；B_j為每個停放點的車輛容納上限；

S3、選擇錦標賽算法作為選擇算子，選擇自交作為交叉算子，選擇雙參賽模式；

S3.1、錦標賽算法的計算過程如下：

S3.1.1、規定篩選后的種群大小為數值S_p，隨機選擇種群中兩個個體p₁和p₂進行適應度比較；

S3.1.2、若p₁和p₂之間存在支配關系，則淘汰被支配的個體；若兩個個體處在同一層非支配解，則跳過淘汰階段，比賽的輪數由種群中剩下的個體數決定；

S3.1.3、繼續進行適應度比較，直到種群大小降低至數值S_p；

S3.2、自交的計算過程如下：

S3.2.1、對種群中的每個個體設定一個基因可交叉長度L_p，該長度不得超過染色體中基因個數的一半；

S3.2.2、在染色體中隨機設置兩個點M₁和M₂，滿足M₁和M₂之間的距離大于基因可交叉長度L_p，且M₁和M₂中后置位點的距離染色體末端距離大于基因可交叉長度L_p；

S3.2.3、以M₁和M₂為錨點，向后端展開兩個長度為L_p的基因片段，進行交叉操作；

S4、利用快速非支配排序將種群分為若干個等級，并計算種群擁擠度；

S4.1、利用快速非支配排序將種群分為若干個等級的過程為：

S4.1.1、設種群中個體數為P，其中每個個體有被支配個數n_p和支配的解M_p這兩個參數，其中M_p為數組；

S4.1.2、將該個體被支配個數n_p取值為0的個體放入數組S₁中，作為該種群中的非支配解；

S4.1.3、取消非支配解對支配個體的支配，將S₁數組中的個體從種群中排除：對每個在數組S₁中的個體，遍歷支配的解M_p中的個體，將該個體的被支配個數n_p參數減1，當前數組S₁中的個體被支配個數n_p取值為-1；

S4.1.4、將剩余個體中被支配個數n_p取值為0的個體加入數組S₂，對數組S₂重復執行步驟S4.1.3，直至種群等級劃分完畢；

S4.2、種群擁擠度計算的過程為：

S4.2.1、對種群中所有個體引入擁擠度L_d，并初始化擁擠度L_d為0；

S4.2.2、對每個優化目標函數f_m進行遍歷，根據每個優化目標函數對個體目標值排序，為優化目標函數f_m的最大值，為優化目標函數f_m的最小值；得到數量為m的個體按優化目標函數升序排序后的數組；

S4.2.3、將每個數組中優化目標函數最大與最小的個體擁擠度L_d置為∞；

S4.2.4、計算數組中剩余個體的擁擠度L_d，當前個體的擁擠度計算公式為：

上式(8)中，L[i]_d為當前個體的擁擠度，L[i+1]_m和L[i-1]_m為相鄰個體的擁擠度，公式(8)將當前個體在m個矩陣中的擁擠度累加得到最終擁擠度；

S5、合并種群：引入精英保留策略維持種群的大小和多樣性；

每一代種群選擇、交叉和變異之后產生新的個體，將新的個體與父種群合成一個種群R_i；接著根據快速非支配排序的結果將種群按等級從低到高覆蓋父種群，直到某一層的個體不能完全放入；最后將該層的個體按擁擠度降序排列，依次覆蓋父種群，直到父種群被完全覆蓋；

S6、將用戶標號距離矩陣和停放點信息表輸入后臺遺傳算法，判斷遺傳算法是否收斂，決定是否繼續執行下一代遺傳操作：

選用Hypervolume指標進行解集的收斂性評價：給定在n個目標中包含m個點的集合S；相對于參考點計算S的Hypervolume評價指標：

上式(9)中，δ為Lebesgue測度；|S|表示非支配解集的數目，v_i表示參照點與解集中第i個解構成的Hypervolume評價指標；Hypervolume評價指標值越大，則該解集收斂性越好；

當種群達到規定的收斂閾值時，執行步驟S7，且遺傳算法終止；反之則遺傳代數Gen增加1，返回執行步驟S3至步驟S5，直到種群達到規定的收斂閾值；

S7、服務器根據路徑規劃算法計算用戶到達目的地時間，并根據用戶到達目的地時間、目的地周圍的停放點信息和停放點區域密度，將推薦停放點和目的地附近其余停放點發送給用戶終端供用戶選擇；并將分配信息存入結果表中。