文/王宇（中國地質大學（北京）經濟管理學院）

一、選題背景

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

二、算法原理

（一）迪杰斯特拉算法

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

（二）哈夫曼樹

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

圖1 哈夫曼樹

（三）算法拓展

1.遺傳算法

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

2.啟發式算法

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

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

（一）問題的提出

共享單車動態調度中一個較為重要的環節為單車搬遷路徑的選擇，即調度車將某個單車過剩的調度點（用車區域）的共享單車運往另一個單車缺少的調度點（放車區域）時，需要擇優選擇前往路徑以確保所花費的調度車使用費用最低。

（二）問題的抽象和說明

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

（三）Dijkstra算法的應用

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

圖2 無向圖

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

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

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

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

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

（四）哈夫曼樹的應用

現構造一個帶有權值哈夫曼樹，步驟如下：

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

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

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

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

四、算法拓展

（一）遺傳算法定義

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

（二）流程圖（見圖3）

圖3 流程圖

（三）在共享單車調度上的運用思路

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

（1）考慮調度過程中由于調度運輸產生的費用。

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

（四）算法分析

1.初始化調度信息

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

2.調度參數設置

（1）調度站點的距離

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

（2）共享單車的調度和損失費用

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

（3）調度車輛信息

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

3.調度方案計算

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

（1）參數初始化

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

（2）種群初始化及編碼

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

（3）適應度函數

計算本次迭代種群的最優適應值。

（4）迭代

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

（5）交叉和變異

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

（6）選代終止

到達最大迭代次數,選擇最小的適應值作為最優的調度費用,并輸出對應的調度路線。

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

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