■ 合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院 劉揚(yáng) 蔣建國(guó)

編者按：筆者依托省電子政務(wù)外網(wǎng)，以災(zāi)害應(yīng)急響應(yīng)聯(lián)盟、救災(zāi)物資分配和調(diào)度優(yōu)化算法為核心算法和技術(shù)，設(shè)計(jì)了應(yīng)急救災(zāi)物資調(diào)度系統(tǒng)，為政府應(yīng)急部門科學(xué)決策、高效有序地應(yīng)對(duì)重大自然災(zāi)害，提供一套示范性解決方案。

應(yīng)急組織架構(gòu)

對(duì)于多儲(chǔ)備點(diǎn)、多發(fā)放點(diǎn)、多種救災(zāi)物資的應(yīng)急調(diào)度問題，其難點(diǎn)在于如何在儲(chǔ)備點(diǎn)救災(zāi)物資有限的情況下，解決各物資發(fā)放點(diǎn)對(duì)稀缺救災(zāi)物資需求的沖突問題，尤其是在災(zāi)害應(yīng)急響應(yīng)的初期。

圖1 應(yīng)急組織架構(gòu)

當(dāng)特大自然災(zāi)害（如地震、洪水等）發(fā)生后，把多個(gè)儲(chǔ)備點(diǎn)的救災(zāi)物資融合在一起，如何快速有效的組成一個(gè)協(xié)作團(tuán)隊(duì)來響應(yīng)各發(fā)放點(diǎn)的救災(zāi)物資需求，需要相關(guān)政府職能部門科學(xué)決策。災(zāi)害應(yīng)急組織架構(gòu)如圖1所示。

然而，從哪些儲(chǔ)備點(diǎn)調(diào)撥救災(zāi)物資到哪些發(fā)放點(diǎn)，現(xiàn)階段，依然是領(lǐng)導(dǎo)或?qū)＜医M根據(jù)的個(gè)人經(jīng)驗(yàn)分配和調(diào)度，缺乏一個(gè)高效科學(xué)的救災(zāi)物資分配和調(diào)度集成系統(tǒng)，為此，我們?cè)O(shè)計(jì)了應(yīng)急救災(zāi)物資調(diào)度系統(tǒng)，根據(jù)各部門提供的相關(guān)動(dòng)態(tài)信息，為省政府應(yīng)急辦科學(xué)指揮和輔助決策提供智力保障。

省應(yīng)急救災(zāi)物資調(diào)度系統(tǒng)框架和核心算法

1.系統(tǒng)框架

依托地方電子政務(wù)外網(wǎng)傳輸平臺(tái)，采用Java Web后端編程技術(shù)、MySQL和百度地圖API，并結(jié)合前端編程語言 HTML、CSS、JavaScript和JQuery等，以災(zāi)害應(yīng)急響應(yīng)聯(lián)盟、救災(zāi)物資分配和調(diào)度集成優(yōu)化算法為核心算法和技術(shù)，設(shè)計(jì)系統(tǒng)框架如圖2所示。

（1）地圖展示模塊

地圖展示模塊默認(rèn)為本系統(tǒng)的主頁，通過調(diào)用百度地圖APIs，將默認(rèn)的應(yīng)急儲(chǔ)備點(diǎn)以矢量圖形的形式直觀、高亮地在地圖上標(biāo)記出來，且其中每一個(gè)矢量圖形都可以通過鼠標(biāo)單擊從而彈出一個(gè)信息窗口，顯示該儲(chǔ)備點(diǎn)的一個(gè)概況。在這里，我們依托地方電子政務(wù)外網(wǎng)，提取儲(chǔ)備點(diǎn)關(guān)鍵數(shù)據(jù)并存入數(shù)據(jù)中心。

圖2 應(yīng)急救災(zāi)物資調(diào)度系統(tǒng)框架

（2）儲(chǔ)備庫列表

儲(chǔ)備庫列表可以查看儲(chǔ)備點(diǎn)的具體情況，包括級(jí)別、經(jīng)緯度、所在城市、救災(zāi)物資列表和路由等信息。我們還可以通過進(jìn)一步點(diǎn)擊“修改信息”，從而對(duì)該儲(chǔ)備點(diǎn)的信息進(jìn)行編輯。

（3）最短路徑模塊

“最短路徑”可以在下拉列表中選擇對(duì)應(yīng)的起點(diǎn)儲(chǔ)備庫和終點(diǎn)儲(chǔ)備庫，點(diǎn)擊確認(rèn)后，后臺(tái)系統(tǒng)通過Dijkstra算法計(jì)算最短路徑，將結(jié)果返回到前臺(tái)，并通過調(diào)用百度地圖 APIs, 將該生成的最短路徑繪制在地圖界面上，同時(shí)將該路徑的距離和途經(jīng)節(jié)點(diǎn)信息顯示在左下角的頁面中。

（4）用戶登錄子系統(tǒng)

用于本系統(tǒng)的注冊(cè)管理、用戶管理、系統(tǒng)管理等功能模塊。

（5）路由信息子系統(tǒng)

在災(zāi)害應(yīng)急響應(yīng)網(wǎng)絡(luò)中，每一個(gè)紅色的矢量圖形均代表一個(gè)儲(chǔ)備點(diǎn)，點(diǎn)擊系統(tǒng)導(dǎo)航欄處的“路由信息”后，即可瀏覽災(zāi)害應(yīng)急響應(yīng)網(wǎng)絡(luò)。在該頁面中展示的是所有的儲(chǔ)備點(diǎn)和發(fā)放點(diǎn)之間的路由網(wǎng)絡(luò)，從而可以為決策者的下一步處理提供依據(jù)。

（6）應(yīng)急調(diào)度子系統(tǒng)

在救災(zāi)物資應(yīng)急調(diào)度子系統(tǒng)中，我們將基于啟發(fā)式和貪心的快速混合算法嵌入到這個(gè)功能中。選擇一個(gè)發(fā)放點(diǎn)，在左側(cè)的列表中輸入救災(zāi)物資需求，確認(rèn)后，系統(tǒng)會(huì)自動(dòng)調(diào)用集成優(yōu)化算法去搜索一個(gè)最優(yōu)分配和調(diào)度方案，并在應(yīng)急網(wǎng)絡(luò)上標(biāo)出。

（7）接口管理子系統(tǒng)

通過信息通報(bào)和報(bào)警模塊，可以輔助職能部門做好平時(shí)的應(yīng)急演練和戰(zhàn)時(shí)的指揮調(diào)度，并且系統(tǒng)預(yù)留與異構(gòu)信息系統(tǒng)之間的API接口。

2.核心算法描述

（1）算法建模

通過算法建模的方式，把應(yīng)急救災(zāi)物資調(diào)度問題抽象成如下多目標(biāo)優(yōu)化模型：

第一，重大自然災(zāi)害發(fā)生后，同時(shí)存在多個(gè)需要響應(yīng)的救災(zāi)物資發(fā)放點(diǎn)；

第二，應(yīng)急專家根據(jù)受災(zāi)情況可以粗略估算出各發(fā)放點(diǎn)所需要的救災(zāi)物資種類和數(shù)量，并以整數(shù)計(jì)數(shù)，即救災(zāi)物資需求量是一個(gè)定量值；

第三，存在多個(gè)分布于不同地域的救災(zāi)物資儲(chǔ)備點(diǎn)，且每個(gè)儲(chǔ)備點(diǎn)擁有有限的救災(zāi)物資種類和數(shù)量(定量)，并以整數(shù)計(jì)數(shù)；

第四，同一種類的救災(zāi)物資由于地域等差異，從各儲(chǔ)備點(diǎn)運(yùn)輸?shù)礁靼l(fā)放點(diǎn)分別有不同的運(yùn)輸成本（因?yàn)檩斔吐窂讲煌?，并以整?shù)計(jì)數(shù)；

第五，依據(jù)各儲(chǔ)備點(diǎn)到各發(fā)放點(diǎn)的廣義時(shí)間距離（比如行程時(shí)間，以整數(shù)計(jì)數(shù)）來設(shè)定應(yīng)急響應(yīng)時(shí)間。

（2）基于啟發(fā)式和貪心的快速混合求解算法

圖3 流程圖

為解決上述應(yīng)急救災(zāi)物資調(diào)度問題，在算法建模的基礎(chǔ)上，我們?cè)O(shè)計(jì)了基于啟發(fā)式和貪心的快速混合求解算法。首先建立輔助網(wǎng)絡(luò)來減小問題的復(fù)雜度，然后從輔助網(wǎng)絡(luò)中提取啟發(fā)式信息，并提出一種基于貪心策略的搜索方法來快速尋找最優(yōu)解。所提出的啟發(fā)式快速求解算法流程圖如圖3所示。

調(diào)度系統(tǒng)運(yùn)行驗(yàn)證

1.測(cè)試用例生成

將安徽某地區(qū)地圖映射到應(yīng)急調(diào)度系統(tǒng)中，每條路段上的數(shù)字為旅行時(shí)間（單位：小時(shí)），可根據(jù)百度地圖的歷史行程時(shí)間函數(shù)得到。儲(chǔ)備點(diǎn)和發(fā)放點(diǎn)的位置由隨機(jī)實(shí)例生成器隨機(jī)定位到應(yīng)急調(diào)度系統(tǒng)中。

實(shí)例生成器基于三種實(shí)驗(yàn)環(huán)境：分別生成3個(gè)隨機(jī)實(shí)例，每個(gè)實(shí)例分別具有不同數(shù)量的儲(chǔ)備點(diǎn)、發(fā)放點(diǎn)和救災(zāi)物資種類。此外，每個(gè)儲(chǔ)備點(diǎn)擁有的救災(zāi)物資量，每個(gè)發(fā)放點(diǎn)的物資需求量，以及每種物資的單位時(shí)間單位運(yùn)輸成本均是隨機(jī)生成的，而根據(jù)應(yīng)急經(jīng)驗(yàn)，每個(gè)發(fā)放點(diǎn)的最大應(yīng)急響應(yīng)時(shí)間設(shè)為12小時(shí)，救災(zāi)物資可以是食物、飲用水、帳篷、被子和其他日常必需品，還可是救援設(shè)備、工具和醫(yī)療器械等。

2.測(cè)試結(jié)果驗(yàn)證

將上述測(cè)試用例樣本輸入系統(tǒng)，點(diǎn)擊“應(yīng)急調(diào)度”即可進(jìn)入救災(zāi)物資分配和調(diào)度模塊，選擇一個(gè)發(fā)放點(diǎn)，在列表中輸入救災(zāi)物資需求，點(diǎn)擊確認(rèn)后，系統(tǒng)會(huì)自動(dòng)調(diào)用集成優(yōu)化算法去搜索一個(gè)最優(yōu)分配和調(diào)度方案在應(yīng)急網(wǎng)絡(luò)上標(biāo)出?？梢钥闯鱿到y(tǒng)從眾多的儲(chǔ)備點(diǎn)中，根據(jù)我們?cè)O(shè)計(jì)的啟發(fā)式和貪心的快速混合算法，自動(dòng)計(jì)算出最優(yōu)的三個(gè)儲(chǔ)備點(diǎn)向發(fā)放點(diǎn)進(jìn)行應(yīng)急救災(zāi)物資分配和調(diào)度。

總結(jié)

本文基于地方電子政務(wù)外網(wǎng)，以救災(zāi)物資分配和調(diào)度集成優(yōu)化算法為核心技術(shù)，研發(fā)了救災(zāi)物資分配和調(diào)度系統(tǒng)，并在電子政務(wù)外網(wǎng)上實(shí)際部署運(yùn)行，實(shí)現(xiàn)了對(duì)各項(xiàng)技術(shù)的統(tǒng)一性和可行性的有效驗(yàn)證，并為政府高效、有序的應(yīng)對(duì)重大自然災(zāi)害提供了示范性解決方案。

下一步的工作重點(diǎn)是對(duì)接相關(guān)政務(wù)部門的信息系統(tǒng)，使得業(yè)務(wù)數(shù)據(jù)能夠?qū)崟r(shí)共享。