【摘要】：隨著GPS、Wi-Fi、RFID以及Bluetooth等無(wú)線網(wǎng)絡(luò)技術(shù)與傳感器設(shè)備的大量普及,出現(xiàn)了越來(lái)越多的車輛推薦系統(tǒng),這些車輛的移動(dòng)軌跡數(shù)據(jù)也能夠被不斷的收集,通過分析與挖掘這些歷史軌跡數(shù)據(jù),可以更好的改善車輛推薦系統(tǒng)。車輛推薦系統(tǒng)可以更好的在用戶與車輛之間進(jìn)行調(diào)度,更準(zhǔn)確地進(jìn)行車輛推薦與路線規(guī)劃,減少車輛盲目行駛,對(duì)于增加車輛的收入,減少用戶等待時(shí)間,緩解交通阻塞,以及減少環(huán)境污染都有著很強(qiáng)的現(xiàn)實(shí)意義。傳統(tǒng)的車輛推薦系統(tǒng)主要關(guān)注于用戶的滿意程度,即盡可能地減少用戶的等待時(shí)間,而忽略了車輛之間的公平性,這些系統(tǒng)趨向于推薦離用戶最近的空乘車輛。本文通過對(duì)真實(shí)歷史軌跡數(shù)據(jù)進(jìn)行統(tǒng)計(jì)分析發(fā)現(xiàn),隨著推薦次數(shù)增加,車輛之間的收入差異變得越來(lái)越大。異于傳統(tǒng)的車輛推薦系統(tǒng),本文的目的就是對(duì)于不斷產(chǎn)生的用戶請(qǐng)求,根據(jù)一些策略將請(qǐng)求推薦給車輛,使得推薦結(jié)果即能保證車輛之間分配的公平性,又能保證較短的用戶等待時(shí)間。然而,通過分析,我們發(fā)現(xiàn)這兩者是一個(gè)權(quán)衡問題,無(wú)法同時(shí)達(dá)到最優(yōu)。本文首先針對(duì)Brute-force算法與Greedy算法在解決該問題存在的不足,提出了一個(gè)高效的RRA-LSP算法。Brute-force算法屬于暴力算法,對(duì)于每一個(gè)用戶請(qǐng)求,都直接從整個(gè)城市中尋找最優(yōu)的車輛,并為其規(guī)劃行駛路線。該算法的時(shí)間復(fù)雜度較高,但結(jié)果準(zhǔn)確。Greedy算法屬于近似算法,每次都是在以用戶請(qǐng)求為圓心,半徑為3000米的范圍內(nèi)尋找局部最優(yōu)的車輛。該算法相對(duì)較快,但很難得到最優(yōu)推薦結(jié)果。RRA-LSP算法則為一個(gè)高效的算法,而且能夠得到與Brute-force算法一致的準(zhǔn)確解。RRA-LSP算法首先不斷地縮小搜索范圍,直到達(dá)到一定的條件,得到最終的搜索范圍。通過嚴(yán)格證明發(fā)現(xiàn),最優(yōu)車輛一定在該范圍內(nèi)。最后,我們只需要在該范圍內(nèi)尋找到最優(yōu)車輛,然后推薦給用戶。對(duì)于多用戶請(qǐng)求場(chǎng)景下產(chǎn)生的沖突問題,我們提出了相應(yīng)的沖突處理規(guī)則,并設(shè)計(jì)了一個(gè)均衡調(diào)度機(jī)制,用于對(duì)多用戶請(qǐng)求的分配。通過對(duì)比在兩個(gè)真實(shí)道路網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明,本文提出的算法不僅能減少車輛之間的收入差異,而且能保證較短的用戶等待時(shí)間,并且進(jìn)一步驗(yàn)證了RRALSP算法的高效性與準(zhǔn)確性,相比傳統(tǒng)的車輛推薦算法,能夠更好地保證車輛之間分配的公平性。
【圖文】：

法的推薦結(jié)果來(lái)看，都是推薦可以使得用戶等待時(shí)間盡可能小的車輛給用戶，而并沒有考慮到車輛之間分配的公平性問題。圖2.1 現(xiàn)實(shí)場(chǎng)景的在線車輛推薦問題為了更好的引出本文的推薦方法，我們先對(duì)真實(shí)的出租車歷史軌跡數(shù)據(jù)進(jìn)行分析。在這里我們統(tǒng)計(jì)分析了上海市 2500 多輛網(wǎng)約出租車 5 天的歷史軌跡數(shù)據(jù)，并有了以下的一些統(tǒng)計(jì)結(jié)論。如圖 2.2，是乘客搭乘出租車的時(shí)間的分布與累積分布圖，從圖中可以發(fā)現(xiàn)，大概 80%的乘客打車時(shí)間少于 20 分鐘，，這意味著大部分乘客的目的地

分配的公平性，而且能保證較短的乘客等待時(shí)間。（a） （b）圖2.2 乘客搭乘出租車的時(shí)間的分布于累積分布圖（a） （b）圖2.3 乘客的等待時(shí)間的分布于累積分布圖
【學(xué)位授予單位】：西安電子科技大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2018
【分類號(hào)】：U495

【參考文獻(xiàn)】

相關(guān)期刊論文 前1條

1 李成功,脫小偉,郭尚彬;公交車調(diào)度優(yōu)化模型[J];工程數(shù)學(xué)學(xué)報(bào);2002年S1期

本文編號(hào)：2632517