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

關(guān)鍵詞：無(wú)容量設(shè)施選址問(wèn)題；禁忌搜索算法；貪心算法；禁忌列表

" 中圖分類號(hào)：F253" " 文獻(xiàn)標(biāo)志碼：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" 引" 言

無(wú)容量限制設(shè)施選址問(wèn)題（Uncapacitated Facility Location Problem，UFLP）是組合優(yōu)化問(wèn)題中研究最廣泛的問(wèn)題之一。

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

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

" 現(xiàn)在禁忌搜索算法的運(yùn)用也越來(lái)越廣泛，例如作業(yè)車間調(diào)度問(wèn)題[6]和醫(yī)療設(shè)施選址問(wèn)題[7]上都有用到禁忌搜索算法去求解。禁忌搜索算法[8]可將最近若干步內(nèi)所得到的解存儲(chǔ)在禁忌表中，從而強(qiáng)制搜索避免再次重復(fù)表中的解。它具有參數(shù)少、穩(wěn)定性強(qiáng)、收斂速度快等優(yōu)點(diǎn)。本文設(shè)計(jì)了一種動(dòng)態(tài)禁忌列表的禁忌搜索算法求解UFLP，在禁忌搜索算法的基礎(chǔ)上，禁忌列表在不同的迭代區(qū)間有不同的禁忌長(zhǎng)度。初始解運(yùn)用隨機(jī)化選擇開(kāi)放設(shè)施與貪心聚類算法結(jié)合的方法生成，其次設(shè)計(jì)了一個(gè)禁忌搜索的優(yōu)化過(guò)程，目的是為了圍繞得到的初始解進(jìn)行強(qiáng)化搜索。禁忌搜索過(guò)程使用設(shè)施點(diǎn)移動(dòng)擴(kuò)大領(lǐng)域空間和增量評(píng)估技術(shù)進(jìn)行快速鄰域檢查。最后，通過(guò)實(shí)驗(yàn)求解一些經(jīng)典UFLP算例，驗(yàn)證了該算法的可行性和有效性。

1" 無(wú)容量限制設(shè)施選址問(wèn)題

無(wú)容量限制設(shè)施選址問(wèn)題與實(shí)際背景相結(jié)合，已被廣泛應(yīng)用于很多領(lǐng)域的設(shè)施選址優(yōu)化，如：不確定環(huán)境下設(shè)施選址問(wèn)題[9]和農(nóng)產(chǎn)品供應(yīng)鏈網(wǎng)絡(luò)設(shè)計(jì)[10]。假設(shè)所有候選設(shè)施的容量都是無(wú)限的，要求每個(gè)客戶都應(yīng)由一個(gè)且只能由一個(gè)設(shè)施提供服務(wù)，目標(biāo)是找到一套開(kāi)放設(shè)施，并在設(shè)施與客戶之間找到合理的分配方案，使總服務(wù)成本和總開(kāi)放設(shè)施成本之和最小化。c表示客戶i由設(shè)施j提供服務(wù)時(shí)的成本，f表示設(shè)施j的開(kāi)放固定成本。數(shù)學(xué)模型可以描述為：

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）為目標(biāo)函數(shù)，即總費(fèi)用；式（2）確保每個(gè)客戶由一個(gè)且僅由一個(gè)設(shè)施提供服務(wù)；式（3）確保只有在設(shè)施被開(kāi)放時(shí)客戶才能獲得服務(wù)式；式（4）、式（5）是二元變量，在0和1之間選取。如果客戶i被設(shè)施j提供服務(wù)時(shí)，則x等于1，否則為0；如果設(shè)施j開(kāi)放使用，則y等于1，否則為0。

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

2.1" 初始解的生成

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

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

2.2" 鄰域結(jié)構(gòu)

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

" 以上在鄰域搜索的過(guò)程中，交換兩個(gè)設(shè)施，增加一個(gè)設(shè)施點(diǎn)和減少一個(gè)設(shè)施點(diǎn)，操作步驟如圖1所示。

2.3" 動(dòng)作選擇策略

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

" 在兩個(gè)或兩個(gè)以上的非禁忌設(shè)施點(diǎn)移動(dòng)后，具有相同的最小的函數(shù)目標(biāo)值情況下，將隨機(jī)選擇其中一個(gè)。一個(gè)設(shè)施點(diǎn)從它的原始集合更改為另一個(gè)集合，它將被劃分到禁忌列表里，在此期間設(shè)施g或h被禁止移動(dòng)。一個(gè)簡(jiǎn)單的解禁標(biāo)準(zhǔn)被應(yīng)用，允許一個(gè)頂點(diǎn)被選擇，盡管是禁忌狀態(tài)下，如果它引導(dǎo)的解決方案比當(dāng)前的最佳解決方案更好，就會(huì)達(dá)到解禁的標(biāo)準(zhǔn)。當(dāng)達(dá)到最大允許的迭代次數(shù)時(shí)，禁忌程序進(jìn)程將停止。

2.4" 禁忌列表和禁忌期限

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

以此類推，每一個(gè)迭代區(qū)間對(duì)應(yīng)一個(gè)禁忌期限。在迭代區(qū)間351，400時(shí)，禁忌期限到達(dá)最大值8α，此后又隨之減小，在750次迭代完成后周期性的重復(fù)這個(gè)變化方案。

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

Step1：給出禁忌搜索算法的參數(shù)，在禁止表為空白的情況下，隨機(jī)產(chǎn)生初始解best_x。

" Step2：判定該算法的結(jié)束條件：當(dāng)結(jié)束條件成立時(shí)，終止該算法運(yùn)行，輸出最優(yōu)解；反之，進(jìn)行下一個(gè)步驟。

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

" Step4：在候選方案滿足藐視準(zhǔn)則的條件下，將候選解best_y替換為新的當(dāng)前解，也就是best_y=best_x，并把與best_y對(duì)應(yīng)的禁忌對(duì)象替換已經(jīng)進(jìn)入禁忌表的禁忌對(duì)象，此時(shí)記錄的最優(yōu)解為best_y，接下來(lái)直接進(jìn)行到Step6。否則，繼續(xù)進(jìn)行下一步。

Step5：檢驗(yàn)選定的方案是否處于禁忌狀態(tài)，選擇沒(méi)有被禁忌方案替代當(dāng)前解，并將相應(yīng)的設(shè)施點(diǎn)添加到禁忌列表中。

" Step6：若算法滿足終止條件，則結(jié)束運(yùn)行并輸出最優(yōu)解；否則，轉(zhuǎn)到Step3。

2.5" 終止原則

首先，采用固定步長(zhǎng)的方式，達(dá)到設(shè)定的最大步長(zhǎng)M終止算法。其次，在最大步長(zhǎng)M范圍內(nèi)時(shí)，當(dāng)所求解出目標(biāo)值的頻率超過(guò)一個(gè)給定的標(biāo)準(zhǔn)值L時(shí)，如果目標(biāo)值不做更優(yōu)改進(jìn)，只造成頻率的增加，此時(shí)的循環(huán)對(duì)解的改進(jìn)已無(wú)作用，因此終止計(jì)算。

2.6" 時(shí)間復(fù)雜度

" 算法的時(shí)間復(fù)雜度是衡量算法執(zhí)行時(shí)間的一個(gè)指標(biāo)，它反映了算法執(zhí)行所需時(shí)間與輸入規(guī)模之間的增長(zhǎng)關(guān)系。具體來(lái)說(shuō)，時(shí)間復(fù)雜度可以描述為當(dāng)給定一個(gè)任務(wù)時(shí)，算法完成特定計(jì)算任務(wù)所需的基本操作步驟數(shù)。這個(gè)度量不僅可以幫助評(píng)估算法的性能，還可以反映算法的收斂速度。禁忌搜索算法的步驟主要包括初始化、鄰域搜索、檢查禁忌狀態(tài)和禁忌列表的更新等操作。

" 初始化過(guò)程包括生成初始解和初始化禁忌列表。生成初始解通常涉及隨機(jī)選擇設(shè)施位置的過(guò)程。最糟糕的情況就是每一個(gè)設(shè)施均選擇打開(kāi)，把每一個(gè)客戶分配給距離最近的設(shè)施點(diǎn)。因?yàn)橐?jì)算出目標(biāo)函數(shù)的數(shù)值，這個(gè)過(guò)程的時(shí)間復(fù)雜度近似為On+m。

" 鄰域搜索是禁忌搜索的核心部分，它涉及探索當(dāng)前解的鄰域。在UFLP初始解的基礎(chǔ)上需要添加或移除開(kāi)放的設(shè)施。根據(jù)改變后的設(shè)施開(kāi)放情況，很容易使每個(gè)給定的客戶找到距離自己最近的設(shè)施點(diǎn)[12]。鄰域搜索過(guò)程中一般設(shè)施點(diǎn)移動(dòng)不會(huì)對(duì)整體狀態(tài)有太大的改變，基于優(yōu)先級(jí)隊(duì)列的模擬實(shí)現(xiàn)，鄰域搜索過(guò)程的時(shí)間復(fù)雜度是Omlogn。

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

" 接受準(zhǔn)則用于決定是否接受一個(gè)新解。需要根據(jù)新解的目標(biāo)函數(shù)變化值，判斷是否用新的解代替當(dāng)前最優(yōu)解，這個(gè)過(guò)程的時(shí)間復(fù)雜度是On+m。

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

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

3" 數(shù)據(jù)分析

3.1" 實(shí)驗(yàn)配置和數(shù)據(jù)

本文所涉及的實(shí)驗(yàn)程序是在Intel Core i7-8550U CPU @ 1.80GHz處理器和16.0GB內(nèi)存上運(yùn)行得出的實(shí)驗(yàn)結(jié)果。為了驗(yàn)證本文提出算法的可行性與實(shí)驗(yàn)的有效性，選取了OR-Liarbry基準(zhǔn)實(shí)驗(yàn)問(wèn)題庫(kù)中的幾個(gè)典型的測(cè)試數(shù)據(jù)集用來(lái)進(jìn)行實(shí)驗(yàn)，它是用于許多運(yùn)籌學(xué)問(wèn)題的測(cè)試數(shù)據(jù)集，提供了12個(gè)數(shù)據(jù)文件。

3.2" 實(shí)驗(yàn)分析

" 本文從運(yùn)行時(shí)間和解決方案質(zhì)量?jī)煞矫嬖u(píng)估所設(shè)計(jì)的禁忌搜索算法的性能。表1列出了尋找最優(yōu)目標(biāo)函數(shù)值、10次運(yùn)行的平均值、運(yùn)行總時(shí)間和誤差值。適當(dāng)設(shè)置參數(shù)可以幫助算法獲得更好的結(jié)果，通過(guò)在多次實(shí)驗(yàn)中調(diào)整單個(gè)參數(shù)值，同時(shí)保持其他參數(shù)不變，以確定該參數(shù)的最佳取值。TS算法參數(shù)設(shè)置：禁忌期限α=50，根據(jù)算法在實(shí)驗(yàn)中的收斂速度設(shè)置最大迭代次數(shù)T=750。運(yùn)行時(shí)間的單位為秒，誤差值計(jì)算方法如下：誤差=

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

" 此外，該算法在求解的速度上也是相對(duì)較快的。當(dāng)數(shù)據(jù)集的規(guī)模在25個(gè)設(shè)施點(diǎn)以下時(shí)，禁忌搜索算法在0.5秒左右就能夠得出結(jié)果；規(guī)模在50個(gè)設(shè)施點(diǎn)時(shí)，運(yùn)行的時(shí)間也可以1秒多便可以輸出目標(biāo)函數(shù)最優(yōu)值。圖3是數(shù)據(jù)集Cap71的迭代收斂圖，從圖中可以看出兩種方法在迭代的初期都快速收斂，改進(jìn)后的禁忌搜索算法在迭代次數(shù)上表現(xiàn)更加良好，運(yùn)行的次數(shù)更少一點(diǎn)。

為了進(jìn)一步評(píng)價(jià)改進(jìn)后的禁忌搜索算法求解的效率如何，表2給出蝙蝠算法和本文所設(shè)計(jì)的禁忌搜索算法求解相同算例的結(jié)果。文獻(xiàn)[13]中的蝙蝠算法實(shí)驗(yàn)環(huán)境：在操作系統(tǒng)為64位Windows7的實(shí)驗(yàn)環(huán)境下，通過(guò)MATLAB編程對(duì)兩組標(biāo)準(zhǔn)算例求解測(cè)試得出的結(jié)果。從表2可以看出禁忌搜索算法在求解的質(zhì)量上比蝙蝠算法要好一點(diǎn)，有三個(gè)測(cè)試算例的誤差比蝙蝠算法的要大，但禁忌搜索算法其他算例基本上都找到與已知最優(yōu)解一樣的目標(biāo)函數(shù)值，本文設(shè)計(jì)的改進(jìn)禁忌搜索算法可以在較短的時(shí)間內(nèi)求出最優(yōu)解。蝙蝠算法的求解時(shí)間最快的運(yùn)行得到結(jié)果也要2秒，耗時(shí)最長(zhǎng)的需要13秒，本文改進(jìn)的禁忌搜索算法僅需要在不到2秒的時(shí)間內(nèi)就得到了最優(yōu)值。這是因?yàn)樵撍惴ㄔ谠嫉慕伤阉魉惴ㄉ霞右愿倪M(jìn)，在鄰域搜索的過(guò)程中生成鄰域解的目標(biāo)函數(shù)值大于當(dāng)前解時(shí)就會(huì)被淘汰，不輸出這個(gè)解的結(jié)果，直接進(jìn)行下一次的迭代，在運(yùn)算的速度上更快。

4" 結(jié)" 論

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

參考文獻(xiàn)：

[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] 王婷婷，張惠珍，趙玉蘋. 求解無(wú)容量設(shè)施選址問(wèn)題的拉格朗日蝙蝠算法[J]. 經(jīng)濟(jì)數(shù)學(xué)，2018，35（3）：105-110.

[14] 安邦，程朋. 基于分支割平面的一類無(wú)容量限制設(shè)施選址問(wèn)題求解算法[J]. 運(yùn)籌學(xué)學(xué)報(bào)，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

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目（72101149）

作者簡(jiǎn)介：?jiǎn)握窠埽?998—），男，安徽亳州人，上海理工大學(xué)管理學(xué)院碩士研究生，研究方向：智能優(yōu)化；張惠珍（1979—），本文通信作者，女，山西忻州人，上海理工大學(xué)管理學(xué)院，教授，博士，研究方向：運(yùn)籌學(xué)、智能優(yōu)化。

引文格式：?jiǎn)握窠?，張惠珍，海舍? 求解無(wú)容量設(shè)施選址問(wèn)題的改進(jìn)禁忌搜索算法[J]. 物流科技，2025，48（3）：11-15.