程龍++何勝學(xué)++陳經(jīng)緯

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

關(guān)鍵詞：城市交通；合乘網(wǎng)絡(luò)；二分圖匹配；高峰時(shí)段通勤；合乘點(diǎn)

中圖分類號(hào)：U492.4 文獻(xiàn)標(biāo)識(shí)碼：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 引 言

隨著我國(guó)城鎮(zhèn)化的快速發(fā)展，城市的機(jī)動(dòng)車保有量迅速增加。同時(shí)多數(shù)城市的交通基礎(chǔ)設(shè)施建設(shè)或設(shè)計(jì)不能滿足日益增長(zhǎng)的城市交通需求，造成了因?yàn)榻煌ü┬璨黄胶庖鸬某鞘薪煌▎?wèn)題，在城市早晚高峰時(shí)段表現(xiàn)尤其明顯。而在處理城市交通問(wèn)題時(shí)機(jī)動(dòng)車合乘可以有效減少城市路網(wǎng)中機(jī)動(dòng)車需求。因?yàn)闄C(jī)動(dòng)車合乘在滿足司機(jī)自身出行需求的同時(shí)也滿足了合乘者的出行需求，即在不增加路網(wǎng)機(jī)動(dòng)車數(shù)量的同時(shí)解決了更多的交通出行需求。

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

城市通勤的時(shí)間段較集中，出行起訖點(diǎn)較集中且通勤時(shí)間段內(nèi)居民出行數(shù)量多，因此易于實(shí)現(xiàn)合乘。針對(duì)城市上下班通勤車輛合乘問(wèn)題，本文主要從如下幾個(gè)方面進(jìn)行了分析研究：（1）基于城市通勤車輛合乘的可行性，建立對(duì)應(yīng)的合乘優(yōu)化模型；（2）通過(guò)二分圖匹配實(shí)現(xiàn)對(duì)合乘過(guò)程的描述；（3）通過(guò)改變合乘點(diǎn)選取范圍，分析合乘點(diǎn)數(shù)量對(duì)合乘模型優(yōu)化結(jié)果的影響。

2 算 例

算例路網(wǎng)如圖1所示。設(shè)定路網(wǎng)中共有22個(gè)節(jié)點(diǎn)。其中1～16節(jié)點(diǎn)為普通節(jié)點(diǎn)，17～22節(jié)點(diǎn)為合乘點(diǎn)。實(shí)線上數(shù)字表示兩點(diǎn)間的距離（單位km）。設(shè)定路網(wǎng)節(jié)點(diǎn)之間可以相互直達(dá)，圖中沒(méi)有顯示出所有節(jié)點(diǎn)間路線及其距離。路網(wǎng)中共有15位通勤司機(jī)，24位合乘乘客。設(shè)定機(jī)動(dòng)車行駛速度40km/h，乘客步行速度為5km/h。機(jī)動(dòng)車最大載客量統(tǒng)一設(shè)定為4人。司機(jī)乘客的部分出行信息分別見(jiàn)表1表2。endprint

司機(jī)能接受的最大行程時(shí)間算例中直接設(shè)置為司機(jī)通勤最晚到達(dá)時(shí)間與最早出發(fā)時(shí)間的差值。算例的匹配和優(yōu)化部分利用軟件Matlab編寫程序進(jìn)行運(yùn)算。運(yùn)算中在原有數(shù)據(jù)條件下分別設(shè)置了有合乘點(diǎn)和沒(méi)有合乘點(diǎn)兩種情況進(jìn)行對(duì)比。結(jié)果如表3所示。

從表3中看出算例中無(wú)論有無(wú)合乘點(diǎn)，每一位司機(jī)以及乘客都可以參與到合乘中。加入合乘點(diǎn)后因?yàn)槌丝偷纳宪圏c(diǎn)和下車點(diǎn)增加，司乘匹配數(shù)顯著增加，由138種增加到461種可能。優(yōu)化后結(jié)果顯示因?yàn)楹铣它c(diǎn)的加入，模型中參與人數(shù)由30位增加為37位，增加23.3%，其中有更多的乘客可以加入合乘模型中。路網(wǎng)中減少機(jī)動(dòng)車行駛距離值由311km增加到474.5km，增加52.6%。

下面對(duì)路網(wǎng)中合乘點(diǎn)的選取范圍進(jìn)行修改，分析合乘點(diǎn)對(duì)合乘模型的影響。原例中節(jié)點(diǎn)2到節(jié)點(diǎn)17、節(jié)點(diǎn)8到節(jié)點(diǎn)19、節(jié)點(diǎn)10到節(jié)點(diǎn)20、節(jié)點(diǎn)15到節(jié)點(diǎn)22距離都超過(guò)1km，超出乘客的最大步行距離（1km），意味著從節(jié)點(diǎn)2、8、10、15出發(fā)的乘客不會(huì)選擇步行到合乘點(diǎn)17、19、20、22?，F(xiàn)將上4對(duì)節(jié)點(diǎn)間距離分別改為0.9、0.7、0.7、0.9，也就是為在節(jié)點(diǎn)2、8、10、15出發(fā)的乘客增加有效合乘點(diǎn)。對(duì)修改過(guò)的算例模型進(jìn)行運(yùn)算得出的結(jié)果如表4所示。

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

3 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[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] 覃運(yùn)梅，石琴. 出租車合乘模式的探討[J]. 合肥工業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版），2006，29（1）：77-79.

[4] 吳芳，李志成，徐琛. 出租車合乘制調(diào)度優(yōu)化模型研究[J]. 蘭州交通大學(xué)學(xué)報(bào)，2009，28（1）：104-107.

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