求解無容量設施選址問題的改進禁忌搜索算法

摘" 要：無容量限制設施選址問題（Uncapacitated Facility Location Problem，UFLP）屬于經典組合優化NP-Hard問題，為了快速有效地求解UFLP，文章采用禁忌搜索算法來求解無容量設施選址問題。首先，描述了局部搜索中用來求解該問題的三種操作算子，進一步增強其全局搜索性能。其次，禁忌搜索算法在尋優過程中對初始解具有一定的依賴性，運用隨機化與貪心算法相結合的方法來生成初始解，通過引入動態禁忌列表的方法，避免搜索到重復表中的解，并對改進后禁忌搜索算法的有效性進行了評估。最后，通過求解經典算例進行測試和其他算法進行比較的方式，驗證了該算法用來求解UFLP的可行性和有效性。

關鍵詞：無容量設施選址問題；禁忌搜索算法；貪心算法；禁忌列表

" 中圖分類號：F253" " 文獻標志碼：A" " DOI：10.13714/j.cnki.1002-3100.2025.03.003

Abstract： The Uncapacitated Facility Location Problem（UFLP）belongs to the classical combinatorial optimization NP-Hard problem. In order to solve the UFLP quickly and efficiently， this paper uses tabu search algorithm to solve the Uncapacitated Facility Location Problem. Firstly， three operators used to solve the problem in local search were described to further enhance the global search performance. Secondly， the tabu search algorithm has a certain dependence on the initial solution in the optimization process， and the method of combining randomization and greedy algorithm is used to generate the initial solution， and the dynamic tabu list is introduced to avoid searching the solution in the repeated table. The effectiveness of the improved tabu search algorithm is evaluated. Finally， the feasibility and effectiveness of the proposed algorithm for solving UFLP are verified by solving classical examples and comparing with other algorithms.

Key words： Uncapacitated Facility Location Problem; tabu search algorithm; greedy algorithms; tabu list

0" 引" 言

無容量限制設施選址問題（Uncapacitated Facility Location Problem，UFLP）是組合優化問題中研究最廣泛的問題之一。

UFLP的主要目標是嘗試找到開放不確定數量的設施，以最大限度地減少設施開放成本和服務成本之和，目前UFLP在物流運輸[1]、資源配置[2]領域具有重要的應用價值。解決這類問題相關的文獻也非常豐富，主要的方法可以分為兩大類：精確算法和啟發式算法。精確算法[3]雖然能求得問題的最優解，但UFLP是一個NP-Hard問題，因此求解速度相對較慢。精確算法通常被應用在處理較小規模的優化任務上，這是由于隨著任務的擴展，其時間復雜性將以指數級別遞增，從而使得解答這些問題變得愈發艱巨。為了方便求解更大規模的優化問題，這時智能算法成為首選。求解無容量限制設施選址問題的智能算法主要有：遺傳算法、差分進化算法和烏鴉搜索算法、算數優化算法。

智能算法雖然具有搜索速度快，在有限時間內能夠找到問題滿意解的優點，但其容易陷入局部最優解。借鑒不同算法的優點使其相互融合，設計新的混合算法用于解決組合優化問題，這已經成為優化領域的主要研究方向。Huseyin et al.[4]提出一種混合螢火蟲-遺傳搜索算法求解UFLP，采用螢火蟲算法進行迭代更新，使用遺傳算法對更新后的解進行進一步優化，以獲得更好的解決方案。Alidaee et al.[5]提出一種直接應用于具有二進制搜索空間問題的優化技術，使用了不同的交叉技術和變異操作來增強基本散射搜索算法的全局搜索能力和局部搜索能力。

" 現在禁忌搜索算法的運用也越來越廣泛，例如作業車間調度問題[6]和醫療設施選址問題[7]上都有用到禁忌搜索算法去求解。禁忌搜索算法[8]可將最近若干步內所得到的解存儲在禁忌表中，從而強制搜索避免再次重復表中的解。它具有參數少、穩定性強、收斂速度快等優點。本文設計了一種動態禁忌列表的禁忌搜索算法求解UFLP，在禁忌搜索算法的基礎上，禁忌列表在不同的迭代區間有不同的禁忌長度。初始解運用隨機化選擇開放設施與貪心聚類算法結合的方法生成，其次設計了一個禁忌搜索的優化過程，目的是為了圍繞得到的初始解進行強化搜索。禁忌搜索過程使用設施點移動擴大領域空間和增量評估技術進行快速鄰域檢查。最后，通過實驗求解一些經典UFLP算例，驗證了該算法的可行性和有效性。

1" 無容量限制設施選址問題

無容量限制設施選址問題與實際背景相結合，已被廣泛應用于很多領域的設施選址優化，如：不確定環境下設施選址問題[9]和農產品供應鏈網絡設計[10]。假設所有候選設施的容量都是無限的，要求每個客戶都應由一個且只能由一個設施提供服務，目標是找到一套開放設施，并在設施與客戶之間找到合理的分配方案，使總服務成本和總開放設施成本之和最小化。c表示客戶i由設施j提供服務時的成本，f表示設施j的開放固定成本。數學模型可以描述為：

minZ=cx+fy" " " " " " " " " " " " " " " " " " " " "（1）

s.t. x=1， j=1，…，n" " " " " " " " " " " " " " " " " " " " " " " " "（2）

x-y≤0， i=1，…，m" " " " " " " " " " " " " " " " " " " " " " " " （3）

x∈0，1" " i=1，…，m， j=1，…，n" " " " " " " " " " " " " " " " " " （4）

y∈0，1" " j=1，…，n" " " " " " " " " " " " " " " " " " " " " " "（5）

其中：式（1）為目標函數，即總費用；式（2）確保每個客戶由一個且僅由一個設施提供服務；式（3）確保只有在設施被開放時客戶才能獲得服務式；式（4）、式（5）是二元變量，在0和1之間選取。如果客戶i被設施j提供服務時，則x等于1，否則為0；如果設施j開放使用，則y等于1，否則為0。

2" 求解UFLP的禁忌搜索算法

2.1" 初始解的生成

為了確保更好地探索初始解決方案，為每個客戶分配了不同的設施點位置且每一個客戶只由一個設施點服務。此外，通過根據開放設施點的數量增加或減少，產生不同的起始解決方案，可以實現更好的多樣化。在所有設施點中選取一些作為開放的設施點，這個步驟使用伯努利過程，以隨機選取位置開始求解。因此，對于每一個設施點在0，1范圍內生成一個隨機數，如果該數字大于或等于0.5，則將其賦值為1（為開放設施），否則為0（為候選設施）。根據運輸成本的大小，每一個客戶選擇距離最近的開放設施點。

" UFLP中設施頂點集J可劃分為兩個子集，這兩個子集分別是已選開放設施集V和候選封閉設施集V。因此，將禁忌算法探索的搜索空間定義為所有可能的J劃分為2個不相交子集，即J=V∪V。

2.2" 鄰域結構

" 找到了一個初始最優解，對當前解進行一個鄰域動作可以得到所有解的集合，從而得到一個更大的解空間。如果只單純添加或減少開放設施點數量將不再降低總成本，則停止。第二階段是局部搜索方法，其中利用開放設施點和候選設施點相互交換的方式，用這種操作方式降低總成本。V中的設施點為客戶提供服務；V中的設施點對客戶不提供服務。本文考慮3種可能的簡單改進措施：（1）在當前解中交換兩個設施點的位置。從開放設施集合V中選取一個設施點與候選設施集合V中一個設施點進行交換；（2）在當前解中增加一個開放設施點。從候選設施集合V移動一個設施點到開放設施集合V；（3）在當前解中減少一個開放設施點。將其中一個設施點從開放設施集合V移到候選設施集合V。

" 以上在鄰域搜索的過程中，交換兩個設施，增加一個設施點和減少一個設施點，操作步驟如圖1所示。

2.3" 動作選擇策略

動作選擇策略被看作為一個設施點從打開到關閉或從關閉到打開的狀態更改。因此，一個移動可以從當前的解決方案中得到一個新的解決方案。在禁忌搜索的每次迭代中，首先對當前解選取兩個設施點進行交換，在V中選擇一個非禁忌設施點g與V中的一個非禁忌的設施點h互換，計算出目標函數變化值為Δg，h；然后對當前解中增加一個設施點，操作步驟類似上一步，從V中選出一個非禁忌的設施點h，并將其從V移動到V，計算出目標函數變化值為Δg，h；最后，在V中選擇一個非禁忌設施點g，并將其從V移動到V，計算出目標函數變化值為Δg，h。最后，比較這三個目標函數變化值，選取目標函數值最小的那一步操作。

" 在兩個或兩個以上的非禁忌設施點移動后，具有相同的最小的函數目標值情況下，將隨機選擇其中一個。一個設施點從它的原始集合更改為另一個集合，它將被劃分到禁忌列表里，在此期間設施g或h被禁止移動。一個簡單的解禁標準被應用，允許一個頂點被選擇，盡管是禁忌狀態下，如果它引導的解決方案比當前的最佳解決方案更好，就會達到解禁的標準。當達到最大允許的迭代次數時，禁忌程序進程將停止。

2.4" 禁忌列表和禁忌期限

" 在禁忌搜索中，引入了一個禁忌列表，以禁止重新訪問以前訪問過的解決方案。在本文的算法中，每當一個設施從開放設施點集合移到相反的集合時，禁止在一定的迭代次數內，將這個設施點再次作為開放設施。受文獻[16]中提出的禁忌搜索機制的啟發，本文采用了一種特殊的方法，其目標是在整個搜索過程中改變禁忌的任期。任期由一個根據迭代次數定義的周期函數T動態調整。階躍函數的每個周期由750次迭代組成，分為15個迭代區間x，…，x-1，其中i=1，2，…，15和x=x+50。在搜索過程中，禁忌列表的長度會有動態變化，T由b=α×1，2，1，4，1，2，1，8，1，2，1，4，1，2，1（α是一個參數）。因此在前50次迭代區間1，50時，禁忌期限為α；在迭代區間為51，100時，禁忌期限為2α；區間為101，150時，禁忌期限為α；區間為201，250時，禁忌期限為4α。

以此類推，每一個迭代區間對應一個禁忌期限。在迭代區間351，400時，禁忌期限到達最大值8α，此后又隨之減小，在750次迭代完成后周期性的重復這個變化方案。

禁忌搜索算法的步驟可敘述如下：

Step1：給出禁忌搜索算法的參數，在禁止表為空白的情況下，隨機產生初始解best_x。

" Step2：判定該算法的結束條件：當結束條件成立時，終止該算法運行，輸出最優解；反之，進行下一個步驟。

Step3：利用局部搜索交換一對設施后計算出Δg，h；增加和減少一個設施后分別計算出Δg和Δh。根據求出的三個結果判斷Δ=minΔg，h、Δg、Δh，如果Δ是小于零，并從中選出這個方案作為候選解best_y。

" Step4：在候選方案滿足藐視準則的條件下，將候選解best_y替換為新的當前解，也就是best_y=best_x，并把與best_y對應的禁忌對象替換已經進入禁忌表的禁忌對象，此時記錄的最優解為best_y，接下來直接進行到Step6。否則，繼續進行下一步。

Step5：檢驗選定的方案是否處于禁忌狀態，選擇沒有被禁忌方案替代當前解，并將相應的設施點添加到禁忌列表中。

" Step6：若算法滿足終止條件，則結束運行并輸出最優解；否則，轉到Step3。

2.5" 終止原則

首先，采用固定步長的方式，達到設定的最大步長M終止算法。其次，在最大步長M范圍內時，當所求解出目標值的頻率超過一個給定的標準值L時，如果目標值不做更優改進，只造成頻率的增加，此時的循環對解的改進已無作用，因此終止計算。

2.6" 時間復雜度

" 算法的時間復雜度是衡量算法執行時間的一個指標，它反映了算法執行所需時間與輸入規模之間的增長關系。具體來說，時間復雜度可以描述為當給定一個任務時，算法完成特定計算任務所需的基本操作步驟數。這個度量不僅可以幫助評估算法的性能，還可以反映算法的收斂速度。禁忌搜索算法的步驟主要包括初始化、鄰域搜索、檢查禁忌狀態和禁忌列表的更新等操作。

" 初始化過程包括生成初始解和初始化禁忌列表。生成初始解通常涉及隨機選擇設施位置的過程。最糟糕的情況就是每一個設施均選擇打開，把每一個客戶分配給距離最近的設施點。因為要計算出目標函數的數值，這個過程的時間復雜度近似為On+m。

" 鄰域搜索是禁忌搜索的核心部分，它涉及探索當前解的鄰域。在UFLP初始解的基礎上需要添加或移除開放的設施。根據改變后的設施開放情況，很容易使每個給定的客戶找到距離自己最近的設施點[12]。鄰域搜索過程中一般設施點移動不會對整體狀態有太大的改變，基于優先級隊列的模擬實現，鄰域搜索過程的時間復雜度是Omlogn。

" 管理禁忌列表包括添加新解、移除舊解和檢查禁忌條件。在檢查的過程中需要檢索一遍整個禁忌列表，假設檢索一個數據消耗時間為1個單位，則禁忌列表管理時間復雜度為Ok，這里禁忌列表的大小為k。

" 接受準則用于決定是否接受一個新解。需要根據新解的目標函數變化值，判斷是否用新的解代替當前最優解，這個過程的時間復雜度是On+m。

迭代過程包含重復執行鄰域搜索、禁忌列表管理和接受準則，直到滿足停止條件（如達到最大迭代次數或解的質量不再提升）。因此，總時間復雜度表示為OT*mlogn，其中T是迭代次數。

禁忌搜索算法流程示意圖如圖2所示。

3" 數據分析

3.1" 實驗配置和數據

本文所涉及的實驗程序是在Intel Core i7-8550U CPU @ 1.80GHz處理器和16.0GB內存上運行得出的實驗結果。為了驗證本文提出算法的可行性與實驗的有效性，選取了OR-Liarbry基準實驗問題庫中的幾個典型的測試數據集用來進行實驗，它是用于許多運籌學問題的測試數據集，提供了12個數據文件。

3.2" 實驗分析

" 本文從運行時間和解決方案質量兩方面評估所設計的禁忌搜索算法的性能。表1列出了尋找最優目標函數值、10次運行的平均值、運行總時間和誤差值。適當設置參數可以幫助算法獲得更好的結果，通過在多次實驗中調整單個參數值，同時保持其他參數不變，以確定該參數的最佳取值。TS算法參數設置：禁忌期限α=50，根據算法在實驗中的收斂速度設置最大迭代次數T=750。運行時間的單位為秒，誤差值計算方法如下：誤差=

從表1可以看出，該算法在求解問題上是比較穩定的。它在以下所有基準測試集上都能以非常高的頻率找到最優解。對算法求得最優值與已知最優解之間的誤差始終低于0.5%，有67%算例都找到最優解與已知最優解結果相同。

" 此外，該算法在求解的速度上也是相對較快的。當數據集的規模在25個設施點以下時，禁忌搜索算法在0.5秒左右就能夠得出結果；規模在50個設施點時，運行的時間也可以1秒多便可以輸出目標函數最優值。圖3是數據集Cap71的迭代收斂圖，從圖中可以看出兩種方法在迭代的初期都快速收斂，改進后的禁忌搜索算法在迭代次數上表現更加良好，運行的次數更少一點。

為了進一步評價改進后的禁忌搜索算法求解的效率如何，表2給出蝙蝠算法和本文所設計的禁忌搜索算法求解相同算例的結果。文獻[13]中的蝙蝠算法實驗環境：在操作系統為64位Windows7的實驗環境下，通過MATLAB編程對兩組標準算例求解測試得出的結果。從表2可以看出禁忌搜索算法在求解的質量上比蝙蝠算法要好一點，有三個測試算例的誤差比蝙蝠算法的要大，但禁忌搜索算法其他算例基本上都找到與已知最優解一樣的目標函數值，本文設計的改進禁忌搜索算法可以在較短的時間內求出最優解。蝙蝠算法的求解時間最快的運行得到結果也要2秒，耗時最長的需要13秒，本文改進的禁忌搜索算法僅需要在不到2秒的時間內就得到了最優值。這是因為該算法在原始的禁忌搜索算法上加以改進，在鄰域搜索的過程中生成鄰域解的目標函數值大于當前解時就會被淘汰，不輸出這個解的結果，直接進行下一次的迭代，在運算的速度上更快。

4" 結" 論

本文采用了一種改進的禁忌搜索算法來求解無容量限制設施選址問題，在原始禁忌搜索算法的基礎上，更新了一些用于解決組合優化問題的步驟。包括隨機化選取開放設施與貪心算法相結合生成初始解，使用了三種操作算子來增加種群的多樣性，添加了動態禁忌列表的策略，從而提高禁忌搜索算法在全局搜索的能力。該算法在12個基準問題算例上進行了測試，并且都在合理的運行時間范圍內得到滿意的解。在求解中小規模的算例上所需的時間也比較短，與另一種智能算法（蝙蝠算法）的結果比較可以驗證，該算法所消耗的運行時間更短，求解的質量上也略有優勢。此外，盡管在改進的禁忌搜索算法快速解決解無容量限制設施選址問題方面表現出了良好的性能，但它是否也能快速有效地解決其他設施選址問題需要進一步的研究。

參考文獻：

[1]" WENTAO JING， INHI KIM， KUN AN. The uncapacitated battery swapping facility location problem with localized charging system serving electric bus fleet[J]. Transportation Research Procedia， 2018，34：227-234.

[2]" JOS？ EVA， JOS？-FERNANDO， CIPRIANO， et al. An enhanced benders decomposition method and a matheuristic algorithm for solving the stochastic capacitated facility location problem with shortages[J]. Expert Systems with Applications， 2024，255：124802.

[3]" KLOSE， ANDREAS. A branch and bound algorithm for an uncapacitated facility location problem with a side constraint[J]. International Transactions in Operational Research， 1998，5（2）：155-168.

[4]" HUSEYIN HAKLI， ZEYNEP ORTACAY. An improved scatter search algorithm for the uncapacitated facility location problem[J]. Computers amp; Industrial Engineering， 2019，135：855-867.

[5]" ALIDAEE BAHRAM， HAIBO WANG. Uncapacitated （Facility） location problem： A hybrid genetic-tabu search approach[J]. IFAC-Papers On Line， 2022，55：1619-1624.

[6]" CHANGYU CHEN， MAHDI FATHI. Hybrid tabu search algorithm for unrelated parallel machine scheduling in semiconductor fabs with setup times， job release， and expired times[J]. Computers amp; Industrial Engineering， 2022，165：107915.

[7]" HAKLI HUSEVIN， ZEYNEP ORTACAY. An improved scatter search algorithm for the uncapacitated facility location problem[J]. Computers amp; Industrial Engineering， 2019，135：855-867.

[8]" GLOVER F. Tabu search—part I[J]. ORSA Journal on Computing， 1989（3）：190-206.

[9]" SOLTANPOUR ALIZADEH， F BAROUGHI. Efficient algorithms for uncapacitated facility location problem on uncertain environments[J]. Iranian Journal of Operations Research， 2023，14：118-132.

[10]" MENDOZA-ORTEGA， GEAN PABLO， et al. Scenario-based model for the location of multiple uncapacitated facilities： Case study in an agro-food supply chain[C] // Applied Computer Sciences in Engineering： 8th Workshop on Engineering Applications， 2021.

[11]" WU Q， HAO J K. Memetic search for the max-bisection problem[J]. Computers amp; Operations Research， 2013（1）：166-179.

[12]" LAURENT MICHEL， PASCAL VAN HENTENRYCK. A simple tabu search for warehouse location[J]. European Journal of Operational Research， 2004，157：576-591.

[13] 王婷婷，張惠珍，趙玉蘋. 求解無容量設施選址問題的拉格朗日蝙蝠算法[J]. 經濟數學，2018，35（3）：105-110.

[14] 安邦，程朋. 基于分支割平面的一類無容量限制設施選址問題求解算法[J]. 運籌學學報，2015，19（4）：1-13.

[15]" TOHYAMA H， IDA K， MATSUEDA J. A genetic algorithm for the uncapacitated facility location problem[J]. Electronics and Communications in Japan， 2011，94（5）：47-54.

[16]" ZHANG FAZHAN， et al. A fast and efficient discrete evolutionary algorithm for the uncapacitated facility location problem[J]. Expert Systems with Applications， 2023，213：118978.

[17]" SONU？， EMRULLAH. Binary crow search algorithm for the uncapacitated facility location problem[J]. Neural Computing and Applications， 2021，33：14669-14685.

[18]" BAS EMINE， G？LNUR YILDIZDAN. A new binary arithmetic optimization algorithm for uncapacitated facility location problem[J]. Neural Computing and Applications， 2024，36（8）：4151-4177.

收稿日期：2024-12-03

基金項目：國家自然科學基金資助項目（72101149）

作者簡介：單振杰（1998—），男，安徽亳州人，上海理工大學管理學院碩士研究生，研究方向：智能優化；張惠珍（1979—），本文通信作者，女，山西忻州人，上海理工大學管理學院，教授，博士，研究方向：運籌學、智能優化。

引文格式：單振杰，張惠珍，海舍舍. 求解無容量設施選址問題的改進禁忌搜索算法[J]. 物流科技，2025，48（3）：11-15.