多物流配送中心選址及求解

李艷冰，徐克林，朱 偉

（同濟(jì)大學(xué) 機(jī)械工程學(xué)院，上海201804）

物流系統(tǒng)中，配送中心是連接物流上下游的樞紐，對(duì)促進(jìn)生產(chǎn)與消費(fèi)的協(xié)調(diào)與配合、保證物流系統(tǒng)的平衡發(fā)展起著重要作用.在各企業(yè)努力降低成本、增加利潤和增強(qiáng)競(jìng)爭(zhēng)力的今天，配送中心的選址問題尤為受人關(guān)注.多配送中心選址問題（multidistribution center location problem，MDLP）的求解具有NP（非確定多項(xiàng)式）難的性質(zhì)，近年來，各種啟發(fā)式 算 法［1－3］和 智 能 算 法［4－5］的 研 究 成 為 該 領(lǐng) 域熱點(diǎn).

蟻群算法采用正反饋并行自催化機(jī)制，具有較強(qiáng)的頑健性及分布計(jì)算能力，容易與其他優(yōu)化算法相融合，尤適于求解復(fù)雜的組合優(yōu)化問題［6］，但因其不能直接求解MDLP等原因，目前蟻群算法在這方面的研究成果不多.為此，通過改變禁忌表設(shè)置方式、改進(jìn)轉(zhuǎn)移規(guī)則、2－opt優(yōu)化及信息素更新等策略，本文提出了改進(jìn)的蟻群算法求解多配送中心選址問題并通過數(shù)值實(shí)驗(yàn)驗(yàn)證了模型和算法的有效性.

1 MDLP模型

多配送中心選址問題可描述為：在給定的P個(gè)候選位置中選擇k個(gè)點(diǎn)，以合理的規(guī)模建立配送中心，服務(wù)l個(gè)客戶點(diǎn)的配送需求.如何選擇k個(gè)位置，使得在滿足客戶需求及配送中心供應(yīng)能力前提下，服務(wù)成本（運(yùn)輸成本、配送中心的可變成本和固定成本之和）最小.

假定每個(gè)客戶點(diǎn)需求只由一個(gè)配送中心服務(wù)，記Ci（1≤i≤p）為中心i的供應(yīng)能力，qj（1≤j≤l）為客戶點(diǎn)j的需求量，duv為網(wǎng)絡(luò)中節(jié)點(diǎn)u到v的距離，ruv是節(jié)點(diǎn)u到v的運(yùn)輸費(fèi)率，Ni是配送中心i服務(wù)的客戶點(diǎn)數(shù)，配送中心i服務(wù)的第j個(gè)客戶記為sji，fi為中心i的固定費(fèi)用，則MDLP模型如下：

其中，式（1）為目標(biāo)函數(shù)，表示系統(tǒng)服務(wù)成本最低；式（2）表示所選配送中心總的服務(wù)能力不小于所有客戶總的需求量；式（3）表示每個(gè)被選中心的服務(wù)能力不小于其服務(wù)客戶的總需求量；式（4）表示客戶需求由一個(gè)配送中心服務(wù)；式（5）為配送中心i服務(wù)的客戶數(shù)量表達(dá)式；式（6）為配送中心的數(shù)量約束；zi，yij為決策變量.

2 MDLP與擴(kuò)展K－TSP的映射

在研究MDLP時(shí)，發(fā)現(xiàn)它與擴(kuò)展K－TSP有諸多相似點(diǎn).為此，把擴(kuò)展K－TSP作為MDLP的數(shù)學(xué)原型，下面考察K－TSP與MDLP的映射關(guān)系.

2.1 擴(kuò)展 K－TSP問題

擴(kuò)展K－TSP問題可描述為：k個(gè)人從k個(gè)城市出發(fā)分頭去訪問n＋1個(gè)城市，每個(gè)城市有且僅有一個(gè)人到達(dá)，最后k個(gè)人都回到原出發(fā)城市，問怎樣安排使得k個(gè)人的總訪問路線最短［7］？

該問題的數(shù)學(xué)語言表示為：設(shè)V＝（v1，v2，…，vn，vn＋1）為平面上n＋1個(gè)點(diǎn)的集合；G＝（V，E）是V上的完全圖；W：E→R為權(quán)函數(shù).稱H為圖G＝（V，E）的k－周游路，如果它是k條子周游路的集合H＝（H1，H2，…，Hk），這里：①Hi至少包含2條邊，i＝1，2，…，k；②Hi經(jīng)過頂點(diǎn)vi，i＝1，2，…，k；③任給存在唯一的子周游路Hj（j＝1，2，…，k）經(jīng)過v.

k－周游路H的長(zhǎng)度記為L(zhǎng)（H），即

2.2 K－TSP與 MDLP映射過程

由對(duì)MDLP的描述可知，在 MDLP中，一組（k個(gè)）配送中心被選定，這些配送中心可以映射為KTSP中的K個(gè)出發(fā)城市，l個(gè)需求點(diǎn)相當(dāng)于K－TSP中被訪問的n＋1個(gè)城市，運(yùn)輸工具從選定的k個(gè)配送中心出發(fā)給l個(gè)需求點(diǎn)的配送過程可映射為KTSP中旅行商從給定的k個(gè)城市出發(fā)分頭去訪問n＋1個(gè)城市的過程，MDLP的總服務(wù)成本最小可以映射為K－TSP的總訪問路線最短.二者的映射關(guān)系如圖1所示.

圖1 MDLP與擴(kuò)展K－TSP映射過程Fig.1 Mapping between MDLP and expended K－TSP

由此可知，求解擴(kuò)展K－TSP的算法可應(yīng)用于MDLP.

3 求解MDLP的改進(jìn)蟻群算法

3.1 蟻群算法

蟻群算法（ant colony algorithm，ACA）是受啟于螞蟻覓食行為的一種仿生算法.在蟻群算法中，為每只螞蟻設(shè)置一個(gè)禁忌表tabu，其中存放已經(jīng)訪問過的節(jié)點(diǎn).當(dāng)一只螞蟻在t時(shí)刻從節(jié)點(diǎn)i向節(jié)點(diǎn)j轉(zhuǎn)移時(shí)，按式（10）確定的概率選擇轉(zhuǎn)移目標(biāo)［8］.

式中：τij（t）為t時(shí)刻節(jié)點(diǎn)i，j間路徑上的信息素量；ηij（t）＝1／dij為啟發(fā)函數(shù)；α為信息素啟發(fā)因子；β為期望函數(shù)啟發(fā)因子.

為避免信息素積累淹沒啟發(fā)信息，當(dāng)蟻群完成一次遍歷后，按式（11）更新信息素.

式中：ρ（0＜ρ＜1）為信息素?fù)]發(fā)因子；Δτij（t）為t時(shí)刻螞蟻遍歷節(jié)點(diǎn)i，j間路徑時(shí)留下的信息素量，Δτij（t）的初始化為零.

蟻群算法（ACA）能有效求解旅行商問題（travelling salesman problem，TSP），但它不能直接求解 K－TSP，因而更不能直接求解擴(kuò)展 K－TSP.ACA求解TSP問題時(shí)，每條蟻路都是一個(gè)完全路徑，都是一個(gè)可行解；在求解K－TSP問題時(shí)，每只螞蟻只形成子路徑，因而存在選擇子路徑構(gòu)造可行解的問題.螞蟻的子路徑存在下述幾種情況：（1）螞蟻的所有子路徑恰好構(gòu)成一個(gè)哈密爾頓通路，只是這種概率比較??；（2）螞蟻的子路徑?jīng)]有覆蓋所有節(jié)點(diǎn)，則子路徑不能構(gòu)造可行解；（3）子路徑覆蓋的節(jié)點(diǎn)有重復(fù)，則子路徑也不能構(gòu)造可行解；而在求解擴(kuò)展K－TSP問題時(shí)，除以上原因外，還有螞蟻從不同的城市出發(fā)，最后回到原出發(fā)點(diǎn)的問題，不像求解TSP問題那樣，所有螞蟻有相同的出發(fā)點(diǎn).

ACA不能直接求解擴(kuò)展K－TSP，因而也不能直接求解MDLP.為此，本文設(shè)計(jì)了改進(jìn)的蟻群算法，該算法不僅可以直接求解MDLP問題，而且具有較好的求解性能及收斂速度.具體措施為：（1）改進(jìn)了禁忌表的設(shè)置方式，所有螞蟻共享一個(gè)禁忌表，而不是給每只螞蟻單獨(dú)設(shè)立禁忌表，確保螞蟻的子路徑合成一個(gè)哈密爾頓通路，從而形成問題的可行解；（2）修改了概率選擇規(guī)則，在概率選擇規(guī)則中加入代價(jià)引導(dǎo)函數(shù).

為提高求解性能，算法使用2－opt策略優(yōu)化螞蟻?zhàn)勇窂讲⒃O(shè)計(jì)了信息素更新規(guī)則.

3.2 改進(jìn)蟻群算法（IACA）

3.2.1 蟻群共享禁忌表

螞蟻從擬選的k個(gè)配送中心出發(fā)，為所有螞蟻建立一個(gè)空白共享禁忌表并在其中放入k個(gè)配送中心.發(fā)生轉(zhuǎn)移時(shí)，每只螞蟻依據(jù)轉(zhuǎn)移策略選擇共享禁忌表里未曾記錄的配送點(diǎn)后，隨之將該配送點(diǎn)放入禁忌表，其他螞蟻就不能再選擇該配送點(diǎn).在滿足服務(wù)能力約束的情況下，螞蟻繼續(xù)選擇下一個(gè)配送點(diǎn)，否則返回其出發(fā)的配送中心.當(dāng)所有螞蟻都返回各自的出發(fā)點(diǎn)后，配送結(jié)束，使用2－opt優(yōu)化配送順序并更新信息素，計(jì)算解的目標(biāo)值.多次運(yùn)行算法，直到目標(biāo)值趨于穩(wěn)定，對(duì)一個(gè)選擇方案的評(píng)估結(jié)束.比較多個(gè)選擇方案的目標(biāo)值，目標(biāo)值小者即為MDLP的解.

3.2.2 螞蟻選擇策略

為提高算法的求解性能，在螞蟻的選擇策略中加入了代價(jià)引導(dǎo)函數(shù)，修改后的概率選擇規(guī)則如下：

式中：τij（t）為t時(shí)刻節(jié)點(diǎn)i，j間路徑上的信息素量；ηij（t）＝1／cij為啟發(fā)函數(shù)，cij為從節(jié)點(diǎn)i到節(jié)點(diǎn)j的配送代價(jià)；ζij（t）＝1／cj為代價(jià)引導(dǎo)函數(shù)，cj為貪婪算法得出的從各配送中心到節(jié)點(diǎn)j的配送成本的平均值；α為信息素啟發(fā)因子；β為期望啟發(fā)因子.

3.2.3 信息素更新規(guī)則

因?yàn)楦髯勇窂骄蓸?gòu)造可行解，故對(duì)2－opt優(yōu)化后的子路徑的每條邊均增加信息素量

式中：cm（m＝1，2，…，k）為各條子路徑的配送代價(jià).

比較各可行解的目標(biāo)函數(shù)值F，設(shè)當(dāng)前最好解的目標(biāo)值為Fb，如果（F－Fb）／Fb＜ε成立（ε是一個(gè)較小的正常量），則給最好解的各邊增加信息素量

同時(shí)，按式（11）更新信息素.為防止信息素過分懸殊導(dǎo)致算法陷入局部最優(yōu)，依照最大最小螞蟻策略修改各邊的信息素［9］，即令τmin≤τij（t）≤τmax，若τij（t）＜τmin，則τij（t）＝τmin；若τij（t）＞τmax，則τij（t）＝τmax.

3.2.4 MDLP－IACA執(zhí)行過程

（1）初始化各關(guān)鍵參數(shù)；

（2）清空螞蟻的共享禁忌表tabu；

（3）將螞蟻置于擬選各配送中心位置上，并將這些配送中心加入共享禁忌表；

（4）按式（12）執(zhí)行螞蟻轉(zhuǎn)移策略，直到全部螞蟻形成自己的子路徑；

（5）對(duì)各子路徑使用2－opt反復(fù)優(yōu)化，并按式（13）更新可行解各邊的信息素；

（6）按式（14）更新當(dāng)前最好解的信息素；

（7）按式（11）更新信息素，并置所有邊上的信息素增量為零；

（8）若不滿足結(jié)束條件，轉(zhuǎn)入（2），否則，結(jié)束.

改進(jìn)蟻群算法中，參數(shù)α，β，ρ對(duì)算法的求解性能及收斂情況有很大的影響.其中，α值的大小反映了配送點(diǎn)到配送中心的信息量受重視的程度，可理解為信息量的指數(shù)加權(quán).α＝0，算法性能接近于貪婪算法，α值越大，螞蟻選擇以前經(jīng)過的路線的可能性越大，但過大會(huì)使算法陷于局部最小解；β的大小表明啟發(fā)式信息受重視的程度，β值越大，螞蟻選擇離它近的城市的可能性也越大，但過大也會(huì)使算法陷入局部最小解；ρ反映信息素的揮發(fā)程度，ρ過小會(huì)使算法過早收斂（信息素積累快），過大則導(dǎo)致前面螞蟻好的搜索結(jié)果不能被后來螞蟻充分利用.本文通過大量的仿真實(shí)驗(yàn)，得出α，β，ρ對(duì)算法結(jié)果的影響曲線，分別如圖2～圖4所示.從曲線圖看出α＝1.1，β＝0.9，ρ＝0.15是較好的配置組合.

4 算例與分析

一物流配送矩形區(qū)域，范圍為（0，0）到（100，1 00），其中散布著27個(gè)配送點(diǎn)，各配送點(diǎn)的坐標(biāo)和需求量見表1；有9個(gè)候選配送中心，各中心的坐標(biāo)、固定費(fèi)用見表2；設(shè)配送中心到各配送點(diǎn)的運(yùn)費(fèi)率均為1，選取5個(gè)配送中心，使得各中心的配送總成本及固定費(fèi)用成本之和最小.

表1 配送點(diǎn)基本數(shù)據(jù)Tab.1 Basic data for distribution points

表2 配送中心基本數(shù)據(jù)Tab.2 Basic data for distribution centers

利用Visual C＋＋6.0編程.參數(shù)設(shè)置為α＝1.1，β＝0.9，ρ＝0.15，ε＝0.05，最大迭代次數(shù)Nc，max＝1000，τmin為0.1，τmax＝10，螞蟻數(shù)＝50，算法執(zhí)行50次，算法所得解的情況見表3.

表3中GA算法（遺傳算法）得到的數(shù)據(jù)是用不同初始值計(jì)算50次得到的最優(yōu)結(jié)果.從表3看出，兩種算法得出的配送服務(wù)點(diǎn)和配送規(guī)模一致，但選擇的配送中心及配送中心服務(wù)總成本不一樣，改進(jìn)蟻群算法得到的解值明顯優(yōu)于遺傳算法.證明改進(jìn)蟻群算法在求解多配送中心選址問題是可行的.

5 結(jié)論

本文將多物流配送中心選址問題映射成擴(kuò)展K－TSP過程，通過設(shè)置共享禁忌表、改進(jìn)轉(zhuǎn)移規(guī)則、2－opt優(yōu)化及信息素更新等策略，實(shí)現(xiàn)了蟻群算法對(duì)多物流中心選址問題的直接求解.仿真算例及算法比對(duì)表明，本算法是求解多配送中心選址問題的較好選擇.

表3 IACA算法和GA算法計(jì)算結(jié)果比較Tab.3 Results comparison between IACA and GA

［1］Da Gama F S，Captivo M E.A heuristic approach for the discrete dynamic location problem［J］.Location Science，1998（6）：211.

［2］Konstantinos G Z，Konstantinos N A.A heuristic algorithm for solving hazardous materials distribution problems［J］.European Journal of Operational Research，2004，152：507.

［3］張潛，高立群，劉雪梅，等.定位-運(yùn)輸路線安排問題的兩階段啟發(fā)式算法［J］控制與決策，2004，19（7）：773.ZHANG Qian，GAO Liqun，LI Xuemei，et al.A two－phase heuristic approach to the location routing problem［J］.Control and Decision，2004，19（7）：773.

［4］Dorigo M，Gambardela L M.The ant system：optimization by a colony of cooperating agents［J］.IEEE Trans on System，Man and Cybernetics，1996，26（1）：29.

［5］聞?dòng)?，吳鐵軍.基于蟻群算法的城域交通控制實(shí)時(shí)滾動(dòng)優(yōu)化［J］，控制與決策，2004，19（9）：1057.WEN Yu，WU Tiejun.Real－time rolling horizon optimization of urban traffic con troll based on ant algorithm［J］.Control and Decision，2004，19（9）：1057.

［6］Dorigo M，Gambardella L M.Ant colony system：a cooperative learning approach to the traveling salesman problem［J］.IEEE Trans on Evolutionary Computation，1997，1（1）：53.

［7］周愛蓮.企業(yè)物流系統(tǒng)網(wǎng)絡(luò)節(jié)點(diǎn)選址方法及應(yīng)用研究［D］.南京：東南大學(xué)交通學(xué)院，2007.ZHOU Ailian.Research on the method and application of nodes location of enterprises logistics network ［D］.Nanjing：Southeast University.College of Transportation，2007.

［8］Frieze A M.An extension of Christofides heuristics to thekperson traveling salesman problem ［J］.Discrete Applied Mathematics，1983（1）：79.

［9］Thomas S，Holger H H.MAX－MIN ant system［J］.Future Generation Computer System，2000，16（8）：889.