共享單車的調(diào)度算法

尹詩穎 駱虎 周駿 申佳訊

【摘要】共享單車極大方便了公眾短距離出行和公共交通換乘，更好地滿足公眾出行需求、有效解決城市交通出行“最后一公里”問題、緩解城市交通擁堵等方面發(fā)揮了積極作用，推動了分享經(jīng)濟(jì)發(fā)展。因此，本文對共享單車進(jìn)行數(shù)據(jù)分析與建模，研究如今共享單車的調(diào)度問題。

【關(guān)鍵詞】共享單車靜態(tài)調(diào)度模型 遍歷網(wǎng)絡(luò)結(jié)構(gòu)圖 A？鄢算法

【中圖分類號】F270.7 【文獻(xiàn)標(biāo)識碼】A 【文章編號】2095-3089（2018）11-0256-01

1.共享單車供應(yīng)能力

通過實(shí)際收集的數(shù)據(jù)，我們通過正態(tài)分布模擬出不同的騎行情況，從而求解出了總的單車供應(yīng)能力最大時(shí)的分布情況。

2.共享單車靜態(tài)調(diào)度模型的建立

我們以騎行時(shí)長為各區(qū)域間距離的衡量標(biāo)準(zhǔn)，得到了各區(qū)域間估計(jì)的距離。本文將以總成本費(fèi)用最低建立共享單車靜態(tài)調(diào)度模型。這里的總成本費(fèi)用分為兩個(gè)部分：第一是調(diào)度車輛從中心車場到各區(qū)域的總路程費(fèi)用；第二是工作人員裝載和投放共享單車的工資。

為了簡化模型，我們近似認(rèn)為中心車場在某一區(qū)域附近。以調(diào)度車輛運(yùn)行總成本最低為目標(biāo)函數(shù)，建立共享單車靜態(tài)調(diào)度模型如下：

3.共享單車靜態(tài)調(diào)度模型的求解

3.1 A？鄢算法原理

算法思想：

A？鄢算法的核心部分，在于估價(jià)函數(shù)的設(shè)計(jì)。在選擇當(dāng)前結(jié)點(diǎn)的下一個(gè)考察節(jié)點(diǎn)時(shí)引入了估價(jià)函數(shù)f（x）。

f（x）=g（x）+h（x）

f（x）表示從起始節(jié)點(diǎn)x到節(jié)點(diǎn)的一條最佳路徑的實(shí)際代價(jià)加上從結(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)的一條最佳路徑的代價(jià)之和。g（x）就是從起始節(jié)點(diǎn)到節(jié)點(diǎn)x之間最小代價(jià)路徑的實(shí)際代價(jià)，h（x）則是從x節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)路徑的估計(jì)代價(jià)。

A？鄢算法流程

（1）生成一個(gè)只包含開始單車網(wǎng)絡(luò)分布節(jié)點(diǎn)n0的搜索圖G，把n0放在一個(gè)叫OPEN的列表上。

（2）生成一個(gè)列表CLOSED，它的初始值為空。

（3）如果OPEN表為空，則失敗退出。

（4）選擇OPEN上第一個(gè)節(jié)點(diǎn)，把它從OPEN中移入CLOSED，該節(jié)點(diǎn)為n。

（5）如果n是目標(biāo)節(jié)點(diǎn)，順著G中，從n到n_{0}的指針找到一條車輛運(yùn)輸路徑，獲得解決方案，成功退出（該指針定義了一個(gè)搜索樹，在第7步建立）。

（6）擴(kuò)展節(jié)點(diǎn)n，生成其后繼結(jié)點(diǎn)集M，在G中，n的祖先不能在M中。在G中安置M的成員，使他們成為n的后繼。

（7）從M的每一個(gè)不在G中的成員建立一個(gè)指向n的指針（例如，既不在OPEN中，也不在CLOSED中。把M1的這些成員加到OPEN中。對M的每一個(gè)已在OPEN中或CLOSED中的成員m，如果到目前為止找到的到達(dá)m的最好路徑通過n，就把它的指針指向n。對已在CLOSED中的M的每一個(gè)成員，重定向它在G中的每一個(gè)后繼，以使它們順著到目前為止發(fā)現(xiàn)的最好路徑指向它們的祖先。

（8）按遞增f？鄢值，重排OPEN（相同最小f？鄢值可根據(jù)搜索樹中的最深節(jié)點(diǎn)來解決）。

（9）返回第3步。

3.2 A？鄢算法求解模型

我們根據(jù)A？鄢算法，使用C++編程求解單車調(diào)度總成本最小值，就能給出投放單車的具體方式和路徑。

4.結(jié)論

我們客觀上構(gòu)建了共享單車靜態(tài)調(diào)度模型。每一天的單車使用情況都存在很大的不確定，但是在短時(shí)間內(nèi)滿足正態(tài)分布，這是我們能給求解出最低單車調(diào)度費(fèi)用的出發(fā)點(diǎn)。還有，我們使用的A？鄢算法比較適合于處理大量數(shù)據(jù)，這使我們的模型能適用于分析大量騎行數(shù)據(jù)下的單車調(diào)度問題。

參考文獻(xiàn)：

[1]李錦霞.公共自行車調(diào)度優(yōu)化研究[D].長沙理工大學(xué).2013.