基于動(dòng)態(tài)規(guī)劃算法的出租車合乘模式研究*

鄧向林

（湖南交通職業(yè)技術(shù)學(xué)院，湖南 長(zhǎng)沙410132）

隨著全球環(huán)保意識(shí)不斷提高，以公共交通為主導(dǎo)的城市交通發(fā)展戰(zhàn)略，因其具有明顯的低碳特征，已成為城市交通發(fā)展的趨勢(shì)，通過(guò)發(fā)展公共運(yùn)輸來(lái)實(shí)現(xiàn)城市交通的節(jié)能減排已逐漸成為各國(guó)政府的主要施政方向。但公共交通的公交基礎(chǔ)設(shè)施建設(shè)進(jìn)度通常落后于城市區(qū)域擴(kuò)張，同時(shí)公共交通也無(wú)法解決私人交通需求的“最后一公里”問(wèn)題，在一定程度上影響到市區(qū)公共交通的服務(wù)水平。相比之下，出租車作為一種介于私人運(yùn)輸與公共運(yùn)輸之間的輔助性運(yùn)輸工具，既具有公共運(yùn)輸服務(wù)的特征，又兼具私人運(yùn)輸?shù)母咦灾餍?，可以成為城市公共運(yùn)輸系統(tǒng)的有益補(bǔ)充[1]。

出租車雖然是公共交通的已有資源，但目前 “一人一乘”的租賃模式造成空載率較高。以長(zhǎng)沙市為例，2009年全市共有7 000余輛出租車，里程空載率為36.1%[2]，其運(yùn)載能力還有提升空間。如果有效提供出租車合乘服務(wù)，可在短距離運(yùn)輸、偏遠(yuǎn)路線以及交通高峰期彌補(bǔ)公共運(yùn)輸?shù)牟蛔?。引?dǎo)出行人群采用出租車合乘服務(wù)而減少私家車使用頻率，不僅能降低公共交通成本，同時(shí)也可以配合政府的節(jié)能減排政策，使城市整體交通狀況得到明顯改善。由于出租車的運(yùn)輸方式屬于“點(diǎn)對(duì)點(diǎn)的最短路徑運(yùn)輸”，如果要提供合乘服務(wù)，必須通過(guò)繞路來(lái)完成接載多位乘客的任務(wù)，因此如何建立有效路徑算法，使有限的出租車輛實(shí)現(xiàn)載客量極大化成為需要研究的課題。

1 模型建立及求解

“車輛合乘”在廣義上包含“車輛共有”與“車輛共用”兩種情況。2003年Matthew Barth等人對(duì)車輛合乘提出了3種模式，即鄰居模式、站車模式和多點(diǎn)復(fù)合模式[3]。鄰居模式是在城市多處設(shè)置專用停車場(chǎng)，使用者在約定的時(shí)間與地點(diǎn)取用車輛，完畢后再停放到專用停車場(chǎng)，此模式要求城區(qū)內(nèi)設(shè)置足夠多的專用停車場(chǎng)。站車模式是合乘車輛僅行駛于城市至郊區(qū)的指定路段，由合乘者分?jǐn)偨煌ǔ杀?，以減少不必要的交通擁堵與燃油消耗，多適用于地廣人稀但城市交通擁堵的區(qū)域。多點(diǎn)復(fù)合模式與鄰居模式類似，區(qū)別在于租借和歸還不限于同一取車點(diǎn)，回程也可選擇其他交通工具，但服務(wù)商需每天進(jìn)行車輛重置以維持各停車場(chǎng)有足夠車輛可提供服務(wù)。

1.1 出租車合乘模式建模

我國(guó)已進(jìn)入城鎮(zhèn)化、汽車化的加速發(fā)展階段，國(guó)內(nèi)各大城市普遍存在居民出行強(qiáng)度增加、對(duì)機(jī)動(dòng)車出行依賴逐漸增加的情況。以長(zhǎng)沙市為例，2009年家庭居民人均出行次數(shù)為2.40次/日，機(jī)動(dòng)車出行占比從2007年的9.7%上升到11.2%。居民出行目的以通勤出行為主（含上班、上學(xué)、公務(wù)、回家），占比達(dá) 74.2%，出行高峰集中在 7：00～8：00、17：20～18：20 時(shí) 段 ， 高 峰 系 數(shù) 分 別 達(dá) 到18.1%、13.9%。出行空間分布具有較強(qiáng)的中心集聚性，以五一廣場(chǎng)、芙蓉廣場(chǎng)為中心，呈“T”字形向外擴(kuò)張[2]。

鄰居模式對(duì)城區(qū)停車區(qū)域占用較多不切實(shí)際，而單獨(dú)運(yùn)用站車模式或多點(diǎn)復(fù)合模式均無(wú)法滿足需求。本文結(jié)合以上模式的優(yōu)點(diǎn)設(shè)計(jì)適合國(guó)內(nèi)城市的出租車合乘模式，對(duì)主要集聚地(如車站、商圈、居民區(qū))設(shè)置為聚集站點(diǎn)，在站點(diǎn)周邊一定距離內(nèi)提供約車接送服務(wù)；設(shè)置主要客運(yùn)車站為中心站點(diǎn)，其他聚集小區(qū)為途徑站點(diǎn)，通過(guò)各小區(qū)匯聚機(jī)動(dòng)車出行的需求，實(shí)現(xiàn)各小區(qū)之間點(diǎn)對(duì)點(diǎn)的出租車合乘服務(wù)，從而擴(kuò)大合乘服務(wù)范圍，更好地發(fā)揮出租車的公共交通輔助效應(yīng)。其示意圖如圖1所示。

1.2 模型求解

本文設(shè)計(jì)的模型以出租車合乘為研究對(duì)象，其問(wèn)題類型與旅行銷售員問(wèn)題TSP（Traveling Salesman Problem）或車輛路線問(wèn)題 VRP（Vehicle Routing Problem）類同，屬于網(wǎng)絡(luò)最優(yōu)求解問(wèn)題。由于出租車實(shí)際運(yùn)營(yíng)中只會(huì)做單向運(yùn)輸，途經(jīng)兩個(gè)或更多的聚集小區(qū)，其路徑規(guī)劃歸納為對(duì)復(fù)雜情況的一對(duì)多情形組合，屬于NP類問(wèn)題。對(duì)VRP問(wèn)題通?？墒褂酶F舉法，但效率偏低，應(yīng)用動(dòng)態(tài)規(guī)劃法作為最短路徑求解是更好的方法[4]。考慮到出租車服務(wù)的實(shí)際市場(chǎng)需求，對(duì)合乘容量、車輛運(yùn)行時(shí)間、候車時(shí)間也將納入計(jì)算因素[5]，在求解規(guī)劃上主要考慮各途徑站點(diǎn)到中心站點(diǎn)的調(diào)度較優(yōu)化，這是本模型求解與傳統(tǒng)TSP或VRP問(wèn)題的最大不同，具體說(shuō)明如下：

對(duì)所有途徑小區(qū)依據(jù)其空間位置劃分為多個(gè)階段，在每個(gè)階段的起點(diǎn)做全體路徑選擇的決策判斷，選擇本階段的最優(yōu)路徑。重復(fù)以上步驟直到完成整體規(guī)劃，則所選擇路徑形成一棵決策樹(shù)。對(duì)該決策樹(shù)從終點(diǎn)站出發(fā)以逆向求解，考慮所有節(jié)點(diǎn)設(shè)置不同人數(shù)組合成為一個(gè)觀察點(diǎn)，搜尋途徑的各節(jié)點(diǎn)直到回到起點(diǎn)站為止，從而得到本路徑下對(duì)于各途徑站點(diǎn)不同人數(shù)狀況的最佳化路徑規(guī)劃。

對(duì)于正在執(zhí)行路徑規(guī)劃的出租車，如果在運(yùn)行途徑出現(xiàn)乘載需求，以乘客的運(yùn)載時(shí)間限制為門檻值判斷是否為即時(shí)需求。對(duì)于即時(shí)需求重新計(jì)算需求插入的可行性，對(duì)路徑規(guī)劃進(jìn)行調(diào)整。如圖2所示，假設(shè)i點(diǎn)為某階段出發(fā)地，j點(diǎn)為該階段目的地，z點(diǎn)為彎繞點(diǎn)，d為點(diǎn)到點(diǎn)之間的距離，v為車輛運(yùn)行平均速率。對(duì)各因素判斷方法如下：

(1)合乘容量。假設(shè)車內(nèi)已有乘客x人，即時(shí)需求乘客數(shù)為y人。出租車的合乘容量限制為z人，則應(yīng)滿足x+y≤z。

(2)運(yùn)行時(shí)間。繞行前車輛運(yùn)行時(shí)間為：

若彎繞到z點(diǎn)，則車輛運(yùn)行時(shí)間為：

假設(shè)按原路徑規(guī)劃i點(diǎn)的剩余運(yùn)行時(shí)間為Ti，則應(yīng)滿 足 Tizj≤ Ti。

(3)候車時(shí)間。假設(shè)即時(shí)需求的乘客候車時(shí)間為tz，則從i點(diǎn)到達(dá)z點(diǎn)的時(shí)間應(yīng)不超過(guò)候車時(shí)間，即滿足tz≤diz/v。

以上通過(guò)應(yīng)用動(dòng)態(tài)規(guī)劃法，對(duì)本模型的求解拆分為兩大部分：其一為對(duì)已收集的小區(qū)乘載需求進(jìn)行路徑規(guī)劃；其二為對(duì)臨時(shí)出現(xiàn)的小區(qū)乘載需求計(jì)算插入可行性，并對(duì)路徑規(guī)劃進(jìn)行調(diào)整，最后完成整體的動(dòng)態(tài)規(guī)劃調(diào)度模式。

2 模擬實(shí)驗(yàn)及結(jié)果

依據(jù)本文所建立的出租車合乘模式，以及針對(duì)該模式的求解算法，設(shè)計(jì)實(shí)例對(duì)所架構(gòu)的模型與算法進(jìn)行模擬實(shí)驗(yàn)，求證模型的邏輯正確性。設(shè)計(jì)兩個(gè)中心站點(diǎn)對(duì)6個(gè)途徑小區(qū)站點(diǎn)提供合乘服務(wù)，其空間關(guān)系示意圖如圖3所示，各小區(qū)站點(diǎn)的坐標(biāo)初始化賦值情況如表1所示。假定各小區(qū)之間為點(diǎn)對(duì)點(diǎn)的直線距離，以坐標(biāo)網(wǎng)格邊距1 000 m估算。

表1 各小區(qū)站點(diǎn)的坐標(biāo)初始化

目前出租車容量為限乘載4人，為避免乘客在合乘時(shí)有過(guò)多身體接觸，對(duì)每臺(tái)合乘車輛的容量限制調(diào)整為3人。由于出租車對(duì)乘客感知上屬于高便利性的交通方式，對(duì)候車時(shí)間限制擬定為10 min為上限[6]，對(duì)合乘出租車的乘客最大可接受運(yùn)行時(shí)間設(shè)定為30 min。關(guān)于對(duì)各站點(diǎn)服務(wù)半徑參數(shù)設(shè)置，以居民步行可接受距離900 m估算[7]，則每個(gè)站點(diǎn)的服務(wù)半徑不低于900 m。按市區(qū)內(nèi)公共交通日均運(yùn)行速率19.86 km/h估算，考慮候車時(shí)間的10 min限制，則每個(gè)站點(diǎn)的最大服務(wù)半徑不高于3.31 km。

結(jié)合各小區(qū)需求人數(shù)的不同組合，對(duì)路徑規(guī)劃的全集如圖4所示。各圓圈符號(hào)表示小區(qū)編號(hào)以及候車人數(shù)，圖中為完成以3人為單位的分組后情況。由于各小區(qū)人數(shù)都按3人為單位進(jìn)行分組，因此出租車抵達(dá)后續(xù)小區(qū)的容量應(yīng)只考慮一人或兩人的組合。

以每小時(shí)需求50人、100人來(lái)進(jìn)行模擬測(cè)試，并設(shè)定需求隨機(jī)在一小時(shí)內(nèi)各時(shí)間點(diǎn)在各途經(jīng)小區(qū)內(nèi)出現(xiàn)。對(duì)每類需求各模擬30次，結(jié)果表明，當(dāng)每小時(shí)需求50人時(shí)，該模式的乘載率為0.83；當(dāng)每小時(shí)需求提高到100人時(shí)，乘載率提高到0.92。對(duì)比傳統(tǒng)的出租車運(yùn)營(yíng)情況，模擬實(shí)驗(yàn)數(shù)據(jù)表明了合乘模式下應(yīng)用動(dòng)態(tài)規(guī)劃算法將具有較好的效益。

通過(guò)發(fā)展公共運(yùn)輸來(lái)改善城市交通狀況已成為我國(guó)政府需要面對(duì)的重要問(wèn)題，然而由于公共交通設(shè)施建設(shè)在城市化進(jìn)程的滯后性，以及公共運(yùn)輸對(duì)個(gè)人出行需求存在“最后一公里”的限制，如何運(yùn)用其他形態(tài)的運(yùn)輸方式（如出租車）來(lái)彌補(bǔ)公共交通的不足成為公共運(yùn)輸發(fā)展中需要研究的課題。本文通過(guò)構(gòu)建一種出租車合乘模式，并運(yùn)用動(dòng)態(tài)規(guī)劃算法進(jìn)行合乘路徑規(guī)劃，以簡(jiǎn)例設(shè)計(jì)以及模擬程序?qū)嶒?yàn)的方式，證明了模型的可行性。對(duì)于合乘模式下回程車輛運(yùn)載效率的提高，以及同一路徑下通過(guò)多車組隊(duì)的方式提高運(yùn)載效率是后續(xù)研究需要關(guān)注的問(wèn)題。

[1]鄭秀妙，許建華.城市出租汽車供需平衡影響因素分析[J].經(jīng)營(yíng)管理者，2011(2)：54.

[2]長(zhǎng)沙市規(guī)劃信息服務(wù)中心.2009長(zhǎng)沙市城市交通狀況年度報(bào)告[R].長(zhǎng)沙，2009.

[3]BARTH M，SHAHEEN S.Shared-use vehicle systems：a framework for classifying carsharing，station cars，and combined approaches[J].Transportation Research Record，2003，1792：105-112.

[4]LI J Q，MIRCHANDANI P B，BORENSTEIN D.Real-time vehicle rerouting problems with time windows[J].European Journal of Operational Research，2009，194(3)：711-727.

[5]HUNSAKER B，SAVELSBERGH M.Efficient feasibility testing for dial-a-ride problems[J].Operations Research Letters，2002，30(3)：169-173.

[6]郭雅玥，李妮楊，秋萍.公共交通系統(tǒng)優(yōu)化與推廣——以成都市公交系統(tǒng)為例[J].經(jīng)營(yíng)管理者，2011(4)：50.

[7]楊曉飛，馬健霄，仲小飛.公交服務(wù)半徑及服務(wù)水平研究[J].森林工程，2011，27(1)：61-64.