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

一、選題背景

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

二、算法原理

（一）迪杰斯特拉算法

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

（二）哈夫曼樹(shù)

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

圖1 哈夫曼樹(shù)

（三）算法拓展

1.遺傳算法

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

2.啟發(fā)式算法

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

三、基于算法求解實(shí)際問(wèn)題

（一）問(wèn)題的提出

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

（二）問(wèn)題的抽象和說(shuō)明

調(diào)度車(chē)每公里的費(fèi)用固定，因此通過(guò)對(duì)比從固定位置P的用車(chē)區(qū)域到K個(gè)近鄰放車(chē)區(qū)域的路徑長(zhǎng)度，選擇路徑長(zhǎng)度最短的近鄰放車(chē)區(qū)域作為終點(diǎn)進(jìn)行調(diào)度。

（三）Dijkstra算法的應(yīng)用

以一個(gè)帶有權(quán)值的無(wú)向圖為例，如圖2，采用Dijkstra算法作為尋路策略完成對(duì)基于起點(diǎn)A到停車(chē)區(qū)域G的最短路線：

圖2 無(wú)向圖

步驟一： 以帶有權(quán)值的一個(gè)矩陣z表示含有各結(jié)點(diǎn)的帶權(quán)無(wú)向圖，如圖2，矩陣相應(yīng)位置的數(shù)值代表對(duì)應(yīng)線段的權(quán)值，如果從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)不連通，那么其矩陣中的值為 ∞。

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

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

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

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

（四）哈夫曼樹(shù)的應(yīng)用

現(xiàn)構(gòu)造一個(gè)帶有權(quán)值哈夫曼樹(shù)，步驟如下：

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

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

（3）在森林當(dāng)中刪除這兩棵樹(shù)，同時(shí)將新得到的二叉樹(shù)加入森林當(dāng)中，即將新得到的路徑加入路徑群中。

（4）迭代，直到森林當(dāng)中只含有一棵樹(shù)為止。

四、算法拓展

（一）遺傳算法定義

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

（二）流程圖（見(jiàn)圖3）

圖3 流程圖

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

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

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

（2）某個(gè)待調(diào)度區(qū)域共享單車(chē)過(guò)少或者過(guò)剩時(shí)由于未被使用帶來(lái)相應(yīng)的損失費(fèi)用。

（四）算法分析

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

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

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

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

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

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

本文對(duì)調(diào)度費(fèi)用做如下假設(shè):針對(duì)該區(qū)域,共享單車(chē)的調(diào)度運(yùn)輸費(fèi)用為12元/公里,而當(dāng)共享單車(chē)不滿足用戶需求或者是超過(guò)用戶需求,所帶來(lái)的損失費(fèi)用為8元/輛天。

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

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

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

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

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

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

（2）種群初始化及編碼

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

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

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

（4）迭代

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

（5）交叉和變異

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

（6）選代終止

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

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

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