基于k-Regret查詢的動態(tài)共乘問題研究.pdf

1、隨著經(jīng)濟的發(fā)展和城市化進程的推進，城市交通越來越擁堵，出行問題受到民眾和相關管理部門的廣泛關注。目前城市交通中，存在車輛空載率高的問題，共乘是一種降低空載率、緩解交通擁堵的有效解決方案。目前，滴滴、Uber等出行軟件提供了網(wǎng)約車及順風車等服務，方便民眾出行的同時在一定程度上緩解了交通擁堵。但是當前的順風車服務需要提前預定以及人為規(guī)劃路線，未能處理實時提交的拼車出行請求，完成動態(tài)共乘服務。
　　本論文研究內(nèi)容是將實時提交的出行請求與

2、路網(wǎng)上行駛的車輛進行動態(tài)匹配的動態(tài)共乘出行問題。動態(tài)共乘問題的研究框架主要由車輛索引構建、路徑規(guī)劃、車輛過濾、車輛-請求匹配四部分組成，本文的研究工作集中在車輛過濾和車輛-請求匹配模塊。在車輛索引方面，本文采用已有的網(wǎng)格索引，該索引結構簡單高效，能滿足車輛位置快速動態(tài)更新的索引要求。在路徑規(guī)劃方面，由于多乘客的路徑規(guī)劃是旅行商問題，本文采用簡潔有效的插入策略下的路徑規(guī)劃方式。
　　在車輛過濾階段，發(fā)現(xiàn)車輛原路徑可視為插入路徑規(guī)劃后

3、新路徑的簡化軌跡，結合方向保證的軌跡簡化思想，本文提出了滿足方向約束的車輛過濾算法。該算法借助滿足方向約束的可探索范圍，對不滿足約束條件的車輛進行過濾從而得到候選集，并從理論上證明探索范圍的合理性。
　　在車輛-請求匹配階段，為彌補已有算法無法滿足乘客個性化出行需求的不足，可使用Skyline查詢選擇匹配車輛，但Skyline查詢結果集的體積不受約束，可依據(jù)乘客選擇的偏好或以往出行習慣確定的偏好函數(shù)，選擇此時得分最高的車輛進行車輛

4、-請求匹配。本文提出了基于k-Regret查詢的匹配算法，該算法對已完成路徑規(guī)劃的候選車輛從共乘車費和到達延時兩個維度進行共乘損失評估，選擇損失最大的乘客作為代表表示整個車輛并進行k-Regret查詢得到最大損失最小化的結果集，乘客根據(jù)自身偏好選擇匹配度更高的車輛完成出行請求從而提升出行質量;進一步地，本文考慮已有乘客的車輛所包含的偏好信息，形成具有強約束的后悔查詢，通過消除部分非最優(yōu)解，提升查詢效率。
　　實驗部分設計并實現(xiàn)原型