張亞楠 王浩鑫

摘要：武警部隊(duì)肩負(fù)著維護(hù)國家安全、保障人民安居樂業(yè)等神圣使命。本文主要研究突發(fā)自然災(zāi)害時(shí)，救援物資的運(yùn)送問題。

針對(duì)問題一，分別計(jì)算兩個(gè)駐扎點(diǎn)途經(jīng)補(bǔ)給站到兩個(gè)受災(zāi)區(qū)的最短時(shí)間，再分配救援對(duì)象。計(jì)算最短時(shí)間時(shí)，采用0、1分配，以最短時(shí)間為目標(biāo)函數(shù)，一個(gè)車隊(duì)只救援一個(gè)受災(zāi)區(qū)為約束函數(shù)，建立優(yōu)化模型，求解救援方案，最優(yōu)救援路徑見表3。

針對(duì)問題二，分別計(jì)算兩個(gè)駐扎點(diǎn)途經(jīng)補(bǔ)給站到10個(gè)受災(zāi)區(qū)的最短時(shí)間，再采用0、1分配，以最短時(shí)間為目標(biāo)函數(shù)，一個(gè)車隊(duì)只救援一個(gè)受災(zāi)區(qū)為約束函數(shù)，建立優(yōu)化模型，得到最優(yōu)救援路徑見表6。

關(guān)鍵詞：救援方案 0、1分配 優(yōu)化模型

一、問題重述

某地區(qū)發(fā)生地震災(zāi)害，需要武警部隊(duì)裝載救援物資、迅速完成救援搶險(xiǎn)任務(wù)，受災(zāi)地區(qū)的道路圖如附件1，其中，紅線是主干道路，為雙車道，行駛速度為70公里/小時(shí);藍(lán)線為單車道，速度為45公里/小時(shí)，且機(jī)動(dòng)車只能在道路節(jié)點(diǎn)會(huì)車。D1、D2兩區(qū)域分別駐扎兩個(gè)中隊(duì)，Z01-Z02為6個(gè)物資補(bǔ)給區(qū)域，F(xiàn)01-F60為60個(gè)村莊。各物資補(bǔ)給區(qū)域每次只能容納1個(gè)機(jī)動(dòng)中隊(duì)，每個(gè)中隊(duì)物資裝卸需要10分鐘。

解決以下問題：

（1）若F02、F55為地震重災(zāi)區(qū)，設(shè)計(jì)從D1、D2出發(fā)到F02、F55的最優(yōu)路徑以順利完成任務(wù)。

（2）若F02、F58、F14、F16、F41、F46、F49、F55、F57、F60為地震重災(zāi)區(qū)，從D1、D2向受災(zāi)區(qū)輸送救援物資，D1、D2兩區(qū)域的中隊(duì)分別統(tǒng)一行動(dòng)，然后返回駐扎點(diǎn)繼續(xù)下一個(gè)輸送任務(wù)。設(shè)計(jì)救援路徑，使用時(shí)最少。

二、問題分析

針對(duì)問題一

我們假設(shè)車隊(duì)出發(fā)時(shí)未裝載物資，則需要先去物資補(bǔ)給區(qū)域進(jìn)行補(bǔ)給，然后再去受災(zāi)區(qū)。由于不確定哪個(gè)中隊(duì)救援哪個(gè)受災(zāi)區(qū)，所以我們先分別求出D1、D2經(jīng)過6個(gè)補(bǔ)給站到F02、F55的最短時(shí)間，再進(jìn)行比較得出救援組合方式。

求時(shí)間時(shí)，采用0、1分配，以最短時(shí)間為目標(biāo)函數(shù)，一個(gè)車隊(duì)只救援一個(gè)受災(zāi)區(qū)為約束函數(shù)，建立優(yōu)化模型，求解救援方案，從而得出最短救援時(shí)間。

針對(duì)問題二

同樣假設(shè)車隊(duì)出發(fā)時(shí)未裝載物資，則需要先去物資補(bǔ)給區(qū)域進(jìn)行補(bǔ)給，然后再去受災(zāi)區(qū)，返回駐扎點(diǎn)再繼續(xù)下一個(gè)救援任務(wù)。時(shí)間為車隊(duì)往返駐扎地的時(shí)間，以時(shí)間最短為目標(biāo)函數(shù)，一個(gè)車隊(duì)只救援一個(gè)受災(zāi)區(qū)為約束函數(shù)，建立優(yōu)化模型。

三、模型假設(shè)

1.假設(shè)車隊(duì)在道路上行駛時(shí)沒有其他時(shí)間損耗;

2.假設(shè)問題一、二車隊(duì)出發(fā)時(shí)未裝載物資。

四、符號(hào)說明

五、模型建立和求解

5.1問題一模型建立和求解

5.1.1數(shù)據(jù)處理

為了方便編寫MATLAB程序，將附件中的要素編號(hào)按順序重新編號(hào)為1，2，3……130，并且將題中所給圖形中相連的線段的起點(diǎn)和終點(diǎn)依次找出，保存在附件2。結(jié)合每個(gè)節(jié)點(diǎn)的坐標(biāo)，利用MATLAB里的graphshortestpath算法[1]，編寫程序（見附錄）將每條道路的路程求解出來，進(jìn)而得到經(jīng)過每條道路所花費(fèi)的時(shí)間。

5.1.2模型建立

采用0、1分配，設(shè)第i個(gè)重災(zāi)區(qū)由j個(gè)駐扎地救援為1，否則為0則有：

設(shè)第一個(gè)重災(zāi)區(qū)是F16，第二個(gè)重災(zāi)區(qū)是F55，第一個(gè)駐扎地是D1，第二個(gè)駐扎地是D2。要求武警部隊(duì)一個(gè)駐扎地出發(fā)后，先經(jīng)過補(bǔ)給點(diǎn)補(bǔ)給物資，再運(yùn)往重災(zāi)區(qū)，且一個(gè)駐扎地只救援一個(gè)重災(zāi)區(qū)，一個(gè)重災(zāi)區(qū)只被一個(gè)駐扎地救援，得到約束條件，。兩個(gè)駐扎地的武警部隊(duì)是同時(shí)行動(dòng)，要求花費(fèi)時(shí)間長(zhǎng)的路線所用時(shí)間盡可能的少，則有，綜上得到優(yōu)化模型：

5.1.3模型求解

將計(jì)算得到的每條道路的時(shí)間矩陣，進(jìn)行對(duì)角化和稀疏化處理，然后調(diào)用MATLAB圖論工具箱中的graphshortestpath函數(shù)[1]，任意給定起點(diǎn)和終點(diǎn)，就可以得到兩點(diǎn)所花費(fèi)的時(shí)間和經(jīng)過的節(jié)點(diǎn)。計(jì)算駐扎地到重災(zāi)區(qū)的時(shí)間時(shí)，中間可以經(jīng)過的物資補(bǔ)給點(diǎn)一共有6個(gè)，依次計(jì)算經(jīng)過每個(gè)補(bǔ)給點(diǎn)的總時(shí)間，保留時(shí)間最小的那一條路徑，記錄補(bǔ)給點(diǎn)的序號(hào)，編寫MATLAB程序見附錄程序一，得到時(shí)間表見表1，補(bǔ)給站經(jīng)過表見表2：

本題數(shù)據(jù)較少，可以不用LINGO進(jìn)行求解，觀察即可得到D1的救援隊(duì)在Z02進(jìn)行補(bǔ)給之后前往F55，D2的救援隊(duì)在Z06進(jìn)行補(bǔ)給之后前往F16，具體路徑如表3。

5.2問題二模型建立和求解

5.2.1模型建立：

采用0、1分配，設(shè)第i個(gè)重災(zāi)區(qū)由j個(gè)駐扎地救援為1，否則為0則有：

參考文獻(xiàn)

[1].https：//blog.csdn.net/weixin_44228675/article/details/98070194

西安理工大學(xué) 710048