基于多旅行商問題的應(yīng)急設(shè)施服務(wù)區(qū)劃分模型

趙 星，吉 康，申 珂

(河海大學(xué)土木與交通學(xué)院，南京210098)

0 引 言

近年來，全球范圍內(nèi)各類突發(fā)公共衛(wèi)生事件頻繁發(fā)生，例如，2002年SARS 事件，2019年新型冠狀病毒事件.面對此類區(qū)域性的突發(fā)公共衛(wèi)生事件，疫區(qū)的應(yīng)急設(shè)施服務(wù)區(qū)劃分，例如臨時醫(yī)院，物資周轉(zhuǎn)中心，避難所等，可以幫助物資配送及緊急救援，是控制疫情發(fā)展，保障民眾生活需要的基本前提.

應(yīng)急設(shè)施位置選擇對服務(wù)區(qū)域劃分具有重要影響，較多研究將應(yīng)急設(shè)施選址問題與服務(wù)區(qū)域劃分問題聯(lián)合求解.典型選址—分配(Location-Allocation，L-A)模型根據(jù)其優(yōu)化目標(biāo)不同可以分為：P-中值模型，P-中心模型，覆蓋模型，均已有成熟的研究應(yīng)用[1].Pan[2]以各個疏散集結(jié)點到避難所的加權(quán)距離和最小為優(yōu)化目標(biāo)，構(gòu)建了一種基于P-中值問題的避難所選址—分配模型，采用遺傳算法進(jìn)行求解，可同步獲得避難所最優(yōu)選址與服務(wù)區(qū)劃分方案.郭鵬輝等[3]研究了災(zāi)后救援物資選址—路徑—配給的集成優(yōu)化問題，并基于進(jìn)化算法對問題進(jìn)行求解.

在應(yīng)急設(shè)施位置已知的情況下，設(shè)施服務(wù)區(qū)劃分可轉(zhuǎn)化為多旅行商問題求解.多旅行商問題(Multiple Traveling Salesman Problem，MTSP)是在傳統(tǒng)的旅行商問題(Travelling Salesman Problem，TSP)基礎(chǔ)上引入多個旅行商和對應(yīng)多個出發(fā)城市的變種問題.事實上，存在多個應(yīng)急設(shè)施的服務(wù)區(qū)劃分問題，與多起點的MTSP(旅行商位于不同的出發(fā)城市)存在共通之處.通常可將應(yīng)急設(shè)施視為虛擬的旅行商，應(yīng)急設(shè)施服務(wù)容量為旅行商攜帶的商品數(shù)量，M為應(yīng)急設(shè)施個數(shù)，則虛擬旅行商的旅行路徑即可匹配為應(yīng)急設(shè)施的服務(wù)區(qū)域.通過應(yīng)急設(shè)施服務(wù)區(qū)劃分，可以將多倉庫多約束的應(yīng)急調(diào)度問題轉(zhuǎn)換為多個單倉庫的應(yīng)急調(diào)度問題，并預(yù)處理相關(guān)約束條件，再利用傳統(tǒng)的VRP 或TSP 方法進(jìn)行應(yīng)急路徑規(guī)劃.針對此類問題，Steven等[4]采用聚集聚類方法對多起點的MTSP進(jìn)行求解.Liu等[5]利用圖論將MTSP分解為TSP，再進(jìn)行模型最優(yōu)解的獲取.此外，Alencar等[6]具體研究MTSP在物資配送、路徑規(guī)劃方面的實際應(yīng)用，并提出了相應(yīng)算法對問題求解，基本思路為先通過旅行商旅行路徑劃分服務(wù)區(qū)域，再進(jìn)行路徑規(guī)劃.

基于MTSP 的應(yīng)急設(shè)施服務(wù)區(qū)劃分研究較為不足，可以看出：MTSP 契合多設(shè)施多集散中心的應(yīng)急設(shè)施服務(wù)區(qū)劃分問題特征，具有重要的研究應(yīng)用價值.本文構(gòu)建一種基于MTSP的應(yīng)急設(shè)施服務(wù)區(qū)劃分模型，并利用針對P-中值選址模型的整數(shù)規(guī)劃方法及禁忌搜索算法，結(jié)合LKH 求解器提出一種復(fù)合算法對模型進(jìn)行求解，從而為物資配送及各類緊急救援方案的制定提供依據(jù).

1 模型構(gòu)建

基于MTSP 構(gòu)建一種應(yīng)急設(shè)施服務(wù)區(qū)劃分模型，將各應(yīng)急設(shè)施視為虛擬旅行商，在網(wǎng)絡(luò)需求，資源供應(yīng)，流量平衡等約束條件下，以最小化遍歷區(qū)域內(nèi)全部集散中心的綜合旅行時間成本為優(yōu)化目標(biāo)，獲取模型最優(yōu)的區(qū)域應(yīng)急設(shè)施服務(wù)區(qū)劃分方案.

1.1 基本假設(shè)

(1)具備先進(jìn)的應(yīng)急調(diào)度系統(tǒng)及信息更新方式，所有應(yīng)急設(shè)施信息共享，均服從系統(tǒng)的聯(lián)合管理，以綜合效益最大化進(jìn)行服務(wù)區(qū)劃分.各應(yīng)急設(shè)施的位置及資源儲存情況已知，且能夠滿足區(qū)域內(nèi)的全部資源需求.

(2)各個集散中心的位置及資源需求已知，且基于公平原則進(jìn)行資源獲取.

(3)應(yīng)急車輛的每次運輸均從其所屬的應(yīng)急設(shè)施出發(fā)，前往服務(wù)區(qū)內(nèi)的集散中心發(fā)放物資，并最終返回該應(yīng)急設(shè)施.

1.2 參數(shù)及變量

(1)參 數(shù).

N——節(jié)點集合，N=E∪D；

Z——應(yīng)急設(shè)施服務(wù)區(qū)域集合；

D——應(yīng)急設(shè)施集合；

E——集散中心集合；

nz——應(yīng)急設(shè)施服務(wù)區(qū)數(shù)量；

nd——應(yīng)急設(shè)施數(shù)量；

ne——集散中心數(shù)量；

——集散中心i的資源需求數(shù)量，i∈E；

rj——應(yīng)急設(shè)施j的資源供應(yīng)數(shù)量，j∈D；

dxy——鄰接矩陣中節(jié)點x到節(jié)點y的應(yīng)急車輛行程時間，x,y∈N；

(2)變 量.

決策變量：

——若，表示集散中心i被分配至應(yīng)急設(shè)施j；若，表示集散中心i未被分配至應(yīng)急設(shè)施j.

中間變量：

μxy——旅行商從節(jié)點x出發(fā)前往節(jié)點y的次數(shù)，若μxy=0，表示旅行商未從節(jié)點x出發(fā)前往節(jié)點y；

Ej——應(yīng)急設(shè)施j所服務(wù)的集散中心集合；

Pj——應(yīng)急設(shè)施j所在的設(shè)施服務(wù)區(qū)的全部節(jié)點集合，Pj=Ej∪{j} .

1.3 模型結(jié)構(gòu)

(1)目標(biāo)函數(shù).

(2)約束條件.

式(1)為模型優(yōu)化目標(biāo)函數(shù)，要求最小化遍歷區(qū)域內(nèi)全部集散中心的綜合旅行時間成本.式(2)確保每個服務(wù)區(qū)均圍繞一個應(yīng)急設(shè)施進(jìn)行劃分.式(3)確保在同一個應(yīng)急設(shè)施服務(wù)區(qū)內(nèi)，任意集散中心必然與該服務(wù)區(qū)內(nèi)的應(yīng)急設(shè)施或其他集散中心鄰接，換而言之，保證設(shè)施服務(wù)區(qū)的聚團(tuán)劃分.式(4)確保任意一個應(yīng)急設(shè)施服務(wù)區(qū)內(nèi)的集散中心物資需求總量不能超過該服務(wù)區(qū)應(yīng)急設(shè)施的資源供應(yīng)數(shù)量.式(5)確保各個應(yīng)急設(shè)施被分配的集散中心數(shù)量之和等于集散中心總數(shù).式(6)要求每個集散中心僅被分配至一個應(yīng)急設(shè)施.因此，式(5)和式(6)共同構(gòu)成集散中心全覆蓋約束.式(7)確保網(wǎng)絡(luò)中的應(yīng)急設(shè)施資源總量可以滿足全部資源集散需求.式(8)為流量平衡約束，保證任意節(jié)點的旅行商抵達(dá)次數(shù)等于該節(jié)點的旅行商出發(fā)次數(shù).

2 求解算法

MTSP 是TSP 的變種形式，屬于組合優(yōu)化問題，在計算復(fù)雜度上屬于NP 困難問題，難以精確求解.因此，本文基于P-中值選址模型的優(yōu)化理念及禁忌搜索(Tabu Search，TS)算法，結(jié)合LKH求解器(Lin-Kernighan-Helsgaun TSP solver)對所構(gòu)建的應(yīng)急設(shè)施服務(wù)區(qū)劃分模型求解.

禁忌搜索算法是一種全局逐步尋優(yōu)的亞啟發(fā)式算法，可有效求解NP困難問題[7].LKH求解器是當(dāng)前求解TSP 及其變種問題的有效工具，其求解速度快，解的優(yōu)越性高，可以為目前所有能夠精確求解的TSP實例找到最優(yōu)解.

首先參考P-中值選址模型的優(yōu)化理念，利用整數(shù)規(guī)劃方法形成初步可行的設(shè)施服務(wù)區(qū)劃分方案；然后基于禁忌搜索算法的理念，通過迭代方式，不斷選取集散中心執(zhí)行移動、交換操作；調(diào)用LKH 求解器計算目標(biāo)函數(shù)值的變化，使初始方案向目標(biāo)函數(shù)優(yōu)化方向搜索，最終獲得模型的局部最優(yōu)解.算法流程如圖1所示，詳細(xì)步驟如下.

Step 0初始化.輸入應(yīng)急設(shè)施集合D，設(shè)施資源供應(yīng)數(shù)量rj，集散中心集合E，各個集散中心的資源需求，網(wǎng)絡(luò)中全部鄰接節(jié)點之間的行程時間dxy.

Step 1參考P-中值選址模型，在約束條件下，以最小化總資源旅行成本，即集散中心到應(yīng)急設(shè)施的旅行時間成本與集散中心資源需求數(shù)量的乘積和為優(yōu)化目標(biāo)，初步劃分應(yīng)急設(shè)施服務(wù)區(qū).具體而言，可以通過Dijkstra算法獲取各個集散中心到各個應(yīng)急設(shè)施的最短路徑，然后將集散中心資源需求數(shù)量作為權(quán)重系數(shù)，以歸屬關(guān)系作為0-1變量直接求解，形成服務(wù)區(qū)劃分初始可行解.

Step 2將應(yīng)急設(shè)施j作為虛擬旅行商，以總旅行時間成本最小為目標(biāo)對其服務(wù)區(qū)域內(nèi)的集散中心進(jìn)行遍歷，即將問題轉(zhuǎn)化為TSP問題.在此基礎(chǔ)上，通過LKH 求解器快速求解其最小的TSP 時間成本.以此類推，獲得各應(yīng)急設(shè)施服務(wù)區(qū)的最小TSP時間成本，得到初始可行解的目標(biāo)函數(shù)值Ttsp.

Step 3將當(dāng)前模型最優(yōu)解作為禁忌對象，執(zhí)行禁忌搜索.設(shè)置備選搜索步長為{0，1，2，3}，禁忌長度為4，最大迭代次數(shù)為nmax，T0=Ttsp，n=0，l=0.

Step 4從當(dāng)前模型最優(yōu)解中隨機選擇應(yīng)急設(shè)施服務(wù)區(qū)域z1，從剩余區(qū)域集合中隨機選擇一個與z1鄰接的區(qū)域z2.執(zhí)行z1→z2，根據(jù)鄰接矩陣篩選出區(qū)域z1中與區(qū)域z2直接相連的集散中心，并將這些集散中心納入集合r1.隨機選擇搜索步長Mmove1，r1中隨機選擇Mmove1個集散中心，并將這些集散中心從區(qū)域z1中移到區(qū)域z2中.

Step 5更新區(qū)域z1，z2.執(zhí)行z2→z1，根據(jù)鄰接矩陣篩選出區(qū)域z2中與區(qū)域z1直接相連的集散中心，并將這些集散中心納入集合r2.隨機選擇搜索步長Mmove2，r2中隨機選擇Mmove2個集散中心，并將這些集散中心從區(qū)域z2中移到區(qū)域z1中.

圖1 算法流程Fig.1 Algorithm flowchart

Step 6基于式(3)，檢驗集散中心的連續(xù)性，確保服務(wù)區(qū)域聚團(tuán)分布. 如 果?x∈Pj,j∈D,?y∈Pj使得dxy≠∞，則進(jìn)入Step 7；反之，重新進(jìn)入Step 4.

Step 7基于式(4)，檢驗應(yīng)急設(shè)施資源容量約束.如果，則進(jìn)入Step 8；反之，重新進(jìn)入Step 4.

Step 8計算當(dāng)前候選解的目標(biāo)函數(shù)值Ttsp，檢驗是否滿足特赦規(guī)則.若Ttsp＜T0，則直接將該候選解替換為模型最優(yōu)解，更新禁忌列表，令T0=Ttsp，n=n+1，l=1，并重新進(jìn)入Step 4；反之，令l=l+1，進(jìn)入Step 9.

Step 9檢驗是否已達(dá)到禁忌長度. 如果l≥4，則進(jìn)入Step 10；反之，重新進(jìn)入Step 4.

Step 10以模型目標(biāo)函數(shù)作為評價標(biāo)準(zhǔn)，選擇候選集合中的最優(yōu)解及其目標(biāo)函數(shù)值Ttsp，替換該候選最優(yōu)解為模型最優(yōu)解，更新禁忌列表，令T0=Ttsp，n=n+1，l=0，并重新進(jìn)入Step 4.

終止條件：迭代次數(shù)n≥nmax.此時，對應(yīng)于當(dāng)前T0的應(yīng)急設(shè)施服務(wù)區(qū)劃分方案即為模型最優(yōu)解.

3 案例分析

基于浙江省寧波市北侖區(qū)實際拓?fù)渚W(wǎng)絡(luò)進(jìn)行案例分析.網(wǎng)絡(luò)布局如圖2 所示，該區(qū)域內(nèi)共有39條路段，23個交叉口，以及分別位于節(jié)點24，25，26的3 處應(yīng)急設(shè)施，具體道路參數(shù)如表1 所示.現(xiàn)假設(shè)該區(qū)域內(nèi)發(fā)生突發(fā)公共衛(wèi)生事件，并產(chǎn)生應(yīng)急資源調(diào)度需求.為確保資源集散的可達(dá)性，集散中心設(shè)置于各路段中點，網(wǎng)絡(luò)中各集散中心的資源需求數(shù)量及應(yīng)急設(shè)施的資源供應(yīng)數(shù)量如表2和表3所示(以防護(hù)服為例).

圖2 北侖區(qū)道路網(wǎng)絡(luò)Fig.2 Road network of Beilun District

表1 網(wǎng)絡(luò)道路屬性表Table 1 Road property in network

表2 集散中心資源需求數(shù)量Table 2 Resource demand of distribution centers

表3 應(yīng)急設(shè)施資源供應(yīng)數(shù)量Table 3 Resource supply of emergency facilities

假設(shè)網(wǎng)絡(luò)上設(shè)有應(yīng)急專用車道，應(yīng)急車輛路段通行速度為60 km/h，獲得模型最優(yōu)解如圖3 所示.該方案滿足模型的全部約束條件，劃分出的3個服務(wù)區(qū)域Ⅰ、Ⅱ、Ⅲ的TSP旅行時間成本分別為632，895，825 s，服務(wù)區(qū)資源需求分別為1 229，964，1 671 件，方案遍歷區(qū)域內(nèi)全部集散中心的綜合旅行時間成本Ttsp=2 352 s.

圖3 模型最優(yōu)服務(wù)區(qū)劃分方案Fig.3 Model optimal service area division scheme

為證明所提模型與算法的優(yōu)越性，基于參考文獻(xiàn)[4]，以應(yīng)急設(shè)施到所服務(wù)集散中心的總旅行時間成本最小為優(yōu)化目標(biāo)，在相同的模型約束條件下，采用聚類蟻群算法進(jìn)行服務(wù)區(qū)劃分對照，獲得對照方案如圖4所示.由圖4可知，劃分出的3個服務(wù)區(qū)域Ⅰ、Ⅱ、Ⅲ的TSP 旅行時間成本分別為591，1 088，873 s，服務(wù)區(qū)資源需求分別為1 267，936，1 661 件，遍歷區(qū)域內(nèi)全部集散中心的綜合旅行時間成本Ttsp=2 552 s.

圖4 服務(wù)區(qū)劃分參照方案Fig.4 Service area division control scheme

對比本文模型最優(yōu)方案與參照方案可以發(fā)現(xiàn)：在模型最優(yōu)方案中，盡管部分集散中心被分配到較遠(yuǎn)的應(yīng)急設(shè)施(如集散中心52距離應(yīng)急設(shè)施25、26的時間成本分別為368 s、270 s，在優(yōu)化過程中被從應(yīng)急設(shè)施26分配至應(yīng)急設(shè)施25)，但是模型最優(yōu)解的目標(biāo)函數(shù)得到一定程度的優(yōu)化，Ttsp降低了7.84%.這意味著，在各個應(yīng)急設(shè)施服務(wù)區(qū)內(nèi)，車輛從應(yīng)急設(shè)施出發(fā)遍歷該區(qū)域內(nèi)全部集散中心的綜合時間成本得到降低，有利于減少運輸時間成本，從整體上提高物資配送或緊急救援方案的效率.

在此基礎(chǔ)上，本文進(jìn)一步假設(shè)應(yīng)急設(shè)施24、25、26 處各有1 輛應(yīng)急運輸車輛，其車輛滿載為400件防護(hù)服，基于簡單插入算法[8]，獲得綜合物資配送方案如表4 所示，其中，車輛每次從應(yīng)急設(shè)施出發(fā)時更新為滿載，不足滿載時則更新為應(yīng)急設(shè)施剩余物資容量，配送完畢后返回應(yīng)急設(shè)施.

表4 綜合物資配送方案Table 4 Resource distribution scheme

4 結(jié) 論

本文構(gòu)建了一種基于多旅行商問題的應(yīng)急設(shè)施服務(wù)區(qū)劃分模型，將各應(yīng)急設(shè)施視為虛擬旅行商，以最小化遍歷區(qū)域內(nèi)全部集散中心的綜合旅行時間成本為優(yōu)化目標(biāo)劃分應(yīng)急設(shè)施服務(wù)區(qū)域，并設(shè)計一種復(fù)合算法對模型進(jìn)行求解.經(jīng)過實例驗證，該模型可以有效解決應(yīng)急設(shè)施服務(wù)區(qū)劃分問題，提高物資配送或緊急救援方案的效率.下一步將在本文研究基礎(chǔ)上，探究如何采用更合理的方法進(jìn)行各應(yīng)急設(shè)施物資配送或緊急救援的路徑規(guī)劃，以及應(yīng)急設(shè)施位置未知情況下的應(yīng)急設(shè)施選址—路徑問題.