基于最大覆蓋模型的救護(hù)車車輛調(diào)度問(wèn)題研究

黃美林 馮 倩 王 雷 蔣 偉

（重慶交通大學(xué) 經(jīng)濟(jì)與管理學(xué)院，重慶 400074）

1 問(wèn)題描述與模型的建立

時(shí)間是衡量救護(hù)車出車效率的一個(gè)重要指標(biāo)，現(xiàn)伊薩卡市要求將響應(yīng)時(shí)間控制在6分鐘內(nèi)，并計(jì)算出需要的救護(hù)車數(shù)量以實(shí)現(xiàn)此目標(biāo)，除此之外救護(hù)車的位置需明確。若在伊薩卡市難以在6分鐘內(nèi)到達(dá)的地區(qū)，可以增加最壞情況下的響應(yīng)時(shí)間，以提高救護(hù)車的效用。

首先根據(jù)伊薩卡市地圖特點(diǎn)，將地圖建立3×3網(wǎng)格，分塊化處理并為其編號(hào)為N=1…9，將復(fù)雜的城市區(qū)域簡(jiǎn)單化，利用救護(hù)車行駛模型對(duì)伊薩卡市現(xiàn)有的4個(gè)救護(hù)車站點(diǎn)進(jìn)行驗(yàn)證是否滿足6分鐘以內(nèi)到達(dá)指定地區(qū)的限制條件。伊薩卡市已知有4個(gè)救護(hù)車站點(diǎn)，求出各救護(hù)車到呼叫點(diǎn)的行駛距離dij。救護(hù)車到達(dá)呼叫點(diǎn)的時(shí)間t應(yīng)在6分鐘以內(nèi)，將時(shí)間轉(zhuǎn)化為距離s，假設(shè)該救護(hù)車的時(shí)速v為55km/h(0.57miles/min)。每個(gè)呼叫點(diǎn)只需一輛救護(hù)車響應(yīng)。根據(jù)以上約束以及目標(biāo)函數(shù)為最短路建立模型：

2 車輛調(diào)度優(yōu)化模型

首先根據(jù)伊薩卡市的地圖，對(duì)伊薩卡市進(jìn)行模塊化，再根據(jù)救護(hù)車到達(dá)呼叫點(diǎn)的時(shí)間約束，利用最大覆蓋模型，尋找到最有數(shù)量的救護(hù)車站點(diǎn)數(shù)量以及位置。以最少的救護(hù)車站點(diǎn)去滿足所有呼叫需求點(diǎn)，所以目標(biāo)函數(shù)為路徑最短。每個(gè)呼叫需求點(diǎn)i只有一輛救護(hù)車響應(yīng)。每輛救護(hù)車的響應(yīng)時(shí)間必須在6分鐘以內(nèi)，其可轉(zhuǎn)化為行駛距離。

人們?cè)谟龅骄o急情況首先會(huì)想到呼叫救護(hù)車急救，而影響呼叫量有很多因素，我們將老年人的呼叫量、突發(fā)疾病的呼叫量、經(jīng)濟(jì)收入中等偏上人群的呼叫量、意外事故引起的呼叫量及護(hù)理機(jī)構(gòu)引起的呼叫量作為影響因素。通過(guò)相關(guān)性分析，檢驗(yàn)這些影響因素對(duì)呼叫量的相關(guān)程度，并對(duì)相關(guān)程度進(jìn)行重要程度D計(jì)算，從而將影響因素定量化。

其中，D為影響因素的重要程度，dlevel為等級(jí)數(shù)，dtotal為總等級(jí)數(shù)。

將重要程度進(jìn)行歸一化處理。根據(jù)伊薩卡市一年的呼叫數(shù)，計(jì)算平均每天的呼叫數(shù)。根據(jù)歸一化結(jié)果以及平均每天呼叫數(shù)計(jì)算各救護(hù)車站點(diǎn)里的救護(hù)車數(shù)量。由于每個(gè)救護(hù)車站點(diǎn)的救護(hù)車數(shù)量有限，若呼叫需求小于該站點(diǎn)救護(hù)車的數(shù)量，則該站點(diǎn)的車輛滿足調(diào)度。若呼叫需求過(guò)多，該站點(diǎn)的救護(hù)車全部出動(dòng)，此時(shí)滿足不了需求，則需要考慮從其他站點(diǎn)調(diào)配救護(hù)車前往救援，但仍需要滿足在6分鐘內(nèi)到達(dá)需求點(diǎn)?；诰茸o(hù)車行駛距離最短模型求解的站點(diǎn)，仍以救護(hù)車行駛距離最短為目標(biāo)函數(shù)。所有站點(diǎn)的救護(hù)車行駛的距離均要滿足在6分鐘行駛的距離內(nèi)。每個(gè)呼叫點(diǎn)僅有一輛救護(hù)車響應(yīng)。根據(jù)以上約束建立車輛調(diào)度模型：

其中，minZ′=∑x j dij+∑x k dik+∑xl dil為目標(biāo)函數(shù)，其表示救護(hù)車行駛距離最短，x j,x k,xl均為0-1變量；x j?d ij≤s，x k?dik≤s，xl?d il≤s表示所有站點(diǎn)的救護(hù)車行駛的距離均要滿足在6分鐘行駛的距離內(nèi)；表示每個(gè)呼叫點(diǎn)僅有一輛救護(hù)車響應(yīng)。

3 結(jié)果分析

利用MATLAB進(jìn)行求解救護(hù)車行駛距離模型，所有約束滿足。此時(shí)，通過(guò)減少站點(diǎn)數(shù)量來(lái)尋找最優(yōu)站點(diǎn)數(shù)量，減少成本。經(jīng)過(guò)分析可以發(fā)現(xiàn)，一個(gè)站點(diǎn)是不可能在6分鐘以內(nèi)到達(dá)所有可能的呼叫點(diǎn)，所以我們將站點(diǎn)減少至2和3，帶入模型求解。由于對(duì)角線為最長(zhǎng)距離，分別對(duì)兩條對(duì)角線的距離進(jìn)行計(jì)算，得到兩條對(duì)角線的距離為8.17英里和8.21英里，救護(hù)車需要在6分鐘內(nèi)到達(dá)呼叫點(diǎn)，則該最大距離為3.42英里，因此在該城市內(nèi)2個(gè)救護(hù)車急救站點(diǎn)不能滿足需求。當(dāng)建立3各救護(hù)車站點(diǎn)時(shí)，每個(gè)救護(hù)車急救站點(diǎn)相鄰區(qū)域的距離均在3.42英里內(nèi)，因此建設(shè)3個(gè)救護(hù)車急救站點(diǎn)滿足該城市6分鐘內(nèi)響應(yīng)。

運(yùn)用貪婪算法求解最大覆蓋模型，求的結(jié)果為只需要在1、7、10區(qū)域設(shè)置3個(gè)救護(hù)車站點(diǎn)就能夠覆蓋伊薩卡市所有可能的需求呼叫點(diǎn)，根據(jù)影響因素計(jì)算各救護(hù)車站點(diǎn)的救護(hù)車數(shù)量為1區(qū)域5輛，7區(qū)域9輛，10區(qū)域6輛，利用遺傳算法求解車輛調(diào)度模型，根據(jù)計(jì)算結(jié)果可以得到，有一部分區(qū)域只有特定的一個(gè)站點(diǎn)能到達(dá)而另一部分可由兩個(gè)站點(diǎn)到達(dá)。因此，為保證盡可能少的站點(diǎn)和救護(hù)車，站點(diǎn)應(yīng)優(yōu)先滿足第一部分區(qū)域的覆蓋即區(qū)域1區(qū)域-6、區(qū)域10區(qū)域-9、區(qū)域10-區(qū)域11、區(qū)域7-區(qū)域14區(qū)域-4,、區(qū)域7-區(qū)域15區(qū)域-16-區(qū)域5 。在此基礎(chǔ)上，區(qū)域1的站點(diǎn)的4條分別可到達(dá)區(qū)域13、3、14、6的備用路線以及區(qū)域10的站點(diǎn)能分別到達(dá)5條區(qū)域8、12、13、15、16的路線可用作在呼叫量大于救護(hù)車數(shù)量時(shí)臨時(shí)派遣前往。

4 總結(jié)

本文首先根據(jù)已知的救護(hù)車站點(diǎn)位置以及救護(hù)車行駛距離模型檢驗(yàn)是否滿足響應(yīng)時(shí)間在6分鐘以內(nèi)的約束，結(jié)果表明滿足。經(jīng)過(guò)分析可知，當(dāng)救護(hù)站點(diǎn)為1時(shí)是不可能滿足響應(yīng)時(shí)間在6分鐘以內(nèi)，所以分別檢驗(yàn)救護(hù)站點(diǎn)為2和3時(shí)的響應(yīng)情況，當(dāng)救護(hù)站點(diǎn)為3時(shí)滿足救護(hù)車響應(yīng)時(shí)間在6分鐘以內(nèi)。

利用最大覆蓋模型對(duì)伊薩卡市呼叫需求點(diǎn)進(jìn)行更加詳細(xì)的區(qū)域劃分，并根據(jù)影響因素計(jì)算各救護(hù)車站點(diǎn)的救護(hù)車數(shù)輛，建立車輛調(diào)度模型，當(dāng)該區(qū)域救護(hù)車全部出車時(shí)，從其他區(qū)域調(diào)車的情況。