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

（遵義師范學(xué)院數(shù)學(xué)與計算科學(xué)學(xué)院，貴州遵義563002）

公共自行車調(diào)度模型研究

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

（遵義師范學(xué)院數(shù)學(xué)與計算科學(xué)學(xué)院，貴州遵義563002）

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

公共自行車系統(tǒng)；調(diào)度問題；多目標調(diào)度優(yōu)化模型

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

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

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

1 相關(guān)工作

目前，國內(nèi)外主要圍繞公共自行車調(diào)度系統(tǒng)調(diào)

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

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

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

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

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

2 調(diào)度模型研究

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

2.1 圍繞用戶滿意度的公共自行車調(diào)度模型

董紅召等[4]將模糊時間窗下的顧客滿意度轉(zhuǎn)化為公共自行車系統(tǒng)中用戶的滿意度，建立了公共慢性系統(tǒng)的動態(tài)調(diào)度模型，目標函數(shù)如下：

其中，

約束條件如下：

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

2.2 圍繞調(diào)度成本和調(diào)度時間的公共自行車調(diào)度模型

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

模型參數(shù)如下：

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

2.3 復(fù)合模型

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

模型參數(shù)如下：

調(diào)度平衡后的自行車數(shù)：

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

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

3 多目標調(diào)度優(yōu)化模型

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

模型系數(shù)如下：

兩階段調(diào)度策略下調(diào)度模型的目標函數(shù)為：

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

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

（2）調(diào)度車輛的調(diào)度時間。

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

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

3.1 租賃點懲罰值的計算

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

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

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

相關(guān)參數(shù)如下：

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

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

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

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

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

3.2 調(diào)度時間

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

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

（2）調(diào)度車輛在所經(jīng)路段等紅綠燈的時間。

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

3.3 時間滿意度

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

圖2 顧客i的滿意度

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

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

圖3 模糊時間窗

隨著調(diào)度車輛達到租賃點時間的不同，相應(yīng)的時間滿意度也會發(fā)生變化。時間滿意度的定義如下：

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

4 案例分析

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

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

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

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

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

5 總結(jié)

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

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

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

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

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

[5]李婷婷.城市公共自行車租賃點選址規(guī)劃研究[D].北京:北京交通大學(xué),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]賀竹磬,孫林巖.動態(tài)交通下車輛路徑選擇模型及算法[J].交通運輸工程學(xué)院學(xué)報,2007,7(1):112-115.

[11]史彩霞.基于公共自行車調(diào)度系統(tǒng)的運行分析和研究[D].杭州：浙江工業(yè)大學(xué),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].北京:科學(xué)出版社,2005.

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

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

（責(zé)任編輯：朱 彬）

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

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