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

0 引言

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

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

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

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

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

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

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

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

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

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

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

共享單車調(diào)度問(wèn)題本質(zhì)上是一個(gè)組合優(yōu)化問(wèn)題，為了獲得更高效的調(diào)度方案，許多學(xué)者對(duì)共享單車調(diào)度方法進(jìn)行了研究。目前，共享單車調(diào)度的方法主要有如下兩類：精確算法和啟發(fā)式算法求解。精確算法主要包括分支定界法、割平面法、動(dòng)態(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)度方法

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

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

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

3 挑戰(zhàn)與展望

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

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

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

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

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

4 結(jié)語(yǔ)

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