基于機器學習的區(qū)域性綜合資源調(diào)度與優(yōu)化算法設(shè)計

中圖分類號：TN915.04-34；TP391.9 文獻標識碼：A 文章編號：1004-373X（2025）16-0128-05

Machine learning based design of regional comprehensive resource scheduling andoptimizationalgorithm

LEIChengtao1，ZHANGLi2，HANTengfei1 （1.College of Architecture and Environment，Sichuan University，Chengdu 61oo65，China; 2.Sichuan University Engineering Design and Research Institute Co.，Ltd.， Chengdu 61O065，China）

Abstract：Inorderto enhancethe emergencyresource scheduling capabilityinurbandisaster preventionandreduction，a regional comprehensiveresourceschedulingandoptimizationalgorithmbasedonmachinelearning isproposed.Inthisalgorithm， thecontinumapproximation（CA）modelisused todeterminetheoptimalreplenishmentquantityandinventorylevelforsevering a specific location，and K -means clustering algorithm is used to cluster the pre allocated routes，making emergency resource schedulingmoreeficient.ByintroducingtheChristofiedesalgorithm，theschedulingpathisfurtheroptimized toensurefinding anaproximateoptimal solutionin polynomial time.Theexperimentalresultsshowthatthe proposed scheduling methodcannot onlyfindefectiveresourcescheduling strategiesinurban disasteremergencyresponse toimproveresourceutilizationand responsespeed，butalsooutperform themethodbasedonlocalobservationinboth motioncostandtotalcost，verifyingits advantages in emergency resource scheduling.

Keywords：emergencyresource scheduling；path optimization;machine learning;continuousapproximation model; K-means clustering algorithm;Christoffedesalgorithm

0 引言

自然災(zāi)害通常會對人們造成一定的安全威脅和財產(chǎn)損失，迅速向受災(zāi)區(qū)域部署必要的救濟物資是救災(zāi)行動的首要任務(wù)[1-2]。然而應(yīng)急物流調(diào)度問題不同于常規(guī)應(yīng)用，在緊急情況下規(guī)劃和實施的時間窗口極為有限[3-4]。在城市防災(zāi)與減災(zāi)過程中，傳統(tǒng)的應(yīng)急資源調(diào)度方法已經(jīng)無法滿足現(xiàn)代城市高效、準確和實時響應(yīng)的需求。隨著城市規(guī)模的不斷擴大及自然災(zāi)害的頻發(fā)，應(yīng)急資源的調(diào)度和管理面臨著巨大的挑戰(zhàn)。為了應(yīng)對這些挑戰(zhàn)，基于機器學習的智能調(diào)度優(yōu)化算法應(yīng)運而生[5]。這些算法不僅能夠?qū)崟r獲取并處理各種應(yīng)急資源數(shù)據(jù)，還能通過優(yōu)化策略提高資源的利用效率和響應(yīng)速度。

針對防災(zāi)減災(zāi)的資源調(diào)度問題，本文設(shè)計了一種基于機器學習的區(qū)域性綜合資源調(diào)度與優(yōu)化算法，以提高城市防災(zāi)減災(zāi)和應(yīng)急調(diào)度的能力。在設(shè)計該算法時，首先利用連續(xù)逼近（ContinuumApproximation，CA）模型確定服務(wù)于給定位置路線的最佳補貨量和庫存水平；接著使用K均值聚類算法對預(yù)先分配的 K 條路線進行聚類，在完成聚類后，采用克里斯托菲德斯（Christofides）算法解決旅行商問題；最后綜合應(yīng)用上述方法，得出最佳的應(yīng)急資源調(diào)度方案。本文所提的調(diào)度策略不僅能夠提高資源調(diào)度效率，還能在面對復(fù)雜多變的災(zāi)害環(huán)境時，提供更加靈活和可靠的解決方案。

1問題描述

應(yīng)急物流調(diào)度模型的目標是從政府或供應(yīng)商的角度提供補貨計劃和路線解決方案，以最小化總運輸成本、管道庫存成本和延期交貨的持有成本[7-8]。假設(shè)每個加油站都以最高容量運行，其可以表述為具有確定性需求的容量限制庫存路線問題。假設(shè)一組分散在平面上的客戶S，以及除客戶之外的所有卡車都將從那里出發(fā)的倉庫，計算每對客戶之間的歐幾里得距離 d_ij ，并設(shè)其互為對稱。由此可得3個控制部分：路線模式、調(diào)度間隔和每條路線的客戶庫存水平。該問題可以用以下混合整數(shù)模型表述：

0?I_k?F

0?DH_k?V

x_ij^k={0，1}

u_i^k={1，2，…}

式中： T 為總成本； H_k 代表路線 k 的發(fā)車間隔，單位為 h;I_k 代表路線 k 的庫存水平，單位為 kg;x_ij^k 表示邊分配的二進制變量； u_j^k 表示用于路由索引的整數(shù)變量； C_m^k 表示路線 k 的運動成本，單位為元 /km ： C_h 代表持有成本，單位為元 /kg;D 為需求成本，單位為元 /kg;F 為設(shè)施容量； V 為車輛裝載容量。

目標函數(shù)由總行程距離和有缺貨的總持有成本除以每個間隔運輸?shù)纳唐妨拷M成。由于最大函數(shù)不允許補貨時出現(xiàn)剩余庫存，且需求是確定的，因此本文所設(shè)計的模型中不存在任何剩余庫存，并且引入的均為純粹的庫存成本。式（2）和式（3）規(guī)定了正在設(shè)計的路線數(shù)量；式（4）和式（5）構(gòu)成了路線的流動條件并消除了子路線；式（6）～式（9）定義了容量約束以及變量域。

由于上述公式涉及二進制變量、整數(shù)變量和非整數(shù)變量，難以通過分析解決，因此，本文進一步提出一種先聚類后生成的啟發(fā)式路線構(gòu)造方法來處理上述問題。

2算法設(shè)計

在應(yīng)急物流調(diào)度模型中提出啟發(fā)式路線構(gòu)造方法，首先，通過連續(xù)逼近模型確定服務(wù)于給定位置路線的最佳補貨量和庫存水平；接著，利用K均值聚類算法對預(yù)先分配的 K 條路線進行聚類；最后，應(yīng)用Christofides方法[解決所選聚類的旅行商問題，從而得到最優(yōu)調(diào)度方案。

2.1連續(xù)逼近模型

本文提出了一個使用連續(xù)逼近模型的解決方案，并采用集群優(yōu)先、路線第二的理念。通過假設(shè)設(shè)施密度在空間中緩慢發(fā)生變化，并采用連續(xù)函數(shù)3進行近似計算，從而解決一對多的分布問題。由某條路線提供服務(wù)的某個位置A的目標函數(shù)可由以下公式表示：

式中：

α₁=2C_dr+C_s

分解后的目標函數(shù)如下所示：

式中： Z 為站點總成本； n 為每條路線的停靠站點； v 為補充數(shù)量； 代表每千米運輸成本； C_dr 為每次停車成本；C_s 表示每次調(diào)度成本； C_i 為管道庫存成本； C_b 為延期綜合成本； C_h 為倉儲成本； δ（x） 為位置 的設(shè)施密度； D_v 為補充數(shù)量所對應(yīng)的需求成本。

式（11）式（12）代表運動成本，包括停車、巡航和調(diào)度成本；式（13）是管道庫存成本；式（14）式（15）表示延期交貨的持有成本。綜上所述，目標成本函數(shù)最終以元/kg為單位，且其數(shù)值主要取決于位置因素。

將目標函數(shù)最小化為受約束的非線性計算過程，公式如下：

（17式中：

式（18）～式（22）表示5個約束條件：式（18）定義卡

車容量；式（19）限制空路線，即無停靠站的路線不可行；

式（20）規(guī)定不允許剩余庫存；式（21）為設(shè)施容量， ；式（22）是庫存水平的非負約束。

本文使用KKT條件[14-15]求解具有封閉邊界的非線性規(guī)劃問題，具體表示為：

由于上文式（18）～式（22）代表5個約束條件，因此總共需要調(diào)查25個約束案例。然而基于現(xiàn)實的可行性考慮，當進行簡易的基礎(chǔ)性分析時，只需要對以下兩個約束案例進行調(diào)查：

1）式（18），規(guī)定是否使用滿載卡車；

2）式（20），規(guī)定是否允許延期交貨。

其余的約束條件則假定為不具有約束性，當應(yīng)用場景中需要時，只需另行調(diào)查賦值即可生效。

當約束條件確定后，作為位置向量 x 的函數(shù)，可得CA模型的解為：

式中上標“*\"表示最優(yōu)解。

2.2聚類和路由

連續(xù)近似的解給出了聚類的指導(dǎo)方向，并將車輛路線問題轉(zhuǎn)化為針對預(yù)分配客戶集的旅行商問題。首先，提出了一個基于局部觀察的過程，僅需在制定路線時尋找停靠點和庫存水平，其目標條件是集群位置的屬性；然后，使用Christofides算法為選定的集群確定最佳路線。Christofides算法是一種經(jīng)典的近似算法，能夠在多項式時間內(nèi)找到近似最優(yōu)解，且其解的質(zhì)量有嚴格的理論保證。該過程可以具體描述如下：

1）初始化倉庫；

2）前往最近的車站，將其設(shè)置為參考點，使用3個最近的設(shè)施計算本地設(shè)施密度，并根據(jù)CA解決方案計算 n^* ：

3）選擇最近的 n^' 站，通過閾值排除遠程站；

4）使用Christofides算法解決旅行商問題；

5）刪除訪問過的車站；

6）前往距離參考點最近的車站，從步驟2）重復(fù)迭代。

Christofides算法能夠同時解決聚類和路由問題，具有較強的清除屬性，該屬性會在轉(zhuǎn)向另一個方向之前耗盡來自一個方向的倉庫客戶點。為了防止錯誤分配，當在遠程集群中錯誤地獲得較大的 n^' 時，可通過觀察分配一個閾值，即使選擇了較多小于 n^* 的客戶，算法也會根據(jù)該閾值對客戶進行篩選并丟棄遠程客戶。

為了與基于局部觀察的路由解決方案進行比較，本文研究了另一種監(jiān)督整個客戶集平均屬性的聚類方法，即K均值聚類算法。該方法通過預(yù)先分配 K 條路線對設(shè)施進行聚類，路線由加權(quán)平均干線運輸距離和設(shè)施密度確定。該過程描述如下：

1）使用加權(quán)平均 r，δ 求解CA模型，即可得出 n^*

2）預(yù)先分配 K=|S|/n^* 條路線；

3）使用K均值聚類方法進行聚類；

4）使用Christofides算法解決所選聚類旅行商問題；

5）根據(jù)距離對客戶進行聚類，并避免錯誤分配聚類。

2.3調(diào)度算法整體架構(gòu)

根據(jù)本文提出的基于機器學習的區(qū)域性綜合資源調(diào)度與優(yōu)化算法，可以設(shè)計出如圖1所示的城市應(yīng)急資源調(diào)度框架。當城市發(fā)生災(zāi)害時，將包含車庫位置、加油站位置、城市地圖和道路標記、城市區(qū)域人口和目標位置等信息的數(shù)據(jù)輸入到綜合資源調(diào)度與優(yōu)化算法中進行計算。

首先連續(xù)逼近模型會計算出對應(yīng)的路線結(jié)果，以及給定位置的路線最佳補貨量和庫存水平；接著由K均值聚類算法對連續(xù)逼近模型計算得到的 K 條路線進行聚類；然后由Christofides算法解決聚類的旅行商問題；最終得到最優(yōu)的資源調(diào)度方案。

圖1城市應(yīng)急資源調(diào)度框架

3實驗結(jié)果與分析

3.1 實驗數(shù)據(jù)

為實現(xiàn)生成調(diào)度車輛運行策略的優(yōu)化自標，需要擬定一組原始數(shù)據(jù)，其中需包括車庫位置、救災(zāi)物資補給站位置和每個站點的需求。為了簡化問題，本文做出了部分假設(shè)：

1）假設(shè)受自然災(zāi)害的影響，某條公路是進人災(zāi)害區(qū)域的唯一可用道路，而車庫位于公路的出口；

2）假設(shè)并非所有的物資補給站都能正常運行。

本文隨機選擇了其中一個物資補給站作為目標點，但由于假設(shè)的物資需求量與每個物資補給站附近幾個街區(qū)的人口數(shù)量有關(guān)，因此，需求數(shù)據(jù)應(yīng)根據(jù)區(qū)域內(nèi)的常住人口數(shù)量得出。

3.2實驗結(jié)果與分析

本文以采集到的某城市2020—2023年區(qū)域性災(zāi)害數(shù)據(jù)為樣本，利用所提出的算法綜合優(yōu)化了資源調(diào)度策略。根據(jù)算法中的約束條件和實際場景需求，本次實驗需要調(diào)查共計4個約束案例。4個案例均使用CA模型完成評估，并通過K均值聚類算法對CA模型的計算結(jié)果進行聚類和路由，具體結(jié)果如表1所示。

由表1可知：案例2即假設(shè)所有約束均不受限，雖然產(chǎn)生了最佳結(jié)果，但是違反了約束案例1，因此不可行；同樣，案例3不允許延期交付的約束也不可行。因此，最佳可行解決方案由案例1產(chǎn)生，且其中每輛卡車都滿載離開倉庫。

接著根據(jù)上述的最佳方案，將本文K均值聚類方法與基于局部觀察的方法進行對比，比較其運動成本和總成本的差異，具體結(jié)果如表2所示。由表2可知，基于局部觀察的方法產(chǎn)生的運動成本高于K均值聚類方法，這是因為節(jié)點在距離方面聚類更完全，并且K均值聚類的方法總成本更低。

表2兩種聚類方法的對比結(jié)果 元/km

上述結(jié)果表明，K均值聚類算法的加入能夠更有利于找到最優(yōu)的應(yīng)急資源調(diào)度策略，且成本更低，速度更快。

4結(jié)論

為了應(yīng)對城市防災(zāi)減災(zāi)中應(yīng)急資源調(diào)度的挑戰(zhàn)，本文提出了一種基于機器學習的區(qū)域性綜合資源調(diào)度與優(yōu)化算法。該算法能夠?qū)崟r獲取和處理應(yīng)急資源數(shù)據(jù)，提高資源利用效率和響應(yīng)速度，并提升調(diào)度方案的整體效率和可靠性。所提出的算法融合了連續(xù)逼近模型、K均值聚類算法以及Christofides旅行商問題解決算法，使得應(yīng)急資源的調(diào)度更為高效。同時優(yōu)化了調(diào)度路徑，確保模型能夠在多項式時間內(nèi)找到近似最優(yōu)解，提高了調(diào)度方案的可靠性和可行性。通過實驗分析與對比可知，本文所提出的基于K均值聚類算法和Christofides算法的調(diào)度方法在運動成本和總成本上均優(yōu)于基于局部觀察的方法。

注：本文通訊作者為張莉。

表1計算結(jié)果

參考文獻

[1]別昊田，黃國平.考慮洪澇災(zāi)害強度的城市應(yīng)急物流配送中心選址研究[J].湖南工業(yè)大學學報，2024，38（5）：76-83.

[2]肖遺規(guī)，李毅群.基于云模型的城市自然災(zāi)害下應(yīng)急物流能力評價[J].洛陽理工學院學報（自然科學版），2024，34（1）：67-71.

[3]周青超，葉春明，耿秀麗.基于IT2F-BWM-MABAC方法的應(yīng)急物流設(shè)施選址方案評價[J].中國安全科學學報，2024，34（4）：226-231.

[4]馬文璇，溫馨，徐劍.基于大數(shù)據(jù)的事故災(zāi)難應(yīng)急物流信息資

源整合內(nèi)在機理與實踐路徑探析[J].情報科學，2024，42（3）：183-190.

[5]張曄，鮑亮.基于機器學習的服務(wù)組合技術(shù)研究進展[J].電子科技，2022，35（11）：58-63.

[6]孫焱焱.基于機器學習的林火預(yù)警和應(yīng)急管理模型研究[D].南京：南京林業(yè)大學，2023.

[7]陳妍.基于AHP方法的應(yīng)急物流配送網(wǎng)絡(luò)優(yōu)化研究[J].信陽農(nóng)林學院學報，2024，34（1）：114-119.

[8]謝英紅，趙蕓潔，韓曉微，等.改進AHP-反熵權(quán)法的應(yīng)急物流運輸路線安排決策[J].沈陽大學學報（自然科學版），2023，35（6）：485-493.

[9]林偉杰，王勇，周林.基于加權(quán)二分圖的K均值最佳聚類數(shù)確定算法[J].計算機工程與設(shè)計，2023，44（4）：1104-1111.

[10]王海玲，楊俊杰.基于改進蜂群算法及K均值聚類的WSN分簇路由算法[J].計算機應(yīng)用與軟件，2022，39（9）：178-182.

[11]姚麗敏.基于變分圖自動編碼器與K均值聚類的虛擬網(wǎng)絡(luò)嵌入算法應(yīng)用[J].哈爾濱師范大學自然科學學報，2024，40（1）：47-54.

[12]孟慶欣.城市無人物流配送的路徑優(yōu)化與近似算法[D].杭州：浙江理工大學，2022.

[13]王能發(fā)，楊哲，劉自鑫.集值偽連續(xù)函數(shù)及其在非合作與合作博弈中的應(yīng)用[J].應(yīng)用數(shù)學學報，2023，46（5）：804-812.

[14]黃曉美，唐國吉.區(qū)間值優(yōu)化問題的KKT和弱互補近似KKT條件[J].數(shù)學物理學報，2023，43（6）：1897-1913.

[15]陶盈吟，楊儀，代祥光，等.基于KKT條件的稀疏編碼算法收斂性研究[J].南京信息工程大學學報（自然科學版），2020，12（3）：360-363.

[16]李林超，魏璞瑄，杜博文.突發(fā)災(zāi)害下考慮地鐵網(wǎng)絡(luò)脆弱性的應(yīng)急資源調(diào)度方法[J].鐵道科學與工程學報，2025，22（1）：102-112.

[17]趙宏偉，趙西珂，王陽陽，等.化工園區(qū)突發(fā)事故應(yīng)急資源調(diào)度策略[J].沈陽大學學報（自然科學版），2023，35（5）：449-458.

作者簡介：雷成濤（1998—），男，陜西咸陽人，碩士研究生，研究方向為智能規(guī)劃及其優(yōu)化技術(shù)。張莉（1994—），女，四川樂山人，博士研究生，研究方向為城市韌性防災(zāi)規(guī)劃。