# Fare inspection patrolling under in-station selective inspection policy

Pablo Escalona, Luce Brotcorne, Bernard Fortz, Mario Ramirez

► To cite this version:

Pablo Escalona, Luce Brotcorne, Bernard Fortz, Mario Ramirez. Fare inspection patrolling under in-station selective inspection policy. Annals of Operations Research, 2023, 10.1007/s10479-023-05670-2. hal-04398408

HAL Id: hal-04398408

https://inria.hal.science/hal-04398408

Submitted on 5 Apr 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Fare inspection patrolling under in-station selective inspection policy

Pablo Escalona, Luce Brotcorne, Bernard Fortz, Mario Ramirez

► To cite this version:

Pablo Escalona, Luce Brotcorne, Bernard Fortz, Mario Ramirez. Fare inspection patrolling under in-station selective inspection policy. Annals of Operations Research, 2023, 10.1007/s10479-023-05670-2. hal-04398408

HAL Id: hal-04398408

https://inria.hal.science/hal-04398408v1

Submitted on 5 Apr 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Fare inspection patrolling under in-station
selective inspection policy

Pablo Escalona¹*, Luce Brotcorne², Bernard Fortz³,⁴,²
and Mario Ramirez¹

¹*Department of Industrial Engineering, Universidad Técnica Federico Santa María, Avenida España 1680, Valparaíso, Chile.

²INOCS Team, INRIA Lille-Nord Europe, 40 Avenue Halley,
59650 Villeneuve d'Ascq, France.

³HEC Liège, Management School of the University of Liège,
Belgium.

⁴Département d'Informatique, Faculté des Sciences, Université libre de Bruxelles, Belgium.

*Corresponding author(s). E-mail(s): pablo.escalona@usm.cl;
Contributing authors: luce.brotcorne@inria.fr;
bernard.fortz@uliege.be; mario.ramirezi@sansano.usm.cl;

**Abstract**

A patrolling strategy that defines fare inspection frequencies on a *proof-of-payment* transportation system is operationally useful to the transit authority when there is a mechanism for its practical implementation. This study addresses the operational implementation of a fare inspection patrolling strategy under an in-station selective inspection policy using an unpredictable patrolling schedule, where the transit authority select a patrolling schedule each day with some probability to induce uncertainty. The challenge is to determine the set of patrolling schedules and their respective probabilities of being selected whose systematic day-to-day application matches the inspection frequencies that inhibit the action of opportunistic passengers in the medium term. We use a Stackelberg game approach to represent the hierarchical decision making process between the transit authority and opportunistic passengers, whose decision on whether to evade the fare depends on the inspection frequencies set by
Fare inspection patrolling under in-station
selective inspection policy

Pablo Escalona¹*, Luce Brotcorne², Bernard Fortz³,⁴,²
and Mario Ramirez¹

¹*Department of Industrial Engineering, Universidad Técnica Federico Santa María, Avenida España 1680, Valparaíso, Chile.

²INOCS Team, INRIA Lille-Nord Europe, 40 Avenue Halley,
59650 Villeneuve d'Ascq, France.

³HEC Liège, Management School of the University of Liège,
Belgium.

⁴Département d'Informatique, Faculté des Sciences, Université libre de Bruxelles, Belgium.

*Corresponding author(s). E-mail(s): pablo.escalona@usm.cl;
Contributing authors: luce.brotcorne@inria.fr;
bernard.fortz@uliege.be; mario.ramirezi@sansano.usm.cl;

**Abstract**

A patrolling strategy that defines fare inspection frequencies on a *proof-of-payment* transportation system is operationally useful to the transit authority when there is a mechanism for its practical implementation. This study addresses the operational implementation of a fare inspection patrolling strategy under an in-station selective inspection policy using an unpredictable patrolling schedule, where the transit authority select a patrolling schedule each day with some probability to induce uncertainty. The challenge is to determine the set of patrolling schedules and their respective probabilities of being selected whose systematic day-to-day application matches the inspection frequencies that inhibit the action of opportunistic passengers in the medium term. We use a Stackelberg game approach to represent the hierarchical decision making process between the transit authority and opportunistic passengers, whose decision on whether to evade the fare depends on the inspection frequencies set by
the transit authority. Numerical experiments show that a joint strategy-
schedule approach provides good-quality unpredictable patrolling sched-
ules with respect to the optimality gap for large-scale networks.

**Keywords:** Fare evasion; Patrolling strategy; Unpredictable patrolling schedule; Selective inspection; Stackelberg games.

# 1 Introduction

Fare evasion in large-scale proof-of-payment transportation systems without barriers ($POP_S$) is an inevitable phenomenon due to the spatial and temporal size of these networks, the variability in the number of system users during the day, the diversity of passenger profiles with the tendency to evade, and the fact that fare inspection resources are often limited. The consequences of evasion in $POP_S$ systems are a well-studied issue and mainly involves loss of revenue for system operators and reduces perceived levels of security (Barabino and Salis (2022), Busco et al (2022), Currie and Delbosc (2017), Buneder and Galilea (2017), Troncoso and de Grange (2017), Lee (2011), Dauby and Kovacs (2007)).

To control and inhibit fare evasion in $POP_S$ systems the transit author-
ity employs a variety of methods (Sasaki (2014), Torres-Montoya (2014)). One
of the most practiced methods is the fare inspection and its effectiveness has
been recognized in recent research (Barabino and Salis (2019)). The design of
$POP_S$ fare inspections is defined by the deployment, location, and inspection
policies, which have been summarized in Figure 1. However, the main charac-
teristic of fare inspections must be their unpredictability from the perspective
of passengers since a predictable fare inspection may be exploited by potentials
fare evaders for their benefit.

<figure><img src="image_2.png" /><figcaption>Fig. 1 Fare inspection components</figcaption></figure>
the transit authority. Numerical experiments show that a joint strategy-schedule approach provides good-quality unpredictable patrolling schedules with respect to the optimality gap for large-scale networks.

**Keywords:** Fare evasion; Patrolling strategy; Unpredictable patrolling schedule; Selective inspection; Stackelberg games.

# 1 Introduction

Fare evasion in large-scale proof-of-payment transportation systems without barriers ($POP_S$) is an inevitable phenomenon due to the spatial and temporal size of these networks, the variability in the number of system users during the day, the diversity of passenger profiles with the tendency to evade, and the fact that fare inspection resources are often limited. The consequences of evasion in $POP_S$ systems are a well-studied issue and mainly involves loss of revenue for system operators and reduces perceived levels of security (Barabino and Salis (2022), Busco et al (2022), Currie and Delbosc (2017), Buneder and Galilea (2017), Troncoso and de Grange (2017), Lee (2011), Dauby and Kovacs (2007)).

To control and inhibit fare evasion in $POP_S$ systems the transit authority employs a variety of methods (Sasaki (2014), Torres-Montoya (2014)). One of the most practiced methods is the fare inspection and its effectiveness has been recognized in recent research (Barabino and Salis (2019)). The design of $POP_S$ fare inspections is defined by the deployment, location, and inspection policies, which have been summarized in Figure 1. However, the main characteristic of fare inspections must be their unpredictability from the perspective of passengers since a predictable fare inspection may be exploited by potentials fare evaders for their benefit.

<figure><img src="image_2.png" /><figcaption>**Fig. 1** Fare inspection components</figcaption></figure>
There are two types of deployment policies. The first one, denoted as *fare inspection patrolling*, requires the deployment of fare inspection teams controlling different locations during the day. The second one, denoted as *spot fare inspection*, involves the simultaneous control of different locations during a given time interval, e.g., at peak hours. Fare inspections can be operated according to 3 approaches (Wolfram et al (2022)): *on-board inspections*, where passengers are inspected on-board the vehicle, *fare-paid area inspections*, where passengers are inspected in the fare payment area or when passengers enter/exit the platform area, and *offboarding inspections*, where passengers are inspected when they leave the vehicle. The last two fare enforcement locations are also denoted as *in-station inspections*. Two types of inspection policies are distinguished. The first one, denoted as *mass inspection policy*, considers that all passengers are inspected at the location controlled by the transit authority without disrupting the service (Egu and Bonnel (2020)). The second one, denoted as *selective inspection policy*, considers that inspectors randomly choose passengers to be inspected at the location controlled by the transit authority.

Passengers on a transportation system do not react in the same way to fare inspections (Barabino et al (2020), Barabino and Salis (2019)). Regardless of the inspection levels, honest passengers always pay the ticket, while other passengers never pay for economic or ideological reasons. Thus, fare inspections have an effect on passengers who assess the risk of being inspected (opportunists). Indeed, according to the economic analysis of rational crime (Winter (2019), Freeman (1999)), an opportunistic passenger's decision to evade fare payment depends on the risk of being inspected, where risk is commonly measured by the probability of inspection. Milioti et al (2020) present evidence that low inspection probability is a very important reason for frequent evaders to evade fare payment. Thus, determining the inspection probability distribution over the transportation network that inhibits the action of opportunistic passengers is highly relevant issues for the transit authority.

The problem of determining inspection probability distributions in a public transportation network, defined as the *fare inspection strategy problem*, is mainly addressed in the literature as a Leader-Follower problem under Stackelberg games (Barabino et al (2020)). We distinguish two types of fare inspection strategies. The *fare inspection patrolling strategy* aims to determine the temporal-spatial inspection probability distribution under a patrolling deployment policy, and the *spot fare inspection strategy* considers the spatial inspection probability distribution under a spot deployment policy.

A fare inspection strategy (patrolling or spot) is operationally useful to the transit authority when an operational mechanism is implemented to achieve the inspection probabilities defined by the fare inspection strategy in a medium-term horizon. A fare inspection patrolling strategy can be operationally implemented through a set of patrolling schedules, where each schedule is a collection of temporal-spatial patrol paths (one for each fare inspection
There are two types of deployment policies. The first one, denoted as *fare inspection patrolling*, requires the deployment of fare inspection teams controlling different locations during the day. The second one, denoted as *spot fare inspection*, involves the simultaneous control of different locations during a given time interval, e.g., at peak hours. Fare inspections can be operated according to 3 approaches (Wolfram et al (2022)): *on-board inspections*, where passengers are inspected on-board the vehicle, *fare-paid area inspections*, where passengers are inspected in the fare payment area or when passengers enter/exit the platform area, and *offboarding inspections*, where passengers are inspected when they leave the vehicle. The last two fare enforcement locations are also denoted as *in-station inspections*. Two types of inspection policies are distinguished. The first one, denoted as *mass inspection policy*, considers that all passengers are inspected at the location controlled by the transit authority without disrupting the service (Egu and Bonnel (2020)). The second one, denoted as *selective inspection policy*, considers that inspectors randomly choose passengers to be inspected at the location controlled by the transit authority.

Passengers on a transportation system do not react in the same way to fare inspections (Barabino et al (2020), Barabino and Salis (2019)). Regardless of the inspection levels, honest passengers always pay the ticket, while other passengers never pay for economic or ideological reasons. Thus, fare inspections have an effect on passengers who assess the risk of being inspected (opportunists). Indeed, according to the economic analysis of rational crime (Winter (2019), Freeman (1999)), an opportunistic passenger's decision to evade fare payment depends on the risk of being inspected, where risk is commonly measured by the probability of inspection. Milioti et al (2020) present evidence that low inspection probability is a very important reason for frequent evaders to evade fare payment. Thus, determining the inspection probability distribution over the transportation network that inhibits the action of opportunistic passengers is highly relevant issues for the transit authority.

The problem of determining inspection probability distributions in a public transportation network, defined as the *fare inspection strategy problem*, is mainly addressed in the literature as a Leader-Follower problem under Stackelberg games (Barabino et al (2020)). We distinguish two types of fare inspection strategies. The *fare inspection patrolling strategy* aims to determine the temporal-spatial inspection probability distribution under a patrolling deployment policy, and the *spot fare inspection strategy* considers the spatial inspection probability distribution under a spot deployment policy.

A fare inspection strategy (patrolling or spot) is operationally useful to the transit authority when an operational mechanism is implemented to achieve the inspection probabilities defined by the fare inspection strategy in a medium-term horizon. A fare inspection patrolling strategy can be operationally implemented through a set of patrolling schedules, where each schedule is a collection of temporal-spatial patrol paths (one for each fare inspection
team) with an associated probability of being selected, denoted as *unpredictable patrolling schedule*. Similarly, a spot fare inspection strategy can be operationally implemented through a set of inspection team allocations, where each allocation is a collection of locations to be controlled (one for each fare inspection team) with an associated probability of being selected, denoted *unpredictable inspection teams allocation*. Thus, the transit authority can select each day a patrolling schedule (inspection teams allocation) with a probability, avoiding any regularity that could be exploited by opportunistic passengers. The challenge is to determine the unpredictable patrolling schedule (unpredictable inspection teams allocation) whose systematic day-to-day application matches in the medium term the inspection probabilities defined by the fare inspection patrolling strategy (spot fare inspection strategy).

This paper addresses the fare inspection patrolling strategy and the unpredictable patrolling schedule problems to inhibit fare evasion in POP<sub>S</sub> systems when the transit authority commits to an in-station selective inspection policy. The fare inspection patrolling strategy problem is addressed using a Stackelberg game approach where the transit authority set a temporal-spatial inspection probability distribution at the transportation network stations, and opportunistic passengers respond by deciding whether or not to evade the fare payment based on their knowledge of the risk of being controlled when leaving their destination station. The fare inspection patrolling strategy problem is formulated as a single-level linear optimization problem. We show how to reformulate the fare inspection patrolling strategy problem as an equivalent unpredictable patrolling scheduling problem. The main contributions are presented as: 1) A *joint strategy-schedule approach* is proposed to address the operational implementation of a fare inspection patrolling strategy in a large-scale public transportation network when the transit authority is committed to an in-station fare inspection policy. This joint strategy-schedule approach ensures that for each fare inspection patrolling strategy there is a corresponding unpredictable patrolling schedule. 2) We show how to take advantage of the optimal fare inspection patrolling strategy to obtain an unpredictable patrolling schedule with quality guarantee in terms of its optimality gap. To the best of our knowledge, we are the first to provide a good-quality unpredictable patrolling schedule, in terms of optimality gap, in large-scale temporal-spatial transportation networks. 3) An estimate of the implementation time of an unpredictable patrolling schedule. We simulate the systematic day-to-day application of the unpredictable patrolling schedule to determine whether or not the unpredictable patrolling schedule can be implemented in the medium term.

The remainder of this paper is structured as follows. A review of related work is discussed in Section 2. Section 3 presents the fare inspection patrolling strategy formulation under a Stackelberg game approach. Section 4 presents the unpredictable patrolling schedule formulation. Computational results are reported in Section 5. Finally, conclusions and suggested future extensions are described in Section 6.
team) with an associated probability of being selected, denoted as *unpredictable patrolling schedule*. Similarly, a spot fare inspection strategy can be operationally implemented through a set of inspection team allocations, where each allocation is a collection of locations to be controlled (one for each fare inspection team) with an associated probability of being selected, denoted *unpredictable inspection teams allocation*. Thus, the transit authority can select each day a patrolling schedule (inspection teams allocation) with a probability, avoiding any regularity that could be exploited by opportunistic passengers. The challenge is to determine the unpredictable patrolling schedule (unpredictable inspection teams allocation) whose systematic day-to-day application matches in the medium term the inspection probabilities defined by the fare inspection patrolling strategy (spot fare inspection strategy).

This paper addresses the fare inspection patrolling strategy and the unpredictable patrolling schedule problems to inhibit fare evasion in POP<sub>S</sub> systems when the transit authority commits to an in-station selective inspection policy. The fare inspection patrolling strategy problem is addressed using a Stackelberg game approach where the transit authority set a temporal-spatial inspection probability distribution at the transportation network stations, and opportunistic passengers respond by deciding whether or not to evade the fare payment based on their knowledge of the risk of being controlled when leaving their destination station. The fare inspection patrolling strategy problem is formulated as a single-level linear optimization problem. We show how to reformulate the fare inspection patrolling strategy problem as an equivalent unpredictable patrolling scheduling problem. The main contributions are presented as: 1) A *joint strategy-schedule approach* is proposed to address the operational implementation of a fare inspection patrolling strategy in a large-scale public transportation network when the transit authority is committed to an in-station fare inspection policy. This joint strategy-schedule approach ensures that for each fare inspection patrolling strategy there is a corresponding unpredictable patrolling schedule. 2) We show how to take advantage of the optimal fare inspection patrolling strategy to obtain an unpredictable patrolling schedule with quality guarantee in terms of its optimality gap. To the best of our knowledge, we are the first to provide a good-quality unpredictable patrolling schedule, in terms of optimality gap, in large-scale temporal-spatial transportation networks. 3) An estimate of the implementation time of an unpredictable patrolling schedule. We simulate the systematic day-to-day application of the unpredictable patrolling schedule to determine whether or not the unpredictable patrolling schedule can be implemented in the medium term.

The remainder of this paper is structured as follows. A review of related work is discussed in Section 2. Section 3 presents the fare inspection patrolling strategy formulation under a Stackelberg game approach. Section 4 presents the unpredictable patrolling schedule formulation. Computational results are reported in Section 5. Finally, conclusions and suggested future extensions are described in Section 6.
## 2 Literature Review

The literature review focuses on papers related to fare inspection patrolling strategies and schedules. In Table 1, we classify these works according to: (i) the problem addressed (patrolling strategy or unpredictable patrolling schedule), (ii) transit network topology (single-line or network), (iii) location policy (on-board or in-station), and (iv) inspection policy (mass or selective).

<table><caption>**Table 1** Studies on fare inspection patrolling strategies and schedules</caption><thead><tr><th rowspan="2">Author</th><th colspan="2">Problem addressed</th><th colspan="2">Network topology</th><th colspan="2">Location policy</th><th colspan="2">Inspection policy</th></tr><tr><th>Strategy</th><th>Schedule</th><th>Single line</th><th>Network</th><th>On-board</th><th>In-station</th><th>Mass</th><th>Selective</th></tr></thead><tbody><tr><td>Jiang et al (2012)</td><td>X</td><td></td><td>X</td><td></td><td>X</td><td>X</td><td></td><td>X</td></tr><tr><td>Yin et al (2012)</td><td>X</td><td></td><td>X</td><td></td><td>X</td><td>X</td><td></td><td>X</td></tr><tr><td>Jiang et al (2013)</td><td>X</td><td></td><td>X</td><td></td><td>X</td><td>X</td><td></td><td>X</td></tr><tr><td>Krogvig (2014)</td><td></td><td>X</td><td></td><td>X</td><td>X</td><td></td><td>X</td><td></td></tr><tr><td>Delfau et al (2018)</td><td></td><td>X</td><td></td><td>X</td><td></td><td>X</td><td>X</td><td></td></tr><tr><td>Brotcorne et al (2021)</td><td>X</td><td>X</td><td>X</td><td></td><td>X</td><td>X</td><td></td><td>X</td></tr><tr><td>This paper</td><td>X</td><td>X</td><td></td><td>X</td><td></td><td>X</td><td></td><td>X</td></tr></tbody></table>

Jiang et al (2012) study the design of a fare inspection patrolling strategy under a Stackelberg game approach in a single-line urban train represented by a temporal-spatial graph. Fare inspections are performed in-station and on-board. Using an upper bound on inspection probabilities, they formulate the patrolling strategy as a linear optimization problem relaxation (LP relaxation). In contrast, we use an exact formulation for the inspection probabilities. They assume a selective inspection policy because the probability of inspecting an opportunistic passenger depends on the fare enforcement team inspection rate.

Yin et al (2012) extend the model defined in Jiang et al (2012), to include temporal constraints for inspection teams embedded in an extended temporal-spatial graph. They derive a LP relaxation of the fare inspection patrolling strategy under a Stackelberg game approach by using an upper bound on the inspection probabilities. They propose a heuristic to compute an unpredictable patrolling schedule without guaranteeing its convergence in steady state with the inspection probabilities defined by the patrolling strategy. Jiang et al (2013) generalize the work of Yin et al (2012) by including uncertainty in the fare inspection patrolling strategy using Markov Decision Processes. Considering an upper bound on the inspection probabilities, they formulate the fare inspection patrolling strategy as a LP and propose a simulation-based heuristic to compute an unpredictable patrolling schedule. The experiments conducted by Yin et al (2012) and Jiang et al (2013) were done independently on each line of Los Angeles Metro, which is equivalent to defining a fare inspection patrolling strategy for each line. In contrast, we carried out experiments on a large-scale transportation network by defining a fare inspection patrolling strategy for the whole network.

Krogvig (2014) addresses the design of an unpredictable patrolling schedule using a Stackelberg game approach. He considers a train network in which passengers can transfer between lines according to a timetable. Inspections
## 2 Literature Review

The literature review focuses on papers related to fare inspection patrolling strategies and schedules. In Table 1, we classify these works according to: (i) the problem addressed (patrolling strategy or unpredictable patrolling schedule), (ii) transit network topology (single-line or network), (iii) location policy (on-board or in-station), and (iv) inspection policy (mass or selective).

<table><caption>**Table 1** Studies on fare inspection patrolling strategies and schedules</caption><thead><tr><th rowspan="2">Author</th><th colspan="2">Problem addressed</th><th colspan="2">Network topology</th><th colspan="2">Location policy</th><th colspan="2">Inspection policy</th></tr><tr><th>Strategy</th><th>Schedule</th><th>Single line</th><th>Network</th><th>On-board</th><th>In-station</th><th>Mass</th><th>Selective</th></tr></thead><tbody><tr><td>Jiang et al (2012)</td><td>X</td><td></td><td>X</td><td></td><td>X</td><td>X</td><td></td><td>X</td></tr><tr><td>Yin et al (2012)</td><td>X</td><td></td><td>X</td><td></td><td>X</td><td>X</td><td></td><td>X</td></tr><tr><td>Jiang et al (2013)</td><td>X</td><td></td><td>X</td><td></td><td>X</td><td>X</td><td></td><td>X</td></tr><tr><td>Krogvig (2014)</td><td></td><td>X</td><td></td><td>X</td><td>X</td><td></td><td>X</td><td></td></tr><tr><td>Delfau et al (2018)</td><td></td><td>X</td><td></td><td>X</td><td></td><td>X</td><td>X</td><td></td></tr><tr><td>Brotcorne et al (2021)</td><td>X</td><td>X</td><td>X</td><td></td><td>X</td><td>X</td><td></td><td>X</td></tr><tr><td>This paper</td><td>X</td><td>X</td><td></td><td>X</td><td></td><td>X</td><td></td><td>X</td></tr></tbody></table>

Jiang et al (2012) study the design of a fare inspection patrolling strategy under a Stackelberg game approach in a single-line urban train represented by a temporal-spatial graph. Fare inspections are performed in-station and on-board. Using an upper bound on inspection probabilities, they formulate the patrolling strategy as a linear optimization problem relaxation (LP relaxation). In contrast, we use an exact formulation for the inspection probabilities. They assume a selective inspection policy because the probability of inspecting an opportunistic passenger depends on the fare enforcement team inspection rate.

Yin et al (2012) extend the model defined in Jiang et al (2012), to include temporal constraints for inspection teams embedded in an extended temporal-spatial graph. They derive a LP relaxation of the fare inspection patrolling strategy under a Stackelberg game approach by using an upper bound on the inspection probabilities. They propose a heuristic to compute an unpredictable patrolling schedule without guaranteeing its convergence in steady state with the inspection probabilities defined by the patrolling strategy. Jiang et al (2013) generalize the work of Yin et al (2012) by including uncertainty in the fare inspection patrolling strategy using Markov Decision Processes. Considering an upper bound on the inspection probabilities, they formulate the fare inspection patrolling strategy as a LP and propose a simulation-based heuristic to compute an unpredictable patrolling schedule. The experiments conducted by Yin et al (2012) and Jiang et al (2013) were done independently on each line of Los Angeles Metro, which is equivalent to defining a fare inspection patrolling strategy for each line. In contrast, we carried out experiments on a large-scale transportation network by defining a fare inspection patrolling strategy for the whole network.

Krogvig (2014) addresses the design of an unpredictable patrolling schedule using a Stackelberg game approach. He considers a train network in which passengers can transfer between lines according to a timetable. Inspections
are performed exclusively on-board. Krogvig (2014) assumes a mass inspection policy because the travel time between stations is long enough to control the entire train. Using a column generation approach to formulate the unpredictable patrolling schedule, Krogvig (2014) derives a LP relaxation for the pricing problem using an upper bound on the inspection probabilities. Small-scale experiments are considered, where the temporal-spatial network has 236 edges. In contrast, in this paper we considered a large-scale temporal-spatial network with 33 048 edges.

Delfau et al (2018) develop a four-step algorithm to generate randomized fare inspection patrolling schedules under an in-station mass inspection policy. In the first step, the stations to be controlled are determined using a modified version of the *non-stochastic multi-armed bandit algorithm* (Auer et al (2002)). In the second step, the travel times between the stations are computed. In the third step, the inspection teams path are determined using the vehicle routing problem. In the fourth step, the inspection teams path are refined by including the bus schedule and temporary labor constraints. The algorithm is tested on a bus network in Paris, France, considering 612 stopping stations.

Brotcorne et al (2021) studied the design of a fare inspection patrolling strategy and unpredictable patrolling schedule under a Stackelberg game approach. They assume that the transit authority adopts a selective inspection policy in-stations and on-board vehicles. Using an exact formulation for the inspection probabilities, they formulate the fare inspection patrolling strategy as a nonlinear optimization problem (NLP) and propose a relaxation-based heuristic. On the other hand, assuming that the transit authority knows all the patrolling schedules, they formulate the unpredictable patrolling schedule as a LP and propose a column generation solution approach. The pricing problem being a mixed integer nonlinear problem (MINLP) difficult to solve. They propose a relaxation-based heuristic to obtain a feasible unpredictable patrolling schedule. The experiments are conducted on a Los Angeles Metro single-line. The formulation of the patrolling strategy and unpredictable patrolling schedule are independent. In contrast, in this paper we address jointly the patrolling strategy and the unpredictable patrolling schedule.

In summary, no previous work has addressed jointly the design of a fare inspection patrolling strategy and unpredictable patrolling schedule ensuring that for any patrolling strategy there is a corresponding unpredictable patrolling schedule in large-scale transportation networks considering an in-station selective inspection policy.
are performed exclusively on-board. Krogvig (2014) assumes a mass inspection policy because the travel time between stations is long enough to control the entire train. Using a column generation approach to formulate the unpredictable patrolling schedule, Krogvig (2014) derives a LP relaxation for the pricing problem using an upper bound on the inspection probabilities. Small-scale experiments are considered, where the temporal-spatial network has 236 edges. In contrast, in this paper we considered a large-scale temporal-spatial network with 33 048 edges.

Delfau et al (2018) develop a four-step algorithm to generate randomized fare inspection patrolling schedules under an in-station mass inspection policy. In the first step, the stations to be controlled are determined using a modified version of the *non-stochastic multi-armed bandit algorithm* (Auer et al (2002)). In the second step, the travel times between the stations are computed. In the third step, the inspection teams path are determined using the vehicle routing problem. In the fourth step, the inspection teams path are refined by including the bus schedule and temporary labor constraints. The algorithm is tested on a bus network in Paris, France, considering 612 stopping stations.

Brotcorne et al (2021) studied the design of a fare inspection patrolling strategy and unpredictable patrolling schedule under a Stackelberg game approach. They assume that the transit authority adopts a selective inspection policy in-stations and on-board vehicles. Using an exact formulation for the inspection probabilities, they formulate the fare inspection patrolling strategy as a nonlinear optimization problem (NLP) and propose a relaxation-based heuristic. On the other hand, assuming that the transit authority knows all the patrolling schedules, they formulate the unpredictable patrolling schedule as a LP and propose a column generation solution approach. The pricing problem being a mixed integer nonlinear problem (MINLP) difficult to solve. They propose a relaxation-based heuristic to obtain a feasible unpredictable patrolling schedule. The experiments are conducted on a Los Angeles Metro single-line. The formulation of the patrolling strategy and unpredictable patrolling schedule are independent. In contrast, in this paper we address jointly the patrolling strategy and the unpredictable patrolling schedule.

In summary, no previous work has addressed jointly the design of a fare inspection patrolling strategy and unpredictable patrolling schedule ensuring that for any patrolling strategy there is a corresponding unpredictable patrolling schedule in large-scale transportation networks considering an in-station selective inspection policy.
## 3 Fare inspection patrolling strategy formulation

Let us consider a public transportation network where the arrival and departure of vehicles (bus, tram, subway) from stations are defined by a timetable. Therefore, passengers and fare inspection teams move temporally and spatially in the transportation network according to their timetable. Fare inspection teams may remain temporarily at a station.

The transportation network is represented by a temporal-spatial graph $G(V, E)$, where $V$ and $E$ are the sets of nodes and edges, respectively. A node $v = (S(v), T(v)) \in V$ is defined as a pair of station and time representing the arrival/departure of vehicles from station $S(v) = s$ at time $T(v) = \tau$. An edge $e \in E$, denoted as $e = (v, v')$, represents a connection between pair of station and time according to the timetable. Furthermore, we define an in-station edge as $\xi(v) = (v, v')$ to model the temporary stay of a fare inspection team at station $v \in V$, where $S(v) = S(v')$, and there is no node $v'' \in V$ such that $S(v) = S(v'')$ and $T(v) < T(v'') < T(v')$. The fare inspection path in the temporal-spatial transportation network is thus represented by a sequence of nodes and edges in $G$. We add to $G$ a source node $v^+$ with artificial edges to all possible nodes where a fare inspection team can start the control and a sink node $v^-$ with artificial edges from all possible nodes where a fare inspection team end the working day.

The transit authority implements a selective inspection policy at the exit of the transportation network stations. Let $d_v \ge 0$ be the number of passengers leaving $v \in V$. Two passengers profiles are considered: honest passengers always paying the fees, and opportunistic passengers deciding to buy a ticket or not on the basis of the expected cost of their trip. This one depends on the probability of being inspected when leaving the transportation network. Let $U_v^o$ be the expected value of the amount paid by an opportunistic passenger who leaves the transit system at $v \in V$. As for Brotcorne et al (2021), we define $U_v^o$ as the minimum between the ticket value and the expected value of the fine, i.e., $U_v^o = \min\{B, F\mathbb{P}_v^o\}$, where $B$ is the ticket price, $F$ is fine, and $\mathbb{P}_v^o$ is the probability that a specific opportunistic passenger is inspected leaving $v \in V$. We assume that the number of opportunistic passengers leaving $v \in V$, denoted $d_v^o$, is a random variable that follows a discrete uniform distribution, i.e., $d_v^o \sim \mathcal{U}\{0, \dots, \tilde{d}_v^o\}$, with $\tilde{d}_v^o \le d_v$, for any $v \in V$.

Fare inspection teams are subject to temporal labor constraints. As for Yin et al (2012), we embed the temporary labor constraints in an extended graph denoted as $G(V, E)$ defined as follows. Let $J$ be the set of time windows, where each of them limits the maximum time that a fare inspection team can remain on the network. Next, we partition $G$ into $|J|$ subgraphs such that subgraph $j$ contains all nodes and edges in the interval $[\underline{\tau}_j, \bar{\tau}_j]$, including all edges in the set $\{(v^+, u) \in E: T(u) \in [\underline{\tau}_j, \bar{\tau}_j]\} \cup \{(u, v^-) \in E: T(u) \in [\underline{\tau}_j, \bar{\tau}_j]\}$, where $\underline{\tau}_j$ and $\bar{\tau}_j$ are the start and end time of the $j$th time window. An exhaustive
## 3 Fare inspection patrolling strategy formulation

Let us consider a public transportation network where the arrival and departure of vehicles (bus, tram, subway) from stations are defined by a timetable. Therefore, passengers and fare inspection teams move temporally and spatially in the transportation network according to their timetable. Fare inspection teams may remain temporarily at a station.

The transportation network is represented by a temporal-spatial graph $G(V, E)$, where $V$ and $E$ are the sets of nodes and edges, respectively. A node $v = (S(v), T(v)) \in V$ is defined as a pair of station and time representing the arrival/departure of vehicles from station $S(v) = s$ at time $T(v) = \tau$. An edge $e \in E$, denoted as $e = (v, v')$, represents a connection between pair of station and time according to the timetable. Furthermore, we define an in-station edge as $\xi(v) = (v, v')$ to model the temporary stay of a fare inspection team at station $v \in V$, where $S(v) = S(v')$, and there is no node $v'' \in V$ such that $S(v) = S(v'')$ and $T(v) < T(v'') < T(v')$. The fare inspection path in the temporal-spatial transportation network is thus represented by a sequence of nodes and edges in $G$. We add to $G$ a source node $v^+$ with artificial edges to all possible nodes where a fare inspection team can start the control and a sink node $v^-$ with artificial edges from all possible nodes where a fare inspection team end the working day.

The transit authority implements a selective inspection policy at the exit of the transportation network stations. Let $d_v \ge 0$ be the number of passengers leaving $v \in V$. Two passengers profiles are considered: honest passengers always paying the fees, and opportunistic passengers deciding to buy a ticket or not on the basis of the expected cost of their trip. This one depends on the probability of being inspected when leaving the transportation network. Let $U_v^o$ be the expected value of the amount paid by an opportunistic passenger who leaves the transit system at $v \in V$. As for Brotcorne et al (2021), we define $U_v^o$ as the minimum between the ticket value and the expected value of the fine, i.e., $U_v^o = \min\{B, F\mathbb{P}_v^o\}$, where $B$ is the ticket price, $F$ is fine, and $\mathbb{P}_v^o$ is the probability that a specific opportunistic passenger is inspected leaving $v \in V$. We assume that the number of opportunistic passengers leaving $v \in V$, denoted $d_v^o$, is a random variable that follows a discrete uniform distribution, i.e., $d_v^o \sim \mathcal{U}\{0, \dots, \tilde{d}_v^o\}$, with $\tilde{d}_v^o \le d_v$, for any $v \in V$.

Fare inspection teams are subject to temporal labor constraints. As for Yin et al (2012), we embed the temporary labor constraints in an extended graph denoted as $G(V, E)$ defined as follows. Let $J$ be the set of time windows, where each of them limits the maximum time that a fare inspection team can remain on the network. Next, we partition $G$ into $|J|$ subgraphs such that subgraph $j$ contains all nodes and edges in the interval $[\tau_j, \bar{\tau}_j]$, including all edges in the set $\{(v^+, u) \in E: T(u) \in [\tau_j, \bar{\tau}_j]\} \cup \{(u, v^-) \in E: T(u) \in [\tau_j, \bar{\tau}_j]\}$, where $\tau_j$ and $\bar{\tau}_j$ are the start and end time of the $j$th time window. An exhaustive
explanation of the procedure for constructing the extended network can be found in Brotcorne et al (2021).

Let $\chi_e$ be a discrete random variable that defines the number of fare inspection teams at $e \in E$ and $X_e = E(\chi_e)$ be the expected number of inspection teams at $e \in E$. Furthermore, we define $Y_e$ as the expected number of inspection teams at $e \in \mathcal{E}$. Thus, the temporary constraints ensuring that a fare inspection team length path is smaller or equal to the labor working day duration are defined by:

$$ \sum_{e \in \delta^{+}(v)} Y_e - \sum_{e \in \delta^{-}(v)} Y_e = 0 \quad \forall v \in \mathcal{V} : v \neq v^{+}, v^{-} \quad (1) $$

$$ \sum_{e \in \delta^{+}(v^{+})} Y_e = n \quad (2) $$

$$ \sum_{e \in \delta^{-}(v^{-})} Y_e = n \quad (3) $$

$$ X_e = \sum_{e' \in E_e} Y_{e'} \quad \forall e \in E \quad (4) $$

$$ 0 \le X_e \le n \quad \forall e \in E \quad (5) $$

$$ 0 \le Y_e \le n \quad \forall e \in \mathcal{E}, \quad (6) $$

where $n$ is the number of fare inspection teams, $\delta^{+}(v)$ is the set of edges that leave node $v \in \mathcal{V}$, and $\delta^{-}(v)$ is the set of edges that enter node $v \in \mathcal{V}$. Constraints (1), (2), and (3) are flow conservation constraints in $\mathcal{G}$. Constraint (4) represents the relationship between $\mathcal{G}$ and $\mathcal{G}$ in terms of edges from the indexed set $E_e = \{e' = (u', v') \in \mathcal{E} : T(u') = T(u), S(u') = S(u), T(v') = T(v), S(v') = S(v)\}$ for all $e = (u, v) \in E$.

Under an in-station selective inspection policy fare inspection teams at edge $\xi(v)$ control passengers leaving node $v \in V$. Let $H_{\xi(v)}^i = \mathbb{P}(\chi_{\xi(v)} = i)$ be the probability that $i$ fare inspection teams are controlling the edge $\xi(v)$ for any $v \in V$. Then:

$$ \sum_{i=0}^{n} H_{\xi(v)}^{i} = 1 \quad \forall v \in V : d_{v} > 0 \quad (7) $$

$$ X_{\xi(v)} = \sum_{i=0}^{n} i H_{\xi(v)}^{i} \quad \forall v \in V : d_{v} > 0 \quad (8) $$

$$ H_{\xi(v)}^{i} \ge 0 \quad \forall v \in V : d_{v} > 0, i = 0, \dots, n. \quad (9) $$

Constraint (7) ensures with a probability equal to 1 that edge $\xi(v)$ is inspected by no more than $n$ fare inspection teams, i.e., $\mathbb{P}(\chi_{\xi(v)} \le n) = 1$. Constraint (8) is the definition of expected value, where $X_{\xi(v)}$ is the expected
explanation of the procedure for constructing the extended network can be found in Brotcorne et al (2021).

Let $\chi_e$ be a discrete random variable that defines the number of fare inspection teams at $e \in E$ and $X_e = E(\chi_e)$ be the expected number of inspection teams at $e \in E$. Furthermore, we define $Y_e$ as the expected number of inspection teams at $e \in \mathcal{E}$. Thus, the temporary constraints ensuring that a fare inspection team length path is smaller or equal to the labor working day duration are defined by:

$$ \sum_{e \in \delta^{+}(v)} Y_e - \sum_{e \in \delta^{-}(v)} Y_e = 0 \quad \forall v \in \mathcal{V} : v \neq v^{+}, v^{-} \quad (1) $$

$$ \sum_{e \in \delta^{+}(v^{+})} Y_e = n \quad (2) $$

$$ \sum_{e \in \delta^{-}(v^{-})} Y_e = n \quad (3) $$

$$ X_e = \sum_{e' \in E_e} Y_{e'} \quad \forall e \in E \quad (4) $$

$$ 0 \le X_e \le n \quad \forall e \in E \quad (5) $$

$$ 0 \le Y_e \le n \quad \forall e \in \mathcal{E}, \quad (6) $$

where $n$ is the number of fare inspection teams, $\delta^{+}(v)$ is the set of edges that leave node $v \in \mathcal{V}$, and $\delta^{-}(v)$ is the set of edges that enter node $v \in \mathcal{V}$. Constraints (1), (2), and (3) are flow conservation constraints in $\mathcal{G}$. Constraint (4) represents the relationship between $\mathcal{G}$ and $\mathcal{G}$ in terms of edges from the indexed set $E_e = \{e' = (u', v') \in \mathcal{E} : T(u') = T(u), S(u') = S(u), T(v') = T(v), S(v') = S(v)\}$ for all $e = (u, v) \in E$.

Under an in-station selective inspection policy fare inspection teams at edge $\xi(v)$ control passengers leaving node $v \in V$. Let $H_{\xi(v)}^i = \mathbb{P}(\chi_{\xi(v)} = i)$ be the probability that $i$ fare inspection teams are controlling the edge $\xi(v)$ for any $v \in V$. Then:

$$ \sum_{i=0}^{n} H_{\xi(v)}^{i} = 1 \quad \forall v \in V : d_{v} > 0 \quad (7) $$

$$ X_{\xi(v)} = \sum_{i=0}^{n} i H_{\xi(v)}^{i} \quad \forall v \in V : d_{v} > 0 \quad (8) $$

$$ H_{\xi(v)}^{i} \ge 0 \quad \forall v \in V : d_{v} > 0, i = 0, \dots, n. \quad (9) $$

Constraint (7) ensures with a probability equal to 1 that edge $\xi(v)$ is inspected by no more than $n$ fare inspection teams, i.e., $\mathbb{P}(\chi_{\xi(v)} \le n) = 1$. Constraint (8) is the definition of expected value, where $X_{\xi(v)}$ is the expected
number of fare inspection teams controlling $\xi(v)$ under an in-station selective inspection policy.

By definition, an in-station selective inspection policy considers that fare inspection teams randomly select passengers leaving the station for checking. Let the random variable $\omega_v^o$ | $\chi_{\xi(v)}$, $d_v^o$ be the number of opportunistic passengers inspected on $\xi(v) \in E$ given that this edge is controlled by $\chi_{\xi(v)}$ inspection teams and the number of opportunistic passengers is $d_v^o$. Let $h_{\xi(v)}$ be the number of passengers that a fare inspection team can inspect per time unit under a selective inspection policy at $\xi(v)$, and $\kappa$ be the average time it takes for passengers to leave the station platform with $\kappa < T(v') - T(v)$ for any $\xi(v) \in E$. We consider that $\omega_v^o$ | $\chi_{\xi(v)}$, $d_v^o$ follows a hypergeometric distribution because $\chi_{\xi(v)}$ fare inspection teams control $\lfloor h_{\xi(v)}\kappa \rfloor \chi_{\xi(v)}$ passengers at $\xi(v)$ (without replacement), out of a total of $d_v$ passengers, i.e., $\omega_v^o$ | $\chi_{\xi(v)}$, $d_v^o \sim \text{Hypergeometric}(d_v, d_v^o, \lfloor h_{\xi(v)}\kappa \rfloor \chi_{\xi(v)})$. Therefore, the conditional probability of inspecting at least one opportunistic passenger leaving $v$, given that $i$ fare inspection teams are controlling $\xi(v)$ and $j$ passengers are opportunistic is defined as follows:

$$f_{\xi(v)|i,j}^{o} = 1 - \mathbb{P}(\omega_{\xi(v)}^{o} = 0 | \chi_{\xi(v)} = i, d_{v}^{o} = j).$$

The probability that a specific opportunistic passenger be inspected leaving $v \in V$ is equal to the probability that the transit authority controls at least one opportunistic passenger in $v \in V$ and the specific opportunistic passenger is controlled. Assuming independence, we have:

$$ \mathbb{P}_v^o = \frac{1}{(\hat{d}_v^o + 1)^2} \sum_{i=0}^{n} \sum_{j=0}^{\hat{d}_v^o} f_{\xi(v)|i,j}^{o} H_{\xi(v)}^{i} \quad \forall v \in V \\ \mathbb{P}_v^o \ge 0 \quad \forall v \in V. \qquad (10) $$

We consider that the objective function of the transit authority is to maximize the expected revenue from ticket sales and fines collected from passengers. Thus, the leader's problem is defined as the LP:

$$ \mathbf{MGLP}: \max_{U,X,Y,H} \sum_{v \in V: d_v > 0} \mathbb{E}(d_v^o) U_v^o \qquad (11) $$

$$ \text{s.t: } U_v^o \le B \qquad \forall v \in V: d_v > 0 \qquad (12) $$

$$ U_v^o \le F \frac{1}{(\hat{d}_v^o + 1)^2} \sum_{i=0}^{n} \sum_{j=0}^{\hat{d}_v^o} f_{\xi(v)|i,j}^{o} H_{\xi(v)}^{i} \quad \forall v \in V: d_v > 0 \qquad (13) $$

$$ U_v^o \ge 0 \qquad \forall v \in V \qquad (14) \\ (1), (2), (3), (4), (5), (6), (7), (8), (9), (10), $$
number of fare inspection teams controlling $\xi(v)$ under an in-station selective inspection policy.

By definition, an in-station selective inspection policy considers that fare inspection teams randomly select passengers leaving the station for checking. Let the random variable $\omega_v^o$ | $\chi_{\xi(v)}$, $d_v^o$ be the number of opportunistic passengers inspected on $\xi(v) \in E$ given that this edge is controlled by $\chi_{\xi(v)}$ inspection teams and the number of opportunistic passengers is $d_v^o$. Let $h_{\xi(v)}$ be the number of passengers that a fare inspection team can inspect per time unit under a selective inspection policy at $\xi(v)$, and $\kappa$ be the average time it takes for passengers to leave the station platform with $\kappa < T(v') - T(v)$ for any $\xi(v) \in E$. We consider that $\omega_v^o$ | $\chi_{\xi(v)}$, $d_v^o$ follows a hypergeometric distribution because $\chi_{\xi(v)}$ fare inspection teams control $\lfloor h_{\xi(v)}\kappa \rfloor \chi_{\xi(v)}$ passengers at $\xi(v)$ (without replacement), out of a total of $d_v$ passengers, i.e., $\omega_v^o$ | $\chi_{\xi(v)}$, $d_v^o \sim \text{Hypergeometric}(d_v, d_v^o, \lfloor h_{\xi(v)}\kappa \rfloor \chi_{\xi(v)})$. Therefore, the conditional probability of inspecting at least one opportunistic passenger leaving $v$, given that $i$ fare inspection teams are controlling $\xi(v)$ and $j$ passengers are opportunistic is defined as follows:

$$f_{\xi(v)|i,j}^{o} = 1 - \mathbb{P}(\omega_{\xi(v)}^{o} = 0 | \chi_{\xi(v)} = i, d_{v}^{o} = j).$$

The probability that a specific opportunistic passenger be inspected leaving $v \in V$ is equal to the probability that the transit authority controls at least one opportunistic passenger in $v \in V$ and the specific opportunistic passenger is controlled. Assuming independence, we have:

$$ \begin{aligned} \mathbb{P}_v^o &= \frac{1}{(\hat{d}_v^o + 1)^2} \sum_{i=0}^n \sum_{j=0}^{\hat{d}_v^o} f_{\xi(v)|i,j}^{o} H_{\xi(v)}^i & \forall v \in V \\ \mathbb{P}_v^o \ge 0 & & \forall v \in V. \end{aligned} \quad (10) $$

We consider that the objective function of the transit authority is to maximize the expected revenue from ticket sales and fines collected from passengers. Thus, the leader's problem is defined as the LP:

$$ \mathbf{MGLP}: \max_{U,X,Y,H} \sum_{v \in V: d_v > 0} \mathbb{E}(d_v^o) U_v^o \quad (11) $$

$$ \text{s.t: } U_v^o \le B \qquad \forall v \in V: d_v > 0 \quad (12) $$

$$ U_v^o \le F \frac{1}{(\hat{d}_v^o + 1)^2} \sum_{i=0}^{n} \sum_{j=0}^{\hat{d}_v^o} f_{\xi(v)|i,j}^{o} H_{\xi(v)}^i \quad \forall v \in V: d_v > 0 \quad (13) $$

$$ U_v^o \ge 0 \qquad \forall v \in V \quad (14) $$
where $E(d_v^o) = 0.5\hat{d}_v^o$. Constraints (12) and (13) are the optimal reaction of the opportunistic passenger to the transit authority's decisions because $U_v^o = \min\{B, F\mathbb{P}_v^o\}$ for any $v \in V$ and MGLP is a maximization optimization problem. The expected revenue of honest passengers is omitted from the objective function since it is a constant.

The probability that the transit authority controls $\xi(v)$ is equal to the probability that the number of fare inspection teams at $\xi(v)$ is strictly greater than zero, i.e., $P(\chi_{\xi(v)} > 0) = 1 - P(\chi_{\xi(v)} = 0) = 1 - H_{\xi(v)}^0$ for any $v \in V$. Thus, the optimal fare inspection patrolling strategy of the transit authority is defined by $\{1 - H_{\xi(v)}^0\}_{v \in V}$, where $H_{\xi(v)}^0$ is the optimal variable of MGLP for any $v \in V$. The optimal solution of the MGLP model offers more insights and allows to enrich the fare inspection patrolling strategy definition in several ways. For example, the optimal fare inspection patrolling strategy can refer to the probability with which the station $v \in V$ is controlled by $i$ fare inspection teams, i.e., $\{H_{\xi(v)}^i\}_{v \in V}$ with $i = 0, ..., n$.

## 4 An equivalent unpredictable patrolling schedule formulation

The MGLP model is a formulation for defining a fare inspection patrolling strategy under an in-station selective inspection policy. The fare inspection patrolling strategy resulting from MGLP is useful for the transit authority if it can be operationally implemented by an unpredictable patrolling schedule. More precisely, a set of fare inspection patrolling schedules and their respective probabilities of being selected, whose systematic day-to-day application matches in the medium term with the inspection probabilities defined by the patrolling strategy resulting from MGLP.

Let $S$ be the set of all fare inspection patrolling schedules. Each patrolling schedule defines the patrolling path for each fare inspection team. The unpredictable patrolling schedule requires to determine the set of patrolling schedules and their respective probabilities of being selected. Let $\pi_s \in [0, 1]$ be the probability of selecting the patrolling schedule $s \in S$, with $\sum_{s \in S} \pi_s = 1$. In a practical setting, $\pi_s$ is the frequency at which the transit authority implements the patrolling schedule $s$.

The expected number of fare inspection teams at $e \in E$ ($e \in \mathcal{E}$), and the probability that $i$ fare inspection teams are controlling $\xi(v) \in E$ can be expressed as a convex combination of patrolling schedules if the set of all patrolling schedules is known. That is, $X_e = \sum_{s \in S} \pi_s X_{e|s}$ ($Y_e = \sum_{s \in S} \pi_s Y_{e|s}$), and $H_{\xi(v)}^i = \sum_{s \in S} \pi_s H_{\xi(v)|s}^i$, with $\sum_{s \in S} \pi_s = 1$, where $X_{e|s}$ ($Y_{e|s}$) is the number of fare inspection teams at $e \in E$ ($e \in \mathcal{E}$) on the patrolling schedule $s$, and $H_{\xi(v)|s}^i$ is equal to 1 if $\xi(v) \in E$ is controlled by $i$ fare inspection teams on the patrolling schedule $s$, but 0 otherwise. In particular, $X_{\xi(v)|s}$ is the number of fare inspection teams controlling edge $\xi(v)$ on the patrolling schedule $s$. By implementing the change of variables in MGLP, we obtain the following LP:
where $E(d_v^o) = 0.5\hat{d}_v^o$. Constraints (12) and (13) are the optimal reaction of the opportunistic passenger to the transit authority's decisions because $U_v^o = \min\{B, F\mathbb{P}_v^o\}$ for any $v \in V$ and MGLP is a maximization optimization problem. The expected revenue of honest passengers is omitted from the objective function since it is a constant.

The probability that the transit authority controls $\xi(v)$ is equal to the probability that the number of fare inspection teams at $\xi(v)$ is strictly greater than zero, i.e., $\mathbb{P}(\chi_{\xi(v)} > 0) = 1 - \mathbb{P}(\chi_{\xi(v)} = 0) = 1 - H_{\xi(v)}^0$ for any $v \in V$. Thus, the optimal fare inspection patrolling strategy of the transit authority is defined by $\{1 - H_{\xi(v)}^0\}_{v \in V}$, where $H_{\xi(v)}^0$ is the optimal variable of MGLP for any $v \in V$. The optimal solution of the MGLP model offers more insights and allows to enrich the fare inspection patrolling strategy definition in several ways. For example, the optimal fare inspection patrolling strategy can refer to the probability with which the station $v \in V$ is controlled by $i$ fare inspection teams, i.e., $\{H_{\xi(v)}^i\}_{v \in V}$ with $i = 0, ..., n$.

# 4 An equivalent unpredictable patrolling schedule formulation

The MGLP model is a formulation for defining a fare inspection patrolling strategy under an in-station selective inspection policy. The fare inspection patrolling strategy resulting from MGLP is useful for the transit authority if it can be operationally implemented by an unpredictable patrolling schedule. More precisely, a set of fare inspection patrolling schedules and their respective probabilities of being selected, whose systematic day-to-day application matches in the medium term with the inspection probabilities defined by the patrolling strategy resulting from MGLP.

Let $S$ be the set of all fare inspection patrolling schedules. Each patrolling schedule defines the patrolling path for each fare inspection team. The unpredictable patrolling schedule requires to determine the set of patrolling schedules and their respective probabilities of being selected. Let $\pi_s \in [0, 1]$ be the probability of selecting the patrolling schedule $s \in S$, with $\sum_{s \in S} \pi_s = 1$. In a practical setting, $\pi_s$ is the frequency at which the transit authority implements the patrolling schedule $s$.

The expected number of fare inspection teams at $e \in E$ ($e \in \mathcal{E}$), and the probability that $i$ fare inspection teams are controlling $\xi(v) \in E$ can be expressed as a convex combination of patrolling schedules if the set of all patrolling schedules is known. That is, $X_e = \sum_{s \in S} \pi_s X_{e|s}$ ($Y_e = \sum_{s \in S} \pi_s Y_{e|s}$), and $H_{\xi(v)}^i = \sum_{s \in S} \pi_s H_{\xi(v)|s}^i$, with $\sum_{s \in S} \pi_s = 1$, where $X_{e|s}$ ($Y_{e|s}$) is the number of fare inspection teams at $e \in E$ ($e \in \mathcal{E}$) on the patrolling schedule $s$, and $H_{\xi(v)|s}^i$ is equal to 1 if $\xi(v) \in E$ is controlled by $i$ fare inspection teams on the patrolling schedule $s$, but 0 otherwise. In particular, $X_{\xi(v)|s}$ is the number of fare inspection teams controlling edge $\xi(v)$ on the patrolling schedule $s$. By implementing the change of variables in MGLP, we obtain the following LP:
$$
\begin{align}
\textbf{MXLP}: \max_{U, \pi} \quad & \sum_{v \in V: d_v > 0} \mathbb{E}(d_v^o) U_v^o \tag{15} \\
\text{s.t:} \quad & U_v^o \le B \tag{12}
\end{align}
$$

$$
U_v^o \le F \frac{1}{(\hat{d}_v^o + 1)^2} \sum_{i=0}^{n} \sum_{j=0}^{\hat{d}_v^o} f_{\xi(v)|i,j}^o \sum_{s \in \mathcal{S}} \pi_s H_{\xi(v)|s}^i \quad \forall v \in V : d_v > 0 \tag{16}
$$

$$
U_v^o \ge 0 \qquad \forall v \in V \quad (14)
$$

$$
\sum_{s \in \mathcal{S}} \pi_s = 1 \tag{17}
$$

$$
\pi_s \ge 0 \qquad \forall s \in \mathcal{S}, \quad (18)
$$

where each patrolling schedule satisfies:

$$
\sum_{e \in \delta^{+}(v)} Y_{e|s} - \sum_{e \in \delta^{-}(v)} Y_{e|s} = 0 \qquad \forall v \in \mathcal{V}: v \neq v^{+}, v^{-} \tag{19}
$$

$$
\sum_{e \in \delta^{+}(v^{+})} Y_{e|s} = n \tag{20}
$$

$$
\sum_{e \in \delta^{-}(v^{-})} Y_{e|s} = n \tag{21}
$$

$$
X_{e|s} = \sum_{e' \in E_e} Y_{e'|s} \qquad \forall e \in E \tag{22}
$$

$$
X_{\xi(v)|s} = \sum_{i=0}^{n} i H_{\xi(v)|s}^{i} \qquad \forall v \in V : d_v > 0 \qquad (23)
$$

$$
\sum_{i=0}^{n} H_{\xi(v)|s}^{i} = 1 \qquad \forall v \in V : d_v > 0 \tag{24}
$$

$$
X_{e|s} \in \{0, \dots, n\} \qquad \forall e \in E \tag{25}
$$

$$
Y_{e|s} \in \{0, \dots, n\} \qquad \forall e \in \mathcal{E} \tag{26}
$$

$$
H_{\xi(v)|s}^{i} \in \{0, 1\} \qquad \forall v \in V, i = 0, \dots, n. \tag{27}
$$

For a realistic temporal-spatial public transportation network, it is impossi-
ble to evaluate each patrolling schedule since the size of S grows exponentially
with the size of G. Following Brotcorne et al (2021), we propose to rely on a
column generation (GC) approach to solve MXLP.

The CG consist in solving MXLP with only a subset of fare inspection
patrolling schedules S<sub>r</sub>(⊂ S). Then iteratively, fare inspection patrolling sched-
ules that have the potential to improve the objective function are added to the
$$
\begin{align}
\textbf{MXLP}: \max_{U, \pi} \quad & \sum_{v \in V: d_v > 0} \mathbb{E}(d_v^o) U_v^o \tag{15} \\
\text{s.t:} \quad & U_v^o \le B \tag{12}
\end{align}
$$

$$
U_v^o \le F \frac{1}{(\hat{d}_v^o + 1)^2} \sum_{i=0}^{n} \sum_{j=0}^{\hat{d}_v^o} f_{\xi(v)|i,j}^o \sum_{s \in \mathcal{S}} \pi_s H_{\xi(v)|s}^i \quad \forall v \in V : d_v > 0 \tag{16}
$$

$$
U_v^o \ge 0 \qquad \forall v \in V \quad (14)
$$

$$
\sum_{s \in \mathcal{S}} \pi_s = 1 \tag{17}
$$

$$
\pi_s \ge 0 \qquad \forall s \in \mathcal{S}, \quad (18)
$$

where each patrolling schedule satisfies:

$$
\sum_{e \in \delta^{+}(v)} Y_{e|s} - \sum_{e \in \delta^{-}(v)} Y_{e|s} = 0 \qquad \forall v \in \mathcal{V}: v \neq v^{+}, v^{-} \tag{19}
$$

$$
\sum_{e \in \delta^{+}(v^{+})} Y_{e|s} = n \tag{20}
$$

$$
\sum_{e \in \delta^{-}(v^{-})} Y_{e|s} = n \tag{21}
$$

$$
X_{e|s} = \sum_{e' \in E_e} Y_{e'|s} \qquad \forall e \in E \tag{22}
$$

$$
X_{\xi(v)|s} = \sum_{i=0}^{n} i H_{\xi(v)|s}^{i} \qquad \forall v \in V : d_v > 0 \tag{23}
$$

$$
\sum_{i=0}^{n} H_{\xi(v)|s}^{i} = 1 \qquad \forall v \in V : d_v > 0 \tag{24}
$$

$$
X_{e|s} \in \{0, \dots, n\} \qquad \forall e \in E \tag{25}
$$

$$
Y_{e|s} \in \{0, \dots, n\} \qquad \forall e \in \mathcal{E} \tag{26}
$$

$$
H_{\xi(v)|s}^{i} \in \{0, 1\} \qquad \forall v \in V, i = 0, \dots, n. \tag{27}
$$

For a realistic temporal-spatial public transportation network, it is impossi-
ble to evaluate each patrolling schedule since the size of S grows exponentially
with the size of G. Following Brotcorne et al (2021), we propose to rely on a
column generation (GC) approach to solve MXLP.

The CG consist in solving MXLP with only a subset of fare inspection
patrolling schedules S<sub>r</sub>(⊂ S). Then iteratively, fare inspection patrolling sched-
ules that have the potential to improve the objective function are added to the
model. This problem is named the restricted master problem RMP. Let $Z_{RMP}^*$ be the optimal objective function of RMP, and $\beta_v^* \ge 0$ and $\theta^*$ are the dual variable values corresponding to constraints (16) and (17), respectively. Then, $Z_{RMP}^*$ is an optimal objective function of MXLP if all of the reduced costs are non-positive, i.e., $\bar{c}_s = F \sum_{v \in V} \beta_v^* \frac{1}{(\hat{d}_v^o+1)^2} \sum_{i=0}^n \sum_{j=0}^{\hat{d}_v^o} f_{\xi(v)|i,j}^o H_{\xi(v)|s}^i - \theta^* \le 0$.

To generate further patrolling schedules or check the optimality of the current solution we need to solve the following pricing problem:

$$ \mathbf{SP}: \max_{X,Y,H} \bar{c}_s = F \sum_{v \in V} \beta_v^* \frac{1}{(\hat{d}_v^o + 1)^2} \sum_{i=0}^{n} \sum_{j=0}^{\hat{d}_v^o} f_{\xi(v)|i,j}^o H_{\xi(v)|s}^i - \theta^* \quad (28) $$

$$ \text{s.t:} \quad (19), (20), (21), (22), (24), (25), (26), (27). $$

If the optimal objective function value of SP is positive, then the fare inspection patrolling schedule with the maximum reduced cost $\bar{c}_s$ is added to RMP as a new entering patrolling schedule, and the updated RMP is solved again. Otherwise, $Z_{RMP}^*$ is an optimal solution to MXLP, i.e., $Z_{RMP}^* = Z_{MXLP}^*$, where $Z_{MXLP}^*$ is the optimal objective function of the MXLP model.

MGLP and MXLP are two equivalent optimization problems since MXLP is a reformulation of MGLP. Thus, $Z_{MXLP}^* = Z_{MGLP}^*$, where $Z_{MGLP}^*$ is the optimal objective function of MGLP.

The SP model being an integer multi-commodity network flow problem is NP-complete. We next suggest to reduce the complexity and computational time of the SP model by exploiting the optimal variables resulting from MGLP. More precisely, let $E_0 = \{e \in E : X_e = 0\}$ ($E_0 = \{e \in E : Y_e = 0\}$) be the set of edges not used by fare inspection teams where $X_e$ ($Y_e$) is the optimal variable of MGLP. Consequently, for any $e \in E_0$ ($e \in E_0$), we have $\pi_s = 0$ or $X_{e|s} = 0$ ($Y_{e|s} = 0$) for any $s \in S$ because $X_e = \sum_{s \in S} \pi_s X_{e|s}$ ($Y_e = \sum_{s \in S} \pi_s Y_{e|s}$). Thus, an equivalent pricing problem can be defined by including $X_{e|s} = 0$ ($Y_{e|s} = 0$) for any $e \in E_0$ ($e \in E_0$) in the SP model, denoted as RSP.

The optimal solution of MXLP is an unpredictable patrolling schedule, i.e., a set of fare inspection patrolling schedules with a positive probability of being selected. Let $\{(s, \pi_s) : \pi_s > 0\}_{s \in S_r}$ be the optimal unpredictable patrolling schedule resulting from MXLP, and $\hat{S}_r = \{s \in S_r : \pi_s > 0\}$ be the set of useful fare inspection patrolling schedules. The pseudo-code of the CG procedure using RMP-RSP, denoted by CG-MX, is described in Algorithm 1.
model. This problem is named the restricted master problem RMP. Let $Z_{RMP}^*$ be the optimal objective function of RMP, and $\beta_v^* \ge 0$ and $\theta^*$ are the dual variable values corresponding to constraints (16) and (17), respectively. Then, $Z_{RMP}^*$ is an optimal objective function of MXLP if all of the reduced costs are non-positive, i.e., $\bar{c}_s = F \sum_{v \in V} \beta_v^* \frac{1}{(\hat{d}_v^o+1)^2} \sum_{i=0}^n \sum_{j=0}^{\hat{d}_v^o} f_{\xi(v)|i,j}^o H_{\xi(v)|s}^i - \theta^* \le 0$.

To generate further patrolling schedules or check the optimality of the current solution we need to solve the following pricing problem:

$$ \textbf{SP}: \max_{X,Y,H} \bar{c}_s = F \sum_{v \in V} \beta_v^* \frac{1}{(\hat{d}_v^o + 1)^2} \sum_{i=0}^{n} \sum_{j=0}^{\hat{d}_v^o} f_{\xi(v)|i,j}^o H_{\xi(v)|s}^i - \theta^* \quad (28) $$

$$ \text{s.t:} \quad (19), (20), (21), (22), (24), (25), (26), (27). $$

If the optimal objective function value of SP is positive, then the fare inspection patrolling schedule with the maximum reduced cost $\bar{c}_s$ is added to RMP as a new entering patrolling schedule, and the updated RMP is solved again. Otherwise, $Z_{RMP}^*$ is an optimal solution to MXLP, i.e., $Z_{RMP}^* = Z_{MXLP}^*$, where $Z_{MXLP}^*$ is the optimal objective function of the MXLP model.

MGLP and MXLP are two equivalent optimization problems since MXLP is a reformulation of MGLP. Thus, $Z_{MXLP}^* = Z_{MGLP}^*$, where $Z_{MGLP}^*$ is the optimal objective function of MGLP.

The SP model being an integer multi-commodity network flow problem is NP-complete. We next suggest to reduce the complexity and computational time of the SP model by exploiting the optimal variables resulting from MGLP. More precisely, let $E_0 = \{e \in E : X_e = 0\}$ ($E_0 = \{e \in E : Y_e = 0\}$) be the set of edges not used by fare inspection teams where $X_e$ ($Y_e$) is the optimal variable of MGLP. Consequently, for any $e \in E_0$ ($e \in E_0$), we have $\pi_s = 0$ or $X_{e|s} = 0$ ($Y_{e|s} = 0$) for any $s \in S$ because $X_e = \sum_{s \in S} \pi_s X_{e|s}$ ($Y_e = \sum_{s \in S} \pi_s Y_{e|s}$). Thus, an equivalent pricing problem can be defined by including $X_{e|s} = 0$ ($Y_{e|s} = 0$) for any $e \in E_0$ ($e \in E_0$) in the SP model, denoted as RSP.

The optimal solution of MXLP is an unpredictable patrolling schedule, i.e., a set of fare inspection patrolling schedules with a positive probability of being selected. Let $\{(s, \pi_s) : \pi_s > 0\}_{s \in S_r}$ be the optimal unpredictable patrolling schedule resulting from MXLP, and $\hat{S}_r = \{s \in S_r : \pi_s > 0\}$ be the set of useful fare inspection patrolling schedules. The pseudo-code of the CG procedure using RMP-RSP, denoted by CG-MX, is described in Algorithm 1.
**Algorithm 1** CG-MX

1: $E_0 = \{e \in E : X_e = 0\}$, $\mathcal{E}_0 = \{e \in E : Y_e = 0\}$ ← solve MGLP

2: Set $s = 0$

3: Set $\mathbf{H}^{(0)} = 0$

4: $\beta^{(0)}, \theta^{(0)}$ ← solve RMP

5: $\bar{c}_s^{(1)}, \mathbf{X}^{(1)}, \mathbf{Y}^{(1)}, \mathbf{H}^{(1)}$ ← solve RSP

6: **while** $\bar{c}_s^{(s)} > 0$ **do**

7: Set $s = s + 1$

8: $\bar{c}_s^{(s)}, \mathbf{X}^{(s)}, \mathbf{Y}^{(s)}, \mathbf{H}^{(s)}$ ← solve RSP

9: $\beta^{(s)}, \theta^{(s)}$ ← solve RMP

10: **end while**

11: Return unpredictable patrolling schedule : $\{(s, \pi_s) : \pi_s > 0\}_{s \in S_r}$

# 5 Computational study

In this section, we first present numerical results to evaluate the performance of the MGLP model and CG-MX Algorithm in terms of CPU time and optimality gap. Then we discuss managerial insights for the transit authority management.

Computational experiments are performed on the Los Angeles metro (LA metro), with 6 lines, 77 stations, and a total track length of 169 kilometers. The LA metro operates 23 hours a day (1380 minutes) and is used by 359 016 daily passengers. We generated a graph $G$ with $|V| = 16 776$ and $|E| = 33 048$ on the basis of the LA metro timetable. Furthermore, considering three time windows ($|J| = 3$) deployed symmetrically during a day, we generated $G$ with $|V| = 17 007$ and $|\mathcal{E}| = 33 070$.

Twenty randomized test problems (test set) were generated, where each of them considers $n \in \{5, 15, 25, 35, 45, 55, 65, 75\}$ leading to a total of 160 instances with the next common parameters. The number of passengers leaving a station is uniformly distributed according to $d_v = \mathcal{U}\{0, ..., 45\}$ for any $v \in V$. Opportunistic passengers are uniformly distributed according to $d_v^o = \mathcal{U}\{0, ..., d_v^o\}$ with $d_v^o = \lfloor 0.4d_v \rfloor$ for any $v \in V$. The time for passengers to leave a station platform is $\kappa = U[1, 1.5]$ minutes for any $v \in V$. The inspection rate (passengers per minute) of a fare inspection team is $h_{\mathcal{E}(v)} = \mathcal{U}\{2, .., 5\}$ for any $v \in V$. The ticket price is $B = 1.5$, and the fine is $F = 75$, so the ratio between the ticket price and the fine is equal to 2%.

Graphs $G$ and $\mathcal{G}$ were simultaneously constructed in Python 3.7. The MGLP, RMP, and RSP models are solved using CPLEX 20.1. The CG-MX Algorithm stopping criterion is $\bar{c}_s^{(s)} \le 0$ or 36 000 seconds of CPU time. All tests were done on a PC with an Intel Core i7 2.3 GHz processor and 16 GB RAM.
**Algorithm 1 CG-MX**

1: $E_0 = \{e \in E : X_e = 0\}$, $\mathcal{E}_0 = \{e \in E : Y_e = 0\}$ ← solve MGLP

2: Set $s = 0$

3: Set $\mathbf{H}^{(0)} = 0$

4: $\beta^{(0)}, \theta^{(0)}$ ← solve RMP

5: $\bar{c}_s^{(1)}, \mathbf{X}^{(1)}, \mathbf{Y}^{(1)}, \mathbf{H}^{(1)}$ ← solve RSP

6: **while** $\bar{c}_s^{(s)} > 0$ **do**

7: Set $s = s + 1$

8: $\bar{c}_s^{(s)}, \mathbf{X}^{(s)}, \mathbf{Y}^{(s)}, \mathbf{H}^{(s)}$ ← solve RSP

9: $\beta^{(s)}, \theta^{(s)}$ ← solve RMP

10: **end while**

11: Return unpredictable patrolling schedule : $\{(s, \pi_s) : \pi_s > 0\}_{s \in S_r}$

# 5 Computational study

In this section, we first present numerical results to evaluate the performance of the MGLP model and CG-MX Algorithm in terms of CPU time and optimality gap. Then we discuss managerial insights for the transit authority management.

Computational experiments are performed on the Los Angeles metro (LA metro), with 6 lines, 77 stations, and a total track length of 169 kilometers. The LA metro operates 23 hours a day (1380 minutes) and is used by 359 016 daily passengers. We generated a graph $G$ with $|V| = 16 776$ and $|E| = 33 048$ on the basis of the LA metro timetable. Furthermore, considering three time windows ($|J| = 3$) deployed symmetrically during a day, we generated $G$ with $|V| = 17 007$ and $|\mathcal{E}| = 33 070$.

Twenty randomized test problems (test set) were generated, where each of them considers $n \in \{5, 15, 25, 35, 45, 55, 65, 75\}$ leading to a total of 160 instances with the next common parameters. The number of passengers leaving a station is uniformly distributed according to $d_v = U\{0, ..., 45\}$ for any $v \in V$. Opportunistic passengers are uniformly distributed according to $d_v^o = U\{0, ..., d_v^o\}$ with $d_v^o = \lfloor 0.4d_v \rfloor$ for any $v \in V$. The time for passengers to leave a station platform is $\kappa = U[1, 1.5]$ minutes for any $v \in V$. The inspection rate (passengers per minute) of a fare inspection team is $h_{\mathcal{E}(v)} = U\{2, .., 5\}$ for any $v \in V$. The ticket price is $B = 1.5$, and the fine is $F = 75$, so the ratio between the ticket price and the fine is equal to 2%.

Graphs $G$ and $\mathcal{G}$ were simultaneously constructed in Python 3.7. The MGLP, RMP, and RSP models are solved using CPLEX 20.1. The CG-MX Algorithm stopping criterion is $\bar{c}_s^{(s)} \le 0$ or 36 000 seconds of CPU time. All tests were done on a PC with an Intel Core i7 2.3 GHz processor and 16 GB RAM.
## 5.1 Performance of MGLP model and CG-MX Algorithm

Figure 2 states the CPU times to solve the MGLP model for all instances and fare inspection teams as well as the average CPU time. Moreover, Figure 2 is a box plot showing for each number of inspection teams the median, quartiles, and outliers.

<figure><img src="image_3.png" /><figcaption>Fig. 2 CPU time to solve the MGLP model</figcaption></figure>

The MGLP model is solved to optimality for all instances with mean and maximum CPU times of 28 s and 69 s, respectively. From Figure 2, we observe that the CPU time to solve MGLP increases with the inspection teams number, even if the highest CPU time is reached when 65 inspection teams are deployed ($n = 65$).

On the other hand, no instance can be solved by the CG-MX Algorithm within the time limit. Consequently, we have that $Z_{RMP} < Z_{MXLP}^* = Z_{MGLP}^*$ where $Z_{RMP}$ is the RMP model objective function value when the CG-MX Algorithm reaches the time limit.

The quality of the unpredictable patrolling schedule resulting from the CG-MX Algorithm can be measured by the optimality gap between the optimal MGLP objective function and the RMP objective function for the instances that can not be solved to optimality within the time limit, i.e.,

$$Gap(\%) = 100 \times \frac{Z_{MGLP}^* - Z_{RMP}}{Z_{MGLP}^*},$$

because $Z_{MGLP}^* = Z_{MXLP}^*$. Figure 3 shows the optimality gap with respect to the fare inspection teams.

From Figure 3, we observe that the optimality gap is increasing in the number of inspection teams up to $n = 45$ and then decreases reaching the
## 5.1 Performance of MGLP model and CG-MX Algorithm

Figure 2 states the CPU times to solve the MGLP model for all instances and fare inspection teams as well as the average CPU time. Moreover, Figure 2 is a box plot showing for each number of inspection teams the median, quartiles, and outliers.

<figure><img src="image_3.png" /><figcaption>Fig. 2 CPU time to solve the MGLP model</figcaption></figure>

The MGLP model is solved to optimality for all instances with mean and maximum CPU times of 28 s and 69 s, respectively. From Figure 2, we observe that the CPU time to solve MGLP increases with the inspection teams number, even if the highest CPU time is reached when 65 inspection teams are deployed ($n = 65$).

On the other hand, no instance can be solved by the CG-MX Algorithm within the time limit. Consequently, we have that $Z_{RMP} < Z_{MXLP}^* = Z_{MGLP}^*$ where $Z_{RMP}$ is the RMP model objective function value when the CG-MX Algorithm reaches the time limit.

The quality of the unpredictable patrolling schedule resulting from the CG-MX Algorithm can be measured by the optimality gap between the optimal MGLP objective function and the RMP objective function for the instances that can not be solved to optimality within the time limit, i.e.,

$$Gap(\%) = 100 \times \frac{Z_{MGLP}^* - Z_{RMP}}{Z_{MGLP}^*},$$

because $Z_{MGLP}^* = Z_{MXLP}^*$. Figure 3 shows the optimality gap with respect to the fare inspection teams.

From Figure 3, we observe that the optimality gap is increasing in the number of inspection teams up to $n = 45$ and then decreases reaching the
<figure><img src="image_4.png" /><figcaption>**Fig. 3** Optimality gap of the unpredictable patrolling schedule resulting from the CG-MX Algorithm</figcaption></figure>

minimum for $n = 65$. The maximum optimality gap is reached for the instances with the maximum number of passengers leaving a station. To confirm this statement, we have generated several additional test problems with a maximum number of passengers leaving a station equal to {35, 55, 65} leading to the same conclusion.

For all instances, we compute the CG-MX Algorithm efficiency defined as the ratio between the number of useful patrolling schedules and the number of patrolling schedules generated by the column generation procedure using RMP-RSP, i.e., $\eta(\%) = 100 \times |\hat{S}_r| / |S_r|$.

<figure><img src="image_5.png" /><figcaption>**Fig. 4** Efficiency of CG-MX Algorithm</figcaption></figure>
<figure><img src="image_4.png" /><figcaption>**Fig. 3** Optimality gap of the unpredictable patrolling schedule resulting from the CG-MX Algorithm</figcaption></figure>

minimum for $n = 65$. The maximum optimality gap is reached for the instances with the maximum number of passengers leaving a station. To confirm this statement, we have generated several additional test problems with a maximum number of passengers leaving a station equal to {35, 55, 65} leading to the same conclusion.

For all instances, we compute the CG-MX Algorithm efficiency defined as the ratio between the number of useful patrolling schedules and the number of patrolling schedules generated by the column generation procedure using RMP-RSP, i.e., $\eta(\%) = 100 \times |\hat{S}_r| / |S_r|$.

<figure><img src="image_5.png" /><figcaption>**Fig. 4** Efficiency of CG-MX Algorithm</figcaption></figure>
As shown in Figure 4, the CG-MX Algorithm efficiency is increasing with the number of inspection teams. For $n = 5$ an average of 1382 patrolling schedules were generated ($|S_r| = 1382$) but only 422 were useful ($|\hat{S}_r| = 422$). Thus, the Algorithm efficiency when 5 inspection teams are deployed is equal to 30%. On the contrary, for $n = 75$ an average of 95 patrolling schedules were generated ($|S_r| = 95$) and 94 were useful ($|\hat{S}_r| = 94$). Thus, the Algorithm efficiency associated with a deployment of 75 inspection teams reached 99%. It should be noted that the number of patrolling schedules generated by the CG-MX Algorithm is decreasing with the number of inspection teams because the pricing problem is more difficult to solve.

## 5.2 Managerial insights for the transit authority

In this section, we derive management insights for the transit authority related to the evasion rate, inspection rate, and the systematic day-to-day application of the unpredictable patrolling schedule.

For each instance, we compute the evasion rate induced by the fare inspection patrolling strategy and unpredictable patrolling schedule resulting from the solution of MGLP model and CG-MX algorithm, respectively. The evasion rate is measured by the ratio of the expected number of evaders to the total number of the transportation network users, i.e.,

$$ER(\%) = 100 \times \frac{\sum_{v \in V: U_v^o < B} E(d_v^o)}{\sum_{v \in V} d_v},$$

where $U_v^o$ is the optimal variable for MGLP model and the feasible variable for CG-MX Algorithm, respectively. The average evasion rate for all instances and fare inspection teams is shown in Figure 5.

<figure><img src="image_6.png" /><figcaption>Fig. 5 Average evasion rate induced by the MGLP model solution and CG-MX Algorithm</figcaption></figure>
As shown in Figure 4, the CG-MX Algorithm efficiency is increasing with the number of inspection teams. For $n = 5$ an average of 1382 patrolling schedules were generated ($|S_r| = 1382$) but only 422 were useful ($|\hat{S}_r| = 422$). Thus, the Algorithm efficiency when 5 inspection teams are deployed is equal to 30%. On the contrary, for $n = 75$ an average of 95 patrolling schedules were generated ($|S_r| = 95$) and 94 were useful ($|\hat{S}_r| = 94$). Thus, the Algorithm efficiency associated with a deployment of 75 inspection teams reached 99%. It should be noted that the number of patrolling schedules generated by the CG-MX Algorithm is decreasing with the number of inspection teams because the pricing problem is more difficult to solve.

## 5.2 Managerial insights for the transit authority

In this section, we derive management insights for the transit authority related to the evasion rate, inspection rate, and the systematic day-to-day application of the unpredictable patrolling schedule.

For each instance, we compute the evasion rate induced by the fare inspection patrolling strategy and unpredictable patrolling schedule resulting from the solution of MGLP model and CG-MX algorithm, respectively. The evasion rate is measured by the ratio of the expected number of evaders to the total number of the transportation network users, i.e.,

$$ER(\%) = 100 \times \frac{\sum_{v \in V: U_v^o < B} E(d_v^o)}{\sum_{v \in V} d_v},$$

where $U_v^o$ is the optimal variable for MGLP model and the feasible variable for CG-MX Algorithm, respectively. The average evasion rate for all instances and fare inspection teams is shown in Figure 5.

<figure><img src="image_6.png" /><figcaption>Fig. 5 Average evasion rate induced by the MGLP model solution and CG-MX Algorithm</figcaption></figure>
The gap observed in Figure 5 between the evasion rate induced by the fare inspection patrolling strategy and the unpredictable patrolling schedule is due to the feasibility (with respect to the optimum) of the unpredictable patrolling schedule resulting from solving the CG-MX Algorithm (with respect to MGLP).

As expected, evasion rate is decreasing with the number of fare inspection teams. We observed the smallest number of fare inspection teams inducing an evasion rate of less than or equal to 1%, which represents opportunistic passengers who do not pay the fine or who do not react to the fare inspection as a mechanism to inhibit evasion. Under the optimal patrolling strategy (Figure 5) the smallest number of inspection teams inducing an evasion rate less than or equal to 1% is achieved with 65 deployed fare inspection teams. Even if the unpredictable patrolling schedule generates an average evasion rate equal to 2.2%. This value represents the transit authority's loss of considering a near-optimal solution for MXLP.

In the following we discuss managerial insights considering the deployment of 65 inspection teams. The minimum, maximum, and average optimality gap of the unpredictable patrolling schedule associated with the deployment of 65 inspection teams are respectively 1.55%, 1.70%, and 1.63%. The inspection rate, defined as the ratio between checked passengers and all passengers (Barabino et al (2014)), is computed as:

$$IR(\%) = 100 \times \frac{\sum_{v \in V} \min \{d_v, \lfloor h_{\xi(v)} \kappa \rfloor X_{\xi(v)}\}}{\sum_{v \in V} d_v},$$

where $X_{\xi(v)}$ is the optimal variable of the MGLP model, and $X_{\xi(v)} = \sum_{s \in \hat{S}_r} \pi_s X_{\xi(v)|s}$ for CG-MX Algorithm. The average optimality gap, average evasion rate, average inspection rate, and average number of checked passengers (\#IP) induced by the fare inspection patrolling strategy and the unpredictable patrolling schedule, respectively, are defined in Table 2.

<table><caption>**Table 2** Optimality gap, evasion rate, inspection rate, and checked passengers when $n = 65$</caption><thead><tr><th></th><th>Gap (%)</th><th>ER(%)</th><th>IR(%)</th><th>\# IP</th></tr></thead><tbody><tr><td>Patroling Strategy</td><td>0</td><td>0.98</td><td>9.1</td><td>35 494</td></tr><tr><td>Unpredictable Schedule</td><td>1.63</td><td>2.20</td><td>8.4</td><td>32 948</td></tr></tbody></table>

The joint strategy-schedule approach to address the operational implementation of a fare inspection patrolling strategy provides a mechanism for determining the quality of the unpredictable patrolling schedule that results from the CG-MX Algorithm. Thus, by considering an unpredictable patrolling schedule that is on average no more than 1.63% of optimal, we observe from Table 2 that the evasion rate increases by 1.22% and the inspection rate decreases by 0.7% (equivalent to checking 2546 fewer passengers) with respect to the optimum. In other words, a non-optimal unpredictable patrolling schedule generates more evasion and a lower inspection rate. Using the joint
The gap observed in Figure 5 between the evasion rate induced by the fare inspection patrolling strategy and the unpredictable patrolling schedule is due to the feasibility (with respect to the optimum) of the unpredictable patrolling schedule resulting from solving the CG-MX Algorithm (with respect to MGLP).

As expected, evasion rate is decreasing with the number of fare inspection teams. We observed the smallest number of fare inspection teams inducing an evasion rate of less than or equal to 1%, which represents opportunistic passengers who do not pay the fine or who do not react to the fare inspection as a mechanism to inhibit evasion. Under the optimal patrolling strategy (Figure 5) the smallest number of inspection teams inducing an evasion rate less than or equal to 1% is achieved with 65 deployed fare inspection teams. Even if the unpredictable patrolling schedule generates an average evasion rate equal to 2.2%. This value represents the transit authority's loss of considering a near-optimal solution for MXLP.

In the following we discuss managerial insights considering the deployment of 65 inspection teams. The minimum, maximum, and average optimality gap of the unpredictable patrolling schedule associated with the deployment of 65 inspection teams are respectively 1.55%, 1.70%, and 1.63%. The inspection rate, defined as the ratio between checked passengers and all passengers (Barabino et al (2014)), is computed as:

$$IR(\%) = 100 \times \frac{\sum_{v \in V} \min \{d_v, \lfloor h_{\xi(v)} \kappa \rfloor X_{\xi(v)}\}}{\sum_{v \in V} d_v},$$

where $X_{\xi(v)}$ is the optimal variable of the MGLP model, and $X_{\xi(v)} = \sum_{s \in \hat{S}_r} \pi_s X_{\xi(v)|s}$ for CG-MX Algorithm. The average optimality gap, average evasion rate, average inspection rate, and average number of checked passengers (\#IP) induced by the fare inspection patrolling strategy and the unpredictable patrolling schedule, respectively, are defined in Table 2.

<table><caption>**Table 2** Optimality gap, evasion rate, inspection rate, and checked passengers when $n = 65$</caption><thead><tr><th></th><th>Gap (%)</th><th>ER(%)</th><th>IR(%)</th><th>\# IP</th></tr></thead><tbody><tr><td>Patrolling Strategy</td><td>0</td><td>0.98</td><td>9.1</td><td>35 494</td></tr><tr><td>Unpredictable Schedule</td><td>1.63</td><td>2.20</td><td>8.4</td><td>32 948</td></tr></tbody></table>

The joint strategy-schedule approach to address the operational implementation of a fare inspection patrolling strategy provides a mechanism for determining the quality of the unpredictable patrolling schedule that results from the CG-MX Algorithm. Thus, by considering an unpredictable patrolling schedule that is on average no more than 1.63% of optimal, we observe from Table 2 that the evasion rate increases by 1.22% and the inspection rate decreases by 0.7% (equivalent to checking 2546 fewer passengers) with respect to the optimum. In other words, a non-optimal unpredictable patrolling schedule generates more evasion and a lower inspection rate. Using the joint
strategy-schedule approach proposed in this paper it is possible to quantify the impact of considering a near-optimal unpredictable patrolling schedule on the evasion and inspection rates.

Theoretically, the systematic day-to-day application of the unpredictable patrolling schedule resulting from the CG-MX Algorithm should generate a steady-state average evasion rate equal to 2.2%. However, a steady-state solution is not operationally useful to the transit authority. Sure they are interested in knowing if a 2.2% evasion rate will be achieved in the medium term. We use Monte Carlo simulation to reproduce the transit authority's daily choice of a patrolling schedule $s \in \hat{S}_r$ with probability $\pi_s$ and compute the evasion rate as a function of time. Let $g_{s,\tau}$ be the frequency with which the patrolling schedule $s \in \hat{S}_r$ is selected after $\tau$ days. Thus, the evasion rate after $\tau$ days is:

$$ER_{\tau}(\%) = 100 \times \frac{\sum_{v \in V: U_{v,\tau}^{o} < B} \mathbb{E}(d_v^{o})}{\sum_{v \in V} d_v},$$

where $U_{v,\tau}^{o} = \min \{F_{(\hat{d}_{v,\tau}^{o}+1)^2} \sum_{i=0}^{n} \sum_{j=0}^{\hat{d}_{v,\tau}^{o}} f_{\xi(v)|i,j}^{o} \sum_{s \in S} g_{s,\tau} H_{\xi(v)|s}^{i}, B\}$ is the amount paid by an opportunistic passenger after $\tau$ days. Figure 6 shows the daily simulation of the unpredictable patrolling schedule over a 500-day horizon when 65 inspection teams are deployed.

<figure><img src="image_7.png" /><figcaption>Fig. 6 Unpredictable patrolling schedule simulation when $n = 65$</figcaption></figure>

The daily evasion rate decreases as the unpredictable patrolling schedule is systematically applied day after day. From Figure 6, we observe that after 120 days an average evasion rate of 2.2% is reached. Although for $n = 65$, the unpredictable patrolling schedule resulting from the CG-MX Algorithm is not optimal after 36 000 s, it generates a good-quality solution providing a set of patrolling schedules whose systematic day-to-day application induce an average evasion rate of 2.2% after 120 days.
strategy-schedule approach proposed in this paper it is possible to quantify the impact of considering a near-optimal unpredictable patrolling schedule on the evasion and inspection rates.

Theoretically, the systematic day-to-day application of the unpredictable patrolling schedule resulting from the CG-MX Algorithm should generate a steady-state average evasion rate equal to 2.2%. However, a steady-state solution is not operationally useful to the transit authority. Sure they are interested in knowing if a 2.2% evasion rate will be achieved in the medium term. We use Monte Carlo simulation to reproduce the transit authority's daily choice of a patrolling schedule $s \in \hat{S}_r$ with probability $\pi_s$ and compute the evasion rate as a function of time. Let $g_{s,\tau}$ be the frequency with which the patrolling schedule $s \in \hat{S}_r$ is selected after $\tau$ days. Thus, the evasion rate after $\tau$ days is:

$$ER_{\tau}(\%) = 100 \times \frac{\sum_{v \in V: U_{v,\tau}^{o} < B} \mathbb{E}(d_v^{o})}{\sum_{v \in V} d_v},$$

where $U_{v,\tau}^{o} = \min \left\{ F_{\left(\frac{d_v^{o}+1}{2}\right)^2} \sum_{i=0}^{n} \sum_{j=0}^{\hat{d}_v^{o}} f_{\xi(v)|i,j}^{o} \sum_{s \in S} g_{s,\tau} H_{\xi(v)|s}^{i}, B \right\}$ is the amount paid by an opportunistic passenger after $\tau$ days. Figure 6 shows the daily simulation of the unpredictable patrolling schedule over a 500-day horizon when 65 inspection teams are deployed.

<figure><img src="image_7.png" /><figcaption>Fig. 6 Unpredictable patrolling schedule simulation when $n = 65$</figcaption></figure>

The daily evasion rate decreases as the unpredictable patrolling schedule is systematically applied day after day. From Figure 6, we observe that after 120 days an average evasion rate of 2.2% is reached. Although for $n = 65$, the unpredictable patrolling schedule resulting from the CG-MX Algorithm is not optimal after 36 000 s, it generates a good-quality solution providing a set of patrolling schedules whose systematic day-to-day application induce an average evasion rate of 2.2% after 120 days.
The Monte Carlo simulation chooses a daily patrolling schedule based on the selection probability $\pi_s$ with $s \in \hat{S}_r$. We compute the empirical probability distribution function of the patrolling schedule selection, i.e., $\sum_{s \in \hat{S}_r} \pi_s$, resulting from the CG-MX Algorithm. In particular, the average number of useful patrolling schedules is $|\hat{S}_r| = 178$ for the test set.

<figure><img src="image_8.png" /><figcaption>Fig. 7 Probability distribution function of the patrolling schedule selection when $n = 65$</figcaption></figure>

From Figure 7, we observe that 20% of the useful patrolling schedules (38 patrolling schedules) accumulate 88% of the selection probability. Thus, we infer that few patrol schedules accumulate a high probability of selection. Consequently, these 20% of patrolling schedules are the ones that are implemented the most over time.

# 6 Conclusions

In this paper, we study the operational implementation of a fare inspection patrolling strategy in a POP$_S$ system using an unpredictable patrolling schedule when the transit authority is committed to an in-station selective inspection policy.

Using a Stackelberg game approach, we formulate the fare inspection patrolling strategy, which refers to temporal-spatial inspection probabilities on the transportation network stations, as a single-level LP solved directly using a standard optimization solver. Defining the inspection probabilities as a convex combination over the set of all fare inspection patrolling schedules, we obtain an equivalent LP which is solved using a column generation approach. The pricing problem generates patrolling schedules, and the master problem defines the probability with which these patrolling schedules should be selected. Thus, the resulting set of patrolling schedules, where each schedule has an associated probability of being selected, defines an unpredictable
The Monte Carlo simulation chooses a daily patrolling schedule based on the selection probability $\pi_s$ with $s \in \hat{S}_r$. We compute the empirical probability distribution function of the patrolling schedule selection, i.e., $\sum_{s \in \hat{S}_r} \pi_s$, resulting from the CG-MX Algorithm. In particular, the average number of useful patrolling schedules is $|\hat{S}_r| = 178$ for the test set.

<figure><img src="image_8.png" /><figcaption>Fig. 7 Probability distribution function of the patrolling schedule selection when $n = 65$</figcaption></figure>

From Figure 7, we observe that 20% of the useful patrolling schedules (38 patrolling schedules) accumulate 88% of the selection probability. Thus, we infer that few patrol schedules accumulate a high probability of selection. Consequently, these 20% of patrolling schedules are the ones that are implemented the most over time.

# 6 Conclusions

In this paper, we study the operational implementation of a fare inspection patrolling strategy in a POP$_S$ system using an unpredictable patrolling schedule when the transit authority is committed to an in-station selective inspection policy.

Using a Stackelberg game approach, we formulate the fare inspection patrolling strategy, which refers to temporal-spatial inspection probabilities on the transportation network stations, as a single-level LP solved directly using a standard optimization solver. Defining the inspection probabilities as a convex combination over the set of all fare inspection patrolling schedules, we obtain an equivalent LP which is solved using a column generation approach. The pricing problem generates patrolling schedules, and the master problem defines the probability with which these patrolling schedules should be selected. Thus, the resulting set of patrolling schedules, where each schedule has an associated probability of being selected, defines an unpredictable
patrolling schedule for the transit authority. Since the patrolling strategy and unpredictable patrolling schedule formulations are two equivalent optimization problems, we ensure that for each patrolling strategy there is a corresponding unpredictable patrolling schedule.

Although the column generation approach, which provides an unpredictable patrolling schedule for the transit authority, does not guarantee an optimal solution in large-scale temporal-spatial transportation network after 36 000 s, we observe that it can provide good-quality solutions. Indeed, the lowest number of inspection teams that induce an evasion rate less than or equal to 1% leads to the maximum optimality gap of 1.7% under the optimal fare inspection patrolling strategy. This good-quality solution provides a patrolling schedule set and their respective probabilities of being selected that define a feasible unpredictable patrolling schedule for the transit authority and that it induces in steady state an average evasion rate of 2.2%. We simulated the daily application of this unpredictable patrolling schedule using Monte Carlo simulation and observed that the evasion rate of 2.2% is achieved after 120 days. Thus, we conclude that the unpredictable patrolling schedule leads to a solution that can be implemented in the medium term.

We next suggest future research prospects. The first one is to address the
design of a fare inspection patrolling strategy and the unpredictable patrolling
schedule when the transit authority implements an in-station mass inspec-
tion policy. Thus, the inspection policy (mass or selective) performing best
in reducing evasion can be determined. The second is to relax the assump-
tion that passengers follow a fixed temporal-spatial path, i.e., to consider
that opportunistic passengers can evade fare payment by the most convenient
temporal-spatial path based on their knowledge of inspection probabilities
and travel times. This would lead to a new follower's problem in a temporal-
spatial transportation network and to a new optimization problem and solution
approach for the leader's problem.

Acknowledgments

Pablo Escalona is grateful for the support of the National Agency for Research and Development (ANID) Chile through grant FONDECYT 11200287.

Compliance with Ethical Standards

* Conflicts of interest. The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this manuscript.

* Research involving human participants and/or animals. This article does not contain any studies with human participants or animals performed by any of the authors.
patrolling schedule for the transit authority. Since the patrolling strategy and unpredictable patrolling schedule formulations are two equivalent optimization problems, we ensure that for each patrolling strategy there is a corresponding unpredictable patrolling schedule.

Although the column generation approach, which provides an unpredictable patrolling schedule for the transit authority, does not guarantee an optimal solution in large-scale temporal-spatial transportation network after 36 000 s, we observe that it can provide good-quality solutions. Indeed, the lowest number of inspection teams that induce an evasion rate less than or equal to 1% leads to the maximum optimality gap of 1.7% under the optimal fare inspection patrolling strategy. This good-quality solution provides a patrolling schedule set and their respective probabilities of being selected that define a feasible unpredictable patrolling schedule for the transit authority and that it induces in steady state an average evasion rate of 2.2%. We simulated the daily application of this unpredictable patrolling schedule using Monte Carlo simulation and observed that the evasion rate of 2.2% is achieved after 120 days. Thus, we conclude that the unpredictable patrolling schedule leads to a solution that can be implemented in the medium term.

We next suggest future research prospects. The first one is to address the
design of a fare inspection patrolling strategy and the unpredictable patrolling
schedule when the transit authority implements an in-station mass inspec-
tion policy. Thus, the inspection policy (mass or selective) performing best
in reducing evasion can be determined. The second is to relax the assump-
tion that passengers follow a fixed temporal-spatial path, i.e., to consider
that opportunistic passengers can evade fare payment by the most convenient
temporal-spatial path based on their knowledge of inspection probabilities
and travel times. This would lead to a new follower's problem in a temporal-
spatial transportation network and to a new optimization problem and solution
approach for the leader's problem.

Acknowledgments

Pablo Escalona is grateful for the support of the National Agency for Research and Development (ANID) Chile through grant FONDECYT 11200287.

Compliance with Ethical Standards

* Conflicts of interest. The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this manuscript.

* Research involving human participants and/or animals. This article does not contain any studies with human participants or animals performed by any of the authors.
References

Auer P, Cesa-Bianchi N, Freund Y, et al (2002) The nonstochastic multiarmed bandit problem. SIAM journal on computing 32(1):48-77

Barabino B, Salis S (2019) Moving towards a more accurate level of inspection against fare evasion in proof-of-payment transit systems. Networks and Spatial Economics 19(4):1319-1346

Barabino B, Salis S (2022) Segmenting fare-evaders by tandem clustering and logistic regression models. Public Transport pp 1-36

Barabino B, Salis S, Useli B (2014) Fare evasion in proof-of-payment transit systems: Deriving the optimum inspection level. Transportation Research Part B: Methodological 70:1-17

Barabino B, Lai C, Olivo A (2020) Fare evasion in public transport systems: A review of the literature. Public Transport 12(1):27-88

Brotcorne L, Escalona P, Fortz B, et al (2021) Fare inspection patrols scheduling in transit systems using a Stackelberg game approach. Transportation Research Part B: Methodological 154:1-20

Buneder C, Galilea P (2017) Temporal and spatial analysis of fare evasion in transantiago. Tech. rep.

Busco C, González F, Jaqueih Y, et al (2022) Understanding transantiago users' motivations for paying or evading payment of bus fares. Journal of Public Transportation 24:100,016

Currie G, Delbosc A (2017) An empirical model for the psychology of deliberate and unintentional fare evasion. Transport Policy 54:21-29

Dauby L, Kovacs Z (2007) Fare evasion in light rail systems. Transportation Research Circular (E-C112)

Delfau JB, Pertsekos D, Chouiten M (2018) Optimization of control agents shifts in public transportation: tackling fare evasion with machine-learning. In: 2018 IEEE 30th International Conference on Tools with Artificial Intelligence (ICTAI), IEEE, pp 409-413

Egu O, Bonnel P (2020) Can we estimate accurately fare evasion without a survey? results from a data comparison approach in lyon using fare collection data, fare inspection data and counting data. Public Transport 12(1):1-26

Freeman RB (1999) The economics of crime. Handbook of labor economics 3:3529-3571
References

Auer P, Cesa-Bianchi N, Freund Y, et al (2002) The nonstochastic multiarmed bandit problem. SIAM journal on computing 32(1):48-77

Barabino B, Salis S (2019) Moving towards a more accurate level of inspection against fare evasion in proof-of-payment transit systems. Networks and Spatial Economics 19(4):1319-1346

Barabino B, Salis S (2022) Segmenting fare-evaders by tandem clustering and logistic regression models. Public Transport pp 1-36

Barabino B, Salis S, Useli B (2014) Fare evasion in proof-of-payment transit systems: Deriving the optimum inspection level. Transportation Research Part B: Methodological 70:1-17

Barabino B, Lai C, Olivo A (2020) Fare evasion in public transport systems: A review of the literature. Public Transport 12(1):27-88

Brotcorne L, Escalona P, Fortz B, et al (2021) Fare inspection patrols scheduling in transit systems using a Stackelberg game approach. Transportation Research Part B: Methodological 154:1-20

Buneder C, Galilea P (2017) Temporal and spatial analysis of fare evasion in transantiago. Tech. rep.

Busco C, González F, Jaqueih Y, et al (2022) Understanding transantiago users' motivations for paying or evading payment of bus fares. Journal of Public Transportation 24:100,016

Currie G, Delbosc A (2017) An empirical model for the psychology of deliberate and unintentional fare evasion. Transport Policy 54:21-29

Dauby L, Kovacs Z (2007) Fare evasion in light rail systems. Transportation Research Circular (E-C112)

Delfau JB, Pertsekos D, Chouiten M (2018) Optimization of control agents shifts in public transportation: tackling fare evasion with machine-learning. In: 2018 IEEE 30th International Conference on Tools with Artificial Intelligence (ICTAI), IEEE, pp 409-413

Egu O, Bonnel P (2020) Can we estimate accurately fare evasion without a survey? results from a data comparison approach in lyon using fare collection data, fare inspection data and counting data. Public Transport 12(1):1-26

Freeman RB (1999) The economics of crime. Handbook of labor economics 3:3529-3571
Jiang AX, Yin Z, Johnson MP, et al (2012) Towards optimal patrol strategies for fare inspection in transit systems. In: 2012 AAAI Spring Symposium Series

Jiang AX, Yin Z, Zhang C, et al (2013) Game-theoretic randomization for security patrolling with dynamic execution uncertainty. In: AAMAS, pp 207–214

Krogvig LB (2014) Fare inspection optimization in train networks. Master's thesis, Institutt for matematiske fag

Lee J (2011) Uncovering San Francisco, California, muni's proof-of-payment patterns to help reduce fare evasion. Transportation Research Record 2216(1):75–84

Milioti C, Panoutsopoulos A, Kepaptsoglou K, et al (2020) Key drivers of fare evasion in a metro system: Evidence from Athens, Greece. Case Studies on Transport Policy 8(3):778–783

Sasaki Y (2014) Optimal choices of fare collection systems for public transportations: Barrier versus barrier-free. Transportation Research Part B: Methodological 60:107–114

Torres-Montoya M (2014) Tackling fare evasion in Transantiago: an integrated approach. Tech. rep.

Troncoso R, de Grange L (2017) Fare evasion in public transport: A time series approach. Transportation Research Part A: Policy and Practice 100:311–318

Winter H (2019) The economics of crime: an introduction to rational crime analysis. Routledge

Wolfram L, Pollan C, Hostetter K, et al (2022) Measuring and managing fare evasion. Tech. rep.

Yin Z, Jiang AX, Tambe M, et al (2012) Trusts: Scheduling randomized patrols for fare inspection in transit systems using game theory. AI magazine 33(4):59–59
Jiang AX, Yin Z, Johnson MP, et al (2012) Towards optimal patrol strategies for fare inspection in transit systems. In: 2012 AAAI Spring Symposium Series

Jiang AX, Yin Z, Zhang C, et al (2013) Game-theoretic randomization for security patrolling with dynamic execution uncertainty. In: AAMAS, pp 207–214

Krogvig LB (2014) Fare inspection optimization in train networks. Master's thesis, Institutt for matematiske fag

Lee J (2011) Uncovering San Francisco, California, muni's proof-of-payment patterns to help reduce fare evasion. Transportation Research Record 2216(1):75–84

Milioti C, Panoutsopoulos A, Kepaptsoglou K, et al (2020) Key drivers of fare evasion in a metro system: Evidence from Athens, Greece. Case Studies on Transport Policy 8(3):778–783

Sasaki Y (2014) Optimal choices of fare collection systems for public transportations: Barrier versus barrier-free. Transportation Research Part B: Methodological 60:107–114

Torres-Montoya M (2014) Tackling fare evasion in Transantiago: an integrated approach. Tech. rep.

Troncoso R, de Grange L (2017) Fare evasion in public transport: A time series approach. Transportation Research Part A: Policy and Practice 100:311–318

Winter H (2019) The economics of crime: an introduction to rational crime analysis. Routledge

Wolfram L, Pollan C, Hostetter K, et al (2022) Measuring and managing fare evasion. Tech. rep.

Yin Z, Jiang AX, Tambe M, et al (2012) Trusts: Scheduling randomized patrols for fare inspection in transit systems using game theory. AI magazine 33(4):59–59