共享單車的調度算法

尹詩穎 駱虎 周駿 申佳訊

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

【關鍵詞】共享單車靜態調度模型 遍歷網絡結構圖 A？鄢算法

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

1.共享單車供應能力

通過實際收集的數據，我們通過正態分布模擬出不同的騎行情況，從而求解出了總的單車供應能力最大時的分布情況。

2.共享單車靜態調度模型的建立

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

為了簡化模型，我們近似認為中心車場在某一區域附近。以調度車輛運行總成本最低為目標函數，建立共享單車靜態調度模型如下：

3.共享單車靜態調度模型的求解

3.1 A？鄢算法原理

算法思想：

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

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

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

A？鄢算法流程

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

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

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

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

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

（6）擴展節點n，生成其后繼結點集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中的每一個后繼，以使它們順著到目前為止發現的最好路徑指向它們的祖先。

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

（9）返回第3步。

3.2 A？鄢算法求解模型

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

4.結論

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

參考文獻：

[1]李錦霞.公共自行車調度優化研究[D].長沙理工大學.2013.