基于交通大數(shù)據(jù)的動態(tài)拼車調(diào)度算法研究.pdf

1、隨著城市汽車數(shù)量呈現(xiàn)出爆炸性增長趨勢，引發(fā)了嚴(yán)重的交通堵塞和環(huán)境污染問題。一個高效的拼車系統(tǒng)是一種有效的解決方案，它可以在滿足乘客需求的同時，提高出租車司機(jī)的收入，同時可以減少環(huán)境污染和能源消耗。隨著智能手機(jī) GPS技術(shù)的不斷成熟，基于智能手機(jī) GPS數(shù)據(jù)實(shí)現(xiàn)一個高效的拼車調(diào)度系統(tǒng)現(xiàn)已成為建設(shè)現(xiàn)代化城市的迫切需求。然而，設(shè)計一個高效的拼車算法是非常具有挑戰(zhàn)性的工作。與非拼車調(diào)度相比，拼車調(diào)度需要更加復(fù)雜的調(diào)度策略。在實(shí)際的應(yīng)用系統(tǒng)中，拼

2、車是一個動態(tài)變化的過程，在做調(diào)度優(yōu)化的同時，也需要保證實(shí)時性。拼車另一個具有挑戰(zhàn)性的原因是乘客的查詢和出租車的位置信息都是高度動態(tài)變化的，而且很難預(yù)測。
　　為了解決上述問題，在本文中我們通過對交通大數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘及分析構(gòu)建了一種基于打車熱點(diǎn)的出租車拼車調(diào)度系統(tǒng)，它可以有效的對乘客打車請求提供實(shí)時拼車服務(wù)，并生成相應(yīng)的調(diào)度方案來滿足乘客需求。與此同時，該系統(tǒng)可以顯著減少出租車總的行駛距離。在我們的方法中，主要分為兩個階段，搜索階

3、段和調(diào)度階段。在搜索階段，提出了一個基于時間二分法的搜索策略來快速高效檢索可能滿足乘客打車需求的出租車候選集。在調(diào)度階段，根據(jù)打車請求中的限制，檢查搜索階段得到的出租車候選集中的每一輛出租車，并從中選出插入打車請求后平均滿意度最大的出租車來為乘客提供服務(wù)。為了減少空載率，針對空車我們提出了一種基于打車熱點(diǎn)的調(diào)度策略，并對地圖數(shù)據(jù)的存取進(jìn)行了優(yōu)化設(shè)置，其中熱點(diǎn)的選取、打車需求量預(yù)測、空車調(diào)度范圍等參數(shù)都通過對真實(shí)打車數(shù)據(jù)分析進(jìn)行了合理的設(shè)

4、置。之后，我們考慮到大數(shù)據(jù)的應(yīng)用場景，給出了拼車調(diào)度系統(tǒng)的Spark平臺實(shí)現(xiàn)，考慮到實(shí)時性我們采用Spark Streaming和Kafka消息隊(duì)列等技術(shù)對平臺的數(shù)據(jù)接收、數(shù)據(jù)處理、數(shù)據(jù)反饋各個模塊進(jìn)行了合理設(shè)計。
　　最后，我們采用一個打車請求生成器生成的在北京朝陽區(qū)一天包含101952次打車請求的大規(guī)模的數(shù)據(jù)集來檢驗(yàn)我們的系統(tǒng)。結(jié)果表明，我們提供的拼車調(diào)度方法和不拼車相比可以在節(jié)省30%行駛距離的同時得到40%的服務(wù)率提升，并