Intelligent Route Planning for Effective Police Patrolling in a Peruvian District

Abstract

Citizen security directly influences life quality and is a great source of concern in Latin America. A scheduling and vehicle routing model is proposed for the allocation and routing of police resources, increasing visits in locations with a higher crime rate, and strategic standby locations based on real data.

1 Introduction

The improvement project is located in the district of La Victoria in the metropolitan city of Lima, Peru, where it seeks to increase the presence of the patrol corps with the current availability of resources. District limits, critical points, and points of interest are defined, which are areas of historical criminal activity, high mobilization, or public areas such as squares, parks, etc. For the allocation of resources, which in this case are the patrol corps personnel, a linear programming model is proposed, imposing constraints on the work hours of resources, critical days of the week, and time windows. The final deliverable of the project is a set of patrol routes that ensures police presence at the study site while minimizing travel distance.

2 Current Situation

La Victoria district is part of Lima Metropolitana, which has an extension of 8.74 km² and a total of 166, 657 citizens. It is divided into 43 zones, as shown in Fig. 1 [1].

Fig. 1

Zones distribution in La Victoria district [1]

According to criminal statistics calculated from 2017 to 2019, presented by the district administration, it is evident that the biggest problem it faces is citizen insecurity (crimes against private property).

Therefore, there is a latent need to improve the surveillance and routing system of personnel to ensure an adequate reach (Table 1).

Table 1 Crime typology statistics from 2017 to 2019 [1]

The current administration has the following resources to ensure district security (Table 2):

Table 2 Current district resources per location [1]

Citizens who live or interact with places with low security are those who, according to studies, report low levels of well-being. In the same way, people who show confidence in the police force are those who feel less fear of being victims of crime. The study of [3] concludes that places with high violence are key points to improve the perception of the police, alongside spaces that facilitate exposure of citizens to patrols, such as parks, hospitals, schools, etc. For this reason, a set of points of interest were defined to ensure police presence in these high-exposure locations (Fig. 2; Table 3).

Fig. 2

(a) Points of interest distribution, (b) historical crime distribution

Table 3 Statistics of points of interest

3 Contribution

A resource-scheduling model is proposed, which aims to maximize a fictitious objective function that forces a greater allocation of security agents on Fridays and Saturdays, in shifts from 11:00 am to 11:00 pm. In addition, a security agent routing model is proposed using a VRP model formulation. In this way, we seek to reach adequate coverage in the most dangerous areas at night and during the day, increasing the perception of safety by the population while visiting the previously mentioned points of interest. Initially, the first resource allocation model is presented and then the vehicle routing model.

3.1 Security Agent Scheduling Model

The following sets are defined, containing different values whose meaning is explained in Table 4:

• I: Agent travel mode

• J: Agent entry work shift (4 h each)

• K: Day of the week an agent starts its shift

Table 4 Meaning of set values (each column represents one value)

3.2 Security Agent Scheduling Model – Decision Variables

The decision variable is defined as follows:

• X_ijk: Number of agents of type i that starts its shift in turn j in day k.

An agent that starts its shift must also work in the next immediate shift, for 6 days a week. It is allowed a single day of rest in the week. In Fig. 3 a pair of examples is shown to further understand these implications, where the entry position is colored in green, the X_ijk variable is present in the shifts and days an agent is actively working and the rest slots are colored in red.

Fig. 3

Example of X_ijk presence along shifts and days

3.3 Security Agent Scheduling Model – Objective Function

The objective function is defined as follows:

$$ \mathit{\operatorname{Max}}\ Z={\sum}_{ijk}{X}_{ijk}\ast G{1}_j\ast G{2}_k $$

(1)

Where G1_j and G2_k are factors that drive a higher allocation of resources in certain shifts and days of the week:

• G1_j: 1.5 if j = 3, 4 or 5. Else, it takes the value of 1.

• G2_k: 2 if j = 5 or 6. Else, it takes the value of 1.

3.4 Security Agent Scheduling Model – Constraints

Two constraints are needed to ensure a minimum and maximum required quantity of agents:

Constraint 1

The number of agents of a given travel mode, located in each shift of each day of the week, must be greater than a previously defined minimum number (Q_i), which depends solely on the travel mode i of the agent. Hereby, it is ensured that each shift is adequately covered with personnel. To achieve this requirement on shift j of day k, it is needed to take into account agents X_ijk that start their shifts in j and (j-1), workdays k, (k-1), (k-2), (k-3), (k-4), and (k-5), with a work coverage of 8 continuous hours and the working range of 6 days a week. Next, the representation of the constraint for the wagon agent (i = 3) for shift 1 (j = 1) on Monday (k = 1) is shown. The same logic is applied for each combination j and k (Fig. 4):

Fig. 4

Example of constraint 1 evaluation for i = 3, j = 1, and k = 1

$$ {\sum}_{k=\textrm{1..7}}{X}_{36k}-{X}_{361}+{\sum}_{k=\textrm{1..7}}{X}_{31k}-{X}_{312}\ge {Q}_3 $$

(2)

Constraint 2

The number of agents in each category, located in each shift of each day of the week must be less than the maximum number of agents available, which depends only on category i of the agent:

$$ {\sum}_{jk}{X}_{ijk}\le {C}_i $$

(3)

The data corresponding to the minimum and the available number of agents per shift are as follows (Table 5):

Table 5 Minimum quantities available per agent

3.5 Agent Routing Model

The CVRP model presented below follows the logic of a variant proposed by Toth and Vigo [2].

3.6 Agent Routing Model – Decision Variables

The model generates m routes, where each route is carried out by a single agent. On each route, the agent visits each location associated with the route only once. A total of n locations are visited only once by a different route. In our case, La Victoria district has n = 186 and m = 23. As the district has three police stations, vehicles depart from these locations as depots. For ease of planning, the district is divided into three different zones, as shown in Fig. 5, where the number of vehicles, the number of locations to visit, and the maximum number of visited locations (C) per route depends on each area’s available resources, as shown in Table 6.

Fig. 5

Zones in La Victoria

Table 6 Zone’s characteristics

The agents start their route from the assigned police station, indexed by 0, carry out their routes, and return to the station.

The indices of the model are presented below, which depend on the zone as previously described:

• m: Index of the route traveled by an agent.

• n: Index of the location to visit

• i = 0,…,n: Index of the location from which the agent departs.

• j = 0,…,n: Index of the location to which the agent arrives.

The decision variables of the model are presented below:

• X_ij:Binary variable that indicates that the agent starts from location i and travels to location j.

• u_i:Integer support variable, associated with each location indexed by a i > = 1. It allows the satisfaction of the subtour elimination constraint.

3.7 Agent Routing Model – Objective Function

The objective is to find the optimal trajectories that each route should follow, such that the total distance traveled by the agents is minimized:

$$ \operatorname{Min}\ \textrm{Z}={\sum}_i{\sum}_j{d}_{ij}\ast {X}_{ij} $$

(4)

Where d_ij is the distance necessary to travel the linear section between locations i and j. It comes from a matrix of Euclidean distances between pairs of locations, using the latitude and longitude coordinates. Given that these distances are merely an approximation of the real distances to travel, it is of interest to have the sequence of locations to visit on each route. With this sequence, routes can be generated that, when traveling through streets, will have different distances. When i = j, the value of d_ij is infinite, causing the model to avoid inserting recurring visits.

3.8 Agent Routing Model – Constraints

First, the constraints that limit the number of entrances and exits to each location are defined. In Eqs. 5 and 6, it is indicated that the number of visits to the police station (indexed by 0) must be equal to the number of routes, while in Eqs. 7 and 8 it is indicated that the rest of the locations must be visited only one once by a single route.

$$ {\sum}_i{X}_{i0}=m $$

(5)

$$ {\sum}_j{X}_{0j}=m $$

(6)

$$ {\sum}_i{X}_{ij}=1,\forall j\in \left\{1,\dots, \textrm{n}\right\} $$

(7)

$$ {\sum}_j{X}_{ij}=1,\forall i\in \left\{1,\dots, \textrm{n}\right\} $$

(8)

Finally, the capacity constraint and elimination of subtours is defined, following the formulation of Miller-Tucker-Zemlin [2]:

$$ {u}_i-{u}_j+{X}_{ij}\ast C<=C-1\forall i,j\in \left\{1,\dots, \textrm{n}\right\},i\ne j $$

(9)

4 Results

The allocation model gives, as a result, the number of agents of each travel type i, that begin its shift j in day k (X_ijk), which is presented in Fig. 6.

Fig. 6

Scheduled number of agents by table type, shift, and day

The implemented routing model provides a series of routes that cover the locations with the highest criminal incidence in La Victoria. The visit sequences of each route by each zone are presented in Fig. 7.

Fig. 7

(a) Travel routes by zone 1, (b) Travel routes by zone 1, (c) Travel routes by zone 1

5 Conclusions

The proposed models systematically cover two important needs of the current police system, referring to the management of police resources, ensuring the availability of security agents at the most critical hours and days, and establishing standard routes to be followed during patrol work, ensuring coverage of critical locations. The model for assigning human resources to shifts provides a flexible tool that can be enriched by new procedures determined by the police station, optimizing new situations easily. The routing model generates a set of standard routes corresponding to each of the sectors, which cover the most critical locations in the district, considering data from 2017–2019. The assignment of agents to each route can be done with total freedom, at the discretion of the police station, without losing the ability to adapt as it can be updated according to variations in the criminal dynamics of the district.