尹詩穎 駱虎 周駿 申佳訊

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

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

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

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

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

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

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

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

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

3.1 A？鄢算法原理

算法思想：

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

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

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

A？鄢算法流程

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

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

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

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

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

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

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

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

（9）返回第3步。

3.2 A？鄢算法求解模型

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

4.結(jié)論

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

參考文獻：

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