Hybrid heuristic approach for generalized police officer patrolling problem

1 Introduction

In the fields of information engineering and science, to solve various social and economic problems, these problems are generally structured as mathematical models, and solutions are found using algorithms that are suited to that structure. Many of these problems are modeled using discrete graphs, and there are many studies on them.

One of the problems modeled by discrete graphs is the routing problem. Routing problems are classified as node routing problems (NRPs), which traverse the nodes of a graph, and arc routing problems (ARPs), which traverse the edges (or arcs). A typical NRP is the traveling salesperson problem (TSP). The TSP is a problem that involves finding the minimum-cost route that visits every vertex exactly once. The vehicle routing problem (VRP) (Dantzig and Ramser, 1959) is a generalization of the TSP. This problem involves planning transportation from a distribution center to multiple customers using trucks or other transportation methods. Both the TSP and VRP are NP-hard; thus, evolutionary algorithms, such as genetic algorithms (GAs), have been studied (Elatar et al., 2023).

The most famous ARP is probably the Euler circuit problem. This problem determines whether there exists a circuit that traverses all edges exactly once for a given graph, and this problem is solvable in polynomial time. The Chinese postman problem (CPP) (Mei-Ko, 1962), which is a generalization of the Euler circuit problem, involves determining whether a tour exists for a post officer in a given area within a given amount of time that starts and ends at the post office. The post officer must traverse every street in the area at least once; however, they may traverse any street several times. The CPP on undirected or directed graphs can be solved in polynomial time (Edmonds and Johnson, 1973). Papadimitriou (1976) showed that the CPP on mixed graphs is NP-complete. Mixed graphs represent realistic situations in urban areas with both two- and one-way streets. The rural postman problem (RPP) is a generalization of the CPP with a given set of edges that must be traversed by a post officer. This problem considers the fact that, in rural areas, not every street has a delivery destination. Lenstra and Rinnooy-Kan (1976) and Lenstra and Rinnooy-Kan (1981) showed that the optimization version of the RPP on undirected or directed graphs is NP-hard. The capacitated ARP (CARP) is an ARP corresponding to the VRP, which belongs to the NRP. The CPP, RPP, and CARP correspond to mathematical models of real social problems such as postal delivery, delivery planning, snow shoveling, and garbage collection. Finding exact solutions for the CPP and RPP optimization problems is intractable, along with the TSP and VRP; thus, various heuristic methods have been proposed for these problems. Recent examples include methods using GAs (Gil-Gala et al., 2023), the Tabu search algorithm (Tang et al., 2024), and ant colony optimization (Sgarro and Grilli, 2024).

Police patrols play a crucial role in preventing crimes and accidents, thereby ensuring public safety within their jurisdictions. Recent studies such as (Kim et al., 2023; Dewinter et al., 2020; Samanta et al., 2022) have proposed methods for optimizing patrol routes. These approaches primarily employ heuristic algorithms to generate efficient patrol routes for multiple officers operating within the shared area.

Recently, Tohyama and Tomisawa (2022) proposed the police officer patrol problem (POPP) as a mathematical model of the patrolling route problem of police officers (or security guards), and showed that the decision problem is NP-complete (Tohyama and Tomisawa, 2022). Patrolling areas generally include one- and two-way streets; thus, the POPP is modeled using a mixed graph. At each intersection, police officers may conduct security checks visually even if they do not traverse the streets connecting to it. If the POPP is considered a CPP model, it is necessary to find a patrolling route that traverses all streets. The POPP model allows some streets to conduct visual security checks without traversing, making it possible to find more efficient patrolling routes. In addition, Tomisawa and Tohyama showed that the POPP on weighted digraphs is NP-complete (Tomisawa and Tohyama, 2024).

In this study, we introduce the generalized POPP (GPOPP) as a model to adapt the POPP to more realistic patrolling routes by police officers. The POPP model requires that all areas be guarded. However, in reality, some streets require security because important facilities are located there, and some roads do not necessarily require security (Chainey et al., 2021). In addition, there are cases where a patrolling route needs to be found that can be patrolled within a given time. Therefore, we define the GPOPP as an optimization problem with the following two objectives. The first objective is to find the shortest patrolling route among the routes that traverse all high-security streets. The second objective is to find a patrolling route that guards as large a given area as possible (maximizes coverage).

Many GAs have been proposed to solve multi-objective problems (Deb et al., 2002; Sardinas et al., 2006; Pizzuti, 2009; Ghoseiri and Ghannadpour, 2010; Aiello et al., 2012; Akyurt et al., 2015; Yu et al., 2015; Lu et al., 2019). The hybrid sampling strategy based multi-objective evolutionary algorithm (MoEA-HSS) (Zhang et al., 2014) is based on a hybrid sampling strategy that combines a vector-valued GA (VEGA) (Schaffer, 2014) and a sampling strategy according to the Pareto dominating and dominated relationship-based fitness function (PDDR-FF) (a goodness-of-fit function based on Pareto dominance–dominance relations). The MoEA-HSS has demonstrated effectiveness for several problems. The Jaya algorithm (Rao, 2016) is a meta-heuristic algorithm with a very simple structure based on the concept that solutions obtained for a particular problem progress toward the best solution and avoid the worst solution. We propose a hybrid heuristic approach that combines the MoEA-HSS with an improved Jaya algorithm, and demonstrate its effectiveness through numerical experiments.

The remainder of this paper is organized as follows. In Section 2, we formally define the Generalized Police Officer Patrolling Problem (GPOPP) and present the necessary graph-theoretical concepts. Section 3 provides a mathematical formulation of the GPOPP as a bi-objective optimization problem. In Section 4, we describe the proposed hybrid heuristic method that combines the MoEA-HSS and an improved Jaya algorithm. Section 5 presents the results of the numerical experiments conducted to evaluate the performance of the proposed method. Finally, Section 6 concludes the paper and discusses potential directions for future research.

2 Generalized police officer patrolling problem (GPOPP)

In this study, we introduce a bi-objective problem that can be applied to more realistic problems based on the POPP, which is NP-complete edge routing decision problem, and propose a heuristic algorithm to solve the problem. One police officer (or security guard or robot) is assigned to a security area, and each officer patrols his/her assigned area. Each street through which a police officer is traversed during a patrol is considered guarded. In addition, except for streets with important facilities, police officers are allowed to visually confirm each street adjacent to an intersection without traversing it. The GPOPP is a bi-objective optimization problem with the following two objectives: One is to find the patrolling route with the shortest length, and the other is to find the route with the largest guarded area. Here, we note that all high-security streets must be traversed. In this section, we define the notion in graph theory necessary to formulate the GPOPP.

Throughout this paper, let N = { 1 , 2 , 3 , ⋯ } be the set of all natural numbers. Let I k = { 0 , 1 , 2 , ⋯ , k − 1 } and I k + = { 1 , 2 , 3 , ⋯ , k } for each k ∈ N. Let G = ( V , E , A ) be a connected simple mixed graph, where V is the set of vertices, E is the set of undirected edges and A is the set of arcs. Hereafter, the number of vertices in G is denoted as n and fixed to V = { 1,2 , … , n }. Here, we denote an undirected edge by { u , v } and an arc by ( u , v ). The term “edge” refers to either an undirected edge or an arc, denoted by ⟨ u , v ⟩. Thus, if ⟨ u , v ⟩ is an undirected edge, ⟨ u , v ⟩ = ⟨ v , u ⟩; if it is an arc, ⟨ v , u ⟩ ∉ A.

Let m ∞ be a sufficiently large positive integer. Then, let d be a function from V 2 to N satisfying the following conditions: for all u, v ∈ V

• 1. d ( u , v ) = d ( v , u ),
• 2. ⟨ u , v ⟩ ∈ E ∪ A or ⟨ v , u ⟩ ∈ E ∪ A ⇒ d ( u , v ) < m ∞,
• 3. ⟨ u , v ⟩, ⟨ v , u ⟩ ∉ E ∪ A ⇒ d ( u , v ) = m ∞.

Here, d ( u , v ) denotes the distance between u and v if there exists an edge ⟨ u , v ⟩ (or ⟨ v , u ⟩). For convenience, d ( u , v ) = m ∞ when there is no edge between u and v.

Let H be a subset of E ∪ A. We consider that there exist important facilities on each edge in H that must be stopped at. Each edge in H is considered a high-security edge. A sequence s: v 0, v 1, v 2, ⋯, v k of vertices is considered a patrolling route on G if the following conditions hold:

• 1. The sequence s is a walk. That is, ⟨ v i , v i + 1 ⟩ ∈ E ∪ A for each i ∈ I k.
• 2. All edges in H are on s. That is, if { u , v } ∈ H, there exists i ∈ I k satisfying u = v i and v = v i + 1 or u = v i + 1 and v = v i. If ( u , v ) ∈ H, there exists i ∈ I k satisfying u = v i and v = v i + 1.
• 3. v k = v 0. That is, the walk s is closed.

The length L ( s ) of a patrolling route s is the total sum of the distances of all edges on s and is calculated as follows:

L s = ∑ i = 0 k − 1 d v i , v i + 1 .

For a patrolling route s, let V s = { v i ∈ V | i ∈ I k } and E s = { ⟨ v i , v i + 1 ⟩ ∈ E ∪ A | i ∈ I k }. Here, V s denotes the set of vertices on s, and E s denotes the set of edges traversed in s. Let ⟨ u , v ⟩ be an edge of G. If u ∈ V s or v ∈ V s, the edge is considered guarded. In particular, if ⟨ u , v ⟩ ∈ E s, said the edge is considered guarded by traversing; otherwise, if exactly one vertex of u and v is in V s, the edge is considered guarded by visual confirmation.

Let E s g = { ⟨ u , v ⟩ ∈ E ∪ A | u ∈ V s or v ∈ V s } be a set of edges guarded by a patrolling route s. Then, the total sum of the distances of all edges guarded by s is denoted as ∑ ⟨ u , v ⟩ ∈ E s g d ( u , v ). The total sum of the distances of all edges of G is denoted as ∑ ⟨ u , v ⟩ ∈ E ∪ A d ( u , v ); thus, the covered ratio c o v ( s ) of G by s is defined as follows:

c o v s = ∑ 〈 u , v 〉 ∈ E s g d u , v ∑ 〈 u , v 〉 ∈ E ∪ A d u , v − 1 .

Similarly, c o v ̄ ( s ) = 1 − c o v ( s ) is called the noncovered ratio of G by s. For any patrolling route s of G, 0 < c o v ( s ) ≤ 1 and 0 ≤ c o v ̄ ( s ) < 1 holds.

An example of a patrolling route for a mixed graph is illustrated in Figure 1. The red edges represent high-security edges, and the blue line indicates a patrolling route. The green area is guarded by this patrolling route. In particular, the green area not on the patrolling route is guarded by visual confirmation. The graph shown in Figure 1 has 60 vertices and 104 edges. Let us assume that the distance between any two vertices is one. Then, the length of the patrolling route is 44. The total sum of the distances of the guarded edges is 84, and the covered and noncovered ratios are 0.808 and 0.192, respectively.

Let v i ( i ∈ I k ) be a vertex on a patrolling route s: v 0, v 1, v 2, ⋯, v k of a mixed graph G = ( V , E , A ). If ⟨ v i − 1 , v i ⟩, ⟨ v i , v i + 1 ⟩ ∉ H and ⟨ v i − 1 , v i + 1 ⟩ ∈ E ∪ A, then the sequence s ′: v 0, v 1, v 2, ⋯, v i − 1, v i + 1, ⋯, v k − 1, v k by removing v i from s is also a patrolling route of G (In the case i = 0, s ′: v 1, v 2, v 3, ⋯, v k − 1, v 1 is a patrolling route if ⟨ v k − 1 , v k ⟩, ⟨ v 0 , v 1 ⟩ ∉ H and ⟨ v k − 1 , v 1 ⟩ ∈ E ∪ A). Some edges guarded by visual confirmation from v i on s may not be guarded on s ′, although two edges removing from s are guarded by visual confirmation. That is, c o v ̄ ( s ) ≤ c o v ̄ ( s ′ ) holds. On the other hand, the increase or decrease in the length of the sequence v 0, v 1, v 2, ⋯, v k does not determine the increase or decrease in the length of the patrolling route. That is, L ( s ′ ) ≤ L ( s ) holds if the triangle inequality d ( v i − 1 , v i + 1 ) ≤ d ( v i − 1 , v i ) + d ( v i , v i + 1 ) (d ( v k − 1 , v 1 ) ≤ d ( v k − 1 , v k ) + d ( v 0 , v 1 ) in the case i = 0) is satisfied, otherwise, L ( s ) ≤ L ( s ′ ) holds.

3 Formulation

The GPOPP is a bi-objective optimization problem that obtains a patrolling route with the shortest length and the lowest noncovered ratio for a given connected simple mixed graph G = ( V , E , A ), a set H ⊆ E ∪ A of high-security edges, and a distance function d : V 2 → Z +. The parameters n, c u , v, h u , v, and d u , v for the GPOPP are defined as follows:

• (i) n: number of vertices.
• (ii) c u , v = 1 , if ⟨ u , v ⟩ ∈ E ∪ A , 0 , otherwise .

If G has an undirected edge { u , v }, c u , v = c v , u = 1; if G has an arc ( u , v ), c u , v = 1 and c v , u = 0.

• (iii) h u , v = 1 , if ⟨ u , v ⟩ ∈ H or ⟨ v , u ⟩ ∈ H , 0 , otherwise .

Note that h u , v = h v , u = 1 even if ⟨ u , v ⟩ is an arc in H.

• (iv) d u , v = d ( u , v ) for each ( u , v ) ∈ V 2.
• (v) c u , v ′ = 1 , if c u , v + c v , u > 0 , 0 , otherwise .

In other words, c u , v ′ = 1 when there is an edge that has endpoints u and v; c u , v ′ = 0 when there is no edge between them in the mixed graph G. c u , v ′ is immediately obtained from c u , v.

The decision variables for the GPOPP are x u , v and y u , v. The decision variable x u , v represents the number of times the edge ⟨ u , v ⟩ is traversed from u to v. If there exists no edge between u and v, x u , v = 0. The decision variable y u , v is expressed as follows:

• (vi) y u , v = 1 2 , if ∑ k = 1 n x u , k > 0 and ∑ k = 1 n x v , k > 0 , 1 , if ∑ k = 1 n x u , k > 0 and ∑ k = 1 n x v , k = 0 , 0 , otherwise .

We remark that ∑ k = 1 n x u , k is strictly positive if and only if the vertex u is in V s. Thus, y u , v = y v , u = 1 2 when both u and v are on s; y u , v = 1 and y v , u = 0 when u is on s even though v is not on s. Note that y u , v = y v , u = 1 2 does not mean that ⟨ u , v ⟩ or ⟨ v , u ⟩ are in E s. Then, ∑ u = 1 n ∑ v = 1 n c u , v ′ d u , v y u , v denotes the total length of edges guarded by the patrolling route s.

Let x = ( x 1,1 , x 1,2 , ⋯ , x n , n ) be an n 2-tuple of nonnegative integers. The mathematical model for the GPOPP is formulated as follows:

minimize f 1 x = ∑ u = 1 n ∑ v = 1 n d u , v x u , v , minimize f 2 x = 1 − ∑ u = 1 n ∑ v = 1 n c u , v ′ d u , v y u , v ∑ u = 1 n − 1 ∑ v = u + 1 n c u , v ′ d u , v − 1 .

The objective function f 1 is the function that minimizes the total length of the patrolling route, and f 2 is the function that minimizes the noncovered ratio.

The following constraints must be satisfied: where V x = u ∈ V ∑ v = 1 n x u , v > 0 is the same as V s defined in the previous section. Equation 1: The number of times to directly traverse from u to v is nonnegative. Equation 2: If there exists no edge between u and v or even if there exists an arc from v to u, it is not possible to directly traverse from u to v. Equation 3: The edge ⟨ u , v ⟩ (or ⟨ v , u ⟩) must be traversed if it is a high-security edge. Equation 4: For any vertex u, the number of times traversed from other vertices to u is the same as the number of times traversed from u to other vertices.

x u , v ≥ 0 ∀ u , v ∈ V , (1)

c u , v = 0 ⇒ x u , v = 0 ∀ u , v ∈ V , (2)

h u , v = 1 ⇒ x u , v + x v , u > 0 ∀ u , v ∈ V , (3)

∑ v = 1 n x v , u = ∑ v = 1 n x u , v ∀ u ∈ V , (4)

W ≠ ϕ ∧ W ≠ V x ⇒ ∑ u ∈ W ∑ v ∉ W x u , v > 0 ∀ W ⊆ V x , (5)

Suppose that x does not satisfy Equation 5. Then, there exists a nonempty proper subset W of V x that satisfies ∑ u ∈ W ∑ v ∉ W x u , v = 0. This means that any edge ⟨ u , v ⟩ incident to u ∈ W and v ∈ V x − W is not traversed; therefore, x represents two or more separate walks. In other words, based on Equation 5, the patrolling route is a continuous closed walk.

The notation used in formulating the mathematical programming model for GPOPP is summarized as follows:

• Parameters
• c u , v 1 if ⟨ u , v ⟩ ∈ E ∪ A, 0 otherwise
• c u , v ′ 1 if ⟨ u , v ⟩ ∈ E ∪ A or ⟨ v , u ⟩ ∈ E ∪ A, 0 otherwise
• d u , v same as d ( u , v )
• h u , v 1 if ⟨ u , v ⟩ ∈ H or ⟨ v , u ⟩ ∈ H, 0 otherwise
• n number of vertices
• Decision variables
• x u , v number of traversing from u to v
• y u , v 1 2 if both u , v on s, 1 if only one of u or v is on s 0 otherwise,
• Objective functions
• f 1 minimize the length of the patrolling route L ( s )
• f 2 minimize the length of the non-covered ratio c o v ̄ ( s )

4 Proposed methods

4.1 Framework

The GPOPP requires two conflicting objectives to be considered simultaneously: minimizing the total length of the patrolling route and minimizing its noncoverage ratio. Many Pareto-optimal solutions with incomparable qualities must be generated for the decision-maker. In this section, we introduce a hybrid heuristic approach based on the MoEA-HSS and the improved Jaya algorithm for the GPOPP.

The MoEA-HSS is based on a hybrid sampling strategy that combines the VEGA and a sampling strategy according to the PDDR-FF. The sampling strategy of the VEGA is a natural extension of simple GAs in the sense that the individuals are divided and reproduced independently according to each objective function. It prefers the edge region of the Pareto front with less time complexity, and the qualities of the solution are not good because of the selection bias. Conversely, the PDDR-FF-based sampling strategy tends to converge toward the central area of the Pareto front. The combination of these two mechanisms is expected to maintain both the convergence rate and distribution performance. The Jaya algorithm modifies a given individual to move closer to the best solution and away from the worst solution based on the best and worst candidates in the population. The Jaya algorithm is expected to accelerate the convergence rate.

The main framework of the proposed method is shown in Figure 2. The assemblage of chromosomes in each generation t is divided into two groups A ( t ) and P ( t ). A ( t ) and P ( t ) are called Archive and Population, respectively. The Pareto solution set update shown in the figure follows the same procedure as in the MoEA-HSS (Zhang et al., 2014) framework.

Let n p be a positive constant. Initially, archive is set to empty, and the initial population consists of n ( 0 ) ( ≥ n p ) individuals. For each individual p in population, the objective functions f 1 ( p ) and f 2 ( p ) and the evaluation function e v a l ( p ) are calculated. We adopt the PDDR-FF as the evaluation function e v a l. Let g d ( p ) be the number of individuals that can be dominated by the individual p and g n d ( p ) be the number of individuals that can dominate the individual p. Then,

e v a l p = g d p + 1 g n d p + 1 .

Based on these values, the Pareto-optimal solution in the population is obtained and maintained.

The following three phases are executed in each generation t. In each generation t ( > 1 ), archive A ( t ) contains n a individuals and population P ( t ) contains n ( t ) ( ≥ n p ) individuals generated by genetic operations (Crossover and Mutation) and Improved Jaya algorithm in the previous generation.

• Phase 1: generating mating pools

• 1. Using the VEGA, two subpopulations M 1 ( t ) and M 2 ( t ), called mating pools from P ( t ), are created. M 1 ( t ) is created by 1 2 n p individuals selected from P ( t ) based only on the value of f 1. Then, the value of f 2 is ignored. Similarly, M 2 ( t ) is created by 1 2 n p individuals selected from P ( t ) based only on the value of f 2.
• 2. An integrated mating pool M ( t ) is created by combining the two mating pools M 1 ( t ) and M 2 ( t ) and Archive A ( t ).

• Phase 2: create P ( t + 1 )

• For individuals in the integrated mating pool M ( t ), Crossover and Mutation operations and the Improved Jaya algorithm are applied, and the t + 1-th generation population P ( t + 1 ) consisting of n p or more individuals is created. These three operations are described in detail in the following.

• Phase 3: create A ( t + 1 )

• 1. For each p in A ( t ) and P ( t + 1 ), the values f 1 ( p ), f 2 ( p ), and e v a l ( p ) are computed.
• 2. A ( t + 1 ) is created by selecting n a individuals from A ( t ) and P ( t + 1 ) in the order of decreasing e v a l value.

Phases 1 – 3 of the proposed method are depicted in Figure 3.

4.2 Chromosome representation and notation

The most natural route expression is adopted as the chromosome expression in the proposed method. For example, if a sequence s: v 0, v 1, v 2, ⋯, v k of vertices is a legal patrolling route, its chromosome representation is a k-tuple p = ( v 0 , v 1 , v 2 , ⋯ , v k − 1 ). The first component of p is considered the starting point. By rotating the genes in p, the chromosome at which the starting point is replaced with v i is denoted by p ( i ). That is,

p i = v i , v i + 1 , ⋯ , v k − 1 , v 0 , v 1 , ⋯ , v i − 1 .

Since GPOPP does not have a fixed starting point, all chromosomes p ( 0 ), p ( 1 ), p ( 2 ), ⋯, p ( k ) represent the same patrolling route. This representation p ( i ) obtained by routing the genes of chromosome p is useful for explaining the genetic operations introduced below. Let V = V be the set of all genes and V p = { v i | 1 ≤ i < k } be the set of genes contained in chromosome p. For each gene v ∈ V, let I v p = { i ∈ I k | v i = v } be the set of gene loci whose gene is v. Let E = E ∪ A and E p = { ⟨ v i , v i + 1 ⟩ | 0 ≤ i < k − 1 } ∪ { ⟨ v k − 1 , v 0 ⟩ } be a set of pairs of adjacent genes in chromosome p and H = H. Genes v k − 1 and v 0 are also considered adjacent. Here, V p = V s and E p = E s. Let v i − and v i + denote the previous and next genes of v i ( 0 ≤ i < k ) in chromosome p, respectively. Here, these gene loci are i − = i − 1 ( mod k ) and i + = i + 1 ( mod k ), where x (mod k) denotes the least nonnegative remainder when x is divided by k. Then, the two sets W u p and W ̄ u p of the gene loci are defined as follows:

• • For each gene u ∈ V p,

W u p = i ∈ I k | v i = u , ⟨ v i − , v i ⟩ , ⟨ v i , v i + ⟩ ∈ E p \ H , ⟨ v i − , v i + ⟩ ∈ E .

• • For each gene u ∉ V p,

W ̄ u p = i ∈ I k | ⟨ v i , v i + ⟩ ∈ E p \ H and ⟨ v i , u ⟩ , ⟨ u , v i + ⟩ ∈ E .

4.3 Initial population

As mentioned in Section 4.1, an initial population consisting of n p individuals is constructed. Each individual in the initial population is generated as follows:

• 1. First, the direction traversing each high-security undirected edge is decided randomly, since because all high-security edges are traversed on every patrolling route.
• 2. Determine the order of traversing high-security edges randomly.
• 3. Generate chromosome q representing the patrolling route that traverses high-security edges in the order determined in step 2. Here, to maintain the diversity of the initial population, two consecutive high-security edges are connected by a shortest path via a randomly selected vertex. The shortest walk w [ u , v , u ′ ] from vertex u to u ′ via v can be determined using the Dijkstra’s algorithm.
• 4. The patrolling route represented by the generated chromosome q may be able to reduce the total length without changing the noncoverage rate. Therefore, the improvement procedure described below is used for chromosome q generated in step 3.

The pseudocode for the procedure generating the initial population P ( 1 ) consisting of n p individuals is presented in Figure 4.

Let s : v 0, v 1, v 2, ⋯, v k − 1, v k be a patrolling route, and assume that v 0 = v i + 1 = v j = u and v 1 = v i = v j + 1 = v (i, j ∈ I k, i ≠ j). Then, the edge connecting u and v is undirected. If i < j, the edge is traversed three times on s, as shown in the left panel of Figure 5a, and there exists a patrolling route that reduces the total length, as shown in the right panel of Figure 5a. Such a patrolling route traverses all edges on the original route; thus, the noncoverage rate remains unchanged. Similarly, even if j < i, the edge is traversed three times, as shown in the left panel of Figure 5b, and there exists a patrolling route that reduces the total length without changing the noncoverage rate, as shown in the right panel of Figure 5b. In general, assume that undirected edge { u , v } is traversed from u to v l 1 ( ≥ 1 ) times and from v to u l 2 ( ≥ 1 ) times. If l 1 ≠ l 2, there exists a patrolling route that reduces both the number of times traversing from u to v and from v to u by min { l 1 , l 2 } times without changing the noncoverage rate. If l 1 = l 2 > 1, there exists a patrolling route that reduces both the number of times traversing from u to v and from v to u by l 1 − 1 times without changing the noncoverage rate. The pseudocode for the improvement procedure of the chromosome is shown in Figure 6.

4.4 Crossover

Let p 1 = ( u 0 , u 1 , ⋯ , u k − 1 ) and p 2 = ( v 0 , v 1 , ⋯ , v l − 1 ) be two parent individuals. Then, the crossover operation is used in the proposed method to replace a partial walk on the patrolling route corresponding to p 1 with that corresponding to p 2. The procedure is as follows:

• (a) Any patrolling route requires that all high-security edges are traversed. First, one high-security edge e 0 is randomly selected from H, and one gene u i 0 in p 1 such that e 0 = ⟨ u i 0 , u i 0 + ⟩ and one gene v j 0 in p 2 such that e 0 = ⟨ v j 0 , v j 0 + ⟩ are selected (Figure 7a).
• (b) Find the high-security edge e 1 = ⟨ u i 1 , u i 1 + ⟩ that first appears in the rotated chromosome p 1 ( i 0 + ), and in the rotated chromosome p 2 ( j 0 + ), randomly select one gene v j 1 such that e 1 = ⟨ v j 1 , v j 1 + ⟩ (Figure 7b).
• (c) In the patrolling route corresponding to the chromosome p 1 ( i 0 + ), the partial walk between u i 0 + and u i 1 does not include high-security edges. Therefore, offspring q 1 can be created by replacing this partial walk with the partial walk between v j 0 + and v j 1 in p 2 ( j 0 + ). However, when selected high-security edges e 0 or e 1 are undirected edges, the direction of traversing them on p 1 may differ from the direction of traversing them on p 2. In this case, simply exchanging partial walks does not lead to creating an accurate patrolling route. Based on the direction of traversing e 0 and e 1, the process of creating offspring q 1 can be divided into four steps as follows (Figure 7c): Let q ′ = ( v j 0 + , ⋯ , v j 1 , u i 1 + , ⋯ , u i 0 ) be a chromosome to be created by simply replacing the partial walk from u i 0 + to u i 1 on p 1 ( i 0 + ) with the partial walk v j 0 + to v j 1 on p 2 ( j 0 + ). Then,
• (1) When both e 0 and e 1 are traversed in the same direction on p 1 ( i 0 + ) and p 2 ( j 0 + ) (that is, u i 0 = v j 0 and u i 1 = v j 1), let q 1 ′ be q ′.
• (2) When e 1 is traversed in the opposite direction although e 0 is traversed in the same direction (that is, u i 0 = v j 0 and u i 1 ≠ v j 1), let q 1 ′ be the chromosome created by inserting gene v j 1 + between v j 1 and u i 1 + on q ′.
• (3) When e 0 is traversed in the opposite direction although e 1 is traversed in the same direction (that is, u i 0 ≠ v j 0 and u i 1 = v j 1), let q 1 ′ be the chromosome created by appending gene u i 0 + at the end on q ′.
• (4) When both e 0 and e 1 are traversed in the opposite direction (that is, u i 0 ≠ v j 0 and u i 1 ≠ v j 1), let q 1 ′ be the chromosome created by inserting gene v j 1 + between v j 1 and u i 1 + and by appending gene u i 0 + at the end on q ′.
• (d) Find the high-security edge e 2 = ⟨ v j 2 , v j 2 + ⟩ that first appears in the rotated chromosome p 2 ( j 0 + ), and in the rotated chromosome p 1 ( i 0 + ), randomly select one gene u i 2 such that e 2 = ⟨ u i 2 , u i 2 + ⟩. Following the procedure used to create offspring q 1, offspring q 2 ′ is created.
• (e) Create offspring q 1 and q 2 by applying the improvement procedure described in Section 4.3 to q 1 ′ and q 2 ′.

The pseudocode for the proposed crossover operation is presented in Figure 8.

4.5 Mutation

In the crossover operation, the walk of parent individuals tends to be inherited by their offspring. Therefore, it is seldom that generated offspring will traverse vertices or edges that their parents do not. To maintain the diversity of the population, we introduce a mutation operation (Figure 9).

In this operation, the following steps are executed repeatedly: randomly select a gene (vertex) u and

• 1. if gene u exists on the patrolling route corresponding to the chromosome, select one locus i such that v i = u, and if there exists an edge ⟨ v i − , v i + ⟩ connecting vertices v i − and v i + before and after u, remove gene v i from the chromosome (see Figure 10a).
• 2. if gene u does not exist on the patrolling route corresponding to the chromosome and succsessive genes v i and v i + exist on the route such that both ⟨ v i , u ⟩ and ⟨ u , v i + ⟩ are in E, insert gene u between v i and v i + (see Figure 10b).

4.6 Local search strategy based on the Jaya algorithm

The crossover operation introduced in Section 4.4 is an order-based operation in which the orders of traversing the high-security edges of parents and other edges are inherited by offspring. To compensate for the ability to converge the solutions of this crossover, we introduce an improvement strategy that moves dominated solutions closer to a Pareto-optimal solution by combining the strategy used in the mutation operation with the Jaya algorithm.

As mention in Section 2, if the triangle inequality holds, removing a vertex v from the patrolling route tends to reduce the noncovered ratio since edges may be no longer guarded by visual confirmation from v, although the total length of the patrolling route becomes shorter. Conversely, adding a vertex that is not on the patrolling route increases the total length; however, this is expected to improve the noncovered ratio because edges guarded by visual confirmation may increase.

The approach we propose here (called the improved Jaya algorithm below) modifies a given individual to move closer to the best solution and away from the worst solution based on the best and worst candidates in the population. The outline of the proposed strategy is presented in Figure 11. Let p b and p w be the best and worst chromosomes in the current population, respectively, and let s b and s w be the patrolling routes corresponding to p b and p w, respectively. Let ϵ be a sufficiently small positive real number. By putting f 1 b = L ( s b ), f 2 b = c o v ̄ ( s b ), f 1 w = L ( s w ), f 2 w = c o v ̄ ( s w ), the coordinates of s b and s w are ( f 1 b , f 2 b ) and ( f 1 w , f 2 w ), respectively. Then, to modify a certain dominated solution s ( f 1 , f 2 ) to be closer to s b and away from s w, a hypothetical solution s o ( o 1 , o 2 ) is computed based on the strategy of the improved Jaya algorithm. To move s closer to the hypothetical solution s o, the mutation strategy is strategically repeated as follows: Let g 1 = 1 f 1 w | f 1 − o 1 | and g 2 = 1 f 2 w | f 2 − o 2 |, which are normalizations of | f 1 − o 1 | and | f 2 − o 2 |, respectively. If all edges are high-security edges, set g 2 = 0 because f 2 w = 0. The following operations are performed if the triangle inequality holds.

• • if g 1 ≥ g 2, an operation is performed to move the first component of point ( f 1 , f 2 ) closer to the first component of point ( o 1 , o 2 ). Specifically, if f 1 ≥ o 1, vertices are removed from the patrolling route to reduce the total distance; if f 1 < o 1, vertices are added not on the patrolling route increase the total distance.
• • If g 1 < g 2, an operation is performed to move the second component of point ( f 1 , f 2 ) closer to the second component of point ( o 1 , o 2 ). Specifically, if f 2 < o 2, vertices are removed from the patrolling route to reduce the noncovered ratio; if f 2 ≥ o 2, vertices are added not on the patrolling route to increase the noncovered ratio.

Remark that s o is a hypothetical solution that does not always exist; thus, the operation is repeated until approaching the neighborhood of s o (inside a circle of radius ϵ centered on s o), or the operation is repeated until the terminal condition is reached. The pseudocode for the improved Jaya algorithm is presented in Figure 12.

5 Numerical experiments

In this section, we report the results of numerical experiments conducted to verify the effectiveness of the proposed method (the hybrid strategy of MoEA-HSS and the improved Jaya algorithm) for the GPOPP. In these experiments, we compared the proposed method (called pMH) with the NSGA-II (called NSGA-II) proposed by Deb et al. (2002) and the original MoEA-HSS without the improved Jaya algorithm (called MoEA-HSS). All these methods incorporated the crossover and mutation operations proposed in this paper.

Evaluating the performance of multi-objective optimization methods is not easy since it is difficult to compare the Pareto-optimal solutions (also called the nondominated solutions) obtained by different methods. We compared pMH with NSGA-II and MoEA-HSS using three representative comparison methods. Let N e x be the number of numerical experiments for each method. Let S NSGA - II [ i ], S MoEA - HSS [ i ] and S pMH [ i ] be the Pareto-optimal solution sets of NSGA-II, MoEA-HSS and pMH obtained by the i-th experiment, respectively. The reference solution set S * is defined as the set of nondominated solutions in the union of all Pareto-optimal solution sets ⋃ i ∈ I N e x + S NSGA - II [ i ] ∪ S MoEA - HSS [ i ] ∪ S pMH [ i ].

The three evaluation criteria we used are as follows: where p = 2 and δ x , y = ( f 1 ( y ) − f 1 ( x ) ) 2 + ( f 2 ( y ) − f 2 ( x ) ) 2 denotes the Euclidean distance between a solution x in S α [ i ] and a reference solution y in S *. A smaller G D ( S α [ i ] ) value implies that S α [ i ] is closer to S *. where y ⪯ x means that f ( y ) ≤ f ( x ) holds for any objective function f. The value C ( S α [ i ] , S β [ j ] ) is in the interval [0,1], with values approaching 1 indicating that a greater number of solutions in S β [ j ] are covered by those in S α [ i ].

• 1. Number of nondominated solutions. For each method α ∈{NSGA-II, MoEA-HSS, pMH}, | S α [ i ] | is the number of nondominated solutions obtained by the i-th experiment for α. In general, the selection of the final solution is left to human judgment; thus, the number of Pareto-optimal solutions is an important evaluation criterion.
• 2. Generational distance. For the nondominated solution set S α [ i ] obtained by each method α ∈{NSGA-II, MoEA-HSS, pMH} and the reference solution set S *, the generational distance G D is defined as follows (Van Veldhuizen, 1999; Ishibuchi et al., 2015):

G D S α i = 1 | S α i | ∑ x ∈ S α i min δ x , y | y ∈ S * p 1 p ,

• 3. Coverage of two sets. For two α , β ∈ { NSGA - II , MoEA - HSS , pMH }, where α ≠ β, the coverage C is defined as follows (Zitzler and Thiele, 1999):

C S α i , S β j = x ∈ S β j ∣ ∃ y ∈ S α i , y ⪯ x S β j ,

The benchmark problems used in the experiments were created based on the Mixed Rural Postman Problem (MRPP) benchmark problems RB422 (| V | = 357, | E | = 674, | A | = 210), RB452 (| V | = 465, | E | = 796, | A | = 259), RB472 (| V | = 498, | E | = 849, | A | = 265), RB522 (| V | = 388, | E | = 828, | A | = 278), RB552 (| V | = 488, | E | = 987, | A | = 331) and RB572 (| V | = 498, | E | = 986, | A | = 340) shown in Arc Routing Problems: Data Instances (https://www.uv.es/corberan/instancias.htm). The number of high-security edges (called required edges) defined in the MRPP benchmark problems is sufficiently large. Therefore, they are not suitable for use as benchmarks for methods against the GPOPP in which visual confirmation is allowed. To confirm the effect of visual confirmation, in these experiments, we changed the required edges of each benchmark problem to non-required edges, creating four patterns of benchmark problems with 10, 20, 30, and 40 high-security edges. We used these edges in the experiments. In addition, the ratio of the number of high-security undirected edges to high-security arcs was set to 4 : 1.

The experiments were conducted on a PC with Windows 11, an AMD Ryzen 5 3500 CPU, 3.59 GHz, and 16.0 GB RAM. We conducted preliminary experiments using the benchmark problem RB422_10 with eight high-security undirected edges and two high-security arcs. The parameters were set as follows: the positive constant n p = 150, the archive size n a = 300, the initial population size n ( 0 ) = 300, the crossover rate = 0.3, the mutation rate = 0.05, the terminating condition for the improved Jaya algorithm T = 50, the radius ϵ = 0.1 of a circle centered on the hypothetical solution s o and the maximum generations M a x G e n = 300. When using the improved Jaya algorithm in pMH, the best solution s b is selected from the nondominated solution set S pMH [ i ]. If many nondominated solutions in S pMH [ i ] are concentrated in close proximity, the probability that s b will be selected from among these concentrated individuals increases. Consequently, the individuals generated by the improved Jaya algorithm also tend to move in the direction of the concentrated population. To distribute the location of the individuals generated by the improved Jaya algorithm to some extent, s b was selected as follows: Let m = | S pMH [ i ] | + 10 10 and l = | S pMH [ i ] | ( mod m ). Then

• 1. If m = 1, then let S 1 = S pMH [ i ].
• 2. If m > 1, then partition S pMH [ i ] into m subsets S 1, S 2, ⋯, S m, which satisfy the following conditions:
• • ⋃ i ∈ I m + S i = S pMH [ i ],
• • S i ∩ S j = ϕ (i, j ∈ I m +, i ≠ j),
• • | S i | = | S pMH [ i ] | m (i ∈ I l +), | S j | = | S pMH [ i ] | m (j ∈ I m + \ I l +).
• • For each i ∈ I m − 1 +,

f 1 x < f 1 y ∀ x ∈ S i , ∀ y ∈ ⋃ j ∈ I m + \ I i + S j .

• 3. Randomly select one subset S i from the m subsets, randomly select one solution x from S i, and put s b = x.

We ran 10 numerical experiments for each method (that is, N e x = 10). Comparison results of pMH with NSGA-II and MoEA-HSS at 10, 50, 150 and 300 generations are shown in Table 1. The number of nondominated solutions, generational distance and CPU time are shown in (a) and these are the maximum, minimum, average and standard deviation obtained by 10 experiments. Here, the G D ( S α [ i ] ) for each generation g e n ∈ { 10,50,150,300 } is calculated using the Pareto-optimal solution sets S α [ i ] at the g e n-th generation and the reference solution set S * at the 300th generation. The comparison results for the coverage are shown in (b) and these are calculated by 100 values of C ( S α [ i ] , S β [ j ] ) ( 1 ≤ i , j ≤ N e x ). The evolution of the Pareto-optimal solution set S α [ 1 ] at the 1st experiment for each method is shown in Figure 13.

TABLE 1. Comparison of pMH with NSGA-II and MoEA-HSS during evolution (benchmark problem: RB422_10).

The number of nondominated solutions | S α [ i ] | for NSGA-II and pMH are no significant difference, although the value for MoEA-HSS is slightly lower. If the Pareto-optimal solution set S α [ i ] contains even a single solution that is far from S *, the generational distance will have a large value. Therefore, method α cannot be considered inferior simply because the generational distance has a large value. On the other hand, when the minimum value of the generational distance is sufficiently small, method α is considered superior because the nondominated solutions obtained by method α are likely to be close to the solutions in the reference solution set S *. For these reasons, it is more appropriate to use the minimum value, rather than the average or maximum, when conducting evaluations with the generational distance. Therefore, from these experimental results, in evaluations based on the number of nondominated solutions and the generational distance, pMH can be considered superior to other methods. In particular, the comparison between MoEA-HSS and pMH based on these criteria implies that the ability of local search for the improved Jaya algorithm has achieved the expected results.

The coverage C ( S α [ i ] , S β [ j ] ) is the rate that solutions in S β [ j ] are covered by solutions in S α [ i ]. Hence, if the average of C ( S α [ i ] , S β [ j ] ) is higher than the average of C ( S β [ j ] , S α [ i ] ), S α [ i ] can be considered as better than S β [ i ] under this criterion. Therefore, by comparing the average of two coverages C ( S pMH [ i ] , S β [ j ] ) and C ( S β [ j ] , S pMH [ i ] ) (β ∈{NSGA-II, MoEA-HSS}), the Pareto-optimal solution set S pMH [ i ] is considered statistically superior to S β [ j ] obtained by other methods at every generations.

The experiment results of comparing pMH with NSGA-II and MoEA-HSS when we ran each method until 300 generations for all benchmark problems are shown in Tables 2, 3.

TABLE 2. Comparison of pMH with NSGA-II and MoEA-HSS by the number of nondominated solutions, generational distance and CPU time ( gen = 300 ).

TABLE 3. Comparison of pMH with NSGA-II and MoEA-HSS by the coverage ( gen = 300 ).

Our method pMH achieved better results than other methods in all benchmark problems with respect to the generational distance and the coverage of two sets, although pMH and NSGA-II are evenly-matched at the criterion the number of nondominated solutions. Here, even if pMH is inferior to that of other methods α at the criteria the number of nondominated solutions, since it is considered that the ratio of solutions in S α [ j ] covered by solutions in S pMH [ i ] is high, S pMH [ i ] is not necessarily inferior to S NSGA - II [ j ] or S MoEA - HSS [ j ]. Based on these numerical experiments, we confirmed that the local search based on the improved Jaya algorithm is effective and that pMH can generate superior Pareto-optimal solutions.

6 Conclusion

In this study, we defined a new arc routing bi-objective optimization problem (GPOPP) that models the patrol security of police officers (or security guards) based on the POPP and proposed a hybrid heuristic approach for the GPOPP. The proposed method combines the hybrid sampling strategy MoEA-HSS, which combines sampling strategies based on the VEGA and PDDR-FF, with a solution improvement strategy based on the improved Jaya algorithm. The solutions of the MoEA-HSS approach to the true Pareto differ in various directions because the VEGA-based sampling strategy has a preference for the edge region of the Pareto front and the PDDR-FF-based sampling strategy tends to converge toward the center area of the Pareto front. The proposed method (pMH) improves convergence by combining the MoEA-HSS with the improved Jaya algorithm-based local search method. The numerical experimental results demonstrate that the proposed method can obtain better solutions than the NSGA-II and the MoEA-HSS. The remaining challenge for us is to improve efficiency by reducing CPU time while maintaining high solution quality. In addition, extending GPOPP model will enable us to more accurately replicate the complex challenges of real-world urban policing. One extension would be to model situations where multiple officers work together, and we consider to adapt our method to address such extended problems.

Generative AI statement

The author(s) declare that no Generative AI was used in the creation of this manuscript.

Publisher’s note

All claims expressed in this article are solely those of the authors and do not necessarily represent those of their affiliated organizations, or those of the publisher, the editors and the reviewers. Any product that may be evaluated in this article, or claim that may be made by its manufacturer, is not guaranteed or endorsed by the publisher.