Finding Optimal Police Patrolling Route from Road

Network Graph for Efficient Crime Response Time

a Information Technology University, 346-B, Ferozepur Road, Lahore, Pakistan

Abstract

Keywords: Crime analysis, Optimal Patrolling Route, Road Network Graph

1. Introduction

The scope of crimes is influenced by the number of factors. Law enforce-

ment officials need to discover about the causes that contribute to a rise in the
propensity to crime. In order to limit it, Crime reduction policies and strategies
5 are still required [1]. Police authorities deal with a huge amount of data that
requires to be processed. By processing criminal records, security agencies can
use effective predictive models for crime reduction. Safety & security has be-
come the top priority of individuals due of the growing number of crimes in the
cities. The well-being and protection of people is important for governments.
10 The basic goal of these institutions is to deter criminal offences immediately. A
wide range of technologies and information have been used to develop strategies
that could safeguard public security [2, 3].
Various approaches have been proposed to address the challenges of network
architecture and shortest routing paths networks. This work focus on locating
15 and optimizing the route of police forces within the jurisdiction of a police
station, allowing the law enforcement officials to operate more efficiently. In this
vein, we construct the integer program for the optimal route prediction based
on maximizing the objective function. Finding shortest path on optimizing
objective function has been researched in a number of manners. It is known
20 as shortest path problem. Generally, in these settings, 1) The shortest path

Preprint submitted to Journal of Information Processing and ManagementDecember 17, 2020

 problem is the process of finding the shortest path between two vertices on a
graph. We can consider it the most efficient route through the graph.
This work focuses on the robust optimization integer program optimal pa-
trol routes for police force, allowing for law enforcement to operate more effi-
25 ciently.An implementation of this algorithm is used successfully in planning the
optimal route for the Lahore Police forces. We perform an extensive case study
on real-world crime data provided in the Lahore Crime Dataset. We predicted
the route for police patrol which will visit the denser crime rate areas. We also
explored the graphs for different areas in the city. Finally our model found the
30 optimal patrol route as finding a score-maximizing cycle within a graph. The
paper is organised as follows. We discuss the related work in Section 2. The
preliminaries and problem definition are discussed in Section 5. We propose
methodologies to solve the problem in Section 6, and perform a case study in
Section 7 to showcase the applicability. Finally, we conclude in Section 8.

35 2. Related work

In this section we present a brief literature review on works related to choos-

ing optimal patrol routes.

2.1. Crime analysis and policing optimization

Criminology has been an area of active research for centuries [1]. The advent
40 of data mining and machine learning techniques has allowed the community to
better automate the analysis of crime [2, 3], and scale to data of larger propor-
tions [4]. Hassani et al. [3] provide a review of common approaches to crime
analysis using these techniques. They identify five data mining techniques used
within the literature: (1) entity extraction, which entails extracting information
45 from sources such as witness reports or news stories, allowing for the analysis of
any patterns found within the data; (2) cluster analysis, which has been used
to find crime “hotspots”, and track the model the behaviour of criminals; (3)
association rule, which has been used to link crimes committed by the same

2
 people; (4) classification, which has been used for various tasks including de-
50 tecting suspicious emails, exposing lies, and uncovering credit card fraud; and
(5) social network analysis, which has been used to detect criminal accounts
and analyze characteristics of terrorist organizations.

2.2. Related problems

Police patrolling is one of the most important task on a daily basis to prevent
55 and reduce crime and respond to emergencies and disasters [5].Design of opti-
mal patrol route involves different strategies in terms of routing, cooperation,
evaluation and other features.There are research problems similar to ours that
focuses on finding optimal police patrol routes, with the aim to minimize crime
response time [6, 7, 5]. In this domain of studies, researchers also focused on
60 spatial patterns of hot spot areas. Li et al. proposed an approach to determine
multiple patrol routes, but they didn’t provide a single solution to plan a patrol
route [7].
Work in this area also focused on finding optimal group performance by
coordinating teams of mobile robots which employed Multi-robot Patrolling Al-
65 gorithm [8].They omit the challenges of daily police patrol including minimizing
the average time lag between two consecutive visits to hot spot.Similarly, work
has been done on cooperative routing strategies. These strategies are moving
toward emergency scenarios handling [9].To solve the police patrol routing prob-
lem (PPRP),versatile approaches have been put forward ranging from methods
70 like Genetic Algorithms, linear programming, routing policies, to more complex
set of solutions like Markov Decision Processes and Stochastic Combinatorial
Optimization [5].Christofides Cyclic Patrolling Strategy (CCPS), which is a de-
terministic and cyclic patrolling strategy from graph theory focuses on regular
and fair visit to each hot spot by patrols following the same direction on the
75 cycle [10].
One of the attractive element of an integer programming approach is its
flexibility,that permits one to effortlessly consolidate general branching decisions
or valid set of inequalities. This is the strong motivating behind using the integer

3
 programming approaches for Elementary Shortest Path Problem (ESPP) [11].
80 ESPP works by finding a minimum-cost path between two nodes s and t with
the end goal that every node of Graph is visited atmost once. Its counterpart,
for finding a longest path over a graph with positive cycles has been discussed in
literature extensively, called as Longest Path Problem (LPP) [12, 13, 14]. Many
variants of ESPP are Orienteering Problem [15], Prize Collecting Travelling
85 Salesman Problem [16] and the Capacitated Profitable Tour Problem [17]. In
our case, we focused on writing an Integer Program to find a cyclic path for
police patrol routes with the objective to minimize crime response time.

3. Preliminaries

In this section we describe the terminology being used throughout the paper,
90 followed by the problem setup and our approach to solving it.

3.1. Terminology

Let G = (V, E, W ) be a weighted directed graph with vertex set V , edge set
E ⊂ V × V , and weight function W : E → R+ . Let N + (vi ) (resp. N − (vi )) be
the out-neighbors (resp. in-neighbors) of of a vertex vi . A cycle is denoted as
95 (v1 , v2 , . . . , vl , v1 ), where each consecutive vertex is connected via an edge in G,
and no vertex may be repeated (except the first vertex, v1 , at the end).
The graph G corresponds to a road network; each vertex represents an inter-
section of roads, and an edge between two vertices implies that a road connects
these two intersections.
100 For each vi ∈ V , let si be a corresponding score. In the sections to follow,
we discuss the factors which determine a vertex’s score, and its relevance to
obtaining the optimal routes. A geographic position/coordinate refers to the
real-world latitude and longitude coordinates. Each vertex vi ∈ V corresponds
to a geographic position pj that is an intersection of two or more roads.
105 Let C be a set of crimes such that each crime cj = (qj , tj , kj ) ∈ C where qj
is the geographic position corresponding to where the crime took place, tj is the

4
 timestamp corresponding to when the crime occurred, and kj is an indicator of
the type of crime (e.g. murder, theft, mugging, etc.). K is the set of all crime
types.
110 For any two geographic positions a and b, we define d(a, b) as the distance
from a to b. The nature of this distance is discussed in the section to follow.

3.2. Problem Definition

We operate under the assumption that allowing a police patrol to visit areas
with denser crime rates will stymie criminal activity in said area. In this vein,
115 our goal is to find, within a police station’s jurisdiction, the route which visits
these areas efficiently. This allows us to model finding an optimal patrol route
as finding a score-maximizing cycle within a graph. The details of said model
are discussed below:
Distance. The distance d(a, b) between two points a, b is defined as the
120 distance via road from a to b, i.e., the distance travelled in meters when one
walks from point a to point b along the shortest path on a given road network.
If there is no sequence of roads that leads from a to b, we say that d(a, b) = ∞.
Also note that this distance need not be symmetric. To incorporate traffic
information, one could instead define d(a, b) as the average time taken from a
125 to b, on a typical day on a vehicle that travels on the road speed limits.
Road Network. G represents the road network formed by the streets within
the station’s jurisdiction. It is assumed that there are no dead-ends within the
road network, i.e. there are no leaf nodes within the graph. However, if there
are dead-end streets in a given road network, one can still incorporate them
130 by adding duplicate vertices and edges that form a path back from the leaf
node. Thus, for the sake of optimization problem we are considering, we may
assume there are no dead-ends. The graph G is directed to mimic the real-world
scenario that some of streets may be one-way while others are two-way. The
graph G may have arbitrarily topology that depends on the road networks. For
135 example, one can not assume that G is planar because any number of roads may
intersect due to presence of fly-overs, tunnels, bridges, and underpasses.

5
 The graph G is weighted and the weight on each edge (vi , vj ) is given by
the corresponding value Ai,j in the adjacency matrix of the graph. For edge
weights, recall that each vertex vi ∈ V corresponds to a real-world coordinate
140 pi . Thereby, we define the weight function for an edge (vi , vj ) as W (vi , vj ) :=
d(pi , pj ).
Constraints. The patrol route must be cyclic. We assume that the police
patrol is to be dispatched from the station or a parking area. In this vein, we
select the vertex in G closest to the station, vs , to be the position where the
145 patrol’s route starts and ends. A patrol’s route will use the edges of the road
network, i.e, G, to travel from a point a to a point b. For each use of an edge
(vi , vj ), the patrol pays a price which is equal to W (vi , vj ). Once used, a road
can not be used again, i.e., a patrol can traverse an edge only once.
Finally, we assume that we may constrained on the maximum distance the
150 patrol may travel within a route (possibly to stay under a certain fuel con-
sumption limit). Hence, let B be the maximum allowed distance of the given
route.
Vertex Scores. The goal of a patrol route is two-fold: an active presence
of a police is believed to as a deterence against a crime, and secondly, in an
155 event a crime takes place, a patrol party can be the first responders who can
potentially get to the crime location quickly. In both of these scenarios, one
would want to use a patrol route that covers a large number of crime hotspots
in the jurisdiction of a police-station. We assume that the vertices and edges of
the road network include all of the potential locations that a patrol can visit.
160 The likelihood of crime event near a vertex or an edge can be modelled by the
number of crimes that took places in the vicinity. Thus, we give each vertex vi ,
a score, ψi , based on the number of crimes that occurred near it. The following
factors are taken into consideration while computing this score for each vertex:
Spatial locality. Since, we would want a patrol route to include crime
165 hotspots, a crime event that took place near a vertex should contribute a higher
value to the score of a vertex compared to a crime that took place far from
it. Let ri,j be the Euclidean distance a crime location qj from a vertex vi , the

6
 2
contribution of this crime to the score of vertex vi is given by, 1/ri,j .
Temporal closeness: Similar to distance, it also makes sense to consider the
170 time at each a crime occurred while computing its contribution to the score of a
vertex. For example, it is reasonable to assume that a crime that took place five
years ago should have much less value than a similar crime that took place a
couple of weeks ago. We observe an exponential decay in value or importance of
a crime with passing time. To model that, a incorporate a similar relation while
175 computing a vertex score. Let t∗ be a timestamp such that t∗ ≥ maxcj ∈C tj .
An exponential falloff function along with a hyperparameter τ ∈ R+ (used to
 ∗ 
t −tj
normalize the time units) is given as: exp τ

Severity: An other variable that may be considered important while com-

puting a vertex score is the severity of the crimes happening in its vicinity.
180 When a police-station is short on resources, it makes sense to only consider the
crime hotspots for sever crimes. For example, it is reasonable to assume that a
homicide crime at a location should have a higher priority than a bicycle theft
at an other location. One could assign integer parameter values ρj to each crime
type and use them as multiplicative factors while aggregating contributions of
185 all crime towards the score of a vertex.
To summarise, for a node vi ∈ V , the score is computed as,

X ρj
ψ(vi ) :=  
2 × exp t∗ −tj
cj ∈C ri,j τ
,
where, ci is a crime in the dataset of all reported crimes C. We translate this
cost function on vertices to the following cost function on edges in a straight-
forward way:
ψi,j := ψ(vi ) + ψ(vj ), ∀(vi , vj ) ∈ E

Formally, our problem can be stated as follows:

Problem 3.1 (Patrolling Route Problem). Given a road-network graph G =

190 (V, E, W ), a police-station vertex vs , a patrolling budget B, and an edge-score
function ψi,j , find a cyclic patrolling route C = (vs , vi1 , . . . , vil , vs ) in G such

7
 that cummulative score of visited vertices is maximized while ensuring that total
cost of traversing the edges in C is at most B.

In the next section, we formally study this problem in terms of its theoretical
195 complexity.

4. Methodology

In this section we discuss our approach to solving Problem 3.1. We first

show that the problem is, in fact, NP-Hard. This, unfortunately, means that
in general, the problem can not be solved efficiently using classic algorithmic
200 techniques. We propose a formulation of the problem that can efficiently solved
on a relatively smaller instances of the problem.

4.1. NP-Hardness

We show that Problem 3.1 is NP-Hard in the general case via a reduction
from Hamiltonian Path Problem, defined below.

205 Problem 4.1 (Hamiltonian Path Problem). Given an undirected unweighted

G = (V, E), does there exist a simple path that includes all the vertices in G.

It is well-known that Hamiltonian Path Problem is NP-Hard. In the following,

we show that PRP is also NP-Hard by reducing a known NP-Hard problem,
Hamiltonian Path Problem, to PRP.

210 Theorem 4.1. Patrolling Route Problem is NP-Hard.

Proof 4.1. We prove the theorem by reducing Hamiltonian Path Problem to

Patrolling Route problem. Let G be the input graph to Problem 4.1. We will
construct an input to Patrolling Route Problem as follows. Let G0 = (V 0 , E 0 , W 0 )
be the input graph for PRP. We set V 0 = V ∪{vs }, i.e., we keep the vertices in V ,
215 and add one more vertex, vs , designated as the police-station vertex. Similarly,
E 0 = E ∪ {(u, vs ), (vs , u)|u ∈ V }, i.e., the edge set of G0 contains all the edges
from G, and we add edges from ( and to) vs to (resp. from) every other vertex in

8
 the graph. Let weight or the cost function W (e) is set to 1 for every edge in E 0 .
Similarly, the score for each vertex is set to one as well, i.e., ψi := 1∀vi inV 0 .
220 The construction of this graph takes polynomial amount of time in the size of
input graph G.
We provide the input G0 , vs , ψi ∀vi ∈ V 0 , and B = n + 1 to the PRP prob-
lem. We observe that a maximum length path in G corresponds to a maximum
cycle including vs in G0 because every vertex has score one. Also, the budget,
225 B, allows for the possibility of a maximum length cycle. Hence, if the solution
to this instance of Problem3.1 is a cycle with length n + 1, we will always get a
Hamiltonian path if we remove vs from this cycle. Note that all the vertices and
edges of this path also lie in G. Thus, if a cycle of length n + 1 is returned by
PRP, a Hamiltonian path exists in G. The converse is also true. If a Hamil-
230 tonian path exists in G, then it will makes a cycle of length n + 1 with vs , and
edges added to E 0 . This completes the reduction.

We conclude that an exact solution to Patrolling Route problem is not pos-

sible in polynomial time, unless P = N P . In the following section, we propose a
novel integer programming formulation of this problem. Using the state-of-the-
235 art integer programming solvers, it becomes possible to solve Patrolling Route
problem on relatively small instances.

4.2. Integer Program

Integer linear programs (ILP) provide a uniform language for writing down
computationally hard problem. There are many open-source and commercial
240 solvers that can be used to find optimal solutions for integer programs in a
reasonable amount of time on smaller instances of problems. But an issue with
many integer programs is that they have an exponential number of constraints,
thus, it is even possible to write down a program in any of these solvers even
for small instances. Therefore, it is crucial to come up with an intger program
245 that has polynomial number of constraints. In the following, we provide first
such formulation for Patrolling Route problem.

9
 The goal of PRP problem is to find an optimal cycle C in the given input
graph G. For each edge (vi , vj ) ∈ E, we define an integer variable xij ∈ {0, 1}
such that xij = 1 if (vi , vj ) is chosen to be in the cycle C, and 0 otherwise. For
l
250 technical purposes, we also define an other set of boolean variables zij , set to 1
whenever, patrolling route cycle C passes through a vertex vl , and then uses the
edge (vi , vj ). This is a standard flow variable used in some of the constraints
below to make sure that output of the program is a single cycle C, and not a
disjoint set of cycles in the graph. For more details, the interested reader is
255 referred to [? ].

si + sj
sij :=
2
The following integer program corresponds to Problem 3.1:
The objective function of our problem can be written as:

X
maximize xij ψij
(vi ,vj )∈E

The following three constraints ensure that a vertex is not visited more than
once, and if a route uses a road to lead to a vertex than it must also use a road
260 to leave that vertex.

X
xij ≤ 1, ∀vi ∈ V (1)
(vi ,vj )∈N + (vi )

X
xji ≤ 1, ∀vi ∈ V (2)
(vj ,vi )∈N − (vi )

X X
xij − xji = 0, ∀vi ∈ V (3)
(vi ,vj )∈N + (vi ) (vj ,vi )∈N − (vi )

Every route must include the starting police-station vertex. The following
constraint says that output cycle must include thet start vertex, vs ,

X
xsj ≥ 1 (4)
(vs ,vj )∈N + (v s)

10
 X
xis ≥ 1 (5)
(vi ,vs )∈N − (vs )

An important condition for a feasible route is that it should be a single cycle,

and not just a disjoint set of cycles. We observe, that this condition is equivalent
265 to saying that every cycle should include the starting vertex. Since, every vertex
is chosen at most due to previous constraints, this will make sure that a single
cycle is returned. In the following, we outline two constraints using variables
l
zij to ensure that. The following constraints are known as the flow constraints
in the literature [? ]. Recall that Vs̄ is the set of vertices V \ {vs }:

X X
l l
zij = zji ∀vi , vl ∈ Vs̄ , vi 6= vl
(vi ,vj )∈N + (vi ) (vj ,vi )∈N − (vi )
(6)

X X X
l l
zij = zji + xij ∀vi , vl ∈ Vs̄ , vi = vl
(vi ,vj )∈N + (vi ) (vj ,vi )∈N − (vi ) (vi ,vj )∈N + (vi )
(7)
270 And lastly, we need to make sure that optimal route doesn’t cost more than
the allocated budget B, and variables take values from their allowed domains:

X
xij Wi,j ≤ B (8)
(vi ,vj )∈E

xij ∈ {0, 1}, ∀(vi , vj ) ∈ E (9)

l
zij ≤ xij ∀vl ∈ Vs̄ , ∀(vi , vj ) ∈ E (10)

l
zij ∈ {0, 1} ∀vl ∈ Vs̄ , ∀(vi , vj ) ∈ E (11)

This completes the list of constraints that make sure that the ILP returns a
feasible solution if there exists one.

11
 Remark 1. In the integer program above, we define the domain of both sets of
l
275 variables xi,j and zij to be in {0, 1} for ease of expression. However, it is not
l
necessary to restrict zij to be an integer, and it can take any value in [0, 1] to give
l
a feasible solution. This cahnge of domain for zij usually results in significant
increase in efficiency wherever a program-solver allows to restrict only a strict
subset of varialbes to be integer.

280 In the following section, we implemente this integer program using MI solver
of open-source GLPK library.

5. Preliminaries

In this section we define the terminology and notation used throughout the
paper, and formally introduce our problem.

285 5.1. Notation

6. Patrol Routing

7. Case study

In this section we discuss about our experimental results on generated road

network and real-world crime data set, for finding optimal patrol route using
290 our proposed Integer Linear Program.

Implementation. We used Python 3.3 for our implementations.For generating

road network graph,osmnx and networkx libraries were used.To implement inte-
ger linear program for optimal route finding, we used cvxpy library along with
cvxopt library.

295 7.1. Road Network Graph

We have generated few road network graph data sets around different Police
Stations i.e. Gulberg, Allama Iqbal Town, Baghban Pura, Bhati Gate and Johar
Town.Given an address of a particle police station, we generated road network
graph G = (V, E) within some distance value for each area respectively. Type

12
300 of generated graph is MultiDiGraph. Generated road network graphs are show
in Figure 1 below. Map View of generated graphs are shown in Figure 2, along
with mapping of crime data for that particular area.

(a) Road Network Graph gen-

erated for Allama Iqbal Town (b) Road Network Graph gen- (c) Road Network Graph gen-
Area having 54 number of erated for Baghbanpura Area erated for Bhaati Gate Area
nodes V and 69 number of having 70 number of nodes V having 69 number of nodes V
edges E. and 79 number of edges E. and 86 number of edges E.

Figure 1: This figure is showing Road Network Graphs generated for three areas of Lahore.

(a) Map View of Road Net- (b) Map View of Road Net- (c) Map View of Road Net-
work Graph generated for work Graph generated for work Graph generated for
Allama Iqbal Town Area. BaghbanPura Area. Bhaati Gate Area.

Figure 2: This figure is showing Map View of Road Network Graphs generated for three areas
of Lahore.Note that Crime data for particular area is also shown here in figure as gray points.

7.2. Lahore Crime dataset

Proposed Integer Linear Program also make use of the Lahore Crime dataset.
305 The dataset has information for a total of 220,719 crimes reported in police
stations from 2014 to 2016. The dataset has various attributes for each report,

13
 including crime type, geodesic coordinates, and the police station the crime was
reported in.
There are a total of 83 police stations represented in the dataset. For our
310 case study we showcase our results for the areas under the jurisdiction of the
Allama Iqbal Town , BaghbanPura and Bhaati Gate police station.
We obtain the geodesic coordinates of each crime within these areas to con-
struct our set of crimes, C. The data was pre-processed and outliers were
removed using the z-score technique, giving us total crimes shown in Table 1.

Area Name Number of entries

Allama Iqbal Town 2810
Baghbanpura 3219
Bhatti Gate 1623
Gulberg 5126

Table 1: Table is showing total number of crime points in each of the targeted area.

315 7.3. Results and Evaluation

As discussed in section above we have to maximize following objective func-

tion:
X
max xij sij
(vi ,vj )∈E

Our proposed Integer Linear Program returns a cyclic path for a given road
network graph.Starting node/vertex to find out cyclic path is set based on near
by police station location for each area .We interpret the solution returned by
our proposed ILP solver using node map file. The cyclic route returned by ILP
320 on road network graph data sets are shown in Figure 3.
Objective Function values for each area with budget value of 1000 are shown
in Table 2. below.
Objective Function values for each area with budget value of 2000 are shown
in Table 3. below.

14
 (a) Cyclic Path returned by
ILP for Allama Iqbal Town (b) Cyclic Path returned by (c) Cyclic Path returned by
Area. ILP for Baghbanpura Area ILP for Bhaati Gate Area

Figure 3: In this figure,we plotted cyclic optimal patrol route return by the Integer Linear
Program on Map. Cyclic route is shown in red color while road network graph for an area is
shown in yellow color. This route is plotted near Police Station marked by marker.

Area Name Budget Objective Function Value

Allama Iqbal Town 1000 44366.0
Baghbanpura 1000 7157.0
Bhatti Gate 1000 13986.0

Table 2: Table is showing objective function values returned by Integer Linear Program with
budget value of 1000 for each area respectively.

Area Name Budget Objective Function Value

Allama Iqbal Town 2000 44897.0
Baghbanpura 2000 7157.0
Bhatti Gate 2000 13986.0

Table 3: Table is showing objective function values returned by Integer Linear Program with
budget value of 2000 for each area respectively.

325 8. Concluding remarks

9. Acknowledgements

This work was supported by the grant received to establish the Crime Inves-
tigation and Prevention Lab, associated with the National Center in Big Data

15
 and Cloud Computing, funded by the Planning Commission of Pakistan.

330 References

[1] C. R. Jeffery, Pioneers in criminology: The historical development of crim-

inology, The Journal of Criminal Law, Criminology, and Police Science
50 (1) (1959) 3–19.

[2] H. Chen, W. Chung, J. J. Xu, G. Wang, Y. Qin, M. Chau, Crime data

335 mining: A general framework and some examples, IEEE Computer 37 (4)
(2004) 50–56.

[3] H. Hassani, X. Huang, E. S. Silva, M. Ghodsi, A review of data mining

applications in crime, Statistical Analysis and Data Mining 9 (3) (2016)
139–154.

340 [4] V. Estivill-Castro, I. Lee, Data mining techniques for autonomous explo-
ration of large volumes of geo-referenced crime data, in: Proc. of the 6th
International Conference on Geocomputation, Citeseer, 2001, pp. 24–26.

[5] M. Dewinter, C. Vandeviver, T. V. Beken, F. Witlox, Analysing the police

patrol routing problem: A review, ISPRS International Journal of Geo-
345 Information 9 (3) (2020) 157.

[6] A. Mukhopadhyay, C. Zhang, Y. Vorobeychik, M. Tambe, K. Pence,

P. Speer, Optimal allocation of police patrol resources using a continuous-
time crime model, in: International Conference on Decision and Game
Theory for Security, Springer, 2016, pp. 139–158.

350 [7] L. Li, Z. Jiang, N. Duan, W. Dong, K. Hu, W. Sun, Police patrol service
optimization based on the spatial pattern of hotspots, in: Proceedings of
2011 IEEE International Conference on Service Operations, Logistics and
Informatics, IEEE, 2011, pp. 45–50.

16
 [8] D. Portugal, R. Rocha, A survey on multi-robot patrolling algorithms,
355 in: Doctoral conference on computing, electrical and industrial systems,
Springer, 2011, pp. 139–146.

[9] H. Chen, T. Cheng, S. Wise, Developing an online cooperative police patrol

routing strategy, Computers, Environment and Urban Systems 62 (2017)
19–29.

360 [10] H. Chen, T. Cheng, S. Wise, Designing daily patrol routes for policing
based on ant colony algorithm., ISPRS Annals of Photogrammetry, Remote
Sensing & Spatial Information Sciences 2.

[11] L. Taccari, Integer programming formulations for the elementary shortest

path problem, European Journal of Operational Research 252 (1) (2016)
365 122–130.

[12] D. Karger, R. Motwani, G. D. Ramkumar, On approximating the longest

path in a graph, Algorithmica 18 (1) (1997) 82–98.

[13] H. N. Gabow, Finding paths and cycles of superpolylogarithmic length,

SIAM Journal on Computing 36 (6) (2007) 1648–1671.

370 [14] A. Björklund, T. Husfeldt, S. Khanna, Approximating longest directed

paths and cycles, in: International Colloquium on Automata, Languages,
and Programming, Springer, 2004, pp. 222–233.

[15] P. Vansteenwegen, W. Souffriau, D. Van Oudheusden, The orienteering

problem: A survey, European Journal of Operational Research 209 (1)
375 (2011) 1–10.

[16] E. Balas, The prize collecting traveling salesman problem, Networks 19 (6)
(1989) 621–636.

[17] M. K. Jepsen, B. Petersen, S. Spoorendonk, D. Pisinger, A branch-and-cut

algorithm for the capacitated profitable tour problem, Discrete Optimiza-
380 tion 14 (2014) 78–96.

17
Appendix

In this section we discuss how the objective values were computed.

Evaluating our methodology

18