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

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

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

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

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

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

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

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

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

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