城市通勤車輛合乘網絡模型

程龍++何勝學++陳經緯

摘 要：針對城市早晚高峰交通擁堵問題，提出了一種通勤車輛的合乘網絡模型。新模型充分利用了通勤出行時間與起訖點位置相對比較集中的特點，并考慮了市民通勤出行的不同需求，因此不僅可以方便通勤者高峰時段的出行，而且有利于緩解城市道路交通壓力。模型的求解首先利用二分圖匹配實現司機乘客的匹配過程，確定可行的司乘匹配集合；然后分別計算各匹配的實際縮減運行距離和總的合乘參與人數；最后使用分層求解的方法確定參與人數限制條件下的最佳合乘匹配。通過算例驗證了模型的可行性和有效性，由數值分析可知：合理的通勤合乘有利于減少車輛總的行駛距離；合乘點的引入提高了司機乘客的匹配率和模型的優化效果。

關鍵詞：城市交通；合乘網絡；二分圖匹配；高峰時段通勤；合乘點

中圖分類號：U492.4 文獻標識碼：A

Abstract： To lighten the congestion during the rushing hours， this paper presented a commuting ride-sharing network model. Making use of the feature of the centralized commuting times and congregated origin-destination locations and taking into account the different demands of commuting， the new model not only facilitates the rush hour commuting， but also relieves the traffic pressure. To solve the model， the paper first used the bipartite matching to realize the process of drivers and passengers matching so as to determine the feasible matching set. Then this study computed the actual reduced travel distance of every feasible matching and the total number of the ride-sharing persons， respectively. At last this study used the hierarchy method to determine the optimal matching set limited to the total number of participated persons. The numerical example verified the feasibility and effectiveness of the new model. The numerical analysis shows that the rational ride-sharing matching can reduce the total travel distance and the introduction of the meeting points can increase the matching ratio of ride-sharing and strengthen the optimized effect of the new model.

Key words： urban traffic； ride-sharing system； bipartite matching； rush hour commute； meeting points

0 引 言

隨著我國城鎮化的快速發展，城市的機動車保有量迅速增加。同時多數城市的交通基礎設施建設或設計不能滿足日益增長的城市交通需求，造成了因為交通供需不平衡引起的城市交通問題，在城市早晚高峰時段表現尤其明顯。而在處理城市交通問題時機動車合乘可以有效減少城市路網中機動車需求。因為機動車合乘在滿足司機自身出行需求的同時也滿足了合乘者的出行需求，即在不增加路網機動車數量的同時解決了更多的交通出行需求。

對于機動車合乘國內外已經進行了大量的研究。Cordeau等提出DARP問題[1]（Dial-a-Ride Problem），其他學者針對該問題提出了不同的算法[2]。國內學者機動車合乘研究對象大多是出租車，對合乘調度、合乘路徑、合乘費率等方向都進行了研究[3-5]。不僅如此，國外發達國家已經對機動車合乘進行了實施和推廣。美國在一些快速路上推行高乘載（HOV-high occupancy vehicle）車道，即車輛中需要乘坐二人或多人才可在HOV車道上行駛。國外如Uber等公司也進入國內網約車市場。這些軟件的推廣一定程度上使居民出行更便利，但對整個城市路網中機動車數量的減少影響不大。因為這些軟件雇傭車主的出行行為大多以盈利為目的，因此相關車輛的行駛對路網來說就成為新增的交通量，并沒有起到減少城市路網機動車數量減緩城市交通壓力的作用。

城市通勤的時間段較集中，出行起訖點較集中且通勤時間段內居民出行數量多，因此易于實現合乘。針對城市上下班通勤車輛合乘問題，本文主要從如下幾個方面進行了分析研究：（1）基于城市通勤車輛合乘的可行性，建立對應的合乘優化模型；（2）通過二分圖匹配實現對合乘過程的描述；（3）通過改變合乘點選取范圍，分析合乘點數量對合乘模型優化結果的影響。

2 算 例

算例路網如圖1所示。設定路網中共有22個節點。其中1～16節點為普通節點，17～22節點為合乘點。實線上數字表示兩點間的距離（單位km）。設定路網節點之間可以相互直達，圖中沒有顯示出所有節點間路線及其距離。路網中共有15位通勤司機，24位合乘乘客。設定機動車行駛速度40km/h，乘客步行速度為5km/h。機動車最大載客量統一設定為4人。司機乘客的部分出行信息分別見表1表2。endprint

司機能接受的最大行程時間算例中直接設置為司機通勤最晚到達時間與最早出發時間的差值。算例的匹配和優化部分利用軟件Matlab編寫程序進行運算。運算中在原有數據條件下分別設置了有合乘點和沒有合乘點兩種情況進行對比。結果如表3所示。

從表3中看出算例中無論有無合乘點，每一位司機以及乘客都可以參與到合乘中。加入合乘點后因為乘客的上車點和下車點增加，司乘匹配數顯著增加，由138種增加到461種可能。優化后結果顯示因為合乘點的加入，模型中參與人數由30位增加為37位，增加23.3%，其中有更多的乘客可以加入合乘模型中。路網中減少機動車行駛距離值由311km增加到474.5km，增加52.6%。

下面對路網中合乘點的選取范圍進行修改，分析合乘點對合乘模型的影響。原例中節點2到節點17、節點8到節點19、節點10到節點20、節點15到節點22距離都超過1km，超出乘客的最大步行距離（1km），意味著從節點2、8、10、15出發的乘客不會選擇步行到合乘點17、19、20、22。現將上4對節點間距離分別改為0.9、0.7、0.7、0.9，也就是為在節點2、8、10、15出發的乘客增加有效合乘點。對修改過的算例模型進行運算得出的結果如表4所示。

從表4中可以看出合乘點的選取范圍擴大后，全部的司機和乘客都能參與到合乘中；路網中機動車行駛距離減少值更大，模型對緩解城市通勤高峰期的交通擁堵作用更明顯。通過對比可以看出模型中參與者人數隨著算例中有效合乘點數增加而增加，而路網機動車行駛距離隨著有效合乘點數增加而減小。

3 結束語

針對城市交通中的通勤問題，本文提出了一種高峰時段通勤車輛的合乘模型，并給出了具體求解算法。通勤時段居民出行的集中性有助于實現網絡合乘行為的整體優化。通過數值分析可知在城市通勤時段進行通勤車輛合乘可以有效地減少路網機動車需求數量，滿足更多人的出行需求，從而緩解城市道路的交通壓力。合乘點的加入使得模型中司乘匹配成功數量顯著增加；通勤合乘參與人數和路網機動車行駛距離減少值也會隨著更多合乘點的加入而不同幅度增加；有效合乘點的數量是取得合乘優化效果的關鍵。

參考文獻：

[1] Cordeau J F， Laporte G. The dial-a-ride problem： models and algorithms[J]. Annals of Operations Research， 2007，153（1）：29

-46.

[2] Parragh S N， Doerner K F， Hartl R F. Variable neighborhood search for the dial-a-ride problem[J]. Computers & Operations Research， 2010，37（6）：1129-1138.

[3] 覃運梅，石琴. 出租車合乘模式的探討[J]. 合肥工業大學學報（自然科學版），2006，29（1）：77-79.

[4] 吳芳，李志成，徐琛. 出租車合乘制調度優化模型研究[J]. 蘭州交通大學學報，2009，28（1）：104-107.

[5] 祝進城，帥斌，孫朝苑，等. 固定費率下城市出租車擁擠收費模型與算法[J]. 計算機應用研究，2013，30（8）：2288-2291.endprint