基于沿途補(bǔ)貨的多配送中心動態(tài)需求VRP建模及優(yōu)化

張景玲，王萬良，趙燕偉

（1．浙江工業(yè)大學(xué) 特種裝備制造與先進(jìn)加工技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，浙江 杭州 310012；2．浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州 310012）

0 引言

根據(jù)配送系統(tǒng)中配送中心數(shù)目的多少，車輛路徑問題［1］（Vehicle Routing Problem，VRP）有單配送中心和多配送中心之分?，F(xiàn)有研究主要集中在單配送中心問題上，多配送中心問題國內(nèi)近幾年才有研究。對于多配送中心VRP，不能簡單地直接使用單配送中心路徑的思路和方法，必須在深入研究其特點(diǎn)的基礎(chǔ)上，選擇合適的方法進(jìn)行求解。

多配送中心VRP的求解目前主要有兩種方法：

（1）將多配送中心VRP轉(zhuǎn)化為多個單配送中心VRP，然后進(jìn)行優(yōu)化組合，該方法的研究重點(diǎn)在多配送中心的分離策略和最后解的優(yōu)化組合方案選擇上，但是較難確定合適的分區(qū)方案，從而比較容易使問題限于局部最優(yōu)。文獻(xiàn)［2］研究了多車型取送混合的多配送中心VRP；文獻(xiàn)［3］結(jié)合Sweep算法和Saving算法，給出了多車場轉(zhuǎn)化為單車場的處理方法，但沒有給出分解點(diǎn)δ的設(shè)定標(biāo)準(zhǔn)，且分配的結(jié)果并不十分理想。

（2）將多配送中心VRP本身看作一個復(fù)雜的組合優(yōu)化問題進(jìn)行研究，該方法的研究重點(diǎn)集中在如何合理地縮小搜索空間和簡化求解步驟上，對算法的要求比較高。文獻(xiàn)［4］考慮車輛最大行駛距離的約束條件，建立多車場滿載條件下的協(xié)同運(yùn)輸問題的數(shù)學(xué)模型，設(shè)計(jì)了基于貪婪算法的兩階段啟發(fā)式算法；文獻(xiàn)［5］研究了以最快完成為目標(biāo)的多車場多車型VRP的變異蟻群算法；文獻(xiàn)［6］研究了基于并行蟻群算法的多配送中心VRP；文獻(xiàn)［7］提出一種基于啟發(fā)式的整數(shù)規(guī)劃方法來求解多配送中心VRP，取得了較好的結(jié)果；李延輝和劉向［8］采用第（2）種方法研究了基于沿途補(bǔ)貨策略的開放式VRP，并提出了帶補(bǔ)貨控制因子的蟻群算法用于求解該問題，但是蟻群算法是基于單點(diǎn)搜索的算法，常常搜索的時間較長，且容易出現(xiàn)停滯現(xiàn)象。

已有文獻(xiàn)對多配送中心問題的研究大多在靜態(tài)環(huán)境下進(jìn)行，與車輛調(diào)度相關(guān)的信息在路徑規(guī)劃之前已知，輸出是一條預(yù)先規(guī)劃好的路線；然而現(xiàn)實(shí)中在路徑規(guī)劃前，這些信息并不能完全已知，這類問題稱為動態(tài)VRP，其輸出路線隨信息的變化動態(tài)調(diào)整。文獻(xiàn)［9］將動態(tài)VRP轉(zhuǎn)化為一系列靜態(tài)子問題，提出了改進(jìn)的遺傳算法（Genetic Algorithm，GA）進(jìn)行求解，并與禁忌搜索、蟻群系統(tǒng)進(jìn)行比較，說明了算法的有效性；文獻(xiàn)［10］研究了多期動態(tài)VRP，提出三階段滾動時域啟發(fā)式算法解決該問題，計(jì)算結(jié)果表明，該方法可以產(chǎn)生合理運(yùn)行時間內(nèi)的高質(zhì)量解決方案；文獻(xiàn)［11］研究了具有實(shí)時顧客需求和動態(tài)網(wǎng)絡(luò)的VRP，建立了對應(yīng)動態(tài)環(huán)境的靜態(tài)轉(zhuǎn)換模型，提出一種能同時利用演化算法全局優(yōu)化能力和蟻群算法局部搜索能力的混合智能優(yōu)化算法（Intelligent Optimized Algorithm，IOA），取得了較好的實(shí)驗(yàn)結(jié)果；文獻(xiàn)［12］提出一種改進(jìn)的大領(lǐng)域搜索算法求解有時間窗的動態(tài)VRP，通過事件觸發(fā)將動態(tài)調(diào)度轉(zhuǎn)換為一系列靜態(tài)子問題進(jìn)行求解，所提算法能快速獲得問題的解；文獻(xiàn)［13］綜述了動態(tài)取送貨VRP的架構(gòu)及求解策略，指出動態(tài)VRP的兩種優(yōu)化策略——重優(yōu)化策略和局部優(yōu)化策略。

本文考慮顧客需求的動態(tài)性，在文獻(xiàn)［8］的研究基礎(chǔ)上提出了基于沿途補(bǔ)貨策略的多配送中心動態(tài)需求VRP。通過將計(jì)劃周期分片，將動態(tài)調(diào)度問題按照時間軸依次分解為一系列的靜態(tài)調(diào)度子問題，建立了該問題基于時間軸的多階段數(shù)學(xué)規(guī)劃模型，為方便問題的描述，采用一個兩階段的模型來體現(xiàn)：第一階段根據(jù)已知客戶信息建立預(yù)優(yōu)化模型；第二階段加入顧客實(shí)時信息，引入虛擬配送中心的概念，建立重調(diào)度模型。多階段的模型是在第二階段模型上進(jìn)行的擴(kuò)展。對多配送中心問題，本文采用第二種方法求解，將其看作一個配送路徑跨區(qū)域的組合優(yōu)化問題。鑒于量子進(jìn)化算法［14］求解效率高、收斂速度快、全局尋優(yōu)能力強(qiáng)等性能，本文將其引入動態(tài)VRP的求解，提出了自適應(yīng)免疫量子進(jìn)化算法，并設(shè)計(jì)了最鄰近法結(jié)合貪婪規(guī)則的沿途補(bǔ)貨策略。

1 多配送中心動態(tài)需求VRP數(shù)學(xué)規(guī)劃模型

1．1 問題描述

沿途補(bǔ)貨的多配送中心動態(tài)需求VRP描述為：有M個車場，各自擁有容量為bk的車輛Km（m＝1，2，…，M）輛，對L個用戶進(jìn)行貨物配送，用戶i的貨物需求為di（i＝1，2，…，L），di＜bk，每個用戶可由任何一個車場的車輛服務(wù)，但只能由一輛車服務(wù)一次，每輛車完成任務(wù)后無須返回原車場。在服務(wù)的過程中，存在客戶需求的動態(tài)變化：考慮新客戶的出現(xiàn)及原有客戶需求量的變化。

（1）沿途補(bǔ)貨策略 從任一配送中心始發(fā)的貨車可在途經(jīng)的多個配送中心補(bǔ)充貨物，并對整個聯(lián)合區(qū)域內(nèi)的缺貨需求點(diǎn)進(jìn)行貨物供給。當(dāng)車載貨物配送完或即將配送完，即無法為下一客戶配送貨物時進(jìn)行補(bǔ)貨。

（2）目標(biāo) 要求一個合適的車輛調(diào)度方案，能夠滿足所有用戶的需求，并使車輛總的運(yùn)輸成本最低。針對動態(tài)調(diào)度問題，本文建立了兩階段數(shù)學(xué)模型：第一階段為預(yù)優(yōu)化模型；第二階段為重調(diào)度模型。

1．2 數(shù)學(xué)規(guī)劃模型

（1）第一階段預(yù)優(yōu)化模型

用戶編號為1，2，…，L；配送中心編號為L＋1，L＋2，…，L＋M；Fk為發(fā)車的固定費(fèi)用，k∈｛1，2，…，Km｝，m∈｛L＋1，L＋2，…，L＋M｝；cij為從i地到j(luò)地的運(yùn)輸成本，i，j∈（1，2，…，L，L＋1，…，L＋M），當(dāng)i，j同時為車場時cij＝∞，即禁止從車場到車場；ωmijk為配送中心m的車輛k從i地到j(luò)地的運(yùn)輸量，i，j∈（1，2，…，L，L＋1，…，L＋M），m∈｛L＋1，L＋2，…，L＋M｝，k∈｛1，2，…，Km｝。

定義決策變量：

則沿途補(bǔ)貨的多配送中心動態(tài)需求VRP數(shù)學(xué)模型表示如下：

目標(biāo)函數(shù)：

其中：式（2）保證車輛的容量限制；式（3）表示各配送中心派出的車輛數(shù)不超過該車場所擁有的車輛數(shù)；式（4）～式（5）保證每個客戶僅被一輛車訪問；式（6）表示從配送中心出發(fā)的貨車的運(yùn)輸量為貨車的載量，即滿載出發(fā)，它是式（7）～式（9）的初始條件；式（7）表示進(jìn)入任一客戶之前，貨車有足夠供給這個客戶的貨物；式（8）表示貨車經(jīng)過客戶點(diǎn)j后運(yùn)輸量發(fā)生改變的關(guān)系式；式（9）表示貨車現(xiàn)有運(yùn)輸量無法為下一需求點(diǎn)配送貨物時進(jìn)入倉庫補(bǔ)貨。

（2）第二階段重調(diào)度模型

在第二階段的開始調(diào)度時刻，預(yù)優(yōu)化階段調(diào)度的車輛因?yàn)轳傠x配送中心，已服務(wù)了部分客戶，車輛的剩余載重量變得不相同，并且由于車輛位于客戶處，直接調(diào)度將無法進(jìn)行，本文引入虛擬配送中心的概念，將車輛所在的客戶點(diǎn)設(shè)為虛擬配送中心，建立如下的多配送中心多車型VRP模型。

N表示第一階段未服務(wù)客戶與第二階段新客戶的總數(shù)量，假設(shè)第一階段派出車輛數(shù)為Hm，派出車輛的剩余車載量為bmh（m＝1，2，…，M，h＝1，2，…，Hm），則用Hm表示虛擬配送中心數(shù)量，虛擬配送中心編號為N＋M＋1，N＋M＋2，…，N＋M＋H，原配送中心編號為N＋1，N＋2，…N＋M，新派車Tm輛。

目標(biāo)函數(shù)：

式（10）包括三部分：①第一階段派出車輛對第一階段未服務(wù)客戶和第二階段新客戶的運(yùn)輸成本；②第二階段新派出車輛的運(yùn)輸成本；③第二階段新派出車輛的發(fā)車成本。

2 多配送中心動態(tài)需求VRP的自適應(yīng)免疫量子進(jìn)化算法

2．1 自適應(yīng)免疫量子進(jìn)化算法設(shè)計(jì)

量子進(jìn)化算法在進(jìn)化的同時不可避免地會出現(xiàn)退化的現(xiàn)象，引入免疫算子進(jìn)行線路內(nèi)（同一個車輛路徑中）和線路間（不同車輛路徑中）的再優(yōu)化，在算法中加入對問題的先驗(yàn)知識能有效地加快算法的收斂速度，提高解的質(zhì)量。具體操作如下：

（1）提取疫苗 根據(jù)問題的特征信息提取，對于VRP，根據(jù)最鄰近法則選擇離節(jié)點(diǎn)最近的點(diǎn)作為該節(jié)點(diǎn)的疫苗，從而得到各節(jié)點(diǎn)的疫苗矩陣。

（2）免疫算子

1）疫苗接種 疫苗接種是染色體基因的調(diào)整過程，根據(jù)選取的疫苗局部調(diào)整染色體基因順序，實(shí)現(xiàn)線路內(nèi)和線路間路線的調(diào)整。以一定的概率選擇染色體，將接受檢查的基因點(diǎn)的后繼點(diǎn)與疫苗點(diǎn)的位置進(jìn)行交換，當(dāng)后繼點(diǎn)為疫苗點(diǎn)時不接種，如下例所示。其中加粗的數(shù)字表示接種疫苗的節(jié)點(diǎn)，加陰影的數(shù)字表示該點(diǎn)的疫苗。

在提取疫苗時，可能存在不同節(jié)點(diǎn)對應(yīng)同一個疫苗的情況，因此在疫苗接種的過程中有可能出現(xiàn)疫苗點(diǎn)在該點(diǎn)前面的情況，此時不接種，繼續(xù)下一點(diǎn)。如下例所示。

2）自適應(yīng)接種 在量子進(jìn)化算法中混合免疫算子可以提高量子進(jìn)化算法的局部搜索能力，但是也需要更多的局部搜索時間，從而增大了算法的時間開銷，這對于動態(tài)調(diào)度是不適合的。因此為減少算法的運(yùn)行時間，不對所有的個體接種疫苗，而是根據(jù)個體適應(yīng)度的高低進(jìn)行有選擇地接種，適應(yīng)度高的個體接種的概率大，適應(yīng)度低的個體則接種的概率小。本文設(shè)計(jì)了一種隨個體適應(yīng)度大小而變化的自適應(yīng)選擇概率pl，

以概率pl選擇個體xl進(jìn)行疫苗接種，f（xl）為個體xl的適應(yīng)度，l表示種群的大小。

3）免疫選擇 選出最優(yōu)個體，當(dāng)該個體比父代最優(yōu)個體更優(yōu)時選用該個體；當(dāng)其比父代劣時，說明免疫操作沒有起到作用，選用父代最優(yōu)個體。

2．2 自適應(yīng)免疫量子進(jìn)化算法流程

針對上述建立的動態(tài)需求VRP的兩階段數(shù)學(xué)規(guī)劃模型，采用“預(yù)優(yōu)化路線的制定＋動態(tài)優(yōu)化調(diào)整”的兩階段求解策略［15］，分別采用自適應(yīng)免疫量子進(jìn)化算法（Adaptive Immune Quantum－inspired Evolutionary Algorithm，AIQEA）進(jìn)行求解，具體步驟如圖1所示。在重調(diào)度階段解碼時先派第一階段的車輛，若第一階段車輛無法滿足，則啟用新車。

算法的主要操作：

（1）基于問題特征的編碼 采用基于客戶序列的編碼方法［15］。

（2）初始化種群 隨機(jī)產(chǎn)生擁有多個染色體的初始種群，根據(jù)上述編碼方案，染色體就是L組且每組都包含n個量子比特的串。量子比特各位采用隨機(jī)初始化，即αi和βi均為由計(jì)算機(jī)隨機(jī)產(chǎn)生0，1之間的任何數(shù)。

（3）基于沿途補(bǔ)貨策略的解碼 解碼過程采取“先客戶，再配送中心”的兩步走方法：

步驟1 產(chǎn)生客戶服務(wù)的先后序列。

步驟2 形成配送路徑。對于沿途補(bǔ)貨的VRP，設(shè)計(jì)了一種基于最鄰近法結(jié)合貪婪規(guī)則的補(bǔ)貨策略：首先按客戶序列表順序服務(wù)客戶，利用最鄰近法則尋找離當(dāng)前客戶點(diǎn)最近的配送中心作為實(shí)際發(fā)車的配送中心或沿途補(bǔ)貨的配送中心；其次結(jié)合貪婪規(guī)則判斷是否需要補(bǔ)貨，如果前一點(diǎn)到其最近配送中心的距離加該點(diǎn)到其最近配送中心的距離之和小于該點(diǎn)到其最近配送中心的距離加固定發(fā)車成本之和，說明補(bǔ)貨的費(fèi)用低，則到最近的配送中心補(bǔ)貨，否則重新派一輛車，若所需車輛數(shù)超過已有車輛數(shù)，則該路徑為不可行解。例如對于一個有11個客戶、3個配送中心的問題，解碼方法具體如下：

以數(shù)字“0”表示補(bǔ)貨的配送中心，如上形成路線：12—6—10—2—14—0—5—13—9—4—8—13—0—3—11—12—0—7—1。其中14—0表示配送中心14作為一次補(bǔ)貨點(diǎn)，同樣13—0，12—0中配送中心13，12也是補(bǔ)貨點(diǎn)。

（4）適應(yīng)度計(jì)算 對種群中的各個染色體解碼后，分別根據(jù)第一階段式（1）和第二階段式（10）求得目標(biāo)函數(shù)值Z；若染色體對應(yīng)不可行解，則賦予Z一個很大的整數(shù)。令染色體的適應(yīng)度函數(shù)為Fitness＝1／Z。

（5）量子旋轉(zhuǎn)門更新 在量子進(jìn)化算法中，量子門是最終實(shí)現(xiàn)進(jìn)化操作的執(zhí)行機(jī)構(gòu)，最常用的為量子旋轉(zhuǎn)門，進(jìn)化過程由量子旋轉(zhuǎn)門更新量子位概率幅來實(shí)現(xiàn)，具體可參見文獻(xiàn)［16］。

3 實(shí)驗(yàn)結(jié)果與分析

3．1 實(shí)例測試

本文所有程序采用Java語言編寫，在Pentium?D CPU 2．8GHz，1．0GB的內(nèi)存上運(yùn)行。某物流配送公司實(shí)際的配送過程可歸結(jié)為開放式、帶容量約束、多配送中心的動態(tài)需求VRP，在配送的過程中，可就近在公司的其他分配送中心補(bǔ)貨。該物流系統(tǒng)擁有4個配送中心，車載量為8t，初始客戶數(shù)為50個，各客戶點(diǎn)的坐標(biāo)和需求如表1所示，表中1～50為客戶點(diǎn)編號，51～54為配送中心編號。

表1 初始客戶點(diǎn)信息

首先對初始客戶點(diǎn)運(yùn)用自適應(yīng)免疫量子進(jìn)化算法進(jìn)行求解，結(jié)果如表2所示。在表2中，如果配送中心后面有0，則表示該配送中心為補(bǔ)貨的配送中心。自適應(yīng)免疫量子進(jìn)化算法在預(yù)優(yōu)化階段的收斂曲線如圖2所示。

在時刻15更新客戶需求信息，此時有10個新客戶提出服務(wù)請求，其坐標(biāo)和需求分別為a（12，43，2．3），b（16，4，1．4），c（21，61，1．2），d（58，74，0．4），e（55，40，1．4），f（62，74，2．0），g（12，75，1．6），h（25，58，2．4），i（77，50，1．2），j（32，68，1．1）。

由計(jì)算結(jié)果可知，此時配送中心已發(fā)出5輛車，分別位于點(diǎn)46（32，39），43（5，64），37（32，22），20（57，58），21（62，42），車輛的剩余載重量分別為0．7 t，4．2t，2．2t，5．2t，1．3t?？蛻酎c(diǎn)38，11，32，1，27，46，48，24，43，41，19，42，37，20，49，10，9，50，16 已服務(wù)。在重調(diào)度階段，除去已服務(wù)客戶點(diǎn)，未服務(wù)客戶點(diǎn)和新需求點(diǎn)共40個，將此時車輛所在的點(diǎn)設(shè)為虛擬配送中心，原配送中心依然對客戶服務(wù)，根據(jù)上文建立的第二階段模型運(yùn)用混合量子進(jìn)化算法進(jìn)行求解，迭代次數(shù)為2 000次，種群大小為50，計(jì)算結(jié)果如表3所示?？梢钥闯觯瑢τ谛录尤氲目蛻酎c(diǎn)，虛擬配送中心的車輛不僅將車上原有的貨物配送完，而且參與第二階段的補(bǔ)貨。重調(diào)度階段的收斂曲線如圖3所示。

表2 初始客戶優(yōu)化路線

表3 重新優(yōu)化路線

3．2 優(yōu)化性能實(shí)驗(yàn)及分析

動態(tài)需求的多配送中心VRP缺少標(biāo)準(zhǔn)的測試實(shí)例庫，研究者隨機(jī)生成或在已有實(shí)例的基礎(chǔ)上進(jìn)行修改。本文預(yù)優(yōu)化階段測試實(shí)例的數(shù)據(jù)來自標(biāo)準(zhǔn)的多配送中心的實(shí)例庫，所有實(shí)例可以從http：／／neo．lcc．uma．es／radi－aeb／WebVRP／上下載，p02（50，4）表示4個配送中心對50個客戶進(jìn)行配送服務(wù)。所選實(shí)例中客戶點(diǎn)的數(shù)量從50～100，配送中心的數(shù)量也隨之改變，分別代表不同類型的問題。實(shí)時優(yōu)化階段客戶信息隨機(jī)生成。第一階段的優(yōu)化結(jié)果如表4所示，圖4是算法的收斂曲線圖。

表4 初始客戶優(yōu)化路線

時刻15更新客戶信息，由計(jì)算結(jié)果可知此時已完成和未完成的路線如表4所示，表中有陰影的數(shù)字表示重調(diào)度階段的虛擬配送中心，位于該點(diǎn)前面的點(diǎn)為已經(jīng)服務(wù)的客戶點(diǎn)，之后的點(diǎn)為還未服務(wù)的點(diǎn)，括號中加字符邊框的點(diǎn)表示該路線上車輛的剩余車載量。

重調(diào)度階段，客戶需求信息隨機(jī)生成，隨機(jī)生成客戶坐標(biāo)和需求量，優(yōu)化結(jié)果如表5所示，圖5是第二階段自適應(yīng)免疫量子進(jìn)化算法的收斂曲線圖。

表5 重新優(yōu)化路線

為了更好地檢驗(yàn)算法的性能，從小、中、大規(guī)模分別對5個經(jīng)典的實(shí)例進(jìn)行了測試，每個測試實(shí)例均隨機(jī)運(yùn)行40次，其最優(yōu)解、均值、標(biāo)準(zhǔn)方差和計(jì)算時間的統(tǒng)計(jì)結(jié)果如表6所示。從表6可以看出，求得的平均值接近最優(yōu)值，算法的優(yōu)化性能較好，標(biāo)準(zhǔn)方差相對平均值較小，算法的穩(wěn)定性能較好。圖6和圖7分別為兩個階段算法的收斂曲線圖。

用Xk表示自適應(yīng)免疫量子進(jìn)化算法第k次迭代時的狀態(tài)。由算法的迭代過程可知，k＋1時刻的狀態(tài)Xk＋1取決于Xk，與以前的狀態(tài)無關(guān)?？梢杂谬R次Markov鏈描述整個迭代過程，自適應(yīng)免疫量子進(jìn)化算法伴隨的馬氏過程能夠收斂到問題的最優(yōu)解。

表6 算法結(jié)果統(tǒng)計(jì)

3．3 沿途補(bǔ)貨策略分析

對于多配送中心的VRP，本文采用沿途補(bǔ)貨的策略，當(dāng)配送車輛裝載的貨物無法為下一個配送點(diǎn)服務(wù)，即車上的裝載貨物已配送完或即將配送完時，車輛進(jìn)入配送中心補(bǔ)貨。采用此策略可減少實(shí)際使用的車輛數(shù)，降低發(fā)車成本，特別是在有動態(tài)需求的情況下，當(dāng)新的需求點(diǎn)插入，配送車輛剩余載貨量小于該新需求點(diǎn)的需求量時，就可以到就近的配送中心補(bǔ)貨，而無需從配送中心新派一輛車，表7所示為沿途補(bǔ)貨策略和基于大范圍統(tǒng)一調(diào)度策略的結(jié)果比較。從表7可以看出，采用沿途補(bǔ)貨策略比基于大范圍統(tǒng)一調(diào)度策略所需的車輛數(shù)少，降低了配送中心的固定成本。

3．4 算法比較分析

對于沿途補(bǔ)貨的動態(tài)需求VRP，目前尚不能找到類似的算例與算法進(jìn)行直接比較，為了比較算法的性能，在重調(diào)度階段分別采用本文所提的AIQEA與最鄰近插入法，以及文獻(xiàn)［9］中的遺傳算法相比較。最鄰近插入法采用局部優(yōu)化策略，將新的客戶需求就近插入預(yù)優(yōu)化的路線中，文獻(xiàn)［9］中的遺傳算法對動態(tài)問題的求解取得了較好的優(yōu)化結(jié)果，計(jì)算時選用的參數(shù)與文獻(xiàn)相同。

表7 沿途補(bǔ)貨策略和基于大范圍統(tǒng)一調(diào)度策略比較

表8所示為優(yōu)化結(jié)果和優(yōu)化時間的對比。可以看出，本文采用的AIQEA能更好地求得問題的解，與最鄰近插入法相比，AIQEA能對第二階段的客戶進(jìn)行全局求解，從而獲得成本更低的調(diào)度方案，雖然比最鄰近插入法求解的速度慢，但能滿足動態(tài)問題的時間要求。相比動態(tài)車輛路徑問題的遺傳算法（Dynamic Vehicle Routing Problem－Genetic Algorithm，DVRP－GA），本文算法除問題P11（249，5）外，其他結(jié)果均較優(yōu)。

表8 算法結(jié)果比較

4 結(jié)束語

本文針對多配送中心動態(tài)需求VRP，在已有文獻(xiàn)提出的基于沿途補(bǔ)貨策略的靜態(tài)模型基礎(chǔ)上，考慮顧客需求的動態(tài)性，進(jìn)一步探討該策略在動態(tài)環(huán)境下的適用性，首次提出了基于沿途補(bǔ)貨策略的多配送中心動態(tài)需求VRP，并建立了該問題的兩階段的數(shù)學(xué)規(guī)劃模型。對于沿途補(bǔ)貨策略，設(shè)計(jì)了一種最鄰近法則來控制車輛補(bǔ)貨的解碼方法，可減少配送中心所使用的車輛數(shù)，從而可降低配送中心的運(yùn)行成本；并設(shè)計(jì)了一種自適應(yīng)免疫量子進(jìn)化算法，在量子進(jìn)化算法中引入免疫算子進(jìn)行線路內(nèi)和線路間的再優(yōu)化，從關(guān)于問題的先驗(yàn)知識中提取疫苗，充分利用了問題的先驗(yàn)知識，有效地加快了算法的收斂速度，提高了解的質(zhì)量，同時為適應(yīng)動態(tài)調(diào)度對算法實(shí)時性要求較高的特點(diǎn)，在疫苗接種的過程中設(shè)計(jì)了一種隨個體適應(yīng)度大小而變化的自適應(yīng)選擇概率，適應(yīng)度高的個體接種的概率大，適應(yīng)度低的個體則接種概率小，從而減少了算法的運(yùn)行時間。最后，對實(shí)例進(jìn)行了仿真測試，并與其他的算法進(jìn)行了比較，實(shí)驗(yàn)結(jié)果表明該方法能有效地求解動態(tài)需求VRP。然而，動態(tài)VRP的研究還包括車輛的動態(tài)性和路網(wǎng)的動態(tài)性，如何綜合考慮多種動態(tài)因素有待于進(jìn)一步研究。

［1］DANTZIG G B，RAMSER J H．The truck dispatching problem ［J］．Management Science，1959，4（6）：80－91．

［2］IRNICH S．A multi－depot pickup and delivery problem with a single hub and heterogeneous vehicles［J］．European Journal of Operational Research，2000，122（2）：310－328．

［3］LI Jun，GUO Yaohuang．Theory and methods for vehicle scheduling on logistics distribution［M］．Beijing：China Supplies Press，2011（in Chinese）．［李 軍，郭耀煌．物流配送車輛優(yōu)化調(diào)度理論與方法［M］．北京：中國物資出版社，2001．］

［4］LIU Ran，JIANG Zhibin，CHEN Feng，et al．Full－load multidepot collaborative transportation problem：models and algo－rithms［J］．Journal of Shanghai Jiaotong University，2009，43（3）：455－459（in Chinese）．［劉 冉，江志斌，陳 峰，等．多車場滿載協(xié)同運(yùn)輸問題模型與算法［J］．上海交通大學(xué)學(xué)報(bào)，2009，43（3）：455－459．］

［5］MA Jianhua，F(xiàn)ANG Yong，YUAN Jie．Mutation ant colony algorithm for multiple－depot multiple－types vehicle routing problems with shortesr finish time［J］．Systems Engineering—Theory ＆Practice，2011，31（8）：1508－1516（in Chinese）．［馬建華，房 勇，袁 杰．多車場多車型最快完成車輛路徑問題的變異蟻群算法［J］．系統(tǒng)工程理論與實(shí)踐，2011，31（8）：1508－1516．］

［6］YU Bin，YANG Zhongzhen，XIE Jingxin．A parallel improved ant colony optimization for multi－depot vehicle routing problem［J］．Journal of the Operational Research Society，2011，62（1）：183－188．

［7］DAMON G，BRUCE G，EDWARD W．The multi－depot split delivery vehicle routing problem：an integer programmingbased heuristic，new test problems，and computational results［J］．Computers and Industrial Engineering，2011，61（3）：794－804．

［8］LI Yanhui，LIU Xiang．Modeling and its ant colony algorithm for multi－depot open vehicle routing problem with replenishment on the way［J］．Computer Integrated Manufacturing Systems，2008，14（3）：260－265（in Chinese）．［李延輝，劉 向．沿途補(bǔ)貨的多車場開放式車輛路徑問題及蟻群算法［J］．計(jì)算機(jī)集成制造系統(tǒng)，2008，14（3）：260－265．］

［9］HANSHAR F T，OMBUKI－BERMAN B M．Dynamic vehicle routing using genetic algorithms ［J］．Applied Intelligence，2007，27（1）：89－99．

［10］WEN Min，CORDEAU J F，LAPORTE G，et al．The dynamic multi－period vehicle routing problem［J］．Computers ＆Operations Research，2010，37（9）：1615－1623．

［11］WANG Jiangqing，ZHU Rongbo．Efficient intelligent optimized algorithm for dynamic vehicle routing problem［J］．Journal of Software，2011，6（11）：2201－2208．

［12］HONG Lianxi．An improved LNS algorithm for real－time vehicle routing problem with time windows［J］．Computers ＆Operations Research，2012，39（2）：151－163．

［13］BERBEGLIA G，CORDEAU J F，LAPORTE G．Dynamic pickup and delivery problems［J］．European Journal of Operational Research，2010，202（1）：8－15．

［14］HAN K H，KIM J H．Quantum－inspired evolutionary algorithm for a class of combinatorial optimization ［J］．IEEE Transactions on Evolutionary Computation，2002，6（6）：580－593．

［15］ZHANG Jingling，ZHAO Yanwei，WANG Haiyan，et al．Modeling and algorithms for a dynamic multi－vehicle routing problem with customers'dynamic requests［J］．Computer Integrated Manufacturing Systems，2010，16（3）：543－555（in Chinese）．［張景玲，趙燕偉，王海燕，等．多車型動態(tài)需求車輛路徑問題建模及優(yōu)化［J］．計(jì)算機(jī)集成制造系統(tǒng)，2010，16（3）：543－555．］

［16］ZHANG Jingling，ZHAO Yanwei，PENG Dianjun，et al．A hybrid quantum－inspired evolutionary algorithm for capacitated vehicle routing problem ［C］／／Proceedings of Advanced Intelligent Computing Theories and Applications．Berlin，Germany：Springer－Verlag，2008，5226：31－38．