隨著我國(guó)經(jīng)濟(jì)的高速增長(zhǎng),私家車(chē)已經(jīng)成為人們普遍的出行工具,但由此帶來(lái)的交通壓力和環(huán)境污染也日趨明顯。通過(guò)車(chē)輛合乘方式共享出行則可有效緩解以上問(wèn)題,因此車(chē)輛合乘問(wèn)題(Carpooling Problem,CPP)逐漸成為研究的熱點(diǎn)領(lǐng)域。長(zhǎng)期車(chē)輛合乘問(wèn)題(Long-Term Carpooling Problem,LTCPP)屬于車(chē)輛合乘問(wèn)題的子問(wèn)題,它是一種用戶(hù)目的地相近且用戶(hù)之間的合乘關(guān)系固定的特殊車(chē)輛合乘問(wèn)題。本文應(yīng)用啟發(fā)式算法中的變鄰域搜索算法(Variable Neighborhood Search Algorithm,VNSA)對(duì)長(zhǎng)期車(chē)輛合乘問(wèn)題進(jìn)行研究,通過(guò)構(gòu)造不同變鄰域結(jié)構(gòu)對(duì)長(zhǎng)期車(chē)輛合乘問(wèn)題的解域進(jìn)行局部搜索,可在較短時(shí)間內(nèi)求解長(zhǎng)期車(chē)輛合乘問(wèn)題。首先對(duì)長(zhǎng)期車(chē)輛問(wèn)題進(jìn)行分析,構(gòu)建以出行成本為目標(biāo)函數(shù)并帶有時(shí)間窗約束和車(chē)容量約束的數(shù)學(xué)模型;然后根據(jù)用戶(hù)地理位置分布,應(yīng)用復(fù)合距離優(yōu)先算法將用戶(hù)劃分到各個(gè)合乘小組,對(duì)各個(gè)合乘小組進(jìn)行約束驗(yàn)證得到質(zhì)量較高的初始解。為了避免陷入局部最優(yōu),本文通過(guò)構(gòu)造不同的鄰域搜索結(jié)構(gòu)分別對(duì)初始解進(jìn)行局部?jī)?yōu)化,經(jīng)過(guò)鄰域搜索迭代優(yōu)化后得到滿(mǎn)足時(shí)間窗口約束和車(chē)容量約束的較優(yōu)解。最后構(gòu)建基于分布式計(jì)算的變鄰域搜索機(jī)制,提高算法的可靠性和精度,達(dá)到節(jié)約出行成本的目的。實(shí)驗(yàn)結(jié)果表明,該算法對(duì)于大規(guī)模算例能夠求解出高質(zhì)量的較優(yōu)解,同時(shí)該算法在收斂速度和求解時(shí)間上均有較高的優(yōu)勢(shì)。
【學(xué)位單位】：遼寧工程技術(shù)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位年份】：2018
【中圖分類(lèi)】：U491;O224
【部分圖文】：

圖 2.1 路徑示意Figure2.1 Path schematic在路徑規(guī)劃中，司機(jī)只能訪(fǎng)問(wèn)用戶(hù)頂點(diǎn)一次，當(dāng)司機(jī)到達(dá)一個(gè)用戶(hù)頂點(diǎn)時(shí)，開(kāi)始窗約束，由于有些較短路徑可能無(wú)法滿(mǎn)足某些用戶(hù)的時(shí)間窗約束，本文在此引入約束，每位用戶(hù)都各自設(shè)置一個(gè)最遲忍耐時(shí)間wt ，如果司機(jī)無(wú)法在用戶(hù)的時(shí)間窗戶(hù)出發(fā)地，便檢驗(yàn)司機(jī)是否能在用戶(hù)最遲忍耐時(shí)間內(nèi)到達(dá)用戶(hù)出發(fā)地。以圖 2.2機(jī)d 進(jìn)行路徑規(guī)劃，首先訪(fǎng)問(wèn)用戶(hù)1c ，2c ，3c 。司機(jī)d 無(wú)法滿(mǎn)足用戶(hù)3c 的軟時(shí)間如圖 2.2(a)所示。則司機(jī)d 進(jìn)行回退訪(fǎng)問(wèn)，如圖 2.2 (b)所示。司機(jī)d 從1c 開(kāi)始訪(fǎng)目的地，合乘小組無(wú)法滿(mǎn)足到達(dá)目的地的硬時(shí)間窗約束，司機(jī)d 進(jìn)行回退訪(fǎng)問(wèn)，c)所示。司機(jī)d 從3c 開(kāi)始訪(fǎng)問(wèn)，由于不能訪(fǎng)問(wèn)2c ，則司機(jī)直接訪(fǎng)問(wèn)目的地，由于合有用戶(hù)2c 沒(méi)有被訪(fǎng)問(wèn)，則該條路徑規(guī)劃失敗，如圖 2.2 (d)所示。如圖 2.2 (e)所示d 無(wú)法滿(mǎn)足用戶(hù)3c 的軟時(shí)間窗約束，則司機(jī)d 進(jìn)行回退訪(fǎng)問(wèn)，此時(shí)訪(fǎng)問(wèn)序列中僅，故將1c 從第二訪(fǎng)問(wèn)頂點(diǎn)中刪除。司機(jī)d 對(duì)2c 進(jìn)行訪(fǎng)問(wèn)，若司機(jī)d 無(wú)法滿(mǎn)足用戶(hù)間窗約束，則司機(jī)d 進(jìn)行回退訪(fǎng)問(wèn)，此時(shí)司機(jī)訪(fǎng)問(wèn)序列僅剩司機(jī)d ，故將2c 從第

目的地，合乘小組無(wú)法滿(mǎn)足到達(dá)目的地的硬時(shí)間窗約束，司機(jī)d 進(jìn)行回退訪(fǎng)問(wèn)，如圖2.2 (c)所示。司機(jī)d 從3c 開(kāi)始訪(fǎng)問(wèn)，由于不能訪(fǎng)問(wèn)2c ，則司機(jī)直接訪(fǎng)問(wèn)目的地，由于合乘小組內(nèi)有用戶(hù)2c 沒(méi)有被訪(fǎng)問(wèn)，則該條路徑規(guī)劃失敗，如圖 2.2 (d)所示。如圖 2.2 (e)所示，若司機(jī)d 無(wú)法滿(mǎn)足用戶(hù)3c 的軟時(shí)間窗約束，則司機(jī)d 進(jìn)行回退訪(fǎng)問(wèn)，此時(shí)訪(fǎng)問(wèn)序列中僅剩司機(jī)d ，故將1c 從第二訪(fǎng)問(wèn)頂點(diǎn)中刪除。司機(jī)d 對(duì)2c 進(jìn)行訪(fǎng)問(wèn)

合乘方案表述了能夠比較直觀(guān)的體現(xiàn)合乘小組的具體細(xì)節(jié)信息，本節(jié)對(duì) LTCPP 合乘方案中進(jìn)行表述，即在待求解問(wèn)題和算法生成的解決方案之間建立一個(gè)完整的映射P 的合乘方案表述包括合乘方案中各個(gè)合乘小組的用戶(hù)信息，在合乘小組內(nèi)用該用戶(hù)接送組內(nèi)其他用戶(hù)的行駛路徑和接送時(shí)間等信息。因此，合乘方案表。第一層僅顯示各個(gè)合乘小組的用戶(hù)編號(hào)信息，而第二層則記錄組內(nèi)用戶(hù)是用戶(hù)作為司機(jī)時(shí)接送組內(nèi)其他用戶(hù)的行駛路徑、總行駛時(shí)間、接送其他用戶(hù)的離和到達(dá)目的地時(shí)間。上所述，在合乘方案的第一層表述為合乘小組集合 1 2, ,...,nS P P P，其中各含的用戶(hù)表述為 , ,..., kP i j m。第二層表述合乘小組內(nèi)每位用戶(hù)i 作為輪值司機(jī)時(shí)的詳細(xì)信息，其中包括用戶(hù)iR 、出發(fā)時(shí)間及到達(dá)其他用戶(hù)所在地點(diǎn)的時(shí)間iT 、是否與其他用戶(hù)合乘i 、itance 、行駛時(shí)間it 及到達(dá)目的地時(shí)間iavt 。合乘方案表述示意圖如圖 3.1 所示。

【參考文獻(xiàn)】

相關(guān)期刊論文 前8條

1 張亦楠;魏志強(qiáng);劉昊;;出租車(chē)多人合乘匹配問(wèn)題的研究[J];信息通信;2014年03期

2 鄧向林;;基于動(dòng)態(tài)規(guī)劃算法的出租車(chē)合乘模式研究[J];微型機(jī)與應(yīng)用;2013年08期

3 宋超超;王洪國(guó);邵增珍;楊福萍;;一種求解多車(chē)輛合乘匹配問(wèn)題的適應(yīng)性算法[J];計(jì)算機(jī)科學(xué);2013年02期

4 程杰;唐智慧;劉杰;鐘流;;基于遺傳算法的動(dòng)態(tài)出租車(chē)合乘模型研究[J];武漢理工大學(xué)學(xué)報(bào)(交通科學(xué)與工程版);2013年01期

5 周和平;鐘璧檣;彭霞花;夏西;;出租車(chē)合乘路徑選擇與費(fèi)率優(yōu)化模型[J];長(zhǎng)沙理工大學(xué)學(xué)報(bào)(自然科學(xué)版);2011年01期

6 李成華;張新訪(fǎng);金海;向文;;MapReduce:新型的分布式并行計(jì)算編程模型[J];計(jì)算機(jī)工程與科學(xué);2011年03期

7 董紅宇;黃敏;王興偉;鄭秉霖;;變鄰域搜索算法綜述[J];控制工程;2009年S2期

8 劉志碩;柴躍廷;申金升;;蟻群算法及其在有硬時(shí)間窗的車(chē)輛路徑問(wèn)題中的應(yīng)用[J];計(jì)算機(jī)集成制造系統(tǒng);2006年04期

本文編號(hào)：2824626