基于兩階段調(diào)度策略下的公共自行車調(diào)度模型與優(yōu)化方法

成先鏡，呂亞楠,翁小勇，孫澤新，陳小勇

（遵義師范學(xué)院a.黔北信息技術(shù)研究院；b.數(shù)學(xué)學(xué)院貴州遵義563006）

隨著經(jīng)濟全球化、區(qū)域一體化的快速發(fā)展，環(huán)境污染、能源浪費、汽車尾氣排放等給城市發(fā)展帶來一系列問題，“綠色出行”理念越來越深入人心。2005年以來我國陸續(xù)推出的公共自行車租賃系統(tǒng)正是出于節(jié)約道路資源、減少環(huán)境污染、緩解“市民出行難”、打造“綠色城市”的目的而提出的一種低碳交通方式[1]。公共自行車在給城市居民出行提供方便的同時，也出現(xiàn)了用戶借車難、還車難以及自行車租賃公司調(diào)度運營成本高等問題，嚴(yán)重制約了公共自行車的發(fā)展。針對公共自行車發(fā)展過程中存在的問題，建立合理、動態(tài)的調(diào)度系統(tǒng)顯得尤為重要。

關(guān)于調(diào)度模型的研究，國內(nèi)外專家提出了許多不同目標(biāo)下的調(diào)度模型[2,3]。劉登濤[4]以運輸成本最少為目標(biāo)建立了公共自行車交通調(diào)度系統(tǒng)模型；董紅召[5]以最大化租賃點滿意度為目標(biāo)建立了公共慢行系統(tǒng)調(diào)度模型；賀竹磬[6]提出了具有時間窗約束與成本最小的車輛路徑混合整數(shù)非線性調(diào)度模型；秦茜[7]提出了以運輸成本最小和用戶滿意度最大為目標(biāo)的調(diào)度模型；張建國[8]將調(diào)度時間分為平峰和高峰，建立了租賃點滿意度最大化和調(diào)度成本最小化的調(diào)度模型；Raviv[9]以調(diào)度路徑長度和用戶滿意度為目標(biāo)，提出了基于時間、基于調(diào)度序列和基于弧的MIP模型；Chemla[10]提出了以實現(xiàn)最優(yōu)平衡為目標(biāo)的調(diào)度模型；Benchimol[11]將平衡作為最主要的約束，提出了以總的調(diào)度路徑長度為目標(biāo)的調(diào)度模型；Vogel[12]以獲取站點的最優(yōu)填充水平為目標(biāo)，提出了一個擴展的動態(tài)服務(wù)網(wǎng)絡(luò)設(shè)計模型下的MIP模型。但這些研究都未針對用戶借車難、還車難為主要目標(biāo)設(shè)計調(diào)度模型，而利用預(yù)測機制能快速準(zhǔn)確地對租賃點的需求進行預(yù)測，能解決借車難和還車難的問題；此外，降低調(diào)度成本也是設(shè)計調(diào)度模型需要考慮的目標(biāo)之一。

1 兩階段調(diào)度策略

當(dāng)前公共自行車調(diào)度系統(tǒng)采用的是貪心策略，即先從距離調(diào)度中心最近的租賃點開始進行調(diào)度，逐步到最遠的租賃點，調(diào)度完畢后返回調(diào)度中心。一旦公共自行車系統(tǒng)中的租賃點提出調(diào)度請求，調(diào)度人員就必須對其進行調(diào)度，而在調(diào)度系統(tǒng)中存在一些地理位置較偏遠或需要運入/運出自行車數(shù)量較少的租賃點，調(diào)度系統(tǒng)在為這些租賃點進行調(diào)度時便增加了調(diào)度的成本。這種調(diào)度策略缺乏全局考慮，僅僅是局部最優(yōu)解。因此，本文提出了兩階段調(diào)度策略，將調(diào)度過程分為兩個階段來進行：

（1）根據(jù)租賃點裝/卸載自行車數(shù)量的大小、地理位置的遠近等對租賃點賦予不同的權(quán)重，在首次篩選租賃點時將權(quán)重大的租賃點優(yōu)先進行調(diào)度，滿足相應(yīng)的約束條件，得到可行的租賃點序列和調(diào)度路線。

（2）將權(quán)重小的租賃點與已選租賃點的距離進行比較。若它們之間的距離、時間和成本都是在可接受的范圍內(nèi)，將此租賃點添加進調(diào)度序列，對初始路線進行適當(dāng)調(diào)整，反之，排除此租賃點，繼續(xù)比較下一租賃點，直到租賃點比較完畢。

兩階段調(diào)度策略重點考慮第一個階段，第二個階段在全局基礎(chǔ)上進行局部優(yōu)化。以各租賃點裝/卸載自行車的數(shù)量作為賦予權(quán)重的主要依據(jù)，在第二階段進行租賃點的距離比較時，根據(jù)調(diào)度人員的經(jīng)驗和統(tǒng)計數(shù)據(jù)可知，權(quán)重小的租賃點與距離最近權(quán)重大的租賃點間的距離在1km以內(nèi)是調(diào)度成本可以接受的，由此將各租賃點的對比距離設(shè)為1km。

2 調(diào)度模型

解決用戶借車難、還車難以及降低租賃公司的調(diào)度成本是本研究的主要目的。調(diào)度系統(tǒng)的目標(biāo)包括用戶滿意度、調(diào)度成本和彈性的時間窗。由于調(diào)度的過程是動態(tài)的，租賃點自行車的需求量會隨著時間而發(fā)生變化，需要將調(diào)度時間分為一系列離散的時間段。時間連續(xù)、租賃點狀態(tài)離散的特性符合連續(xù)時間的馬爾科夫鏈的生成過程，從而能精確地進行調(diào)度預(yù)測量的計算。通過對用戶無法租車和無法還車設(shè)置懲罰值進行用戶滿意度的計算[13]。

2.1 懲罰值的計算

采用馬爾科夫鏈的生滅過程[14]對租賃點的自行車需求量作出預(yù)測，生滅過程的變化情況分為三種情形：

圖1 表示租賃點變化的連續(xù)時間的馬爾科夫鏈

租賃點的狀態(tài)有三種即已空、已滿和正常。當(dāng)租賃點狀態(tài)為已空或已滿時，用戶無法進行正常的借還操作，對此設(shè)置懲罰值。將懲罰值分為兩類：

（1）將租賃點狀態(tài)為已空即租賃點可借自行車數(shù)為零、用戶不能借車稱為用戶無法借車的懲罰值。

（2）將租賃點狀態(tài)為已滿即租賃點空位數(shù)為零、用戶不能還車稱為用戶無法還車的懲罰值。

租賃點的懲罰值為用戶無法借車的懲罰值與用戶無法還車的懲罰值之和。

2.2 調(diào)度時間的確定

調(diào)度時間分為三部分：

（1）車輛行駛時間；

（2）車輛沿途遇紅燈延遲的時間；

（3）車輛起停時間及裝/卸自行車時間。

2.3 時間滿意度計算

在調(diào)度系統(tǒng)中，租賃點對調(diào)度車輛的到達有時間要求。因此，本文利用滿意優(yōu)化理論[15,16]對時間進行限制。傳統(tǒng)的車輛調(diào)度將硬性時間窗作為調(diào)度車輛的時間約束，在實際應(yīng)用中，硬性時間窗不能很好地反映出用戶的滿意程度，用戶傾向于在某個特定的時間段或在其他時間段接受服務(wù)，不同時間段的服務(wù)會造成滿意度的變化。設(shè)FAi為租賃點i接受車輛到達的開始時間，為租賃點i接受車輛到達的最晚時間，為租賃點接受i車輛到達的期望時間，如圖2所示。

圖2 租賃點i時間滿意度

調(diào)度時間和時間滿意度之和為：

N0：包含起始點的租賃點集合

Ci：租賃點i的鎖樁數(shù)即容量

kv：調(diào)度車輛的最大載重量

T：調(diào)度周期

tij：租賃點i到的調(diào)度時間

Sit：在時刻租賃點i的可借自行車數(shù)

yijv：時刻，調(diào)度車輛v從租賃點i到裝載的自行車數(shù)

模型目標(biāo)函數(shù)為：

其中，time與f分別為調(diào)度時間和時間滿意度。

3 鄰域搜索算法

在兩階段調(diào)度策略的第二個階段，隨著租賃點的增加，程序運行時間也會增加。在實際調(diào)度過程中，要求快速計算調(diào)度路徑，縮短程序運行時間。由變鄰域[17,18]思想，本文提出了一個縮短程序計算時間的方法，稱之為鄰域搜索算法，步驟如下：

（1）從起點開始搜索附近小于1km的租賃點；

（2）若存在這樣的租賃點，則找出目標(biāo)值最小的一條路徑，將最后的租賃點作為起點進行搜索；若不存在這樣的租賃點，則添加最近的租賃點，將此作為起點繼續(xù)進行下一次搜索。

（3）如果起點剛好為調(diào)度序列終點時，則結(jié)束搜索，否則，回到步驟（2）繼續(xù)進行搜索。

圖3 鄰域搜索算法

該算法是在租賃點1km范圍內(nèi)搜索出租賃點，計算出目標(biāo)值最小的一條路徑，而不是通過排列組合的方式得到所有路徑，再求出目標(biāo)值最小的一條路徑。通過這樣的思想和方法，即可減少程序運行的時間。

4 實驗

在此實驗中，作者選取了溫州市鹿城區(qū)20天公共自行車的調(diào)度數(shù)據(jù)。設(shè)調(diào)度租賃點的懲罰值和調(diào)度時間是相對固定的，對比采用和未采用兩階段調(diào)度模型和鄰域搜索算法的時間滿意度、目標(biāo)值和程序運行時間。

設(shè)調(diào)度時間段為早上6到11點，車輛在每個租賃點的停車時間為5min，每輛自行車的裝/卸時間為1min，車速為30km/h，并假設(shè)調(diào)度車輛的容量足夠大。通過實驗數(shù)據(jù)發(fā)現(xiàn)時間滿意度的值為1時符合實驗的要求，因此，分別設(shè)每1、5、10、15min調(diào)度一次，即分別取值為1，1/5，1/10，1/15。選取10個租賃點進行調(diào)度，如圖4所示。

圖4 租賃點數(shù)為10的數(shù)據(jù)分析

表1 租賃點為10的運行時間(s)

由圖4可知，在對10個租賃點進行調(diào)度時，采用兩階段調(diào)度策略的時間滿意度低，即用戶滿意度高，基于鄰域搜索算法下的兩階段調(diào)度策略的時間滿意度要略低于兩階段調(diào)度策略的時間滿意度，即基于鄰域搜索算法下的兩階段調(diào)度策略用戶滿意度最高。此外，其目標(biāo)值也低于兩階段調(diào)度策略下的目標(biāo)值。

由表1可知，未采用兩階段調(diào)度策略的運行時間長，采用兩階段調(diào)度策略的運行時間顯著少于未采用兩階段調(diào)度策略的運行時間，基于鄰域搜索算法下的兩階段調(diào)度策略的運行時間最短。

圖5 租賃點數(shù)為20的數(shù)據(jù)分析

表2 租賃點為20的程序運行時間(s)

由圖5可知，隨著租賃點的增加，時間滿意度的數(shù)值隨著增加，采用兩階段調(diào)度策略的用戶滿意度高越來越明顯，而采用基于鄰域搜索算法下的兩階段調(diào)度策略得到的時間滿意度更低，目標(biāo)值更小。由表2可知兩階段調(diào)度策略下的程序運行時間顯著縮短，而采用基于鄰域搜索算法下的兩階段調(diào)度策略的運行時間最短，能在較短的時間內(nèi)做出處理，滿足在實際運行中的要求。

由表2可知，采用不同調(diào)度策略的運行時間差別較大：兩階段調(diào)度策略下的運行時間明顯少于未采用兩階段策略下的運行時間，而基于鄰域搜索算法下的兩階段調(diào)度策略時間最短。

圖6 租賃點數(shù)為30的數(shù)據(jù)分析

表3 租賃點為30的運行時間(s)

由圖6可知，在30個調(diào)度租賃點下得到的基于鄰域搜索算法下的兩階段調(diào)度策略的時間滿意度值低于未采用鄰域搜索算法和兩階段調(diào)度策略的時間滿意度值，即采用基于鄰域搜索算法下的兩階段調(diào)度策略的用戶滿意度高。

由表3可知，在30個調(diào)度租賃點下未采用兩階段調(diào)度策略和鄰域搜索算法的運行時間較長，不能在較短的時間內(nèi)作出調(diào)度?；卩徲蛩阉魉惴ㄏ碌膬呻A段調(diào)度策略將程序運行時間控制在0.1s內(nèi)，能快速得到調(diào)度路線，更符合在實際運營過程中的調(diào)度需求。

實驗采用10、20和30個租賃點對比分析了未采用兩階段調(diào)度策略、采用未基于鄰域搜索算法下的兩階段調(diào)度策略和采用基于鄰域搜索算法下的兩階段策略的時間滿意度（即用戶滿意度）、目標(biāo)值和程序運行時間，得到以下結(jié)論：

（1）兩階段調(diào)度得到的時間滿意度更低，即用戶滿意度更高。

（2）隨著租賃點數(shù)的增加，程序運行時間也會增加。由實驗可知，基于鄰域搜索算法下的兩階段調(diào)度策略能夠快速進行調(diào)度，能更好地滿足實際的需求。

（3）未采用兩階段調(diào)度策略的目標(biāo)值較大，采用兩階段調(diào)度策略的目標(biāo)值較低，而基于鄰域搜索算法下的兩階段調(diào)度策略得到的目標(biāo)值最低。

（4）采用基于鄰域搜索算法下的兩階段調(diào)度策略計算時間最短，時間滿意度最低即用戶滿意度高，得到的路線更優(yōu)，在實際應(yīng)用中具有更高的效率，實用性較強。

5 結(jié)語

本文針對公共自行車調(diào)度系統(tǒng)提出了兩階段調(diào)度模型。在第一階段增加了動態(tài)調(diào)度過程中模糊時間窗的概念，在初次調(diào)度時篩選租賃點得到初始路徑；在第二階段通過衡量成本和距離將滿足條件的租賃點添加進調(diào)度序列。通過實驗發(fā)現(xiàn)該模型在實際運行中具有較高的效率。然而，在實驗中也發(fā)現(xiàn)隨著調(diào)度租賃點的增加，程序運行時間較長。針對此問題，提出了鄰域搜索算法，明顯地縮短了運行時間。在動態(tài)調(diào)度過程中還存在很多復(fù)雜的問題，如用戶出行規(guī)律、兩階段模型中篩選租賃點的準(zhǔn)則、早晚高峰期自行車數(shù)量、精確的預(yù)測機制等，將是下一步的研究工作。

[1]龔迪嘉,朱忠東.城市公共自行車交通系統(tǒng)實施機制[J].城市交通,2008,6(6):27-32.

[2]成先鏡,王正偉,冉杰,等.公共自行車調(diào)度模型研究[J].遵義師范學(xué)院學(xué)報,2016,4(18):94-100.

[3]呂亞楠,吳有富,楊正云.一種改進的TOPSIS算法及其在貴陽市水質(zhì)評價中的應(yīng)用研究[J].遵義師范學(xué)院學(xué)報,2016,18(1):91-94.

[4]劉登濤,方文道,章堅民,等.公共自行車交通系統(tǒng)調(diào)度算法[J].計算機系統(tǒng)應(yīng)用,2011,20(9):112-115.

[5]董紅召,趙敬洋,郭海鋒,等.公共慢行系統(tǒng)的動態(tài)調(diào)度建模與滾動時域調(diào)度算法研究[J].公路工程,2009,34(6):68-75.

[6]賀竹磬,孫林巖.動態(tài)交通下車輛路徑選擇模型及算法[J].交通運輸工程學(xué)院學(xué)報,2007,7(1):112-115.

[7]秦茜.公共自行車租賃系統(tǒng)調(diào)度問題研究[D].北京:北京交通大學(xué),2013.

[8]張建國,吳婷,蔣陽升.基于蟻群算法的公共自行車系統(tǒng)調(diào)度算法研究[J].西華大學(xué)學(xué)報,2014,33(3):70-76.

[9]Raviv T,Tzur M,Forma I A.Static Repositioning in a Bike-Sharing System:Models and Solution Approaches[J].EURO J Transp Logist,2013,11(2):187-229.

[10]Chemla D,Meunier F,Calvo R W.Bike sharing systems:Solving the static rebalancing problem[J].Discrete Optimization,2013,10(2):120-146.

[11]Benchimol M,Benchimol P,Chappert B,et al.Balancing The Stations of a Self-Service Bike Hire System[J].RAIRO-Operations Research,2011,45(1):37-61.

[12]Vogel P,Bruno A,Saavedra N,Mattfeld D C.A Hybrid Metaheuristic to Solve the Resource Allocation Problem in Bike Sharing Systems[C].Hybrid Metaheuristics,Lecture Notes in Computer Science 8457,2014.16-29.

[13]成先鏡.公共自行車兩階段調(diào)度策略與模型及求解方法研究[D].南京:南京師范大學(xué),2015.

[14]王梓坤,楊向群.生滅過程與馬爾可夫鏈[M].北京:科學(xué)出版社,2005.

[15]張建勇,郭耀煌,李軍.基于顧客滿意度的多目標(biāo)模糊車輛優(yōu)化調(diào)度問題研究[J].鐵道學(xué)報,2003,25(2):15-17.

[16]Bent R,Pascal V H.A Two-Stage Hybrid Local Search for the Vehicle Routing Problem With Time Windows[J].Transportation Science,2004,38(4):515-530.

[17]董紅宇,黃敏,王興偉,等.變鄰域搜索算法綜述[J].控制工程,2009,7(16):1-13.

[18]Mladenovi′cN,HansenP.Variable Neighborhood Search[J].European Journal of Operational Research,2001,130(3):449-467.