帶懲罰的無容量設施選址問題的降階回溯算法

茍海雯，寧愛兵，胡 沁，張惠珍

上海理工大學 管理學院，上海200093

1 引言

設施選址問題（Facility Location Problem，FLP）是運籌學、理論計算機科學和管理科學中一類非常重要的組合優化問題，受到了廣泛而深入的研究[1-4]。該問題在實際生活中有著非常重要的應用，如醫院、消防站、超市、無線通訊網絡基站和自動取款機等位置的確定[2]。在無容量設施選址問題（Uncapacitated Facility Location Problem，UFLP）中，每個顧客的需求都必須得到滿足；然而在某些實際情況下，某些顧客的需求不一定必須得到滿足[5]，引入對每個顧客懲罰的概念，對沒有被滿足需求的顧客，將會造成一定的損失，即懲罰費用，在UFLP的基礎上考慮這個因素，將它添加到UFLP的一般模型中，于是就得到了UFLP 的一個變形問題，即帶懲罰的無容量設施選址問題（Uncapacitated Facility Location Problem With Penalties，UFLPWP）[6]，其目標是選擇給定設施集合的一個子集，開設該子集中的設施，決定對哪些顧客提供服務，對哪些顧客不提供服務而選擇被懲罰，最終使得設施的開設費用、顧客與設施之間的連接費用和支付的懲罰費用之和最小。

UFLPWP是組合優化中NP-Hard問題，除非P=NP，否則不存在多項式時間的精確算法。目前解決NPHard問題的算法主要分為三類：精確算法、近似算法和啟發式算法。雖然近似算法能夠在多項式時間內得到一個常數近似比的解，但缺點是無法求得問題的最優解；啟發式算法的求解速度相對較快，但缺點是容易陷入局部最優解，因此近似算法和啟發式算法都無法保證得到問題的全局最優解；目前的精確算法雖然能求得問題的最優解，但缺點是沒有研究問題本身的數學性質，因此求解速度相對較慢。本文針對以上缺點，首先研究UFLPWP 的數學性質，并進行了相應的數學證明，利用這些數學性質可以對問題進行降階進而縮小問題的規模；然后在此基礎上設計了基于上、下界的一種精確算法來求解UFLPWP，本文的數學性質不僅可以應用于本文設計的算法，還能廣泛應用于其他各種算法，達到加快精確算法及其他算法求解速度的目的。

2 文獻綜述

UFLPWP最先是由Charikar等[7]開始研究的，Charikar等[8]針對UFLPWP的懲罰函數類型和特征，根據對偶規劃原則，基于保證可行性的前提下，得到問題的對偶可行解，結合懲罰性設計了基于原始對偶技巧的近似算法，起到了加快問題求解速度和得到有質量保證解的作用，得出算法的近似比為3；后來，Xu[9-10]針對UFLPWP的整數線性規劃模型，研究了UFLPWP的可度量性，即距離滿足非負性、對稱性和三角不等式，設計了基于線性規劃舍入技巧的近似算法，加快了UFLPWP 的求解速度，得出算法的近似比為（2+2/e）；隨后利用費用收縮和貪婪算法，將兩者相結合，又將近似比改進到了1.852 6；此外，Hayrapetyan等[11]設計了基于線性規劃舍入技巧的(1+ρ)近似比的算法。

以上文獻綜述中的近似算法能夠在多項式時間內求得一個常數比的近似解，但缺點是不能求得問題的最優解，本文針對文獻中近似算法的不足，設計了一種能夠求得最優解的精確算法，對UFLPWP 的整數線性規劃數學模型進行研究，對問題的求解特性進行數學分析，得出能加快問題求解速度的數學性質，在此基礎上設計一種降階回溯算法來求解UFLPWP。

3 問題分析與模型構建

3.1 問題分析

UFLPWP 是UFLP 的變形問題之一，與UFLP 的不同在于，在UFLPWP中，某些顧客的需求不一定必須被滿足，對沒有被滿足需求的顧客j∈C，將造成一部分費用損失，即懲罰費用；對被滿足需求的顧客j∈C，必定與開設的設施相連接，并由其提供服務，將產生設施的開設費用和顧客與設施之間的連接費用。UELPWP的目標是選擇給定設施集合F的一個子集R，開設R中的設施，且選擇被懲罰的顧客集合，將沒有被懲罰的顧客連接到一個開設設施上（即為沒有被懲罰的顧客提供服務），最終使得設施開設費用、顧客與設施之間的連接費用和支付的懲罰費用之和最小。

3.2 數學模型

在UFLPWP 中，給定設施集合F，顧客集合C，對于任意的i∈F,j∈C,fi表示設施i開設的開設費用，cij表示設施i為顧客j提供單位服務量所需支付的連接費用，pj表示顧客j∈C被懲罰的懲罰費用，也就是說當顧客j沒有被服務時，需要支付的懲罰費用為pj。其中，設施總個數為m，顧客總個數為n，對每個設施i∈F是否開設引入0-1變量yi，對顧客j∈C是否連接到設施i∈F上引入0-1 變量xij，對顧客j∈C是否被懲罰引入0-1變量zj。最終使得設施開設費用顧客與設施之間的連接費用和支付的懲罰費用三項之和達到最小。

于是，UFLPWP 可以用下面的0-1 線性規劃模型來表示：

在上述0-1 線性規劃模型中，yi表示設施i∈F是否開設，若設施i∈F開設，則yi=1，否則yi=0；xij表示顧客j∈C是否與設施i∈F相連接，若相連接，則xij=1，否則xij=0；zj表示顧客j∈C是否被懲罰，若被懲罰，則zj=1，否則zj=0。目標函數（1）表示在滿足全部約束條件下，最小的設施開設費用、連接費用以及支付的懲罰費用之和；約束條件（2）保證了顧客j如果沒有被懲罰，那么它肯定與一個設施相連并由其提供服務；約束條件（3）表示顧客j只能與開設的設施相連并由其提供服務。

4 算法設計與分析

4.1 數學符號及解釋

為了便于描述，采用以下數學符號表示。

m：設施總個數；

n：顧客總個數；

fi：開設設施i∈F的開設費用；

cij：設施i∈F為顧客j∈C提供單位服務的連接費用；

pj：顧客j∈C被懲罰的懲罰費用，即顧客j沒有被服務時，需要支付的懲罰費用；

F={1,2,…,i,…,m}：設施集合；

C={1,2,…,j,…,n}：顧客集合；

F1：最優解中需要開設的設施集合，若F1中任一設施關閉則不能取得最優解，為全局變量；

F0：最優解中不能開設的設施集合，若F0中任一設施開設則不能取得最優解，為全局變量；

F5：F5=F/F1/F0，表示暫未確定是否開設的設施集合，為全局變量；

FF1：F5中的設施在回溯算法中假設開設的設施集合，為全局變量；

FF0：F5中的設施在回溯算法中假設關閉的設施集合，為全局變量；

Temp1：若設施h開設，則設施集合Temp1中的設施一定不開設，為全局變量；

Temp2：若設施h開設，則設施集合Temp2中的設施一定不開設，為全局變量；

S：服務集；

P：懲罰顧客集，不對集合P中的顧客提供服務；

min_cij：對于顧客j，連接到設施i上的連接費用在所有可能開設的設施中的連接費用是最小的，記最小的連接費用為min_cij；

C1：滿足條件min_cij＜pj的顧客集合；

C2：滿足條件pj＜min_cij的顧客集合。

4.2 數學性質

性質1若設施i的開設費用在所有設施的開設費用中最小，且為C1顧客集合中的顧客提供服務并且連接費用均是該顧客的最小連接費用min_cij，則設施i一定開設并為C1顧客集合中的顧客提供服務，且為該問題的最優解。

證明由該問題的數學定義可知，顯然成立。

性質2若存在一顧客j的懲罰費用pj=+∞，則顧客j一定與某一設施i相連且被提供服務。

證明由于顧客j的懲罰費用pj=+∞，若顧客j不被提供服務即被懲罰，則會使總成本為+∞，所以顧客j一定與某一設施i相連且被提供服務。

性質3 若存在設施i,k，其設施開設費用fi＞fk，且對于任一顧客j連接費用都滿足cij≥ckj，則稱設施i相對設施k為嚴格劣勢，則設施i一定關閉，即將設施i放入集合F0中，且刪除設施i的關聯邊。

證明在UFLPWP 中，開設設施k比開設設施i更優，此時連接到設施i上的顧客都可以連接到設施k上且目標函數值更小，故性質3成立。

性質4 在開設設施未定的情況下，存在設施i，若顧客j連接到設施i的連接費用cij大于懲罰費用pj，即滿足cij＞pj，則顧客j一定不連接到設施i上，且刪除設施i與顧客j之間的連接邊。

證明由于cij＞pj，因此顧客j連接到設施i上會使總成本更大，所以顧客j一定不連接到設施i上，且刪除設施i與顧客j之間的連接邊。

性質5 存在一設施i，設施i分別連接到顧客j1,j2,…,jk上的連接費用cij1,cij2,…,cijk均大于顧客j1,j2,…,jk的懲罰費用pj1,pj2,…,pjk,即滿足cij1＞pj1,cij2＞pj2,…,cijk＞pjk，則設施i一定關閉，即將設施i放入集合F0中，且刪除設施i的關聯邊。

證明用反證法。如果設施i開設，則必定有顧客與其連接并提供服務，由于cij1＞pj1,cij2＞pj2,…,cijk＞pjk，因此會使目標函數值更大，所以設施i一定關閉。

性質6 對于設施i，存在一顧客j，若同時滿足下面2個條件：

（1）若fi+cij＜ckj，其中的k為除設施i之外的任一設施，該條件對每一設施k都成立。

（2）顧客j與設施i的連接費用cij與設施i開設費用fi之和小于顧客j的懲罰費用pj，即滿足fi+cij＜pj。

那么設施i一定開設，即將設施i放入集合F1中，且客戶j由設施i提供服務。

證明在UFLPWP中，顧客j要么被提供服務，要么被懲罰，由于fi+cij＜ckj，說明此時開設設施i能夠使目標函數值更小，又由于cij+fi＜pj，說明此時顧客j與設施相連并被服務能使目標函數值更小，所以設施i一定開設且顧客j由設施i提供服務。

性質7 對于顧客j，求得min_cij，此時表示顧客j連接到設施i上的連接費用在所有可能開設的設施中的連接費用是最小的，其連接費用為min_cij；此時若設施i已經確定開設且min_cij＞pj，則顧客j一定被懲罰，即將顧客j放入集合P中。

證明由于設施i已經確定開設的情況下，且min_cij＞pj，因此顧客j連接到設施i上的費用比顧客j的懲罰費用大，且顧客j連接到設施i上的連接費用在所有可能開設的設施中的連接費用是最小的，因此顧客j一定被懲罰。

性質8 對于顧客j，求得min_cij，此時表示顧客j連接到設施i上的連接費用在所有可能開設的設施中的連接費用是最小的，其連接費用為min_cij；此時若設施i已經確定開設且min_cij＜pj，則顧客j一定被設施i服務。

證明由于設施i已經確定開設的情況下，且min_cij＜pj，因此顧客j連接到設施i上的費用比顧客j的懲罰費用小，且顧客j連接到設施i上的連接費用在所有可能開設的設施中的連接費用是最小的，因此顧客j一定被設施i服務。

性質9 若存在某一設施i，假如設施i不開設，且此時下界b大于全局的上界u，則設施i一定開設。

證明上界u小于下界b，說明此時關閉設施i不可能獲得最優解，所以設施i一定開設。

性質10 若存在某一設施i，假如設施i開設，且此時下界b大于全局的上界u，則設施i一定不開設。

證明上界u小于下界b，說明此時開設設施i不可能獲得最優解，所以設施i一定不開設。

性質11 若最優解中，設施g開設，假如存在設施h，對每一個客戶j都滿足cgj＜chj或pj＜chj，就把設施h放入集合Temp1；也就是說在設施g開設的情況下，集合Temp1中的設施必定不開設。

證明由于設施g開設，若存在設施h，若對每一個客戶j都滿足cgj＜chj或pj＜chj，那么要么客戶j連接到設施g比連接到設施h上的成本小（當cgj＜chj），要么客戶j接受懲罰的成本比連接到設施h上的成本小（當pj＜chj），因此不會開設設施h。

該性質可以用批量決定某些設施一定不開設。

性質12 若最優解中，設施g不開設，假如存在設施h，對每一個客戶j都滿足fg+cgj＜chj或pj＜chj，就把設施h放入集合Temp2；也就是說在設施g不開設的情況下，集合Temp2中的設施必定不開設。

證明由于設施g不開設，若存在設施h，若對每一個客戶j都滿足fg+cgj＜chj或pj＜chj，那么要么開設設施g且客戶j連接到設施g比連接到設施h上的成本小（當fg+cgj＜chj），要么顧客j接受懲罰的成本比連接到設施h上的成本小（當pj＜chj），因此不會開設設施h。

該性質可以用批量決定某些設施一定不開設。

性質13 對于任一設施i，存在一顧客j，若顧客j與設施i的連接費用cij與設施i開設費用fi之和小于顧客j的懲罰費用pj，即滿足cij+fi＜pj，則顧客j一定被提供服務。

證明由于cij+fi＜pj，即使開設設施i且把顧客j連接到設施i上的總成本比顧客j的懲罰費用小，因此顧客j一定被提供服務。

4.3 求解算法

4.3.1 上界和下界

（1）上界子算法

實際上，任何一個可行解對應的目標函數值均能作為該問題的一個上界，本文在前文提出的數學性質的基礎上采用貪心算法的策略來設計上界子算法，算法主要步驟如下：利用前文提出的數學性質，對問題進行降階處理，把確定不開設的設施以及與該設施相連接的邊刪除，之后開設與C1顧客集合中的每個顧客連接費用最小的設施作為一個可行解，此時開設的設施集合為Fu，對Fu中的每一個設施i做如下處理：

假設設施i不開設，令設施i服務的顧客集合為Cu，假設把Cu中的每一個客戶j連接到集合(Fu/i)中連接費用最小的設施h(j)上；若滿足：

若上述假設成立，則執行假設中的操作，此時對應一個目標函數更好的可行解，其對應的目標函數值作z即可作為UFLPWP的一個初始上界u。

（2）下界子算法

利用前文提出的數學性質對問題進行降階處理，然后利用下面的公式計算下界b：

上式中，等式右邊的第1項表示確定開設的設施集合F1中每一個設施的開設費用fi之和，第2 項表示C1顧客集合中每一個顧客的最小連接費用min_cij之和，第3項表示C2顧客集合中每一個顧客的懲罰費用pj之和，第4項表示回溯算法中假設開設的設施集合FF1中每一個設施的開設費用fi之和。

4.3.2 降階回溯算法

此部分的算法由降階子算法和回溯子算法兩部分組成，降階算法通過前文提出的數學性質進行降階處理，進而縮小問題的規模；回溯算法采用深度優先策略，從根結點出發搜索解空間樹，算法搜索至解空間樹的任一結點時，先判斷該結點是否包含問題的解。如果肯定不包含，則跳過對以該結點為根的子樹的搜索，逐層向其祖先結點回溯。否則，進入該子樹，繼續按深度優先策略搜索。本文的回溯算法從根結點出發，當搜索至解空間樹的任一結點時，根據上下界子算法計算出的該結點的上界u和下界b，判斷該結點的下界b是否小于上界u，若是，則繼續向下深度優先搜索，否則進行剪枝處理，即跳過該結點及以下的子樹，逐層向上級回溯。用present_c（簡記為pre_c）來表示當前可行解的目標函數值，best_c來表示當前搜索到的最小目標函數值。

降階子算法描述如下：

步驟1 初始化u=+∞,b=0,pre_c=0,best_c=+∞。

步驟2 利用前文的數學性質對該問題進行降階處理，確定必定開設的設施，把確定必定開設的設施放入設施集合F1中；確定必定關閉的設施，把確定必定關閉的設施放入設施集合F0中；最后把剩下的不能確定是否開設的設施放入設施集合F5中；經過降階處理后，可以得到兩種情況：

（1）根據性質1得到問題的最優解，則算法結束。

（2）還沒有得到最優解，則跳到步驟3。

步驟3 利用前文中的上下界子算法計算當前的上界u，且best_c=u，更新數組best_y與上界u對應的設施開設情況一致。

步驟4 對當前設施的開設費用按照非增排序，即此時的開設費用f1≥f2≥…≥fi≥…≥fm。

步驟5 調用回溯子算法Backtrack（1）。

回溯子程序Backtrack(i)算法描述如下：

步驟1 如果當i＞|F5|時，說明此時算法搜索至葉子結點，此時對應一個可行解，即得到一個確定開設設施的子集合F1，此時對應的目標函數值cur_c為確定開設的設施子集合F1開設費用之和加上顧客集合C1中(j∈C1)每一個顧客在F1上的最小連接費用之和，以及加上沒有被連接的顧客懲罰費用之和，并將此時的pre_c與best_c比較，若pre_c＜best_c，則更新best_c=pre_c,u=best_c，數組best_y=y，該回溯子程序結束；如果當i≤|F5|時，則執行步驟2。

步驟2 利用二叉樹來搜索最優解，在F5中取出開設設施費用最高的設施i，分兩種情況處理：

（1）假設設施i開設，則執行步驟3。

（2）假設設施i關閉，則執行步驟5。

步驟3 假設設施i開設，利用性質11，可批量確定設施集合Temp1不開設，并設FF1=FF1∪{i},FF0=FF0∪Temp1,F5=F5/{i}/Temp1；此時利用下界子程序計算當前情況下的下界b1，若b1≥u，則該分支不存在更好的解，剪枝，跳到步驟4；若b1＜u，則先利用前文提出的數學性質對當前情況的問題進行降階處理，然后再調用回溯子程序Backtrack(i+1)進入左子樹。

步驟4 返回二叉樹上一層之前恢復設置：FF1=FF1/{i},FF0=FF0/Temp1,F5=F5∪{i}∪Temp1。

步驟5 假設設施i關閉，利用性質12，可批量確定某些設施集合Temp2不開設，并設FF0=FF0∪{i}∪Temp2,F5=F5/{i}/Temp2；此時利用下界子程序計算當前情況下的下界b1，若b1≥u，則該分支不存在更好的解，剪枝，跳到步驟6；若b1＜u，則先利用前文提出的數學性質對當前情況的問題進行降階處理，然后再調用回溯子程序Backtrack(i+1)進入右子樹。

步驟6 返回二叉樹上一層之前恢復設置：FF0=FF0/{i}/Temp2,F5=F5∪{i}∪Temp2。

算法結束后，當前的最優目標函數值best_c、對應的開設設施集合、被提供服務的顧客集合以及被懲罰的顧客集合就是整個問題的一個最優解。

4.4 算法的時間復雜度及對比分析

本文研究的問題規模即設施的個數為m，該算法在搜索空間樹中最多產生2m個葉子結點，由于本文算法通過數學性質對問題進行了降階處理，問題的規模減小為|F5|，令k=|F5|，因此算法在最壞情況下的時間復雜度為O(2k)。

針對設施選址問題，目前有三類算法可以解決此問題：近似算法[6，12]、啟發式算法[13]和精確算法[14-15]。對于近似算法和啟發式算法而言，雖然求解速度快，但是一般不能保證獲得全局最優解，所以其解的質量不能保證。本文設計的降階回溯算法是精確算法，所得到的解一定是全局最優解。對于一般的精確算法而言，沒有針對問題進行數學分析，沒有利用問題的數學性質對問題進行降階處理，也沒有考慮部分設施能夠在多項式時間內確定其是否開設，所以算法的時間復雜度為O(2m)，由于本文的算法對問題進行了降階處理，因此相對于本文的算法而言，其時間復雜度更高。本文的精確算法的優點在于首先研究了UFLPWP 的數學性質，然后根據其數學性質對問題進行降階處理，從而減小問題規模，進而縮小了問題的解空間，因此算法僅對一部分設施進行搜索，降低了算法的時間復雜性，同時利用上下界子算法進行剪枝處理，只對子樹進行搜索，提高了算法的求解速度。

5 算法應用及示例分析

為了更清楚地闡述本文算法的原理以及執行過程，下面給出一個示例來進行說明。

示例1 現有8個備選設施i，7個顧客j，從中選出若干個設施使其開設為顧客服務，同時選出被懲罰的顧客，且使設施的開設費用、顧客與開設設施之間的連接費用和支付被懲罰顧客的懲罰費用之和最小，即使總費用最小。設施的開設費用如表1所示，設施與顧客的連接費用如表2所示，顧客的懲罰費用如表3所示，總體示例如圖1所示。

表1 設施的開設費用fi

表2 設施與顧客的連接費用cij

表3 顧客的懲罰費用pj

圖1 示例1的圖形表示

對示例1的求解分析過程如下：

（1）利用數學性質3，關閉設施i2，從圖1 中刪除設施i2，將設施i2放入集合F0中，同時刪除各顧客與設施i2的連接邊{i2j1,i2j2,i2j3,i2j4,i2j5,i2j6,i2j7}。

（2）利用數學性質4，對于顧客j1，可從圖1 中刪除邊{i3j1,i4j1,i5j1,i6j1,i7j1,i8j1}；對于顧客j2，可從圖1中刪除邊{i1j2,i3j2,i4j2,i5j2,i6j2,i7j2,i8j2} ，將顧客j2放入集合P中；對于顧客j3，可從圖1中刪除邊{i1j3,i3j3,i6j3,i7j3}；對于顧客j4，可從圖1中刪除邊{i1j4,i3j4,i4j4,i5j4,i6j4,i7j4,i8j4}，將顧客j4放入集合P中；對于顧客j5，可從圖1 中刪除邊{i1j5,i3j5,i6j5,i7j5,i8j5}；對于顧客j6，可從圖1 中刪除邊{i3j6,i4j6,i6j6}；對于顧客j7，可從圖1中刪除邊{i3j7,i4j7,i6j7,i7j8,i8j7}。

（3）利用數學性質5，關閉設施i3，從圖1 中刪除設施i3，將設施i3放入集合F0中。

（4）利用數學性質6可知，設施i1必定開設，且顧客j1由設施i1提供服務，將設施i1加入集合F1中，將顧客j1與設施i1的連接邊{i1j1}加入到服務集S中。

（5）利用數學性質8，顧客j6一定由設施i1提供服務，將顧客j6與設施i1的連接邊{i1j6}加入服務集合S中，并從圖1中刪除邊{i5j6,i7j6,i8j8}；顧客j7一定由設施i1提供服務，將顧客j7與設施i1的連接邊{i1j7}加入服務集合S中，并從圖1中刪除邊{i5j7}。

（6）由于設施i1已經確定開設，利用數學性質11，批量確定關閉設施集合Temp1={i6,i7}，并從圖1中刪除與設施i6,i7關聯的所有邊。

（7）通過數學性質降階處理后，問題規模如圖2 所示，計算當前情況的初始上界為u=56。

圖2 降階處理后的問題規模圖形表示

（8）由于設施i1確定開設，對圖2 中的設施i4、i5和i8按照費用fi非增排序f8＞f5＞f4。

（9）執行回溯算法對當前圖進行處理，執行過程如圖3。

通過上述算法可得到該問題的開設設施集為F1={i1},得到服務集S={i1j1,i1j6,i1j7},懲罰顧客集合為P={j2,j3,j4,j5}，最優目標函數值Z=46。采用本文設計的降階回溯算法求解示例1，搜索樹的葉子結點個數為23，若采用通常的精確算法求解示例1，則搜索樹的葉子結點個數為28，若采用近似算法來求解示例1，則得到的解是常數近似比的解，不是全局最優解，若采用啟發式算法求解示例1，容易陷入局部最優解，因此本文設計的算法與通常的精確算法、近似算法和啟發式算法相比，本文的算法在求解的過程中減小了問題的規模，降低了算法的時間復雜度，加快了問題的求解速度，同時求出了問題的最優解。

圖3 搜索樹

6 結論

本文研究了UFLP的變形問題之一，即帶懲罰的無容量設施選址問題（UFLPWP），有如下創新點：（1）首先研究了UFLPWP的數學性質，并進行了數學證明，這些數學性質不僅可以應用于本論文設計的算法，還能廣泛應用于其他各種算法；（2）利用這些數學性質可以對問題進行降階進而縮小問題的規模；（3）然后在數學性質和降階算法的基礎上設計了基于上、下界的回溯算法來求解UFLPWP。通過對示例1求解過程分析可知，求解的時間復雜度為23與普通精確算法求解的時間復雜度28比有了很大程度的降低，減小了問題的規模，加快了問題的求解速度。