# Multi-officer Routing for Patrolling High Risk Areas Jointly Learned from
Check-ins, Crime and Incident Response Data

Shakila Khan Rumi, Kyle K. Qin, and Flora D. Salim Shakila Khan Rumi, Kyle K.
Qin and Flora D. Salim were with the School of Science, RMIT University,
Melbourne, VIC, Australia e-mail: (flora.salim@rmit.edu.au).

###### Abstract

A well-crafted police patrol route design is vital in providing community
safety and security in the society. Previous works have largely focused on
predicting crime events with historical crime data. The usage of large-scale
mobility data collected from Location-Based Social Network, or check-ins, and
Point of Interests (POI) data for designing an effective police patrol is
largely understudied. Given that there are multiple police officers being on
duty in a real-life situation, this makes the problem more complex to solve.
In this paper, we formulate the dynamic crime patrol planning problem for
multiple police officers using check-ins, crime, incident response data, and
POI information. We propose a joint learning and non-random optimisation
method for the representation of possible solutions where multiple police
officers patrol the high crime risk areas simultaneously first rather than the
low crime risk areas. Later, meta-heuristic Genetic Algorithm (GA) and Cuckoo
Search (CS) are implemented to find the optimal routes. The performance of the
proposed solution is verified and compared with several state-of-art methods
using real-world datasets.

###### Index Terms:

Route Planning, Optimization, Crime Dynamics

##  I Introduction

Public safety is an important task for the social and economical development
of a country across the world. Police patrolling plays a vital role to
establish the power of law and ensure the public safety. Prevention of the
future crime event occurrences and prompt response to the emergency events are
fundamental in effective police surveillance strategy. Limited police
resources compare to the operational demands makes the problem more
challenging. Moreover, funding cuts to police resources could further
complicate the situation [1]. Therefore, strategic patrol route planning is
required to help preventing future crime events and enabling instantaneous
response to emergency calls with minimal number of police officers.

Nowadays, with the society’s active participation in the web and social media,
the availability of user-generated social media data is widespread. The web
and big data that is either generated voluntarily by users or through a system
usage contains a plethora of information about human activities and
surrounding environments [2]. Thus, exploring web data provide unprecedented
opportunities to tackle various societal problems. By harnessing this large-
scale web data, the planning of patrol routes of multiple officers can be done
in a more strategic and effective manner.

Several algorithms have been developed in past to design optimal police patrol
routes. Recently, the crime patrol planning problem was formulated to deal
with the cooperation of a police officer for visiting different parts of city
for crime event prevention and minimize the response time for emergency call
based on the priority in [3]. However, it lacks the mutual communications
between multiple police officers. For realistic solution, it is important to
consider the environment, where a patrol officer can communicate with the
other officers. In this paper, we extend the crime patrol planning problem for
multiple police officers which aims at obtaining overall reward as much as
possible. Figure 1 demonstrate the patrolling issue for three different police
officers.

Figure 1: Demonstration of routes arrangement for three policemen in the city
area that has been divided into 15 grids.

This work focuses on patrol route planning problem from the outputs of dynamic
crime event prediction model for short time interval. A classification model
is applied to predict the crime hotspot for a time interval from heterogeneous
data source. Based on the output of crime event prediction, we propose Guided
Leader-based Random Keys Encoding Scheme (G-LERK) to generate the initial
population of solutions which could better adapt to this special issue. One
fitness function is then defined for solution optimization, which considers
the prediction output, crime history and the call priority. At last, we adopt
GA, CS and greedy approach with new encoding method and fitness function for
optimization of multiple police patrol arrangement.

In summary, the contributions of this paper are:

  1. 1.

A new problem formulation for dynamic police patrolling route planning with
cooperation of multiple police officers combining dynamic crime event
prediction and real-time response demand.

  2. 2.

A new solution encoding method is applied to initialise population of
solutions.

  3. 3.

The defined fitness function that integrates the travelling distance affect is
used for acceptance criterion of global optimization.

  4. 4.

Extensive experiments using real-world data to evaluate the capability of
metahuristic algorithms with different number of officers for the patrol
problem.

##  II Related Work

Police patrol route planning include strategic solution of crime hotspot
visits. Several researches have been conducted balanced and effective patrol
routes design for police officers. In [4], the authors modeled the road
network into a graph where the vertices were the nodes to be visited and the
edges were the street segments. The weight of each edge depended on the
distance between the nodes. This work aimed to reduce the idle time between
two consecutive visits of a location by a police officer. This work was lack
of considering the crime history in different locations. In [5] the weight of
the edge depended on the length of the street segment and the importance of
the hotspot locations. The importance of hotspot location was derived from the
long-term crime event density in that location. The goal of this work was to
provide optimal patrol routes which maximizes the coverage of crime hotspots
in minimum distance. A cross-entropy based patrol route planning was applied
in [6]. The authors considered the spatial pattern of crime hotspots to
suggest patrol routes and the effectiveness of collective patrol activities.
In [7], a Baysian ant colony algorithm was proposed to minimize the average
idle time between two consecutive visits of crime hotspots by police officers.
It used probabilistic bayesian model with ant colony algorithm which made the
patrol route selections less predictable by offenders. In [8], the authors
proposed a decision support system based on spatial choice. Here, the decision
makers’ preference were extracted from the incident reports.

The above described researches proposed the patrol routes based on road
network and history of crime event occurrences which made the patrol
environment static or change slowly with time. Dynamic environment in patrol
route planning was considered in [9] for single police officer and in [10] for
multiple police officers. The objective function in the proposed methods were
reduction of the risk of potential crime rate arrival in a location in certain
time interval. In [11], the authors provide a dynamic probability based
solution for catching cars in parking violation. Here, they applied
probability based greedy and ant colony algorithm to design a route for
parking officer.

Some researchers proposed metaheuristic approaches to solve orienteering
problems that are constrained by time [12]. But such work rarely considers
predictive analytics in conjunction with optimization. Some researchers
focused on path planning considering different contexts. In [13], the authors
used accessibility contexts to suggest path with minimal travel time. But in
this paper, the contexts are non dynamic which makes it different to our work.

None of the mentioned work optimize the patrol path generation from a
proactive aspect which include prediction output in route planning. The
authors considered emergency response demand and historical crime data for
predicting high demand areas and used the prediction output for maximizing the
demand coverage in [14]. Here, the authors focused on positioning the police
officers in different areas of city for demand coverage instead of route
planning.

However, uncertainties can happen in real life environment when re-planning of
police patrol route will be required with existing planning. None of the
mentioned works considered the fluctuation in crime event occurrences and
sudden emergency call that need to be attended by a patrol officer. Our work
attempts to fill the gap.

##  III Patrol Route Planning Problem

In this section, we discuss the patrol route planning problem in a dynamic
environment. First, we introduce the patrol route planning problem for a
single police officer and then we formulate the problem for multiple police
officers.

###  III-A Patrol route planning for single police officer

Here, each police officer is responsible for one police beat and moves on road
network using motor vehicle with 50 km per hour average speed. The purpose of
the patrolling is to prevent crime event occurrences by visiting different
nodes and attend the emergency calls. G(V, E) is an indirect weighted graph
where V represents the patrol nodes and E represents the edges between the
nodes. The travel time between nodes represent cost, C associated with the
edges between the nodes. L is a set of all nodes appeared in patrol region,
$N\in V$ and emergency node, $M\in V$ which a police needs to visit. Hence,
$L=N\cup M$.

Mathematically, the patrol reward for each node, $l_{k}$ during time interval,
t can be calculated as

$B(l_{k}(t))=exp(w_{k}(t))*p_{k}*exp(\lambda_{k}(t)).$ (1)

Here, $w_{k}(t)$ and $\lambda_{k}(t)$ denotes the importance and crime arrival
probability of node $l_{k}$ during time interval $t$. $w_{k}(t)$ depends on
the density of crime event during past 3 days in node $l_{k}$ during time
interval $t$. $\lambda_{k}(t)$ has been set as 0, 2, 4 for coldspot, hotspot
and emergency node respectively. $p_{k}$ represents priority of crime. The
priority of a emergency node depends on the type of response demand of the
node 111http://dallascityhall.com/government/. The priority of different nodes
are noted in Table I. The priority of other node is set to 1. The objective is
to maximize this reward for a police officer during the planning horizon,T.
Mathematically, the goal is

$max\sum_{t}\sum_{l_{k}\in L}B(l_{k}(t))$ (2)

s.t.,

$\sum_{e_{ij}\in S,l_{j}\in L}C(e_{ij})+a(l_{j})\leq T$ (3)
$t_{a}=t_{c}+C(e_{l,l+1})$ (4)

In the first constraint, Equation 3, T represents the total duty hours of a
police officer in a day. We assume that, each police officer will stay in a
node for some minutes which is denoted by $a(l_{j})$. According to the first
constraint the total travelling time between node i to j and the staying time,
in node, j can not exceed the maximum duty hours of a police officer in a day.
In second constraint, Equation 4, $t_{a}$ denotes the arrival time of a police
officer in the destination node.

TABLE I: Priority of Different node based on response type Priority |  Types of Response Call
---|---
1 |  False Alarms, Nauisance Mischief, Missing Person, Missing Property, Trespass, Fraud call, Mental health, prowl
2 |  Animal complaints, Theft, Disturbances, hazards, shoplifting, property damage, suspicious circumstances
3 |  Burglary, Liquor violations, Narcotics complaints
4 |  Assaults, Sex Offender, Prostitution, Reckless burning, Robbery, Threats, Harassment
5 |  Accident, Arrest, Homicide, Person Down/Injury, Weapons calls

###  III-B Patrol route planning for multiple police officers

In patrol route planning for multiple police officers, more than one police
officer patrol a region without any area restriction. Here, the police
officers need to communicate in between them for effective patrol without
overlapping. An effective system is required to assign the patrol tasks to
optimal police officers and to find a suitable officer to attend the emergency
call on time which appears dynamically. Let, X is a set of police officers.
Each officer $x\in X$ needs to patrol a route $r_{x}$ and has fixed salary
$\rho$. The goal of this problem is to gain maximum patrol reward with minimum
number of resource consumption. Mathematically, it can be formulated as
follows:

$max\sum_{t=0}^{T}\sum_{x=1}^{|X|}\sum_{l_{k}\in L}B(l_{k}(t))-|X|*\rho$ (5)

s.t.,

$\sum_{e_{ij}\in S,l_{j}\in L}C(e_{ij})+a(l_{j})\leq T$ (6)
$\sum_{t=0}^{T}\sum_{x=1}^{|X|}\sum_{l_{k}\in L}x_{l_{k}(t)}=1$ (7)

Similar to the patrol route planning for single police officer, here, the
first constraint, Equation 6, represents that the total cost can not exceed
total planning time, T. The second constraint, Equation 7, denotes that a node
can be assigned to only one police officer to patrol in a certain time
interval of a day.

##  IV DataSets

The datasets are collected for a sector in Seattle, USA. The city is divided
into total 17 different sectors. Police sector is type of spatial division
which consists of more than one police beats. Each police beat is used to
patrol by a police officer.

#### Crime Dataset

The crime event records of Seattle, USA from “03-2012” -“02-2013” are
collected from from public source 222https://data.seattle.gov/Public-
Safety/Seattle-Police-Department-Police-Report-Incident/7ais-f98f. The total
number of crime events that happened in K police sector during this time
period is 9,157.

#### Check-in Data

We acquire Foursquare venue data and check-in data in Seattle for the same
time period as crime event records are obtained from the authors [15, 16].The
venue is also known as Point Of Interest (POI). In the K police sector, the
data set consists of 5,090 check-ins performed by 1,017 users a during the
same time period as crime dataset.

#### 911 Incident Response

To simulate the emergency call to response, we use 911 Incident Response data
333https://data.seattle.gov/Public-Safety/Seattle-Police-
Department-911-Incident-Response/3k2p-39jp. In K police sector, total 19,410
emergency call were required to attend by a police officer during the same
time period as crime data.

#### Google Maps

The distance between two nodes are used to calculate the cost of each edge. We
measure the distance between the centroid of the nodes to find the travel
cost.

##  V System Approach

The proposed system to design optimal police patrol route consists of two
parts : 1) Crime event prediction using dynamic information and 2) Patrol
route generation. The framework is illustrated in Figure 2. In the following
sections, we describe the crime prediction method and the prediction based
dynamic route planning algorithms.

Figure 2: The framework for solving the multiple police patrol issue. TABLE II: Summary of Crime Event Prediction Features Feature Category |  Name |  Equation
---|---|---
Historical Features |  $30$-days Crime Event Density |  $H_{1}(v_{i},t)=\dfrac{\sum_{j=d-30}^{d}Cr_{j}(v_{i},t)}{30}$, $Cr_{j}(v_{i},t)$ is the number of crime events occurred at day, $j$ in node $v_{i}$ during time interval, $t$
|  $7$-days Crime Event Density |  $H_{2}(v_{i},t)=\dfrac{\sum_{j=d-7}^{d}Cr_{j}(v_{i},t)}{7}$
|  POI Distribution |  $G_{x}(v_{i})=\dfrac{X_{x}(v_{i})}{X(v_{i})}$ , $X_{x}(v_{i})$ and $X(v_{i})$ represents number of x-type and total venues in $v_{i}$ node
POI based Features |  POI Density |  $G_{2}(v_{i})=\frac{X(v_{i})}{A(v_{i})}$, Here $A(v_{i})$ is the grid size
|  Location Diversity |  $G_{3}(v_{i})=-\sum_{x\in X_{p}}(\dfrac{X_{x}(v_{i})}{X(v_{i})}\times\log\dfrac{X_{x}(v_{i})}{X(v_{i})})$, $X_{p}$ is total types of venues
|  Visitor Entropy |  $D_{1}(v_{i},t)=-\sum_{u\in U(v_{i})}Pr_{v_{i},t}(u)log_{2}Pr_{v_{i},t}(u)$ , $U(v_{i})$ denotes total social media user in $v_{i}$ node and $Pr_{v_{i},t}$ represents the probability of giving check-in in $v_{i}$ during t time interval
|  Visitor Homogeneity |  $D_{2}(v_{i},t)=\dfrac{\sum_{{u_{1},u_{2}}\in U(v_{i},t)}sim(u_{1},u_{2})_{v_{i},t}}{U(v_{i},t)}$, $sim(u_{1},u_{2})$ calculates cosine similarity between pair of users $u_{1}$ and $u_{2}$ who gave check-in in $v_{i}$ node during $t$ time interval
Mobility based Features |  Region Popularity |  $D_{3}(v_{i},t)=\dfrac{|CH(v_{i},t)|}{\sum_{v_{i}\in V}|CH(v_{i},t)|}$, $CH(v_{i},t)$ represents number of check-ins in $v_{i}$ node during $t$ time interval
|  Visitor Ratio |  $D_{4}(v_{i},t)=\dfrac{|VR(v_{i},t)|}{|CH(v_{i},t)|}$, $VR(v_{i},t)$ denotes the new users in node, $v_{i}$ during $t$ interval
|  User Count |  Number of total users in $v_{i}$ node during $t$ interval, $|U(v_{i},t)|$
|  Observation Frequency |  Number of total check-ins in $v_{i}$ node during $t$ interval, $|CH(v_{i},t)|$

###  V-A Crime Event Prediction

Crime event prediction component aims to predict crime event in a short-term
interval, which helps the police to design a patrol strategy in advance. With
an aim to predict crime event with fine temporal granularity, we predict crime
for 2 hours. Similarly, it can be predicted for other temporal granularities
also. The prediction method consists of the following steps:

####  V-A1 Feature Extraction

Crime event prediction is a complex problem which depends upon different types
of information regarding the past history of crime events, the geography of a
region, and the human mobility in a region at different time intervals. We
extract several features as predictors of crime event prediction model
including historical features, geographic features and dynamic features.

Crime events are more likely to happen in the vicinity of past crime events.
To retain the historical knowledge about crime event occurrence in a patrol
node, we calculate features based on the crime event density. There is
correlation between the type of land usages and crime event rates in a region
[17]. The POI based features describe the geographic information of different
nodes in patrol area. This type of features are extracted from foursquare POI.

According to the environmental criminal theories, activity location, daily
life style are dominant in prompting crime event occurrences [18, 19, 20].
Human movement in a city helps us to understand the activity spaces and life
style of urban people in timely manner. Now a days, booming of social media
opens the door to analyze human movement in large scale. Therefore,
integrating the environmental criminal theories with mobility data from social
media is able to build an efficient crime event prediction model. In [21], the
authors proposed several mobility based features from foursquare and showed
the superior performance of this type of features. We apply similar dynamic
features into our model. For node $v_{i}$ at time interval $t$, the training
and test data includes the features which are summarized in Table II.

####  V-A2 Data Sampling

Crime does not happen frequently. Therefore, many regions in many time
intervals have “no-crime” class. With very low number of “crime” class, the
distribution of class variables becomes asymmetrical. The classifiers with
imbalanced training data cause bias towards the majority class in test result.
To mitigate the problem, we balance the training set using under-sampling
technique. This technique removes some classes with major distribution. In the
balanced training set, the dataset contains 50% crime data and 50% no crime
data.

Figure 3: The illustration of new solution encoding scheme, G-LERK for
multiple police patrol issue.

####  V-A3 Classification

In final step, we build a classifier based on Random Forest (RF) algorithm for
dynamic crime event prediction. _RF_ is an ensemble learning method which
constructs multiple decision trees ($n_{tree}$) in a random subspace of the
feature space [22]. For each subspace, the unpruned tree generates their
classifications and in the final step, all the decisions generated by
$n_{tree}$ are combined for final prediction [23]. The reason behind choosing
RF as a classifier algorithm is that the convergence of the algorithm depends
on only the number strong features without taking account the less important
or noisy features [24]. The non-parametric nature of this algorithm makes it
more suitable learning algorithm when the feature space is heterogeneous and
multidimensional like our problem [25]. Again, RF provided consistent and good
performance in crime prediction over linear and kernel based method in
previous studies [26, 27, 28].

###  V-B Patrol Route Planning for Multiple Police Officers

Here, we describe the patrol route planning framework for multiple police
officers based on meta-heuristic algorithms like Genetic Algorithm (GA) and
Cuckoo Search (CS). We assume that the system has real time record of
emergency call, location and working status of police officers. We apply non-
random, guided population generation scheme based on Leader-based Random Keys
Encoding Scheme to generate the initial solution for multiple police officers.
Later, we apply greedy based sorting approach to find the local optima.
Finally, we apply metaheuristic algorithms, GA and CS to obtain the global
optimal solution among initial population. The fitness function of the
metaheuristics is defined based on the crime event density, prediction output
or emergencies and priority. The fitness of a solution also depends on the
arrival time of a police officer in a node.

####  V-B1 Guided Leader-based Random Keys Encoding Scheme (G-LERK)

Our main challenge in patrol route planning for police officer is that the
states of locations change with time and the police officers may prevent more
crime if they visit the hotspot node first than the coldspot node. Therefore,
we need to construct a temporary path for police officers which will guide
them to the hotspot locations before visiting the coldspot node. We introduce
a new population generation approach G-LERK based on the prediction outcome
and Leader based Random Keys Encoding Scheme (LERK), which generate intial
solutions for the police officers. LERK is a method which has been used to
generate random ids for parking officers and parking nodes for initial
solution [29]. In LERK, the parking nodes are assigned randomly to the police
officers for next task. However, in our scenario, using this encoding scheme
directly in population generation might limit the chances to prevent crime.
With this method, all the hotspot nodes will be assigned to first few officers
or one officer. Therefore, it lowers the chances to prevent crime. To overcome
this drawback, we propose G-LERK, where all idle officers start their patrol
with a hotspot node instead a coldspot. Fig. 3 shows the encoding process of a
solution, G-LERK for multiple police patrol issue. In our problem, each police
officer and node has unique id. The LERK combines theses ids in a link-list
with a random number between 0 to 1. From, the sorted link list, the initial
patrol route for each police officer is determined. In G-LERK, first, we
consider two separate link lists depending on hotspot nodes and coldspot
nodes. We assign different range of numbers for the hotspot nodes and colspot
nodes. The first link-list combines the police officers and the hotspot nodes
with a random number drawn from (0.5,1]. Later, we sort them ensuring that a
police officer is in the front of the list. Similarly, we generate and sort
another link list with similar police officers and coldspot nodes with a
random number drawn from (0,0.5]. Finally, we combine these two lists in a
single list based on the officers’ id to encode a initial solution.

####  V-B2 Local Optimization

The local optimization helps to find the optimal solution of each sub-tour for
every police officer in a new solution. We apply greedy based approach here
based on the location of police officer. The node with highest benefit in a
will be selected and moved to the front position of a sub-tour for the
corresponding police officer. This method ensures that a police officer can
have high opportunity to prevent future crime and response the demand at right
time.

####  V-B3 Global Optimization

We search for the best solution for multiple police officer patrol route
problem using metaheuristic algorithms like GA, CS and greedy. For finding the
optimal solution for patrol node assignment, a fitness function is defined for
evaluation of the quality of solution.

TABLE III: Benefit calculation based on arrival time of police Arrival Time(min) | Priority of Crime Type
---|---
|  5 |  4 |  3 |  2 |  1
$<15$ |  1 |  1 |  1 |  1 |  1
[15 - 30] |  0 |  0 |  0.8 |  0.8 |  0.8
[31 - 60) |  0 |  0 |  0 |  0.6 |  0.6
$>60$ |  0 |  0 |  0 |  0 |  0.5

Fitness Function In metaheuristic algorithms, in each iteration the solution
is updated based on the superiority of the solution. In our experiment, a
solution replaces the old one, if it achieves higher fitness value. The
fitness function is defined as follows:

$\sum_{r\in R}\sum_{l_{k}\in r}B(l_{k}(t))*Pr_{l_{k},l_{k+1}},$ (8)

s.t.,

$Pr_{l_{k},l_{k+1}}\in{0,1}$ (9)

In Equation 10, R refers to the sub-routes generated for each police officer
in the solution. $Pr_{l_{k},l_{k+1}}$ determines the time-dependent benefit
that a police officer can obtain based on the arrival time of a police officer
in a node. The benefit value calculation based on the arrival time of a police
officer is summarized in Table III. The priority value for each crime type is
based on the call priority system established by Dallas police, USA [30].

Genetic Algorithm (GA) for Optimization GA is a popular metaheuristic
algorithm to identify optimal solutions for problem [31]. In our approach, we
use G-LERK for initial population generation for GA. Each individual in
population is called chromosome. After generating the initial population, the
chromosomes are ranked based on their fitness value. It separates the
chromosomes into three parts including, elitist, crossover part and mutate
part. Crossover and mutate part are used to generate new off-springs and
elitist is kept exactly in new population. The proposed G-LERK-GA is
illustrated in Algorithm 1.

Algorithm 1 Guided Genetic Algorithm (G-LERK-GA)

1:

2:Set of nodes for patrol $L$; set of idle officers $P_{f}$; portion of
population for Elitist $elitistRate$; size of population for Crossover
$crossoverSize$; portion of population for Immigration $mutateRate$

3:

4:The optimal solution $S_{best}$

5:Initialize a population of chromosomes $S$ via the G-LERK

6:while ($i<$ $maxIteration$) do

7: Rank $S$ by fitness in descending order

8: $S_{new}\leftarrow$ $S$

9: Keep $elitistRate$ portion of best $S_{new}$ unchanged

10: for ($j<$ $crossoverSize$) do

11: Select $S_{Mom}$, $S_{Dad}$ from $S$ at random

12: Get $S_{child}$ by new crossover on $S_{Mom}$, $S_{Dad}$

13: Apply local optimization on $S_{child}$

14: Replace $S_{i}\in S_{new}$ by $S_{child}$

15: end for

16: Immigration on a $mutateRate$ portion of worst $S_{new}$

17: $S\leftarrow S_{new}$

18:end while

19:Return $S_{best}$ from $S$

Cuckoo Search (CS) for Optimization CS is another popular metaheuristic
algorithm, which was developed based on the parasitic behaviour of some cuckoo
birds [32] and showed efficiency in several optimization problems. Similar to
GA, we apply G-LERK method to generate initial solution (population of nest),
in our proposed CS algorithm. A parameter, preFly, represents the superior
candidates (cuckoos) in population. These cuckoos are allowed to fly and find
high quality nests. The portion of preFly nest, $p_{c}$ is determined via Levy
flights. In each iteration, the fitness value between one candidate from
preFly and another randomly selected competitor from population nest is
compared for replacement. If the new solution is better than the old one, it
replaces the previous one. After end of the comparison a portion of worst nest
is abandoned and new nest is built. The detail of the G-LERK-CS is illustrated
in Algorithm 2.

Algorithm 2 Guided Cuckoo Search (G-LERK-CS)

1:

2:Set of nodes for patrol $L$; set of idle officers $P_{f}$; number of
superior candidates $preFly$; portion of population for incubation $p_{c}$ and
drop $p_{a}$

3:

4:The optimal solution $S_{best}$

5:Initialize a population of nests $S$ via the G-LERK

6:while ($i<$ $maxIteration$) do

7: for ($j<$ $preFly$) do

8: Select a nest $S_{j}$ from a portion $p_{c}$ of top $S$

9: Get a candidate $S_{j}^{{}^{\prime}}$ based on $S_{j}$ via Levy flights

10: Apply local optimization on $S_{j}^{{}^{\prime}}$

11: Evaluate $S_{j}^{{}^{\prime}}$ fitness $F_{j}$

12: Pick competitor $S_{k}\in S$ randomly with fitness $F_{k}$

13: if ($F_{i}>F_{k}$) then

14: replace $S_{k}$ by $S_{j}^{{}^{\prime}}$

15: end if

16: end for

17: Abandon a portion $p_{a}$ of worse nests and create new ones to replace

18: Rank $S$ by fitness in descending order

19:end while

20:Return $S_{best}$ from $S$

Algorithm 3 Greedy Algorithm by Importance (Imp-Greedy)

1:

2:Set of nodes for patrol $L$; set of idle officers $P_{f}$

3:

4:The optimal solution $S_{best}$

5:for node $v_{i}\in L$ do

6: $P_{best}$ $\leftarrow$ null

7: $Pr_{max}$ $\leftarrow$ null

8: for node $p_{f}\in P_{f}$ do

9: $Pr$ $\leftarrow$ Fitness($v_{i}$, $p_{f}$)

10: if ( then$Pr>Pr_{max}$)

11: $Pr_{max}$ $\leftarrow$ Pr

12: $P_{best}$ $\leftarrow p_{f}$

13: end if

14: end for

15: Assign $v_{i}$ to $P_{best}$

16:end for

Greedy Algorithm for Optimization We also implement the greedy algorithm for
arranging routes for police officers, which is simple and usually effective
[33, 34]. Two variants of greedy algorithm called Imp-Greedy and Dis-Greedy
are developed in our implementation. In each arrangement of Imp-Greedy, we
first calculate the essential of each node in emergency according to current
position of idle officers, then a node will be allocated to the officer who
has the highest essential for it. This algorithm is described in Algorithm 3.
And the way to calculate the essential of a node is below:

$B(l_{k}(t))*Pr_{l_{k},l_{k+1}},$ (10)

In contrast, instead of computing the essential for nodes, we calculate the
walking or driving distance between each node and idle officers in the Dis-
Greedy where a node will be assigned to the person who has the shortest
distance to it.

(a) Week 1

(b) Week 3

(c) Week 5

Figure 4: Weekly robustness obtained by algorithms in five runs.

(a) Week 1

(b) Week 3

(c) Week 5

Figure 5: Weekly efficiency obtained by algorithms in five runs.

##  VI Experiments

The different optimisation algorithms mentioned in previous section for patrol
route generation are evaluated here with real-world data described in Section
IV. For the crime event prediction, a day is partitioned into intervals of 2
hours. We have used data that lies into “04/2012 - 12/2012” for training
purpose. The data lies in “01/2013 - 02/2013” have been used to evaluate
prediction performance and design the patrol route. The total number of
emergencies and crime event occurrences of every week during patrol route
planning period are given in Table IV.

TABLE IV: Total Emergencies and Crime Occurrences of January and February in 2013. Data Time | Total Emergencies | Total Crime Events
---|---|---
Week 1 (07/01 - 13/01) | 215 | 48
Week 2 (14/01 - 20/01) | 189 | 51
Week 3 (21/01 - 27/01) | 203 | 33
Week 4 (28/01 - 03/02) | 219 | 54
Week 5 (04/02 - 10/02) | 251 | 45
Week 6 (11/02 - 17/02) | 230 | 52

The experimental results for patrol route planning with system settings and
evaluation methods are described in the following sections.

###  VI-A System Settings

A simulation system have been built for the experiments. Firstly, we divided
the map into 94 grids equally and the initial positions of all the police
officers start from the first grid. It is assumed that the polices work from 8
am to 8 pm each day to patrol around the whole map. When next patrolling
duration of a police to a grid exceeds 8 pm, the system will stop the work of
this police in a day. In addition, if one grid is visiting by a police, the
status of both police and grid will be hided from the process of following
assignments until the visit is finished. In this system, the street walking
speed of officers is approximately 1.2 m/s and the frequency to scan current
emergency calls, hotspot records and available polices is 1 minute. The
probability to conduct the local optimization for CS and GA is 0.5,which sorts
the nodes on a temporary path by their importance.

TABLE V: Parametric configuration for LERK-CS and G-LERK-CS. Parameter | Value | Description
---|---|---
$p_{a}$ | 0.3 | Portion of worse nests
$p_{c}$ | 0.6 | Portion of superior nests
$\alpha$ | 0.05 | Scaling factor of step size
$\lambda$ | 1 | Exponent of a power-law distribution
preFly | 0.3 | Portion of superior cuckoos to seek high-quality nests
TABLE VI: Parametric configuration for LERK-GA and G-LERK-GA. Parameter | Value | Description
---|---|---
elitistRate | 0.2 | Proportion of population for reproduction operation
crossRate | 0.3 | Proportion of population for crossover operation
mutateRate | 0.2 | Proportion of population for immigration operation

Moreover, the population size and the number of iterations for all the
implemented GA and CS are 100 and 300, respectively. The other parametric
settings of these two types of algorithms are given in Tables V and VI.
Finally, the system was implemented in Python 3.6 and executed on a desktop
with Intel i9-9900k CPU 8 Cores 3.6 GHz and Memory 64 GB DDR3. The details of
experimental results are discussed in the section VI-D.

###  VI-B Comparison Algorithms

For comparison, we adopt random initial population generation method and
different fitness function for solving the patrol route planning problem. We
apply LERK-GA and LERK-CS, proposed in [29] for comparison. Here, the authors
used Random Keys Encoding Scheme, LERK to generate the initial solution. Then,
we conduct experiments for the comparison between the proposed methods
(G-LERK-GA and G-LERK-CS) and the original ones (LERK-GA and LERK-CS). In
addition, we also implement two different versions of greedy algorithms with
either prediction output or pure travelling distance consideration. They are
mentioned as Dis-Greedy and Imp-Greedy.

###  VI-C Evaluation Methodology

We evaluate the performance of routes arrangement with two different metrics:
efficiency and robustness.

Efficiency The efficiency measures how many real crime events are prevented in
duty hour of a police officer. The efficiency of a patrol route is measured as
follows:

$Ef(T)=\frac{\sum_{t=t_{c}-60,n_{i}\in N}^{t_{c}+60}visit(n_{i})}{|N|}$ (11)

Here, $t_{c}$ represents the occurrence time of crime event; $N$ represents
the nodes where the crime event occurred. $visit(n_{i})$ returns 1 if the
crime node is visited by a police officer in between before or after 1-hour of
occurrence.

Robustness The robustness determines how many emergencies are attended by a
police officer. It also depends on the arrival time of a police officer and
crime priority. If a police officer arrives to a crime spot in between 15
minutes of occurrence time the robustness has been set to 1 for all type of
calls. When arrival time is between 15 - 30 minutes, it is set to 1 when the
priority of call is below 4. When the arrival time increases to 31 - 60
minutes, only the calls with 1 and 2 priority returns value. If the priority
of call is 1, visit of a police officer to a crime event occurrence spot after
1 hour is valuable. The robustness value is determined based on the arrival
duration after making the call and the priority of the crime type.

(a) January

(b) February

Figure 6: Monthly robustness obtained by algorithms in five runs.

(a) January

(b) February

Figure 7: Monthly efficiency obtained by algorithms in five runs.

###  VI-D Experimental Results

In this section, we first conducted the prediction of criminal information
based on different features that mentioned in Section V-A. Along with the
emergencies and criminal events of three weeks between January and February
2013, we then evaluate the efficiency and robustness for six different
algorithms. The detail of the weekly events is showed in Table IV. In these
algorithms, G-LERK-CS and G-LERK-GA leverage the fitness evaluation of the
destinations along with the prediction data for arranging routes of polices on
map, but LERK-CS and LERK-GA only apply the fitness evaluation without
considering hotspot or coldspot prediction. Greedy algorithms allocate tasks
based on either the maximum essential or nearest travelling distance between
offices and destinations.

####  VI-D1 The Total Robustness Obtained

In this experiment, we use 5-30 police officers to patrol the whole area and
count the total robustness that received in weekly and monthly respectively.
The mean and standard deviation of the total robustness are calculated based
on five trials for each algorithm. As the information showed in Fig. 4 and
Fig. 6, the mean value of the robustness that got in a week or in a month is
increased gradually when more polices involve into the patrolling. The figures
of all the algorithms tend to converge at using 30 police officers. We also
notice that G-LERK-CS, G-LERK-GA have better performance than their
counterparts LERK-CS, LERK-GA when the number of working officers is less than
15 people. However, the gap of the performance between algorithms is shrank
when the number of polices who participated into the patrolling officers
reaches 20 or 30. Moreover, from Fig. 4 and Fig. 6, we can observe that the
greedy algorithm performs better than the advanced GA and CS when the number
of patrolling officers is less than 15 people. As greedy algorithm selects the
next visiting node based on the highest patrol reward, it is more robust to
the emergencies. However, when many patrolling officers are involved the
system becomes more complex. In this scenario, GA and CS based algorithms
outperform greedy based algorithms. Among two variants of greedy algorithm,
Greedy-Imp outperforms Greedy-dist. It verifies that patrolling a node based
on their possibility of crime event occurrence provide more robust solution
than patrolling nearby nodes from current position.

####  VI-D2 The Total Efficiency Obtained

We also evaluate the weekly and monthly efficiency of the algorithms and
illustrate them in Fig. 5 and Fig. 7 respectively. Similar to robustness
calculation, 5-30 police officers are allocated in the missions and the
results of total efficiency each week are recorded and compared. The mean and
standard deviation of the total efficiency are calculated based on five tests
for each algorithm. Both Fig. 5 and Fig. 7 indicate that the efficiency of the
algorithms on solving the problem can be enhanced with more polices for the
patrolling. In addition, the figures also demonstrate that G-LERK-CS and
G-LERK-GA often perform better than their counterpart LERK-CS and LERK-GA
respectively when the number of police officers is less than 20. But with the
increasing number of officers, the former algorithms and the latter ones show
a neck-and-neck result in the total efficiency. We also observe that when more
police officers are involved, the greedy algorithm base solutions are more
efficient in catching crime than the solutions obtained from GA and CS
algorithms. The reason behind such result is when more police officers are
involved they cover many observation areas. Therefore, visiting nearby
locations only help them deterring crime event efficiently. The overall
results provide us an insight that we could choose a suitable implementation
to solve the proposed issue according to available human resources and the
management effect worth more attention, such as robustness or efficiency.

##  VII Conclusion

This work focus on designing effective police surveillance strategy to prevent
the future crime event occurrences and response to the emergency events.
Compared with the existing studies on police patrol route designing where the
potential nodes are selected based on spatial segmentation, this work include
crime event prediction method where human mobility is considered as
environment sensor to determine the next potential hotspot nodes. The provided
model is also responsive to the uncertain arrival of emergency situations that
is required to attend by a police officer. The findings in this research
suggest that by fusing crime event prediction and real-time emergencies, the
planning of patrol routes for multiple officers can be done more effectively.

## References

  * [1] “Criminals going unpunished because of cuts, says police chief,” https://www.theguardian.com/uk-news/2019/may/02/criminals-going-unpunished-because-of-cuts-says-police-chief, published on: 2019-05-02.
  * [2] R. Kitchin, “The real-time city? big data and smart urbanism,” _GeoJournal_ , vol. 79, no. 1, pp. 1–14, 2014.
  * [3] S. K. Rumi, W. Shao, and F. D. Salim, “Realtime predictive patrolling and routing with mobility and emergency calls data,” in _Proceedings of the International AAAI Conference on Web and Social Media_ , 2020.
  * [4] Y. Chevaleyre, F. Sempe, and G. Ramalho, “A theoretical analysis of multi-agent patrolling strategies,” in _Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems-Volume 3_. IEEE Computer Society, 2004, pp. 1524–1525.
  * [5] S. S. Chawathe, “Organizing Hot-Spot Police Patrol Routes,” _2007 IEEE International Conference in Intelligence and Security Informatics_ , pp. 79–86, 2007.
  * [6] L. Li, Z. Jiang, N. Duan, W. Dong, K. Hu, and W. Sun, “Police patrol service optimization based on the spatial pattern of hotspots,” _Proceedings of 2011 IEEE International Conference on Service Operations, Logistics and Informatics, SOLI 2011_ , pp. 45–50, 2011.
  * [7] H. Chen, T. Cheng, and S. Wise, “Designing Daily Patrol Routes for Policing Based on Ant Colony Algorithm,” _ISPRS Annals of Photogrammetry, Remote Sensing and Spatial Information Sciences_ , vol. II-4/W2, no. January 2016, pp. 103–109, 2015.
  * [8] Y. Xue and D. E. Brown, “A decision model for spatial site selection by criminals: a foundation for law enforcement decision support,” _IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews)_ , vol. 33, no. 1, pp. 78–85, 2003.
  * [9] X. Chen and T.-S. P. Yum, “Cross entropy approach for patrol route planning in dynamic environments,” _Intelligence and Security Informatics (ISI), 2010 IEEE International Conference on_ , pp. 114–119, 2010.
  * [10] X. Chen, “Fast Patrol Route Planning in Dynamic Environments,” _IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans_ , vol. 42, no. 4, pp. 894–904, 2012.
  * [11] W. Shao, F. D. Salim, T. Gu, N.-T. Dinh, and J. Chan, “Traveling officer problem: Managing car parking violations efficiently using sensor data,” _IEEE Internet of Things Journal_ , vol. 5, no. 2, pp. 802–810, 2018.
  * [12] Y. Mei, F. D. Salim, and X. Li, “Efficient meta-heuristics for the multi-objective time-dependent orienteering problem,” _European Journal of Operational Research_ , vol. 254, no. 2, pp. 443–457, 2016.
  * [13] M. S. Rahaman, Y. Mei, M. Hamilton, and F. D. Salim, “Capra: A contour-based accessible path routing algorithm,” _Information Sciences_ , vol. 385, pp. 157–173, 2017.
  * [14] J. Leigh, S. Dunnett, and L. Jackson, “Predictive police patrolling to target hotspots and cover response demand,” _Annals of Operations Research_ , pp. 1–16.
  * [15] D. Yang, D. Zhang, and B. Qu, “Participatory cultural mapping based on collective behavior data in location-based social networks,” _ACM Transactions on Intelligent Systems and Technology (TIST)_ , vol. 7, no. 3, p. 30, 2016.
  * [16] D. Yang, D. Zhang, L. Chen, and B. Qu, “Nationtelescope: Monitoring and visualizing large-scale collective behavior in lbsns,” _Journal of Network and Computer Applications_ , vol. 55, pp. 170–180, 2015.
  * [17] J. C. Wo, “Mixed land use and neighborhood crime,” _Social science research_ , vol. 78, pp. 170–186, 2019.
  * [18] L. E. Cohen and M. Felson, “Social change and crime rate trends: A routine activity approach,” _American sociological review_ , pp. 588–608, 1979.
  * [19] P. L. Brantingham and P. J. Brantingham, “Environment, routine and situation: Toward a pattern theory of crime,” _Advances in criminological theory_ , vol. 5, no. 2, pp. 259–94, 1993.
  * [20] H. J. Miller, “A measurement theory for time geography,” _Geographical analysis_ , vol. 37, no. 1, pp. 17–45, 2005.
  * [21] S. K. Rumi, K. Deng, and F. Salim, “Crime Event Prediction with Dynamic Features,” _EPJ Data Science_ , 2018, in Press.
  * [22] T. K. Ho, “Random decision forests,” in _Document Analysis and Recognition, 1995., Proceedings of the Third International Conference on_ , vol. 1. IEEE, 1995, pp. 278–282.
  * [23] A. Liaw and M. Wiener, “Classification and regression by randomforest,” _R news_ , vol. 2, no. 3, pp. 18–22, 2002.
  * [24] G. Biau, “Analysis of a random forests model,” _Journal of Machine Learning Research_ , vol. 13, no. Apr, pp. 1063–1095, 2012.
  * [25] C. Kadar and I. Pletikosa, “Mining large-scale human mobility data for long-term crime prediction,” _EPJ Data Science_ , vol. 7, no. 1, p. 26, 2018\.
  * [26] S. K. Rumi, K. Deng, and F. Salim, “Theft prediction with individual risk factor of visitors,” in _Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems_. ACM, 2018.
  * [27] A. Bogomolov, B. Lepri, J. Staiano, N. Oliver, F. Pianesi, and A. Pentland, “Once upon a crime: towards crime prediction from demographics and mobile data,” in _Proceedings of the 16th international conference on multimodal interaction_. ACM, 2014, pp. 427–434.
  * [28] A. Bogomolov, B. Lepri, J. Staiano, E. Letouzé, N. Oliver, F. Pianesi, and A. Pentland, “Moves on the street: Classifying crime hotspots using aggregated anonymized data on people dynamics,” _Big data_ , vol. 3, no. 3, pp. 148–158, 2015.
  * [29] K. K. Qin, W. Shao, Y. Ren, J. Chan, and F. D. Salim, “Solving multiple travelling officers problem with population-based optimization algorithms,” _Neural Computing and Applications_ , pp. 1–27, 2019.
  * [30] D. O. Brown, “Communications operations center (handling calls for service),” 2006\.
  * [31] D. Whitley, “A genetic algorithm tutorial,” _Statistics and computing_ , vol. 4, no. 2, pp. 65–85, 1994.
  * [32] X.-S. Yang and S. Deb, “Cuckoo search via lévy flights,” in _2009 World Congress on Nature & Biologically Inspired Computing (NaBIC)_. IEEE, 2009, pp. 210–214.
  * [33] Y. Akçay, H. Li, and S. H. Xu, “Greedy algorithm for the general multidimensional knapsack problem,” _Annals of Operations Research_ , vol. 150, no. 1, p. 17, 2007.
  * [34] R. Ruiz and T. Stützle, “A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem,” _European Journal of Operational Research_ , vol. 177, no. 3, pp. 2033–2049, 2007.