冉昊杰，王宏智

(青島農(nóng)業(yè)大學(xué)管理學(xué)院，山東 青島 266109)

0 引 言

隨著我國經(jīng)濟(jì)社會(huì)的發(fā)展，配送中心除承擔(dān)基本物流職能外，還要越來越多地執(zhí)行動(dòng)態(tài)調(diào)度、信息篩選等職能。通常情況下，生鮮農(nóng)產(chǎn)品的物流配送半徑較小，但是其供應(yīng)鏈及物流網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜，涉及的相關(guān)利益者較多。因此，實(shí)現(xiàn)生鮮農(nóng)產(chǎn)品配送中心的最優(yōu)選址決策，建立高標(biāo)準(zhǔn)、高效率的配送體系，以最快的速度將最好品質(zhì)的生鮮農(nóng)產(chǎn)品運(yùn)送到超市大賣場等終端銷售網(wǎng)點(diǎn)，對整個(gè)生鮮農(nóng)產(chǎn)品物流系統(tǒng)的優(yōu)化具有重要的現(xiàn)實(shí)意義。

近年來，我國諸多學(xué)者針對配送中心選址問題的算法求解及改進(jìn)措施進(jìn)行了積極的探索研究，從定性和定量方面提出了許多可供借鑒學(xué)習(xí)的解決方法。李晶晶[1]運(yùn)用灰色模型分析新鮮度降低和打折銷售對顧客購買需求的影響，建立以滿足需求為前提、總成本最小為目標(biāo)的冷鏈配送中心選址模型。裴時(shí)域等[2]采用一種部分流量再配置的新解產(chǎn)生方式，并基于改進(jìn)的模擬退火算法對該問題進(jìn)行優(yōu)化求解，使其具有良好的求解能力。劉婧[3]采用與粒子群算法相結(jié)合的方式，改進(jìn)模擬退火算法，使其收斂性能更佳，降低配送和倉儲(chǔ)成本。

其中遺傳算法為群體需求點(diǎn)搜索方式，在實(shí)際運(yùn)算中算力規(guī)模較大。相比之下，模擬退火算法為個(gè)體需求點(diǎn)搜索，雖然算力規(guī)模較小，但會(huì)在算法后期產(chǎn)生大量無效搜索[4]。為探究生鮮農(nóng)產(chǎn)品配送中心選址問題的更優(yōu)思路，本文基于傳統(tǒng)模擬退火算法，引入遺傳算法解決方案，在改進(jìn)原有算法搜索性能的同時(shí)保證搜索精度，使得在實(shí)際應(yīng)用中做到更優(yōu)的選址決策。

1 生鮮農(nóng)產(chǎn)品配送中心選址模型建立

1.1 選址問題描述

生鮮農(nóng)產(chǎn)品配送中心選址問題可描述為：某個(gè)地區(qū)范圍內(nèi)有若干個(gè)生鮮農(nóng)產(chǎn)品需求點(diǎn)，且各需求點(diǎn)的需求情況確定，選取若干個(gè)配送中心備選點(diǎn)，并從中選取部分建立配送中心，以滿足該地區(qū)需求點(diǎn)的需求，并實(shí)現(xiàn)包括貨物運(yùn)輸固定費(fèi)用以及生鮮農(nóng)產(chǎn)品存儲(chǔ)費(fèi)用在內(nèi)的總費(fèi)用最少[5]。

本文所建立的生鮮農(nóng)產(chǎn)品配送中心選址問題的數(shù)學(xué)模型假設(shè)為：運(yùn)輸費(fèi)用與生鮮農(nóng)產(chǎn)品運(yùn)量情況成正比；配送中心僅建立在備選點(diǎn)當(dāng)中；單個(gè)配送中心的容量足夠滿足所包含需求點(diǎn)的需求；各需求點(diǎn)的生鮮農(nóng)產(chǎn)品需求量確定，并且在短期內(nèi)不會(huì)產(chǎn)生較大波動(dòng)。

1.2 構(gòu)建選址模型

假設(shè)有n個(gè)生鮮農(nóng)產(chǎn)品需求點(diǎn)，各個(gè)需求點(diǎn)的需求量已知，將t個(gè)生鮮農(nóng)產(chǎn)品配送中心建立在m個(gè)備選地當(dāng)中，實(shí)現(xiàn)生鮮農(nóng)產(chǎn)品配送系統(tǒng)的總費(fèi)用最少?？蓪⒍鄠€(gè)生鮮農(nóng)產(chǎn)品配送中心的選址問題表示成如下線性規(guī)劃模型：

(1)

(2)

(3)

(4)

xij≥0,yj∈{0,1};i=1,2,…,m;j=1,2,…,n

(5)

式(1)表示配送中心到需求點(diǎn)總運(yùn)輸費(fèi)用最小值的目標(biāo)函數(shù)，第1項(xiàng)表示從配送中心到需求點(diǎn)的總運(yùn)輸費(fèi)用，第2項(xiàng)表示配送中心的固定費(fèi)用，第3項(xiàng)表示配送中心的存儲(chǔ)費(fèi)用，m為配送中心備選地個(gè)數(shù)，n為需求點(diǎn)個(gè)數(shù)，hij為從配送中心到目標(biāo)需求點(diǎn)的單位運(yùn)費(fèi)，xij為配送中心為目標(biāo)需求點(diǎn)供應(yīng)的貨物量，yi為在備選地i建立配送中心的情況[6]，F(xiàn)i為在第i個(gè)備選點(diǎn)建立生鮮農(nóng)產(chǎn)品配送中心的年固定費(fèi)用，Ci為在第i個(gè)配送中心存儲(chǔ)單位貨物的存儲(chǔ)費(fèi)。約束條件式(2)表示各個(gè)需求點(diǎn)的需求量必須得到滿足，Dj為第j個(gè)需求點(diǎn)的生鮮農(nóng)產(chǎn)品年需求量。式(3)表示在備選地中選取若干建立配送中心，t為擬建配送中心個(gè)數(shù)。式(4)表示如果一個(gè)備選地為某些需求點(diǎn)提供貨物，則需要在該地建立配送中心，其中M是一個(gè)很大的正數(shù)，表示該配送中心能夠充分滿足所包含需求點(diǎn)的需求量。式(5)表示變量的取值限制。

2 模擬退火算法優(yōu)化改進(jìn)

2.1 模擬退火算法原理

模擬退火算法是由固體退火原理產(chǎn)生，二者比較如表1所示。在模擬退火算法中，首先需要將固體加熱融化為完全無序液態(tài)，此時(shí)固體中的粒子內(nèi)能增大，處于自由運(yùn)動(dòng)態(tài)；隨后逐漸降溫，粒子運(yùn)動(dòng)逐漸趨于有序；當(dāng)溫度降低到結(jié)晶程度時(shí)，粒子內(nèi)能減為最小，運(yùn)動(dòng)為圍繞晶格點(diǎn)的規(guī)則振動(dòng)。同時(shí)采用Metropolis準(zhǔn)則，以概率接受新狀態(tài)，得到非線性規(guī)劃問題的優(yōu)化解[7]。

表1 固體退火過程與模擬退火過程比較

2.2 模擬退火算法求解流程

2.2.1 求得局部最優(yōu)解

從某個(gè)初始解出發(fā)，在約束區(qū)間中隨機(jī)搜索，利用以概率接受新狀態(tài)的準(zhǔn)則，使無序逐漸向收斂過渡，實(shí)現(xiàn)局部最優(yōu)解。算法準(zhǔn)則規(guī)定系統(tǒng)從某一狀態(tài)能量E1變化到另一狀態(tài)能量E2時(shí)，能量變化概率情況如式(6)所示。

(6)

其中T為算法初始設(shè)定的模擬溫度值。

如果新解比當(dāng)前解更優(yōu)，即E2≥E1，則接受該變化狀態(tài)產(chǎn)生的新解；否則算法將基于Metropolis準(zhǔn)則判斷是否接受新解。該變化狀態(tài)新解被接受的概率如式(7)所示。

(7)

2.2.2 控制相對最優(yōu)解

通過逐漸減小控制參數(shù)的值，重復(fù)執(zhí)行以概率接受新狀態(tài)的算法準(zhǔn)則，經(jīng)過大量求解運(yùn)算后，得到在系統(tǒng)約束范圍內(nèi)的相對最優(yōu)解。

溫度變量在算法準(zhǔn)則中起到?jīng)Q定性控制作用：在溫度逐漸升至最高時(shí)，系統(tǒng)可以接受任何情況下的惡化解；隨著溫度的逐漸降低，系統(tǒng)只接受較好情況下的惡化解；最后在溫度趨于最低時(shí)，系統(tǒng)將不接受任何惡化解。

2.2.3 獲得整體最優(yōu)解

溫度作為決定性的控制參數(shù)必須緩慢衰減，使系統(tǒng)通過一定次數(shù)的迭代運(yùn)算，趨于相對穩(wěn)定的能量分布態(tài)。當(dāng)控制參數(shù)趨于最低時(shí)，模擬退火算法將求得非線性規(guī)劃問題的整體最優(yōu)解。具體流程如圖1所示。

2.3 模擬退火算法求解模型過程中的特點(diǎn)

由上述求解過程可知，模擬退火算法求得整體最優(yōu)解的可實(shí)現(xiàn)性高，緩慢降溫過程有效避免了搜索過程陷入局部最優(yōu)解的缺陷，以一定的概率接受惡化解，從而提高整體最優(yōu)解的可靠性。

但同時(shí)求解過程存在較為明顯的矛盾，主要體現(xiàn)在降溫過程與解的質(zhì)量之間。若要在算法后期進(jìn)行更加有效的搜索，就必須減小退火溫度的衰變值，根據(jù)搜索的需要表現(xiàn)出系統(tǒng)的分散性；而延長降溫過程，會(huì)造成迂回搜索和局部極小解的問題[8]。

2.4 遺傳算法原理及其求解模型過程中的特點(diǎn)

遺傳算法是由生物進(jìn)化原理產(chǎn)生的搜索算法，用于解決最佳化問題。在遺傳算法中，需要在已知求解空間的前提下對可行解進(jìn)行編碼，并在可行解空間里隨機(jī)生成初始種群，求出種群中各個(gè)體的適應(yīng)度值，借助遺傳的選擇復(fù)制交叉變異等算子，依據(jù)適者生存的原理，引導(dǎo)搜索出全局最優(yōu)解[9-12]。其良好的可擴(kuò)展性和靈活性，能夠與傳統(tǒng)優(yōu)化算法進(jìn)行有機(jī)結(jié)合，形成混合算法，有效改進(jìn)傳統(tǒng)模擬退火算法的缺陷。

2.5 遺傳算法與模擬退火算法的融合

本文將遺傳算法與模擬退火算法融合，實(shí)現(xiàn)對模擬退火算法的改進(jìn)。在退火過程的溫度閾值搜索環(huán)節(jié)引入以配送中心為自然數(shù)編碼的染色體個(gè)體，在此基礎(chǔ)上創(chuàng)建符合約束條件的初始種群。

進(jìn)一步，篩選出符合當(dāng)前控制參數(shù)條件的染色體集。通過輪盤賭選擇，選出若干個(gè)適應(yīng)度大的個(gè)體作為父代，在此基礎(chǔ)上進(jìn)行交叉和變異操作，產(chǎn)生新一代種群P(gen+1)，保證優(yōu)良父代的染色體片段遺傳給后代的同時(shí)，變異跳出局部最優(yōu)，實(shí)現(xiàn)整體最優(yōu)，并輸出退火過程的最優(yōu)解。

3 算例分析

3.1 山東省A公司生鮮農(nóng)產(chǎn)品配送中心選址問題

A公司是山東省內(nèi)一家知名生鮮農(nóng)產(chǎn)品企業(yè)，表2描述了該公司分布在省內(nèi)的20個(gè)區(qū)域的需求點(diǎn)及其需求量。為提高配送效率，有效降低服務(wù)成本，該企業(yè)決定建立若干配送中心。由于其車輛設(shè)備等硬件需要，配送中心備選地分別是膠州市、平度市、萊西市、招遠(yuǎn)市、蓬萊市、棲霞市、諸城市、壽光市。從上述8個(gè)備選地中選擇3個(gè)建立生鮮農(nóng)產(chǎn)品配送中心，實(shí)現(xiàn)優(yōu)化[13-20]。

表2 A公司生鮮農(nóng)產(chǎn)品需求點(diǎn)及對應(yīng)需求量

3.2 改進(jìn)模擬退火算法選址過程

結(jié)合A公司實(shí)際的選址要求，運(yùn)用改進(jìn)后的模擬退火算法進(jìn)行選址，選址具體過程如下。

3.2.1 獲取基本數(shù)據(jù)

對A公司分布在山東省內(nèi)的20個(gè)區(qū)域的需求點(diǎn)進(jìn)行劃分，將每個(gè)區(qū)域內(nèi)客戶的需求量匯總作為該需求點(diǎn)的運(yùn)輸量。再利用ArcGIS空間查詢功能獲得各需求點(diǎn)的經(jīng)緯度坐標(biāo)，建立平面直角坐標(biāo)系如圖2所示。

在實(shí)際選址過程中，生鮮農(nóng)產(chǎn)品昂貴的存儲(chǔ)費(fèi)用是影響生鮮農(nóng)產(chǎn)品配送中心運(yùn)營成本的重要因素，主要包括貨損費(fèi)及倉庫保管費(fèi)等。且不同城市間運(yùn)輸情況不同，導(dǎo)致單位運(yùn)費(fèi)存在較大差異[21-23]。A公司各備選點(diǎn)存儲(chǔ)費(fèi)用及單位運(yùn)費(fèi)情況如表3和表4所示。

表3 A公司各備選點(diǎn)單位存儲(chǔ)及固定費(fèi)用

表4 A公司備選點(diǎn)到需求點(diǎn)單位運(yùn)輸費(fèi)用表 單位：元/t

3.2.2 溫度搜索環(huán)節(jié)引入染色體個(gè)體形成初始種群

本文在模擬退火算法的退火溫度閾值搜索環(huán)節(jié)引入以配送中心為自然數(shù)編碼的染色體個(gè)體，在此基礎(chǔ)上創(chuàng)建符合約束條件的初始種群。在確定初始種群的過程中，N表示種群規(guī)模，Mb表示最大進(jìn)化代數(shù)，pc表示交叉概率，pm表示變異概率，gen表示當(dāng)前執(zhí)行代數(shù)，C表示遺傳代溝。

3.2.3 通過適應(yīng)度函數(shù)選出父代個(gè)體

(8)

si+fi+tij-M(1-kij)≤sj

(9)

(10)

式(8)表示車輛的容積約束，qi表示單個(gè)車輛從配送中心i裝載的貨物量，kj表示向需求點(diǎn)j運(yùn)輸貨物的車輛數(shù)，K表示配送中心可供運(yùn)輸貨物的車輛總數(shù)。式(9)表示車輛配送的時(shí)間窗約束，si表示配送服務(wù)的開始時(shí)刻，sj表示配送服務(wù)的結(jié)束時(shí)刻，fi表示配送服務(wù)的持續(xù)時(shí)間，tij表示從配送中心i到需求點(diǎn)j車輛行駛所消耗的時(shí)間。kij表示車輛從配送中心i行駛到需求點(diǎn)j的情況判斷，若有車輛從配送中心行駛到需求點(diǎn)，則kij=1；否則kij=0。M仍為一個(gè)很大的正數(shù)，當(dāng)沒有車輛對需求點(diǎn)進(jìn)行配送服務(wù)時(shí)，車輛配送的時(shí)間窗約束仍成立。式(10)表示時(shí)間窗約束的懲罰適應(yīng)度函數(shù)。其中，ai、bi表示客戶規(guī)定的最早和最晚開始配送服務(wù)的時(shí)間。當(dāng)配送服務(wù)在客戶規(guī)定的最早與最晚服務(wù)時(shí)間內(nèi)進(jìn)行時(shí)，會(huì)產(chǎn)生相應(yīng)的單位激勵(lì)成本c1；當(dāng)配送服務(wù)晚于客戶規(guī)定的最晚服務(wù)時(shí)間時(shí)，會(huì)產(chǎn)生相應(yīng)的單位懲罰成本c2。由此得到Ci為時(shí)間窗約束的懲罰成本適應(yīng)度值。

3.2.4 通過輪盤賭選擇進(jìn)行順序交叉和變異

進(jìn)一步，篩選出符合當(dāng)前控制參數(shù)條件的染色體集。通過輪盤賭選擇，選出若干個(gè)適應(yīng)度大的個(gè)體作為父代，并在此基礎(chǔ)上進(jìn)行順序交叉操作，產(chǎn)生新一代種群P(gen+1)，保證優(yōu)良父代的染色體片段遺傳給后代。同時(shí)進(jìn)行變異操作跳出局部最優(yōu)，實(shí)現(xiàn)整體最優(yōu)。

3.2.5 將基礎(chǔ)數(shù)據(jù)代入算法模型，求得最優(yōu)解

采用Matlab求解，得到3個(gè)配送中心分別應(yīng)該建在招遠(yuǎn)市、諸城市和萊西市，最小總費(fèi)用為1613952元。

根據(jù)計(jì)算結(jié)果，得出模擬退火算法求出的配送中心與需求點(diǎn)之間的最優(yōu)分配結(jié)果，3個(gè)配送中心網(wǎng)點(diǎn)基本覆蓋20個(gè)需求點(diǎn)，如表5所示。

表5 配送中心與需求點(diǎn)之間最優(yōu)分配結(jié)果

3.3 改進(jìn)前后模擬退火算法求解過程對比

算例仿真所在的實(shí)驗(yàn)平臺(tái)為Win11系統(tǒng)，采用MATLAB R2021b軟件進(jìn)行實(shí)驗(yàn)運(yùn)算，迭代總次數(shù)為2000次，輸出改進(jìn)前后的模擬退火算法總成本變化趨勢圖，即算法評價(jià)函數(shù)值曲線，如圖3所示。其中縱坐標(biāo)表示選址總成本的平均適應(yīng)度值。

通過圖3對比可以發(fā)現(xiàn)在算法運(yùn)行早期，改進(jìn)前后的算法表現(xiàn)同樣高效，評價(jià)值下降平穩(wěn)且較快；從第100次左右迭代開始，改進(jìn)前的算法搜索過程出現(xiàn)明顯斷層停滯，說明迂回搜索和無效搜索已經(jīng)出現(xiàn)，相比之下，改進(jìn)后的算法搜索更為連續(xù)平滑；在第200次迭代時(shí)，改進(jìn)前的算法搜索進(jìn)入了相對瓶頸期，雖然在第500、第700和第1000次左右仍然尋找到了更優(yōu)解，但與改進(jìn)后算法搜索的有效性和連續(xù)性上存在較大差異；從第1200次迭代以后，改進(jìn)前的算法評價(jià)函數(shù)值曲線基本保持不變，說明搜索進(jìn)入無效階段，而改進(jìn)后的算法仍在保持有效搜索，直到第2000次算法停止迭代。

因此，模擬退火算法與遺傳算法融合后，既保持了群體搜索方式在實(shí)際應(yīng)用中的并行優(yōu)勢和極強(qiáng)的容錯(cuò)能力，又延續(xù)了單點(diǎn)搜索方式的更少算力，二者兼?zhèn)涫沟酶倪M(jìn)后的模擬退火算法有效解決了降溫過程與解質(zhì)量的矛盾[24-26]，在保證更少迭代的基礎(chǔ)上，減少模擬退火算法在迭代后期(1200次及以后)大量迂回搜索、無效搜索的問題。

4 結(jié)束語

本文通過構(gòu)建生鮮農(nóng)產(chǎn)品配送中心選址模型，借鑒模擬退火算法在已有的一些組合優(yōu)化問題中的成功應(yīng)用經(jīng)驗(yàn)，分析模擬退火算法的實(shí)際求解流程。通過求解可知在生鮮農(nóng)產(chǎn)品配送中心選址過程中，模擬退火算法作為單點(diǎn)搜索方式表現(xiàn)出算法簡單，便于實(shí)現(xiàn)，全局整體最優(yōu)求解的可靠性高，適用于復(fù)雜非線性優(yōu)化問題的求解，同時(shí)也暴露出求解過程中體現(xiàn)在降溫過程與解的質(zhì)量之間的矛盾。因此，本文將遺傳算法與模擬退火算法融合，實(shí)現(xiàn)對模擬退火算法的改進(jìn)，在退火過程的溫度閾值搜索環(huán)節(jié)引入以配送中心為自然數(shù)編碼的染色體個(gè)體，篩選出符合當(dāng)前控制參數(shù)條件的染色體集。進(jìn)一步通過輪盤賭選擇，選出若干個(gè)適應(yīng)度大的個(gè)體作為父代，并在此基礎(chǔ)上進(jìn)行交叉和變異操作，保證優(yōu)良父代的染色體片段遺傳給后代的同時(shí)，變異跳出局部最優(yōu)，實(shí)現(xiàn)整體最優(yōu)。

通過對以山東省A公司的生鮮農(nóng)產(chǎn)品配送中心選址問題為例進(jìn)行仿真模擬，實(shí)驗(yàn)結(jié)果表明改進(jìn)的模擬退火算法在實(shí)際應(yīng)用中保持了遺傳算法搜索的并行優(yōu)勢和極強(qiáng)的容錯(cuò)能力，又延續(xù)了模擬退火算法搜索的最優(yōu)算力。由此可見，本文所提改進(jìn)的模擬退火算法對于生鮮農(nóng)產(chǎn)品配送中心選址問題的解決具有一定的實(shí)用價(jià)值。