黃玉文

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

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

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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

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

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

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

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

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

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

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

2.1 編碼方式

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

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

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

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

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

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

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

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

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

3 算法驗(yàn)證

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

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

4 結(jié)論

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

參考文獻(xiàn)：

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

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

[3] 孫麗君. 基于暢通可靠性分析的城市物流配送網(wǎng)絡(luò)優(yōu)化研究[D]. 長(zhǎng)沙： 長(zhǎng)沙理工大學(xué)， 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.