运筹学在交巡警服务平台设置和调度中的应用

[摘 要]当前培养应用型人才是高等教育的主要目标，所以学生在学习和掌握基本知识的同时更重要的是运用运筹学的方法借助软件解决实际问题，这也是我们运筹学教学改革的主要目标。在运筹学的实际教学工作中，我们以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）.

[责任编辑：王 品]