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

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

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

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

4、度。本文主要研究工作如下:
　　(1)介紹現(xiàn)有出租車拼車問題的特點，對相關(guān)研究進行了系統(tǒng)的總結(jié)和分析。在定義了出租車拼車問題的基礎(chǔ)上，介紹了出租車拼車問題的研究現(xiàn)狀，歸納動態(tài)拼車存在的問題和面臨的挑戰(zhàn)，如:人和車位置不確定性、實時準確的應答、計算準確的行駛時間等。綜述了幾種拼車系統(tǒng)，對這幾種拼車系統(tǒng)的框架和工作流程進行分析，并指出了這幾種拼車系統(tǒng)的優(yōu)缺點。
　　(2)設(shè)計基于城市實時路況的動態(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個模塊:數(shù)據(jù)交互模塊、RTTC模塊、搜索模塊和調(diào)度模塊。數(shù)據(jù)交互模塊接收乘車請求和出租車狀態(tài)，并將這些數(shù)據(jù)發(fā)送給搜索模塊;RTTC模塊將實時的路況信息發(fā)送給搜索模塊;搜索模塊根據(jù)時間約束、最大載客量約束和路況信息篩選出租車，

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

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