基于排隊論的公共自行車系統(tǒng)自平衡問題研究

萬圓圓

（上海交通大學 安泰經(jīng)濟與管理學院，上海 200030）

隨著人們生活質(zhì)量和購買力水平的提高，城市家用轎車的持有量呈現(xiàn)放量式增長的態(tài)勢，導致城市公共空間變得擁擠，交通擁堵問題日益嚴峻。此外，人們對綠色環(huán)保、節(jié)能減排等問題日漸重視，綠色出行的概念也越來越受到人們的關注。公共自行車系統(tǒng)的出現(xiàn)，一方面能夠緩解城市交通的壓力，同時解決公共交通“最后一公里”的問題，另一方面能滿足人們對于低碳、環(huán)保、健康的交通方式的需求。因此，公共自行車系統(tǒng)的建設得到了世界各國和各地區(qū)政府的重視，成為公共交通的重要發(fā)展方向。

我國公共自行車系統(tǒng)起源于2008年5月開始運營的杭州公共自行車系統(tǒng)，此后公共自行車系統(tǒng)在全國各地迅速發(fā)展。據(jù)中國交通與發(fā)展政策研究所統(tǒng)計，截至2017年底，我國共有170多個城市和地區(qū)的政府發(fā)起建設了公共自行車系統(tǒng)，運營自行車數(shù)量近100萬輛。隨著共享經(jīng)濟理念的興起，以互聯(lián)網(wǎng)作為媒介，借助智能手機支付技術的大發(fā)展，誕生于校園的共享單車也快速進入中國各大城市。據(jù)統(tǒng)計，截至2017年4月，中國的共享單車運營企業(yè)數(shù)量已達45家，共投放自行車約720萬輛。

可見，目前國內(nèi)的公共自行車系統(tǒng)主要有兩種模式，其一為政府主導的有樁公共自行車系統(tǒng)，其二為社會資本支持的無樁共享單車模式。兩種模式在運營過程中各自存在著一些問題，也有一些共同的問題。比如，公共自行車系統(tǒng)存在操作復雜、借還車困難等問題，而共享單車則存在無序停放、對用戶行為監(jiān)管困難等問題。然而不管是哪種運營模式，由于用戶借還車行為的不規(guī)律性和不確定性，都存在車輛分布不均的問題，需要花費大量的人力和成本去調(diào)度不同區(qū)域的自行車數(shù)量。本文所研究的問題就是通過激勵用戶從車輛較多的區(qū)域借車或到車輛較少的區(qū)域還車，從而影響用戶行為，改變部分用戶借車或還車的租賃點，從而實現(xiàn)公共自行車系統(tǒng)的自我平衡，減少需要調(diào)度的自行車數(shù)量，提高運營效率，降低管理成本。

目前，國內(nèi)外學者對于公共自行車系統(tǒng)的研究主要分以下幾個方向：一是對于借還車需求預測的研究，二是對于公共自行車系統(tǒng)車輛調(diào)度問題的研究，三是公共自行車租賃點選址的研究。在公共自行車的車輛調(diào)度問題上，國內(nèi)外學者主要做過以下研究：一是基于需求預測的調(diào)度問題研究；二是調(diào)度車輛路徑規(guī)劃問題研究；三是多階段、動態(tài)公共自行車系統(tǒng)調(diào)度問題的研究等。本文所研究的公共自行車系統(tǒng)自平衡問題目前較少有學者研究，僅有的少量研究也是基于同質(zhì)化的站點，而本文則考慮了不同站點的用戶借還車到達率不同，通過建模和仿真給出了系統(tǒng)自平衡方案。

1 建立模型

1．1 基礎模型

本文研究的是一個擁有n個自行車租賃點的有樁公共自行車系統(tǒng)，該系統(tǒng)共運營m輛自行車。對于單輛自行車而言，可能存在兩種狀態(tài)：被鎖在某個租賃點或正在被用戶使用。每一個租賃點擁有有限個車樁可供用戶借車或還車，因此對于單個租賃點而言可能存在三種狀態(tài)：無可用自行車、無空閑車樁、既有可用自行車又有空閑車樁。若一個自行車租賃點無可用自行車，則用戶無法在該租賃點借車并離開系統(tǒng)；若一個自行車租賃點無空閑車樁，則用戶無法在該租賃點還車并離開該租賃點繼續(xù)騎行。

假設各租賃點的借車用戶和還車用戶分別服從泊松分布，不同租賃點之間相互獨立。相關的參數(shù)設置如下：

n—自行車租賃點個數(shù)；

m—所有自行車數(shù)量；

λi—第i個租賃點還車用戶的到達率；

μi—第i個租賃點借車用戶的到達率；

ci—第i個租賃點擁有的車樁數(shù)量；

xi（t）—第i個租賃點在t時刻擁有的自行車數(shù)量。

不妨將所有正在被用戶使用的自行車看作一個租賃點，并記為租賃點0。記租賃點0的還車用戶到達率為λ0，借車用戶到達率為μ0，擁有車樁數(shù)量為c0，在時刻t擁有自行車數(shù)量為x0（t）。當有用戶從其他租賃點借車時，租賃點0的自行車數(shù)量增加1輛；當有用戶從其他租賃點還車時，租賃點0的自行車數(shù)量減少1輛?？傻糜浤硶r刻該公共自行車系統(tǒng)的狀態(tài)為S＝｛x0，x1，x2，…，xn｝，其中本文將該公共自行車系統(tǒng)作為一個排隊論過程進行研究，在自然狀態(tài)下S的生滅過程如下圖所示。

不妨設狀態(tài)S的穩(wěn)態(tài)概率為Px0，x1，x2，…，xn，則由上圖易得S的狀態(tài)轉移方程如下：

1．2 推薦模型

基于以上設定，本文通過推薦用戶更改還車租賃點的方式，來影響用戶的還車到達率，從而減少需要調(diào)度的自行車的數(shù)量。當一個自行車租賃點無可用自行車時，我們需要從其他租賃點調(diào)入自行車；當一個租賃點無空閑車樁時，則需要將部分車輛調(diào)配到其他租賃點。因此，若要減少需要調(diào)度的自行車數(shù)量，一個有效的方法是降低各租賃點無可用自行車及無空閑車樁的概率。令ex0，x1，x2，…，xn表示狀態(tài)S下無可用自行車的租賃點的數(shù)量，fx0，x1，x2，…，xn表示無空閑車樁的租賃點的數(shù)量，則在狀態(tài)S下需要調(diào)度的租賃點的比例為（ex0，x1，x2，…，xn＋fx0，x1，x2，…，xn）／n，可得 該 公共自行車系統(tǒng)需要進行調(diào)度的概率Q為

為了改變用戶的還車行為，我們以概率h′ij推薦到達租賃點i還車的用戶將自行車還到租賃點j。假設用戶以概率αij接受我們給出的推薦方案，則可得到達租賃點i還車的用戶實際上以hij＝h′ij*αij的概率將自行車還到租賃點j。因此，我們不妨設以概率推薦到達租賃點i還車的用戶將自行車還到租賃點j，用戶以概率1接受我們給出的推薦方案，則租賃點i的實際還車到達率λ′i為

其中，hii表示不對到達租賃點i還車的用戶推薦的概率，∑nj＝1hij＝1。

綜上，為了降低需要進行調(diào)度的概率，可得如下規(guī)劃問題：

易知，上述規(guī)劃問題的復雜性會隨著n的增大而增加，當n較大時，上述問題難以直接求解。因此，本文考慮各租賃點之間的獨立性對上述問題進行化簡。當用戶到達租賃點借車時，若租賃點自行車數(shù)量不為0，則用戶借車后離開該租賃點；若租賃點無可用自行車，則假設用戶直接離開該系統(tǒng)，所以用戶的借車行為不會對其他租賃點產(chǎn)生影響。同理，當用戶到達租賃點還車時，若租賃點有空閑的車樁，則用戶還車后離開該租賃點；若租賃點無空閑的車樁，則假設用戶離開該租賃點繼續(xù)騎行，所以用戶的還車行為也不會對其他租賃點產(chǎn)生影響。因此，我們不妨假設所有租賃點之間相互獨立。設租賃點i的穩(wěn)態(tài)概率為Pxi，0≤xi≤ci，則

考慮單個租賃點i，其生滅過程如下：

其狀態(tài)轉移方程為

2 仿真實驗

2．1 實驗設定

本文仿真實驗部分的數(shù)據(jù)來自美國華盛頓哥倫比亞特區(qū)（Washington D．C．，以下簡稱華盛頓）的公共自行車租賃系統(tǒng)——Capital Bikeshare。它是美國最大的公共自行車租賃系統(tǒng)，覆蓋了哥倫比亞特區(qū)，以及周邊的阿林頓、費爾法克斯等若干城市，24小時為居民提供自行車租賃服務。自2008年成立以來，該公共自行車系統(tǒng)已經(jīng)運營了9年多的時間，租賃點的設置已經(jīng)十分完善，用戶來源也較為穩(wěn)定。

該公共自行車系統(tǒng)目前擁有440個租賃點、3700多輛自行車以及7555個車樁。本文所采用的是2016年9月1日—2016年9月30日的344246條借還車數(shù)據(jù)，數(shù)據(jù)記錄了借車時間、還車時間、借還車間隔時間、借車站點、還車站點、自行車編號以及是否注冊會員等信息。本文以Capital Bikeshare的用戶借還車數(shù)據(jù)作為初始借還車需求，并以此為基礎計算不同策略下的調(diào)度數(shù)量，研究用戶借還車行為改變后運營效率的變化。考慮到實際問題中用戶借車的地點較難改變，因此本文僅考慮通過推薦新的還車點改變用戶的還車行為。

由上文可知，為了使得需要進行調(diào)度的概率盡可能小，我們需要以概率hij推薦到達租賃點i還車的用戶將自行車還到租賃點j，從而使得租賃點i的實際還車到達率λ′i＝μi，即使得單個租賃點在足夠長的時間內(nèi)，借車的用戶數(shù)與還車的用戶數(shù)相等。假設在足夠長的觀察期內(nèi)，有Oi個用戶到達租賃點i借車，Ii個用戶到達還車，則我們可以通過求解…，n來計算推薦概率hij。

然而在實際問題中，由于距離等因素的限制，通常無法實現(xiàn)這一理想狀態(tài)。公共自行車屬于短途交通工具，用戶接受推薦的概率會隨著租賃點i、j之間距離的增加而降低，且當距離超過一定范圍后，用戶幾乎不會接受推薦方案。因此，我們只能在一定的距離范圍內(nèi)進行推薦，使得I′i盡可能地接近Qi。結合實際情況，為及時滿足用戶需求，本文采取推薦與調(diào)度相結合的方案來平衡公共自行車系統(tǒng)。

在初始狀態(tài)下，我們將全部3700輛自行車，根據(jù)車樁的數(shù)量按比例分配到各個租賃點，租賃點自行車數(shù)量記為S0＝｛s1，s2，…，sn｝，si表示租賃點i的初始自行車數(shù)量。記在時刻t時，租賃點i的自行車數(shù)量為xi（t），則在時刻t＋1時，若有Qi（t）個用戶到達租賃點i借車，Ii（t）個用戶到達還車，則xi（t＋1）＝xi（t）－Oi（t）＋Ii（t）。若xi（t＋1）＜0，則租賃點現(xiàn)有自行車無法滿足用戶的借車需求，需從其他租賃點調(diào)度－xi（t＋1）輛自行車到租賃點i；若xi（t＋1）＞ci，則租賃點現(xiàn)有空閑車樁無法滿足用戶的還車需求，需將xi（t＋1）－ci輛自行車調(diào)度至其他租賃點。在調(diào)度的過程中，由于調(diào)度成本的主要影響因素是租賃點間的距離，因此當某個租賃點無可用自行車時，需要在滿足其他租賃點需求的前提下，從距離相對較近的若干個租賃點調(diào)度一定數(shù)量的自行車，以滿足該站點用戶的需求。同理，當某個租賃點無空閑車樁時，需要將部分車輛調(diào)配到距離相對較近的若干個租賃點。

在時刻t，若xi（t＋1）＜0，假設從租賃點j調(diào)度yj輛自行車到租賃點i，令dij表示租賃點i與租賃點j之間的距離，則求解如下線性規(guī)劃問題可得各租賃點的調(diào)度量yj：

易看出當上述線性規(guī)劃取最優(yōu)解時，需在有多余車輛的租賃點中選擇距離最近的租賃點調(diào)度，若仍不能滿足租賃點i的需求，則繼續(xù)從第二近的租賃點調(diào)度，如此重復直至調(diào)度量能夠滿足租賃點i的需求為止。因此，在本文的仿真實驗中，當租賃點i無可用自行車時，采用的具體調(diào)度流程如下：

Step1：將其余租賃點按與租賃點i的距離從小到大進行排序，記為i1，i2，…，in－1，令k＝1，R＝Oi（t）－Ii（t）；

Step2：令H＝x ik（t）－Oik（t）＋Iik（t），若H≤0，跳到Step3；若0≤H＜R，則從租賃點ik向i調(diào)度H輛自行車，R＝R－H，跳到Step3；若H≥R，則從租賃點ik向i調(diào)度R輛自行車，并停止循環(huán)；

Step3：k＝k＋1，重復Step2。

同理，當租賃點i無空閑車樁時，用類似方案將自行車調(diào)度到附近租賃點，細節(jié)不再贅述。每次調(diào)度時，記錄調(diào)度自行車的數(shù)量，并在最后進行求和即可得總的調(diào)度量。

2．2 實驗方案

本文將Capital Bikeshare系統(tǒng)在2016年9月1日至2016年9月30日共30天的借還車數(shù)據(jù)作為初始需求輸入，當用戶到達租賃點借車而租賃點沒有可用的自行車，或用戶到達租賃點還車而租賃點沒有空閑的車樁時，則按上文所述的方案進行調(diào)度。為便于計算，不考慮調(diào)度時間，即假設調(diào)度所需的時間為0。為衡量推薦策略對系統(tǒng)運營效率的提高，本文考慮無推薦的初始方案、無距離限制的理想推薦方案以及考慮距離因素的合理推薦方案三種情況，并記錄三種情況下需要調(diào)度的自行車數(shù)量，以此研究推薦方案的可行性。三種方案的具體實驗流程如下：

（1）初始方案：在初始方案中，我們考慮自然狀態(tài)下不做任何推薦的情況。在仿真實驗中，我們將時間劃分為長度為15分鐘的時間窗，并計算每個時間窗內(nèi)各租賃點總的借車需求Oi（t）和總的還車需求Ii（t），則租賃點i的實際需求，即自行車數(shù)量的變化為Di（t）＝Ii（t）－Oi（t），Di（t）＞0則實際需求為還車需求，Di（t）＜0則實際需求為借車需求。記時間窗t結束時租賃點i的自行車數(shù)量為x i（t），則x i（t＋1）＝x i（t）－Oi（t）＋Ii（t）。若x i（t＋1）＜0，則需從其他租賃點調(diào)度－x i（t＋1）輛自行車到租賃點i；若x i（t＋1）＞ci，則需將x i（t＋1）－ci輛自行車調(diào)度至其他租賃點。計算總調(diào)度數(shù)量A。

（2）理想方案：在理想方案中，我們不考慮距離等因素的限制，可以將用戶推薦至系統(tǒng)中任意租賃點還車，假設用戶100%接受推薦方案。由上文可知，我們可以通過求解I′i＝Ii＋∑ns＝1hsi*Is－∑nt＝1hit*Ii＝Oi，其中i＝1，2，…，n來計算推薦概率h ij，但由于該方程組的等式數(shù)量遠小于未知變量的數(shù)量，因此有無窮多解，我們將增加一些約束條件以獲得最優(yōu)解。令Qij＝Ii*hij表示從租賃點i推薦至租賃點j的用戶數(shù)，則租賃點i的凈流入用戶數(shù)為NI i＝（Ii－Oi）＋＝∑nj＝1Qij，凈流出用戶數(shù)為NOj＝（Oj－I j）＋＝∑ni＝1Qij（其中，X＋＝記租賃點i到租賃點j的距離為d ij，令d ij為一個足夠大的數(shù)M，使得hii＝0，則求解如下線性規(guī)劃即可得推薦概率hij：

在時間窗t內(nèi)，對于到達租賃點i還車的用戶，按概率將用戶推薦至租賃點j。重新計算各租賃點實際的用戶借還車需求D′i（t），用D′i（t）代替Di（t），按（1）中方案進行仿真實驗。記錄總調(diào)度數(shù)量B。

（3）推薦方案：在推薦方案中，考慮距離等現(xiàn)實因素的限制，推薦的站點距離越遠，用戶接受推薦的概率越低，當距離超過一定范圍后，用戶不會再接受推薦。不妨設當距離超過800米后，用戶不會再接受推薦方案，令其中Y是一個足夠大的數(shù)，并令d ii為一個足夠大的數(shù)Z，且Z小于所有d ij*Y，使得求解（2）中線性規(guī)劃時，對于距離大于800米的租賃點i、j的推薦概率h ij＝0，當沒有滿足條件的站點可以推薦時，則不進行推薦，即hij≠0。用d′ij代替d ij，按（2）中策略進行調(diào)度，記錄總調(diào)度數(shù)量C。

2．3 實驗結果

按上文中的三個方案分別進行計算機仿真實驗后所得結果如表1所示。

表1 三個實驗方案的調(diào)度量對比

由表1可以看出，當采用推薦方案時，如不考慮距離因素，在理想狀態(tài)下可以使得調(diào)度量減少37．77%，即使考慮距離的影響，僅將用戶推薦至800米以內(nèi)的租賃點，也可以使得調(diào)度的自行車數(shù)量減少8．94%。這一結果雖然相較理想狀態(tài)下的情況低很多，但這主要是由于公共自行車是短途交通工具，距離較近的租賃點其用戶行為也較為相近。當用戶數(shù)量足夠多時，減少8．94%的調(diào)度量也可以減少大量調(diào)度成本。

表2記錄了總調(diào)度量最多的30個租賃點在不同方案下的總調(diào)度數(shù)量，可以看出在理想方案下，調(diào)度量較大的租賃點的調(diào)度數(shù)量下降了50%～70%，可見通過推薦用戶到其他租賃點還車的方式，有效降低系統(tǒng)的調(diào)度數(shù)量。而在推薦方案下，由于距離的限制，雖然不是所有租賃點的調(diào)度數(shù)量都大幅降低，但是也有約四分之一的租賃點的調(diào)度量下降較多，下降了約20%～30%，而其他租賃點的調(diào)度量也有一定的改善。由此可見，推薦用戶到其他租賃點還車，可以有效減少用戶量較大的租賃點的調(diào)度量，提高運營效率。

表2 部分租賃點在不同方案下的總調(diào)度量

3 總結及展望

綜上，本文采用排隊論對公共自行車系統(tǒng)的調(diào)度問題進行了建模研究，如果以概率將到達租賃點i還車的用戶推薦至租賃點j，則當時各租賃點無可用自行車或無空閑車樁的概率最小?；谶@一結論我們進行了仿真實驗，對無推薦的初始方案、無距離限制的理想推薦方案以及考慮距離因素的合理推薦方案三種情況分別進行了仿真實驗，并對比三種方案調(diào)度的自行車數(shù)量，最終證明通過推薦用戶到鄰近的站點還車可以有效減少公共自行車系統(tǒng)的調(diào)度數(shù)量，降低調(diào)度成本。

本文主要研究的是各租賃點擁有有限個車樁的公共自行車系統(tǒng)，如果將無樁的共享單車模式看作一個租賃點無窮多、每個租賃點擁有無限個車樁的公共自行車系統(tǒng)，則本文的模型可以拓展至共享單車模式。因此，在后續(xù)的研究中，可以對本文的模型進行進一步的擴展。