基于數(shù)據(jù)結(jié)構對共享單車動態(tài)調(diào)度中的應用分析
——以動態(tài)調(diào)度問題為例

文/王宇（中國地質(zhì)大學（北京）經(jīng)濟管理學院）

一、選題背景

在最大化滿足城市共享單車用戶的用車需求以及提高共享單車使用效率等方面，共享單車的動態(tài)調(diào)度發(fā)揮著格外重要的作用，但城市熱門用車區(qū)域、用車頻次與行程結(jié)束后的熱門停車區(qū)域及其停車頻次等因素均會直接影響對調(diào)度策略的制定，因此共享單車的動態(tài)調(diào)度問題存在一定的復雜性，為了讓共享單車調(diào)度策略具有更好的有效性，能將復雜問題簡單化的算法將必不可少，所以，本小組對數(shù)據(jù)結(jié)構中的特定算法原理以及其在本市場調(diào)度問題中的應用進行展開研究。

二、算法原理

（一）迪杰斯特拉算法

迪杰斯特拉算法(Dijkstra)是由荷蘭計算機科學家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法，解決的是有權圖中最短路徑問題。迪杰斯特拉算法主要特點是從起始點開始，采用貪心算法的策略，每次遍歷到始點距離最近且未訪問過的頂點的鄰接節(jié)點，直到擴展到終點為止。

（二）哈夫曼樹

哈夫曼樹（Huffman）又稱最優(yōu)樹，是一類帶權路徑長度最短的樹，在實際中有廣泛的用途。比如，給定N個權值作為N個葉子結(jié)點，構造一棵二叉樹，若該樹的帶權路徑長度達到最小，稱這樣的二叉樹為最優(yōu)二叉樹，即哈夫曼樹。哈夫曼樹中權值較大的結(jié)點離根較近。（如：圖1）

圖1 哈夫曼樹

（三）算法拓展

1.遺傳算法

遺 傳 算 法（Genetic Algorithm，GA）最早是由美國的 John holland于20世紀70年代提出,該算法是根據(jù)大自然中生物體進化規(guī)律而設計提出的。是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優(yōu)解的方法。該算法通過數(shù)學的方式,利用計算機仿真運算,將問題的求解過程轉(zhuǎn)換為類似生物進化中的染色體基因的交叉、變異等過程，并被人們廣泛地應用于組合優(yōu)化、機器學習、信號處理、自適應控制和人工生命等領域。

2.啟發(fā)式算法

啟發(fā)式算法（heuristic algorithm)是相對于最優(yōu)化算法提出的。一個問題的最優(yōu)算法求得該問題每個實例的最優(yōu)解。啟發(fā)式算法可以這樣定義：一個基于直觀或經(jīng)驗構造的算法，在可接受的花費（指計算時間和空間）下給出待解決組合優(yōu)化問題每一個實例的一個可行解，該可行解與最優(yōu)解的偏離程度一般不能被預計。

三、基于算法求解實際問題

（一）問題的提出

共享單車動態(tài)調(diào)度中一個較為重要的環(huán)節(jié)為單車搬遷路徑的選擇，即調(diào)度車將某個單車過剩的調(diào)度點（用車區(qū)域）的共享單車運往另一個單車缺少的調(diào)度點（放車區(qū)域）時，需要擇優(yōu)選擇前往路徑以確保所花費的調(diào)度車使用費用最低。

（二）問題的抽象和說明

調(diào)度車每公里的費用固定，因此通過對比從固定位置P的用車區(qū)域到K個近鄰放車區(qū)域的路徑長度，選擇路徑長度最短的近鄰放車區(qū)域作為終點進行調(diào)度。

（三）Dijkstra算法的應用

以一個帶有權值的無向圖為例，如圖2，采用Dijkstra算法作為尋路策略完成對基于起點A到停車區(qū)域G的最短路線：

圖2 無向圖

步驟一： 以帶有權值的一個矩陣z表示含有各結(jié)點的帶權無向圖，如圖2，矩陣相應位置的數(shù)值代表對應線段的權值，如果從一個結(jié)點到另一個結(jié)點不連通，那么其矩陣中的值為 ∞。

步 驟 二： 選 擇 vj，使 S(j)=min{ S(i)| vi∈ {B, C, D, E, F}}，vj是從結(jié)點A出發(fā)找出一條最短線路的終止結(jié)點，令 Q ←Q∪{vj}。

步驟三： 修改起始結(jié)點A，再次到集合 {B, C, D, E, F}中任一結(jié)點vn之間的最短線路的長度值, 若S(j) + z(j, n) ＜ S(n)，那么S(n) = S(j) + z(j, n)；

基于以上最短距離線路的計算方法, 同時采用歐氏距離計算方法獲取基于用車區(qū)域當前位置Pcurrent到各停車區(qū)域Ci的最短路徑path（pathi=Pcurrent→P1→P2→···→Pn→Ci），通過比較兩區(qū)域之間的線路長度Scost的大小完成路線推薦。對應的公式為：

公式中Scost表示用車區(qū)域到停車區(qū)域的線路長度，S(Pcurrent,P1)表示當前位置Pcurrent到道路交叉口P1的距離，S(Pi,Pi+1)代表邊e(Pi,Pi+1)的長度，S(Pn,Ci)代表交叉口Pn到單車分布區(qū)域Ci的距離。

（四）哈夫曼樹的應用

現(xiàn)構造一個帶有權值哈夫曼樹，步驟如下：

（1）首先分別賦予四個地鐵站（調(diào)度點）權值{w1,w2,w3,w4}，每一個權值相當于到達該調(diào)度點的時間或距離，構造出4棵只有根節(jié)點的二叉樹，這4棵二叉樹構成一個森林。

（2）在森林當中選取兩棵根節(jié)點的權值最小的樹作為左右子樹構造一棵新的二叉樹，并置新的二叉樹的根節(jié)點的權值為其左、右樹上的根節(jié)點的權值之和，即新的總路徑權值等于其分路徑權值的加和。

（3）在森林當中刪除這兩棵樹，同時將新得到的二叉樹加入森林當中，即將新得到的路徑加入路徑群中。

（4）迭代，直到森林當中只含有一棵樹為止。

四、算法拓展

（一）遺傳算法定義

遺傳算法是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優(yōu)解的方法。該算法通過數(shù)學的方式,利用計算機仿真運算,將問題的求解過程轉(zhuǎn)換成類似生物進化中的染色體基因的交叉、變異等過程，目前已被人們廣泛地應用于組合優(yōu)化、機器學習、信號處理、自適應控制和人工生命等領域。

（二）流程圖（見圖3）

圖3 流程圖

（三）在共享單車調(diào)度上的運用思路

共享單車的調(diào)度受其運營方式的影響，使得其調(diào)度過程是一個復雜的動態(tài)過程。通常，在對共享單車進行調(diào)度分析時，我們把它的調(diào)度過程簡化成靜態(tài)過程。本文在建立優(yōu)化調(diào)度模型時，考慮調(diào)度的目標函數(shù)為如下兩個部分：

（1）考慮調(diào)度過程中由于調(diào)度運輸產(chǎn)生的費用。

（2）某個待調(diào)度區(qū)域共享單車過少或者過剩時由于未被使用帶來相應的損失費用。

（四）算法分析

1.初始化調(diào)度信息

首先在某區(qū)域中的二維坐標隨機生成共享單車用戶的位置信息以及對應的需求數(shù)量，并將該區(qū)域均衡地分為25個調(diào)度區(qū)域，根據(jù)用戶的需求信息以及調(diào)度區(qū)域的位置信息，并運用重心法求出每個調(diào)度區(qū)域的調(diào)度站點內(nèi)，保障每次調(diào)度車輛將共享單車調(diào)度在該位置可以滿足調(diào)度需求。最后，初始化各個調(diào)度站點的需求數(shù)量。

2.調(diào)度參數(shù)設置

（1）調(diào)度站點的距離

在已知各個調(diào)度站點坐標的前提下,為了簡化問題,本文選取兩個調(diào)度站點的歐式距離作為兩個站點之間的調(diào)度距離。

（2）共享單車的調(diào)度和損失費用

本文對調(diào)度費用做如下假設:針對該區(qū)域,共享單車的調(diào)度運輸費用為12元/公里,而當共享單車不滿足用戶需求或者是超過用戶需求,所帶來的損失費用為8元/輛天。

（3）調(diào)度車輛信息

本文假定上述劃分的25個調(diào)度站點(分別命名為1-26號) ,均由該區(qū)域的調(diào)度中心負責調(diào)度,該調(diào)度中心包含三輛調(diào)度車,每輛車最大裝載量為40輛共享單車。

3.調(diào)度方案計算

目前,運用遺傳算法求解物流配送車輛路徑(VRP)問題的研究具有較多成果,運用遺傳算法對該優(yōu)化的調(diào)度模型進行求解,求解步驟如下:

（1）參數(shù)初始化

初始化樣本個數(shù)N,最大迭代次數(shù)n,交叉概率p和變異概率Pme

（2）種群初始化及編碼

本文將調(diào)度站點隨機連接遍歷的路徑作為初始化種群,并通過自然編碼的方式對該初始化種群進去編碼為E(1,2,3,米)

（3）適應度函數(shù)

計算本次迭代種群的最優(yōu)適應值。

（4）迭代

判斷是否到達最大迭代次數(shù)n,如果到達則退出循環(huán)并輸出最優(yōu)的適應值,否則進入(5)。

（5）交叉和變異

選擇(4)中個體適應度值小的作為優(yōu)良的染色體,并按照設置的交叉變異概率進行交叉變異操作,產(chǎn)生新的種群并轉(zhuǎn)入(3)繼續(xù)計算適應值。

（6）選代終止

到達最大迭代次數(shù),選擇最小的適應值作為最優(yōu)的調(diào)度費用,并輸出對應的調(diào)度路線。

設定遺傳算法迭代的參數(shù)如下:以模型的目標函數(shù)作為迭代的適應度函數(shù),初始化樣本為2000個,交叉概率設為0.9，變異概率設為0.12,終止選代次數(shù)為600代。

1輛車調(diào)度時,站點7、12、19、22、 24未被調(diào)度,而其他站點被調(diào)度且滿足站點的車輛需求,最優(yōu)的調(diào)度費用約為551.19元;當我們使用2輛調(diào)度時,其費用為477.14元,其中4、7、10、12、19、21、26這7個站點未被調(diào)度,當使用3輛車進行調(diào)度且保證都有調(diào)度任務時,其調(diào)度費用反而增加,最優(yōu)調(diào)度費用為600.78元。分析發(fā)現(xiàn),相比于1輛車和3輛車,派出2輛車時其服務的站點較少,但是節(jié)省了調(diào)度運輸費用,保證了綜合成本最小。