車輛合乘匹配問題研究.pdf

1、進入21世紀以來我國經(jīng)濟飛速發(fā)展,隨著人民生活水平的不斷提高,私家車擁有量不斷攀升.私家車大規(guī)模進入尋常家庭給人們帶來了許多便利和享受,在擴大內(nèi)需、促進經(jīng)濟發(fā)展、提高人民生活水平等方面都起著重要作用.然而,私家車的快速發(fā)展一定程度上造成環(huán)境污染、交通擁堵、資源利用率低等一系列的社會問題,阻礙著城市交通的健康發(fā)展,如何合理的利用好私家車這個社會資源,提高社會資源的利用率,降低環(huán)境污染,使私家車出行惠及全社會,成為了一個大家不得不思考和解決

2、的重要問題,由此各國學者提出了車輛合乘匹配(Vehicle Ride-Matching,RMP)——即“拼車”的解決方案.
　　車輛合乘匹配問題,是指車主與搭乘順風車的乘客雙方達成一定的約定,車主愿意讓乘客順便搭乘自己駕駛的車輛出行,并在雙方認為合適的地方讓乘客下車,合乘產(chǎn)生的費用由乘客(包括車主)分攤的出行方式.目前,針對車輛合乘匹配問題,國內(nèi)外已經(jīng)有了一些研究成果,為后續(xù)的深入研究奠定了重要的基礎(chǔ).但是現(xiàn)有的研究仍存在以下幾點

3、不足:
　　(1)當前的車輛合乘匹配問題著重于合乘匹配制度、政策、道路設(shè)施等方面的研究,對于合乘匹配問題具體數(shù)據(jù)模型的構(gòu)建以及調(diào)度優(yōu)化等方面的研究較少.
　　(2)現(xiàn)有的車輛合乘網(wǎng)站,大多只是簡單的信息發(fā)布供求平臺,不具備智能匹配功能,沒有較好的乘客選擇方法,無法保證合乘行駛路線的最優(yōu)化.
　　(3)車輛合乘涉及到車主和乘客雙方,由于受路線匹配程度、花費成本、時間窗、車主和乘客的容忍度等因素的影響,導致搭載成功率比較低

4、.
　　本文在已有的研究成果基礎(chǔ)上,針對以上問題展開研究,主要的研究工作概括如下:
　　1.對現(xiàn)有的車輛合乘匹配問題相關(guān)研究進行了系統(tǒng)的總結(jié)和分析,綜述了車輛合乘匹配問題.
　　在定義了車輛合乘匹配問題概念、研究要素和分類的基礎(chǔ)上,給出了車輛合乘匹配問題的研究現(xiàn)狀,分析了車輛合乘匹配研究存在的問題.詳細地綜述了求解車輛合乘匹配問題的啟發(fā)式算法,系統(tǒng)地描述了各種算法的機理.
　　2.針對單車輛合乘匹配問題,構(gòu)建了帶

5、約束條件的數(shù)學模型,并提出了基于乘客選擇的合乘路線優(yōu)化方法,有效地解決了乘客選擇盲目性問題,提高了合乘路線匹配的效率.
　　通過引入容量約束和時間窗約束,研究了帶約束條件的單車輛合乘匹配問題,構(gòu)建了合乘匹配問題的數(shù)學模型,并提出了求解該模型的算法.單車輛合乘匹配問題的解決方案往往過于重視乘客選擇,忽視車主的意愿,而使合乘路線與車主原本的行駛路線出現(xiàn)很大的偏離,本文提出在車主最優(yōu)行駛路線的基礎(chǔ)上進行乘客選擇,既重視了車主的意愿,又滿

6、足了乘客的要求.本文提出的解決方法分為三部分:第一部分,利用Dijkstra算法找出車主的最優(yōu)行駛路線;第二部分,在車主最優(yōu)行駛路線的基礎(chǔ)上,優(yōu)先選擇與車主路線基本匹配的乘客,其次選擇不完全匹配的乘客;第三部分,利用優(yōu)先關(guān)系確定乘客的搭乘順序,并重新優(yōu)化合乘的行駛路線.實驗結(jié)果說明,該算法有效地解決了乘客選擇盲目性的問題,提高了合乘路線匹配的效率.
　　3.針對多車輛合乘匹配問題,構(gòu)建了數(shù)學模型,提出了一種兩階段算法,有效地提高了

7、多車輛合乘的搭載成功率,實現(xiàn)了合乘路線最優(yōu)的目標.
　　通過對單車輛合乘匹配問題的擴展,引入新的約束條件,研究了一類多車輛合乘匹配問題.考慮到在搭載成功率高的情況下,實現(xiàn)合乘路徑最短的目標,構(gòu)建了問題的數(shù)學模型.在該模型中采用軟時間窗約束,加入了一定的懲罰機制,使模型更接近現(xiàn)實.本文提出了求解該模型的兩階段算法.第一階段,采用乘客分配算法去解決乘客分類問題,通過乘客的單乘距離與重疊距離的關(guān)系,實現(xiàn)乘客最終分類;第二階段,利用改進的