基于混合量子進(jìn)化算法的隨機(jī)車輛路徑問(wèn)題的研究.pdf

1、車輛路徑問(wèn)題(VRP)是物流配送末端的一項(xiàng)重要內(nèi)容，而現(xiàn)代物流產(chǎn)業(yè)的飛速發(fā)展為車輛路徑問(wèn)題的研究提供了寬闊的應(yīng)用空間。隨著我國(guó)經(jīng)濟(jì)的高速增長(zhǎng)，市場(chǎng)競(jìng)爭(zhēng)的日益加劇，產(chǎn)業(yè)升級(jí)的不斷加快，越來(lái)越多的企業(yè)把提高物流效率、降低物流成本作為提升本企業(yè)核心競(jìng)爭(zhēng)能力的重要手段。目前對(duì)于VRP的研究多是基于確定性信息，在市場(chǎng)需求瞬息萬(wàn)變的現(xiàn)代社會(huì)，與配送相關(guān)的信息往往呈現(xiàn)某種統(tǒng)計(jì)規(guī)律，隨機(jī)車輛路徑問(wèn)題(SVRP)專注于此類情況的研究。因此，對(duì)隨機(jī)車輛路徑

2、問(wèn)題的研究具有重要的學(xué)術(shù)意義和實(shí)用價(jià)值。
　　 本文針對(duì)隨機(jī)需求的車輛路徑問(wèn)題進(jìn)行研究，建立了帶時(shí)間窗的和基于模糊預(yù)約時(shí)間的多目標(biāo)問(wèn)題模型，并設(shè)計(jì)了不同的混合量子進(jìn)化算法對(duì)上述模型進(jìn)行求解。縱觀全文，本文的主要工作如下：
　　 (1)建立帶時(shí)間窗的隨機(jī)需求車輛路徑問(wèn)題(VRPSDTW)的數(shù)學(xué)模型，設(shè)計(jì)了一種基于免疫算子的混合量子進(jìn)化算法(IQEA)對(duì)上述問(wèn)題求解。針對(duì)車輛路徑問(wèn)題的特點(diǎn)，提出了一種基于整數(shù)排序的量子編碼方

3、式，并通過(guò)引用“虛擬客戶點(diǎn)”的概念將多車配送簡(jiǎn)化為單車配送。采用概率選擇最優(yōu)解和動(dòng)態(tài)旋轉(zhuǎn)角度提高算法的精細(xì)搜索能力。引入免疫算子，保留優(yōu)秀量子基段，避免出現(xiàn)倒退現(xiàn)象。對(duì)多組實(shí)例的仿真和與其他算法的對(duì)比，結(jié)果表明IQEA能獲得90％以上的最優(yōu)解，接種概率越大所得結(jié)果越精確，而且加入免疫算子的IQEA收斂速度更快。
　　 (2)在VRPSDTW的基礎(chǔ)上，建立了基于模糊預(yù)約時(shí)間的多目標(biāo)問(wèn)題模型，針對(duì)該模型設(shè)計(jì)了一種量子進(jìn)化算法(QEA

4、)與粒子群算法(PSO)分段優(yōu)化的方法對(duì)其進(jìn)行求解。分別利用QEA搜索空間大和PSO快速收斂的特性，在進(jìn)化的初始階段使用QEA獲得具有一定規(guī)模的非劣解集，并設(shè)計(jì)了一種轉(zhuǎn)化方案將離散編碼轉(zhuǎn)化為連續(xù)編碼，進(jìn)而使用PSO的進(jìn)化機(jī)制快速搜索最終的Pareto最優(yōu)解。提出了一種自適應(yīng)網(wǎng)格算法，通過(guò)自適應(yīng)的改變網(wǎng)格密度保持Pareto最優(yōu)解的多樣性和均勻性。仿真結(jié)果表明，該方法不僅能獲得足夠數(shù)量的Pareto解，而且與其他算法的對(duì)比結(jié)果也顯示該方法