文/周思憶 肖晰 翟宏強(qiáng)

1 問題的重述

1.1 背景知識(shí)

1.1.1 背景介紹

城市生活的大型中心設(shè)施通常管理著多個(gè)移動(dòng)服務(wù)點(diǎn)，當(dāng)城市某地點(diǎn)產(chǎn)生需求的時(shí)候，將從中心設(shè)施派出移動(dòng)服務(wù)點(diǎn)趕往需求地點(diǎn)進(jìn)行服務(wù)。需求是否以最快的速度得到響應(yīng)，與諸多因素有關(guān)。例如，從中心設(shè)施趕往現(xiàn)場(chǎng)所要的時(shí)間、接受服務(wù)的時(shí)間、等待的時(shí)間等。在服務(wù)力量有限情況下，如何根據(jù)以往需求產(chǎn)生的情況、道路狀況，將中心設(shè)施建在合適的位置顯得尤為重要。

1.1.2 提出問題

根據(jù)城市地理簡(jiǎn)圖以及各地區(qū)呼叫救助隊(duì)的時(shí)刻，通過改變緊急醫(yī)療中心設(shè)施位置，降低平均響應(yīng)時(shí)間，求出其最小值，以及此時(shí)中心設(shè)施所處位置。

2 模型的假設(shè)

（1）假設(shè)救助中心到每個(gè)救助區(qū)域的所有路徑道路狀況相同，不能存在堵車。

（2）假設(shè)各救援隊(duì)的行駛速度為1km/min。

3 名詞解釋與符號(hào)說明

3.1 名詞解釋

平均響應(yīng)時(shí)間：從一個(gè)呼叫產(chǎn)生到救助隊(duì)趕到該呼叫地點(diǎn)所用的平均時(shí)長(zhǎng)。

3.2 符號(hào)說明

如表1所示。

表1

圖1：區(qū)域圖網(wǎng)絡(luò)

4 模型的建立與求解

4.1 問題的分析與求解

4.1.1 對(duì)問題的分析

經(jīng)分析，平均響應(yīng)時(shí)間與救助隊(duì)到救助區(qū)域的距離有關(guān)，因?yàn)闉榱四鼙M快到達(dá)救助地，必須求得救助中心到各救助區(qū)域的最短距離。因此首先根據(jù)迪杰斯特拉算法建立最短救助路徑模型，得到救助中心到達(dá)救援區(qū)域的最短距離。再分析，發(fā)現(xiàn)呼叫地點(diǎn)、呼叫時(shí)間間隔不服從常見的均勻分布、正態(tài)分布、泊松分布、指數(shù)分布，故呼叫地點(diǎn)、呼叫時(shí)間間隔為一般分布，故用累積分布列的方式表訴它們的分布規(guī)律；并假設(shè)救援時(shí)間服從均值為15、方差為1的正態(tài)分布。最后在前兩步的基礎(chǔ)上，建立基于計(jì)算機(jī)模擬的平均響應(yīng)時(shí)間模型，求得平均響應(yīng)時(shí)間。

模型Ⅰ——基于計(jì)算機(jī)模擬的平均時(shí)間響應(yīng)模型：

4.1.2 模型的準(zhǔn)備

4.1.2.1 確定救助中心到各區(qū)域距離

（1）分析。緊急醫(yī)療中心派出的車輛到救助地點(diǎn)之間的路徑不是唯一，如果時(shí)間稍微延誤，將造成不可挽回的損失。因此，車輛必然會(huì)選擇到救助地的最短路徑，如何求解從緊急醫(yī)療中心到救助地點(diǎn)的最短路徑成了解決問題一的前提。本文使用迪杰斯特拉(Dijkstra)算法計(jì)算一個(gè)節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短路徑。

（2）分步求解。

步驟一：確定救援位置。

如圖1所示，45個(gè)救助區(qū)域分別占據(jù)的面積是一塊小矩形。矩形邊為公路，每條邊均長(zhǎng)1.5公里。救援時(shí)，無法得知具體救助位置處于小矩形區(qū)域哪一塊。為方便計(jì)算，把45個(gè)區(qū)域的位置看成一個(gè)一個(gè)的節(jié)點(diǎn)，將節(jié)點(diǎn)之間的連接關(guān)系轉(zhuǎn)化為圖論里面的“圖”。故建立“圖”網(wǎng)絡(luò)。

步驟二：建立圖網(wǎng)絡(luò)。

如圖1所示，其中的一個(gè)小圓代表一個(gè)區(qū)域節(jié)點(diǎn)，小圓中的數(shù)字代表區(qū)域號(hào)。節(jié)點(diǎn)與節(jié)點(diǎn)之間的公路用一條線段表示，連接節(jié)點(diǎn)與節(jié)點(diǎn)之間的每條線段均為1.5公里。

步驟三：確定算法思路-迪杰斯特拉算法。

a.指定一個(gè)節(jié)點(diǎn)，計(jì)算該點(diǎn)到其他點(diǎn)的最短路徑。

b.引入兩個(gè)集合（S、U），S集合包含已求出的最短路徑的點(diǎn)（以及相應(yīng)的最短長(zhǎng)度），U集合包含未求出最短路徑的點(diǎn)（以及A到該點(diǎn)的路徑及長(zhǎng)度，若兩點(diǎn)間沒有連通，則距離記為無窮）。

c.初始化兩個(gè)集合，S集合初始時(shí) 只有當(dāng)前的源節(jié)點(diǎn)以及路徑長(zhǎng)度0。

d.從U集合中找出路徑最短的點(diǎn)，加入S集合。

e.若源點(diǎn)到步驟d加入集合S的點(diǎn)的距離加上該點(diǎn)到集合U中某點(diǎn)的距離小于源點(diǎn)到集合U中某點(diǎn)的距離，則更新U集合路徑，更新為前者。

f.循環(huán)進(jìn)行d、e步驟，直至集合U中所有節(jié)點(diǎn)都加入集合S。

步驟四：基于迪杰斯特拉算法建立最短救助路徑模型。

a、創(chuàng)建一個(gè)距離的矩陣W，Wij表示第i個(gè)節(jié)點(diǎn)到第j個(gè)節(jié)點(diǎn)（距離）。

b、本題救助中心在節(jié)點(diǎn)16，故建立第16個(gè)節(jié)點(diǎn)到其他節(jié)點(diǎn)的距離矩陣W，初始化為無窮。

c、錄入節(jié)點(diǎn)之間的距離，如區(qū)域2到區(qū)域3的距離為1.5公里，則W23為1.5。

d、visited用于記錄節(jié)點(diǎn)是否已經(jīng)放入集合S。

e、建立目標(biāo)變量，即最短路徑長(zhǎng)度，用shortPath記錄。

步驟五：最短救助路徑求解

將12個(gè)區(qū)域分別作為救援中心距離其他地區(qū)的分別求解結(jié)果。

步驟六：最短救助路徑結(jié)果分析。

由上述可知，將每個(gè)區(qū)域都看成一個(gè)一個(gè)的節(jié)點(diǎn)，各區(qū)域到其他區(qū)域的最短距離是為了求解本題平均響應(yīng)時(shí)間所做的提前準(zhǔn)備。

4.1.2.2 確定分布

（1）呼叫地點(diǎn)的分布。對(duì)8天的呼叫地點(diǎn)進(jìn)行統(tǒng)計(jì)，用matlab畫出頻數(shù)分布直方圖。得到呼叫地點(diǎn)和均勻分布、正態(tài)分布、指數(shù)分布、泊松分布的符合情況，然后使用spss軟件對(duì)這些數(shù)據(jù)進(jìn)行Kolmogorov-Smirnov檢驗(yàn)。從圖中找出數(shù)據(jù)四種分布的漸進(jìn)顯著性水平，若大于0.05，為對(duì)應(yīng)分布，否則不服從這四種分布，認(rèn)為它服從一般分布。本題四種分布的漸進(jìn)顯著性水平為0，呼地點(diǎn)服從一般分布。

（2）呼叫時(shí)間間隔的分布。將呼叫地點(diǎn)轉(zhuǎn)換成的頻數(shù)分布直方圖，用同樣方法確定呼叫時(shí)間間隔屬于一般分布。

（3）救援時(shí)間的分布。已知一次救援的時(shí)間服從均值為15，方差為1的分布，假設(shè)它服從均值為15，方差為1的正態(tài)分布：

其中μ=15，σ=1。

根據(jù)[0，1]區(qū)間上服從均勻分布的隨機(jī)數(shù)確定隨機(jī)變量的值：

如每次呼叫時(shí)間間隔、呼叫地點(diǎn)、每次的救援時(shí)這些隨機(jī)變量的分布為：

P{X=xi}=pi,i=0,1… 其中0

將概率分布轉(zhuǎn)化為累計(jì)分布，令：

對(duì)于[0，1]區(qū)間上服從均勻分布的隨機(jī)數(shù)ζ，取滿足

式子的xi為本次隨機(jī)變量的值。

4.2 模型的建立

4.2.1 模型說明

圖2：計(jì)算機(jī)模擬流程圖

通過計(jì)算機(jī)模擬程序，生成每次呼叫時(shí)間間隔以及地點(diǎn)的分布規(guī)律，生成每次呼叫產(chǎn)生的時(shí)間間隔和相應(yīng)的地點(diǎn)，按照某種確定的派出救援隊(duì)的算法對(duì)一天或若干天救助隊(duì)的救助情況進(jìn)行模擬，最后通過模擬，可以算出救助中心在不同地點(diǎn)的時(shí)候所對(duì)應(yīng)的平均響應(yīng)時(shí)間。t為當(dāng)前時(shí)刻，tl1為第一個(gè)救援隊(duì)返回的時(shí)刻，tl2為第二個(gè)救援隊(duì)返回的時(shí)刻，tl3為第三個(gè)救援隊(duì)返回的時(shí)刻，interval為下次呼叫的間隔時(shí)間，tr為總的響應(yīng)時(shí)間、t_road為救援中心到救助點(diǎn)單程時(shí)間、t_rescue為本次救援所用時(shí)間。

具體模擬過程如圖2所示。

模型——基于計(jì)算機(jī)模擬的最優(yōu)救助中心選擇模型：

4.2.2 模型的建立

（1）模型說明。

先求出各區(qū)域的平均響應(yīng)時(shí)間，找出使平均響應(yīng)時(shí)間最短的區(qū)域即要選擇的救助中心。將第n次模擬的總平均響應(yīng)時(shí)間控制到最小，作為約束條件，加上min trn。在此條件下求得目標(biāo)變量，則中心區(qū)域?yàn)榈趈個(gè)區(qū)域pj。

（2）建立模型。

4.2.3 模型的求解

求解結(jié)果：

問題求解結(jié)果為：將救助中心設(shè)置在區(qū)域36，此時(shí)最短平均響應(yīng)時(shí)間為18.6238分鐘。