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

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

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

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

1 兩階段調度策略

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

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

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

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

2 調度模型

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

2.1 懲罰值的計算

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

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

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

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

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

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

2.2 調度時間的確定

調度時間分為三部分：

（1）車輛行駛時間；

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

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

2.3 時間滿意度計算

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

圖2 租賃點i時間滿意度

調度時間和時間滿意度之和為：

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

Ci：租賃點i的鎖樁數即容量

kv：調度車輛的最大載重量

T：調度周期

tij：租賃點i到的調度時間

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

yijv：時刻，調度車輛v從租賃點i到裝載的自行車數

模型目標函數為：

其中，time與f分別為調度時間和時間滿意度。

3 鄰域搜索算法

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

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

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

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

圖3 鄰域搜索算法

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

4 實驗

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

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

圖4 租賃點數為10的數據分析

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

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

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

圖5 租賃點數為20的數據分析

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

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

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

圖6 租賃點數為30的數據分析

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

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

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

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

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

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

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

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

5 結語

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

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

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

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

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

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

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

[7]秦茜.公共自行車租賃系統調度問題研究[D].北京:北京交通大學,2013.

[8]張建國,吳婷,蔣陽升.基于蟻群算法的公共自行車系統調度算法研究[J].西華大學學報,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]成先鏡.公共自行車兩階段調度策略與模型及求解方法研究[D].南京:南京師范大學,2015.

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

[15]張建勇,郭耀煌,李軍.基于顧客滿意度的多目標模糊車輛優(yōu)化調度問題研究[J].鐵道學報,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.