隨著我國(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)題,它是一種用戶目的地相近且用戶之間的合乘關(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ù)用戶地理位置分布,應(yīng)用復(fù)合距離優(yōu)先算法將用戶劃分到各個(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)化后得到滿足時(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
【中圖分類】：U491;O224
【部分圖文】：

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

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

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