基于生滅過程的公共自行車站點(diǎn)車輛調(diào)度方法研究

李牧添，朱從坤

(蘇州科技大學(xué) 土木工程學(xué)院，江蘇 蘇州 215011)

近年來，隨著公共自行車系統(tǒng)的快速發(fā)展，公共自行車站點(diǎn)經(jīng)常出現(xiàn)“無車可借、無樁可還”的現(xiàn)象。這嚴(yán)重影響了市民對(duì)公共自行車的使用體驗(yàn)，制約了公共自行車的進(jìn)一步發(fā)展，因此合理的車輛調(diào)度尤為迫切。

在公共自行車車輛調(diào)度方面，芮一鳴等[1]以庫存理論為基礎(chǔ)，分析車輛調(diào)度的啟動(dòng)閾值，并結(jié)合系統(tǒng)特性，建立了基于用戶滿意度的多目標(biāo)調(diào)度模型；黎文建[2]在兼顧用戶滿意度和運(yùn)營商調(diào)度成本的同時(shí)，以時(shí)間窗懲罰值最小為目標(biāo)，建立了帶模糊時(shí)間窗的動(dòng)態(tài)調(diào)度路徑優(yōu)化模型，并利用蟻群算法對(duì)模型進(jìn)行求解；焦云濤等[3]提出一種以離散差分算法為基礎(chǔ)的混合算法，用于生成公共自行車動(dòng)態(tài)調(diào)度的初始方案，并根據(jù)需求預(yù)測(cè)信息和實(shí)時(shí)需求信息對(duì)初始方案進(jìn)行動(dòng)態(tài)調(diào)整；劉新宇等[4]以用戶需求最大化和調(diào)度成本最小化為目標(biāo)，建立了公共自行車車輛調(diào)度路徑的優(yōu)化模型，并利用遺傳算法對(duì)模型進(jìn)行求解，驗(yàn)證了模型的有效性。綜上所述，目前車輛調(diào)度模型多以用戶滿意度最大化、調(diào)度成本最小化和調(diào)度路徑最優(yōu)化等為目標(biāo)，利用不同算法對(duì)模型求解，最終得到不同的調(diào)度方案。

本文利用生滅過程理論分析公共自行車站點(diǎn)的狀態(tài)概率分布特征，建立站點(diǎn)的狀態(tài)概率模型，并根據(jù)站點(diǎn)的調(diào)度需求提出最佳調(diào)度時(shí)機(jī)和調(diào)度車輛數(shù)，以滿足用戶的借、還車需求。

1 基于生滅過程的公共自行車站點(diǎn)的狀態(tài)概率模型

1.1 公共自行車站點(diǎn)排隊(duì)模型

在公共自行車使用過程中，用戶借、還車都要與站點(diǎn)上的停車樁進(jìn)行交互。在每個(gè)站點(diǎn)，單個(gè)停車樁位都會(huì)存在滿樁和空樁兩種狀態(tài)。為了將公共自行車站點(diǎn)的“借車”和“還車”兩種服務(wù)放在同一個(gè)模型進(jìn)行研究，將公共自行車站點(diǎn)看作是一個(gè)M/M/K/K的損失制排隊(duì)系統(tǒng)[5]，站點(diǎn)內(nèi)總停車樁位數(shù)看作排隊(duì)系統(tǒng)中的服務(wù)臺(tái)數(shù)K，站點(diǎn)的系統(tǒng)容量也為K，并假設(shè)借車用戶到達(dá)的時(shí)間間隔和站點(diǎn)的服務(wù)時(shí)間均服從負(fù)指數(shù)分布M。

1.2 基于生滅過程的站點(diǎn)狀態(tài)概率分布模型

單個(gè)公共自行車停車樁狀態(tài)變化如圖1所示。當(dāng)單個(gè)停車樁處于滿樁狀態(tài)(空閑狀態(tài))時(shí)，該停車樁可提供借車服務(wù)，但無法還車；當(dāng)單個(gè)停車樁處于空樁狀態(tài)(服務(wù)狀態(tài))時(shí)，該停車樁無法借車，但可以提供還車服務(wù)。結(jié)合生滅過程理論，圖1中將停車樁滿樁狀態(tài)轉(zhuǎn)變?yōu)榭諛稜顟B(tài)的過程看作是“生的過程”，把樁位從空樁狀態(tài)轉(zhuǎn)變?yōu)闈M樁狀態(tài)的過程看作是“滅的過程”。

圖1 單個(gè)公共自行車停車樁位狀態(tài)變化圖Fig.1 State change diagram of a single public bicycle parking spot

設(shè)某公共自行車站點(diǎn)的總樁數(shù)為K，空樁數(shù)為n(0≤n≤K)，則滿樁數(shù)(在樁的公共自行車數(shù)量)為K-n。對(duì)于任一時(shí)刻t，若站內(nèi)空樁處于狀態(tài)Sn(即站內(nèi)有n個(gè)空樁)，隨著時(shí)間的變化,Sn存在以下4種可能[6-7]：

①在時(shí)間(t,t+Δt)內(nèi)，有一位用戶到達(dá)站點(diǎn)借車，空樁由狀態(tài)Sn轉(zhuǎn)移到Sn+1(n≥0)的概率為λnΔt+o(Δt),其中λn為狀態(tài)Sn時(shí)的出生率。

②在時(shí)間(t,t+Δt)內(nèi)，有一位用戶到達(dá)站點(diǎn)還車，空樁由狀態(tài)Sn轉(zhuǎn)移到Sn-1(n≥1)的概率為μnΔt+o(Δt),其中μn為狀態(tài)Sn時(shí)的死亡率。

③在時(shí)間(t,t+Δt)內(nèi)，沒有用戶到達(dá)站點(diǎn)進(jìn)行借、還車，站點(diǎn)內(nèi)空樁狀態(tài)沒有發(fā)生轉(zhuǎn)移的概率為1-λnΔt-μnΔt+o(Δt)。

④在時(shí)間(t,t+Δt)內(nèi)，同時(shí)有兩個(gè)或兩個(gè)以上的用戶在站點(diǎn)進(jìn)行借、還車，空樁狀態(tài)發(fā)生兩次或兩次以上轉(zhuǎn)移的概率為o(Δt)。

假設(shè)在一定時(shí)段內(nèi)，用戶借車與還車的到達(dá)率保持不變，則站點(diǎn)的出生率表現(xiàn)為用戶的借車到達(dá)率，而站點(diǎn)的死亡率取決于用戶的還車到達(dá)率和站點(diǎn)內(nèi)的空樁數(shù)量。站點(diǎn)出生率λn和死亡率μn的計(jì)算公式如下：[8]

λn=λ,n=0,1,…,K

(1)

(2)

式中:λ為平均借車速率，輛/h；μ為平均還車速率，輛/h。

站點(diǎn)的服務(wù)強(qiáng)度ρn為借車用戶到達(dá)速率與服務(wù)臺(tái)數(shù)量和平均服務(wù)速率乘積的比值，即

(3)

當(dāng)ρn<1時(shí)，系統(tǒng)是穩(wěn)定的。

對(duì)每個(gè)狀態(tài)而言，當(dāng)出生率期望值等于死亡率期望值時(shí)，系統(tǒng)達(dá)到狀態(tài)平衡[9],即對(duì)于任意狀態(tài)Sn，出生率期望值為E=μnPn+λnPn(Pn為公共自行車站點(diǎn)處于n個(gè)空樁狀態(tài)的概率),死亡率期望值為E′=λn-1Pn-1+μn+1Pn+1。當(dāng)E=E′時(shí)，系統(tǒng)達(dá)到狀態(tài)平衡，有：

μnPn+λnPn=

λn-1Pn-1+μn+1Pn+1(1≤n

(4)

對(duì)于狀態(tài)S0，有μ1P1=λ0P0

(5)

對(duì)于狀態(tài)SK，有λK-1PK-1=μKPK

(6)

式(4)～式(6)稱為生滅過程的哥爾莫可爾夫方程[10]，聯(lián)解可得：

(7)

站點(diǎn)內(nèi)空樁的期望值E空、滿樁的期望值E滿計(jì)算公式如下：

(8)

E滿=K-E空

(9)

2 典型站點(diǎn)狀態(tài)分析

以蘇州市軌交濱河路公共自行車站點(diǎn)早、晚高峰期為例進(jìn)行狀態(tài)概率分析，車輛實(shí)時(shí)借、還數(shù)據(jù)由永安行蘇州分公司提供。該站點(diǎn)總樁位數(shù)K=30，分析時(shí)段為2019年6月12日的早高峰(7：00—9：00)與晚高峰(17：00—19：00)。這兩個(gè)時(shí)段內(nèi)車輛借、還速率如表1所示。

2.1 站點(diǎn)車輛借、還間隔時(shí)間分布檢驗(yàn)

運(yùn)用SPSS Statistics軟件對(duì)以“秒”為單位進(jìn)行統(tǒng)計(jì)的軌交濱河路公共自行車站點(diǎn)早、晚高峰期的借車間隔時(shí)間和還車間隔時(shí)間進(jìn)行分布檢驗(yàn)，結(jié)果如圖2～圖5所示。

圖2～圖5的檢驗(yàn)結(jié)果顯示，該站點(diǎn)借、還車間隔時(shí)間分布的漸進(jìn)顯著性均大于臨界值P=0.05，表明該站點(diǎn)在早、晚高峰時(shí)段借還車間隔時(shí)

表1 軌交濱河路公共自行車站點(diǎn)車輛借還速率Table 1 Vehicle loan and return rate at the public bicycle station on Binhe Road of rail transit

間均服從負(fù)指數(shù)分布。

2.2 站點(diǎn)狀態(tài)特征分析

將表1數(shù)據(jù)代入式(7)～式(9)，可得該站點(diǎn)在早、晚高峰兩個(gè)時(shí)段的狀態(tài)概率分布Pn、服務(wù)強(qiáng)度ρn和空(滿)樁期望，如表2所示。

利用實(shí)際借、還車數(shù)據(jù)，還可繪出該站點(diǎn)早、晚高峰時(shí)段的空樁數(shù)量變化曲線，如圖6所示。

圖2 早高峰借車間隔時(shí)間分布及檢驗(yàn)結(jié)果Fig.2 The distribution of the car-borrowing interval in the morning rush hour and test results

圖3 早高峰還車間隔時(shí)間分布及檢驗(yàn)結(jié)果Fig.3 The distribution of the time interval between returning vehicles in the morning rush hour and test results

圖4 晚高峰借車間隔時(shí)間分布及檢驗(yàn)結(jié)果Fig.4 The distribution of the car-borrowing interval in the evening rush hour and test results

圖5 晚高峰還車間隔時(shí)間分布及檢驗(yàn)結(jié)果Fig.5 The distribution of the time interval between returning vehicles in the evening rush hour and test results

表2 蘇州市軌交濱河路公共自行車站點(diǎn)部分狀態(tài)的統(tǒng)計(jì)數(shù)據(jù)Table 2 Statistical data of part of the state of the public bicycle station on Binhe Road of Suzhou Rail Transit

由表2可知，早高峰時(shí)段該站點(diǎn)處于S0狀態(tài)(系統(tǒng)內(nèi)有0個(gè)空樁)的概率要遠(yuǎn)大于S30狀態(tài)(系統(tǒng)內(nèi)有30個(gè)空樁)的概率，說明該站點(diǎn)在早高峰時(shí)段大概率會(huì)出現(xiàn)“無樁可還”現(xiàn)象；晚高峰時(shí)段該站點(diǎn)處于S30狀態(tài)的概率要大于S0狀態(tài)的概率，說明該站點(diǎn)在晚高峰時(shí)段大概率會(huì)出現(xiàn)“無車可借”現(xiàn)象。這一結(jié)論與圖6所表現(xiàn)出的空樁數(shù)量變化規(guī)律一致，表明該站點(diǎn)在早高峰時(shí)段有車輛調(diào)出需求，在晚高峰時(shí)段有車輛調(diào)入需求。

3 站點(diǎn)車輛調(diào)度方法

3.1 站點(diǎn)車輛調(diào)度閾值

針對(duì)蘇州市軌交濱河路公共自行車站點(diǎn)在早高峰易出現(xiàn)“無樁可還”、晚高峰易出現(xiàn)“無車可借”現(xiàn)象，以早、晚高峰期間的空樁期望E空為參考，確定車輛調(diào)度的啟動(dòng)閾值。即早高峰期間，當(dāng)站點(diǎn)內(nèi)僅存1.73個(gè)空樁時(shí)，應(yīng)該對(duì)該站點(diǎn)進(jìn)行車輛調(diào)出；晚高峰期間，在站點(diǎn)有21.17個(gè)空樁時(shí)，應(yīng)該對(duì)站點(diǎn)進(jìn)行車輛調(diào)入?？紤]到車輛調(diào)度所花費(fèi)的時(shí)間損耗，將車輛調(diào)度啟動(dòng)閾值適當(dāng)提高，即在站點(diǎn)只有2～4個(gè)空樁時(shí)對(duì)站點(diǎn)實(shí)施車輛的調(diào)出，在站點(diǎn)有21～23個(gè)空樁時(shí)對(duì)站點(diǎn)實(shí)施車輛的調(diào)入。

a 早高峰

b 晚高峰圖6 蘇州市軌交濱河路公共自行車站點(diǎn)早、晚高峰空樁數(shù)變化曲線圖Fig.6 The change curve of the number of empty piles in the morning and evening peak hours at the public bicycle station of Binhe Road, Suzhou Rail Transit

3.2 站點(diǎn)車輛調(diào)度數(shù)量

在早高峰期間站點(diǎn)調(diào)出車輛時(shí)，還需同時(shí)考慮避免出現(xiàn)“無車可借”的現(xiàn)象。由公式(7)可知，在站點(diǎn)的平均借車速率與平均還車速率不變的情況下，“無車可借”的概率PK隨K值而變化。早高峰時(shí)段站點(diǎn)在不同規(guī)模下處于SK狀態(tài)的概率PK的部分結(jié)果如表3所示。

表3 不同規(guī)模下站點(diǎn)在早高峰處于SK狀態(tài)的概率

若能接受“無車可借”現(xiàn)象的概率為1%左右，由表3可知，K=7時(shí)，P7=0.010 7(即“無車可借”的概率為1.07%)符合要求。即車輛調(diào)度人員在早高峰期間調(diào)度車輛時(shí)，應(yīng)保證站點(diǎn)內(nèi)至少有7輛公共自行車。

同理可確定晚高峰的車輛調(diào)度數(shù)量。利用公式(7)計(jì)算晚高峰時(shí)段站點(diǎn)在不同規(guī)模下處于S0狀態(tài)概率P0，部分結(jié)果如表4所示。

表4 不同規(guī)模下站點(diǎn)在晚高峰處于S0狀態(tài)的概率

若能接受“無樁可還”現(xiàn)象的概率為1%左右，由表4可知，當(dāng)K=11時(shí)，P0=0.010 8和K=12時(shí)，P0=0.009 2均符合要求，只是K=12時(shí)，出現(xiàn)滿樁的概率要低一些。即車輛調(diào)度人員在晚高峰期間調(diào)度車輛時(shí)，應(yīng)保證站點(diǎn)內(nèi)至少有11個(gè)或12個(gè)空樁。

4 結(jié)語

根據(jù)生滅過程和排隊(duì)論的相關(guān)理論研究公共自行車站點(diǎn)車輛調(diào)度方法，建立公共自行車站點(diǎn)狀態(tài)概率分布模型，推導(dǎo)出站點(diǎn)的狀態(tài)概率分布、服務(wù)強(qiáng)度、空樁期望等計(jì)算公式；在站點(diǎn)服務(wù)強(qiáng)度 的前提下，利用站點(diǎn)狀態(tài)概率分布確定站點(diǎn)的調(diào)度需求，以站點(diǎn)空樁期望作為參考制定車輛調(diào)度的啟動(dòng)閾值，討論站點(diǎn)合理的車輛配置數(shù)量，為公共自行車站點(diǎn)車輛調(diào)度方案的制定提供定量依據(jù)。