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

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

0 引言

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

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

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

題[8-9]。

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

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

1 問題的描述與建模

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

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

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

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

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

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

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

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

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

2 模型求解

2.1 站點的相似度

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

2.2 遺傳算法

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

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

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

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

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

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

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

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

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

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

3 案例分析

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

3.1 公共自行車站點區(qū)域的層級劃分

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

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

圖2 寧波市公共自行車站點的層級劃分示意圖Fig.2 Sketch map of the hierarchical division of the stations from bike-sharing system in Ningbo

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

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

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

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

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

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

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

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

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

3.3 對比實驗與分析

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

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

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

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

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

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

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

4 結(jié)束語

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

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

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