基于城市實(shí)時(shí)路況的動(dòng)態(tài)拼車算法研究.pdf

1、出租車在城市公共交通中扮演非常重要的角色，如何降低出租車空載率，解決乘客打車難問題是城市生活中面臨的重大課題。出租車拼車系統(tǒng)能夠根據(jù)乘客需求自動(dòng)匹配出租車，實(shí)現(xiàn)出租車一次行程搭載多個(gè)乘客，提高出租車資源利用率。這不僅有效降低公眾出行費(fèi)用，而且有助于提倡人們減少自駕出行，從而緩解交通擁堵和減輕環(huán)境污染，具有重要的現(xiàn)實(shí)意義。
　　目前，針對出租車拼車問題的研究中，出租車是根據(jù)時(shí)間約束和載客量限制篩選的，忽略了實(shí)時(shí)交通狀況對車輛的影響。

2、這種算法有兩方面問題:一方面，系統(tǒng)可能將擁堵路段的出租車分配給乘客，導(dǎo)致出租車不能按時(shí)到達(dá)預(yù)定地點(diǎn)，從而降低拼車服務(wù)的準(zhǔn)確性。另一方面，擁堵路段上的出租車基本上是不可能為乘客提供所要求的服務(wù)，但系統(tǒng)仍然對擁堵路段的出租車進(jìn)行搜索和調(diào)度，影響系統(tǒng)應(yīng)答速度。因此，如何過濾掉擁堵路段的出租車，提高出租車拼車的準(zhǔn)確性和應(yīng)答速度是一個(gè)值得研究的重要問題。
　　為了解決上述問題，本文提出了基于城市實(shí)時(shí)路況的動(dòng)態(tài)拼車算法(DynamicCarp

3、ooling algorithm Based on Urban Real-time Traffic Conditions DC-RTTC),DC-RTTC拼車算法包括:DC-RTTC候選出租車搜索算法和DC-RTTC調(diào)度策略。為了驗(yàn)證本文提出的拼車算法，采用北京市2008年2月10355輛出租車產(chǎn)生的GPS軌跡數(shù)據(jù)集和實(shí)驗(yàn)平臺TaxiQueryGenerator進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，DC-RTTC拼車算法提高了拼車服務(wù)的準(zhǔn)確性和響應(yīng)速

4、度。本文主要研究工作如下:
　　(1)介紹現(xiàn)有出租車拼車問題的特點(diǎn)，對相關(guān)研究進(jìn)行了系統(tǒng)的總結(jié)和分析。在定義了出租車拼車問題的基礎(chǔ)上，介紹了出租車拼車問題的研究現(xiàn)狀，歸納動(dòng)態(tài)拼車存在的問題和面臨的挑戰(zhàn)，如:人和車位置不確定性、實(shí)時(shí)準(zhǔn)確的應(yīng)答、計(jì)算準(zhǔn)確的行駛時(shí)間等。綜述了幾種拼車系統(tǒng)，對這幾種拼車系統(tǒng)的框架和工作流程進(jìn)行分析，并指出了這幾種拼車系統(tǒng)的優(yōu)缺點(diǎn)。
　　(2)設(shè)計(jì)基于城市實(shí)時(shí)路況的動(dòng)態(tài)拼車系統(tǒng)框架（Dynamic C

5、arpooling Framework Basedon Urban Real-time Traffic Conditions RTC）和數(shù)據(jù)模型。數(shù)據(jù)模型包含:乘車請求、出租車狀態(tài)、路況信息和網(wǎng)格索引。系統(tǒng)框架包含4個(gè)模塊:數(shù)據(jù)交互模塊、RTTC模塊、搜索模塊和調(diào)度模塊。數(shù)據(jù)交互模塊接收乘車請求和出租車狀態(tài)，并將這些數(shù)據(jù)發(fā)送給搜索模塊;RTTC模塊將實(shí)時(shí)的路況信息發(fā)送給搜索模塊;搜索模塊根據(jù)時(shí)間約束、最大載客量約束和路況信息篩選出租車，

6、并將篩選出來的候選出租車集合發(fā)送給調(diào)度模塊;調(diào)度模塊對候選集合中每一輛出租車進(jìn)行插入可行性檢查，并計(jì)算得到一輛“合適”的出租車推薦給乘客。
　　(3)提出基于城市實(shí)時(shí)路況的候選出租車搜索算法。DC-RTTC候選出租車搜索算法采用了RTC系統(tǒng)框架，考慮道路擁堵狀況對車輛行駛速度的影響，引入道路擁堵系數(shù)，將路況劃分為不同的等級，并根據(jù)擁堵系數(shù)計(jì)算行駛時(shí)間。DC-RTTC候選出租車搜索算法的工作流程大致為:首先，根據(jù)時(shí)間約束和路況信息篩

7、選出發(fā)地和目的地附近的網(wǎng)格;其次，根據(jù)時(shí)間約束、最大載客量約束和路況信息篩選目標(biāo)網(wǎng)格內(nèi)的出租車;最后，得到出租車候選集。
　　(4)提出基于城市實(shí)時(shí)路況的調(diào)度策略。DC-RTTC調(diào)度策略包含DC-RTTC最優(yōu)調(diào)度策略和DC-RTTC最快調(diào)度策略，DC-RTTC調(diào)度策略需要檢查插入可行性，確保將新的出發(fā)地和目的地插入到出租車行程計(jì)劃表后，不違反到達(dá)原行程計(jì)劃表其他點(diǎn)的時(shí)間約束。同時(shí)，出租車為了接送新乘客會比原行程計(jì)劃多繞行一段距離，