共享單車調(diào)度模型和方法綜述

0 引言

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

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

圖1 共享單車調(diào)度具體過程

該問題本質(zhì)上是一個車輛路徑規(guī)劃問題，但是也有別于車輛路徑規(guī)劃問題，其復(fù)雜性要高于傳統(tǒng)的車輛路徑規(guī)劃問題，但本質(zhì)上都是組合優(yōu)化問題。調(diào)度車輛時，當(dāng)單車以及租賃點(diǎn)個數(shù)較少時，我們可以采用數(shù)學(xué)方法進(jìn)行精確求解；當(dāng)問題規(guī)模較大時，我們需要尋求高效的方法來獲取較優(yōu)的調(diào)度策略。

1 共享單車調(diào)度模型

為了求解共享單車調(diào)度問題，我們需要構(gòu)建上述問題的數(shù)學(xué)模型，也即問題所要滿足的特定的指標(biāo)，比如調(diào)度成本最低、車輛利用率最高等。

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

此外，還有一些工作考慮了其他的指標(biāo)。比如，于德新等分析了影響共享單車成本的參數(shù)，在考慮成本最低的同時，將投放率最高為目標(biāo)，構(gòu)建了共享單車調(diào)度模型；李珍萍等考慮單車?yán)寐屎陀脩魸M意度，將這兩個指標(biāo)建立成問題的數(shù)學(xué)模型，同時，融合調(diào)度總成本，建立共享單車調(diào)度問題的整數(shù)規(guī)劃模型；文蝶斐等考慮單車系統(tǒng)資源的充分利用，收集某市某區(qū)域一天的共享單車騎行數(shù)據(jù)，并對數(shù)據(jù)進(jìn)行處理，提取特征，結(jié)合需求分析，考慮單車使用率、閑置率，單車平均使用次數(shù)，以初始配置的車輛總數(shù)為目標(biāo)函數(shù)，來構(gòu)建問題的數(shù)學(xué)模型；呂曉萌等收集共享單車數(shù)據(jù)，統(tǒng)計各個區(qū)域的人流量和用戶需求量，構(gòu)建單車調(diào)度的非線性規(guī)劃調(diào)度模型，并據(jù)此來分配每個租賃點(diǎn)的共享單車數(shù)量。

共享單車主要的調(diào)度指標(biāo)如表1所示。

表1 主要調(diào)度指標(biāo)總結(jié)

2 共享單車調(diào)度方法

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

圖2 常用共享單車調(diào)度方法

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

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

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

3 挑戰(zhàn)與展望

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

3.1 模型構(gòu)建創(chuàng)新

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

3.2 基于復(fù)雜模型的算法設(shè)計

目前，求解已有模型的算法設(shè)計已經(jīng)取得了很多成果，但是，針對3.1節(jié)所述復(fù)雜模型的求解算法成果相對偏少。針對多目標(biāo)、動態(tài)、不確定以及無模型等復(fù)雜問題，如何設(shè)計高效的求解方法，也是共享單車調(diào)度面臨的新問題。

4 結(jié)語

共享單車調(diào)度模型和方法研究已經(jīng)有了很多成果。本文歸納了現(xiàn)有模型的構(gòu)建方法，總結(jié)了該領(lǐng)域中算法的研究進(jìn)展，也對存在的挑戰(zhàn)與展望進(jìn)行了討論。隨著智能技術(shù)的不斷發(fā)展，大數(shù)據(jù)、人工智能等的融合，必然會豐富共享單車調(diào)度方法，加快該領(lǐng)域的發(fā)展。