多周期競爭性設施選址問題優化研究

李進

關鍵詞：多周期；設施選址；模型

1 引言

考慮到企業所面臨的市場需求與外部競爭復雜多變，靜態單周期的設施選址模型無法有效應對，本文在最大選址覆蓋模型的基礎上擴展構建了一個多周期的競爭性設施選址決策優化模型。模型將決策維度劃分為多個時間周期，并允許各周期內各潛在位置服務設施可重新或關閉以應對市場變化。多周期選址問題已在中心選址[1]、應急救援物流[2]，閉環物流網絡[3-4]等多個領域得到了廣泛的研究。為解決共享模式下在線設施資源的波動，徐小峰等將單周期決策轉變為多周期決策，數據結果驗證多周期方案可有效降低設施的選址成本[5]。已有研究雖考慮到市場需求的周期性變動，但卻忽略了外部競爭的變動。為此，本文聚焦于企業服務設施的網絡布局，考慮到市場需求與外部競爭周期性變動，以最小化成本與最大化覆蓋需求為雙目標，建立一個多周期的競爭性設施選址優化模型，對設施位置進行多周期維度的決策優化。為求解問題模型，文章采用并改進了NSGA-Ⅱ算法進行求解，并通過數據實驗來驗證模型與算法有效性。

2 問題與模型

2.1 問題描述與研究假設

某企業計劃在新市場進行產品銷售或服務，備選服務設施位置信息已知，潛在顧客需求點信息已知，且競爭者門店位置信息已知。市場環境是動態變化的，顧客需求與外部競爭情況將在不同時間周期內出現變化。外部競爭情況的變化表現在新競爭者設施的開放與原競爭者設施的關閉。為應對市場變化實現最小化成本與最大化覆蓋需求的雙目標，決策者需在不同的時間周期內重新調整各設施位置的運營狀態。此外，模型做出如下一般性假設：（1） 企業與競爭者所售產品或服務無顯著差別；（2） 設施對顧客的吸引力由距離決定；（3） 各潛在顧客需求點的需求基于吸引力大小按比例分配至多個設施；（4） 門店的開放、關閉在決策周期開始階段立即生效；（5） 各周期內，設施的開放運營或關閉均需支付成本；（6） 各周期決策前，顧客需求與競爭者設施位置信息已知。

2.2 模型符號

1） 集合：

2.3 需求與成本的推導計算

本問題模型假定設施對顧客吸引力由距離效用決定，即uijt = f （dij ）（1），f （dij ）為顧客關于距離的效用函數，如公式（1）所示，其中R 為設施的服務距離上限。

考慮到設施的建立是一項長期投入，為此本模型進一步區分了設施建立成本c1 與運營成本c2。設施建立與運營的先后關系為：設施建立后才可運營，且各備選位置設施的建立至多只需一次，即在設施首次開放時建立支付建立成本c1與運營成本c2，后續周期中若繼續開放運營只需支付運營成本c2。因考慮了全周期維度的建立成本，若設施建立后有若干周期未開放運營仍需分攤建立成本，因此模型忽略周期內的設施關閉成本。為此，引入參數Yj表示位置j設施是否被建立。

2.4 最優化模型

目標函數：

3 算法設計

為解決所構建的雙優化目標決策模型，本文將改進NSGA-Ⅱ算法進行求解。NSGA-Ⅱ算法以遺傳算法為基礎，是一種較為成熟的啟發式算法，特別的NSGA-采用了快速非支配排序算法，降低了求解多目標模型時的復雜度，同時采用擁擠度比較算子和精英選擇策保證了子代種群的多樣性，有效避免了優化迭代過程中局部收斂。具體的算法流程如下：

步驟1. 初始化參數，輸入種群規模N、最大迭代次數，交叉與變異率；

步驟2. 生成初代種群，gen = 1；

步驟3. 進行非支配排序，計算種群個體的適應度、擁擠度，并進行排序；

步驟4. 依據選擇策略，生成新子代種群，且gen =gen + 1；

步驟5. 判gen 是否小于最大迭代次數，若小于轉入Step 3，否則結束算法。

算法關鍵步驟詳細設計如下：

1） 染色體編碼：為對應多周期決策，染色體采用矩陣編碼。算法初始化時隨機若干矩陣，一個染色體矩陣即表示一個可行解，其中矩陣的行數對應決策周期，列數對應備選設施位置編號?；蛑当硎酒溟_閉決策，值為0即關閉，值為1則開放。

2） 交叉變異：算法針對染色體的矩陣編碼方式，采用了子矩陣交叉方式。首次，從父代種群內選擇兩個不相同的染色體，然后決定一個子矩陣位置，最后交換子矩陣內基因得到新解。染色體變異操作時，首先從染色體矩陣中選擇若干位置，然后改變其取值。

3） 選擇策略：算法將結合組合選擇與精英選擇策略，子代種群將由三部分組成。第一部分比例為α%，由父代種群內排序前α%的染色體解構；第二部分占比β%，從交叉變異后的備選染色體池中采用精英選擇策略選出占種群數量為β%的個體；第三部分比例為（1 - α% - β%），由算法重新隨機生成的新建構成。

4） 染色體接受規則：算法在交叉變異流程中將不斷產生新染色體，為確保新染色體符合問題約束，需對可行性進行判斷，若可行則選入，若不可行則拒絕新解，仍繼續保留原父代解。

4 算例實驗

4.1 算例背景

為驗證模型與算法有效性，本節選用案例數據進行數值實驗。數據集經處理后，共有10個備選設施位置點，5個競爭者設施，50個潛在顧客需求點，且市場共三個周期階段，即T = 3。備選設施位置信息見表1所示，競爭者設施位置與開閉信息見表2所示，顧客點位置與需求見表3所示。

4.2 算例結果與分析

算法參數設置如下，種群數為30，最大迭代數為200，且染色體的交叉概率為0.3，變異概率為0.1；種群選擇規則中第一部分比例為20%，第二部分比例為60%，第三部分為20%。企業計劃各周期內均開放6個服務設施，即M1 = M2 = M3 = 6。建店成本c1 為15，周期運營成本c2 為5。算法關于覆蓋需求與總成本目標的收斂圖見圖1所示，覆蓋需求目標值在80代左右收斂，而總成本目標值先升后降，收斂結果表明算法有效實現了雙目標同時優化。最后，選取帕累托等級為1的解集組合中需求目標適應度最高的解作為備選最優解，具體結果見圖1所示，其覆蓋需求目標值為844.99，總成本為180。

5 總結

本文考慮了一個多周期競爭市場中的企業設施選址問題，以覆蓋需求最大化與總成本最小化為優化目標，建立一個多周期競爭性設施選址決策模型，并改進NSGA-Ⅱ算法用以問題模型的求解，最后的數據實驗驗證了模型與算法的有效性。本研究僅聚焦于設施位置對顧客效用的影響，現實的競爭市場中設施的質量設計、庫存水平等因素都將對顧客效用與行為選擇產生影響，這些方面在未來的研究仍需進一步討論。