交巡警服务平台的设置与调度论文.pdf

1 交巡警服务平台的设置与调度 摘要 本文通过建立数学模型 对合理地设置交巡警服务平台 分配各平台的管辖范围 调度警务资源等问题进行了深入的分析和研究 对于问题一 通过相关资料了解到 交巡警的工作职责除了处理辖区内各路口发生 的案件外 还需对辖区内的道路进行巡逻 因此 服务平台的工作量除了受辖区内路口 节点的总案发率影响外 还受辖区内道路总长的影响 首先 对于问题 1 1 根据 3 分钟内有交巡警到达事发地 的要求 得到各服务 平台的可管辖路口节点 发现还有 6 个路口由于不满足要求未被管辖 因此 采取 就 近分配 原则 将这些路口分别分配给邻近的服务平台管辖 其次 对于问题 1 2 一个合理的快速封锁调度方案 即在最短时间内实现全封锁 据此 以缩短耗时最长的路口封锁时间为目标 建立 0 1 规划模型并求解 得到实现全 封锁所需最短时间为 8 01 分钟 最后 对于问题 1 3 根据拓扑结构中的星状结构 将路口节点与其相连边的一半 看作一个节点单元 利用熵权法 确定各节点单元的路程长短和案发率大小在节点单元 工作量指标中的权值 并通过加权得到节点单元工作量的综合量化值 然后 以所有平 台总工作量尽量小及平台工作量尽量均衡为目标建立规划模型 求解得到现有各平台工 作量及辖区划分情况 考虑出警时间的约束 确立了增设 4 个平台的方案 再通过均衡 性评价了新方案的合理性 问题二中 对于问题 2 1 在问题一中已有模型的基础上 建立模型求解出全市各 区被管辖的路口节点个数 发现全市有 23 9 的节点未被管辖 说明现有方案明显不合 理 对此 采用递归算法 确立了增设平台数最少的方案 对于问题 2 2 利用图论中 最短路问题 的求法 采用动态模拟法 模拟出不同 时段嫌犯可能到达的路口节点 给出了较优的围堵参考方案 关键词 交巡警服务平台 floyd 算法 星状拓扑结构 熵权法 递归算法 2 一 问题重述 1 1 问题背景 有困难找警察 是家喻户晓的一句流行语 警察肩负着刑事执法 治安管理 交通管理 服务群众四大职能 为了更有效地贯彻实施这些职能 需要在市区的一些交 通要道和重要部位设置交巡警服务平台 每个交巡警服务平台的职能和警力配备基本相 同 由于警务资源是有限的 如何根据城市的实际情况与需求合理地设置交巡警服务平 台 分配各平台的管辖范围 调度警务资源是警务部门面临的一个实际课题 附件 1 A 区和全市六区交通网络与平台设置的示意图 附件 2 全市六区交通网络与平台设置的相关数据表 共 5 个工作表 1 2 问题提炼 1 2 1 问题一的提炼 根据问题一中要求 有以下几个问题需要解决 问题 1 1 为 A 区已有 20 个交巡警服务平台分配管辖范围 使其在所管辖的范围内出现 突发事件时 尽量能在 3 分钟内有交巡警 警车的时速为 60km h 到达事发 地 问题 1 2 对于重大突发事件 需要调度全区 20 个交巡警服务平台的警力资源 对进出 该区的 13 条交通要道实现快速全封锁 实际中一个平台的警力最多封锁一 个路口 请给出该区交巡警服务平台警力合理的调度方案 问题 1 3 根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情 况 拟在该区内再增加 2 至 5 个平台 请确定需要增加平台的具体个数和位 置 1 2 2 问题二的提炼 根据问题二中要求 有以下几个问题需要解决 问题 2 1 针对全市 主城六区 A B C D E F 的具体情况 按照设置交巡警服 务平台的原则和任务 分析研究该市现有交巡警服务平台设置方案 参见附 件 的合理性 如果有明显不合理 请给出解决方案 问题 2 2 如果该市地点 P 第 32 个节点 处发生了重大刑事案件 在案发 3 分钟后接 到报警 犯罪嫌疑人已驾车逃跑 为了快速搜捕嫌疑犯 请给出调度全市交 巡警服务平台警力资源的最佳围堵方案 3 二 问题分析 2 1 问题一分析 由已给信息 每个交巡警服务平台的工作量主要由辖区内的路口节点的总案发率决 定 然而 通过查阅相关资料 交巡警服务平台的职责除了需要处理各路口节点的案件 以外 其还承担着巡逻管辖区内道路的任务 因此 为使得模型更符合实际需求 在建 立模型时 考虑巡逻对工作量的影响 也即辖区内道路的总长度对工作量的影响 对于问题 1 1 在对已有交巡警服务平台的管辖范围进行划分时 根据低于 3 分钟 的出警时间的要求 可直接以出警时间作为考量的指标 求解出每个交巡警服务平台的 可管辖路口 对于问题 1 2 考虑到一次快速全封锁所需时间是由封锁耗时最长的那个路口决定 因此可从尽量缩短封锁耗时最长的那个路口所需的时间方向考虑 建立模型对问题进行 求解 对于问题 1 3 可从现有各服务平台工作量均衡情况方向考虑 并遵循服务平台的 原则 建立模型确定增加平台的位置和个数 2 2 问题二分析 对于问题 2 1 根据 3 分钟内有交巡警到达事发地 的原则 求出全市各区中未 被管辖的点的个数 并以此作为评价指标 即可知道现有平台设置方案的合理性 对于 不合理的情况 可采用增设平台的办法进行解决 对于问题 2 2 考虑到嫌犯驾车逃窜的速度和方向具有很大的不确定性 并且封堵 耗时越长 围堵嫌犯的难度也越大 因此在确定围堵方案时 应以围堵时间尽量短 围 堵区域尽量小作为考虑的重点 三 模型假设 1 假设警局在接到报案后 能迅速反应 确定调度方案 2 假设参考警车的行驶速度 嫌犯驾车逃逸的平均时速为 60km h 3 假设各服务平台在没有接到特殊调度时 只处理本辖区内的事务 4 假设嫌犯驾车逃逸的方向是未知的 并且是以远离案发地点的方向行驶 5 假设道路上发生的案件归属到离案发地较近的那个节点 6 假设各服务平台的工作量主要由其辖区内的巡逻道路长度及各路口节点的总发案率 决定 4 四 符号说明及定义 4 1 符号说明 问题一符号说明 问题 1 1 符号说明 ij d 第 i 个服务平台到第 j 个路口的最短距离 问题 1 2 符号说明 v 表示警车的速度 取值为 16 67m s 60km h ij b 当第 i 交巡警服务平台被派往封锁第 j 个出人口则取值为 1 否则为 0 ij t 第 i 个交巡警平台到第 j 个出入 A 区路口节点的最短时间 问题 1 3 符号说明 X 2 行 92 列的每个节点原始数据矩阵 2 行表示两个评价指标 第一评 价指标为发案发率 第二评价指标为路程属性 92 列表示共 92 个节点 ij x 每个节点原始矩阵 X 中第 i 行第 j 列的值 ij r 对 X 中两指标发案率属性与路程属性归一化后第 i 行第 j 列的值 i H 第 i 个评价指标的熵值 i B 第 i 个评价指标的熵权 j t 第 j 个节点单元工作量综合指标 i w 第 i 个服务平台的总工作量 ij b 当第 i 交巡警服务平台管辖第 j 个节点则取值为 1 否则为 0 ij a 若第 i 个服务平台能在 3 分钟内赶到第 j 个节点则取 1 否则取 0 ij S 当第 i 交巡警服务平台到第 j 个节点的最短路程 均衡度牺牲程度 距离牺牲程度 5 4 2 定义 1 出警时间 是指从交巡警在接到报警电话时 从警务平台到案发现场的最短时间 2 节点单元 根据通信子网中的星状拓扑结构 如图 4 1 所示 将路口节点抽象为中 央节点 将路口节点对外伸展的道路的中点抽象为拓扑结构中的站点 如图 4 2 所示 将各道路中点依次连接后 得到图中的阴影区域 区域内的道路及节点即构成了一个节 点单元 这个节点单元的工作量由区域内巡逻道路的总长度和节点案发率决定 图 4 1 星状拓扑结构 图 4 2 节点单元 3 星状拓扑结构 辐射面区域划分法 是根据通信子网中的星状拓扑结构 并结合节 点 干线 辐射面理论引进的一种辖区划分法 其中 各路口抽象为拓扑结构的中央节 点 路口对外辐射的道路的中点抽象为中央节点外站点 以 A B C 服务平台为例 如 下图 假设 A 平台有五个路口 图中以字母表示 需要管辖 B 平台和 C 平台也各有 若干路口需要管辖 A 平台的路口节点会通过道路对外辐射并与 B C 平台的路口节点相 连 那么分别取这些道路的中点 图中的实心圆点 并依次连接这些外围中点 那么 这些外围连线即为 A 平台管辖区的边界 外围连线所围区域即为 A 平台的管辖区 图 4 2 A 服务平台辖区划分图 6 五 问题一模型的建立与求解 对于问题一 围绕划分各服务平台管辖范围 制定封锁调度方案 和制定增设平台 方案这些问题 分别建立模型进行分析求解 5 1 问题 1 1 各服务平台管辖范围的划分 现实生活中 在案情发生时 人们报警后总希望交巡警能以最快的速度赶到 由已 给信息 各服务平台的工作是当其管辖范围内有报案时 应在 3 分钟之内赶到事发现场 因此 可根据 尽量能在 3 分钟内有交巡警赶到事发地 的要求确定个交巡警平台的管 辖范围 由简单的物理学知识 在已知时间 t 为 3 分钟 警车速度 v 为 60km h 的情形下 警车能行驶的路程 S 为 svt 求得警车三分钟内能行驶的最长路程为 3 千米 由 A 区地图中各路口的坐标值 可以由两点距离公式 22 1212 Dxxyy 利用 Matlab 软件 对各路口节点坐标数据进行处理 求得各路口节点间的距离矩 阵 进而得到各条道路的长度 因此 问题转化为 从交巡警服务平台沿已有道路向周边延伸 3 千米所覆盖的区域 即为其辖区 根据已有假设 道路上发生的案件归属于道路两端路口中离案发地较近 的那个路口节点 问题又可进一步简化为 从交巡警服务平台沿已有道路向周边延伸 3km 所能覆盖的节点即为其管辖范围 根据图论知识 可利用 最短路问题 的求法 求得交巡警服务平台到其他各节点的最短路距离 便可得出在服务平台 3 千米区域的节 点 问题转化流程图如下 将路口节点 服务台抽象为节点 将各条道路抽象为边 其长度即为边的权值 由 7 各条道路的长度矩阵得到各节点的邻接矩阵 运用 floyd 算法 求得节点间的最短 路 同时得到了服务平台 i 到其他节点 j 的最短路 ij d 运用 matlab 软件 找出距每个服务平台 3km 以内的节点 这些节点即为每个服务 平台可管辖的节点 每个服务平台警力 3 分钟内能到达的节点表如下 表 5 1 交巡警服务平台的可管辖路口节点表 交巡警服务平台 112 18 19 42 43 44 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 2123 17 40 42 43 44 66 67 68 69 70 71 72 73 74 75 76 78 323 43 44 54 55 64 65 66 67 68 70 76 44 57 58 60 62 63 64 65 66 5567 47 48 49 50 51 52 53 56 58 59 6567 47 48 50 51 52 56 58 59 756789 30 31 32 33 34 47 48 8789 16 31 32 33 34 35 36 37 45 46 47 9789 16 31 32 33 34 35 36 37 45 46 1010 1111 25 26 27 1212 25 1313 21 22 23 24 1414 1515 31 1689 16 33 34 35 36 37 45 46 172 17 40 41 42 43 70 72 181 18 19 20 71 72 73 74 77 78 79 80 81 82 83 84 85 87 88 89 90 91 191 18 19 64 65 66 67 68 69 70 71 73 74 75 76 77 78 79 80 81 82 83 2018 20 81 82 83 84 85 86 87 88 89 90 91 可管辖路口节点 此外 由于只考虑 3 分钟到达事发地 的约束 有 28 29 38 39 61 92 6 个路 口节点未能划分到管辖区 因此 采取就近原则 将这些路口分别分配到临近的服务平 台管辖 分配情况如下表 表 5 2 未划分的路口节点最终划分情况 未分配的路口节点 28 29 38 39 61 92 划分后所在管辖区 15 15 2 2 7 20 5 2 问题 1 2 确定封锁调度方案 事实上 在对 13 条交通要道实现快速全封锁时 整个封锁的方案所耗时间是由封 锁耗时最长的那个路口决定的 因此 应使最后封锁的路口所花费的时间最少 依据此 建立目标函数 11 1112 1220 13 minmax ijij t bt bt bt b 此外 每个路口只由一个平台的警力来封锁 即 20 1 1 ij i b 因为一个平台的警力最多可以封锁一个路口 所以 8 13 1 1 ij j b 总共有 13 个交通要道 所以 2013 11 13 ij ij b 第 i 个服务平台到第 j 个路口节点的要花费的最短时间 ij ij d t v 由此可建立如下规划模型 11 1112 1220 13 minmax ijij t bt bt bt b 20 1 13 1 2013 11 1 1 13 1 2 201 2 13 ij ij ij i ij j ij ij d t v b st b b ij 利用 lingo 软件编程求解得到封锁调度方案如下表 表 5 3 封锁调度方案表 待封锁的 路口 16 48 30 29 22 24 12 21 23 28 14 38 62 被选服务 平台 3 4 5 7 10 11 12 13 14 15 16 17 18 耗时 min 6 02 7 39 3 18 8 01 7 71 3 80 0 2 71 6 47 4 75 6 74 4 75 6 73 通过上表 可以知道封锁调度情况 并且可以知道 10 号服务平台封锁 22 号路口耗 时最长 为 8 01 分钟 由此可知 最后全封锁所耗时间为 8 01 分钟 5 3 问题 1 3 增设服务平台方案 首先 在确定增设服务平台方案之前 需要了解现有各平台工作量情况 鉴于每个 服务平台的交巡警兼有办案与巡逻的两方面职责 那么每个平台的工作量应该将办案的 9 工作量与巡逻的工作量综合考虑 为便于将这两种工作量综合量化为一个工作量指标 引用前面已定义的 节点单元 模型 下面逐步确定 工作单元 的工作量 5 3 1 确定各节点单元的路程属性和案发率属性 由以上分析知 节点单元的工作量由单元内节点的工作量和巡逻道路的工作量决 定 每个节点工作量取决于节点的案发率 因此可认为每个节点单元拥有一个案发率属 性 案发率属性值即为案发率 巡逻道路工作量取决于单元内道路总长 因此可认为每 个节点单元拥有一个的路程属性 路程属性值即为路程长短 图 5 1 节点单元 如图 5 1 所示 节点单元路程属性值D可由以下公式求得 1 11 21 314 1 11 21 314 BBBB 1 2 ACACACAC AAAA Ddddd dddd 式 其中 1 1 AC d 表示路线 11 AC 的长度 即节点路程属性D为节点相连边边长的一半求和 事实上 式所表示的节点单元路程属性的现实意义为 如果将某个节点划分给某 个服务平台管辖 那么该节点所在的节点单元内的所有道路的巡逻任务也都交由该服务 平台负责 因此 某服务平台的总巡逻路程即为该服务平台辖区内所有节点单元的路程 属性值之和 即 ij j SD i S 表示第 i 个服务平台总巡逻距离 j 为第 i 个服务平台所管辖的节点 对于节点单元的案发率属性R 其值就等于已知的路口节点平均每天案发率值 因此 A 区每个节点单元的两个属性 案发率属性和路程属性 值都已确定 得下 表 以 1 10 号节点所在节点单元为例 表 5 4 节点单元案发率属性值表 节点单元 1 2 3 4 5 6 7 8 9 10 案发率属性值 1 7 2 1 2 2 1 7 2 1 2 5 2 4 2 4 2 1 1 6 10 表 5 5 节点单元路程属性值表 节点 1 2 3 4 5 6 7 8 9 10 路程属 性值 13 48 22 62 41 39 05 14 02 15 45 49 32 24 99 10 43 42 3 5 3 2 利用熵权法确定各节点单元的路程属性和节点属性的权值 每个服务平台的总工作量为其辖区内各节点单元的工作量总和 对于确定节点单元 的综合工作量 需对案发率属性值与路程属性值综合量化 因此 需先确定这两种属性 在总工作量目标中的权值 对于确定权值 可采用熵权法确定 熵权法不同于很多其他的权值确定评价方法 如 层次分析法 其完全是根据样本数据的统计规律 客观定量地确定样本指标的权值 5 3 2 1 熵的基本原理 信息熵是系统无序程度的度量 它被定义为信息量的概率加权统计平均值 即 1 lg 1 n ii i Hpp 式中 i p 为事件的概率 式 1 表明 H是 i p 或 p x 的函数 是平均不确定性的一种表征 因此用熵 来确定权重 当评价对象在某项指标上的值相差较大时 熵值较小 说明该指标提供的 有效信息量较大 权重也应较大 反之 若某项指标的值相差越小 熵值较大 说明该 指标提供的信息量较小 权重也应较小 熵值赋权法就是在客观的条件下由各评价指标的监测值构成的判断矩阵来确定各 指标的权重的方法 引用信息熵评价所获系统的有序度与效用 避免了各因子权重的主 观性 因而评价的结果更能反映实际情况 5 3 2 2 熵权的计算方法 对于每个节点单元有 2 个工作量评价指标 路程属性值 案发率属性值 被评对 象即为 A 区节 92 个路口节点 由此形成了原始数据矩阵 2 92 ij Xx 具体步骤如下 1 形成原始矩阵 X 11121 92 21222 92 xxx X xxx X 矩阵第一行为 92 个节点的路程属性值 第二行表示 92 个节点的案发率属性值 对不同指标需进行归一化处理 根据案发率与道路长度都是值越大则工作量越大 因此 采用 11 min max min ijij j ij ijij jj xx r xx 对前 10 个节点的作归一化处理后 得到下表归一化值 表 5 6 节点单元属性归一化值 节点单元 1 2 3 4 5 6 7 8 9 10 案发率属 性 0 64 0 8 0 84 0 64 0 8 0 96 0 92 0 92 0 8 0 6 路程属性 0 199 0 3645 0 6975 0 6622 0 2088 0 2346 0 8483 0 4074 0 1437 0 7211 2 定义熵 第 i 个指标的熵定义为 1 ln 1 2 92 ln n ijij i i ff Hin n 式中 92 1 ijijij j frr 当 0 ij f 时 令 ln0 ijij ff 通过程序求得节点单元的案发率属性和路程属性的熵值如下表 表 5 7 节点单元的发案率属性和路程属性的熵值 指标 熵值 发案率属性 0 9779 路程属性 0 9505 3 定义熵权 2 1 1 i i i i H B mH 式中 2 1 01 1 ii i BB 求得节点单元的案发率属性和路程属性的熵权如下表 表 5 8 节点单元的案发率属性和路程属性的熵权 指标 熵权 w 发案率属性 0 3081 路程属性 0 6919 4 综合量化节点单元工作量 12 由案发率属性与路程属性分别对熵权加权求和 得到各节点单元的工作量综合量化值 t 2 1 j 1 2 92 ji ij i tB r 各节点单元的工作量综合量化值见下表 表 5 9 各节点单元的工作量综合量化值表 节点单元12345678910 工作量0 33490 49860 74140 65540 39090 45810 87040 56530 34590 6838 11121314151617181920 0 66360 57140 46510 89170 93840 95090 80010 44040 26790 3006 21222324252627282930 0 44650 50360 28340 35440 50420 42900 30870 47390 65420 7619 31323334353637383940 0 51030 31800 26010 65060 22880 41280 19130 58770 76390 5651 41424344454647484950 0 72370 24110 36480 31680 47470 38460 61250 41890 24300 2344 51525354555657585960 0 12400 13740 36740 42480 40640 12210 34770 18790 23500 3983 61626364656667686970 0 42970 58940 40180 23070 19450 15910 19990 16580 24140 2027 71727374757677787980 0 20160 18730 26670 30070 16380 28230 20740 19980 15300 2395 81828384858687888990 0 45450 21200 19660 20570 55410 27920 32040 19540 25460 1739 9192 0 24160 6048 5 3 3 现有平台辖区的划分及工作量的确定 首先 假设每个节点只能由一个服务平台管辖 在对现有服务平台进行划分时 既要能保证服务平台工作量均衡 均衡度指标 又要保证服务平台尽量管辖距其较近的节点 距离指标 然而 在实际求解过程中 往往不能同时使得两个指标达到最优 只能尽量平衡这两项指标 在对两种指标进行综 合考量时 由于这两个指标的量纲不一致 故需要对这两个指标进行标准化处理 而运 用一般的标准化方法对这两个指标进行处理 并不能得到一个理想的结果 为此 在此 定义一种新的方法 对这两个目标进行标准化处理 先仅以 尽量使每个服务平台工作量均衡 为目标 对问题进行求解 得到一个均 衡度最理想的方案 将求得的目标值作为其度量标尺 再以 尽量使服务平台管辖距其近的节点 为目标 对问题进行求解 得到一个 距离指标最理想方案 将求得的目标值作为其度量标尺 1 只考虑 尽量使每个服务平台工作量均衡 受 出警时间小于 3 分钟 约束 使得一些平台工作量较小且其值具有稳定性 这使得所有节点中工作量的最小值具有稳定性 现定义均衡度如下 min 均衡度 1 2 20 max i i w i w 13 由此定义可知 平台工作量的最大值即能反应各平台工作量均衡情况 因此 以使平台 工作量的最大值尽量小为目标建立规划模型 目标函数为 minmax 1 2 20 i wi 1 0 1 约束 01 ij bor 2 每个节点只能归一个服务平台管辖约束 20 1 1 1 2 92 ij i bj 3 每个服务平台的管辖范围仅限于 3 分钟车程内能到达的节点 对于 3 分钟车程不能 到达的 6 个节点 划分给距其最近的服务平台管辖 有如下约束 0 ijij ab 4 每个服务平台的工作量为 92 1 iijj i wb t 因此可建立以下 0 1 规划模型 minmax 1 2 20 i wi 20 1 92 1 01 1 0 1 2 20 1 2 92 ij ij i ijij iij j i bor b st ab wb t ij 由模型的求解结果分析 发现若只考虑工作量均衡这一目标 会出现某个服务平台 为使得其工作量和其他平台尽量均衡 而 舍近求远 来增加自身的工作量 这使得 全区所有平台的工作总量增大 这种结果也验证了均衡度指标和距离指标之间的对立 性 为便于后续模型的改进 将此模型求出的目标值 W 作为度量工作量均衡度的一个 标尺 通过定义均衡度牺牲量 max i w W 便可反映均衡度的 牺牲程度 其值越大 14 均衡度牺牲量越大 换来 的距离指标值越理想 2 只考虑 尽量使服务平台管辖距其近的节点 目标函数可定义为 所有服务平台与其管辖节点距离总和尽量小 2092 11 min ijij ij b S 其中 ij S 为第 i 个服务平台与第 j 个节点之间的最短距离 1 0 1 约束 01 ij bor 2 每个节点只能归一个服务平台管辖约束 20 1 1 1 2 92 ij i bj 3 每个服务平台的管辖范围仅限于 3 分钟车程内的节点 对于 3 分钟车程不能到达 的 6 个节点 划分给距其最近的服务平台管辖 0 ijij ab 因此可建立以下 0 1 规划模型 2092 11 min ijij ij b S 20 1 01 1 0 1 2 20 1 2 92 ij ij i ijij bor b st ab ij 将此模型求解出的目标值 D 作为 尽量使分配的节点离其服务平台最近 这一目标 的标尺 同样定义 2092 11 ijij ij b S D 通过 值的大小便可知道距离指标的牺牲程度 其值越大 表示这一指标牺牲程度 越大 15 3 综合考虑均衡度与距离指标 由以上定义的均衡度牺牲程度 与距离牺牲程度 为同时照顾到均衡度与距离 指标 即要使得这两项指标的牺牲程度都尽量小 设定一下目标函数 min 20 1 92 1 2092 11 01 1 0 max 1 2 20 1 2 92 ij ij i ijij iijj i i ijij ij bor b ab wb t st w W b S D ij 通过对模型进行求解 得到现有服务平台的分配情况 见附表 10 1 1 现有服务平台分布合理性分析 建立以上 综合考虑均衡度与距离指标 的辖区划分模型 按照现有的服务平台及 其分布情况 寻找到最优的辖区分配方案 可得出各服务平台的任务量表 表 5 10 现有各服务平台工作量情况 节点12345678910 工作量2 35692 60502 24302 62332 53250 58022 48091 52802 21030 6838 节点11121314151617181920 工作量1 40131 07562 05300 89172 06651 55502 33002 10500 62832 5683 求得各服务平台任务量的标准差为 0 7195 2 合理地增加服务平台 由问题 1 1 中结果得有 6 个节点 图示中已编号的 6 个节点 发现这六个节点 又分布在 4 个区域 为满足 3 分钟内及时到达案发现场的原则 可按图示方法确定 增加四个服务平台 图中方框标示 16 图 5 2 新增设的 4 各平台分布情况 增加这 4 个节点后 再次应用服务平台辖区划分模型 重新为服务平台分配辖区节 点 得到增加 4 个节点后的每个服务平台的辖区分布情况 见附表 10 2 每个服务平台 的工作量见下表 表 5 11 增设 4 个平台后每个服务平台的工作量 节点123456789101112 工作量2 35691 57022 15692 39262 04211 07062 36921 21002 21030 68381 40131 0756 节点131415161718192029396192 工作量2 05300 89170 93841 55501 76491 74870 62832 31981 12811 91670 42970 6048 求得各服务平台任务量的标准差为 0 6411 在此基础上 对新旧方案进行全面的对比 如下表所示 表 5 22 新服务平台设置方案和原有方案的比较 较远的节点个数 平台最大任务量 任务量标准差 路程总和 增加服务平台前 6 2 6233 0 7195 1077 345 增加服务平台后 0 2 3569 0 6411 797 1493 通过比较发现 在指定节点增加 4 个交巡警服务平台后 新方案的各项指标均有 较大改善 特别是增加 4 个交巡警服务平台后所有节点都在服务平台 3 分钟车程的范围 内 很大程度地改善了出警时间过长的问题 此外 增设 4 个交巡警服务平台后 服务 平台的最大工作量也有相应的减少 各平台任务量标准差也降低了 说明各平台工作量 的均衡性得到了改善 从路程总和上看 减小的量比较大 说明增设平台后 服务平台 在 尽量管辖离其近的节点 方面得到了改善 综合以上各种因素 发现按这种方案增 加服务平台的位置与个数是很合理的 17 六 问题二模型的建立与求解 6 1 问题 2 1 模型的建立与求解 设置交巡警服务平台的原则是 3 分钟内有交巡警到达事发地 先依据此原则对全 市各区的服务平台的进行辖区划分 然后以 未划分给辖区的路口节点数 作为评价指 标 对全市市现有交巡警服务平台设置方案合理性进行评价 节点数越少 方案越合理 6 1 1 确定各区 未划分给辖区的路口数 根据全市六区的现有服务平台设置情况和已有数据 在问题 1 1 模型的基础上 求 解出各区未划分给辖区的路口节点数 程序求解步骤如下 1 建立各个城区路口节点到路口节点的邻接矩阵 A B C D E F 2 建立各个城区服务平台到各个路口节点的邻接矩阵 a b c d e f 3 用 floyd 算法分别求出上述各个矩阵的最短路径矩阵 分别定义为 A B C D E F a b c d e f 4 由上述最短路路径矩阵 得出各个城区中未划分给辖区的路口节点数 程序求解结果如下表 表 6 1 全市六区未划分给辖区的路口信息表 各区 市 A 区 B 区 C 区 D 区 E 区 F 区 全市 未划分给辖区的路口数 6 6 47 12 33 35 139 路口总数 92 73 154 52 103 108 582 未划分给辖区的路口数占各 区 市总数的百分比 6 5 8 2 30 5 23 1 32 32 4 23 9 由结果发现 全市未划分给辖区的路口数为 139 个 占全市路口总数的 23 9 即 相当于平均每 5 个路口中 就有 1 个路口未被管辖 由此可以认为该市现有交巡警服务 平台设置方案是不合理的 可以通过增加平台的方式去解决这个问题 6 1 2 增加服务平台方案 在确定增加节点的方案时 需要考虑增加节点的个数和节点的位置 对于增设个数 可以采取逐个增设的方式 因为新增设的平台 又可以对其周围 3 分钟内能到达的节点 进行管辖 即将未管辖点转化为管辖点 因此新增平台的位置应设在能最大程度将未 管辖点转化为管辖点的位置 通过这种方式可以使增加的平台数最少 事实上 通过定义一个递归函数 f x 即可实现这种增设方式 定义如下 1 i 1 i 1 第次增设时 还有未管辖点 第次增设时 已无未管辖点 ii i i f x f x 其中 i为待增设的平台 i x 表示第 i 次增设时 未管辖点之间建立的最短路径 矩阵 i f x 返回的结果为第i 1次增设确定的待增设服务平台的集合 利用这个递归 函数 通过 matlab 编程求解 得到各区待增设平台的情况如下表 18 表 6 2 新增平台个数及位置 区 个数 新增平台所在的路口节点号 A 4 28 38 61 92 B 2 122 151 C 16 184 201 203 204 207 216 239 241 249 252 258 262 265 286 313 316 D 10 320 329 332 336 337 339 344 362 369 370 E 15 387 388 390 391 392 408 415 417 418 420 446 458 464 471 474 F 15 486 509 512 517 527 540 541 559 560 561 566 574 575 578 582 6 2 问题 2 2 模型的建立与求解 为了快速搜捕嫌疑犯 围堵方案应遵循以下原则 1 包围区域尽量小 即使得抓捕工作量尽量小 2 全面围堵耗时尽量短 使逃犯逃逸的距离尽量短 6 2 1 接到报警时 嫌疑犯的位置分析 已假设逃犯驾车逃逸的最大时速为 60km h 则在未接到报警的 3 分钟内 逃犯最大 行驶里程为 3km 运用 floyd 算法 求得全市 6 个区任意两点间的最短路径 以此求得 距案发 P 点 3km 内的节点 如下图 所示节点 因此 嫌犯很有可能已逃出这些节 点 因此可初步判断若在这些节点设堵 意义不大 图 6 1 不同时段逃犯可能到达的节点 由于逃犯驾车方向是不可预知 因此可以认为逃犯是在从图示 所圈节点或其 附近道路 正驾车向远离案发 P 点逃窜 但还未到下一个 3km 以外的节点 与此同时 警局接到报案 迅速作出反应 确定围堵方案 安排全市各交巡警服务 平台按要求实施围堵 围堵方案确定原则 19 a 警局接到报案时 图示 所圈节点或其附近道路便是逃犯的起点 b 全面考虑逃犯逃窜的所有可能性 c 可调派全市所有交巡警服务平台警力 提前对节点实施围堵 即警力能赶在逃犯以 最短路径到达节点前 对路口节点实施封堵 d 当所有的警力部署完后 逃犯已被包围 不可能再沿着道路离开包围圈 即对嫌犯 已完成完全封锁 e 包围圈尽量小 通过取 0 5 分钟为最小步长 对逃犯于各时间段可能逃到的节点进行动态模拟 每次 增加 0 5 分钟 由 P 点与其他节点间的最短路径 确定逃犯可能逃往的最远节点 再运 用调优法 直到确定围堵方案满足上述原则 得到各交巡警服务平台调度方案如下表 在这种调度方案下 实现全封堵所需时间为围堵所用的最长时间为 8 79 分钟 表 6 3 交巡警服务平台调度表 服务平台 2 3 4 10 15 16 17 168 169 围堵节点 40 3 54 10 239 16 41 62 253 围堵时间 1 91 0 00 3 45 0 00 7 06 0 00 0 85 3 35 6 13 服务平台 170 171 173 175 179 320 321 475 围堵节点 227 216 235 168 273 371 370 561 围堵时间 2 59 0 96 0 53 4 98 2 59 7 36 8 79 4 35 七 模型的评价 7 1 模型的评价 7 1 1 模型的优点 1 我们建立了一个很好量化工作量的模型 节点单元 将辖区工作量单元化 工 作量由案发率和巡逻路程两个部分决定 通过合理地引入熵权法来确定其权值 避免了人为定权值的主观性 2 用 星状拓扑结构 辐射面区域划分法 划分管辖区域 形象直观地表述出各 平台的管辖区域 3 在问题 2 1 中 采用递归算法得到增设平台方案 结构清晰 可读性强 当然也 会在一定程度上降低程序的执行效率 7 1 2 模型的不足 1 在问题 1 1 中 由于题目所给的信息有限 使得我们所建立的模型只考虑了点的情 况 在现实生活中 发生道路上的事故往往不能简单地认为发生在最近的路口 2 在问题一中建立的优化模型 lingo 程序执行时间比较慢 可以考虑有没有更加有效 的算法 比如尝试用某些启发式算法进行求解 3 第二问中的围堵问题 虽然模型得到了较优的方案 但是主观性强 20 八 模型的深入与推广 8 1 模型的深入 现实问题远比题目复杂 而且考虑因素也复杂的多 对于这类问题可以尝试进一步 深入 可以考虑路线 区域 人口密度等因素对交巡警服务平台影响 当然 解决这类 问题得还需要获得更多数据 8 2 模型的推广 交巡警服务平台的设置与调度问题类似于资源调配和人员安排这类问题 我们建立 的模型不仅可以较好解交巡警服务平台的设置与调度的问题 对于某些资源调配和人员 安排的问题也很有参考意义 模型应用图论的相关理论和算法 简化了原问题中元素之 间的关系 使问题求解过程清晰 熵值法确立权值 可以减少人为主观因素对结果到印 象 很具有推广性 九 参考文献 1 1 邓春燕 两种最短路径算法的比较 J 电脑知识与技术 2008 12 511 513 2 2 程吉树 陈水利 点集拓扑学 M 北京 科学出版社 2008 年 5 月 3 3 张国伍 彭宏勤 智能交通系统工程导论 M 电子工业出版社 2003 年 9 月 4 4 姜启源 数学模型 第三版 M 电子工业出版社北京 高等教育出版社 2008 年 3 月 5 5 安鑫 周维博 马艳 云涛 基于熵权的模糊综合评价法在水安全中的应用 J 水 资源研究 2011 32 1 18 19 21 十 附录 10 1 表格部分 10 1 1 问题一建模图表 附表 10 1 A 区现有服务平台辖区划分情况表 服务平台 11676869717374757678 223839437072 334454556566 445760626364 554749505152535859 6656 77304861 88323346 9931343545 1010 11112627 121225 131321222324 1414 15152829 16163637 1717404142 1818808182838791 19197779 202084858688899092 未增加服务平台 管辖节点 附表 10 2 增加 4 个服务平台后辖区划分情况表 服务平台 11676869717374757678 2243447072 335455646566 4457606263 554950515253565859 6647 77303248 883346 9931343545 1010 11112627 121225 131321222324 1414 1515 16163637 17174142 181880818283840 19197779 202085868788899091 212829 22383940 2361 2492 增加4个服务平台 管辖节点 22 10 2 程序部分 部分程序因占篇幅较大未附 10 2 1 问题一程序 10 2 1 1 问题 1 1 程序 floyd m floyd 算法 保存为 floyd m function D R floyd a n size a 1 D a for i 1 n for j 1 n R i j j end end R for k 1 n for i 1 n for j 1 n if D i k D k j D i j D i j D i k D k j R i j R i k end end end end k D R 1 1 m 任意两点直线距离距离 for i 1 92 for j 1 92 AD i j A i 2 A j 2 2 A i 3 A j 3 2 0 5 end end 求邻接矩阵 AD road AD road ones 92 92 10000 for i 1 140 AD road A road i 1 A road i 2 AD A road i 1 A road i 2 23 AD road A road i 2 A road i 1 AD A road i 2 A road i 1 end for i 1 92 AD road i i 0 end 用 floyd 算法求任意两点最短距离 D R floyd AD road 10 2 1 2 问题 1 2 程序 sets patrol 1 20 cross 1 13 link patrol cross b bwteen t endsets data bwteen 22236 1527 16028 4737 9286 8122 19293 4393 21096 2149 22501 7534 22893 2028 19001 1602 19515 8062 12083 4445 5880 9349 11850 1148 4885 2167 20463 9221 14129 7247 7388 0632 17394 6903 19197 4659 20603 0044 21120 9722 17228 9296 17743 5756 10311 2139 3982 1859 10309 5372 6035 0675 18352 2685 12767 2273 6025 5658 16032 1928 17834 9685 19240 5070 19009 3186 15117 2760 15631 9220 8199 5603 6093 8396 8197 8836 4393 3852 21997 3830 15008 5146 8266 8530 18273 4801 20076 2557 21481 7943 22654 4331 16226 9087 15535 3379 8102 9762 4860 9758 7395 8694 350 0000 17628 1911 12969 6286 6227 9671 16234 5941 17749 5236 19155 0621 18285 2412 11306 8652 10615 2943 3182 9327 9421 1191 2475 8259 5255 0748 17658 7760 13000 2135 6258 5520 16265 1790 17780 1085 19185 6470 18315 8261 11337 4501 10645 8792 3213 5176 9451 7040 2506 4108 5337 3324 14914 9358 10901 2210 4159 5595 14166 1865 15036 2683 16441 8068 15571 9859 8570 2184 8015 4569 583 0952 7352 7115 1290 2020 7991 7216 14092 5057 9433 9432 2692 2817 12698 9087 14213 8382 15619 3767 14749 5558 10228 0254 10493 1815 3060 8198 5885 4337 3099 4673 8677 2828 13010 7149 8274 2018 1532 5403 11539 1674 13132 0474 14537 5859 13667 7650 9775 7224 10724 4057 3492 3036 4725 6923 4199 4104 9336 6681 24 7586 5852 12775 6589 6956 6700 9510 6934 7707 9177 9113 4563 8243 6353 14194 8645 15143 5478 7911 4458 10149 8220 8618 5526 14760 7978 3791 3528 8337 2977 11395 0312 5072 3322 3269 5