摘  要： 針對目前出租車“一人一乘”的租賃模式導(dǎo)致空載率較高的問題，對現(xiàn)有的車輛合乘模式予以改進(jìn)，以提高出租車在城市公共運(yùn)輸系統(tǒng)的輔助效應(yīng)。通過構(gòu)建一種適合國內(nèi)大中型城市出行分布特征的出租車合乘模式，對出租車運(yùn)營路徑按各節(jié)點(diǎn)已確定乘載需求以決策樹求解，對運(yùn)行過程中的臨時乘載需求，以動態(tài)規(guī)范算法計(jì)算調(diào)整路徑的插入可行性，實(shí)現(xiàn)整體的動態(tài)規(guī)劃調(diào)度。模擬程序?qū)嶒?yàn)結(jié)果表明，隨著乘載量的提高，車輛運(yùn)載效率也隨著提高。
關(guān)鍵詞： 動態(tài)規(guī)劃算法；出租車合乘；運(yùn)行路徑

    隨著全球環(huán)保意識不斷提高，以公共交通為主導(dǎo)的城市交通發(fā)展戰(zhàn)略，因其具有明顯的低碳特征，已成為城市交通發(fā)展的趨勢，通過發(fā)展公共運(yùn)輸來實(shí)現(xiàn)城市交通的節(jié)能減排已逐漸成為各國政府的主要施政方向。但公共交通的公交基礎(chǔ)設(shè)施建設(shè)進(jìn)度通常落后于城市區(qū)域擴(kuò)張，同時公共交通也無法解決私人交通需求的“最后一公里”問題，在一定程度上影響到市區(qū)公共交通的服務(wù)水平。相比之下，出租車作為一種介于私人運(yùn)輸與公共運(yùn)輸之間的輔助性運(yùn)輸工具，既具有公共運(yùn)輸服務(wù)的特征，又兼具私人運(yùn)輸?shù)母咦灾餍?，可以成為城市公共運(yùn)輸系統(tǒng)的有益補(bǔ)充[1]。
    出租車雖然是公共交通的已有資源，但目前 “一人一乘”的租賃模式造成空載率較高。以長沙市為例，2009年全市共有7 000余輛出租車，里程空載率為36.1%[2]，其運(yùn)載能力還有提升空間。如果有效提供出租車合乘服務(wù)，可在短距離運(yùn)輸、偏遠(yuǎn)路線以及交通高峰期彌補(bǔ)公共運(yùn)輸?shù)牟蛔?。引?dǎo)出行人群采用出租車合乘服務(wù)而減少私家車使用頻率，不僅能降低公共交通成本，同時也可以配合政府的節(jié)能減排政策，使城市整體交通狀況得到明顯改善。由于出租車的運(yùn)輸方式屬于“點(diǎn)對點(diǎn)的最短路徑運(yùn)輸”，如果要提供合乘服務(wù)，必須通過繞路來完成接載多位乘客的任務(wù)，因此如何建立有效路徑算法，使有限的出租車輛實(shí)現(xiàn)載客量極大化成為需要研究的課題。
1 模型建立及求解
    “車輛合乘”在廣義上包含“車輛共有”與“車輛共用”兩種情況。2003年Matthew Barth等人對車輛合乘提出了3種模式，即鄰居模式、站車模式和多點(diǎn)復(fù)合模式[3]。鄰居模式是在城市多處設(shè)置專用停車場，使用者在約定的時間與地點(diǎn)取用車輛，完畢后再停放到專用停車場，此模式要求城區(qū)內(nèi)設(shè)置足夠多的專用停車場。站車模式是合乘車輛僅行駛于城市至郊區(qū)的指定路段，由合乘者分?jǐn)偨煌ǔ杀?，以減少不必要的交通擁堵與燃油消耗，多適用于地廣人稀但城市交通擁堵的區(qū)域。多點(diǎn)復(fù)合模式與鄰居模式類似，區(qū)別在于租借和歸還不限于同一取車點(diǎn)，回程也可選擇其他交通工具，但服務(wù)商需每天進(jìn)行車輛重置以維持各停車場有足夠車輛可提供服務(wù)。
1.1 出租車合乘模式建模
    我國已進(jìn)入城鎮(zhèn)化、汽車化的加速發(fā)展階段，國內(nèi)各大城市普遍存在居民出行強(qiáng)度增加、對機(jī)動車出行依賴逐漸增加的情況。以長沙市為例，2009年家庭居民人均出行次數(shù)為2.40次/日，機(jī)動車出行占比從2007年的9.7%上升到11.2%。居民出行目的以通勤出行為主（含上班、上學(xué)、公務(wù)、回家），占比達(dá)74.2%，出行高峰集中在7:00～8:00、17:20～18:20時段，高峰系數(shù)分別達(dá)到18.1%、13.9%。出行空間分布具有較強(qiáng)的中心集聚性，以五一廣場、芙蓉廣場為中心，呈“T”字形向外擴(kuò)張[2]。
    鄰居模式對城區(qū)停車區(qū)域占用較多不切實(shí)際，而單獨(dú)運(yùn)用站車模式或多點(diǎn)復(fù)合模式均無法滿足需求。本文結(jié)合以上模式的優(yōu)點(diǎn)設(shè)計(jì)適合國內(nèi)城市的出租車合乘模式，對主要集聚地(如車站、商圈、居民區(qū))設(shè)置為聚集站點(diǎn)，在站點(diǎn)周邊一定距離內(nèi)提供約車接送服務(wù)；設(shè)置主要客運(yùn)車站為中心站點(diǎn)，其他聚集小區(qū)為途徑站點(diǎn)，通過各小區(qū)匯聚機(jī)動車出行的需求，實(shí)現(xiàn)各小區(qū)之間點(diǎn)對點(diǎn)的出租車合乘服務(wù)，從而擴(kuò)大合乘服務(wù)范圍，更好地發(fā)揮出租車的公共交通輔助效應(yīng)。其示意圖如圖1所示。

1.2 模型求解
    本文設(shè)計(jì)的模型以出租車合乘為研究對象，其問題類型與旅行銷售員問題TSP（Traveling Salesman Problem）或車輛路線問題VRP（Vehicle Routing Problem）類同，屬于網(wǎng)絡(luò)最優(yōu)求解問題。由于出租車實(shí)際運(yùn)營中只會做單向運(yùn)輸，途經(jīng)兩個或更多的聚集小區(qū)，其路徑規(guī)劃歸納為對復(fù)雜情況的一對多情形組合，屬于NP類問題。對VRP問題通常可使用窮舉法，但效率偏低，應(yīng)用動態(tài)規(guī)劃法作為最短路徑求解是更好的方法[4]?？紤]到出租車服務(wù)的實(shí)際市場需求，對合乘容量、車輛運(yùn)行時間、候車時間也將納入計(jì)算因素[5]，在求解規(guī)劃上主要考慮各途徑站點(diǎn)到中心站點(diǎn)的調(diào)度較優(yōu)化，這是本模型求解與傳統(tǒng)TSP或VRP問題的最大不同，具體說明如下：
    對所有途徑小區(qū)依據(jù)其空間位置劃分為多個階段，在每個階段的起點(diǎn)做全體路徑選擇的決策判斷，選擇本階段的最優(yōu)路徑。重復(fù)以上步驟直到完成整體規(guī)劃，則所選擇路徑形成一棵決策樹。對該決策樹從終點(diǎn)站出發(fā)以逆向求解，考慮所有節(jié)點(diǎn)設(shè)置不同人數(shù)組合成為一個觀察點(diǎn)，搜尋途徑的各節(jié)點(diǎn)直到回到起點(diǎn)站為止，從而得到本路徑下對于各途徑站點(diǎn)不同人數(shù)狀況的最佳化路徑規(guī)劃。
  
2 模擬實(shí)驗(yàn)及結(jié)果
    依據(jù)本文所建立的出租車合乘模式，以及針對該模式的求解算法，設(shè)計(jì)實(shí)例對所架構(gòu)的模型與算法進(jìn)行模擬實(shí)驗(yàn)，求證模型的邏輯正確性。設(shè)計(jì)兩個中心站點(diǎn)對6個途徑小區(qū)站點(diǎn)提供合乘服務(wù)，其空間關(guān)系示意圖如圖3所示，各小區(qū)站點(diǎn)的坐標(biāo)初始化賦值情況如表1所示。假定各小區(qū)之間為點(diǎn)對點(diǎn)的直線距離，以坐標(biāo)網(wǎng)格邊距1 000 m估算。

    目前出租車容量為限乘載4人，為避免乘客在合乘時有過多身體接觸，對每臺合乘車輛的容量限制調(diào)整為3人。由于出租車對乘客感知上屬于高便利性的交通方式，對候車時間限制擬定為10 min為上限[6]，對合乘出租車的乘客最大可接受運(yùn)行時間設(shè)定為30 min。關(guān)于對各站點(diǎn)服務(wù)半徑參數(shù)設(shè)置，以居民步行可接受距離900 m估算[7]，則每個站點(diǎn)的服務(wù)半徑不低于900 m。按市區(qū)內(nèi)公共交通日均運(yùn)行速率19.86 km/h估算，考慮候車時間的10 min限制，則每個站點(diǎn)的最大服務(wù)半徑不高于3.31 km。
    結(jié)合各小區(qū)需求人數(shù)的不同組合，對路徑規(guī)劃的全集如圖4所示。各圓圈符號表示小區(qū)編號以及候車人數(shù)，圖中為完成以3人為單位的分組后情況。由于各小區(qū)人數(shù)都按3人為單位進(jìn)行分組，因此出租車抵達(dá)后續(xù)小區(qū)的容量應(yīng)只考慮一人或兩人的組合。

    以每小時需求50人、100人來進(jìn)行模擬測試，并設(shè)定需求隨機(jī)在一小時內(nèi)各時間點(diǎn)在各途經(jīng)小區(qū)內(nèi)出現(xiàn)。對每類需求各模擬30次，結(jié)果表明，當(dāng)每小時需求50人時，該模式的乘載率為0.83；當(dāng)每小時需求提高到100人時，乘載率提高到0.92。對比傳統(tǒng)的出租車運(yùn)營情況，模擬實(shí)驗(yàn)數(shù)據(jù)表明了合乘模式下應(yīng)用動態(tài)規(guī)劃算法將具有較好的效益。
    通過發(fā)展公共運(yùn)輸來改善城市交通狀況已成為我國政府需要面對的重要問題，然而由于公共交通設(shè)施建設(shè)在城市化進(jìn)程的滯后性，以及公共運(yùn)輸對個人出行需求存在“最后一公里”的限制，如何運(yùn)用其他形態(tài)的運(yùn)輸方式（如出租車）來彌補(bǔ)公共交通的不足成為公共運(yùn)輸發(fā)展中需要研究的課題。本文通過構(gòu)建一種出租車合乘模式，并運(yùn)用動態(tài)規(guī)劃算法進(jìn)行合乘路徑規(guī)劃，以簡例設(shè)計(jì)以及模擬程序?qū)嶒?yàn)的方式，證明了模型的可行性。對于合乘模式下回程車輛運(yùn)載效率的提高，以及同一路徑下通過多車組隊(duì)的方式提高運(yùn)載效率是后續(xù)研究需要關(guān)注的問題。
參考文獻(xiàn)
[1] 鄭秀妙，許建華.城市出租汽車供需平衡影響因素分析[J].經(jīng)營管理者，2011(2)：54.
[2] 長沙市規(guī)劃信息服務(wù)中心.2009長沙市城市交通狀況年度報告[R].長沙，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)營管理者，2011(4)：50.
[7] 楊曉飛，馬健霄，仲小飛.公交服務(wù)半徑及服務(wù)水平研究[J].森林工程，2011，27(1)：61-64.