基于遺傳算法的多設(shè)施選址問題研究

摘" 要：文章采用數(shù)學(xué)建模和遺傳算法相結(jié)合的方式對(duì)考慮貨物分配的多設(shè)施選址問題進(jìn)行求解，并且在研究中運(yùn)用正交實(shí)驗(yàn)法優(yōu)化參數(shù)設(shè)定，在算法中運(yùn)用輪盤賭選擇法保證染色體的多樣性，運(yùn)用精英保留策略防止優(yōu)良基因的丟失，最終達(dá)到使企業(yè)物流以更低成本和更高效率運(yùn)作的目的，所給出的算例驗(yàn)證了算法在求解上述問題的有效性。

" 關(guān)鍵詞：遺傳算法；多設(shè)施選址；精英保留策略；算法優(yōu)化

" 中圖分類號(hào)：F252" " 文獻(xiàn)標(biāo)志碼：A" " DOI：10.13714/j.cnki.1002-3100.2024.15.002

Abstract： In this paper， the mathematical modeling and genetic algorithm（GA）are used to solve the multi-facility location problem considering goods distribution， and the orthogonal experiment method is applied to optimize the parameters of GA. The roulette wheel selection strategy is used in GA to generating the next generation of individuals， thereby ensuring population diversity. The elitist preservation strategy is designed in GA to prevent the loss of the good gene. The ultimate goal of the above research is to enable enterprises to achieve low-cost and efficient operation， and the provided experiments verify the effectiveness of the algorithm in solving the above problem.

Key words： genetic algorithm; multi-facilities location; elitist preservation strategy; algorithm optimization

0" 引" 言

" 在企業(yè)中，設(shè)施選址是企業(yè)建立和經(jīng)營(yíng)的第一步，如果不能采用正確的方法獲得良好的選址方案，其產(chǎn)生的負(fù)面影響將不能用建設(shè)完成后的管理與完善來彌補(bǔ)。所以應(yīng)當(dāng)更注重設(shè)施選址，將設(shè)施選址與管理并重，從而提高企業(yè)的運(yùn)營(yíng)效率。

" 目前很多專家學(xué)者都針對(duì)設(shè)施選址問題開展了研究。由于傳統(tǒng)的優(yōu)化算法很難求解日益復(fù)雜的NP-hard問題，1975年Holland第一次在他的文章中提到遺傳算法（Genetic Algorithm，GA），才讓這類復(fù)雜問題的解決有所突破，所以基于元啟發(fā)式算法的近似求解算法成為目前和未來解決復(fù)雜設(shè)施選址問題的主要方向。張振[1]對(duì)縣域低碳物流選址及配送路徑優(yōu)化問題進(jìn)行研究，結(jié)合模擬退火算法與遺傳算法設(shè)計(jì)提出二階段混合啟發(fā)式算法，通過MATLAB進(jìn)行算法編程，求解得出最優(yōu)方案，驗(yàn)證了該模型與算法的可靠性及有效性。馮瑛杰等[2]運(yùn)用灰色預(yù)測(cè)模型對(duì)需求進(jìn)行預(yù)測(cè)，通過非支配排序遺傳算法對(duì)模型進(jìn)行求解。趙培忻等[3]提出了一類基于圖論的新型聚類算法并將其應(yīng)用于物流系統(tǒng)中的多設(shè)施選址問題。茆劍[4]將具有較強(qiáng)局部尋優(yōu)性能的模擬退火算法與具有較強(qiáng)全局搜索性能的遺傳算法相結(jié)合，以此求解了供應(yīng)鏈物流設(shè)施選址優(yōu)化問題。Jolai et al[5]使用多目標(biāo)粒子群優(yōu)化算法尋找動(dòng)態(tài)設(shè)施布局的最優(yōu)解，實(shí)驗(yàn)表明該算法具有魯棒性。Luis et al[6]研究考慮多種容量約束的平面多設(shè)施選址分配問題，提出貪心隨機(jī)自適應(yīng)搜索算法（Greedy Randomized Adaptive Search Procedure， GRASP）。王繼嫻[7]對(duì)多目標(biāo)優(yōu)化的電動(dòng)汽車充電站選址問題進(jìn)行研究，采用層次分析法將多目標(biāo)優(yōu)化模型轉(zhuǎn)化為單目標(biāo)函數(shù)，并利用雞群算法進(jìn)行求解，案例驗(yàn)證了該方法的實(shí)用性和有效性。

" 本文采用數(shù)學(xué)建模和元啟發(fā)式算法相結(jié)合的方式對(duì)考慮貨物分配的多設(shè)施選址問題進(jìn)行研究，合理運(yùn)用遺傳算法對(duì)關(guān)于多設(shè)施選址的這類NP-hard問題進(jìn)行求解，從而獲得問題的近似全局最優(yōu)化方案，為多設(shè)施選址的問題提供有效的解決途徑。

1" 問題描述與數(shù)學(xué)模型

1.1" 問題描述。本文所研究的考慮貨物分配的多設(shè)施選址問題描述如下：某企業(yè)需要對(duì)N個(gè)需求點(diǎn)供貨，且各需求點(diǎn)的產(chǎn)品需求量是確定的，擬建設(shè)k個(gè)工廠開展生產(chǎn)，以滿足供貨需要，現(xiàn)通過一些常規(guī)的方法確定了M個(gè)候選點(diǎn)，需要從這M個(gè)候選點(diǎn)中確定k個(gè)工廠的建設(shè)位置，并對(duì)k個(gè)工廠與N個(gè)需求點(diǎn)之間的供貨關(guān)系進(jìn)行優(yōu)化，以從整體上提高物流效率、降低物流成本。本文假定在不同運(yùn)輸模式下，單車運(yùn)輸和單位距離運(yùn)輸成本是一樣的。

" 優(yōu)化目標(biāo)：從M個(gè)候選點(diǎn)中選擇k個(gè)地點(diǎn)作為工廠建設(shè)位置，并為各個(gè)工廠的每車（集裝箱）貨物分配運(yùn)往的需求點(diǎn)，使總的物流成本最低，其中，將貨物以車（集裝箱）為單位進(jìn)行分配優(yōu)化的好處在于，一方面可以將問題離散化和簡(jiǎn)化，另一方面也符合企業(yè)物流運(yùn)輸模式。

2" 算法實(shí)現(xiàn)

2.1" 輸入遺傳算法的變量。該問題相關(guān)參數(shù)如下：N：區(qū)域中的需求點(diǎn)（客戶）數(shù)量；M：區(qū)域中工廠候選點(diǎn)數(shù)量；k：最終確定建設(shè)的工廠的候選點(diǎn)數(shù)量k≤M；Q：種群的規(guī)模；C：迭代次數(shù)；m：進(jìn)化淘汰加速指數(shù)；Pc：交叉概率；Pm：變異概率；Posm：候選點(diǎn)坐標(biāo)；Posn：需求點(diǎn)坐標(biāo)；D：距離矩陣；T：?jiǎn)挝贿\(yùn)輸成本；FF：各候選點(diǎn)建設(shè)的固定成本；VV：可變成本（單位貨物的生產(chǎn)成本）；nn：各需求點(diǎn)貨物需求量（集裝箱數(shù)量）；W：每個(gè)方案的成本。

2.2" 算法設(shè)計(jì)。遺傳算法的主要流程如圖1所示。算法的各步驟具體內(nèi)容如下：

第一步：初始化：隨機(jī)生成初始種群、設(shè)置算法參數(shù)

" 第二步：計(jì)算初始種群各個(gè)體的適應(yīng)度

因?yàn)閱栴}的目標(biāo)函數(shù)是方案的成本，所以先計(jì)算出每個(gè)個(gè)體的成本，再將目標(biāo)函數(shù)“成本”進(jìn)行處理，轉(zhuǎn)化為后面迭代過程中所需要用到的適應(yīng)度函數(shù)。

（1）計(jì)算成本?？偝杀景ńㄔO(shè)成本F、可變成本V、運(yùn)輸成本L。

（2）計(jì)算適應(yīng)度函數(shù)。首先構(gòu)造適應(yīng)度函數(shù)，由于目標(biāo)函數(shù)成本是越小越好，而遺傳算法是默認(rèn)適應(yīng)度值越高越好，本文采用“取倒數(shù)”和“歸一化、取差值”的方法來對(duì)目標(biāo)函數(shù)進(jìn)行處理。

" 第三步：選" 擇

" 本文用輪盤賭法來選擇個(gè)體，以保證子代染色體的多樣性。該方法是當(dāng)前最普遍的一種遺傳算法選擇方法，其中，染色體的適應(yīng)度值越高，被選擇的幾率就越大。

" 交叉是為了模仿個(gè)體在進(jìn)化中發(fā)生的基因重組，目的是更新群體中的個(gè)體，優(yōu)化后代的適應(yīng)度值。本文算法采用的是單點(diǎn)交叉。單點(diǎn)交叉是指在任意選定的位點(diǎn)上切割兩個(gè)個(gè)體，并對(duì)其一邊進(jìn)行交換，從而得到兩個(gè)新的個(gè)體。單點(diǎn)交叉的混合速率要低一些，由于只把染色體分為兩個(gè)部分進(jìn)行交叉，所以對(duì)個(gè)體也會(huì)產(chǎn)生更少的損害。如圖3所示為單點(diǎn)交叉示意圖。

第五步：變" 異

" 變異是模擬生物進(jìn)化過程中的染色體的基因突變現(xiàn)象，目的是增強(qiáng)群體中個(gè)體的多樣性。本文算法采用的是位點(diǎn)變異。是將某一特定位置的基因值用另一基因的等位基因值替代。

第六步：適應(yīng)度評(píng)價(jià)

" 此次計(jì)算是為了根據(jù)適應(yīng)度獲取當(dāng)前代的最優(yōu)解和全局最優(yōu)解。當(dāng)前代最優(yōu)解保存至pbest中。保存下來有兩個(gè)目的，第一是為了“精英保留”時(shí)方便引用；第二是為了取得問題的最終解，最終的全局近似最優(yōu)解gbest就是pbest中的最優(yōu)方案。

第七步：采用精英保留策略生成新的種群

（1）將當(dāng)前種群更新至下一代。若算法設(shè)置的迭代次數(shù)為C次，初始群體為第一代，那么迭代C次就是由2：C+1代。每次迭代完成后都將本代的種群作為下一代的初始種群，這就是初始化種群，迭代到C+1代為止。

（2）使用精英保留策略改善算法。精英保留（Elitist Preservation）策略是De Jong針對(duì)遺傳算法提出來的。對(duì)遺傳算法來說，能否收斂到全局最優(yōu)解是其首要問題。但是遺傳算法中的染色體，并不一定真實(shí)地反映了待求解問題的本質(zhì)，因此各個(gè)染色體之間不一定是相互獨(dú)立的，如果只是簡(jiǎn)單地進(jìn)行交叉和變異，很可能把優(yōu)良的組合給破壞了，這樣就沒有達(dá)到累積較好基因的目的，反而會(huì)造成優(yōu)良基因丟失。為了避免最優(yōu)個(gè)體會(huì)因?yàn)榻徊婊蜃儺惒僮鞫黄茐?，?dǎo)致遺傳算法不能收斂到全局最優(yōu)解。

De Jong在其博士論文中提出了精英選擇策略，也稱為精英保留策略。該策略的思想是，把群體在進(jìn)化過程中迄今出現(xiàn)的最好個(gè)體（稱為精英個(gè)體）不進(jìn)行配對(duì)交叉而直接復(fù)制到下一代中。有兩種做法：一種做法是將精英個(gè)體放入到種群中，即種群規(guī)模為Q+1；另一種做法是保持種群規(guī)模，即使用精英個(gè)體替換掉種群中的某個(gè)其他個(gè)體。精英保留策略對(duì)改進(jìn)標(biāo)準(zhǔn)遺傳算法的全局收斂能力產(chǎn)生了重大作用，Rudolph已經(jīng)從理論上證明了具有精英保留的標(biāo)準(zhǔn)遺傳算法是可以做到全局收斂的。

" 本文算法采用的是保持種群規(guī)模，在初始化種群結(jié)束后，在種群中隨機(jī)選擇一個(gè)個(gè)體，并且使用精英個(gè)體將其換掉。

3" 算例分析

3.1" 算例生成。根據(jù)前文對(duì)遺傳算法變量的定義，準(zhǔn)備算例數(shù)據(jù)如下：

（1）候選點(diǎn)坐標(biāo)PosmM=12為：[89.69 41.34；19.20 37.01；54.69 65.28；84.99 83.48；28.38 9.85；82.81 75.71；36.61 19.76；57.72 77.77；84.13 90.44；18.61 0.03；40.12 18.98；53.01 38.40]。

（2）需求點(diǎn)坐標(biāo)PsonN=20為：[58.53 79.84；66.33 78.91；1.79 90.38；19.21 83.55；65.98 36.76；35.56 75.02；84.40" 53.23；26.40 71.66；13.68 31.42；60.52 49.41；58.53 79.84；66.33 78.91；1.79 90.38；1.10 57.68；29.96 4.45；3.21 6.05；18.78 9.16；91.27 52.24；10.18 49.64；99.45 45.61；88.57 62.65；60.24 98.97；74.93 62.03；1.10 57.68；29.96 4.45；3.21 6.05]。

" （3）單位運(yùn)輸成本T=78。

" （4）各候選點(diǎn)建設(shè)的固定成本FF和可變成本VV如表1所示。

" （5）各需求點(diǎn)貨物需求量NN（集裝箱）如表2所示。

3.2" 參數(shù)選擇。在之前算法運(yùn)行的基礎(chǔ)上，選取種群的個(gè)數(shù)Q、迭代次數(shù)C、加速指數(shù)m、交叉概率Pc、變異概率Pm這五個(gè)較為顯著的影響因素，以目標(biāo)函數(shù)成本為衡量標(biāo)準(zhǔn)，進(jìn)一步研究這五個(gè)因素對(duì)方案成本的影響，并選出最優(yōu)組合。因素水平如表3所示。

根據(jù)因素水平表來設(shè)計(jì)正交實(shí)驗(yàn)，選擇L25_5_6的正交表。正交實(shí)驗(yàn)試驗(yàn)結(jié)果如表4所示。

可以看出最優(yōu)組合為A1B5C5D4E1，代入MATLAB得gbest_W=79 994.97，與正交實(shí)驗(yàn)的25組實(shí)驗(yàn)結(jié)果相比也是最好的。由此確定遺傳算法容易獲得最優(yōu)解的條件為Q=50，C=3 000，m=10，Pc=0.8，Pm=0.05。

3.3" 精英保留策略改善情況分析。將遺傳算法每一次迭代收斂到近似最優(yōu)解的過程繪制出來進(jìn)行比較。標(biāo)準(zhǔn)遺傳算法最優(yōu)解收斂過程圖如圖4所示。使用精英保留策略的遺傳算法最優(yōu)解收斂過程圖如圖5所示。

由圖4和圖5對(duì)比看出：（1）使用精英保留策略之后GA的解更優(yōu)；（2）標(biāo)準(zhǔn)GA迭代的收斂的時(shí)間過早，結(jié)合前一點(diǎn)，可以認(rèn)為GA并沒有達(dá)到全局最優(yōu)，而是陷入了局部最優(yōu)。

綜上所述，精英保留策略確實(shí)能夠極大地提高標(biāo)準(zhǔn)遺傳算法搜索全局最優(yōu)解的能力，達(dá)到了本文優(yōu)化算法的目的。

3.4" 運(yùn)算結(jié)果分析。在應(yīng)用正交實(shí)驗(yàn)得出的遺傳算法容易獲得最優(yōu)解的條件Q=50，C=3 000，m=10，Pc=0.8，Pm=0.05的情況下，本文進(jìn)一步對(duì)遺傳算法是否能有效求解多設(shè)施選址這一問題進(jìn)行驗(yàn)證。驗(yàn)證過程如下：

首先，根據(jù)前述算例數(shù)據(jù)，隨機(jī)生成10組問題的初始解作為優(yōu)化前的比較對(duì)象，每組初始解所對(duì)應(yīng)的成本如表5所示。

根據(jù)本文算法設(shè)計(jì)的內(nèi)容和前述算例數(shù)據(jù)，在MATLAB中運(yùn)行算法，其迭代曲線如圖6所示。并且得到優(yōu)化方案如下。

（1）在12個(gè)候選點(diǎn)選擇建設(shè)工廠的候選點(diǎn)編號(hào)：1 2 6 8 10 12。

（2）每個(gè)工廠生產(chǎn)量如表6所示。

（3）各需求點(diǎn)貨物需求量：NN=2 2 1 1 1 1 2 2 4 4 1 4 1 1 2 1 5 5 2 2。

" （4）所有需求點(diǎn)的需求量之和為44，也就是6個(gè)工廠共產(chǎn)出44車（集裝箱）貨物，各貨物來源工廠編號(hào)如下：

gbest=8 8 8 8 8 8 12 8 1 1 8 8 2 2 2 2 12 12 12 12 2 10 10 10 10 10 10 1 1 2 1 1 1 1 1 6 6 6 6 6 8 6 6。

貨物的分配依據(jù)第1～2箱貨物送往1號(hào)需求點(diǎn)，第3～4箱貨物送往2號(hào)需求點(diǎn)，依此類推。此時(shí)得到了算法最終解的gbest_W為79 994.97。和表5中的數(shù)據(jù)對(duì)比后可以明顯看出，在算法條件都取最優(yōu)條件的情況下，應(yīng)用了遺傳算法得到的解的成本值比隨機(jī)生成解的成本值要低很多。

" 由此也進(jìn)一步驗(yàn)證了遺傳算法的優(yōu)化性能、收斂性能是良好的，并且這種有效性可以用于多設(shè)施選址問題的研究。綜上，遺傳算法是一種求解多設(shè)備選址問題的有效方法。

4" 結(jié)" 論

本文針對(duì)多設(shè)施選址問題開展了研究，構(gòu)建了一種問題求解模型，提出了一種采用精英保留策略的遺傳算法對(duì)其進(jìn)行求解，并采用算例對(duì)算法的有效性和精英保留策略的效果進(jìn)行了驗(yàn)證。算例結(jié)果表明，所提出的算法能夠有效解決企業(yè)多設(shè)施選址問題，且精英保留策略應(yīng)用效果顯著。綜上所述，本文的研究為當(dāng)前多設(shè)施選址問題的解決提供了一種有效途徑。

參考文獻(xiàn)：

[1] 張振. 考慮碳排放的縣鄉(xiāng)村三級(jí)物流網(wǎng)絡(luò)選址與路徑優(yōu)化研究[D]. 北京：北京交通大學(xué)，2022.

[2] 馮瑛杰，謝慶紅. 基于遺傳算法的應(yīng)急物流設(shè)施選址與調(diào)度[J]. 科技和產(chǎn)業(yè)，2021，21（9）：102-106.

[3] 趙培忻，張存銓，趙炳新. 基于新型圖論聚類法的物流系統(tǒng)多設(shè)施選址策略研究[J]. 中國(guó)管理科學(xué)，2012，20（6）：149-153.

[4] 茆劍. 基于混合遺傳算法的供應(yīng)鏈物流設(shè)施選址優(yōu)化[D]. 南京：河海大學(xué)，2006.

[5]" JOLAI F， MOGHADDAM T Z， TAGHIPOUR M. A multi-objective particle swarm optimisation algorithm for unequal sized dynamic faciproblem with pickup/drop-off locations[J]. International Journal of Production Research， 2012，50（15）：4279-4293.

[6]" LUIS M， RAMLI F M， LIN A. A greedy heuristic algorithm for solving the capacitated planar multi-facility location-allocation problem[J]. AIP Conference Proceedings， 2016（1）：040010.

[7] 王繼嫻. 基于多目標(biāo)優(yōu)化的電動(dòng)汽車充電站選址研究[D]. 北京：華北電力大學(xué)，2022.

收稿日期：2023-08-16

基金項(xiàng)目：甘肅農(nóng)業(yè)大學(xué)“農(nóng)林經(jīng)濟(jì)管理+農(nóng)商互聯(lián)與數(shù)智農(nóng)業(yè)發(fā)展研究團(tuán)隊(duì)”資助項(xiàng)目；甘肅省科技廳軟科學(xué)專項(xiàng)項(xiàng)目“甘肅‘兩州一縣’易地扶貧搬遷農(nóng)戶生計(jì)資本變遷及搬遷效能研究”（21CX6ZA077）

作者簡(jiǎn)介：郝浩浩（1999—），男，甘肅天水人，甘肅農(nóng)業(yè)大學(xué)財(cái)經(jīng)學(xué)院碩士研究生，研究方向：農(nóng)業(yè)管理；段小紅（1968—），女，陜西華陰人，甘肅農(nóng)業(yè)大學(xué)財(cái)經(jīng)學(xué)院，副教授，碩士生導(dǎo)師，研究方向：農(nóng)林經(jīng)濟(jì)統(tǒng)計(jì)及農(nóng)村社會(huì)學(xué)。

引文格式：郝浩浩，段小紅. 基于熵權(quán)TOPSIS法的甘肅省農(nóng)產(chǎn)品物流能力評(píng)價(jià)研究[J]. 物流科技，2024，47（15）：10-13.