黃玉文

摘要：為了提高多配送中心車輛調(diào)度效率，該文提出了一種基于優(yōu)化蟻群算法的的多配送中心車輛路徑調(diào)度算法。優(yōu)化算法通過對信息素揮發(fā)因子、啟發(fā)式因子，信息素強度初始值的夠造，消除參數(shù)選擇對蟻群算法性能的影響，使其具有較強的全局搜索能力。實驗表明，該文提出的基于優(yōu)化蟻群算法的多配送中心車輛路徑算法比其余算法有更好的實驗效果。

關(guān)鍵詞：蟻群算法，遺傳算法；多配送中心；車輛路徑優(yōu)化

中圖分類號：TP391 文獻標識碼：A 文章編號：1009-3044（2015）15-0190-02

Abstract：In order to improve the the efficiency of the multiple depots vehicle routing， a new method of the improved genetic algorithm for the multiple depots vehicle routing isproposed. The improved algorithm eliminates the influence of the selected parameter by optimizingthe heuristic factor， evaporation factor， initial pheromone distribute， and have the strong globalsearching ability. The experiments demonstrate that the solving results of the improved algorithm is more excellent than the other algorithm

Key words： ant colony algorithm； genetic algorithm； multiple depots； vehicle routingoptimization

當前，隨著電子商務的快速興起，物流業(yè)在市場經(jīng)濟中占有越來越重要的地位，引起國家的高度重視和越來越多的企業(yè)的關(guān)注，物流服務業(yè)在國民經(jīng)濟中的地位越來越重要，黨的十八大明確提出要轉(zhuǎn)變經(jīng)濟結(jié)構(gòu)，鼓勵電子商務和現(xiàn)代物

流行業(yè)的快速發(fā)展[1]。物流業(yè)和信息產(chǎn)業(yè)、運輸產(chǎn)業(yè)、信貸業(yè)務等產(chǎn)業(yè)密切相關(guān)，涉及就業(yè)人員較廣，對生產(chǎn)力的影響較大，在現(xiàn)代市場經(jīng)濟和增強國民經(jīng)濟競爭力中發(fā)揮重要作用。目前對單配送物流企業(yè)的車輛配送路徑的優(yōu)化問題研究的較多，在實際應用中單配送中心的路徑比較成熟，但對多配送中心車輛路徑優(yōu)化的研究還比較少，與我國高速發(fā)展的物流配送業(yè)不相適應。從我國現(xiàn)有物流配送企業(yè)的發(fā)展看，多配送中心的車輛路徑優(yōu)化問題比單配送中心的物流調(diào)度求解更難，計算復雜度更高度，也更具有現(xiàn)實意義，逐漸成為物流調(diào)度中的一個研究熱點問題[2-3]。

1 多配送中心車輛優(yōu)化的數(shù)學模型

在多配送中心車輛優(yōu)化的數(shù)學模型中，所有車場、貨物配送點、客戶等是配送網(wǎng)絡的結(jié)點多配送中心車輛路徑的數(shù)學模型如下。

約束（2）保證起點和終點是相同的，而約束條件（3）和（4）保證所有路徑平行及其不超過客戶數(shù)量。約束條件（5）假定多配送中心沒有分配任務。約束條件（6）確保車輛不超過負載的需求。約束（7）和（8）是路線長度和客戶數(shù)量限制，約束（9）是時間限制。約束（10），（11）和（12）是軟時間窗，和約束（13）是硬時間窗，c和d是懲罰系數(shù)。

2 基于優(yōu)化蟻群算法的多配送中心車輛路徑算法

為了提高收斂效果和全局的搜索能力，本文提出了一種蟻群算法與遺傳算法相融合的混合算法。遺傳算法優(yōu)化蟻群算法的交叉算子和變異算子，每個進化儲備最佳解決方案，加快收斂速度，提高算法的全局的能力。整個算法分兩個階段進行，第一階段引入遺傳算法，利用遺傳算法收斂速度快、全局性等優(yōu)點調(diào)整蟻群算法中初始參數(shù)的分布。第二階段利用第一階段得到的值對蟻群算法進行初始化，執(zhí)行蟻群算法，并在蟻群算法中加入交叉和變異，對多配送中心的車輛路徑進行求解，具體算法步驟執(zhí)行如下：

2.1 編碼方式

本文對對染色體采用[G1，G2，...，GL]的編碼方式，染色體包括起點車場號、車輛編號、順序編號和終點車場號四部分。例如：染色體[SA13BB13AA11BA12BB12AB11A]表示編號為1和編號為2的車輛的行駛路線，其中編號為1的車輛以A為起始車站，以B為終止車站，行駛路線為[A→3→4→1→B]。編號為2的車輛以B為起始站點，以A為終止站點，編號為2的行駛路線為[B→6→5→2→A]。

2.2 基于優(yōu)化蟻群算法的多配送中心車輛路徑算法

步驟1： 利用遺傳算法對蟻群算法參數(shù)[ρ，α，β，Q]進行優(yōu)化。首先對染色體[ρ，α，β，Q]編碼，[0.1≤ρ≤0.99]，[0≤α≤5]，[0.1≤β≤5]，[10≤ρ≤10000]，首先進行初始化種群，然后對適應度函數(shù)進行計算，為了充分考慮蟻群算法求解特性，從求解問題的目標函數(shù)、蟻群算法探索能力和開發(fā)能力 3 個方面來構(gòu)建適應度函數(shù)。然后進行交叉和變異運算，采用正比選擇策略，即每個個體被選中進行遺傳運算的概率為該個體的適應值和群體中所有個體適應值總和的比例。查看是否達到最大迭代次數(shù)，如果沒有達到，繼續(xù)利用遺傳算法對蟻群算法參數(shù)進行優(yōu)化。

步驟2：初始化各個參數(shù)，將m只螞蟻放置在[M+H]個頂點上，如果頂點為車場，則置該車場為該路徑的永久車場，并將除該車場除外的其它車場加入禁忌表；否則將該頂點放置在此螞蟻禁忌表里。當前路徑tour、當前最優(yōu)路徑best_tour、當前路徑的長度tour_length，當前最優(yōu)路徑長度best_length；visited[i] 表示節(jié)點i是否被訪問過，qual表示車輛目前已載貨物重量，隨機選擇一個車場，以變量start_depot表示當前車場編號，賦值變量i=start_depot；

步驟3：選擇下一個節(jié)點 j，若沒找到可用節(jié)點，將邊（i，start_depot）加入當前路徑，若對所有的節(jié)點i（i=1，2， ，N）都有 visited[i]=1，此時螞蟻完成一條完成路徑的搜索，對各邊信息素進行局部更新， k=k+1 ，若所求路徑小于當前路徑 ， 則設(shè)置所求路徑為最優(yōu)路徑，

步驟4：將邊（i，j）加入當前路徑，修改車輛目前已載貨物重量，設(shè)置結(jié)點j被訪問過。

步驟5：更新信息素，若滿足結(jié)束條件，轉(zhuǎn)向step 7，計算最優(yōu)路徑和次優(yōu)路徑值。

步驟6：選出本次循環(huán)中的最優(yōu)路徑和次優(yōu)路徑，并保留最優(yōu)路徑，轉(zhuǎn)向步驟3。

步驟 7：算法結(jié)束。

3 算法驗證

用VC + +6.0來設(shè)計程序，并選擇標準測試集Cordeau算例中的數(shù)據(jù)做為測試數(shù)據(jù)進行實驗，以取得最佳參數(shù)，從而使本文提出的基于優(yōu)化蟻群算法的多配送中心車輛路徑算法（GAACVNS）取得更好的實驗效果。本文GAACVNS算法和TS算法[4]，VNS算法[5]，CNVNS算法[6]的車輛配送路徑的最優(yōu)解比較結(jié)果如表1所示。

從表1可以看出，本文提出的基于優(yōu)化蟻群算法的多配送中心車輛路徑算法比其余算法有更好的實驗效果。

4 結(jié)論

本文給出了多配送中心車輛調(diào)度模型及染色體螞蟻的編碼方法。融合算法消除了所選參數(shù)的影響，融合算法通過對信息素揮發(fā)因子、啟發(fā)式因子，信息素強度初始值的夠造，消除參數(shù)選擇對蟻群算法性能的影響，使其具有較強的全局搜索能力。引入遺傳操中的交叉算子和變異算子，對蟻群算法在每次解過程中的最優(yōu)解和次優(yōu)解進行運算，并對優(yōu)秀解進行保留，對優(yōu)秀解公共解集的保留加快了算法收斂速度，引入交叉和變異擴大了解的搜索空間，提高了解的全局性。

參考文獻：

[1] 張欣鈺. 半開放式多配送中心車輛路徑優(yōu)化問題研究[D]. 大連： 大連海事大學， 2014.

[2] 李保偉. 多配送中心的城市物流配送車輛路徑問題研究[D]. 合肥： 合肥工業(yè)大學， 2013.

[3] 孫麗君. 基于暢通可靠性分析的城市物流配送網(wǎng)絡優(yōu)化研究[D]. 長沙： 長沙理工大學， 2010.

[4] Cordeau J F， Laporte G， Mercier A. An improved Tabu search algorithm for the handling of route du-ration constraints in vehicle routing problems with Time windows[J]. Journal of the Operational Re-search Society， 2004， 55（5）： 542-546.

[5] Polacek M， Hartl R F， Doemer K. A variable neighborhood seareh for the multi-depot vehicle routing problem with time windows[J]. Journal of heuristics， 2004， 10（6）： 613-627.

[6] Polacek M， Benkner S， Doerner K， et al. A cooperative and adaptive variable neighborhood search for the multi-depot vehicle routing problem with timewindows[J]. Business Research Journal， 2008， 1（2）： 207-218.