基于細(xì)節(jié)層次模型的公共自行車(chē)調(diào)度方法*

胡正華 周繼彪 周涵林 張敏捷

（1.寧波工程學(xué)院建筑與交通工程學(xué)院 浙江 寧波 315211；2.浙江大學(xué)信息與電子工程學(xué)院 杭州 310063；3.同濟(jì)大學(xué)交通運(yùn)輸工程學(xué)院 上海 201804）

0 引言

隨著城市化進(jìn)程的不斷加快，汽車(chē)保有量日益增長(zhǎng)，道路交通的擁堵問(wèn)題變得越來(lái)越嚴(yán)峻，致使許多城市的主干路高峰時(shí)段的車(chē)速不足20 km/h。持續(xù)性的道路交通擁堵及其帶來(lái)的諸如尾氣排放和能源浪費(fèi)等一系列社會(huì)問(wèn)題嚴(yán)重阻礙了城市經(jīng)濟(jì)的健康發(fā)展[1-2]；而另一方面，面對(duì)不斷加劇的城市交通問(wèn)題和日益惡化的生態(tài)環(huán)境，“綠色出行”的理念也越來(lái)越受到各國(guó)政府的關(guān)注，大力發(fā)展城市公共交通已經(jīng)成為社會(huì)各界的共識(shí)。作為“低碳”和“綠色”的出行方式，城市公共自行車(chē)的出現(xiàn)受到了許多城市的熱捧。它不僅能夠緩解城市道路的交通壓力，還也可以解決公共交通“最后一公里”的難題。繼北京、上海、廣州之后，許多中小城市也相繼推出了城市公共自行車(chē)的租賃服務(wù)。然而，隨著2015年以來(lái)移動(dòng)互聯(lián)網(wǎng)快速發(fā)展普及，共享單車(chē)入駐各大城市，憑借無(wú)樁化設(shè)計(jì)、移動(dòng)支付定位、智能解鎖等創(chuàng)新型技術(shù)，共享單車(chē)和電動(dòng)車(chē)在一、二線城市中迅速崛起，城市公共自行車(chē)系統(tǒng)受到了不同程度的沖擊[3]。一些城市甚至?xí)和Ａ藢?duì)公共自行車(chē)系統(tǒng)的運(yùn)營(yíng)。公共自行車(chē)系統(tǒng)未來(lái)要如何發(fā)展成為1個(gè)難題。

然而，共享單車(chē)在給出行帶來(lái)便利的同時(shí)，也引發(fā)了諸如“車(chē)輛亂停亂放”“調(diào)度不及時(shí)”“廢棄后無(wú)人回收”等一系列問(wèn)題[4]。特別是在一些大城市里，共享單車(chē)的過(guò)量投放，使得單車(chē)的車(chē)輛堆滿了人行通道，這就給行人的出行帶了極大的不方便，嚴(yán)重影響了行人的道路安全；不僅如此，在許多住宅小區(qū)的門(mén)口和公交站臺(tái)附近經(jīng)常堆滿了各種各樣的單車(chē)或者電動(dòng)自行車(chē)，嚴(yán)重影響了市容市貌和交通秩序。尤其是電動(dòng)自行車(chē)普遍存在“車(chē)輛運(yùn)行安全風(fēng)險(xiǎn)高”“電池污染嚴(yán)重”“火災(zāi)隱患突出”等問(wèn)題[5]?；诖?，交通運(yùn)輸部發(fā)布了《關(guān)于鼓勵(lì)和規(guī)范互聯(lián)網(wǎng)租賃自行車(chē)發(fā)展的指導(dǎo)意見(jiàn)》，明確提出“不鼓勵(lì)發(fā)展互聯(lián)網(wǎng)租賃電動(dòng)自行車(chē)，建議各地審慎對(duì)待，從嚴(yán)掌握”。許多城市的政府部門(mén)相繼出臺(tái)了相應(yīng)的政策方針，開(kāi)始限制甚至取締了共享單車(chē)和共享電動(dòng)車(chē)的使用；有些城市則是保留了部分共享單車(chē)的投放使用，但為了有效的控制亂停亂放的現(xiàn)象，設(shè)定了指定的停車(chē)點(diǎn)；還有一些城市則是設(shè)定了共享單車(chē)的可使用區(qū)域，超出區(qū)域之外則無(wú)法為用戶(hù)提供服務(wù)。在這樣的背景下，城市的公共自行車(chē)系統(tǒng)的發(fā)展又一次迎來(lái)了春天。

然而，城市的公共自行車(chē)系統(tǒng)依舊存在其發(fā)展的瓶頸。首先，對(duì)于公共自行車(chē)而言，其自行車(chē)和站點(diǎn)的數(shù)量與共享單車(chē)相差很大。從分布密度上看，共享單車(chē)的投放密度已經(jīng)比公共自行車(chē)高出十余倍。其次，政府對(duì)公共自行車(chē)系統(tǒng)維護(hù)的投入力度不夠。尤其是對(duì)于自行車(chē)車(chē)輛的調(diào)度，許多站點(diǎn)在早晚高峰時(shí)段仍然出現(xiàn)“無(wú)車(chē)可借”或“無(wú)位可還”的現(xiàn)象，導(dǎo)致許多市民放棄使用公共自行車(chē)出行，這就大大降低了公共自行車(chē)的使用率，嚴(yán)重制約了公共自行車(chē)系統(tǒng)的發(fā)展[6-7]。如何高效的將自行車(chē)在各個(gè)租賃點(diǎn)之間進(jìn)行調(diào)度，進(jìn)而使租賃點(diǎn)上的自行車(chē)數(shù)量與用戶(hù)需求相匹配依然是研究學(xué)者關(guān)注的話

題[8-9]。

Haider等[10]通過(guò)使用定價(jià)的方案來(lái)激勵(lì)用戶(hù)從相鄰的站點(diǎn)借還自行車(chē)，結(jié)合單級(jí)重構(gòu)的雙層優(yōu)化模型，從戰(zhàn)略上最大限度地減少不平衡自行車(chē)站點(diǎn)的數(shù)量。實(shí)驗(yàn)結(jié)果表明該方法能夠有效降低了公共自行車(chē)系統(tǒng)的運(yùn)營(yíng)成本。但由于該方法假設(shè)時(shí)間價(jià)值對(duì)所有的用戶(hù)都是相同的，不僅如此，用戶(hù)對(duì)于價(jià)格的變化具有不同程度的敏感性，自行車(chē)使用者的異構(gòu)概率有待進(jìn)一步研究。Kadri等[11]將自行車(chē)車(chē)輛的再平衡問(wèn)題簡(jiǎn)單的建模成1個(gè)帶有附加約束條件的旅行商問(wèn)題，以最小化車(chē)輛再平衡時(shí)間作為模型的目標(biāo)函數(shù)，通過(guò)大量的實(shí)驗(yàn)驗(yàn)證了方法的有效性。Pal等[12]結(jié)合1種混合整數(shù)線性規(guī)劃方法，進(jìn)一步提出了1種混合嵌套鄰域搜索算法，該方法在解決大型公共自行車(chē)系統(tǒng)的靜態(tài)調(diào)度問(wèn)題時(shí)既有效又高效。通過(guò)驗(yàn)證實(shí)驗(yàn)表明，所提出的算法優(yōu)于禁忌搜索算法而具有很強(qiáng)的競(jìng)爭(zhēng)力。Cruz等[13]討論了當(dāng)只有1輛調(diào)度車(chē)可供車(chē)輛的調(diào)度時(shí)，如何在滿足所有自行車(chē)站點(diǎn)的需求，且不違反調(diào)度車(chē)輛負(fù)載限制的基礎(chǔ)上找到1條調(diào)度成本最低的路線，提出了1種基于迭代局部搜索的啟發(fā)式方法，獲得了較好的效果。但是在驗(yàn)證解決方案是否可行時(shí)，需要耗費(fèi)大量的時(shí)間，使得算法的效率得不到應(yīng)有的保障。Ren等[14]旨在最小化包括自行車(chē)車(chē)輛庫(kù)存和調(diào)度成本在內(nèi)的運(yùn)營(yíng)成本，提出了2種混合整數(shù)規(guī)劃方程，以找到調(diào)度車(chē)輛最優(yōu)的調(diào)度線路以及需要調(diào)度的自行車(chē)數(shù)量。通過(guò)實(shí)驗(yàn)驗(yàn)證了所提出的方法比現(xiàn)有解決方案擁有更低的運(yùn)營(yíng)成本。但由于每個(gè)自行車(chē)站的庫(kù)存水平?jīng)]有與倉(cāng)庫(kù)的庫(kù)存一起考慮，該方法仍然存在一定的局限性。Chiariotti等[15]采用“出生-死亡”的過(guò)程來(lái)對(duì)自行車(chē)站點(diǎn)的占用率進(jìn)行建模，并確定重新分配自行車(chē)的時(shí)機(jī)，他們采用圖論來(lái)選擇車(chē)輛調(diào)度的路徑和所涉及的自行車(chē)站點(diǎn)。模擬實(shí)驗(yàn)表明該方法是1種能夠適應(yīng)波動(dòng)性質(zhì)的動(dòng)態(tài)調(diào)度策略，因而優(yōu)于傳統(tǒng)的靜態(tài)調(diào)度方案。但為了使建立的模型在數(shù)學(xué)上可處理，對(duì)其做了相應(yīng)的簡(jiǎn)化，在應(yīng)用到現(xiàn)實(shí)的公共自行車(chē)系統(tǒng)之前，還需要進(jìn)一步的完善。Hu等[16]使用歷史數(shù)據(jù)和預(yù)測(cè)數(shù)據(jù)來(lái)評(píng)估車(chē)輛的調(diào)度需求，以便在調(diào)度范圍內(nèi)避免站點(diǎn)的2次服務(wù)，并提出了1種基于時(shí)間窗的滿意度模型來(lái)評(píng)估用戶(hù)對(duì)公共自行車(chē)系統(tǒng)的滿意度。使用真實(shí)數(shù)據(jù)進(jìn)行的實(shí)驗(yàn)表明，所提出的算法優(yōu)于常規(guī)算法。但是模型中并沒(méi)有考慮運(yùn)輸車(chē)的數(shù)量對(duì)調(diào)度成本的影響，自行車(chē)庫(kù)存變動(dòng)率系數(shù)也是需要在進(jìn)一步的研究中考慮的重要因素。

綜上所述，現(xiàn)有的公共自行車(chē)調(diào)度方案大多基于靜態(tài)的調(diào)度模型，不能針對(duì)公共自行車(chē)系統(tǒng)的動(dòng)態(tài)性做出實(shí)時(shí)的調(diào)整，而且建立的模型所考慮的影響因素過(guò)于簡(jiǎn)單，在應(yīng)用到現(xiàn)實(shí)的公共自行車(chē)系統(tǒng)之前，還需要進(jìn)一步的優(yōu)化。而一些基于動(dòng)態(tài)調(diào)度模型的算法又過(guò)于復(fù)雜，很難針對(duì)每個(gè)城市公共自行車(chē)系統(tǒng)的發(fā)展現(xiàn)狀得到有效的應(yīng)用。本文在已有調(diào)度算法的基礎(chǔ)上，結(jié)合目前城市公共自行車(chē)系統(tǒng)的發(fā)展瓶頸，提出了1種基于細(xì)節(jié)層次模型的公共自行車(chē)調(diào)度方法。該方法結(jié)合人類(lèi)認(rèn)知和思維的過(guò)程，以1種準(zhǔn)動(dòng)態(tài)且相對(duì)簡(jiǎn)單、靈活的方式對(duì)城市公共自行車(chē)系統(tǒng)的調(diào)度方案進(jìn)了優(yōu)化，從而有效地改善了城市公共自行車(chē)的運(yùn)營(yíng)效率。

1 問(wèn)題的描述與建模

公共自行車(chē)調(diào)度問(wèn)題解決的是由于公共自行車(chē)借/還需求在時(shí)間和空間分布的不均衡而引發(fā)的“借車(chē)難”“還車(chē)難”問(wèn)題，即在調(diào)度車(chē)數(shù)量一定的情況下，確定各個(gè)租賃點(diǎn)需要調(diào)入或調(diào)出的自行車(chē)數(shù)量以及調(diào)度車(chē)輛最優(yōu)的調(diào)度路徑，使各個(gè)自行車(chē)租賃點(diǎn)的車(chē)輛數(shù)能夠在時(shí)空范圍內(nèi)達(dá)到相對(duì)的平衡，從而在最大程度上滿足市民的出行需求。

為了簡(jiǎn)化模型求解，本文假設(shè)公共自行車(chē)系統(tǒng)中自行車(chē)租賃點(diǎn)和公共自行車(chē)的總數(shù)是有限的。一方面，對(duì)于每輛自行車(chē)而言，只有被鎖在某個(gè)租賃點(diǎn)或者正在被用戶(hù)使用2個(gè)狀態(tài)。另一方面，假設(shè)在城區(qū)范圍內(nèi)設(shè)有一定數(shù)量的自行車(chē)調(diào)度中心用于負(fù)責(zé)其周邊的自行車(chē)站點(diǎn)的車(chē)輛調(diào)度，每個(gè)調(diào)度中心配有擺渡車(chē)對(duì)自行車(chē)進(jìn)行調(diào)度，其運(yùn)載能力保持一定。利用公共自行車(chē)站點(diǎn)的歷史借還車(chē)數(shù)據(jù)結(jié)合深度學(xué)習(xí)模型來(lái)預(yù)測(cè)未來(lái)一定時(shí)間段內(nèi)各個(gè)站點(diǎn)上的借還車(chē)需求。當(dāng)站點(diǎn)樁位的鎖車(chē)比低于或者超過(guò)一定的范圍后，調(diào)度系統(tǒng)將會(huì)自動(dòng)預(yù)警，進(jìn)而生成相應(yīng)的時(shí)間窗，并提醒管理中心的工作人員對(duì)相關(guān)站點(diǎn)進(jìn)行車(chē)輛的調(diào)配。

對(duì)于用戶(hù)而言，如果1個(gè)自行車(chē)站點(diǎn)上無(wú)可用自行車(chē)或者站點(diǎn)無(wú)空閑樁位可以歸還自行車(chē)，則該站點(diǎn)無(wú)法對(duì)用戶(hù)提供服務(wù)，用戶(hù)只能放棄使用公共自行車(chē)出行，這樣就降低了公共自行車(chē)站點(diǎn)的服務(wù)能力。因此，在調(diào)度車(chē)輛在盡可能少的返回調(diào)度中心的前提下，如何根據(jù)各個(gè)租賃站點(diǎn)的需求量，設(shè)計(jì)合理高效的調(diào)度方案，使得調(diào)度車(chē)輛從調(diào)度中心出發(fā)有序通過(guò)各個(gè)有調(diào)度需求的租賃站點(diǎn)后又回到調(diào)度中心。最大可能的滿足居民的出行需求，提高自行車(chē)站點(diǎn)的服務(wù)質(zhì)量。同時(shí)，還要兼顧到公共自行車(chē)系統(tǒng)車(chē)輛調(diào)度的成本，使調(diào)度車(chē)輛的行駛的路程最短或者調(diào)度時(shí)間最短。因此，本文設(shè)計(jì)的公共自行車(chē)車(chē)輛的調(diào)度方案將調(diào)度車(chē)輛的運(yùn)輸成本和用戶(hù)滿意度2個(gè)方面作為優(yōu)化自行車(chē)調(diào)度方案的目標(biāo)函數(shù)。

1）運(yùn)輸成本。要使得調(diào)度車(chē)輛的運(yùn)輸成本最低，只要確保車(chē)輛的行駛路程最短即可。車(chē)輛1次調(diào)度的運(yùn)輸距離見(jiàn)式（1）。

式中：Xij為決策變量，Xij=1代表在某1趟調(diào)度中，運(yùn)輸車(chē)輛從站點(diǎn)i行駛到站點(diǎn)j，Xij=0代表運(yùn)輸車(chē)輛沒(méi)有從站點(diǎn)i行駛到站點(diǎn)j；dij為站點(diǎn)i至站點(diǎn)j的距離，m；n為在某一趟調(diào)度過(guò)程中需要進(jìn)行調(diào)度的站點(diǎn)總數(shù)。

2）用戶(hù)滿意度。用戶(hù)滿意度可以轉(zhuǎn)化為不滿足時(shí)間窗的罰時(shí)成本。具體而言，為了保證用戶(hù)能夠在站點(diǎn)得到所需的服務(wù)，調(diào)度車(chē)輛應(yīng)盡可能在用戶(hù)期望的時(shí)間內(nèi)完成對(duì)站點(diǎn)的調(diào)度。利用軟時(shí)間窗來(lái)對(duì)調(diào)度車(chē)輛的到達(dá)時(shí)間進(jìn)行約束，到達(dá)時(shí)間距離期望時(shí)間點(diǎn)越遠(yuǎn)，懲罰成本越高。公共自行車(chē)調(diào)度模型的時(shí)間窗罰時(shí)成本見(jiàn)式（2）。

式中：Wi為決策變量，表示站點(diǎn)i是否需要被調(diào)度；ti為調(diào)度車(chē)輛到達(dá)站點(diǎn)i的時(shí)間；[ ]Li，Ui為站點(diǎn)i的時(shí)間窗，Li表示站點(diǎn)i期望的最早被調(diào)度時(shí)間，Ui表示站點(diǎn)i期望的最晚被調(diào)度時(shí)間；epu為不滿足時(shí)間窗時(shí)的早到罰時(shí)成本，lpu為晚到罰時(shí)成本。如果調(diào)度車(chē)輛在Li之前到達(dá)站點(diǎn)i，產(chǎn)生過(guò)早調(diào)度損失成本epu×(Li-ti)；如果調(diào)度車(chē)輛在Ui之后到達(dá)站點(diǎn)i，產(chǎn)生延誤調(diào)度成本lpu×(ti-Ui)，否則，不產(chǎn)生時(shí)間窗懲罰成本。

綜上，公共自行車(chē)調(diào)度模型的目標(biāo)函數(shù)見(jiàn)式（3）。

式中：α，β為運(yùn)輸成本與時(shí)間窗罰時(shí)成本所占的權(quán)重；Z1為運(yùn)輸成本；Z2為時(shí)間窗罰時(shí)成本。

2 模型求解

2.1 站點(diǎn)的相似度

傳統(tǒng)的聚類(lèi)算法都是基于站點(diǎn)的空間位置關(guān)系，即利用站點(diǎn)之間的歐式距離來(lái)衡量不同對(duì)象的相似程度而進(jìn)行的[17]。而在對(duì)城市公共自行車(chē)站點(diǎn)進(jìn)行自行車(chē)車(chē)輛的調(diào)度時(shí)，還應(yīng)該考慮到自行車(chē)站點(diǎn)之間的借/還車(chē)情況，將它作為評(píng)價(jià)站點(diǎn)相似度的指標(biāo)之一[18]。將公共自行車(chē)站點(diǎn)之間的歐氏距離以及站點(diǎn)之間的借/還車(chē)情況來(lái)進(jìn)行聚類(lèi)的。這樣會(huì)使得聚類(lèi)結(jié)果中的自行車(chē)站點(diǎn)更具有同質(zhì)性，而不同簇之間的自行車(chē)站點(diǎn)更加異質(zhì)性。即采用這樣的方法得到同1個(gè)簇中的自行車(chē)站點(diǎn)不僅在空間位置上比較靠近；同時(shí)，這些站點(diǎn)之間的借/還車(chē)情況也比較相似。這也為后續(xù)的公共自行車(chē)調(diào)度提供了更好的數(shù)據(jù)基礎(chǔ)。因此，本文借鑒了文獻(xiàn)[18]的設(shè)計(jì)思路，以站點(diǎn)之間的空間距離作為衡量站點(diǎn)間相似度的主體，同時(shí)將借/還車(chē)情況作為權(quán)重，與空間距離一起作為衡量2個(gè)站點(diǎn)之間相似度的依據(jù)。

2.2 遺傳算法

遺傳算法是以決策變量的編碼作為運(yùn)算對(duì)象，以目標(biāo)函數(shù)值作為搜索信息，通過(guò)模擬生物的基因、染色體和遺傳進(jìn)化的方式來(lái)尋找最優(yōu)個(gè)體的過(guò)程，并使用適應(yīng)度函數(shù)值來(lái)評(píng)價(jià)個(gè)體的優(yōu)劣程度。遺傳算法基于概率規(guī)則，參數(shù)對(duì)其搜索效果的影響也比較小，而且可以避免傳統(tǒng)的搜索方法在對(duì)多峰分布的搜索空間進(jìn)行搜索時(shí)容易陷入局部極值點(diǎn)的缺陷，因此具有較好的全局搜索性。同時(shí)遺傳算法具有可擴(kuò)展性，易于與細(xì)節(jié)層次模型混合使用。

2.3 長(zhǎng)短期記憶網(wǎng)絡(luò)

長(zhǎng)短期記憶網(wǎng)絡(luò)（long short-term memory，LSTM）是循環(huán)神經(jīng)網(wǎng)絡(luò)的1種，也是1種時(shí)間循環(huán)神經(jīng)網(wǎng)絡(luò)，具有長(zhǎng)時(shí)記憶功能。它可以很好地刻畫(huà)具有時(shí)空關(guān)聯(lián)的序列數(shù)據(jù)，可以計(jì)算出不穩(wěn)定時(shí)間序列中各個(gè)觀測(cè)值之間的依賴(lài)性，也解決了長(zhǎng)序列訓(xùn)練過(guò)程中存在的梯度消失和梯度爆炸的問(wèn)題。因此，LSTM通常用于時(shí)間序列數(shù)據(jù)預(yù)測(cè)的目的。本文基于LSTM網(wǎng)絡(luò)模型，并結(jié)合公共自行車(chē)的借/還車(chē)序列來(lái)預(yù)測(cè)未來(lái)的借/還車(chē)需求。

2.4 基于細(xì)節(jié)層次模型的公共自行車(chē)調(diào)度算法

1976年，Clark提出了細(xì)節(jié)層次模型的概念[19]。它是指在不影響畫(huà)面視覺(jué)效果的條件下，根據(jù)物體模型的節(jié)點(diǎn)在顯示環(huán)境中所處的位置和重要度，決定物體渲染的資源分配，降低非重要物體的面數(shù)和細(xì)節(jié)度，從而獲得高效率的渲染運(yùn)算，完成對(duì)復(fù)雜場(chǎng)景進(jìn)行快速繪制。目前，細(xì)節(jié)層次模型在多個(gè)領(lǐng)域都得到了應(yīng)用。

基于劃分的層次聚類(lèi)方法是以所有對(duì)象在同1個(gè)簇中作為聚類(lèi)的起點(diǎn)，然后按照一定的規(guī)則逐個(gè)地將每個(gè)集群劃分為更小的集群的過(guò)程[20-21]。從整體上看，基于劃分的層次聚類(lèi)方法也是1種按照某種規(guī)則自頂向下分裂1個(gè)簇的過(guò)程，直到簇中只有1個(gè)對(duì)象或者滿足預(yù)設(shè)的終止條件為止。在眾多的基于劃分的層次聚類(lèi)方法中，結(jié)合譜聚類(lèi)方法的層次聚類(lèi)算法是使用較為廣泛的算法之一。譜聚類(lèi)是從圖論中演化出來(lái)的算法，后來(lái)在聚類(lèi)中得到了廣泛的應(yīng)用。它的主要思想是把所有的數(shù)據(jù)看作空間中的點(diǎn)，這些點(diǎn)之間用邊連接起來(lái)。距離較遠(yuǎn)的2個(gè)點(diǎn)之間的邊權(quán)重值較低，而距離較近的2個(gè)點(diǎn)之間的邊權(quán)重值較高，通過(guò)對(duì)所有數(shù)據(jù)點(diǎn)組成的圖進(jìn)行切圖，讓切圖后不同的子圖間邊權(quán)重和盡可能的低，而子圖內(nèi)的邊權(quán)重和盡可能的高，進(jìn)而達(dá)到聚類(lèi)劃分的目的。

基于譜聚類(lèi)的層次聚類(lèi)算法，設(shè)計(jì)了與之相對(duì)應(yīng)的城市公共自行車(chē)調(diào)度策略。由前文的分析可知，基于譜聚類(lèi)的層次聚類(lèi)算法其實(shí)是1種粒度由粗到細(xì)的劃分過(guò)程，而基于細(xì)節(jié)層次模型的公共自行車(chē)調(diào)度算法的本質(zhì)則是1種調(diào)度粒度由大到小，不斷細(xì)化的過(guò)程。

在得到了相應(yīng)的站點(diǎn)劃分區(qū)域以后，首先利用劃分粒度最大的區(qū)域作為頂層的調(diào)度單元，其次利用每個(gè)簇中站點(diǎn)的自行車(chē)借/還需求來(lái)制定相應(yīng)的調(diào)度方案，并將其作為最高層級(jí)的自行車(chē)調(diào)度策略。對(duì)于每個(gè)調(diào)度單元，依次獲取下一層級(jí)的公共自行車(chē)站點(diǎn)的聚類(lèi)劃分方案，同樣作為相應(yīng)的自行車(chē)調(diào)度單元，形成第二層級(jí)的調(diào)度策略。按照這樣的規(guī)則遍歷由基于譜聚類(lèi)的層次聚類(lèi)算法得到的不同層級(jí)上的站點(diǎn)簇，同時(shí)根據(jù)同一層級(jí)內(nèi)不同簇之間自行車(chē)的借/還總需求來(lái)制定相應(yīng)的調(diào)度方案。這樣把每一層的調(diào)度策略整合到一起，最終形成1個(gè)類(lèi)似樹(shù)結(jié)構(gòu)的調(diào)度方案，也就是本文提出的基于細(xì)節(jié)層次模型的城市公共自行車(chē)調(diào)度算法，其完整的流程見(jiàn)圖1。

圖1 基于細(xì)節(jié)層次模型的公共自行車(chē)調(diào)度算法流程圖Fig.1 The flow chart of the rebalancing algorithm based on the hierarchical scheme for bike-sharing system

綜上所述，基于細(xì)節(jié)層次模型的公共自行車(chē)調(diào)度算法實(shí)質(zhì)上是1個(gè)由粗到細(xì)統(tǒng)籌、規(guī)劃的過(guò)程。這也充分體現(xiàn)了人類(lèi)從宏觀到微觀的認(rèn)知過(guò)程。當(dāng)決策者在實(shí)施車(chē)輛的調(diào)度時(shí)，總是先從宏觀上來(lái)統(tǒng)籌和規(guī)劃車(chē)輛的調(diào)配，然后再逐步細(xì)化到1個(gè)更小的區(qū)域來(lái)調(diào)配車(chē)輛，而不會(huì)一開(kāi)始就著眼于某個(gè)自行車(chē)站點(diǎn)的調(diào)度需求。因此，本文提出的公共自行車(chē)調(diào)度算法也符合人類(lèi)認(rèn)知和思維的過(guò)程。

3 案例分析

本文的實(shí)驗(yàn)采用Python語(yǔ)言開(kāi)發(fā)，其測(cè)試與運(yùn)行環(huán)境均在Windows 10操作系統(tǒng)下進(jìn)行。實(shí)驗(yàn)首先基于公共自行車(chē)站點(diǎn)的相似度矩陣，利用譜聚類(lèi)算法對(duì)所有站點(diǎn)所在的區(qū)域進(jìn)行劃分。接著對(duì)每個(gè)劃分得到的區(qū)域遞歸地執(zhí)行譜聚類(lèi)，形成空間范圍由大到小的站點(diǎn)簇，作為不同層級(jí)上自行車(chē)的調(diào)度單元。然后從頂層的調(diào)度單元開(kāi)始，利用站點(diǎn)的歷史借/還車(chē)數(shù)據(jù)和LSTM網(wǎng)絡(luò)模型預(yù)測(cè)在未來(lái)時(shí)段內(nèi)各個(gè)調(diào)度單元之間的借/還車(chē)總需求；同時(shí)，結(jié)合遺傳算法對(duì)每一層級(jí)上的各個(gè)調(diào)度單元進(jìn)行調(diào)度；最后將不同層級(jí)上的調(diào)度方案疊加在一起，形成1種調(diào)度粒度由粗到細(xì)的調(diào)度策略。通過(guò)與傳統(tǒng)的調(diào)度方案對(duì)比證明本文提出的公共自行車(chē)調(diào)度算法具有明顯的優(yōu)越性。

3.1 公共自行車(chē)站點(diǎn)區(qū)域的層級(jí)劃分

寧波市公共自行車(chē)系統(tǒng)經(jīng)過(guò)多年的發(fā)展，已經(jīng)基本覆蓋到每個(gè)縣市區(qū)。到目前為止，該系統(tǒng)已經(jīng)取得了可觀的實(shí)施效果。寧波市市民可以根據(jù)市民卡或者公交卡在公共自行車(chē)站點(diǎn)刷卡借/還公共自行車(chē)，并且每個(gè)站點(diǎn)上都詳細(xì)記錄了用戶(hù)的借/還車(chē)刷卡記錄。以主城區(qū)為例，該區(qū)域內(nèi)共有公共自行車(chē)站點(diǎn)169個(gè)，鎖車(chē)樁5 428個(gè)。

選取寧波市主城區(qū)的公共自行車(chē)站點(diǎn)作為實(shí)驗(yàn)對(duì)象，對(duì)其進(jìn)行了細(xì)節(jié)層次的聚類(lèi)劃分，見(jiàn)圖2。其中的圓點(diǎn)代表區(qū)域中的每個(gè)公共自行車(chē)租賃點(diǎn)。首先，將主城區(qū)范圍內(nèi)的所有公共自行車(chē)站點(diǎn)的集合視為1個(gè)簇，作為層次劃分方案的起點(diǎn)。然后，調(diào)用譜聚類(lèi)方法對(duì)該節(jié)點(diǎn)所包含的自行車(chē)站點(diǎn)進(jìn)行聚類(lèi)劃分，形成在空間范圍內(nèi)較原始的站點(diǎn)簇更小的子簇，作為第1層級(jí)的劃分方案，見(jiàn)圖2（a）中的區(qū)域1，2，3。從圖2中可以清楚的發(fā)現(xiàn)，通過(guò)1次聚類(lèi)劃分，整個(gè)公共自行車(chē)站點(diǎn)所在的區(qū)域被劃分成了3個(gè)子區(qū)域；這些站點(diǎn)簇從空間范圍上來(lái)看，占據(jù)的空間還比較大，包含的站點(diǎn)數(shù)量也相對(duì)較多，站點(diǎn)的分布密度較小，排列比較稀疏。最后，對(duì)一次劃分得到的每個(gè)簇，再次構(gòu)建相似度矩陣并結(jié)合譜聚類(lèi)算法進(jìn)行進(jìn)一步的劃分，得到第2層級(jí)的劃分方案，見(jiàn)圖2（b）。按照這樣的劃分過(guò)程不斷地繼續(xù)下去，直到每個(gè)簇中站點(diǎn)之間的平均距離小于1 km（根據(jù)實(shí)施過(guò)程中的外部條件，如負(fù)責(zé)調(diào)度的車(chē)輛數(shù)、站點(diǎn)之間的平均距離等因素來(lái)綜合考慮），則整個(gè)劃分的流程結(jié)束，見(jiàn)圖2（c）。隨著不斷的劃分，得到子簇的空間范圍會(huì)越來(lái)越小，每個(gè)子簇中的自行車(chē)站點(diǎn)的數(shù)量也越來(lái)越少，站點(diǎn)的分布密度越來(lái)越高。將多個(gè)不同空間范圍大小的簇疊加在一起，就形成了1個(gè)劃分粒度由大到小，類(lèi)似樹(shù)狀結(jié)構(gòu)的自行車(chē)站點(diǎn)區(qū)域的層級(jí)劃分方案。

圖2 寧波市公共自行車(chē)站點(diǎn)的層級(jí)劃分示意圖Fig.2 Sketch map of the hierarchical division of the stations from bike-sharing system in Ningbo

從宏觀上看，基于譜聚類(lèi)的層次聚類(lèi)方法就是將公共自行車(chē)站點(diǎn)所在的主城區(qū)范圍按照不同的劃分粒度進(jìn)行由粗到細(xì)的劃分，形成分布區(qū)域由大到小的空間區(qū)域。這也為本文將要提出的基于細(xì)節(jié)層次模型的公共自行車(chē)調(diào)度算法提供了數(shù)據(jù)準(zhǔn)備。

3.2 基于細(xì)節(jié)層次模型的公共自行車(chē)調(diào)度實(shí)例與分析

為了減少計(jì)算量，實(shí)驗(yàn)將層級(jí)劃分方案中最后1層上的自行車(chē)站點(diǎn)形成的簇作為最底層的調(diào)度單元，即不再對(duì)該單元中的站點(diǎn)進(jìn)行劃分。將當(dāng)前層級(jí)中每個(gè)簇所在的自行車(chē)站點(diǎn)區(qū)域作為每個(gè)層級(jí)的車(chē)輛調(diào)度單元，結(jié)合各個(gè)單元內(nèi)自行車(chē)借/還需求的總和，對(duì)自行車(chē)進(jìn)行調(diào)度。然后把每個(gè)層級(jí)上的車(chē)輛調(diào)度方案疊加在一起，形成1個(gè)調(diào)度粒度由粗到細(xì)的公共自行車(chē)調(diào)度方案。

實(shí)驗(yàn)利用歷史借/還車(chē)數(shù)據(jù)（2017年1月1日—6月29日）并結(jié)合長(zhǎng)短期記憶網(wǎng)絡(luò)LSTM對(duì)2017年6月30日早高峰（07：30—08：30）時(shí)刻城區(qū)各自行車(chē)站點(diǎn)的借/還車(chē)需求進(jìn)行了預(yù)測(cè)。同時(shí)，本文設(shè)置公共自行車(chē)站點(diǎn)的報(bào)警閾值為0.4和0.6，即當(dāng)站點(diǎn)的車(chē)輛飽和度超出閾值區(qū)間[0.4，0.6]時(shí)，站點(diǎn)發(fā)出預(yù)警信號(hào)，然后生成以超過(guò)閾值的報(bào)警時(shí)間為中心，每個(gè)層級(jí)上固定長(zhǎng)度的時(shí)間窗，最后統(tǒng)計(jì)各個(gè)調(diào)度區(qū)域內(nèi)總的借/還自行車(chē)需求量，見(jiàn)表1。

表1 早高峰時(shí)各調(diào)度單元的自行車(chē)需求與相應(yīng)的時(shí)間窗Tab.1 Demand and the corresponding time window of each rebalancing unit during morning peak

利用遺傳算法求解調(diào)度車(chē)在當(dāng)前層級(jí)上不同小區(qū)域之間最佳的調(diào)度方案，盡可能減少調(diào)度車(chē)輛返回調(diào)度中心進(jìn)行車(chē)輛裝配的次數(shù)，從而減少車(chē)輛的調(diào)度成本。其中，遺傳算法所涉及的核心參數(shù)包括種群規(guī)模100，迭代次數(shù)為1 000，變異率為0.10，車(chē)輛行駛速度為14.4 km/h，裝卸1輛自行車(chē)的時(shí)間為50 s，調(diào)度車(chē)輛的最大運(yùn)載量為300，初始裝載量為150。最終求解出各個(gè)層級(jí)上站點(diǎn)的調(diào)度方案，見(jiàn)表2，調(diào)度方案的示意圖見(jiàn)圖3。

圖3 調(diào)度方案的示意圖Fig.3 Sketch map of the rebalancing scheme

表2 不同層級(jí)上各調(diào)度單元之間的調(diào)度方案Tab.2 Rebalancing scheme between each unit on different levels

調(diào)度車(chē)輛首先從第1層級(jí)上的調(diào)度中心出發(fā)，先后經(jīng)過(guò)該層級(jí)上需要進(jìn)行調(diào)度的站點(diǎn)簇，最后返回調(diào)度中心，完成第1層級(jí)的調(diào)度任務(wù)（例如C0→C1→C3→C0，在該算例中區(qū)域2處于自平衡狀態(tài)，因此無(wú)需進(jìn)行調(diào)度）。然后在當(dāng)前層級(jí)的各個(gè)調(diào)度單元內(nèi)，繼續(xù)統(tǒng)計(jì)每個(gè)簇中下1個(gè)層級(jí)上各個(gè)子簇之間的自行車(chē)使用需求，再次調(diào)用遺傳算法計(jì)算最優(yōu)的調(diào)度路線，使調(diào)度車(chē)輛從當(dāng)前調(diào)度區(qū)域內(nèi)的某個(gè)調(diào)度單元出發(fā)，先后經(jīng)過(guò)本區(qū)域內(nèi)每個(gè)需要進(jìn)行調(diào)度的站點(diǎn)子簇，最后返回到出發(fā)的調(diào)度單元，完成第2層級(jí)的調(diào)度任務(wù)（例如C1→C12→C11→C1）。這個(gè)過(guò)程一直執(zhí)行下去，每輛調(diào)度車(chē)都依據(jù)上1個(gè)層級(jí)的調(diào)度結(jié)果，結(jié)合本層級(jí)上各個(gè)站點(diǎn)簇之間的自行車(chē)使用需求，并結(jié)合遺傳算法計(jì)算最優(yōu)的調(diào)度路線對(duì)車(chē)輛實(shí)施調(diào)度，直到完成所有站點(diǎn)的調(diào)度任務(wù)為止。

3.3 對(duì)比實(shí)驗(yàn)與分析

本文將提出的基于細(xì)節(jié)層次模型的公共自行車(chē)調(diào)度算法與傳統(tǒng)的調(diào)度算法（不分層調(diào)度）進(jìn)行了比較試驗(yàn)，為了使結(jié)果更加的清晰，在本次實(shí)驗(yàn)中，我們只安排1輛調(diào)度車(chē)進(jìn)行調(diào)度，同樣利用遺傳算法對(duì)每趟調(diào)度路徑進(jìn)行求解（參數(shù)同前）。實(shí)驗(yàn)結(jié)果見(jiàn)圖4。

圖4 傳統(tǒng)調(diào)度方案與本文調(diào)度方案對(duì)比圖Fig.4 Comparison of the traditional rebalancing scheme and the one proposed in the article

如果使用傳統(tǒng)的調(diào)度方法，則調(diào)度車(chē)輛將從調(diào)度中心出發(fā)直接對(duì)所有站點(diǎn)進(jìn)行調(diào)度，通過(guò)遺傳算法計(jì)算出針對(duì)每個(gè)站點(diǎn)的調(diào)度方案，見(jiàn)表3，調(diào)度車(chē)在整個(gè)過(guò)程中的行駛總長(zhǎng)度為700 005.58 m，有效調(diào)度時(shí)間為291.70 min。而基于本文提出的調(diào)度方案，首先將實(shí)驗(yàn)區(qū)域進(jìn)行層次聚類(lèi)劃分，并在此基礎(chǔ)上進(jìn)行細(xì)節(jié)層次的車(chē)輛調(diào)度。各子區(qū)域中每條調(diào)度路徑的總長(zhǎng)度見(jiàn)表4。通過(guò)對(duì)不同層級(jí)上統(tǒng)計(jì)數(shù)據(jù)的累加，計(jì)算出使用本文提出的調(diào)度方法，調(diào)度車(chē)的行駛總長(zhǎng)度為40 111.38 m，有效調(diào)度時(shí)間為167.13 min，與傳統(tǒng)的調(diào)度方法相比，大約提升了42.7%的調(diào)度效率。

表3 傳統(tǒng)調(diào)度方法的調(diào)度路徑長(zhǎng)度與調(diào)度時(shí)間Tab.3 The length of the path and the rebalancing time of the traditional method

表4 基于層次調(diào)度方法的路徑長(zhǎng)度與調(diào)度時(shí)間Tab.4 The length of the path and the rebalancing time of the hierarchical method

可見(jiàn)，本文提出的調(diào)度方法在沒(méi)有增加人力成本和實(shí)施難度的前提下，就可以有效縮短總的調(diào)度距離和調(diào)度時(shí)間。這樣可以盡可能滿足用戶(hù)對(duì)自行車(chē)的使用需求，提高城市公共自行車(chē)系統(tǒng)的整體服務(wù)能力。因此，這是1種經(jīng)濟(jì)、實(shí)用的公共自行車(chē)調(diào)度方案。在具體的實(shí)施過(guò)程中，當(dāng)調(diào)度車(chē)到達(dá)當(dāng)前調(diào)度區(qū)域的中心點(diǎn)后，先對(duì)下層的子區(qū)域內(nèi)實(shí)施調(diào)度（有點(diǎn)類(lèi)似于對(duì)樹(shù)的深度優(yōu)先遍歷方法），然后在下層的子區(qū)域內(nèi)完成調(diào)度后回到當(dāng)前層后對(duì)下1個(gè)調(diào)度單元進(jìn)行調(diào)度。當(dāng)調(diào)度車(chē)輛比較充裕的情況下，可以在當(dāng)前層級(jí)安排調(diào)度車(chē)輛來(lái)實(shí)現(xiàn)集群之間的調(diào)度，并在下1個(gè)層級(jí)的每個(gè)子區(qū)域分配其他調(diào)度車(chē)輛執(zhí)行調(diào)度。

城市公共自行車(chē)車(chē)輛的調(diào)度算法是解決公共自行車(chē)車(chē)輛借/還需求時(shí)空分布不均衡問(wèn)題的關(guān)鍵。實(shí)驗(yàn)證明本文提出的公共自行車(chē)調(diào)度方法可以較好的提升城市公共自行車(chē)系統(tǒng)的調(diào)度響應(yīng)速度和服務(wù)質(zhì)量，降低系統(tǒng)的維護(hù)成本。如果將本文的方法應(yīng)用于各大城市的公共自行車(chē)系統(tǒng)的運(yùn)營(yíng)管理，不僅有助于提升公共自行車(chē)的服務(wù)水平，提高市民對(duì)公共自行車(chē)系統(tǒng)的滿意度，更能有效地引導(dǎo)人們使用公共自行車(chē)代替小汽車(chē)出行，從而改善城市道路交通擁堵的現(xiàn)狀。

4 結(jié)束語(yǔ)

本文以滿足借/還車(chē)需求最大化和調(diào)度成本最小化為優(yōu)化目標(biāo)，結(jié)合基于譜聚類(lèi)的層次聚類(lèi)算法，研究了1種基于細(xì)節(jié)層次模型的公共自行車(chē)調(diào)度方案。算法首先將所有自行車(chē)站點(diǎn)的集合看成1個(gè)簇，采用譜聚類(lèi)算法對(duì)其進(jìn)行聚類(lèi)劃分，然后將得到的子簇再利用譜聚類(lèi)算法進(jìn)行聚類(lèi)，形成在空間范圍上更小的簇。按照這樣的規(guī)則不斷執(zhí)行下去，形成對(duì)公共自行車(chē)站點(diǎn)區(qū)域不同粒度的劃分。在每個(gè)層級(jí)結(jié)構(gòu)中，將每個(gè)子簇所在的空間范圍看成1個(gè)調(diào)度單元，統(tǒng)計(jì)各個(gè)單元內(nèi)自行車(chē)的借/還需求總量，并使用遺傳算法求解每個(gè)層級(jí)上最佳的調(diào)度方案。最后，將每個(gè)層級(jí)上的調(diào)度方案疊加在一起，形成1種調(diào)度粒度由粗到細(xì)的調(diào)度方案。

并以寧波市主城區(qū)的公共自行車(chē)系統(tǒng)為例，詳細(xì)驗(yàn)證了該算法的可行性和實(shí)用性。對(duì)比實(shí)驗(yàn)證明，該調(diào)度方案能夠有效的減少“借車(chē)難”“還車(chē)難”的情況，最大程度的滿足借還車(chē)需求，提升自行車(chē)站點(diǎn)的服務(wù)能力，提高用戶(hù)使用公共自行車(chē)的滿意度水平。因此，本文的研究可以為城市公共自行車(chē)車(chē)輛的調(diào)度提供有效的理論依據(jù)，也可以對(duì)相關(guān)部門(mén)進(jìn)行公共自行車(chē)調(diào)度提供重要的指導(dǎo)意義。

本文仍存在一些不足。例如，在構(gòu)建模型時(shí)，時(shí)間窗的長(zhǎng)度設(shè)置成了固定值。文中并沒(méi)有討論這個(gè)值的設(shè)置對(duì)算法結(jié)果的影響。在后續(xù)的研究中，還將針對(duì)站點(diǎn)借/還車(chē)需求的分布特征，分析設(shè)置不同時(shí)間窗長(zhǎng)度對(duì)算法的影響，從而確定時(shí)間窗的最優(yōu)值。最后希望本研究的貢獻(xiàn)能給從事該領(lǐng)域的研究人員帶來(lái)一些啟發(fā)或指導(dǎo)，我們將進(jìn)一步研究城市公共自行車(chē)系統(tǒng)的智能調(diào)度策略。