基于遺傳算法物流配送中心選址研究

摘 要：物流配送中心選址一直是物流領(lǐng)域的重要研究方向，為了提高選址的準(zhǔn)確性，通過分析物流配送的運(yùn)輸成本、建設(shè)成本，并利用整數(shù)規(guī)劃法，建立單目標(biāo)規(guī)劃模型，最后再借助MATLAB軟件，運(yùn)用遺傳算法求解單目標(biāo)規(guī)劃模型，得到模型的全局最優(yōu)解。結(jié)果表明，遺傳算法對所建立模型的求解具有可行性、有效性。

關(guān)鍵詞：遺傳算法；配送中心；整數(shù)規(guī)劃

中圖分類號：U115 文獻(xiàn)標(biāo)志碼：A

DOI：10.13714/j.cnki.1002-3100.2024.19.007

Abstract： The location of logistics distribution centers has always been an important research direction in the field of logistics. In order to improve the accuracy of site selection， by analyzing the transportation cost and construction cost of logistics and distribution， and using the integer programming method， a single-objective programming model is established， and finally with the help of MATLAB software， the genetic algorithm is used to solve the established single-objective programming model， and the global optimal solution of the model is obtained. The example results show that the genetic algorithm is feasible and effective for solving the established objective programming model.

Key words： genetic algorithm; distribution center; integer programming

0 引 言

物流配送中心選址問題一直是物流領(lǐng)域所研究的重要問題[1]。早在20世紀(jì)初，德國學(xué)者Weber A[2]就提出了經(jīng)典Weber問題，提出通過確定唯一的倉庫，實(shí)現(xiàn)與多個客戶之間的總運(yùn)輸距離最小，該研究也是物流設(shè)施選址問題發(fā)展的重要開端。

物流設(shè)施選址問題通常都是NP-hard問題，目前選址模型建立主要包括定性方法和定量方法。其中最常用的定性方法有模糊綜合評判法、層次分析法、數(shù)據(jù)包絡(luò)分析法等，常用的定量研究方法主要包括重心法、網(wǎng)絡(luò)選址法、整數(shù)規(guī)劃法等[3]。倪衛(wèi)紅等[4]利用聚類重心法，研究了物流配送中心選址問題。李晶晶[5]構(gòu)建0～1混合整數(shù)規(guī)劃模型，確定了連鎖超市的配送中心的選址位置。冉昊杰等[6]設(shè)計了一種基于改進(jìn)的模擬退火算法的農(nóng)產(chǎn)品配送中心選址的方法。秦芳芳等[7]研究了物流配送中心選址問題。

配送中心的選址問題具有復(fù)雜性，而針對這一點(diǎn)啟發(fā)式算法具有較高的求解效率。因此，本文通過建立整數(shù)規(guī)劃模型，并求解該模型，最終證明了算法及模型的可行性與有效性。

1 模型的建立

1.1 模型假設(shè)

為了便于問題分析，我們對選址問題進(jìn)行了以下假設(shè)：（1）模型只考慮在單個周期內(nèi)的運(yùn)行情況，即時間成本、社會效益、政府政策等不在考慮之中；（2）每一個備選地址都有可能被選中；（3）各個客戶點(diǎn)需求量已知，且備選地址供貨量充足；（4）單位運(yùn)輸距離及運(yùn)輸成本已知且固定；（5）所有客戶點(diǎn)都會被覆蓋；（6）一個配送中心可以覆蓋多個客戶點(diǎn)；（7）一個客戶點(diǎn)只能有一個配送中心來配送；（8）各個客戶點(diǎn)均采取公路運(yùn)輸方式；（9）只考慮物流中心運(yùn)輸、建設(shè)成本，其他成本不考慮。

1.2 模型構(gòu)建

物流配送中心選址問題就是在滿足所有客戶點(diǎn)需求的情況下，選出配送中心，使所有費(fèi)用達(dá)到最小化。

目標(biāo)函數(shù)：

minF=qσdcC+qdcC+qα （1）

式中：M表示配送中心地址集合，N表示所有客戶點(diǎn)集合，q表示配送中心是否被選中，σ表示客戶點(diǎn)j是否有配送中心i配送，d表示客戶j到配送中心i的距離，c表示客戶j和配送中心i之間單位運(yùn)輸成本， C表示客戶j的需求量，d表示從發(fā)件中心到配送中心的距離，c表示到配送中心i的單位運(yùn)輸成本，C表示到配送中心i的發(fā)件數(shù)量，α表示配送中心i建設(shè)成本。

約束條件：

（1）從發(fā)件網(wǎng)點(diǎn)到配送中心的運(yùn)輸量要等于所有客戶點(diǎn)的需求量：

qC=C （2）

（2）配送中心的容量不小于所有客戶的需求量，其中V表示配送中心i的容量：

qV≥C （3）

（3）配送中心建設(shè)數(shù)量要小于配送中心最大可建設(shè)數(shù)量，其中Q表示最大可建設(shè)數(shù)量：

q≤Q， q=0，1 （4）

（4）每一個客戶點(diǎn)都只能有一個配送中心服務(wù)：

σ=1， j∈N， σ=0，1 （5）

（5）配送中心的容量要滿足客戶需求：

σC≤V， j∈N &nbs1EX3STyQVhQMiTZHf0qDUA==p; （6）

（6）沒有選為配送中心的地點(diǎn)不會有客戶：

σ≤q （7）

（7）所有客戶點(diǎn)的需求都會被滿足，不會出現(xiàn)某個客戶點(diǎn)沒配送的情況，其中n表示客戶點(diǎn)數(shù)量：

σ=n （8）

2 遺傳算法

遺傳算法（Genetic Algorithm，GA）[8]于20世紀(jì)60年代末期提出，主要有選擇、交叉、變異等操作。

2.1 編 碼

遺傳算法的編碼就是將實(shí)際問題的解映射到染色體中，因此編碼方式至關(guān)重要。本文用二進(jìn)制編碼，用0，1來代表基因，其中：0表示沒被選中，1表示被選中。

2.2 初始種群產(chǎn)生

產(chǎn)生100個個體，使其滿足編碼方案，構(gòu)成初始種群G：

2.3 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)實(shí)際上就是為了保證種群的優(yōu)良性而建立的一個評價個體優(yōu)劣的函數(shù)。適應(yīng)度函數(shù)由目標(biāo)函數(shù)F變換得到，目標(biāo)函數(shù)值越小，適應(yīng)度函數(shù)值就會越大，將自己的基因傳給下一代的可能性就會越高，反之亦然。基于此，本文建立適應(yīng)度函數(shù)如下：

2.4 選 擇

選擇就是通過計算種群個體適應(yīng)度，挑選適應(yīng)度高的優(yōu)秀個體。通過選擇，優(yōu)秀的個體就會保留下來，符合優(yōu)勝劣汰的自然規(guī)則。最后通過選擇將優(yōu)秀個體作為優(yōu)秀的種群保留下來。

2.5 交 叉

交叉就是從種群里選擇兩個染色體，隨機(jī)選取一部分基因片段進(jìn)行雜交重組。雜交能夠產(chǎn)生新一代更加優(yōu)良的個體，是種群進(jìn)化的重要手段。本文采用兩點(diǎn)交叉，隨機(jī)設(shè)置兩個交叉點(diǎn)，交換交叉點(diǎn)間的基因。

2.6 變 異

變異就是指將染色體上的基因在符合編碼要求的條件下進(jìn)行替換，從而形成新個體。變異就是為了獲取新個體，當(dāng)變異概率較小時，不利于新個體的出現(xiàn)，當(dāng)變異概率較大時，染色體的基因結(jié)構(gòu)不穩(wěn)定，不利于適應(yīng)度收斂。因此本文設(shè)置變異概率如下：

3 仿真分析

3.1 參數(shù)設(shè)置

假設(shè)在100*100平方千米的區(qū)域里，有發(fā)件中心一個坐標(biāo)為（50，50），可選7個配送中心，其坐標(biāo)、容量和成本如表1所示，有20個客戶，其坐標(biāo)和需求量如表2所示，配送成本為1元/噸公里，設(shè)置種群數(shù)量為100，最大迭代次數(shù)為1 000。

3.2 模型求解

利用MATLAB讀取上述數(shù)據(jù)并運(yùn)行30次，通過對該實(shí)例模型進(jìn)行求解最終得到2個較優(yōu)仿真結(jié)果方案如圖1所示。

最終得到配送方案如表3所示，其中，方案1選取1、2、3、5號配送中心，總成本為553.30萬元；方案2選取1、2、3號配送中心，總成本為575.02萬元。通過對比，最終決定選取方案1，總成本最低為553.30萬元。

4 結(jié) 論

本文通過建立整數(shù)規(guī)劃模型，并進(jìn)行求解得到穩(wěn)定、可靠的選址方案，證明該算法可用于物流配送中心的選址問題中，對物流配送中心選址具有重要實(shí)用價值和指導(dǎo)意義。但由于本文只考慮運(yùn)輸成本和建設(shè)成本，并沒有考慮其他因素，因此，在今后的研究中可以將社會效益、管理成本等條件加進(jìn)來，以便求出更合理的配送中心地址。

參考文獻(xiàn)：

[1] 周興龍，金鵬飛. 基于遺傳算法的單點(diǎn)物流選址問題探析[J]. 物流工程與管理，2010，32（7）：39-42.

[2] WEBER A. über den standort der industrien[M]. JCB Mohr， 1909.

[3] 李錦. 秸稈收儲中心選址及收集路徑優(yōu)化研究[D]. 鄭州：河南農(nóng)業(yè)大學(xué)，2021.

[4] 倪衛(wèi)紅，陳太. 基于聚類-重心法的應(yīng)急物流配送中心選址[J]. 南京工業(yè)大學(xué)學(xué)報（自然科學(xué)版），2021，43（2）：255-263.

[5] 李晶晶. 鮮農(nóng)產(chǎn)品冷鏈物流配送中心選址研究[D]. 太原：中北大學(xué)，2021.

[6] 冉昊杰，王宏智. 基于改進(jìn)模擬退火算法的生鮮農(nóng)產(chǎn)品配送中心選址[J]. 計算機(jī)與現(xiàn)代化，2022（10）：36-40.

[7] 秦芳芳，張珈瑞，張霆，等. 基于自適應(yīng)遺傳算法的物流配送中心選址[J]. 物流工程與管理，2023，45（8）：1-6.

[8] HOLLAND J H. Adaptation in naturation in natural and artificial systems[J]. The University of Michigan Press， 1975（1）：21-24.