数学建模试题.pdf

2011 高教社杯全国大学生数学建模竞赛高教社杯全国大学生数学建模竞赛 承承 诺诺 书书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则 我们完全明白 在竞赛开始后参赛队员不能以任何方式 包括电话 电子邮件 网 上咨询等 与队外的任何人 包括指导教师 研究 讨论与赛题有关的问题 我们知道 抄袭别人的成果是违反竞赛规则的 如果引用别人的成果或其他公开的 资料 包括网上查到的资料 必须按照规定的参考文献的表述方式在正文引用处和参 考文献中明确列出 我们郑重承诺 严格遵守竞赛规则 以保证竞赛的公正 公平性 如有违反竞赛规 则的行为 我们将受到严肃处理 我们参赛选择的题号是 从A B C D中选择一项填写 B 我们的参赛报名号为 如果赛区设置报名号的话 13243003 所属学校 请填写完整的全名 华中农业大学 参赛队员 打印并签名 1 傅昱贤 2 陈 适 3 黄松钱 指导教师或指导教师组负责人 打印并签名 教练组 日期 2011年 9 月 12 日 赛区评阅编号 由赛区组委会评阅前进行编号 2011 高教社杯全国大学生数学建模竞赛高教社杯全国大学生数学建模竞赛 编编 号号 专专 用用 页页 赛区评阅编号 由赛区组委会评阅前进行编号 赛区评阅记录 可供赛区评阅时使用 评 阅 人 评 分 备 注 全国统一编号 由赛区组委会送交全国前编号 全国评阅编号 由全国组委会评阅前进行编号 交巡警服务平台的设置与调度 摘要 警察肩负着保卫人民生命财产安全的职责 科学地安排警力 不仅能提高出警效 率 而且能更好地为人民服务 本文基于图论中的相关理论 对交巡警服务平台的设 置与调度做了一些探讨 对于第 1 问 首先构造 A 城区内各节点之间的直达距离矩阵 并通过 Dijkstra 算 法计算出平台与各节点之间的最短距离 然后基于距离最小原则 先建立 3 分钟车程 约束的点到达模型 再将各道路按半分钟车程离散化为一些的切点 建立线到达模型 得到平台管辖范围分配 见表 5 1 和表 5 2 和 3 分钟点到达率 93 48 线到达率 87 27 最后 对两个模型进行了比较 线到达模型有效克服了高点到达率背后隐藏 的道路空缺假象 对于第 2 问 首先建立了基于最大用时最小的短板效应规划模型 继而建立了基 于全局用时最少的单目标规划模型以及综合最大用时最小和全局用时最少的双目标规 划模型 分别得到快速全封锁的警力调度方案 见表 5 3 并对三个规划模型进行了比 较分析 双目标规划模型求得的警力调度方案最大用时 8 015 分钟 平均用时 3 553 分钟 相对于两个单目标规划更实用 对于第 3 问 首先限制各地出警时间时长 筛选能够保证城区内大部分地区出警 时间不超过 3 分钟 个别地点不超过 4 分钟的新平台位置在 29 61 号节点 其次 对 各平台工作量均衡的限制 采用逐层目标规划模型 逐次搜索 最后确定在 30 41 号节点再新增 2 个服务台 并讨论了增加第 5 个平台的效益 认为没有必要 最终确 定在 29 30 41 61 号节点处新增 4 个服务台 3 分钟线到达率为 93 64 但是对 于各平台相对工作量的均衡性很强 方差为 0 2031 并且利用 5 1 1 线到达模型得到 24 个平台管辖范围 见表 5 6 对于第 4 问 首先根据各区域现状及警察相关职能 提出了平台平均覆盖面积指 数 平台平均管辖人口指数 3 分钟到达率指数 警力分布均衡性指数四个评价指数 最后用模糊综合评判求出了各区域的得分 并进行了分级 分级结果表明 A 城区交巡 警平台设置等级为优 而 D F 城区较为不合理 等级为较差 最后 再考虑到交巡 警平台设置规则 提出了 渴望度 指标对各区域的增加数目进行了分配 见表 5 13 对于第 5 问 考虑到嫌犯行动路线的不确定 无法准确了解其位置 同时 受到 孙悟空逃不出如来佛祖手掌心 这一神话故事的启发 本文提出 五指山 搜捕法 手掌 边界比孙悟空提前赶到即可成功捉拿孙悟空 据此思想 本文首先对该围捕 问题进行了简化 考虑两次围堵 利用算法求解 最终得到了全市最优的交巡警调度 方案 见表 5 14 表 5 15 之后对算法进行了改进 并提出了对一般案件的响应机制 最后 对所建立的模型和求解方法的优缺点给出了中肯的评价 并指出了改进的 方向 还对所建立的模型进行了推广 关键词 资源配置 逐层目标规划 模糊综合评价 均衡算法 五指山搜捕法 1 1 问题的背景和研究意义 1 1 问题的背景 有困难找警察 是家喻户晓的一句流行语 警察肩负着刑事执法 治安管理 交通管理 服务群众四大职能 为了更有效地贯彻实施这些职能 需要在市区的一些 交通要道和重要部位设置交巡警服务平台 每个交巡警服务平台的职能和警力配备基 本相同 由于警务资源是有限的 如何根据城市的实际情况与需求合理地设置交巡警 服务平台 分配各平台的管辖范围 调度警务资源成为警务部门面临的一个实际课题 1 2 文献综述 对于警察治安管理服务点 公共自行车停放场所 公交车站等场所布局安排和调 度问题 已经得到许多专家学者的关注研究 求解车辆路径调度问题的精确算法有动 态规划法 分支定界法 由于精确算法只能求解一些小规模问题 人们开始寻求并非 尽善尽美的所谓启发式算法 1 以求处理各种实际问题 上世纪 70 80 年代是启发式 方法的全胜时期 但由于绝大多数启发式方法都是按照某种确定性的收缩规则来进行 的 想要改进所得解的可能性几乎是零 80 年代后其他学科的新一代优化算法相继出 现 比如禁忌搜索算法 Tabu Search 简称 TS 源自生物学的遗传算法 Genetic Algorithms 简称 GA 人工神经网络算法 Artificial Neural Networks 简称 ANNs 以及 近几年来问世的蚁群算法 Ants Colony Algorithm 简称 ACA 等 2 林阳斌 3 基于图论 的知识 综合模糊数学和贪心算法给出了 110 警车分配区域巡逻问题的求解方法 其 中不少学者的研究方法对于本问题都适用 可以借鉴过来解决本问题 1 3 研究意义 对交巡警服务平台 以下简称服务台 的设置与调度问题的研究 有利于合理分配 现有服务台资源 发挥警察和服务台的最大效益 同时 对于公共自行车停放场所 公交车站等场所布局安排和调度具有借鉴推广意义 2 问题的提出和分析 对于第 1 问 对 A 城区内现有的 20 个巡警服务平台进行管辖区域划分 使得报案 发生后都有唯一的 最方便的服务台出警处理 并努力实现在 3 分钟内达到事发地点 在不考虑各服务台之间工作量的均衡性时 各节点所属辖区应是距离它最近的服务台 即基于距离最小原则分配各服务台管辖范围 在求解各节点之间最短距离之后 提出 两种 3 分钟到达模型 节点到达和线到达模型 从两个角度给出了各服务台的管辖范 围 线到达模型有效克服了高点到达率背后隐藏的道路空缺假象 对于第 2 问 调度 20 个服务台的警力快速全封锁进出 A 城区的 13 条交通要道 在明确各服务台和需要封锁路口的位置 距离等信息之后 实现服务台对路口的一一 对应封锁 实际上是一个匹配规划问题 求解本问题有两种思路 基于最长时间最 小的短板效应封锁模型 基于全局用时最少的封锁模型 最终给出基于短板效益 全局最优以及两者综合考虑的三个规划模型 供实际需要作选择 对于第 3 问 考虑到各服务台的工作量不均衡和部分地区出警时间过长等问题 通过增加服务台数目缓解这些问题 新服务台位置的选择分两步进行 根据出警时 2 间长度考虑增加服务台的数量并确定其位置 根据服务台工作量不均衡考虑新增服 务台并确定其位置 对于第 4 问 首先根据警察刑事执法 治安管理 交通管理 服务群众的四大职 责和现实情况建立以服务台平均覆盖面积 服务台平均管辖人口 3 分钟到达率 警 力分布均衡性为指标的模糊综合评判模型 利用加权平均型的模糊评判方法可以得到 模糊评价结果 随后对结果按照评分进行分级 从而得到评价结果 最后根据评价结 果 对评价较差的区域进行整改 对于第 5 问 考虑到犯罪嫌疑人逃跑方向的不确定性 无法预知下一时刻的逃跑 方向 所以需要对其实行快速封锁 本文在受到 孙悟空逃不出如来佛祖手掌心 这 一神话故事的启发后 提出 五指山 搜捕法 手掌 边界比孙悟空提前赶到即可捉 拿孙悟空 据此思想 本文对此围捕问题进行了简化求解 最终得到了最优的交巡警 调度方案 3 模型的假设 3 1 假设警车在执行任务时的行车时速度不受外界因素 包括堵车和红绿灯等 的影响 3 2 假设报案都发生在路口节点及短路所在路线上 其他地方的报案也近似到附近的节 点和道路 3 3 假设在发生重大安全事件是巡警服务平台只顾及到重大安全事件的处理 对于平 常报案事情暂停处理 3 4 假设每个巡警服务平台同时最多只能执行一次任务 同一服务台不会同时接到两起 出警任务 3 5 假设警车能规定时间内到达切片路段端点 认为警车在规定时间内到达该切片路段 任何一处 3 6 假设 1 个服务台警力就能实行对重要交通路口的封锁 其他服务台不需加强对路口 的封锁 3 7 假设报案中心接到报案后 各服务台能同时接到出警命令 4 符号说明 符号 符号说明 x y 任意节点的位置坐标 l 任意两节点之间的距离 w 任意两节点之间的最短路 xij 服务台 i 是否管辖路口节点 j wij 服务台 i 到路口节点 j 之间的最短距离 v 警车行驶速度 Tij 任意两节点间最短时间 Ri 模糊综合评价指标 注 其他符号见文中说明 3 5 模型的建立与求解 5 1 问题一模型的建立与求解 5 1 1 管辖范围分配模型 1 问题分析 在某市中心城区 A 的交通网络图和信息表中统计发现 共有 92 个路口节点 包括 13 个出入 A 城区的路口和 20 个巡警服务平台以及 143 条道路 包括出入 A 城区道路 为了应对各节点处发生突发事件后 马上会有服务台出警前往事发地点处理 需要对 A 城区内现有的 20 个巡警服务平台进行管辖区域划分 使得报案发生后都有唯一的 最方便的服务台出警处理 并努力实现在 3 分钟内达到事发地点 根据假设 3 1 警 车在执行任务时车速不受外界因素 包括堵车和红绿灯等 的影响 始终保持 60km h 的 速度前进 3 分钟车程相当于 3km 的路程 从假设 3 4 中 本文认为同一服务台不会 在同一时间接到两起出警任务 也就是说只要接到报案该服务台都能及时出警 不用 考虑不同服务台之间工作量的均衡性 为了达到这种要求 各节点所属辖区应是距离 它最近的服务台 能及时实现对突发事件的处理 即基于距离最小原则 2 数据处理 根据附件所提供某中心城区A的交通网络和现有的20个服务台的设置情况及相关 的数据信息 城区交通路口节点的坐标信息 再利用平面两点之间的距离公式 5 1 求出 A 城区内所有节点之间的距离 即 A 城区各路线的长度 据此分析 可绘得 A 城区交通路况详细信息如下图 5 1 所示 L 2 21 2 yyxxl jiij 5 1 不直接相邻节点 相邻节点 ji jil ji jiL ij 0 5 2 200250300350400450 260 280 300 320 340 360 380 400 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 3435 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 7071 72 73 74 75 76 77 78 79 80 81 82 83 84 8586 87 88 89 90 91 92 A区 图 5 1 某市中心城区 A 道路信息 4 建立各节点之间的直接距离矩阵 然后利用 Dijkstra 算法求解每个服务台与各节 点之间的最短距离矩阵 计算服务台至各节点之间的最短距离流程如下 4 L 9220X W Step1 k 1 取 0 11 vL 3 2 1 njvL j 取 min 11 1 AVAvAvLvL j Vvj 0 11 vvd Step2 对于1 kkAvj 令 min 11jkjkjk vvvLvLvL min 2 vAAvAAvLvL j Avj k 取 1 vLvvd k Step3 若 D 中至 1 vvd 1 vA的路径不存在 算法终止 Step4 若 则输出最短路径长度 算法终止 否则转 Step2 nk 1 vvLn 3 建立模型 1 模型 点到达模型 开始 j 1 i1 i2 0 取第j个节点最短距离 d min w i j 最小距离对应服务台i 图 5 2 各服务台的管辖节点分配流程图 基上述Dijkstra算法求解出的各服务台与各道路路口节点之间的最短距离 9220X W 点到达率a i1 i1 i2 结束 i2 i2 1 节点j 属服务台i管辖 i1 i1 1 节点j 属服务台i管辖 d 3 j j 1 j 92 YN N Y 5 然后建立各节点与服务台之间匹配的模型 利用 Matlab 整理路程数据时发现 某些节 点到达任何服务台的最短路径都大于警车 3 分钟的车程 所以本文对于各路口节点的 管辖分配分两步进行 到达服务台最短路径小于 3 分钟车程的路口节点管辖分配 到达服务台最短路径大于 3 分钟车程的路口节点管辖分配 各服务台的管辖节点分 配流程图如上图 5 2 利用上述流程算法 按照最小距离原则 对各节点所属服务台管辖进行划分 划 分结果如下表 5 1 表 5 1 点到达模型的服务台管辖分布情况表 服务台 管辖路口节点 服务台管辖路口节点 1 1 67 68 69 71 73 74 75 76 7811 11 26 27 2 2 40 43 44 70 72 39 3 68 12 12 25 3 3 54 55 65 66 13 13 21 22 23 24 4 4 57 60 62 63 64 14 14 5 5 49 50 51 52 53 56 58 59 15 15 28 4 75 29 5 70 6 6 16 16 36 37 38 3 41 7 7 30 32 47 48 61 4 19 17 17 41 42 8 8 33 46 18 18 80 81 82 83 9 9 31 34 35 45 19 19 77 79 10 10 20 20 84 85 86 87 88 89 90 91 92 3 60 注 括号内数字表示到达对应节点所需要的最短时间 从表 5 1 中可以得出如下结论 各路口节点在发生突发事情后 巡警服务平台出 动警车前往 在 3 分钟内能达到的节点有 86 个 点到达率为 93 48 其中 只有 28 29 38 39 61 和 92 号节点发生突发事件 服务台在接警后 3 分钟内不能到达 达 到节点需要的最长时间是 5 70 分钟 服务台达到各节点的平均时间为 1 12 分钟 基 本满足对于各节点发生突发事件后 3 分钟到达事发地点的要求 同时 对于出入 A 城 区的 13 个交通路口中 28 29 38 号路口节点警车最快到达时间分别为4 75 5 70 3 41分钟 不能及时赶到该处处理突发事件 给犯罪分子逃脱提供了时间空缺 是警 察治安管理上的一个漏洞 2 模型 线到达模型 考虑到实际生活中 各种突发事件不一定都发生于路口节点或在路口节点报案 模型 仅仅考虑到 3 分钟内警车能到达所在的节点 并未考虑到突发事件发生于节点 中间的路段情形 继而 本文在点到达模型的基础之上 研究了线到达模型 主要思 想是将道路离散化为点 再用离散化的点代表道路线段 问题研究目标是警车尽量 3 分钟之内到达 本文以时间间隔 0 5 分钟 车程 500m 为研究对象 将各道路切片离散 为 500m 的路段 结合假设 3 5 只要警车在规定的时间范围内到达路段的任何一处 本文认为警车能规定的时间内到达该路段任何一处处理突发事件 将道路切片离散化 的流程如下 Step1 计算当前道路长度 并与警车0 5分钟车程比较 若 大于则转入Step2 否则转入Step5 ldld Step2 依据下式 5 3 的计算公式 计算出需要插入的点的坐标 转入Step3 Step3 将新加的点插入到存放坐标的数组末端 转入Step4 Step4 将原来的边从边集合移除 并加入两条新的边 转入Step5 6 Step5 判断是否还存在长度大于的边 若有转入Step1 否则退出 d 设新产生点的坐标 与其左右相临的两点坐标为和 到 的距离为 则根据相似三角形的性质可得点的坐标为 yxB 111 A x y 222 A xy 1 A 2 Al yxB 1 12 1 12 y l yyd y x l xxd x 5 3 200250300350400450 260 280 300 320 340 360 380 400 1 7 2 1 2 2 1 7 2 1 2 5 2 4 2 4 2 1 1 6 2 6 2 4 2 2 2 5 2 1 2 6 2 5 1 9 1 8 1 9 1 4 1 4 2 4 1 1 1 6 1 2 0 8 1 3 1 4 2 1 1 6 1 5 1 4 1 71 4 1 1 0 1 1 2 1 4 1 7 1 4 1 4 1 7 1 1 1 4 1 2 1 6 1 4 1 2 1 1 0 8 0 6 1 4 0 9 1 0 5 0 8 1 1 0 9 0 7 0 6 1 2 1 4 0 8 0 7 0 8 0 8 0 9 1 1 0 91 1 0 8 0 9 1 1 0 8 1 1 0 8 0 8 0 8 0 8 1 4 1 1 0 9 1 1 21 4 1 1 0 9 1 4 0 9 0 9 0 8 A区道路切片离散图 图5 3 A城区道路切片离散图 对A城区进行切片操作后 共离散化为330个节点 包括已有的92各路口节点 计算服务台到各节点之间的最短距离参照5 1 1数据处理 各服务台辖区节点分配远侧 参照5 1 1模型 得到20各服务台的管辖节点情况如下表5 2 表 5 2 线点到达模型的服务台管辖分布情况表 服务台所在节点 管辖路口节点 1 1 67 68 69 71 73 74 75 76 78 93 310 311 317 319 2 2 40 43 44 70 72 94 250 251 252 253 312 313 39 249 3 3 54 55 65 66 98 99 100 101 102 103 262 267 268 282 283 287 4 4 57 60 62 63 64 107 108 109 110 111 112 284 285 286 289 290 291 296 297 298 299 300 301 302 309 104 105 106 293 294 295 303 5 5 49 50 51 52 53 56 58 59 272 273 278 279 280 281 288 6 6 113 114 270 271 7 7 30 32 47 48 115 116 145 146 147 224 225 226 227 228 237 238 239 240 269 274 275 276 61 216 217 218 219 220 221 222 223 277 292 8 8 33 46 118 119 120 263 264 265 266 9 9 31 34 35 45 95 96 97 117 126 127 128 129 229 230 7 10 10 121 122 123 124 125 196 197 198 199 11 11 26 27 132 133 134 191 192 193 194 195 204 12 12 25 135 136 190 200 201 202 203 13 13 21 22 23 24 130 131 183 184 185 186 187 188 189 14 14 137 138 139 140 141 153 154 155 156 157 158 15 15 142 143 144 148 149 150 151 152 209 210 211 212 213 28 29 205 206 207 208 214 215 16 16 36 37 160 161 162 163 164 165 166 167 168 169 170 231 232 233 234 241 38 159 235 236 242 17 17 41 42 171 172 173 174 175 176 177 178 179 245 246 247 248 254 255 256 257 243 244 258 259 260 18 18 80 81 82 83 180 181 182 314 315 316 318 321 19 19 77 79 320 20 20 84 85 86 87 88 89 90 91 304 305 306 307 308 322 323 325 326 327 329 330 92 261 324 328 注 括号内节点表示距服务台最短距离超过警车 3 分钟车程的节点 其中 还有42个切片节点距离服务台的距离超过警车3分钟车程 只能利用距离 最近的巡警服务平台来管辖 利用线到达模型计算出的线到达率为87 27 相对于模 型 的点到达率93 48 从表象上来看降低了 但是点到达模型的到达率是以点的数 目为单位进行计量的 线到达模型是以道路长度为计量单位 更真切地反映了服务台 对A城区的整体覆盖情况 意义更现实 线到达模型有效克服了高点到达率背后隐藏 的道路空缺假象 同样 对于出入A城区的28 29 38号路口节点不能有效 及时 的控制 5 1 2 快速全封锁模型 1 问题分析 对于A城区发生重大突发事件 需要调度全区20个交巡警服务平台的警力资源 对进出该区的13条交通要道实现快速全封锁 结合假设3 4 一个平台的警力同时最 多执行一次任务 封锁一个路口 对于各服务台接到封锁所有进出A城区的路口任务 后 首先需要确定的是各服务台封锁的路口位置及距离等信息 使得每个路口都有一 个唯一的服务台去封锁 而不导致出现某些进出路口有2个或2个以上服务台封锁 而某些进出路口没有服务台负责封锁 结合假设3 6 每个重要交通路口只需要一个服 务台的警力封锁 本问题转化为一个从20个服务台中选择13个服务台对13个进出A 城区路口进行封锁的最佳匹配问题 求解本问题有两种思路 基于最长时间最小的 短板效应封锁模型 基于全局用时最少的封锁模型 最终给出基于短板效益 全局 最优以及两者综合考虑的三个规划模型 2 建立模型 1 模型 基于短板效应的封锁模型 短板效益是指一只水桶想盛满水 必须每块木板都一样平齐且无破损 如果这只桶 的木板中有一块不齐或者某块木板下面有破洞 那么这只桶就无法盛满水 也就是说 一只水桶能盛多少水 并不取决于最长的那块木板 而是取决于最短的那块木板 同 本问题相似 要求对进出A城区的所有道路实行快速封锁 封锁效益取决于服务台到 达路口耗时最长的那次封锁 首先 从5 1 1数据处理中建立的各节点到服务台的最短距离矩阵中获取13个进 8 出A城区的路口和20个服务台之间的最短距离矩阵 除以警车行驶速度得到重 要交通路口与服务台之间的时间矩阵 然后 建立如下规划模型 2013X D 2013X T 目标分析 封锁所有进出 A 城区的交通路口最长时间最小 约束分析 每个交通要道路口都有对应服务台出动警车实行封锁 选择的执行封锁任务的 13 个服务台各封锁一个路口 服务台与路口之间的 0 1 匹配关系 将上述描述转化为数学模型如下 max min 1ijijT xT 5 4 1 0 13 1 1 13 1 20 1 13 1 20 1 ij ij ij i ij j ij xij x xj xi ts 5 5 2 模型 基于全局用时最少的封锁模型 针对快速全封锁的不同理解 可以认为是对全局的快速封锁 即封锁所有总时间 最短 据此建立第二个规划模型 目标分析 封锁所有进出 A 城区的交通路口所用总时间最少 约束分析 每个交通要道路口都有对应服务台出动警车实行封锁 选择的执行封锁任务的 13 个服务台各封锁一个路口 服务台与路口之间的 0 1 匹配关系 将上述描述转化为数学模型如下 13 1 20 1 2 min ij ijijT xT 5 6 1 0 13 1 1 13 1 20 1 13 1 20 1 ij ij ij i ij j ij xij x xj xi ts 5 7 3 模型 基于最大用时较小和全局用时较少的双目标规划模型 在分析上述两个模型的过程中 本文认为在实际过程中在处理类似的较大问题时 9 不能仅从单一的目标进行考虑 综合考虑着两个因素的使用价值更大 因此建立如下 双目标规划模型 max min 1ijijT xT 13 1 20 1 2 min ij ijijT xT 利用线性加权法将双目标转化为单目标 2 13 1 20 1 1 1 max min T Tx T Tx ij ijij ijij 5 8 1 0 13 1 1 13 1 20 1 13 1 20 1 ij ij ij i ij j ij xij x xj xi ts 5 9 3 模型求解 利用 Lingo 软件编程 程序代码见附录 求解该模型 取5 0 得到以下结果 表 5 3 对进出 A 城区路口封锁的服务台调度方案 出入城区路口节点 短板效益模型 全局用时最少模型 双目标规划模型 12 12 12 12 14 16 9 16 16 9 16 9 21 14 14 14 22 10 10 10 23 13 13 13 24 11 11 11 28 15 15 15 29 7 8 7 30 8 7 8 38 17 2 2 48 6 5 5 62 4 4 4 最大用时值 分钟 8 015 10 493 8 015 用时均值 分钟 3 615 3 553 3 553 结合 A 城区地形图和上表 5 3 可以得知三种模型各有优劣 短板效益模型封锁的 最大时间最短 实现了最快速的全局封锁 但是平均用时最大多 从地形图上可以看 出部分出入口节点原本就有服务台 但是各服务台协同合作为了实现最大时间最短 10 该处服务台警车并不封锁自己的出入口 在实际应用中值得商榷 全局用时最少模型 所得到的平均用时明显比短板效应模型要小 但是最大用时远远超过了短板效应模型 而综合考虑最大用时最小和平均用时最少的双目标规划模型很好的融合了前两者的优 点 避免了各自的缺点 实现了最大用时同短板效应模型一样小 平均用时同全局用 时最少模型一样少 在实际应用中更有价值意义 5 1 3 新增服务台优化模型 1 问题分析 前述研究中 问题1和问题2都是针对突发事件进行处理的 并未考虑到各服务 台的日工作量 从表5 1和表5 2中就可以明显看出服务台管辖的不均衡性和部分地区 出警时间过长等问题 为此 拟新增2到5个新服务台以解决这些问题 并确定这些 新增服务台的位置 新增服务台后 可能需要对之前的服务台管辖范围进行调整 同 时结合实际 本文认为不应该对A城区内的所有服务台管辖范围进行大的调整 求解该问题可以分为两步 根据出警时间长度考虑增加服务台的数量并确定其 位置 根据服务台工作量不均衡考虑新增服务台并确定其位置 在结合5 1 1的基础 之上 部分服务台到达节点的时间远远超过3分钟 为了尽量满足服务台到达每个节 点时间在3分钟以内 对于出警时间较长的节点 特别是重要的交通路口附近可以考 虑新增服务台 其次明确工作量的含义 本文定义服务台的工作量为相对日接报案数 量总和 对于工作量特别大地服务台 为了均衡各服务台之间的工作量 可以考虑在 工作量较大的服务台附近新增一个服务台 以缓解该台的工作量 并分析新增后各台 工作量的均衡性 然后再选取工作量较大的服务台 在其附近同样新增一个服务台 同上分析新增后各服务台的工作量均衡性 以此类推 一次增加一个服务台 直到增 加若干个服务台后达到理想的效果为止 2 按优先级的新增服务台逐层目标规划模型 在实际生活过程中 警察肩负着刑事执法 治安管理 交通管理 服务群众的职 能 警察能否有效 及时的赶到案发地点处理突发事件 增加人们的安全感 对于警 察来说是最为重要的 在城区内任何一处的出警时间都到达要求后 保证了人民生命 财产安全的前提下 才能进一步考虑各服务台工作量的均衡 1 按出警时间长短安排新增服务台 结合 5 1 1 所分配的各服务台管理辖区 发现部分节点的出警时间超过 3 分钟 其中部分节点出警时间甚至超过 4 分钟 对于维护警察在人民群众心中神圣职能造成 了极大地负面影响 为此需要筛选 A 城区内出警时间过长的节点 以 4 分钟出警时间为 限制 继而新增服务台 新增服务台选址筛选流程如下图 5 5 利用下述流程图对 5 1 1 中各节点按照出警时间进行筛选 安排新的服务台 最 终确定在 29 和 61 号道路节点出新增两个服务台 尽量满足各路口节点的出警时间在 3 分钟附近 不超过 4 分钟 利用 5 1 1 线到达模型计算得到新增 29 61 号节点服务 台 使得线到达率增加至 92 42 不同服务台之间的相对工作量的方差为 0 2188 相 对于未增加这两个服务台 87 27 的线到达率和 0 2339 的相对工作量方差 表明新增 这两个服务台对于缩短最长出警时间和均衡各服务台之间工作量具有一定意义 11 开始 图 5 4 按出警时间长短安排新增服务台筛选流程图 2 按工作量均衡安排新增服务台 在新增 29 和 61 号服务台后 并没有改变 5 1 1 中制定的管辖分区中存在的各服 务台工作量的不均衡性 为了协同各服务台之间的工作量 需要对工作量特别大或者 工作量很小的服务台进行调整 在基于调整幅度尽量小的原则下 本文对于工作量很 小的服务台不作调整 只是针对工作量相对特别大的服务台进行调整 调整主要依靠 增加新的服务台共同承担其工作量 并少量改变其附近的节点的所属管辖范围 由于附件提供的发案率只是各节点处的 而下文研究的工作量是基于 A 城区内所 有道路离散化的切片点 因此 需要对相邻节点之间道路上的离散化切片点的工作量 进行定义 假设某道路中间有个切片点 路端两节点的发案率分别是 如图 5 5 n 21 a a 图 5 5 某条切片道路实例分析图 对于 A 城区内各道路进行切片分析后 大部分道路进行了切片 按照 5 1 1 线到 达模型计算到达率 并统计各服务台的工作量时 需要对切片点处的发案率进行分析 补充 切片点处的发案率按照下式 5 10 计算 i n aa aia 1 12 1 5 10 j j 1 记录下节点j 出警时间 取j节点出警时间 t和位置信息 t 4 j 9 j 1 Y Y N N 取2个记录节点 计算距离s 2节点中有 无服务台 以1节点为 新台位置 N Y 2节点归属 1服务台 s v long 1 ntmp 1 D ntmp 1 V 1 i v 1 V i ntmp 1 end long 1 V i min long 1 V i long 1 ntmp 1 D ntmp 1 V 1 i end end 附程序2 点 线 到达模型分配服务台管辖范围程序 function LL tmp zuiduanlu clc clear lingjie xlsread cumcm2011B附件2 全市六区交通网路和平台设置的数据表 xls 全市交通路 口的路线 A2 B144 Loc xlsread cumcm2011B附件2 全市六区交通网路和平台设置的数据表 xls 全市交通路口节 点数据 B2 C93 R xlsread cumcm2011B附件2 全市六区交通网路和平台设置的数据表 xls 全市交通路口节点 数据 E2 E93 churu 12 14 16 21 22 23 24 28 29 30 38 48 62 jiadian juli Rtmp fengge lingjie Loc R R Rtmp idx find lingjie 2 92 lingjie idx n0 size lingjie 1 lingjie lingjie juli 93 end 1 2 点线到达模型 Loc Loc jiadian 93 end 22 num size Loc 1 求交巡警服务平台到个点的最短路 L L road lingjie Loc LL zeros 20 num 两点间的最短路 vv zeros 20 num 前向节点 for i 1 20 LL i vv i dijkstra L i end 做路径图 for i 1 n0 xa Loc lingjie i 1 1 ya Loc lingjie i 1 2 xb Loc lingjie i 2 1 yb Loc lingjie i 2 2 plot xa xb ya yb b hold on end 标注出入A区的点 for i 1 length churu plot Loc churu i 1 Loc churu i 2 r MarkerSize 8 end 标注交巡警服务平台及各节点 plot Loc 1 92 1 Loc 1 92 2 ks MarkerSize 4 MarkerFaceColor b hold on plot Loc 1 20 1 Loc 1 20 2 rO MarkerSize 10 hold on 对管辖范围进行分配并将其管辖范围标注在图上 guanxia1 guanxia2 huafen LL fenqu guanxia1 guanxia2 Loc text 412 390 A区部分 FontSize 20 end 对线段进行划分 function jiadian juli Rr fengge lingjie Loc R n size Loc 1 idx lingjie 2 n lingjie idx Rr R 案发率 L L road lingjie Loc r 5 分割步长 23 k n 1 j n 1 for i 1 length lingjie L1 lingjie i 1 L2 lingjie i 2 Ltmp L L1 L2 x2tmp Loc L1 1 y2tmp Loc L1 2 x3tmp Loc L2 1 y3tmp Loc L2 2 theat atan Loc L1 2 Loc L2 2 Loc L1 1 Loc L2 1 q floor Ltmp r jj 1 while Ltmp r 4 if x2tmpr 4 if Loc L1 1 Loc L2 1 24 juli j k 1 L2 Ltmp j j 1 else juli j k 1 L1 Ltmp j j 1 end end end end 管辖范围的划分 function guanxia1 guanxia2 huafen LL N size LL 2 idx zeros 1 N guanxia1 zeros 20 100 num1 ones 20 1 guanxia2 zeros 20 100 num2 ones 20 1 for i 1 N if min LL i 30 idx i find LL i min LL i guanxia1 idx i num1 idx i i num1 idx i num1 idx i 1 else idx i find LL i min LL i guanxia2 idx i num2 idx i i num2 idx i num2 idx i 1 end end n length find guanxia1 0 r n N end 做分区图 function fenqu guanxia1 guanxia2 Loc for i 1 20 j 1 while guanxia1 i j 0 text Loc guanxia1 i j 1 1 Loc guanxia1 i j 2 num2str i FontSize 11 j j 1 25 end j 1 while guanxia2 i