基于遺傳-蟻群融合算法的共享單車優(yōu)化調(diào)度研究

梁巖 王靚 李林玉 徐小本

摘 要：隨著共享單車規(guī)模的擴大，資源調(diào)配需要更加科學合理。因此，提出了一種基于遺傳-蟻群融合算法的共享交通工具調(diào)度方法。對比該調(diào)度方法和常規(guī)蟻群算法，兩種算法的結果一致，且融合算法的收斂速度更快。

關鍵詞：共享單車;優(yōu)化調(diào)度;遺傳-蟻群融合算法;數(shù)學模型

中圖分類號：U491.2+25 文獻標識碼：A 文章編號：1003-5168（2019）01-0105-02

Research on Optimal Scheduling Problem of Shared Single Vehicle Based

on Ghybrid Genetic Algorithm- Ant Colony Optimization

LIANG Yan WANG Liang LI Linyu XU Xiaoben

（Zhengzhou University，Zhengzhou Henan 450000）

Abstract： With the expansion of the scale of shared bicycles， resource allocation needs to be more scientific and reasonable. Therefore， a method of shared transportation scheduling based on genetic and ant colony fusion algorithm was proposed. The comparison between this scheduling method and the conventional ant colony algorithm showed that the results of the two algorithms were the same， and the convergence of the scheduling results of the fusion algorithm was faster.

Keywords： shared bikes;scheduling methods;genetic-ant colony fusion algorithm;mathematicle model

隨著契合互聯(lián)網(wǎng)思維的ofo和Mobike進入市場，興起了無樁自行車。與站點式共享自行車相比，無站式共享自行車節(jié)省了啟動成本，但用戶的隨機使用行為帶來了分布不平衡，降低了共享自行車系統(tǒng)的便捷性。本文基于具有正反饋性的蟻群算法，借鑒遺傳算法，提出了一種遺傳-蟻群融合算法，提高了算法的收斂性。該方法以最小距離成本為最終目標，適用于大中規(guī)模的共享自行車系統(tǒng)。

1 基本思路

本文提出了一種基于靜態(tài)調(diào)度的三步優(yōu)化調(diào)度方法。首先，采用K-means算法對自行車聚類并集群修復。其次，采用遺傳算法獲得連接各節(jié)點的初始解，并采用蟻群算法計算和做出裝卸載自行車數(shù)量的決策。最后，直接使用蟻群算法獲得連接每個集群內(nèi)站點的最短路徑，完成集群內(nèi)部小范圍的調(diào)度。

2 站點的聚類

聚類修復是調(diào)度車輛訪問一次即可達到各站點自行車的平衡，避免二次及多次訪問，主要包括分割節(jié)點和分割集群兩種方法。由于調(diào)度車輛存在容量限額，因此考慮使用這兩種方法[1]。

3 基于遺傳-蟻群融合算法的集群間優(yōu)化調(diào)度

3.1 數(shù)學模型的建立

實際路況中，連接兩節(jié)點之間的道路長度和兩節(jié)點之間的直線距離存在較大差異。為簡化計算，用兩節(jié)點之間的直線距離作為距離指標：

[LθRf=ij∈Rflij]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（1）

其中，[Lθ]是總距離指標;[Rf]是由融合算法得到的訪問節(jié)點的順序;[lij]是站點[Ni]到站點[Nj]的距離。

先在集群層面做出路由決策，然后針對每個節(jié)點執(zhí)行詳細的自行車裝卸載決策：

[minEk-S0k-Dk]? ? ? ? ? ? ? ? ? ? ? ? ? ? （2）

[s.t.Ck<Dk<00<Dk<V-CkCk+1=Ck+Dk，k∈Rf2，Rf3，…，Rfn當k=Rf1時，Ck=0]? ?（3）

其中，[Ek]為第k個集群節(jié)點自行車的目標數(shù)量;[S0k]為調(diào)度前的自行車數(shù)量;[Dk]為對該節(jié)點的裝卸載操作;[Ck]為訪問該節(jié)點前調(diào)度車內(nèi)的自行車數(shù)量;V是調(diào)度車容量。

3.2 遺傳-蟻群融合算法求解目標函數(shù)

本文提出了一種遺傳-蟻群融合算法，將蟻群算法和遺傳算法進行優(yōu)勢互補，用于解決集群之間的自行車調(diào)度問題，以期達到最小距離成本的目標。該算法以蟻群算法為基礎，依據(jù)遺傳算法得到初始較優(yōu)解，并考慮調(diào)度任務的完成時間，基于綜合適應值對路徑信息進行初始化，生成初始信息素分布，然后依據(jù)蟻群算法進行選擇、遍歷，并更新節(jié)點路徑信息素，最終獲取精確解[2]。

基本步驟如下。

步驟1：隨機生成初始種群，設定種群規(guī)模;

步驟2：選擇操作;

步驟3：執(zhí)行遺傳算子（交叉、變異）;

步驟4：進行GA終止條件判斷，若滿足終止條件則轉(zhuǎn)步驟5;否則，轉(zhuǎn)步驟2;

步驟5：從GA得到的解中選擇1%個體作為較優(yōu)解輸入ACO;

步驟6：以Ant-cycle模型為基礎，對ACO中節(jié)點的路徑進行信息素初始化;

步驟7：ACO中的參數(shù)初始化;

步驟8：應用ACO尋優(yōu)，構造MRO維修調(diào)度問題的可行解，并更新信息素濃度;

步驟9：進行ACO終止條件判斷，若滿足終止條件，則轉(zhuǎn)步驟10，否則，轉(zhuǎn)步驟8;

步驟10：輸出最優(yōu)解，算法結束。

4 集群內(nèi)部優(yōu)化調(diào)度

集群內(nèi)部調(diào)度存在范圍小、運送量小的問題。解決此問題的方法有蟻群算法、禁忌搜索算法及遺傳優(yōu)化算法[3]。為減小計算復雜度，采用蟻群算法找到每個集群內(nèi)連接所有站點的最短路徑，并按照順序依次訪問每個站點。

5 實例驗證與分析

以北京Mobike的494個站點為例，采用遺傳-蟻群融合算法，以MATLAB為實現(xiàn)工具，調(diào)度前后自行車需求分布如圖1和圖2所示。

為計算分析方便，將自行車實際的經(jīng)緯位置轉(zhuǎn)化為橫向地理單位為100、縱向地理單位為100的網(wǎng)格，圖2中X、Y軸分別為橫向與縱向地理坐標軸，點的大小代表站點容量大小。其中，灰色站點代表自行車利用率高的站點;藍色代表正需求，即需要調(diào)來自行車;紅色代表負需求，即可以調(diào)走自行車;顏色越深，則需求越強烈。負需求無需緩解，因為多余的自行車不會造成任何損失，反而可以為更多人提供服務。調(diào)度后，灰色站點數(shù)量明顯增多，藍色站點數(shù)量急劇減少，可更好地滿足出行需求。

<F：＼歡歡文件夾＼201904＼河南科技201901＼河南科技（創(chuàng)新驅(qū)動）2019年第01期_103595＼Image＼image15.png>[Y][100

90

80

70

60

50

40

30

20

10

0][0? ? ? ? ? ? ? ?20? ? ? ? ? ? ?40? ? ? ? ? ? ? 60? ? ? ? ? ? ?80? ? ? ? ? ? ?100? ? ?X]

圖1 調(diào)度前Mobike分布圖

<F：＼歡歡文件夾＼201904＼河南科技201901＼河南科技（創(chuàng)新驅(qū)動）2019年第01期_103595＼Image＼image16.png>[Y][100

90

80

70

60

50

40

30

20

10

0][0? ? ? ? ? ? ? ?20? ? ? ? ? ? ? 40? ? ? ? ? ? ?60? ? ? ? ? ? ? 80? ? ? ? ? ? 100? ? ? X]

圖2 調(diào)度后Mobike分布圖

6 結語

本文提出了基于遺傳-蟻群融合算法的三步調(diào)度法，有效解決了城市內(nèi)公共自行車系統(tǒng)分布不平衡的問題，節(jié)約了調(diào)度距離時間成本。

參考文獻：

[1]陳文蘭，戴樹貴.旅行商問題算法研究綜述[J].滁州學院學報，2006（3）：1-6.

[2]聶兆偉，熊丹丹，楊海成.基于混合遺傳一蟻群算法的MRO服務調(diào)度研究[J].計算機應用研究，2018（2）：438-440.

[3]張建國，吳婷，蔣陽升.基于蟻群算法的公共自行車系統(tǒng)調(diào)度算法研究[J].西華大學學報，2014（3）：70-76.