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

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

" 關鍵詞：遺傳算法；多設施選址；精英保留策略；算法優化

" 中圖分類號：F252" " 文獻標志碼：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" 引" 言

" 在企業中，設施選址是企業建立和經營的第一步，如果不能采用正確的方法獲得良好的選址方案，其產生的負面影響將不能用建設完成后的管理與完善來彌補。所以應當更注重設施選址，將設施選址與管理并重，從而提高企業的運營效率。

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

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

1" 問題描述與數學模型

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

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

2" 算法實現

2.1" 輸入遺傳算法的變量。該問題相關參數如下：N：區域中的需求點（客戶）數量；M：區域中工廠候選點數量；k：最終確定建設的工廠的候選點數量k≤M；Q：種群的規模；C：迭代次數；m：進化淘汰加速指數；Pc：交叉概率；Pm：變異概率；Posm：候選點坐標；Posn：需求點坐標；D：距離矩陣；T：單位運輸成本；FF：各候選點建設的固定成本；VV：可變成本（單位貨物的生產成本）；nn：各需求點貨物需求量（集裝箱數量）；W：每個方案的成本。

2.2" 算法設計。遺傳算法的主要流程如圖1所示。算法的各步驟具體內容如下：

第一步：初始化：隨機生成初始種群、設置算法參數

" 第二步：計算初始種群各個體的適應度

因為問題的目標函數是方案的成本，所以先計算出每個個體的成本，再將目標函數“成本”進行處理，轉化為后面迭代過程中所需要用到的適應度函數。

（1）計算成本。總成本包括建設成本F、可變成本V、運輸成本L。

（2）計算適應度函數。首先構造適應度函數，由于目標函數成本是越小越好，而遺傳算法是默認適應度值越高越好，本文采用“取倒數”和“歸一化、取差值”的方法來對目標函數進行處理。

" 第三步：選" 擇

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

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

第五步：變" 異

" 變異是模擬生物進化過程中的染色體的基因突變現象，目的是增強群體中個體的多樣性。本文算法采用的是位點變異。是將某一特定位置的基因值用另一基因的等位基因值替代。

第六步：適應度評價

" 此次計算是為了根據適應度獲取當前代的最優解和全局最優解。當前代最優解保存至pbest中。保存下來有兩個目的，第一是為了“精英保留”時方便引用；第二是為了取得問題的最終解，最終的全局近似最優解gbest就是pbest中的最優方案。

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

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

（2）使用精英保留策略改善算法。精英保留（Elitist Preservation）策略是De Jong針對遺傳算法提出來的。對遺傳算法來說，能否收斂到全局最優解是其首要問題。但是遺傳算法中的染色體，并不一定真實地反映了待求解問題的本質，因此各個染色體之間不一定是相互獨立的，如果只是簡單地進行交叉和變異，很可能把優良的組合給破壞了，這樣就沒有達到累積較好基因的目的，反而會造成優良基因丟失。為了避免最優個體會因為交叉或變異操作而被破壞，導致遺傳算法不能收斂到全局最優解。

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

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

3" 算例分析

3.1" 算例生成。根據前文對遺傳算法變量的定義，準備算例數據如下：

（1）候選點坐標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）需求點坐標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）單位運輸成本T=78。

" （4）各候選點建設的固定成本FF和可變成本VV如表1所示。

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

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

根據因素水平表來設計正交實驗，選擇L25_5_6的正交表。正交實驗試驗結果如表4所示。

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

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

由圖4和圖5對比看出：（1）使用精英保留策略之后GA的解更優；（2）標準GA迭代的收斂的時間過早，結合前一點，可以認為GA并沒有達到全局最優，而是陷入了局部最優。

綜上所述，精英保留策略確實能夠極大地提高標準遺傳算法搜索全局最優解的能力，達到了本文優化算法的目的。

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

首先，根據前述算例數據，隨機生成10組問題的初始解作為優化前的比較對象，每組初始解所對應的成本如表5所示。

根據本文算法設計的內容和前述算例數據，在MATLAB中運行算法，其迭代曲線如圖6所示。并且得到優化方案如下。

（1）在12個候選點選擇建設工廠的候選點編號：1 2 6 8 10 12。

（2）每個工廠生產量如表6所示。

（3）各需求點貨物需求量：NN=2 2 1 1 1 1 2 2 4 4 1 4 1 1 2 1 5 5 2 2。

" （4）所有需求點的需求量之和為44，也就是6個工廠共產出44車（集裝箱）貨物，各貨物來源工廠編號如下：

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。

貨物的分配依據第1～2箱貨物送往1號需求點，第3～4箱貨物送往2號需求點，依此類推。此時得到了算法最終解的gbest_W為79 994.97。和表5中的數據對比后可以明顯看出，在算法條件都取最優條件的情況下，應用了遺傳算法得到的解的成本值比隨機生成解的成本值要低很多。

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

4" 結" 論

本文針對多設施選址問題開展了研究，構建了一種問題求解模型，提出了一種采用精英保留策略的遺傳算法對其進行求解，并采用算例對算法的有效性和精英保留策略的效果進行了驗證。算例結果表明，所提出的算法能夠有效解決企業多設施選址問題，且精英保留策略應用效果顯著。綜上所述，本文的研究為當前多設施選址問題的解決提供了一種有效途徑。

參考文獻：

[1] 張振. 考慮碳排放的縣鄉村三級物流網絡選址與路徑優化研究[D]. 北京：北京交通大學，2022.

[2] 馮瑛杰，謝慶紅. 基于遺傳算法的應急物流設施選址與調度[J]. 科技和產業，2021，21（9）：102-106.

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

[4] 茆劍. 基于混合遺傳算法的供應鏈物流設施選址優化[D]. 南京：河海大學，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] 王繼嫻. 基于多目標優化的電動汽車充電站選址研究[D]. 北京：華北電力大學，2022.

收稿日期：2023-08-16

基金項目：甘肅農業大學“農林經濟管理+農商互聯與數智農業發展研究團隊”資助項目；甘肅省科技廳軟科學專項項目“甘肅‘兩州一縣’易地扶貧搬遷農戶生計資本變遷及搬遷效能研究”（21CX6ZA077）

作者簡介：郝浩浩（1999—），男，甘肅天水人，甘肅農業大學財經學院碩士研究生，研究方向：農業管理；段小紅（1968—），女，陜西華陰人，甘肅農業大學財經學院，副教授，碩士生導師，研究方向：農林經濟統計及農村社會學。

引文格式：郝浩浩，段小紅. 基于熵權TOPSIS法的甘肅省農產品物流能力評價研究[J]. 物流科技，2024，47（15）：10-13.