警车配置及巡逻方案研究

以警车的配置与巡逻方案为研究对象,建立了一套警车巡逻模型,并提出巡逻效果显著度及隐藏性的评价标准,分别针对警车初始位置配置与巡逻方案的制定,提出警车配置优化选址的贪婪算法与基于多Agent的警车巡逻方案设计方法,给出了不同情景下的配置及巡逻方案:①在只考虑警车选址配置的情况下,配置19辆警车可以使全市路网警车覆盖率达到92.8%;②在顾及巡逻效果显著性与隐藏性的情况下,配置25辆警车使全市路网在整个巡逻过程中平均警车覆盖率达到90.9%;③在配置10辆警车的情况下,使得全市路网在整个巡逻过程中平均警车覆盖率达到61.5%.     

Contributions to a Theory of Patrol Scheduling

The problem considered in this paper is that of scheduling police patrols in a random pattern. This involves generating patrol routes as well as schedules for dispatching patrol vehicles. A solution to this problem is obtained by specifying minimum average patrol requirements on each route segment in a network and then developing a procedure which meets these requirements while minimizing the total patrol effort. Introducing vehicles into the network in a Poisson stream results in Poisson streams in each route segment and so ensures that an observer cannot use previous history for predicting arrival patterns. This solution also has the property that the number of patrol cars in the network is a Poisson random variable for which the steady-state can be achieved immediately. The steady-state distribution function is also used to determine the number of patrol cars required.     

A 2D chaotic path planning for mobile robots accomplishing boundary surveillance missions in adversarial conditions

The path-planning algorithm represents a crucial issue for every autonomous mobile robot. In normal circumstances a patrol robot will compute an optimal path to ensure its task accomplishment, but in adversarial conditions the problem is getting more complicated. Here, the robot’s trajectory needs to be altered into a misleading and unpredictable path to cope with potential opponents. Chaotic systems provide the needed framework for obtaining unpredictable motion in all of the three basic robot surveillance missions: area, points of interests and boundary monitoring. Proficient approaches have been provided for the first two surveillance tasks, but for boundary patrol missions no method has been reported yet. This paper addresses the mentioned research gap by proposing an efficient method, based on chaotic dynamic of the Hénon system, to ensure unpredictable boundary patrol on any shape of chosen closed contour.     

A note on the square root law for urban police travel times

The classical Square Root Law formula for emergency travel times consists of one observable component, the density of patrol coverage, and one unknown component that must be estimated empirically, the effective travel speed. The effective travel speed is typically assumed to be an empirical constant. We test whether this simplifying assumption is justified empirically. We propose a modern machine-learning approach and a Least Absolute Shrinkage and Selection Operator regression to incorporate into a travel speed model various exogenous factors such as call type, incident location, weather conditions and traffic congestion. The value of the proposed analytical approach and some practical implications are demonstrated using operational data from a large urban police jurisdiction based in British Columbia, Canada. Although the analysis is framed within the context of urban emergency police operations, the proposed approach has the potential to be useful for other emergency services or roving business units that deal with unscheduled service calls.     

基于时间切片叠加的警车巡逻路线规划

在城市中,有效的安排警车巡逻对于降低犯罪率,预防潜在犯罪案件发生和及时处理案件具有十分重要的意义.通过一些必要简化首先确定了巡逻方案应当满足的条件以及方案的评价体系.通过随机贪心算法求解足够多的可行静态解,并引入时间片叠加的思想在静态解的基础上应用深度优先搜索算法,将求解动态巡逻问题转化为在有向连通图中寻找使目标函数达到最大的约束环路的问题,最终求得动态巡逻方案.最后,通过实例对模型进行了验证和评价.     

Modelling Rural Police Patrol

Police patrol has been modelled extensively in the urban environment, but these urban models cannot usually be applied to rural settings. The length of travel times and the nature of calls for service in rural, wide-area, low-population regions demand special consideration. In this paper, we develop a Markov model that explicitly incorporates travel times and priority calls to analyse police patrol policies in rural areas. Results of the model using data from Washtenaw County, Michigan, USA, are given to show its utility.     

Location-allocation models for traffic police patrol vehicles on an interurban network

This research investigates the traffic police routine patrol vehicle (RPV) assignment problem on an interurban road network through a series of integer linear programs. The traffic police RPV’s main task, like other emergency services, is to handle calls-for-service. Emergency services allocation models are generally based on the shortest path algorithm however, the traffic police RPV also handles other roles, namely patrolling to create a presence that acts as a deterrence, and issuing tickets to offenders. The RPVs need to be located dynamically on both hazardous sections and on roads with heavy traffic in order to increase their presence and conspicuousness, in an attempt to prevent or reduce traffic offences, road accidents and traffic congestion. Due to the importance of the traffic patrol vehicle’s location with regard to their additional roles, allocation of the RPVs adheres to an exogenous, legal, time-to-arrival constraint. We develop location-allocation models and apply them to a case study of the road network in northern Israel. The results of the four models are compared to each other and in relation to the current chosen locations. The multiple formulations provide alternatives that jointly account for road safety and policing objectives which aid decision-makers in the selection of their preferred RPV assignments. The results of the models present a location-allocation configuration per RPV per shift with full call-for-service coverage whilst maximizing police presence and conspicuousness as a proxy for road safety.     

Queueing models for police-fire merger analysis

Cities with under 100,000 in population expend a significant portion of their budgets on emergency services. One option that a number of these cities have considered for improving service and cutting costs is training personnel to handle both police and fire roles. In this paper we describe a hierarchy of models that we have used to assess the performance viability of a merger as well as to design specific deployment plans. The modeling environment is more complex than a traditional police or fire system. We need to model the response pattern of four or more patrol units along with the simultaneous dispatch of fire equipment from one or more fire stations. The major contribution of the paper is the manner in which a series of models is linked together to forecast a wide range of performance measures under differing dispatch assumptions. We use a queueing model of police patrol to calculate steady state probabilities and expected delays without preemption. We then model two types of preemptive dispatch strategies utilized in responding initially to a major fire by superimposing a binomial distribution on the basic queueing model. There is also a travel time simulation model to calculate conditional expected response time statistics. The queueing models and the travel time simulation are then combined to estimate unconditional expected values. Lastly, we describe a simulation model used to address transient performance issues that are of concern during a major fire.     

On the validity and utility of queueing models of human service systems

Based on observations made during an extensive study of police patrol operations in New York City, we examine the issues of the validity and utility of queueing models of service systems in which adaptive behavior by the (human) customers or servers is likely. We find that in addition to depending on the technical accuracy of its assumptions, the accuracy of such a model will also depend upon the level of managerial control of the system and adequacy of resources. We recommend that queueing models of human service systems be used in a normative fashion and incorporated in the management feedback loop.     

Models for Allocating Police Preventive Patrol Effort

This paper develops models that maximize the expected number of occasions per unit of time that a police patrol unit enters a street segment during the time that a crime is visible. Constraints are added that insure a minimum patrol coverage to all streets. The successive visits from street-to-street form a Markov chain. The solution that maximizes the objective function gives a stochastic decision rule which is used with Monte Carlo techniques to generate a random patrol schedule. The problem is posed with one car and several cars patrolling the same region.     

Optimizing State Patrol Manpower Allocation

One of the most difficult tasks of state highway patrol administrators is allocation of manpower; i.e. determining the most effective level of operational manpower for patrol tasks. Typically, administrators resolve the allocation problem by relying on prior statistical data and by employing subjective analysis. In general, only limited systematic analyses have been applied to the problem. This paper presents an integer goal programming model for allocating highway patrolmen to road segments within a patrol region. The model is demonstrated via a case example of the Nebraska State Patrol. The results of the model are valuable to the patrol administrator for considering departmental goals and priority structure, in addition to available historical data, in the assignment of state patrol manpower.     

考虑占位决策的围堵嫌犯模型

研究了2011年中国大学生数学建模竞赛B题的突发事件中交巡警对在逃嫌犯的围堵问题。不同于对该问题的以往的研究,本文考虑了交巡警在包围圈中可以占据某些路口,使得嫌犯不能通过这些被交巡警占据的路口,从而为形成包围圈的交巡警赢得更多时间。利用两篇相关文献的关于点截集判断的结论和考虑占位决策的建模方法,以不同的目标函数建立了考虑占位决策的围堵嫌犯问题的三个混合0-1非线性整数规划模型。通过选取部分线性约束和目标函数一起组合成混合0-1线性整数规划模型,设计了基于混合0-1线性整数规划方法的算法,并给出了算例。     

Fuzzy resource management analysis

Traditionally, the efficient and productive delivery of services is a major goal of public institutions. This is especially true in the law enforcement industry. Here, the management of a set of dynamic resources (police patrol personnel) is central to the delivery of services. In the past there have been two major perspectives towards the management of low enforcement resources: first, ignoring all patterns in demands resources are distributed equally across time and space. Second, resources are deployed according to the proportionate distribution of demands. In both of these models the resources are manipulated or controlled according to an algorithm derived independently from demand patterns. These models are highly vulnerable to shifts in demand patterns and can be strategically inefficient and tactically unstable. In this paper a new algorithmic process is defined for the strategic and tactical evaluation of resource needs for police patrolling which combines deployment and control strategies, and simulates combinations of the strategies for comparative analysis. It was discovered that the degree of reliance upon the analysis of future resource usage and the accuracy of the projection of the future demands had a significant impact on the performance of the methodologies studied. This process can be used to draw general conclusions about patrolling systems.     

面向突发事件的安保巡逻选址-路径优化研究

安保巡逻任务要求以中心会场为保卫目标,进行指挥中心的选址、巡逻线路的规划。考虑区域环境、安保主体及突发事件对巡逻线路优化的影响,依据警方安保任务的规划流程,建立了多约束条件下安保指挥中心选址-巡逻路径规划的优化模型。设计了基于真实安保区域特征的安保中心模拟试验,各区域由专家依据CPTED理论进行评定分级,利用遗传算法求解并对结果进行了模拟检验,提出了基于整体应急水平最优的安保巡逻策略。     

最小封堵圈的扩张算法设计

在发生突发事件之后,及时制定有效的封堵方案才能掌握抓捕嫌疑犯的主动权.提出了对逃跑罪犯实施完全封堵的最小包围圈的计算机算法,通过规则图形的仿真演示,验证了该算法的正确性.最后以某市案发时候的警力分布和交通图作为实例,模拟了对嫌疑犯实施封堵时计算最小包围圈的最优方案.结果证明该算法具有简洁、可靠的优点.     

110警车配置及巡逻方案

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

Scheduling patrol boats and crews for the Royal Australian Navy

The Royal Australian Navy's Patrol Boat Force carries out essential tasks in the surveillance, policing and defence of Australia's coastal waters. To help the Navy make efficient use of a new generation of boats, the authors have developed optimization procedures to schedule the activities of the boats and their crews. The procedures—embodied in a software system called CBM (‘Crews, Boats, Missions’)—use simulated annealing and specialized heuristic techniques within a multi-stage problem-solving framework. Tests show that CBM is reliable in terms of solution quality, and flexible with respect to the range of scheduling conditions applied. CBM has proved valuable to the Navy as an investigatory tool, and it is planned that it should be adapted for operational use, as part of a decision support system to aid in the ongoing management of patrol boat operations.     

Judgement and supply chain dynamics

Forecasting demand at the individual stock-keeping-unit (SKU) level often necessitates the use of statistical methods, such as exponential smoothing. In some organizations, however, statistical forecasts will be subject to judgemental adjustments by managers. Although a number of empirical and ‘laboratory’ studies have been performed in this area, no formal OR modelling has been conducted to offer insights into the impact such adjustments may have on supply chain performance and the potential development of mitigation mechanisms. This is because of the associated dynamic complexity and the situation-specific nature of the problem at hand. In conjunction with appropriate stock control rules, demand forecasts help decide how much to order. It is a common practice that replenishment orders may also be subject to judgemental intervention, adding further to the dynamic system complexity and interdependence. The system dynamics (SD) modelling method can help advance knowledge in this area, where mathematical modelling cannot accommodate the associated complexity. This study, which constitutes part of a UK government funded (EPSRC) project, uses SD models to evaluate the effects of forecasting and ordering adjustments for a wide set of scenarios involving: three different inventory policies; seven different (combinations of) points of intervention; and four different (combinations of) types of judgmental intervention (optimistic and pessimistic). The results enable insights to be gained into the performance of the entire supply chain. An agenda for further research concludes the paper.     

A patient adaptable ECG beat classifier based on neural networks

A novel supervised neural network-based algorithm is designed to reliably distinguish in electrocardiographic (ECG) records between normal and ischemic beats of the same patient. The basic idea behind this paper is to consider an ECG digital recording of two consecutive R-wave segments (RRR interval) as a noisy sample of an underlying function to be approximated by a fixed number of Radial Basis Functions (RBF). The linear expansion coefficients of the RRR interval represent the input signal of a feed-forward neural network which classifies a single beat as normal or ischemic. The system has been evaluated using several patient records taken from the European ST-T database. Experimental results show that the proposed beat classifier is very reliable, and that it may be a useful practical tool for the automatic detection of ischemic episodes.     

Locality and bounding-box quality of two-dimensional space-filling curves

Space-filling curves can be used to organise points in the plane into bounding-box hierarchies (such as R-trees). We develop measures of the bounding-box quality of space-filling curves that express how effective different space-filling curves are for this purpose. We give general lower bounds on the bounding-box quality measures and on locality according to Gotsman and Lindenbaum for a large class of space-filling curves. We describe a generic algorithm to approximate these and similar quality measures for any given curve. Using our algorithm we find good approximations of the locality and the bounding-box quality of several known and new space-filling curves. Surprisingly, some curves with relatively bad locality by Gotsman and Lindenbaum's measure, have good bounding-box quality, while the curve with the best-known locality has relatively bad bounding-box quality.