物流配送動態(tài)需求車輛調(diào)度模型及其混合QEA研究.pdf

1、現(xiàn)代物流業(yè)的飛速發(fā)展為車輛路徑問題（Vehicle Routing Problem，VRP）的研究提供了廣泛的現(xiàn)實背景，同時通信和信息處理技術(shù)以及計算機硬件技術(shù)的飛速發(fā)展，能夠快速獲取和處理實時信息，為動態(tài)車輛調(diào)度問題的研究創(chuàng)造了條件。隨著對VRP研究的深入，以往靜態(tài)VRP的模型和算法僅能處理預(yù)先確定的信息，難以滿足現(xiàn)實中處理各種動態(tài)信息的需求，有必要研究包含動態(tài)信息的VRP，建立符合物流配送實際的動態(tài)車輛路徑問題（Dynamic Ve

2、hicle Routing Problem，DVRP）的模型和算法。DVRP己成為現(xiàn)階段車輛路徑問題研究的熱點，通過對車輛路徑進(jìn)行實時動態(tài)調(diào)度，有助于提高企業(yè)物流配送服務(wù)水平，增強企業(yè)競爭力，具有較強的現(xiàn)實意義；同時對該問題的研究還能豐富和充實物流科學(xué)、運籌學(xué)及組合優(yōu)化等研究領(lǐng)域，還具有較強的理論意義。
　　 本文在國家自然科學(xué)基金項目“面向物流配送的動態(tài)車輛調(diào)度模型和混合量子進(jìn)化算法（N0.60970021）”的資助下，針對物

3、流配送動態(tài)需求車輛調(diào)度中的幾類典型問題，在分析其理論和實踐背景的基礎(chǔ)上，建立了多車型開放式、基于沿途補貨的多配送中心、具有模糊預(yù)約時間窗的多目標(biāo)以及具有隨機信息的動態(tài)需求VRP模型；研究了混合量子進(jìn)化算法對上述模型的求解。本文的主要工作和成果如下：
　　 1.首先闡述了課題的研究背景及意義，給出了動態(tài)車輛路徑問題的定義和分類，分析了動態(tài)需求車輛路徑問題的構(gòu)成要素，在對國內(nèi)外大量文獻(xiàn)總結(jié)提煉的基礎(chǔ)上，從模型和求解方法兩方面深入分析

4、其研究現(xiàn)狀，針對目前研究中存在的問題以及我國物流配送車輛調(diào)度的特點，提出了論文的主要研究內(nèi)容和組織結(jié)構(gòu)。
　　 2.分析了已有研究關(guān)于每種車型車輛數(shù)目固定的多車型VRP的不足，引入虛擬配送中心，建立了動態(tài)需求多車型開放式VRP的兩階段數(shù)學(xué)規(guī)劃模型；制定了相應(yīng)的“預(yù)優(yōu)化路線的制定十實時動態(tài)優(yōu)化調(diào)度”兩階段求解策略；提出混合2-OPT量子進(jìn)化算法進(jìn)行求解，引入2-OPT局部優(yōu)化方法來優(yōu)化子路徑能減少客戶序列的交叉從而提高了算法的收斂

5、速度；設(shè)計了一種將常用的基于整數(shù)的編碼引入到量子比特的編碼方法，從而解決了車輛路徑問題不能直接運用量子進(jìn)化算法求解的矛盾；最后，基于標(biāo)準(zhǔn)測試問題進(jìn)行實驗仿真分析，并與最鄰近插入法的結(jié)果進(jìn)行比較，實驗結(jié)果表明了模型的正確性和算法求解動態(tài)需求車輛路徑問題的有效性，該混合2-OPT量子進(jìn)化算法能滿足調(diào)度的實時性要求。
　　 3.分析了已有研究對于沿途補貨策略局限于靜態(tài)問題的不足，引入顧客需求的動態(tài)性，提出了基于沿途補貨的動態(tài)需求多配送

6、中心VRP，建立其模型；設(shè)計了一種最鄰近法則來控制車輛補貨的解碼方法；提出了自適應(yīng)免疫量子進(jìn)化算法進(jìn)行求解，引入免疫算子進(jìn)行線路內(nèi)和線路間再優(yōu)化，從關(guān)于問題的先驗知識中提取疫苗，有效的加快了算法的收斂速度，提高解的質(zhì)量，同時為適應(yīng)動態(tài)調(diào)度對算法有較高實時性的要求，在疫苗接種的過程中設(shè)計了一種隨個體適應(yīng)度大小而變化的自適應(yīng)選擇概率，從而減少了算法的運行時間；最后，對實例進(jìn)行了仿真測試，分析了疫苗接種方式以及沿途補貨策略對結(jié)果的影響，并與最

7、鄰近插入法進(jìn)行了比較，實驗結(jié)果表明沿途補貨策略適應(yīng)于動態(tài)需求車輛路徑問題，所提的算法能有效能滿足調(diào)度的實時性要求。
　　 4.提出了一種更符合實際情況的模糊預(yù)約時間窗，通過該模糊預(yù)約時間窗來表示客戶滿意度，該模糊預(yù)約時間窗可區(qū)別對待提前客戶和延期客戶的滿意度，彌補了已有研究同等看待的不足。將最大化的客戶滿意度和最小化的運行成本作為目標(biāo)，建立了多目標(biāo)動態(tài)需求車輛路徑問題的模型；提出自適應(yīng)網(wǎng)格多目標(biāo)量子進(jìn)化算法進(jìn)行求解，在算法中設(shè)計

8、了一種自適應(yīng)網(wǎng)格保持解集多樣性的方法，每一代中網(wǎng)格的數(shù)量不固定，而是根據(jù)當(dāng)前代非劣最優(yōu)解集的分布情況自適應(yīng)調(diào)整，采用擂臺賽法則構(gòu)造非支配解集；最后通過實驗分析對比，分析了算法參數(shù)對于結(jié)果的影響，選擇適合問題的參數(shù)對標(biāo)準(zhǔn)測試實例進(jìn)行了實驗仿真，結(jié)果表明了模型的正確性和所提算法求解多目標(biāo)動態(tài)問題的有效性。
　　 5.分析了Lars M.H的動態(tài)隨機需求VRP模型，該模型將表示顧客數(shù)量的隨機變量設(shè)為確定值，并假設(shè)在某時刻t隨機需求的信

9、息變?yōu)橐阎?，從而隨機數(shù)變?yōu)榇_定值。針對其模型的不足，本章研究在時刻t客戶是否有需求能確定，但需求量服從參數(shù)為λ泊松分布的動態(tài)隨機問題，并在Lars M.H建立的模型的基礎(chǔ)上考慮多配送中心，開放式的特點，建立了動態(tài)隨機問題的基于補償策略的兩階段隨機規(guī)劃模型；設(shè)計的自適應(yīng)免疫量子進(jìn)化算法有效加快算法的收斂速度，提高解的質(zhì)量；最后，對實例進(jìn)行測試仿真，分析了參數(shù)λ取不同值時的優(yōu)化結(jié)果，并與基本量子進(jìn)化算法和最鄰近插入法進(jìn)行了比較，實驗結(jié)果表明