基于改進模擬退火算法的生鮮農(nóng)產(chǎn)品配送中心選址

冉昊杰，王宏智

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

0 引 言

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

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

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

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

1.1 選址問題描述

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

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

1.2 構建選址模型

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

(1)

(2)

(3)

(4)

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

(5)

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

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

2.1 模擬退火算法原理

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

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

2.2 模擬退火算法求解流程

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

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

(6)

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

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

(7)

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

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

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

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

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

2.3 模擬退火算法求解模型過程中的特點

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

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

2.4 遺傳算法原理及其求解模型過程中的特點

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

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

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

進一步，篩選出符合當前控制參數(shù)條件的染色體集。通過輪盤賭選擇，選出若干個適應度大的個體作為父代，在此基礎上進行交叉和變異操作，產(chǎn)生新一代種群P(gen+1)，保證優(yōu)良父代的染色體片段遺傳給后代的同時，變異跳出局部最優(yōu)，實現(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個區(qū)域的需求點及其需求量。為提高配送效率，有效降低服務成本，該企業(yè)決定建立若干配送中心。由于其車輛設備等硬件需要，配送中心備選地分別是膠州市、平度市、萊西市、招遠市、蓬萊市、棲霞市、諸城市、壽光市。從上述8個備選地中選擇3個建立生鮮農(nóng)產(chǎn)品配送中心，實現(xiàn)優(yōu)化[13-20]。

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

3.2 改進模擬退火算法選址過程

結合A公司實際的選址要求，運用改進后的模擬退火算法進行選址，選址具體過程如下。

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

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

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

表3 A公司各備選點單位存儲及固定費用

表4 A公司備選點到需求點單位運輸費用表 單位：元/t

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

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

3.2.3 通過適應度函數(shù)選出父代個體

(8)

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

(9)

(10)

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

3.2.4 通過輪盤賭選擇進行順序交叉和變異

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

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

采用Matlab求解，得到3個配送中心分別應該建在招遠市、諸城市和萊西市，最小總費用為1613952元。

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

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

3.3 改進前后模擬退火算法求解過程對比

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

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

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

4 結束語

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

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