車輛路徑問題的量子進(jìn)化算法研究.pdf

1、物流業(yè)已成為國際經(jīng)濟(jì)體系的重要組成部分，是推動經(jīng)濟(jì)全球化的重要服務(wù)業(yè)。但是物流費(fèi)用居高不下，特別是運(yùn)輸費(fèi)用占社會物流費(fèi)用的比重達(dá)到一半以上，是影響物流成本的重要因素。車輛路徑問題（Vehicle Routing Problem，VRP）主要研究物流配送環(huán)節(jié)車輛路線的優(yōu)化，是物流配送優(yōu)化中的關(guān)鍵一環(huán)。該問題是運(yùn)籌學(xué)和組合優(yōu)化領(lǐng)域著名的NP問題，隨著問題規(guī)模的增加會產(chǎn)生指數(shù)爆炸，目前的求解方法主要是亞啟發(fā)式算法。本文主要研究了一種新型的進(jìn)化

2、算法-量子進(jìn)化算法（Quantum Evolutionary Algorithm，QEA）在車輛路徑問題中的應(yīng)用，具體求解以下四類問題：有能力約束車輛路徑問題（Capacitated Vehicle Routing Problem，CVRP），開發(fā)式車輛路徑問題（Open Vehicle Routing Problem，OVRP），動態(tài)網(wǎng)絡(luò)車輛路徑問題（Dynamic Networks Vehicle Routing Problem），

3、動態(tài)需求車輛路徑問題（Dynamic Demands Vehicle Routing Problem）。本文的主要成果如下： 1.研究了有能力約束車輛路徑問題的量子進(jìn)化算法求解方法。提出0-1矩陣的編碼方法，通過量子旋轉(zhuǎn)門實(shí)現(xiàn)進(jìn)化，引入災(zāi)變操作保證解的多樣性；分析了算法復(fù)雜度；選用基準(zhǔn)實(shí)例進(jìn)行測試，并與其它算法進(jìn)行了比較。實(shí)驗(yàn)結(jié)果表明量子進(jìn)化算法是求解有能力約束車輛路徑問題的有效算法。 2.建立了開發(fā)式車輛路徑問題的數(shù)學(xué)

4、模型，研究了求解開發(fā)式車輛路徑問題的量子進(jìn)化算法。算法采用動態(tài)調(diào)整旋轉(zhuǎn)角機(jī)制，混合了最鄰近算法和2-Opt方法增強(qiáng)局部搜索能力；分析了算法復(fù)雜度；討論了算法參數(shù)對于優(yōu)化結(jié)果的影響。選用基準(zhǔn)實(shí)例進(jìn)行了測試。 3.研究了量子進(jìn)化算法求解動態(tài)網(wǎng)絡(luò)車輛路徑問題。建立了動態(tài)網(wǎng)絡(luò)車輛路徑問題的數(shù)學(xué)模型；構(gòu)造了測試實(shí)例并進(jìn)行了求解，并對量子進(jìn)化算法的收斂性進(jìn)行了證明。 4.研究了量子進(jìn)化算法求解動態(tài)需求車輛路徑問題。建立了動態(tài)需求車輛