運籌學在交巡警服務平臺設置和調度中的應用

[摘 要]當前培養應用型人才是高等教育的主要目標，所以學生在學習和掌握基本知識的同時更重要的是運用運籌學的方法借助軟件解決實際問題，這也是我們運籌學教學改革的主要目標。在運籌學的實際教學工作中，我們以2011年高教社杯全國大學生數學建模競賽B題中某市交巡警服務平臺的設置和調度為具體實例闡述運籌學在實際生活中的具體應用，運用0-1規劃、目標規劃、最短路等運籌學相關知識對交巡警服務平臺的設置和調度建立模型，借助matlab和lingo軟件給出了警力資源的合理分配方案和快速封鎖方案。

[關鍵詞]運籌學 floyd算法 0-1規劃模型 MATLAB LINGO

[中圖分類號] G642 [文獻標識碼] A [文章編號] 2095-3437（2014）17-0168-02

一、案例分析

我們以2011年高教社杯全國大學生數學建模競賽B題—交警服務平臺的設置與調度為具體事例，用運籌學的方法加以分析，建立模型并借助軟件給出可行方案。

（一）問題的提出

警察肩負著刑事執法、治安管理、交通管理、服務群眾四大職能。為了更有效地貫徹實施這些職能，需要在市區的一些交通要道和重要部位設置交巡警服務平臺。由于警務資源是有限的，如何根據城市的實際情況與需求合理地設置交巡警服務平臺、分配各平臺的管轄范圍、調度警務資源是警務部門面臨的一個實際課題。為此需要解決如下兩個具體問題：

問題一：根據某市中心城區A的交通網絡和現有的20個交巡警服務平臺的設置情況，為該市各交巡警服務平臺分配管轄范圍，使其在所管轄的范圍內出現突發事件時，盡量能在3分鐘內有交巡警（警車的時速為60km / h）到達事發地。

問題二：對于重大突發事件，需要調度全區20個交巡警服務平臺的警力資源，對進出該區的13條交通要道實現快速全封鎖。實際中一個平臺的警力最多封鎖一個路口，請給出該區交巡警服務平臺警力合理的調度方案。

（二）模型的建立

1.基本假設

（1）交巡警服務臺在出警時警車的速度保持在60公里 / 小時不變；

（2）A區的道路沒有單行道而且都是通暢的；

（3）不考慮各服務臺工作量之間的差別（簡化模型）；

（4）A區不同地點的人口密度相差不大。

2.符號說明

I={1，2……，92}：路口節點編號

J={1，2……，20}：交巡警服務平臺的編號

aij=1，頂點vi與vj相鄰0，頂點vi與vj不相鄰

（xi，yj）：頂點vi的坐標

dij：相鄰頂點vi與vj之間的距離

fij=1，服務平臺j向節點i提供服務0， other

dij：頂點vi到頂點vj的最短距離

sij=1，第j個服務臺對第i條道路進行封鎖0， other

ωj：第j個服務臺管轄的節點數量

3.問題一數學模型的建立

根據要求將20個已知具體位置的交巡警服務平臺的管轄范圍進行分配，在保證其在3min內到達各自管轄區域的前期下，盡可能讓交巡警出警時的行駛路徑和最小，為此我們利用已知條件建立了鄰接矩陣和邊權矩陣，建立模型。

根據所給示意圖將路口節點視為圖的頂點，利用matlab建立以路口節點為頂點的鄰接矩陣A=（aij），計算鄰接圖中相鄰兩節點之間的距離dij：

其中vi與vj相鄰，即aij=1，若兩頂點不相鄰，距離默認為∞，以兩頂點間距離為邊權，用matlab編程得邊權矩陣D92×92=（dij）。

在保證每個可能事發節點有且只有一個服務平臺出警和服務平臺出警時間最短的前提下，我們建立目標函數min dij fij

且滿足以下條件：

1）每個路口節點只有一個服務臺負責管轄：

2）每個巡警服務臺至少管轄一個路口：

3）負責出警的服務臺到事發節點的距離不超過30mm

dij fij≤30

4）問題二數學模型的建立

用Floyd算法編程得任意兩節點之間的最短距離dij，以及任意兩節點之間的最短路徑。為保證短時間內是此案快速封鎖，所以我們要在最長時間中尋求最小于，是我們引入0-1變量建立了快速封鎖模型：

min max dij sij

二、模型的求解和方案的確定

（1）利用matlab得交巡警服務平臺的管轄范圍，如下表：

（2）借助lingo得到A區的13條交通要道的快速封鎖方案，最短時間為7.4min如下表：

至此我們給出了該市各交巡警服務平臺管轄范圍的分配方案和突發事件時交通要道的快速封鎖方案。

三、結束語

運籌學是一門應用性非常強的課程，但是目前獨立學院在運籌學方面的教學工作主要集中在理論知識方面，過于強調學生對模型的求解相反忽視了如何建立模型這一關鍵環節。另外，現實中能用運籌學來解決的問題多數是要借助計算機進行求解的，但是我們的教學中重點考核的卻是學生在理論方面的掌握情況忽視了軟件的重要性。這一現狀導致學生雖然學完了運籌學課程的所有內容，但應用運籌學解決實際問題的能力卻是很差的。所以我們要對運籌學的教學模式進行改革，提高學生建立模型和用軟件求解模型的能力。2011年高教社杯全國大學生數學建模競賽B題中某市交巡警服務平臺的設置和調度就是一個非常好的實例，我們通過對該問題的分析、建模、求解來幫助學生更好的理解和掌握如何在實際問題中運用運籌學。

[ 參 考 文 獻 ]

[1] 謝金星.優化模型與LINDO/LINGO軟件[M].北京：清華大學出版社，2006.

[2] 王沫然.MATLAB與科學[M].北京：電子工業出版社，2008年.

[3] 袁新生.lingo和excel在數學建模中的應用[M].北京：科學出版社，2007.

[4] 孫強，沈建華，顧君忠.求圖中頂點之間所有最短路徑的一種實用算法[J].計算機工程，2002（2）.

[5] 徐鳳生.最短路徑的求解算法[J].計算機應用，2004（5）.

[6] 馬云峰，張敏，楊珺.物流設施選址問題中時間滿意度函數的定義及應用[J].物流技術，2005（9）.

[7] 周建勤，鞠頌東.一種基于經驗與模型的選址優化方法[J].物流技術，2006（3）.

[責任編輯：王 品]