高效移動(dòng)序列推薦算法的研究與實(shí)現(xiàn).pdf

1、大規(guī)模的位置軌跡數(shù)據(jù)為發(fā)現(xiàn)運(yùn)輸系統(tǒng)中有用信息提供了不可預(yù)測(cè)的機(jī)會(huì)。一個(gè)熱點(diǎn)研究領(lǐng)域就是抽取節(jié)能高效的運(yùn)輸模式以便節(jié)省能源提高效率。本文著重研究節(jié)能高效的移動(dòng)序列推薦問(wèn)題。該問(wèn)題的目的就是為空的出租車推薦一條連接一系列載客點(diǎn)的最優(yōu)線路，使得該出租車能夠以最小的巡航開(kāi)銷載到乘客。求解該問(wèn)題對(duì)于節(jié)省能源提高效率、增加收益、減小環(huán)境污染以及緩解交通都具有非常廣泛的實(shí)踐意義。求解該問(wèn)題的主要面臨的挑戰(zhàn)就是它的高計(jì)算復(fù)雜度。
　　本文提出了一

2、種基于動(dòng)態(tài)規(guī)劃的方法來(lái)解決該問(wèn)題。本文提出的的方法主要分為兩個(gè)部分：線下預(yù)處理部分和線上搜索部分。在線下預(yù)處理部分，本文發(fā)現(xiàn)了比較序列間代價(jià)的常用潛在行駛距離函數(shù)滿足迭代特性并給出了迭代公式，基于該函數(shù)的迭代特性，提出了兩種新的潛在序列剪枝方法：增量剪枝和批量剪枝。在此基礎(chǔ)上，提出了一種后向遞增的潛在序列構(gòu)造算法，并同時(shí)進(jìn)行潛在序列的增量剪枝，使得候選路徑的搜索空間大大減小。此外，在生成的特定長(zhǎng)度的潛在序列集合中，進(jìn)一步使用批量剪枝方法

3、對(duì)候選序列集進(jìn)行了大量約簡(jiǎn)。而為了處理更大規(guī)模的數(shù)據(jù)，本文把提出的兩個(gè)算法在MapReduce上進(jìn)行并行實(shí)現(xiàn)，使得算法效率有了數(shù)量級(jí)的提升。通過(guò)線下剪枝效率隨著序列長(zhǎng)度的不斷提高，在線上處理部分，本文提出的的方法能夠?qū)λ玫暮蜻x潛在序列集合實(shí)時(shí)高效地完成最優(yōu)線路的搜索。另外，本文開(kāi)發(fā)了一個(gè)出租車線路推薦的原型系統(tǒng)，以便應(yīng)用于實(shí)際場(chǎng)景中。
　　通過(guò)對(duì)比在真實(shí)和人工數(shù)據(jù)集上的實(shí)驗(yàn)表明：本文提出的方法能夠使得線下搜索時(shí)間得到極大降低，能