公共自行車調度模型研究

成先鏡，王正偉，冉 杰，龍圣杰

（遵義師范學院數學與計算科學學院，貴州遵義563002）

公共自行車調度模型研究

成先鏡，王正偉，冉 杰，龍圣杰

（遵義師范學院數學與計算科學學院，貴州遵義563002）

隨著大氣污染日趨嚴重，“綠色出行”理念越來越深入人心，公共自行車系統應運而生，并得到迅猛發展。但在實際運營過程中存在的調度問題，即如何解決用戶“借車難、還車難”和如何使企業運營成本最小化，始終制約著公共自行車系統的長期發展。根據國內外運營經驗和相關研究成果發現，合理的調度是解決這些問題的關鍵所在。作者在分析各種調度優化模型和策略的基礎上，提出了一個多目標的調度優化模型。

公共自行車系統；調度問題；多目標調度優化模型

氣候變化、生態惡化越來越影響到人類的生存與發展，碳排放成為影響全球氣候變暖的首要因素。而爆發性增長的小汽車則是碳排放的主要制造者之一，它們引發了交通擁堵、空氣污染、噪聲污染、能源消耗加大等諸多城市問題。低碳交通，作為一種“低二氧化碳排放”的綠色交通形式，在全世界許多城市正受到越來越多的推崇，而自行車當仁不讓地占據首位[1]。

然而隨著城市公共自行車的發展，也出現了諸多問題。從調度上看主要是用戶在使用過程中出現的還車難和借車難問題，而從運營方來看則要盡量降低自行車調度的成本。只有解決了這兩方面的問題，公共自行車才能得到長足發展。在各租賃點自行車動態變化的情況下，調度系統的優劣決定了運行效率的高低，因此調度系統應有精確的預測機制，預測各租賃點自行車的變化情況，同時各租賃點間自行車的調度時間也是調度系統需要考慮的重要因素之一。

在設計公共自行車調度系統模型時，需要考慮影響調度的所有因素，得到較優的目標函數。國內外針對不同的模型提出了不同的求解方法，如：貪心策略、遺傳算法、車輛調度中的蟻群算法等[2,3]。

1 相關工作

目前，國內外主要圍繞公共自行車調度系統調

度成本進行研究，但側重點有所不同。

國內研究主要以降低成本為目標，目前主要以靜態研究為主，即在某一時段內租賃點自行車數量不隨時間變化而變化，在靜態調度的情況下對公共自行車調度系統進行改進。浙江工業大學研究了公共慢行系統調度過程中租賃點需求的動態特性及其模糊時間窗的約束，為使租賃點的滿意度最大化，為目標建立了公共慢行系統調度模型，并結合滾動時域調度算法對該模型進行求解，從而獲得調度計劃，實現了公共自行車的動態調度[4]。杭州電子科技大學針對公共自行車交通系統的靜態車輛調度問題，以運輸成本最少為目標，建立了公共自行車交通系統調度模型，并用模擬退火算法和遺傳算法的混合算法進行求解，使車輛調度的路程縮短了近50%[2]。北京交通大學根據租賃點的分布情況，利用雙層規劃模型對租賃點的布局進行規劃，從而提高了調度的效率[5]。

國外主要圍繞動態情況下公共自行車調度模型和算法進行研究。Chemla[6]列出了單車輛在靜態情況下（一定的時間段內租賃點自行車需求量無變化）的一些變化。以實現最優的平衡為目標，使用了一個分支界定算法，其搜索策略利用了局部優化的嵌入式禁忌搜索方法。在這個方法中，最重要的因素是調度過程中租賃點的訪問序列，通過基于最大流計算的輔助算法得到裝/卸操作的數量，通過實驗證明這種方法明顯減小了搜索的范圍。Raviv[7]提出了基于時間、基于調度序列和基于弧的MIP模型，以用戶滿意度和調度路徑長度為主要目標，忽略了調度過程中自行車裝/卸操作的數量，該模型在巴黎Velib的60個公共自行車租賃點進行測試，結果表明，在給定的有限時間段內基于弧索引的模型能產生最好的下界，具有一定的彈性。Benchumol[8]將平衡作為最主要的約束，以總的調度路徑長度作為唯一目標，選擇了針對不同目標下的近似算法進行求解。Conardo[9]考察了公共自行車系統在動態情況下（租賃點自行車需求量隨著時間變化而變化）平衡的變化，使用了一個基于弧流量和針對時空網絡模型的計算方法，在100個租賃點和60個時間段內對該算法進行了測試，發現誤差較大。

BBSS（Bicycle Balance Share System）與傳統車輛調度問題（VehicleRoutingProblem,VRP）[5,10,11]有很多聯系，但又有所區別。BBSS允許調度車輛多次訪問租賃點，每次訪問租賃點時裝/卸自行車的數量是任意的。根據BBSS的特性可認為，BBSS是一個調度車輛容量有限的具有裝/卸操作的單車輛VRP[18]。

現有的模型和求解方法擁有各自的優缺點。目前，較為優化和具有實際意義的模型利用了預測的機制，通過連續時間的馬爾科夫鏈的生成過程對租賃點在未來一個時間段內是否進行調度做出判斷，根據相應的約束得到可行的調度序列。本文在此基礎上提出了多目標的調度優化模型。

2 調度模型研究

公共自行車系統的調度模型構建主要是圍繞降低成本、用戶滿意度和調度時間展開，目前有以下幾種較為常見的模型。

2.1 圍繞用戶滿意度的公共自行車調度模型

董紅召等[4]將模糊時間窗下的顧客滿意度轉化為公共自行車系統中用戶的滿意度，建立了公共慢性系統的動態調度模型，目標函數如下：

其中，

約束條件如下：

式（1）為目標函數，以總的用戶滿意度最大化為目標。式（2）表示在調度過程中對租賃點進行卸載的自行車數量不能超過調度車輛的最大載重量。式（3）表示任意一個有調度需求的租賃點至少有一輛調度的車輛。

2.2 圍繞調度成本和調度時間的公共自行車調度模型

劉登濤等[2]主要針對靜態情況下的公共自行車調度進行研究，以運輸成本最小化為目標建立調度模型。在調度模型中，各個租賃點之間的距離和需求量都是已知的。

模型參數如下：

由式（4）可知調度模型的目標函數包括調度車輛的固定成本和行駛成本，運營成本為這兩部分成本之和。式（5）表示調度車輛最大數目為m。式（6）表示調度車輛必須返回調度中心。式（7）表示調度車輛對租賃點只服務一次。式（8）表示每次租賃點進行調度時運出的公共自行車數量不能超過調度車輛的最大載重量。

2.3 復合模型

在公共自行車調度過程中，租賃點的需求量和實際調度后的數量、租賃點裝/卸公共自行車數量和調度時間是衡量調度效率的重要指標。Marian[12]針對這三個方面建立了較為復雜的調度模型。此模型在調度的過程中，主要關注兩部分：按序訪問租賃點的路徑和租賃點進行裝/卸的自行車數量。

模型參數如下：

調度平衡后的自行車數：

以上三類調度模型各有優缺點。圍繞用戶滿意度模型忽略了調度成本和調度時間，單純地追求用

戶滿意度最大化。圍繞調度成本和調度時間模型追求調度成本和調度時間的最小化，忽略了用戶滿意度。復合模型將用戶滿意程度轉化為將調度成本轉化為計算租賃點裝/卸自行車的數量和調度時間，考慮得比較全面，而在實際調度中，發現偏差的值很難得到，因此，需要將此模型進行轉化，可通過精確的預測機制求得偏差建立一個新的、易求解的調度模型，也即多目標調度優化模型。

3 多目標調度優化模型

公共自行車調度的目的是為了解決用戶借車難和還車難的問題，旨在滿足用戶滿意度的前提下，使調度成本最低。影響調度效率的三個因素為用戶滿意度、調度成本和彈性時間窗。用戶滿意度的計算，需要采用預測機制，利用以往租賃點的歷史數據，預測出在未來一個時間段內租賃點自行車的需求量。調度的過程是動態的，租賃點自行車的需求量隨著時間的變化而變化，此時，將調度時間分為一系列小的時間段。這種時間連續、租賃點狀態離散的特點符合連續時間的馬爾科夫鏈的生成過程，結合用戶無法租車和無法還車的懲罰值可得到用戶滿意度；調度的成本與距離密切相關，在計算時通過時間來表示，包括調度車輛根據調度路線在各租賃點間行駛所花費的時間、調度車輛在租賃點停靠的時間、租賃點裝/卸自行車所花費的時間和調度車輛在路口等紅綠燈的時間；調度車輛到達租賃點所需的時間也是公共自行車調度系統的影響因素之一，而租賃點對于調度車輛到達的時間應該具有一定彈性，本文定義為時間滿意度。

模型系數如下：

兩階段調度策略下調度模型的目標函數為：

式（10）為本文中兩階段調度策略下調度模型的目標函數，由以下三部分組成：

（1）租賃點無法還車和無法借車的懲罰值之和的計算。當租賃點無車可借時，對用戶無法借車設置懲罰值并計算，同理，計算租賃點自行車已滿時用戶無法還車的懲罰值。

（2）調度車輛的調度時間。

（3）租賃點的時間滿意度。利用車輛調度中計算模糊時間窗下顧客滿意度的方法，得到公共自行車系統中租賃點對調度車輛到達時間的滿意度。

式（11）表示租賃點i初始時刻的可借自行車數。式（12）表示租賃點i的容量平衡即t時刻租賃點i的可借自行車數為t-1時刻租賃點i的可借自行車數加上調度車輛v對租賃點i調度的裝/卸自行車數。式（13）表示t時刻租賃點i的可借自行車數不能超過租賃點i的容量。式（14）表示開始時刻調度車輛v離開調度中心。式（15）表示結束時刻調度車輛回到調度中心。式（16）表示車輛流量守恒公式，確保調度車輛的調入和調出時的自行車數平衡。式（17）表示調度車輛v的自行車數守恒公式。式（18）表示t時刻從租賃點i到j裝載的自行車數不能超過調度車輛v的最大載重量。式（19）表示調度車輛v在租賃點i需要的裝載量為租賃點i容量和調度車輛最大載重量的最小值。式（20）表示調度車輛v在租賃點i需要的卸載量為租賃點i容量和調度車輛v最大載重量的最小值。式（20）～（24）為相應變量的完整性和非負的線性約束。式（25）和式（26）表示在t時刻調度車輛對租賃點i和j只調度一次。

3.1 租賃點懲罰值的計算

在多約束條件下，調度過程中最重要的一點是在未來時間段租賃點所期待的自行車數，即需要對租賃點是否進行調度做出預測。根據預測出來的結果得到租賃點序列，進行調度。在公共自行車調度的過程中，調度時間是連續的，各租賃點所期待的自行車數會隨著時間的變化而變化。在某一時間段內，租賃點的狀態是離散的即需要裝載、卸載和不變動。這種時間連續、狀態離散的特點符合連續時間馬爾科夫鏈的生成過程的特性。鑒于此，本文用馬爾科夫鏈的生成過程對租賃點做出預測。

生滅過程[13,14]的變化情況分為三種情形：

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

相關參數如下：

p：租賃點可借自行車數為零時用戶無法借車的懲罰值

h：租賃點空車位數為零時用戶無法還車的懲罰值

根據租賃點以往數據得到轉移概率矩陣p，通過笛卡爾積得到從初始到t時刻的概率值

假設用戶無法借車的懲罰值和無法還車的懲罰值是一樣的，即p=h=1。由于租賃點狀態是離散的。所以，得到的目標是用戶在租賃點無法借車和還車懲罰值之和，即

由式（27）得到租賃點的懲罰值之和，對應于式（10）中的p，得到調度的租賃點序列。這種求解方式利用了預測的機制，租賃點生成率和死亡率的值越精確，求得的預測情況就越符合實際情況。

3.2 調度時間

在公共自行車調度過程中，調度時間主要分為以下幾個部分：

（1）調度車輛的行駛時間。行駛的路程越長，所耗費的時間越長，成本越高，反之，成本越低。

（2）調度車輛在所經路段等紅綠燈的時間。

（3）調度車輛在各租賃點的停車時間，主要為裝/卸自行車的時間、停車和起步的時間。

3.3 時間滿意度

在公共自行車調度系統中，調度車輛到達租賃點是有時間要求的。本文引入物流系統滿意優化理論[15]。滿意優化理論的關鍵是建立一個反映變量取值（客觀）與客戶心理反應（主觀）之間關系的數學表達式，也就是客戶滿意度和客戶滿意度函數[16]。傳統的車輛調度系統用硬性的時間窗作為對調度車輛的時間約束，而在實際調度時，硬性的時間窗不能反映顧客的滿意度，顧客可能傾向于在某個特定的時間段內接受服務，也可能在其他時間段內接受服務，在不同的時間段內顧客接受服務會有不同的滿意度。

圖2 顧客i的滿意度

在圖2中，a為顧客滿意的最早服務時間，b為顧客滿意的最晚服務時間，a2為顧客可接受的最早服務時間，bi為顧客可接受的最晚服務時間為顧客滿意的服務區間，為顧客可接受的服務區間，其顧客滿意度公式fi(t)的定義如下：

在本文的公共自行車調度系統中，對到達租賃點的調度車輛有時間限制（即軟時間窗），稱為時間滿意度。將顧客滿意度的概率和計算方法運用到公共自行車調度系統中，由式（10）可知，模型的目標函數得到最小值。故將顧客滿意度函數fi(t)作如下修改：設為租賃點i可接受調度車輛服務的開始時間為租賃點i可接受調度車輛服務的最晚到達時間，為租賃點i期望的服務時間，如圖3所示。

圖3 模糊時間窗

隨著調度車輛達到租賃點時間的不同，相應的時間滿意度也會發生變化。時間滿意度的定義如下：

根據以上定義計算出租賃點的時間滿意度，即式(10)的第三部分。

4 案例分析

選取10租賃點下對未采用兩階段調度策略、采用兩階段調度策略和基于鄰域搜索算法采用兩階段調度策略進行調度。由于上述10個租賃點在不同調度條件下的租賃點懲罰值和調度時間固定不變，故記錄不同租賃點個數的時間滿意度、程序運行時間和目標值進行對比分析，時間系數 分別選取1,1/5,1/10,1/15。

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

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

由表1可知，不同時間系數值的程序運行時間差距較大，其中未采用兩階段調度策略的運行時間最長，采用兩階段調度策略運行時間顯著少于未采用兩階段調度策略的運行時間，而采用基于鄰域搜索算法的兩階段調度策略的運行時間最少。

表1 租賃點為10個時的程序運行時間（s）

5 總結

本文針對公共自行車調度系統存在的問題，對當前的調度模型進行了分析和總結。主要關注了公共自行車系統的動態調度過程模型，針對各調度模型存在的優缺點，結合預測機制、調度時間和用戶滿意度，提出了多目標的調度優化模型。而在動態調度過程中還存在很多復雜的問題，如用戶出行規律、早晚高峰期自行車數量、精確的預測機制、調度模型是否合理等，還有待進一步的研究。

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

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

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

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

[5]李婷婷.城市公共自行車租賃點選址規劃研究[D].北京:北京交通大學,2010.

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

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

[8]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.

[9]Contardo C,Morency C,Rousseau L M.Balancing a Dynamic Public Bike-Sharing System[R].Transportation Science,2012.

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

[11]史彩霞.基于公共自行車調度系統的運行分析和研究[D].杭州：浙江工業大學,2013.

[12]Marian R H,Petrina P,Hu B.Balancing Bicycle Sharing Systems:A Variable Neighborhood Search Approach[R]. EvoCOP 2013,LNCS 7832,Springer-Verlag Berlin Heidelberg,2013.121-132.

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

[14]Raviv T,Kolka O.Optimal inventory management of a bikesharing station[J].IIE Transactions,2013,1(45):1077-1093.

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

（責任編輯：朱 彬）

On the Dispatching Mode of Bicycle

CHENG Xian-jing，WANG Zheng-wei，RAN Jie，LONG Sheng-jie
(School of Maths and computational Science,Zunyi Normal College,Zunyi 563002,China)

As air pollution is increasingly serious,the concept of“Green Travelling”goes deep into the people’s mind;and the bicycle system arises at this very moment,and gains rapid development.However,there exists dispatching problem in the actual performance, viz.,how to tackle the customer’s problem of borrowing bicycle and returning it and how to minimize the operation cost of business, and these two factors restrict development of bicycle system in the long run.The operative experience from home and abroad as well as the relevant findings shows that proper dispatching system is the key to solving these problems.After analyzing the various optimum dispatching models and strategies,the author of this paper propounds an optimum dispatching model with multiple purposes.

bicycle system;dispatching problem;optimum dispatching model with multiple purposes

TP399

A

1009-3583（2016）-0094-07

2016-03-12

成先鏡，男，貴州遵義人，遵義師范學院數學與計算科學學院教師，碩士。研究方向：智能交通。