摘 要：疫情爆發(fā)后，封控區(qū)內居民的生活物資發(fā)放問題成為亟待解決的焦點問題之一，該問題可抽象為疫情期間生活物資集散點選址問題，其實質為組合優(yōu)化中的NP-hard問題?；谝咔榉饪仄陂g的應急生活物資集散點選址問題的精確算法進行研究，首先得出一些可以降低問題規(guī)模的數(shù)學性質并證明利用這些性質可以減小問題規(guī)模，降低問題的求解難度；然后設計出分配子算法、上下界子算法以及降階子算法；基于這些子算法提出一種可以減小問題規(guī)模同時得到最優(yōu)解的降階回溯算法；最后通過分析和求解若干個示例進一步闡述該算法的原理和執(zhí)行過程，結果表明該算法能通過減小問題規(guī)模來降低問題求解的難度。

關鍵詞：生活物資集散點選址問題；數(shù)學性質；分配算法；上下界算法；降階回溯算法

中圖分類號：TP301.6 文獻標志碼：A 文章編號：1001-3695（2023）08-017-2351-10

doi： 10.19734/j.issn.1001-3695.2023.01.0005

Backtracking algorithm with reduction for location problem of

distribution points for living supplies during epidemic

Chu Xu， Ning Aibing Hu Kaiyuan， Dai Suyu， Zhang Huizhen

（Business School， University of Shanghai for Science amp; Technology， Shanghai 200093， China）

Abstract：After the outbreak of the epidemic， the allocation of living supplies in residential areas under closed management become one of the focal issues to be solved urgetly， and this problem can be abstracted as the location problem of distribution points for living supplies during the epidemic， whose essence is the NP-hard problem in combinational optimization. This paper studied the exact algorithm of the location problem of distribution points for living supplies during the lockdown period，firstly it researched some mathematical properties and corresponding proof of the problem， and these properties could be used to reduce the size of the given problem， thereby reducing the difficulty of the problem solving. Then this paper designed the allocation sub-algorithm， upper and lower bound sub-algorithms and the reduced order sub-algorithm， and based on these sub-algorithms， it proposed a backtracking algorithm with reduction which could reduce the size of the problem and get the optimal solution. Finally， this paper analyzed and solved several examples to further illustrate the principle and execution process of the proposed algorithm. The results show that the proposed algorithm can reduce the difficulty of solving the problem by reducing the size of the problem.

Key words：location problem of distribution points for living supplies; mathematical properties; allocation algorithm; upper and lower bound algorithms; backtracking algorithm with reduction

0 引言

近年來，自然災害、事故災難、公共衛(wèi)生事件和社會安全事件等突發(fā)事件在世界各地頻發(fā)，嚴重危害了受災地區(qū)居民的生命安全。自2020年以來新冠疫情肆虐全球，由于疫情爆發(fā)的高度不確定性和高度破壞性，造成的人員傷亡和經濟損失無法估量。疫情爆發(fā)后，封控區(qū)內的居民面臨物資供給不足的問題，尤其是食物、飲用水和醫(yī)療物資的不足使居民生命安全受到威脅，及時有效地將應急物資運往各封控區(qū)并合理有序地分配給居民，是保障居民生命安全以及應對疫情的有力措施。疫情期間應急物資儲備設施的選址是保障封控所需各種物資供應的基礎工作，科學的應急物資儲備設施選址方案才能高效合理地調運和分配應急物資。非特殊的設施選址是NP-hard問題［1，2］，除非P=NP，否則不存在多項式時間內的解。

國內外學者對應急物資儲備設施選址問題進行了大量的研究。袁穎［3］研究了重大疫情下應急醫(yī)療服務設施選址問題，構建了以醫(yī)療設施物理成本和心理成本最小化為目標的雙目標優(yōu)化模型，并使用非支配排序遺傳算法求解。宋英華等人［4］研究了常態(tài)化疫情防控背景下區(qū)域應急醫(yī)療物資選址—分配問題，構建以醫(yī)院儲備點需求未滿足率加權和最小化及物資購買點物資分配公平性最大化為目標的選址模型，并使用非支配排序遺傳算法求解。王紫巖［5］研究了新冠疫情背景下的防疫物資儲備中心選址—分配問題，并使用遺傳算法求解。郗蒙浩等人［6］研究了國家級應急物資儲備設施選址優(yōu)化布局問題，考慮了地區(qū)人口分布、經濟條件、交通狀況和多重覆蓋關鍵地區(qū)等綜合因素，并使用變鄰域算法求解。朱莉等人［7］研究了考慮區(qū)域異質性的應急物資選址—分配優(yōu)化問題，將反映時間因素納入應急總成本決策考量時的最優(yōu)選址和物資分配優(yōu)化問題，并使用遺傳算法求解。于冬梅等人［8］研究了共享不確定需求和中斷情景下服務能力有限的應急設施多級覆蓋選址魯棒優(yōu)化模型，并使用灰狼優(yōu)化算法求解。叢雯婧［9］研究了臺風災害情景下的區(qū)域應急物資儲備庫選址問題，設計了帶精英策略的非支配排序遺傳算法進行求解。鄭夏等人［10］構建了應急物資儲備中心多目標優(yōu)化選址模型，并設計引入局部搜索機制的免疫非線性算法進行求解。劉博等人［11］研究了政企協(xié)同視角下應急物資儲備庫選址問題，構建以加權時間最小化和政府初始成本最小化為目標的應急物資儲備庫選址模型，并使用非支配排序遺傳算法求解。彭大江等人［12］研究了基于模糊需求的應急物資中心選址—路徑問題，并使用基于Q-學習的超啟發(fā)式算法求解；他們還研究了應急資源中心選址問題，并提出了一種改進的多目標離散粒子群優(yōu)化方法求解［13］。Karatas等人［14］針對災害中臨時應急服務中心選址問題提出了一種多目標選址分析模型，并使用具有目標規(guī)劃的綜合迭代分支和定界算法求解。Yu［15］研究了同時考慮到隨機性和不確定性的應急商品的災前選址和儲存模型，并使用改進的列和約束生成方法求解。宋英華等人［16］考慮動態(tài)需求的應急物資配送中心選址問題，并使用耦合Dijstra算法的分層序列法求解。胡少龍等人［17］研究了考慮應急物資需求的不確定性的應急物資配置問題，并設計了基于機器學習的樣本均值近似算法進行求解。譚正園等人［18］研究了新冠肺炎疫情下應急物資儲備倉庫選址問題，構建應急物資配送倉庫選址的最大覆蓋模型，并使用層次分析法求解。張敏等人［19］研究了基于失效情景下新增中央儲備庫選址問題，并選取處理多輸入多輸出問題具有優(yōu)勢的評估方法——數(shù)據(jù)包絡法進行評估，最終得出選址方案。

目前求解應急物資儲備設施選址問題的算法主要分為四類：a）評估方法，如層次分析法、數(shù)據(jù)包絡法，評估方法的缺點在于其帶有一定的主觀性；b）近似算法，它可以保證在多項式時間內獲得一個常數(shù)近似比的解，但是無法得到問題的最優(yōu)解；c）啟發(fā)式算法，如遺傳算法、粒子群優(yōu)化算法、灰狼優(yōu)化算法等，啟發(fā)式算法的優(yōu)點是可以快速得到問題的一個可行解，但是此類算法所獲得的解的質量無法保證；d）精確算法，如分支定界法、列和約束生成法，此類算法能保證得到全局最優(yōu)解，但是由于沒有研究問題本身的數(shù)學性質來加快算法的執(zhí)行速度，求解速度較慢。

本文以2022年以來全國范圍內多次較大規(guī)模區(qū)域性疫情爆發(fā)為背景，對封閉式管理期間衍生的應急生活物資集散點選址問題構建數(shù)學模型，并提出了求解該問題的一種精確算法。在該算法中，首先探究了該問題的數(shù)學性質，其中某些性質可以批量地確定某些設施備選點必須開設或者必須不開設；然后給出上界和下界子算法，并結合降階子算法設計了一個降階回溯算法，它與單純的回溯算法相比通過降階子算法減小了問題的規(guī)模，通過上下界子算法加快了求解的速度；最后對該算法的時間復雜度與特點進行分析，并通過分析和求解若干個示例來驗證該降階回溯算法可以減小問題規(guī)模并剪枝，從而加快問題的求解速度，最終得到問題的最優(yōu)解。

1 問題描述

1.1 問題介紹

當疫情出現(xiàn)區(qū)域性爆發(fā)時，對相關社區(qū)采取封閉式管理是快速撲滅疫情的有效方式，針對大量、分散的居家隔離人員實現(xiàn)統(tǒng)一化管理成為新的難點問題。相關數(shù)據(jù)分析表明，在疫情期間政府完全有能力調動足夠數(shù)量的生活物資，只是生活物資發(fā)放給社區(qū)居民的渠道不暢［20］。為了解決這個問題，可在城市中建造一定數(shù)量的生活物資集散點，各集散點向上接收物資儲備庫的物資，向下負責若干個居民點的生活物資的有序發(fā)放，所以生活物資集散點的科學選址成為了至關重要的問題。

1.2 數(shù)學符號與解釋

1.3 數(shù)學模型

1.4 數(shù)學性質

2 算法設計與分析

2.1 分配子算法

2.2 上界子算法

2.3 下界子算法

2.4 降階子算法

2.5 回溯子算法

2.6 主算法

2.7 算法時間復雜度分析

3 示例分析

3.1 小規(guī)模示例分析

3.2 隨機算例測試

3.3 真實案例分析

4 結束語

本文針對疫情期間生活物資集散點選址問題，首先得出一些可以降低問題規(guī)模的數(shù)學性質并證明，其中某些性質可以批量地確定某些備選點必須開設或者必須不開設從而降階；然后設計出上下界子算法；最后在上下界子算法的基礎上設計出能減小問題規(guī)模且能求出最優(yōu)解的降階回溯算法。

從理論分析可以看出，采用本文設計的算法求解時，在回溯搜索之前和回溯搜索過程中均可以降低問題的規(guī)模。在例3中，通過降階子算法將待判斷備選點數(shù)量從7個降低到3個，時間復雜度由27下降到23，同時也將待處理居民點數(shù)量從8個降低到5個；在搜索解空間二叉樹過程中又通過性質6進行降階，加快了求解速度。在隨機算例測試中，各測試數(shù)據(jù)集都能通過降階子算法部分減小問題規(guī)模，并且在回溯搜索時又能實現(xiàn)降階或剪枝，進一步加快算法的求解速度。

在未來的研究中，一方面考慮繼續(xù)探索求解應急生活物資集散點選址問題的高效準確的啟發(fā)式算法，以應對中大規(guī)模問題；另一方面考慮將應急生活物資集散點選址問題與其上游問題，即應急生活物資儲備庫選址問題相融合，構建一個雙層選址模型，探究該問題的數(shù)學性質并提出高效的求解算法。

參考文獻：

［1］王非，徐渝，李毅學. 離散設施選址問題研究綜述 ［J］. 運籌與管理，2006，15（5）： 64-69. （Wang Fei，Xu Yu，Li Yixue. Review on facility location models ［J］. Operational Research and Management Science，2006，15（5）： 64-69.）

［2］劉勇，馬良，寧愛兵. 給定限期條件下應急選址問題的量子競爭決策算法 ［J］. 運籌與管理，2011，20（3）： 66-71. （Liu Yong，Ma Liang，Ning Aibing. Quantum competitive decision algorithm for emergency facility location with a given deadline ［J］. Operational Research and Management Science，2011，20（3）： 66-71.）

［3］袁穎. 重大疫情下的應急醫(yī)療服務設施選址研究 ［D］. 重慶： 重慶郵電大學，2021. （Yuan Ying. Research on emergency medical service facilities location for serious epidemic diseases ［D］. Chongqing： Chongqing University of Posts amp; Telecommunications，2021.）

［4］宋英華，裴俊龍，方丹輝，等. 常態(tài)化疫情防控背景下區(qū)域應急醫(yī)療物資選址—分配模型 ［J］. 中國安全生產科學技術，2021，17（11）： 5-9. （Song Yinghua，Pei Junlong，F(xiàn)ang Danhui，et al. Location-allocation model of regional emergency medical material under background of normalized epidemic prevention and control ［J］. Journal of Safety Science and Technology，2021，17（11）： 5-9.）

［5］王紫巖. 新冠疫情背景下的防疫物資儲備中心選址—分配研究 ［D］. 上海： 東華大學，2022. （Wang Ziyan. A study on the location and distribution of epidemic prevention supplies storage centers in the context of the COVID-19 ［D］. Shanghai： Donghua University，2022.）

［6］郗蒙浩，張靜，趙秋紅，等. 基于P-center問題的國家級應急物資儲備設施選址優(yōu)化布局研究 ［J］. 自然災害學報，2019，28（3）： 123-129. （Xi Menghao，Zhang Jing，Zhao Qiuhong，et al. Research of location problem of national emergency reserve facilities for emergency relief based on P-center problem ［J］. Journal of Natural Disasters，2019，28（3）： 123-129.）

［7］朱莉，丁家蘭，計夢婷. 考慮區(qū)域異質性的應急物資選址—分配優(yōu)化 ［J］. 系統(tǒng)管理學報，2018，27（6）： 1142-1149. （Zhu Li，Ding Jialan，Ji Mengting. Location-allocation optimization of emergency relief materials considering regional heterogeneity. ［J］. Journal of Systems amp; Management，2018，27（6）： 1142-1149.）

［8］于冬梅，高雷阜，趙世杰. 可靠性應急設施選址多級覆蓋魯棒優(yōu)化模型 ［J］. 中國礦業(yè)大學學報，2019，48（4）： 919-927. （Yu Dongmei，Gao Leifu，Zhao Shijie. A robust hierarchical covering optimization model for reliability emergency facility location ［J］. Journal of China University of Mining amp; Technology，2019，48（4）： 919-927.）

［9］叢雯婧. 臺風災害情景下的區(qū)域應急物資儲備庫選址研究 ［D］. 杭州： 杭州電子科技大學，2020. （Cong Wenjing. Emergency material storage location decision research based on scenario of typhoon disaster ［D］. Hangzhou： Hangzhou Dianzi University，2020.）

［10］鄭夏，馬良. 應急物資儲備中心多目標優(yōu)化選址的仿真研究 ［J］. 計算機仿真，2019，36（9）： 473-478. （Zheng Xia，Ma Liang，Simulation research of emergency materials reserve center multi-objective optimization location ［J］. Computer Simulation，2019，36（9）： 473-478.）

［11］劉博，徐曉敏. 政企協(xié)同視角下應急物資儲備庫選址優(yōu)化研究 ［J］. 北京信息科技大學學報： 自然科學版，2022，37（4）： 82-87. （Liu Bo，Xu Xiaomin. Study on site selection optimization of the emergency material reserve from the perspective of government-enterprise coordination ［J］. Journal of Beijing Institute of Machinery： Natural Science，2022，37（4）： 82-87.）

［12］彭大江，葉春明，萬孟然. 基于模糊需求的應急物資中心選址—路徑問題的算法研究 ［J］. 計算機應用研究，2022，39（12）： 3631-3638. （Peng Dajiang，Ye Chunming，Wan Mengran. Research on algorithm for emergency resource center location-routing problem based on fuzzy demand ［J］. Application Research of Compu-ters，2022，39（12）： 3631-3638.）

［13］Peng Dajiang，Ye Chunming，Wan Mengran. A multi-objective improved novel discrete particle swarm optimization for emergency resource center location problem ［J］. Engineering Applications of Artificial Intelligence，2022，111（5）： 104725.

［14］Karatas M，YakIcI E. A multi-objective location analytics model for temporary emergency service center location decisions in disasters ［J］. Decision Analytics Journal，2021，1（11）： 100004.

［15］Yu Wuyang. Pre-disaster location and storage model for emergency commodities considering both randomness and uncertainty ［J］. Safety Science，2021，141（9）： 105330.

［16］宋英華，蘇貝貝，霍非舟，等. 考慮動態(tài)需求的應急物資配送中心快速選址研究 ［J］. 中國安全科學學報，2019，29（8）： 172-177. （Song Yinghua，Su Beibei，Huo Feizhou，et al. Research on rapid location selection of emergency materials distribution center considering dynamic demand ［J］. China Safety Science Journal，2019，29（8）： 172-177.）

［17］胡少龍，范婷睿. 基于機器學習的樣本均值近似算法求解應急物資配置問題 ［J］. 管理現(xiàn)代化，2022，42（3）： 32-38. （Hu Shao-long，F(xiàn)an Tingrui. Sample mean approximation algorithm based on machine learning to solve emergency materials allocation problem ［J］. Management Modernization，2022，42（3）： 32-38.）

［18］譚正園，李嘉麗，唐琳婕，等. 新冠肺炎疫情下應急物資儲備倉庫選址研究——以南寧市為例 ［J］. 中國物流與采購，2022，43（14）： 57-58. （Tan Zhengyuan，Li Jiali，Tang Linjie，et al. Study on the location of emergency supplies storage ware-house under the COVID-19 epidemic： a case study of Nanning City ［J］. China Logistics amp; Purchasing，2022，43（14）： 57-58.）

［19］張敏，黃鈞. 考慮關鍵交通路段失效情景的中央儲備庫選址評估 ［J］. 運籌與管理，2018，27（10）： 11-16. （Zhang Min，Huang Jun. Evaluation of national storehouse location with failure scenarios of key traffic road ［J］. Operational Research and Management Science，2018，27（10）： 11-16.）

［20］姜凱凱，高浥塵，孫潔. 依托便利店構建生活物資應急配送終端體系——以日本便利店的災后救援經驗為例 ［J］. 國際城市規(guī)劃，2021，36（5）： 121-128. （Jiang Kaikai，Gao Yichen，Sun Jie. Exploration on the emergency distribution terminal system of subsis-tence goods based on convenience stores： experience of convenience stores in post-disaster rescues of Japan ［J］. Urban Planning International，2021，36（5）： 121-128.）

［21］《運籌學》教材編寫組. 運籌學 ［M］. 4版. 北京： 清華大學出版社，2012： 318-320. （“Operations Research” Writing Group. Operations research ［M］. 4th ed. Beijing： Tsinghua University Press，2012： 318-320.）

［22］Lindvall T. On a routing problem ［J］. Probability in the Enginee-ring and Informational Sciences，2004，18（3）： 329-337.