110警车配置及巡逻方案

Distribution of 110 Police Wagon and The Patrol Scheme

针对110警车调度问题，引入了图论中的最短路算法以及计算几何的相关理论，建立了车辆调配模型、巡逻路线模型以及基于模糊数学的评价指标模型．另外，用C＋＋编写了一个可视化的软件，不仅实现了手动描点，自动求出覆盖线段集合的功能，同时利用计算机模拟警车的巡逻路线，最后通过计算机检验得到结果，其合理性和实用性都令人满意．针对问题一，通过人机结合，配置17辆警车就能实现D1的目标，很好地兼顾了警车巡逻的运行成本，减少公安部门车辆和人员等的投入．针对问题二，采用模糊数学相关理论使评价指标实现了从定性到定量的转变．针对问题三和六，在D1的基础上，兼顾了巡逻效果的显著性，采用最少被巡逻道路优先的贪心算法建立了动态巡逻模型，得到了合理的巡逻方案．在此方案中，我们动用了30辆警车完成了问题一的目标．另外还额外考虑了案发事件概率不均匀分布的情况，建立了改进模型．针对问题四，在完成问题三指标的基础上，为了尽可能提高巡逻车辆的隐蔽性和增强巡逻效果，采用轮盘赌算法来引入随机性．针对问题五，采用最远距离道路优先贪心策略，使模型尽可能满足条件D1，D2．针对问题七，提出了一些额外因素及其解决方案，进一步完善了模型，使模型更贴近现实．

This paper mainly researches into the problem of 110 police car scheduling through using the shortest path algorithm of graph the.ory and some relevant theories of computational geometry. We establish the deployment model of the car, the patrol route model and the evaluation model based on fuzzy mathematics. In addition, we program a visual soft by C＋＋ to get the results. It not only realizes tracing point manually and gets the covering segment sets automatically but also can simulate cars＇ patrol routes to obtain the result. And the result is valid and practical. Firstly, we use human-computer cooperation to solve problem 1 and the result is 17 cars to satisfy condition D1. It gives consideration to the operations costs to reduce the number of cars and people. Secondly, we use evaluation model to achieve the change from quality to quantity solve problem 2. Thirdly, for problem 3 and problem 6, taking account of the significance of patrol effects, we build dynamic patrol model based on D1 using greedy algorithm with the priority of the least patrolled road. And we obtain a reasonable patrol scheduling scheme. In this scheme, we use 30 cars to realize the object of problem1. Moreover, we make some modification on the previous model by considering the condition of uneven distribution of the incident event probability. For problem 4, we add randomness by using roulette algorithm for improving the imperceptibility and enhancing the patrol effects. For problem 5, we apply the most long distance road priority greedy policy to meet condition D1.D2 as much as possible. At last, we propose some extra factors and corresponding solutions for making the model closer to reality.