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

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

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

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

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