軟容量約束的物流設(shè)施選址問(wèn)題的改進(jìn)差分進(jìn)化算法

張新邦++邢航++李貴棟++汪恭書

摘 要：研究了廣泛存在于物流系統(tǒng)設(shè)計(jì)與管理中的軟容量約束的物流設(shè)施選址問(wèn)題，主要決策每個(gè)客戶需求由哪個(gè)設(shè)施服務(wù)以及每個(gè)設(shè)施開放的次數(shù)，目標(biāo)為最小化設(shè)施開放成本和運(yùn)輸成本之和。為了有效求解該問(wèn)題，提出了一種改進(jìn)的差分進(jìn)化算法，編碼方式上采用實(shí)數(shù)編碼策略，較為簡(jiǎn)單易于實(shí)現(xiàn)且能得到較好結(jié)果，進(jìn)化過(guò)程采用多種變異算子并進(jìn)行對(duì)比。對(duì)以往文獻(xiàn)給出的算例采用5種變異算子進(jìn)行測(cè)試，計(jì)算結(jié)果表明，DE/rand-to-best/1/bin變異算子最好，且所有算子都能得到較好結(jié)果，DE算法在軟容量約束的設(shè)施選址問(wèn)題上應(yīng)用具有可行性。

關(guān)鍵詞：物流設(shè)施選址問(wèn)題；軟容量約束；差分進(jìn)化；實(shí)數(shù)編碼

中圖分類號(hào)：F253.9 文獻(xiàn)標(biāo)識(shí)碼：A

Abstract： This paper studies the soft-capacitated logistics facility location problem that is widely existed in the design and management of logistics system. The problem is to make decision that each customer demand should be serviced by which facility and the open times for each facility so as to minimize the sum of facility opening cost and transportation cost. To solve the problem efficiently， we proposed an improved differential evaluation algorithm. The proposed algorithm uses a real number coding strategy to implement easily， and compares multiple mutation operators in the evolutionary process. We test 5 mutation operators over the instances collected from an existing article. The computational results show that the DE/rand-to-best/1/bin has the best mutation operator， and all other mutation operators can also get better solution for some instances. This verifies that it is feasible to use differential evaluation algorithm to solve the soft-capacitated logistics facility location problem.

Key words： logistics facility location problem； soft-capacitated； differential evaluation； real number coding

0 引 言

設(shè)施選址問(wèn)題是物流與供應(yīng)鏈管理領(lǐng)域一類重要的組合優(yōu)化問(wèn)題，其在企業(yè)選址、網(wǎng)絡(luò)設(shè)施及服務(wù)點(diǎn)的分布等眾多方面都有應(yīng)用。自1909年韋伯發(fā)表了關(guān)于設(shè)施選址問(wèn)題的第一篇論文至今，該類問(wèn)題備受眾多研究者青睞。這一問(wèn)題受到廣泛關(guān)注是因?yàn)閷?duì)設(shè)施選址問(wèn)題的研究存在著極為重要的實(shí)際意義。選址決策屬于長(zhǎng)期的，具有戰(zhàn)略意義的決策，決策的好壞對(duì)于服務(wù)方式、服務(wù)質(zhì)量、生產(chǎn)成本等方面都有很大的影響，通常一個(gè)較好的設(shè)施選址方案會(huì)很大程度減少不必要的費(fèi)用，對(duì)一個(gè)企業(yè)而言，甚至還會(huì)極大、長(zhǎng)久地影響到其生產(chǎn)經(jīng)營(yíng)、市場(chǎng)競(jìng)爭(zhēng)力甚至企業(yè)的發(fā)展命運(yùn)。從宏觀而言，設(shè)施選址影響著經(jīng)濟(jì)、政治、文化、社會(huì)、生態(tài)各個(gè)方面，以及系統(tǒng)的運(yùn)行效率。

設(shè)施選址問(wèn)題常被分為有容量約束的設(shè)施選址問(wèn)題（Capacitated Facility Location Problem）、無(wú)容量約束的設(shè)施選址問(wèn)題（Un-capacitated Facility Location Problem）和軟容量約束的設(shè)施選址問(wèn)題（Soft-capacitated Facility Location Problem）。目前對(duì)設(shè)施選址問(wèn)題的研究已有一些不錯(cuò)的研究成果。如Guha & Khuller[1]將一維的無(wú)容量限制的設(shè)施選址問(wèn)題推廣至k維，并通過(guò)實(shí)驗(yàn)得到1.463的硬度近似比；Jain et al[2]的研究表明貪婪算法可以用于求解帶懲罰的無(wú)容量約束設(shè)施選址問(wèn)題且近似比為2；Charikar & Guha[3]將原始對(duì)偶方法與增強(qiáng)的貪心算法相結(jié)合得到近似比為1.853。

本文主要研究了軟容量約束的設(shè)施選址問(wèn)題。軟容量指的是在考慮設(shè)施提供服務(wù)的有限性的同時(shí)，考慮到現(xiàn)實(shí)生活中設(shè)施可以多次開設(shè)并支付費(fèi)用來(lái)增加自身容量。該類問(wèn)題的目標(biāo)是使設(shè)施開設(shè)費(fèi)用和連接費(fèi)用之和的最小。對(duì)于此類問(wèn)題，Arya et al[4]提出了一種局部搜索算法，得到了一個(gè)近似比為3.72的優(yōu)化結(jié)果；Jain et al[5]的研究表明軟容量近似比可以達(dá)到3。徐大川等[6]研究?jī)呻A段模型，考慮隨機(jī)性與容錯(cuò)率，使用原始—對(duì)偶近似算法進(jìn)行求解。Holmberg et al[7]針對(duì)有容量約束的設(shè)施選址問(wèn)題，提出了最優(yōu)化精確算法，可求得中小規(guī)模問(wèn)題的最優(yōu)解。

從目前的研究情況來(lái)看，運(yùn)用近似算法來(lái)求解該類問(wèn)題，雖然步驟簡(jiǎn)潔和計(jì)算復(fù)雜度低，但其優(yōu)化結(jié)果較最優(yōu)解還有較大距離。運(yùn)用最優(yōu)化算法來(lái)進(jìn)行求解，雖然能得到最優(yōu)解，但從最優(yōu)化算法自身的特點(diǎn)來(lái)看，其無(wú)法解決大規(guī)模問(wèn)題。目前有一種備受學(xué)術(shù)界關(guān)注的優(yōu)化算法—智能優(yōu)化算法，其能夠在短時(shí)間內(nèi)獲得高質(zhì)量解的優(yōu)化算法，能從一定程度上彌補(bǔ)以上兩種算法在求解該類問(wèn)題時(shí)的缺點(diǎn)，且其不受問(wèn)題結(jié)構(gòu)的限制，是一種優(yōu)化問(wèn)題的較好選擇。本文正是嘗試運(yùn)用目前一種較好的智能優(yōu)化算法—差分進(jìn)化算法來(lái)求解軟容量約束的設(shè)施選址問(wèn)題。endprint

差分進(jìn)化算法是1995年Storn和Price提出的一種仿生物進(jìn)化的智能優(yōu)化算法[8]，近年由于其較好的魯棒性與收斂性得到越來(lái)越多學(xué)者的關(guān)注。應(yīng)用DE求解設(shè)施選址問(wèn)題關(guān)鍵是對(duì)編碼方法、變異和交叉過(guò)程等進(jìn)行合理設(shè)計(jì)，使其得到較為理想的結(jié)果。

本文針對(duì)軟容量約束的設(shè)施選址問(wèn)題的特點(diǎn)，對(duì)差分進(jìn)化算法編碼、變異以及交叉過(guò)程進(jìn)行設(shè)計(jì)，編碼過(guò)程采用實(shí)數(shù)編碼策略，改進(jìn)了差分算子，并且對(duì)不同差分算子進(jìn)行了比較，選擇過(guò)程采用貪婪策略。通過(guò)實(shí)驗(yàn)可以看出，本文應(yīng)用差分進(jìn)化算法解決該類問(wèn)題具有可行性。

4 結(jié) 論

本文研究了一類廣泛存在于物流系統(tǒng)設(shè)計(jì)與管理中的軟容量約束條件下的設(shè)施選址問(wèn)題，建立了問(wèn)題的混合整數(shù)規(guī)劃模型，提出了收斂速度與魯棒性較好的差分進(jìn)化算法的求解方法，并通過(guò)實(shí)驗(yàn)對(duì)比了不同變異算子作用下的結(jié)果，驗(yàn)證了差分進(jìn)化算法在此類問(wèn)題上的可行性。

參考文獻(xiàn)：

[1] Guha S， Khuller S. Greedy Strikes Back： Improved Facility Location Algorithms[J]. Journal of Algorithms， 1999，31（1）：228-248.

[2] Jain K， Mahdian M， Markakis E， et al. Greedy Facility Location Algorithms Analyzed using Dual Fitting with Factor-Revealing LP[J]. Journal of the Acm， 2002，50（6）：127-137.

[3] Charikar M， Guha S. Improved Combinatorial Algorithms for Facility Location Problems[J]. Foundations of Computer Science Annual Symposium on， 1999，34（4）：378-388.

[4] Arya V， Garg N， Khandekar R， et al. Local Search Heuristics for k-median and Facility Location Problems[J]. Siam Journal on Computing， 2004，33（3）：21-29.

[5] Jain K， Mahdian M， Saberi A. A New Greedy Approach for Facility Location Problems[C] // Proceedings of Annual Acm Symposium on the Theory of Computing， 2010：731-740.

[6] 徐大川，萬(wàn)瑋，吳晨晨，等. 隨機(jī)容錯(cuò)設(shè)施選址問(wèn)題的原始—對(duì)偶近似算法[J]. 運(yùn)籌學(xué)學(xué)報(bào)，2014，18（2）：17-28.

[7] Holmberg K， Ronnqvist M， Yuan D. An exact algorithm for the capacitated facility location problems with single sourcing[J]. European Journal of Operational Research， 1999，113：544-559.

[8] Storn R， Price K V. Differential evolution： A simple and efficient adaptive scheme for global optimization over continuous spaces[J]. Journal of Global Optimization， 1995，23（4）：341-359.endprint