共享單車調度模型和方法綜述

0 引言

近年來，共享經濟模式深入人心，共享單車也應運而生，低碳綠色出行逐漸成為一種趨勢。共享單車解決了“最后一公里”的問題，緩解了交通堵塞壓力，因而，逐漸成為人們短途出行的主要交通工具之一。但是，在共享單車迅猛發展的同時，也出現了一系列問題：租車難、還車難、單車分配不均衡，一些站點資源過剩，而另外一些資源不足，滿足不了用戶需求。這些問題不僅造成資源浪費，也會降低用戶的滿意度。高效的共享單車調度是解決上述問題的最有效途徑。

所謂共享單車調度問題，即，調度車輛從車場出發，途經若干租賃點，調度人員需要對各租賃點的共享單車進行分配或者收集，然后調度車輛再返回車場；調度車輛在此過程中需要合理規劃路徑并對租賃點共享單車進行調整，以滿足特定的指標。共享單車調度的具體過程可以參見圖1，其中，箭頭表示調度車輛行駛的方向，雙向箭頭表示一個來回過程，圖1（a）為單個調度車輛完成任務的過程，圖1（b）為多個車輛的調度過程。

圖1 共享單車調度具體過程

該問題本質上是一個車輛路徑規劃問題，但是也有別于車輛路徑規劃問題，其復雜性要高于傳統的車輛路徑規劃問題，但本質上都是組合優化問題。調度車輛時，當單車以及租賃點個數較少時，我們可以采用數學方法進行精確求解；當問題規模較大時，我們需要尋求高效的方法來獲取較優的調度策略。

1 共享單車調度模型

為了求解共享單車調度問題，我們需要構建上述問題的數學模型，也即問題所要滿足的特定的指標，比如調度成本最低、車輛利用率最高等。

一般來說，共享單車調度問題的數學模型多為調度成本。徐國勛等考慮共享單車出現的供需不平衡現象，考慮采用“紅包車”機制來緩解運營商調度壓力，以整體運營成本最低為目標函數，構建問題的混合整數規劃模型；楊珈惠等考慮實際使用中的動態規劃情況，允許出現局部路徑重復的情況，引入動態規劃模型，考慮調度車輛和運輸距離最小的情況，以獲得總的調度成本最低；張陌塵等考慮共享單車不同時期的狀態，根據靜態和動態兩種不同情況，在靜態調度過程中，考慮行駛距離最小，而在動態過程中，考慮調度成本最低，以此來構建問題的數學模型；關宏志等根據用戶信息建立用戶選擇模型，并綜合考慮用戶獎勵成本和運營調度成本，建立了用戶參與的成本最低化的混合調度模型。

此外，還有一些工作考慮了其他的指標。比如，于德新等分析了影響共享單車成本的參數，在考慮成本最低的同時，將投放率最高為目標，構建了共享單車調度模型；李珍萍等考慮單車利用率和用戶滿意度，將這兩個指標建立成問題的數學模型，同時，融合調度總成本，建立共享單車調度問題的整數規劃模型；文蝶斐等考慮單車系統資源的充分利用，收集某市某區域一天的共享單車騎行數據，并對數據進行處理，提取特征，結合需求分析，考慮單車使用率、閑置率，單車平均使用次數，以初始配置的車輛總數為目標函數，來構建問題的數學模型；呂曉萌等收集共享單車數據，統計各個區域的人流量和用戶需求量，構建單車調度的非線性規劃調度模型，并據此來分配每個租賃點的共享單車數量。

共享單車主要的調度指標如表1所示。

表1 主要調度指標總結

2 共享單車調度方法

共享單車調度問題本質上是一個組合優化問題，為了獲得更高效的調度方案，許多學者對共享單車調度方法進行了研究。目前，共享單車調度的方法主要有如下兩類：精確算法和啟發式算法求解。精確算法主要包括分支定界法、割平面法、動態規劃法等；啟發式算法可以分為傳統啟發式算法和元啟發式算法，傳統啟發式算法主要包括局部搜索算法、松弛方法、構造型方法等，元啟發式算法包括遺傳算法、粒子群優化算法、人工神經網絡算法、模擬退火算法、禁忌搜索算法等。常用共享單車調度方法的分類如圖2所示。

圖2 常用共享單車調度方法

對于精確算法，Zhou Yuyan等針對北京病人前往醫院就診前后使用共享單車行為進行建模，基于效用最大化準則，采用多項式評定模型（Logit模型）進行模型求解；戴敏等針對帶有時間窗的局內開放式車輛調度問題，進行競爭分析，設計了用于求解該問題的競爭算法，提出了重新規劃策略；文獻針對構建的共享單車調度模型，采用LINGO軟件來求解，以得到問題的最優調度方案；王浩等采用單純形法來求解共享單車優化調度問題，所得結果達到了最小的成本和最高效的調度方式。

對于啟發式算法，于德新等采用改進的遺傳算法對問題進行求解，引入了精英選擇策略以及優劣解距離法（TOPSIS法）來評價解的優劣，以降低企業的調度成本；Duan Yubin等考慮在車輛違反交通限制而不能沿著漢密爾頓路徑行駛時，采用貪婪算法來調整路徑，以獲得一個更快速且靈活的策略；賈立雙等提出一種改進的多車調度方法，采用最近鄰和遺傳算法相結合，獲取的配送路線較之其他算法更合理；王玲玲等針對傳統調度方法的不足，提出了一種多點循環甩掛運輸模式，并采用禁忌搜索方法對問題進行求解；此外，周騫等也將禁忌搜索算法用于單車調度優化中，不同的是，所提方法結合了遺傳算法；文獻均考慮采用基于BP神經網絡來優化共享單車調度問題，依靠BP神經網絡來進行需求等的預測，來為共享單車調度提供策略。

此外，隨著人工智能的興起，許多學者將深度學習融入調度策略的求解。如, Mao Dianhui等基于時空圖，根據自行車的騎行數據估計出每個區域的自行車數量，給出了單車的移動模式和規則，以更好地進行共享單車調度；王嘉薇等基于VRP模型，采用模糊綜合評價的方法來構建模型，給出共享單車調度方案；Vazquez-Abad J. Felisa等考慮共享單車系統獲取的大量數據，考慮采用數據驅動的方法來對問題進行求解；Xu Miao等基于上海地區GPS數據時空特征的可視化分析結果，提出了一個新的分級和分區方法，并采用深度學習來對共享單車供需多塊混合模型進行預測；張建同等針對共享單車分布動態變化的情況，提出采用深度強化學習來對共享單車進行重置，該方法根據單車分布的數據，構建環境交互模擬器，通過大規模數據實驗，得到性能優越的解。

3 挑戰與展望

上述成果豐富了共享單車調度理論，為共享單車商家提供了眾多解決方案。但是隨著科技的發展，技術迭代越來越快，我們有必要對調度方法和模型提出更高的要求，以便滿足用戶進一步的需求。

3.1 模型構建創新

在模型構建方面，我們可以根據前期搜索的數據，采用機器學習等方法來進行特征選擇構建問題的模型；如有必要，可以讓用戶參與進來，采用人機交互的方法來選擇或評價模型的優劣；此外，還可以同時考慮多目標，比如調度時間、調度人工成本、用戶滿意度、用戶徒步到租賃點的距離等，構建多目標模型；進一步，考慮實際問題中存在的動態或不確定問題，比如車輛突然損壞、換車租賃點車滿等情況，據此構建動態不確定模型。

3.2 基于復雜模型的算法設計

目前，求解已有模型的算法設計已經取得了很多成果，但是，針對3.1節所述復雜模型的求解算法成果相對偏少。針對多目標、動態、不確定以及無模型等復雜問題，如何設計高效的求解方法，也是共享單車調度面臨的新問題。

4 結語

共享單車調度模型和方法研究已經有了很多成果。本文歸納了現有模型的構建方法，總結了該領域中算法的研究進展，也對存在的挑戰與展望進行了討論。隨著智能技術的不斷發展，大數據、人工智能等的融合，必然會豐富共享單車調度方法，加快該領域的發展。