發(fā)布時(shí)間：2021-03-25 07:04

　　針對(duì)現(xiàn)有的車輛共享調(diào)度算法未充分考慮車輛共享調(diào)度時(shí)造成的接駁費(fèi)用問題,研究最小車輛規(guī)模最少接駁費(fèi)用調(diào)度優(yōu)化模型,并改進(jìn)二分圖匹配算法進(jìn)行求解。根據(jù)車輛共享過程中調(diào)度方案的優(yōu)化問題描述,以滿足給定出行需求的車輛規(guī)模最小以及車輛調(diào)度接駁費(fèi)用最少為目標(biāo),構(gòu)建雙目標(biāo)優(yōu)化模型�；谟邢驘o環(huán)圖對(duì)車輛出行需求進(jìn)行建模,將模型求解轉(zhuǎn)化為二分圖最大匹配且權(quán)重最優(yōu)匹配問題,提出Kuhn-Munkres算法求解最大匹配最小權(quán)重匹配的權(quán)重設(shè)置條件并進(jìn)行證明,進(jìn)而設(shè)計(jì)Hopcroft-Karp與Kuhn-Munkres算法融合框架進(jìn)行求解。以安徽省宣城市部分出行為例進(jìn)行模型和算法合理性分析,479輛自動(dòng)駕駛共享車輛可以滿足13 575個(gè)出行需求;與未考慮接駁費(fèi)用目標(biāo)的調(diào)度算法相比,調(diào)度總費(fèi)用減少40.8%左右。算法可求解最小車輛規(guī)模并降低調(diào)度成本。 

【文章來源】：交通信息與安全. 2020,38(02)北大核心CSCD

【文章頁數(shù)】：10 頁

【部分圖文】：

車輛共享接駁示意Fig.1Vehiclesharingdiagram

ǖ撓邢蛭藁吠冀?Ａ瞬煌?某盜鏡鞫?的分配方案。例如，圖2（a）所示的車輛分配方案包括：T1T3，T1T2T3，T1T4T3，T5T4T6，T5T6。圖1的最小車隊(duì)規(guī)模問題則轉(zhuǎn)化為求解有向無環(huán)圖的最少不相交路徑覆蓋問題。如圖2（b）所示，T1T2T3，T5T4T6為圖2（a）有向無環(huán)圖的最小不相交路徑覆蓋，路徑數(shù)量為2，表示滿足圖1車輛出行需求的車輛共享最小規(guī)模為2。（a）車輛共享有向無環(huán)圖（b）最小不相交路徑覆蓋圖2車輛有向無環(huán)圖Fig.2Directedacyclicgraphofvehiclesharing2.2二分圖的最大匹配與帶權(quán)最大匹配2.2.1二分圖匹配對(duì)于上述構(gòu)建的車輛共享有向無環(huán)圖，其最小路徑覆蓋問題可以應(yīng)用二分圖的最大匹配算法進(jìn)行求解。二分圖是一種經(jīng)典的圖論模型，最早用于婚戀匹配的問題中，目前已形成比較成熟的理論。二分圖一般用G=(X?Y?E)表示，X?Y表示頂點(diǎn)集分割的不相交的2個(gè)子集，E為連接2個(gè)集合的邊集，其連接的2個(gè)頂點(diǎn)分別在X?Y這2個(gè)子集中。在本研究當(dāng)中，把圖2有向無環(huán)圖描述的車輛出行需求T={T1?T2??Tk}中的每個(gè)點(diǎn)Tk拆分成Tkx和Tky這2個(gè)點(diǎn)，見圖3（a）。對(duì)于V=(N?E)，如果2個(gè)出行需求Tx和Ty能夠連接，則加1條邊從X集合中的Tx指向Y集合中的Ty，即可得到V所對(duì)應(yīng)的二分圖。二分圖有以下3個(gè)核心概念。1）最大匹配。在二分圖G=(X?Y?E)中，若存在1個(gè)子圖MíG，且M中的任意的邊集均不同時(shí)連接到同一頂點(diǎn)，則稱M為G的1個(gè)匹配，見圖3（b）實(shí)線

算法流程獲得KM算法改進(jìn)條件后，提出求解最大匹配情況下最小權(quán)重匹配的HK-KM算法流程。算法在給定出行需求后，將出行需求轉(zhuǎn)化為有向無環(huán)圖，進(jìn)一步轉(zhuǎn)化為二分圖，根據(jù)出行的時(shí)空信息構(gòu)建二分圖的銜接矩陣和費(fèi)用權(quán)重矩陣。最小車輛規(guī)模目標(biāo)模型輸入二分圖銜接矩陣，通過HK算法求解二分圖最大匹配k，同時(shí)，最少費(fèi)用目標(biāo)模型輸入原始接駁費(fèi)用權(quán)重和最大匹配數(shù)k，補(bǔ)充邊的權(quán)重調(diào)整為L(zhǎng)>klmax，通過調(diào)整后的KM算法求解最小權(quán)重匹配，即可求得最大匹配情況下最小權(quán)重匹配方案。具體算法流程見圖6。圖6最小車輛規(guī)模最少費(fèi)用求解算法流程圖Fig.6Algorithmflowchart3案例研究3.1出行數(shù)據(jù)獲取案例分析選取安徽省宣城市中心城區(qū)某年某月卡口系統(tǒng)的車牌識(shí)別數(shù)據(jù)進(jìn)行先驗(yàn)信息庫的構(gòu)建與案例分析，數(shù)據(jù)內(nèi)容見表1。宣城市位于安徽省東南76

【參考文獻(xiàn)】：
期刊論文
[1]無人駕駛汽車共享調(diào)度方法研究[J]. 崔洪軍,李雨生,朱敏清,李霞,宋長(zhǎng)柏.  公路交通科技. 2019(12)
[2]未來城市自動(dòng)駕駛共享汽車規(guī)模研究：以上海為例[J]. 姚曉銳,王冠,楊超.  交通運(yùn)輸系統(tǒng)工程與信息. 2019(06)
[3]基于調(diào)度池的共享單車調(diào)度研究[J]. 蔣塬銳,賈順平,李軍.  交通信息與安全. 2019(05)
[4]基于遺傳算法的定制公交多停車場(chǎng)多車線路優(yōu)化[J]. 王超,馬昌喜.  交通信息與安全. 2019(03)
[5]自動(dòng)駕駛條件下共享車輛車隊(duì)規(guī)模[J]. 王冠,楊超,張英杰,陳海林.  綜合運(yùn)輸. 2019(02)
[6]無人駕駛汽車路徑跟蹤控制方法擬人程度研究[J]. 郭應(yīng)時(shí),蔣拯民,白艷,唐杰幀.  中國(guó)公路學(xué)報(bào). 2018(08)

碩士論文
[1]基于車聯(lián)網(wǎng)環(huán)境的共享自動(dòng)駕駛汽車調(diào)度研究[D]. 王睿.大連理工大學(xué) 2019
[2]基于匹配理論的共享車輛網(wǎng)絡(luò)穩(wěn)定最優(yōu)車輛調(diào)度策略[D]. 鐘宜軒.哈爾濱工業(yè)大學(xué) 2019



本文編號(hào)：3099263