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.     

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

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

Patrol scheduling in urban rail network

This paper presents the problem of scheduling security teams to patrol a mass rapid transit rail network of a large urban city. The main objective of patrol scheduling is to deploy security teams to stations of the network at varying time periods subject to rostering as well as security-related constraints. We present several mathematical programming models for different variants of this problem. To generate randomized schedules on a regular basis, we propose injecting randomness by varying the start time and break time for each team as well as varying the visit frequency and visit time for each station according to their reported vulnerability. Finally, we present results for the case of Singapore mass rapid transit rail network and synthetic instances.     

Beat patrolling in urban areas A case study

Urban police patrol work has been analysed in the present paper. Working on the crime-rate, as reported by the police department, a plan has been worked out to ensure an effective police patrol in a given locality. This locality is predominantly a “business/marketing area”. Many problems connected with beat patrol like type of beat, route numbers, beat-ranking and others have been discussed. The analysis will help the police station to understand the beat patrol problem. Alternative beat routes have been suggested, together with deployment. Beat ranking may help in assessing the vulnerability of an area and as such proper steps may be taken in advance to prevent the occurrence of the crime. It is expected that patrolling will be more effective and useful after the implementation of this study.     

警车配置及巡逻方案研究

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

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

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

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.     

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.     

Applying min–max <Emphasis Type="Italic">k</Emphasis> postmen problems to the routing of security guards

The most essential and alluring characteristic of a security estate is the estate's ability to provide 24-h security to its residents, of which the continual patrolling of roads and paths is vital. The objective of this paper is to address the lack of sufficient patrol route design procedures by presenting a tabu search algorithm capable of generating multiple patrol routes for an estate's security guards. The paper shows that the problem of designing these routes can be modelled as an Arc Routing Problem, specifically as min–max k postmen problems. The algorithm is illustrated with a real problem instance from an estate in Gauteng, South Africa. The patrol routes generated by the algorithm provide a significant improvement in the even patrolling of the road network, and a more balanced work distribution among guards. The algorithm is also tested on several benchmark problems from literature.     

A model for a textile winding process

This paper solves the problem of determining the efficiency of N machines uni-directionally patrolled by one operative when walking time between the machines is constant, and repair time is constant, but repairs are not always successful. The problem arises in the context of a textile winding process and the results are of value in maintaining controls over the process. The increased efficiency that results from the operative repeatedly trying to repair a stopped machine, rather than leaving it stopped and continuing with his patrol is also calculated, and the design implications of this improved strategy are considered.     

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.     

110警车配置及巡逻方案

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

基于点截集的围堵嫌犯模型

研究了在突发事件中交巡警对在逃嫌犯的围堵问题, 该问题为2011年全国大学生数学建模竞赛B题的一部分。接到报警后,交巡警服务平台的警力需要指派到路网路口以堵截嫌犯。将该问题转化为阻止嫌犯逃到特定点集的问题;并分析了怎样判断被选为围堵点的点集对一个指定点形成包围的问题。推广了点截集的概念,给出了判断点集是否为点截集和紧点截集的优化模型。然后将判断是否为点截集的模型转换为约束集合, 用于建立围堵嫌犯模型,以四个不同的优化标准分别建立了围堵问题的0-1整数规划模型。并给出了部分模型的Lingo算例。     

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.     

The efficiency of bi-directionally patrolled machines when repairs are not always successful

This paper solves the problem of calculating the effective rate of production of a set of N machines, under the care of one operative, whose method of working is to patrol the machines, first in one direction until all the machines have been inspected and then in the opposite direction, and so on. The time taken to walk from one machine to the next, and inspect and service that machine is assumed to be a constant and is called the walking time. If a machine is stopped when the operative reaches it he spends an additional constant repair time putting it in order before proceeding to the next machine. The problem arises in the practical context of a textile winding process in which the operative is a robot which is not always successful in its attempt to carry out a repair. The numerical results are of value in monitoring this process.     

A smuggling game with asymmetrical information of players

This paper deals with a smuggling game with multiple stages. Customs is allowed to patrol within the limited number of chances and obtain reward by the capture of a smuggler. The smuggler gets a reward depending on the amount of contraband he succeeds to ship in smuggling at each stage. The pay-off of the game is zero-sum. In almost all past studies, they adopt the alternative of smuggling or non-smuggling as the smuggler's strategy. From the point of view of information, some researchers assumed that both players could observe their opponent's behaviour at the past stage or a few assumed that both players had no information about their opponent. Other than these types of smuggling games with the symmetric information, we introduce the asymmetrical acquisition of information or the concept of perfect Bayesian equilibrium in the smuggling game for the first time.     

Scheduling programs with repetitive projects: A comparison of a simulated annealing,a genetic and a pair-wise swap algorithm

We address the problem of scheduling in programs involving the production of multiple units of the same product. Our study was motivated by a construction program for fast naval patrol boats. Other applications of this problem include procurement of multiple copies of aircraft, spacecraft, and weapon systems. In this problem we must decide how many units of the product to assign to each of a number of available crews (individuals, teams, subcontractors, etc.). These types of problems are characterized by two potentially conflicting considerations: 1) the need to complete each unit by its contractual due date, and 2) learning effects. Because of the first consideration, there is a tendency to use multiple crews for simultaneous production, so that meeting due dates is assured. However, the second consideration encourages assigning many units to a single crew so that learning effects are maximized. We study this scheduling problem with two different penalty cost structures and develop models for both versions. The models trade-off the penalty associated with late deliveries and the savings due to learning (and possibly incentive payments for early completion). We discuss different heuristic algorithms — simulated annealing, a genetic algorithm, and a pair-wise swap heuristic — as well as an exhaustive search to determine a baseline for comparisons. Our computational results show that the pair-wise swap algorithm is the most efficient solution procedure for these models.     

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.     

Distribution of waiting time for dynamic pickup and delivery problems

In this paper, we present a basic discrete-time queueing model whereby the service process is decomposed in two (variable) components: the demand of each customer, expressed in a number of work units needed to provide full service of the customer, and the capacity of the server, i.e., the number of work units that the service facility is able to perform per time unit. The model is closely related to multi-server queueing models with server interruptions, in the sense that the service facility is able to deliver more than one unit of work per time unit, and that the number of work units that can be executed per time unit is not constant over time.     

Routing of platforms in a maritime surface surveillance operation

Maritime surface surveillance is the process of obtaining and maintaining information about surface ships in a certain sea area. It is carried out by maritime platforms such as frigates, helicopters or maritime patrol aircraft. Surface surveillance plays a vital role in maritime operations like trade embargo operations, counterdrug operations and traditional warfare operations.The problem of finding optimal tactics for a single surveillance unit is a routing problem which can to some extent be considered as an extension of the on-line travelling salesman problem, but there are essential complications which call for a different approach. A mathematical formulation of the surveillance routing problem is given in this paper. The complications of this problem, in comparison to the on-line travelling salesman problem, are explained.This routing problem is part of the rather complicated process of maritime surface surveillance. SURPASS, an acronym of SURface Picture ASSessment, is a computer model which simulates this process. The model SURPASS provides insight into both the means (i.e. platforms and sensors) needed for a surveillance operation and the effectiveness of various existing and newly developed rules for surveillance tactics. The structure of SURPASS is explained, including the way in which it solves the surveillance routing problem. A number of decision rules that can be used in the routing of the surveillance units are described. The effectiveness of these rules is analysed and evaluated.