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

梁巖 王靚 李林玉 徐小本

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

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

中圖分類號(hào)：U491.2+25 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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進(jìn)入市場(chǎng)，興起了無樁自行車。與站點(diǎn)式共享自行車相比，無站式共享自行車節(jié)省了啟動(dòng)成本，但用戶的隨機(jī)使用行為帶來了分布不平衡，降低了共享自行車系統(tǒng)的便捷性。本文基于具有正反饋性的蟻群算法，借鑒遺傳算法，提出了一種遺傳-蟻群融合算法，提高了算法的收斂性。該方法以最小距離成本為最終目標(biāo)，適用于大中規(guī)模的共享自行車系統(tǒng)。

1 基本思路

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

2 站點(diǎn)的聚類

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

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

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

實(shí)際路況中，連接兩節(jié)點(diǎn)之間的道路長(zhǎng)度和兩節(jié)點(diǎn)之間的直線距離存在較大差異。為簡(jiǎn)化計(jì)算，用兩節(jié)點(diǎn)之間的直線距離作為距離指標(biāo)：

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

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

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

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

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

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

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

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

基本步驟如下。

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

步驟2：選擇操作;

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

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

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

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

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

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

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

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

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

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

5 實(shí)例驗(yàn)證與分析

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

為計(jì)算分析方便，將自行車實(shí)際的經(jīng)緯位置轉(zhuǎn)化為橫向地理單位為100、縱向地理單位為100的網(wǎng)格，圖2中X、Y軸分別為橫向與縱向地理坐標(biāo)軸，點(diǎn)的大小代表站點(diǎn)容量大小。其中，灰色站點(diǎn)代表自行車?yán)寐矢叩恼军c(diǎn);藍(lán)色代表正需求，即需要調(diào)來自行車;紅色代表負(fù)需求，即可以調(diào)走自行車;顏色越深，則需求越強(qiáng)烈。負(fù)需求無需緩解，因?yàn)槎嘤嗟淖孕熊嚥粫?huì)造成任何損失，反而可以為更多人提供服務(wù)。調(diào)度后，灰色站點(diǎn)數(shù)量明顯增多，藍(lán)色站點(diǎn)數(shù)量急劇減少，可更好地滿足出行需求。

<F：＼歡歡文件夾＼201904＼河南科技201901＼河南科技（創(chuàng)新驅(qū)動(dòng)）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ū)動(dòng)）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 結(jié)語(yǔ)

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

參考文獻(xiàn)：

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

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

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