車輛路徑問題的量子進化算法研究.pdf

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

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

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

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