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

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

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

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

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