交巡警服務(wù)平臺(tái)設(shè)置與調(diào)度的數(shù)學(xué)模型

徐 標(biāo)，陳 昊，楊文芳，魯 群，張 碩

(淮北師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，安徽 淮北 235000)

此問題為2011年全國大學(xué)生建模競賽的B題第一部分，問題的背景見文[1]，主要是結(jié)合重慶市交巡警服務(wù)平臺(tái)設(shè)置的相關(guān)情況，建立數(shù)學(xué)模型分析研究下面的問題:

圖1給出該市中心城區(qū)A的交通網(wǎng)絡(luò)和現(xiàn)有的20個(gè)交巡警服務(wù)平臺(tái)的設(shè)置情況示意圖，相關(guān)的數(shù)據(jù)信息見文獻(xiàn)[2].請(qǐng)為各交巡警服務(wù)平臺(tái)分配管轄范圍，使其在所管轄的范圍內(nèi)出現(xiàn)突發(fā)事件時(shí)，盡量能在3 min內(nèi)有交巡警(警車的時(shí)速為60 km/h)到達(dá)事發(fā)地.

對(duì)于重大突發(fā)事件，需要調(diào)度全區(qū)20個(gè)交巡警服務(wù)平臺(tái)的警力資源，對(duì)進(jìn)出該區(qū)的13條交通要道實(shí)現(xiàn)快速全封鎖.實(shí)際中一個(gè)平臺(tái)的警力最多封鎖一個(gè)路口，請(qǐng)給出該區(qū)交巡警服務(wù)平臺(tái)警力合理的調(diào)度方案.

根據(jù)現(xiàn)有交巡警服務(wù)平臺(tái)的工作量不均衡和有些地方出警時(shí)間過長的實(shí)際情況，擬在該區(qū)內(nèi)再增加2－5個(gè)平臺(tái)，請(qǐng)確定需要增加平臺(tái)的具體個(gè)數(shù)和位置.

1 問題分析

首先利用Floyd[3]算法分別求出每個(gè)坐標(biāo)節(jié)點(diǎn)到各平臺(tái) i(i=1，2，…，20)的最短距離，對(duì)各節(jié)點(diǎn) j，選擇使得距離 dij最小的路線.對(duì)于每個(gè)節(jié)點(diǎn) j，將其劃分到離它最近的平臺(tái)管轄的區(qū)域，則得到一個(gè)初步的管轄范圍，再對(duì)結(jié)果進(jìn)行優(yōu)化.

對(duì)于調(diào)度方案，本文采用最大時(shí)間最小化的方法[4－5]，即選取到達(dá)每一個(gè)交通要道的時(shí)間最短的路線，而封鎖的時(shí)間為選取的時(shí)間中最大的時(shí)間，再爭取該最大時(shí)間最小，表示為max mindij，同時(shí)盡可能保證總時(shí)間最小.

對(duì)現(xiàn)有方案進(jìn)行研究時(shí)，首先從設(shè)立平臺(tái)的原則考慮，將每個(gè)區(qū)域視為一個(gè)整體，將區(qū)域分為交通要道、重要部位兩個(gè)部分，以重要部位的平均工作量代替區(qū)域的平均工作量，對(duì)交通要道、重要部位上的方案分別進(jìn)行調(diào)整.其次從設(shè)立平臺(tái)的任務(wù)來考慮，按層次分析法進(jìn)行定性定量分析.綜合分析結(jié)果，判斷是否合理.

對(duì)于最佳圍堵方案，為簡化計(jì)算，假設(shè)嫌疑人逃跑后便設(shè)法在最短時(shí)間到達(dá)該市出口，則對(duì)于該市的13個(gè)出口存在13條最短路線.從而在全市內(nèi)的圍堵方案簡化為對(duì)13條最短路線的圍堵方案.

2 模型假設(shè)

假設(shè)1:警車在行駛過程中速度保持平穩(wěn);

假設(shè)2:每一個(gè)交巡警服務(wù)平臺(tái)的警力資源足夠應(yīng)付其管轄區(qū)域的突發(fā)事件;

假設(shè)3:新增交巡警服務(wù)平臺(tái)的財(cái)力資源足夠;

假設(shè)4:由于嫌疑犯是駕車逃跑，所以假設(shè)嫌疑犯的逃跑速度與交巡警相同;

假設(shè)5:假設(shè)每個(gè)平臺(tái)接到任務(wù)后馬上出發(fā)，不考慮準(zhǔn)備的時(shí)間.

3 模型的符號(hào)說明

X:路口節(jié)點(diǎn)的橫坐標(biāo);Y:路口節(jié)點(diǎn)的縱坐標(biāo);v:警車行駛過程中的速度;tij:警車從服務(wù)平臺(tái) i到路口節(jié)點(diǎn) j的時(shí)間;dij:警車從服務(wù)平臺(tái) i到路口節(jié)點(diǎn) j的距離;sij:服務(wù)平臺(tái) i到達(dá)路口節(jié)點(diǎn) j的路程;tmax:最大封鎖時(shí)間;S:每個(gè)服務(wù)平臺(tái)案發(fā)率的方差;X:每個(gè)服務(wù)臺(tái)案發(fā)率的均值;t:增加平臺(tái)以后的平均出警時(shí)間.

4 模型的建立與求解

4.1 A區(qū)交巡警服務(wù)平臺(tái)的設(shè)置與調(diào)度

根據(jù)文獻(xiàn)[2]給出的該市市中心城區(qū)A的交通網(wǎng)絡(luò)和現(xiàn)有的20個(gè)交巡警服務(wù)平臺(tái)的設(shè)置情況示意圖，可以清楚地從圖中了解各個(gè)服務(wù)平臺(tái)的地理位置以及各個(gè)路口與服務(wù)平臺(tái)的距離遠(yuǎn)近.要想設(shè)置服務(wù)平臺(tái)或者要調(diào)度服務(wù)平臺(tái)需先計(jì)算出每兩個(gè)路口節(jié)點(diǎn)之間的距離，附件2[2]提供了每兩個(gè)路口節(jié)點(diǎn)在圖上的坐標(biāo)值(X，Y)，其中 X表示路口節(jié)點(diǎn)的橫坐標(biāo)，Y表示路口節(jié)點(diǎn)的縱坐標(biāo)，再根據(jù)Floyd算法程序計(jì)算出A區(qū)內(nèi)每兩點(diǎn)之間的距離長度.由于地圖的距離與實(shí)際的距離比是1:100 000，再將所算出的距離數(shù)值換算成實(shí)際的距離，從中挑選出符合題目要求的數(shù)據(jù).

4.1.1 交巡警服務(wù)平臺(tái)管轄范圍的設(shè)置

4.1.1.1 模型的建立

將時(shí)間單位進(jìn)行一致化處理，警車的速度為 v=60 km/h，即 v=103m/min，對(duì)于交巡警服務(wù)平臺(tái)所管轄的范圍內(nèi)發(fā)生重大突發(fā)事件時(shí)，要在3 min內(nèi)盡可能到達(dá)事發(fā)地點(diǎn)，就是要求服務(wù)平臺(tái)與路口節(jié)點(diǎn)的實(shí)際距離不能超過3 000 m.

以時(shí)間 tij表示路口節(jié)點(diǎn) i到服務(wù)平臺(tái) j的時(shí)間，根據(jù)附表中給出的各節(jié)點(diǎn)的坐標(biāo)編寫Floyd算法程序求出各節(jié)點(diǎn)之間的最小距離 dij(i=1，2，…，20;j=1，2，…，92)，求得對(duì)應(yīng)的時(shí)間 tij(i=1，2，…，20;j=1，2，…，92)，表示為:

對(duì)于所寫的程序，首先根據(jù)盡量小于3 min的原則對(duì)各節(jié)點(diǎn)間的時(shí)間矩陣進(jìn)行篩選，將 tij大于3 min對(duì)應(yīng)的路線剔除掉，對(duì)各節(jié)點(diǎn) i，選擇 tij最小的路線，其中 j為管轄節(jié)點(diǎn)的服務(wù)平臺(tái).

4.1.1.2 模型的求解

將上述模型中程序的運(yùn)行結(jié)果進(jìn)行優(yōu)化.

存在的問題:第一，存在節(jié)點(diǎn)到各服務(wù)平臺(tái)的最短行走時(shí)間均大于3 min，因此沒有分配給任何服務(wù)平臺(tái)管轄，如節(jié)點(diǎn)28，29，38，39，61，92.第二，由于平臺(tái)周圍節(jié)點(diǎn)的密集程度大不相同，所以存在管轄范圍分配不均勻的情況，如節(jié)點(diǎn)1，20與節(jié)點(diǎn)10，14.

解決方案[6]:1)對(duì)于到每個(gè)平臺(tái)的時(shí)間都超過3 min的節(jié)點(diǎn)，安排給離它最近的服務(wù)平臺(tái)進(jìn)行管轄.2)對(duì)于管轄范圍嚴(yán)重不均衡的點(diǎn)，由于希望各平臺(tái)總以最短時(shí)間到達(dá)事故現(xiàn)場，在允許行走時(shí)間最多增加10 s的前提下細(xì)微地做出一些調(diào)整.最終結(jié)果如表1和圖2所示:

表1 各交巡警服務(wù)平臺(tái)管轄范圍

4.1.1.3 結(jié)果分析

上述結(jié)果表明，若發(fā)生緊急情況，可以保證有93.5%的節(jié)點(diǎn)能在3 min以內(nèi)達(dá)到案發(fā)地點(diǎn)，因此該模型具有較高的可操作性.

但是平臺(tái)的管轄區(qū)域并不均衡，這是因?yàn)楦鞴?jié)點(diǎn)分布其本身已經(jīng)存在著不均衡的情況，有些平臺(tái)的設(shè)立除了自身區(qū)域外沒有其他的管轄區(qū)域，則從節(jié)約資源的角度來看，可以將這些平臺(tái)除去或者轉(zhuǎn)移，結(jié)果會(huì)更優(yōu).

4.1.2 巡警服務(wù)平臺(tái)警力合理的調(diào)度方案

4.1.2.1 模型的建立

由圖1可以得知，A區(qū)有13條交通要道，對(duì)于產(chǎn)生的突發(fā)事件必須要在第一時(shí)間封鎖交通要道，以盡快解決問題.A區(qū)總共有20個(gè)交巡警服務(wù)平臺(tái)，且一個(gè)平臺(tái)的警力最多封鎖一個(gè)路口，合理安排這20個(gè)服務(wù)平臺(tái)是必須的，每一個(gè)服務(wù)平臺(tái)到交通要道的距離是不均衡的.封鎖整個(gè)A區(qū)的時(shí)間是受最長時(shí)間制約，所以應(yīng)當(dāng)使最長時(shí)間最短，同時(shí)使總時(shí)間盡可能小.

4.1.2.2 模型的求解[7]

首先通過程序求出各平臺(tái)到交通要道的最小時(shí)間，然后使用迭代的思想對(duì)結(jié)果進(jìn)行優(yōu)化，直至達(dá)到最優(yōu)結(jié)果.具體求解過程如下:

(1)求出一組總時(shí)間最小的解.

(2)從這組解中取出時(shí)間最長的一個(gè)數(shù)據(jù)，對(duì)其進(jìn)行優(yōu)化，如果發(fā)生沖突就在一個(gè)數(shù)據(jù)確定的基礎(chǔ)上求出一組新的解，如果沒有沖突則繼續(xù)進(jìn)行第二步.

(3)直到對(duì)時(shí)間最長的數(shù)據(jù)進(jìn)行優(yōu)化時(shí)使總時(shí)間發(fā)生很大的增加，則停止優(yōu)化，取當(dāng)前解為最優(yōu)解.

根據(jù)上文敘述的方法，通過計(jì)算.求出如下結(jié)果.

表2 各交通要道分管交巡警服務(wù)平臺(tái)

通過線性規(guī)劃:

求出一組更加優(yōu)化的結(jié)果:

表3 各交通要道分管交巡警服務(wù)平臺(tái)(優(yōu)化)

4.1.2.3 結(jié)果分析

由求得結(jié)果的數(shù)據(jù)可以清楚地知道，每一個(gè)交巡警服務(wù)平臺(tái)到達(dá)這13個(gè)交通要道的時(shí)間是不等的，有的甚至相差特別大，根據(jù)表3給出的數(shù)據(jù)可以分別找出到達(dá)13個(gè)交通要道的最短時(shí)間(不包括本身是要道的情況).

表4 平臺(tái)到各要道的最小時(shí)間

由于要考慮這13個(gè)交通要道中的每一個(gè)要道都要被封鎖，而且一個(gè)平臺(tái)的警力最多封鎖一個(gè)道路，因此不存在一個(gè)服務(wù)平臺(tái)負(fù)責(zé)封鎖兩個(gè)交通要道的情況，則選取時(shí)間短的那條路線為準(zhǔn)則，同時(shí)也要考慮這20個(gè)服務(wù)平臺(tái)分別到達(dá)13個(gè)交通要道的最短時(shí)間，對(duì)比選取最優(yōu)時(shí)間.根據(jù)這些條件的限制得出需要的交巡警服務(wù)平臺(tái)的標(biāo)號(hào)以及對(duì)應(yīng)負(fù)責(zé)的交通要道標(biāo)號(hào)及其需要的時(shí)間.

表5 最優(yōu)方案

相比而言，最大封鎖時(shí)間為:tmax=480.93 s=8.015 min.因此在8.015 min可以實(shí)現(xiàn)全封鎖的目標(biāo).

4.1.3 服務(wù)平臺(tái)的設(shè)置

4.1.3.1 模型的建立與求解

由上面所得出的結(jié)果以及原始數(shù)據(jù)可知，一些密集的地區(qū)處交巡警的工作量相對(duì)于其他地區(qū)交巡警的工作量大，也有一些地區(qū)的出警時(shí)間相對(duì)于其他服務(wù)平臺(tái)的時(shí)間來得更長一些，因此需要增加一些服務(wù)平臺(tái)來均衡工作量和優(yōu)化出警時(shí)間.

在這里，由于要添加的服務(wù)平臺(tái)數(shù)是未知的，但要滿足如下條件:

其中X為案發(fā)率的均值，Xi為每個(gè)服務(wù)平臺(tái)的案發(fā)率，t為加 a個(gè)平臺(tái)后的平均出警時(shí)間.

因?yàn)樘砑拥姆?wù)平臺(tái)的位置具有不確定性[8]，將導(dǎo)致計(jì)算量很大.本文將采用枚舉法的算法將交巡警服務(wù)平臺(tái)需要的個(gè)數(shù)以及具體位置算出來，算法如下.

(1)在A區(qū)內(nèi)，依次從2到5增加服務(wù)平臺(tái)數(shù) x.

(2)假設(shè)增加2個(gè)服務(wù)平臺(tái)數(shù)，則依次編程求出每個(gè)服務(wù)平臺(tái)案發(fā)率的方差及出警時(shí)間的長度.

(3)按照(2)式給定的方法分別對(duì)增加3個(gè)、4個(gè)、5個(gè)服務(wù)平臺(tái)進(jìn)行分析研究，從而得出最優(yōu)的平臺(tái)數(shù)和合理的安放位置，增加新的服務(wù)平臺(tái)標(biāo)號(hào)是:

其方差為S=6.051 510;t=79.455 500 s.

4.1.3.2 結(jié)果的推廣

如果該題不考慮設(shè)置服務(wù)平臺(tái)數(shù)花費(fèi)時(shí)間的話，也可以設(shè)置5個(gè)服務(wù)平臺(tái)，相對(duì)于設(shè)置2個(gè)、3個(gè)、4個(gè)服務(wù)平臺(tái)數(shù)要均衡些，設(shè)置的路口節(jié)點(diǎn)數(shù)以及對(duì)應(yīng)的方差、出警時(shí)間如表6所示.

表6 增加5個(gè)服務(wù)平臺(tái)的最優(yōu)結(jié)果

表6中所顯示的數(shù)據(jù)就是在一定的條件下，比如警力資源足夠多，在允許建立足夠多的服務(wù)平臺(tái)數(shù)的情況下設(shè)置的優(yōu)化方案.

[1]韓中庚，但琦.交巡警服務(wù)平臺(tái)的設(shè)置與調(diào)度問題解析[J].數(shù)學(xué)建模及其應(yīng)用，2012，1(1):67－72.

[2]全國大學(xué)生數(shù)學(xué)建模競賽組委會(huì) .2011 年競賽 [EB/OL].[2011－09－10].http:∥www.mcm.edu.cn/html_cn/node/a1ffc4c5587c8a6f96eacefb8dbcc34e.html.

[3]林劉寧.運(yùn)籌學(xué)[M].北京:北京郵電大學(xué)出版社，2003.

[4]孫霞林.用最優(yōu)化選擇原則求最短路徑及長度[J].湖北師范學(xué)院學(xué)報(bào)，2002(2):72－74.

[5]孟凡江，高樹喜，楊新安，等.多路徑分配的車流徑路優(yōu)化模型[J].遼寧工程技術(shù)大學(xué)學(xué)報(bào):自然科學(xué)版，2008，27(z1):93－95.

[6]鄭暢.物流中心選址方法研究[M].武漢:武漢理工大學(xué)，2004.

[7]繆成.突發(fā)公共事件下應(yīng)急物流中的優(yōu)化運(yùn)輸問題的研究[D].上海:同濟(jì)大學(xué)，2007.

[8]范麗芳，江浩斌，陳昆山.模糊層次分析法在配送中心選址中的應(yīng)用[J].鐵道貨運(yùn)，2005(11):20－23.