L Brotcorne

P Escalona
email: pablo.escalona@usm.cl

B Fortz

M Labbé

Fare inspection patrols scheduling in transit systems using a Stackelberg game approach

Keywords: Fare Inspection Scheduling, Stackelberg Game, Proof-of-payment Transit Systems

This study analyzes the scheduling of unpredictable fare inspections in proof-of-payment transit systems, where the transit operator chooses a collection of patrol paths (one for each patrol) every day with some probability in order to avoid any regularity that could be exploited by opportunistic passengers. We use a Stackelberg game approach to represent the hierarchical decision-making process between the transit operator and opportunistic passengers, whose decision on whether to evade the fare depends on the inspection probabilities set by the transit operator. Unlike previous work, we use an exact formulation of the inspection probabilities that allows us to develop new heuristics for the fare inspection scheduling problem, and to assess their solution quality in terms of their optimality gap.

Introduction

The three main ticketing systems in public transportation systems are: proof-of-payment (POP) where passengers must purchase a ticket before boarding the transport vehicle; pay-on-entry (POE) which requires that the fare payment be made via driver or showing the proof-of-payment each time passengers get into the vehicle; and conductor (C) where the fare is paid via conductors on board. This classification is introduced by [START_REF] Barabino | Fare evasion in public transport systems: a review of the literature[END_REF] and is based on when and to whom the fare is paid. A POP system implies that passengers purchase tickets (or passes) in advance and are required to validate them before using the service, regardless of verification of payment of the fare. As defined by [START_REF] Barabino | Fare evasion in public transport systems: a review of the literature[END_REF], POP systems can be applied with barriers (POP B ) and without barriers (POP S ). In systems with barriers the transit operator installs entrance gates or turnstiles and establishes a clearly defined payment zone assuming that these physical barriers inhibit fare evasion. In contrast, barrier-free systems do not have physical barriers, thus allowing the rapid boarding of transport vehicles. Thus, the POP S system's inherent structure can lead to significant fare evasion by passengers, resulting in significant revenue losses for transit operators.

Several previous studies have investigated the evasion levels and loss of revenue in POP S systems. For instance, [START_REF] Dauby | Fare evasion in light rail systems[END_REF] studied 18 light rail systems in Europe and found that the measured fare evasion rates averaged 10.4%, while some systems had rates as high as 25%. [START_REF] Lee | Uncovering san francisco, california, muni's proof-of-payment patterns to help reduce fare evasion[END_REF] analyzed the San Francisco light rail system and showed that the minimum system-wide fare evasion rate was 9.5% and that the uncaptured revenue was 19 million dollars annually based on the fares in 2009. [START_REF] Troncoso | Fare evasion in public transport: A time series approach[END_REF] found that the evasion level in the Santiago (Chile) bus system was approximately 28% and the cost of evasion was estimated at 415 million dollars annually [START_REF] Buneder | Temporal and spatial analysis of fare evasion in transantiago[END_REF]). Similarly, [START_REF] Currie | An empirical model for the psychology of deliberate and unintentional fare evasion[END_REF] found that the annual losses in Melbourne (Australia) amounted to 35 million euros, which corresponded to 11.6% of the ridership.

In POP S systems, transit operators can employ a limited number of operational mechanisms to inhibit the evaders actions. These mechanisms are mainly based on daily fare inspection scheduling. Since the transit operator has a fixed number of inspectors in the short term and the number of passengers in the network depends on the time of day, an efficient fare inspection schedule must consider several specific requirements.

More precisely, inspections must be deployed throughout the day since POP S systems normally operate between 15 and 24 hours a day, the daily fare inspection schedule must respect the working hours of the inspectors, and inspections must be unpredictable from the users perspective of the transportation system since opportunistic passengers can exploit any regularity in the daily execution of inspections for their benefit.

An efficient method for scheduling unpredictable fare inspections in a transportation system is to generate randomized patrolling using the principles of Stackelberg's game theory. In this game, the transit operator (the leader) uses a fixed set of inspectors organized in patrols, which move through the transit system inspecting passengers, to inhibit opportunistic passengers (the followers) from evading the fare. More precisely, the transit operator associates a temporal-spatial path to each patrol based on the timetable (daily schedule) of the transit system, thereby defining a collection of patrol paths consisting of one path for each patrol (joint patrol paths), which under a Stackelberg game approach corresponds to a pure strategy for the leader. The transit operator could define the joint patrol paths that most contribute to its objective function (e.g., minimize the number of evaders or maximize revenue from ticket sales and fines collected) and implement it regularly. However, any regularity in patrol paths can be exploited by opportunistic passengers. To induce unpredictability, the transit operator defines a set of joint patrol paths, where each joint patrol path has an associated probability of being selected, thereby defining a mixed strategy under a Stackelberg game approach. In a real implementation, the probability of selecting a joint patrol path is interpreted as the frequency at which the transit operator implements that joint patrol path. Clearly, the transit operator wants to define the mixed strategy (i.e., the set of joint patrol paths and their corresponding probabilities of being selected) that contributes the most to its objective function. By establishing the set of joint patrol paths and their corresponding probabilities of being selected, the transit operator further sets the probabilities of inspecting passengers at different locations on the network and at different times of the day (inspection probabilities), which will influence the decision about whether to buy a ticket or not for the opportunistic passengers. Thus, it is important that the transit operator explicitly integrate the behavior of opportunistic passengers when defining its mixed strategy. This hierarchical relationship, where the behavior of opportunistic passengers is part of the restrictions of the transit operator, defines the leader's problem under a Stackelberg game. However, since the set of joint patrol paths grows exponentially with the size of the network and the duration of the daily schedule, the literature has been focused on explicitly determining the temporal-spatial inspection probabilities in the network without determining the set of joint patrol paths and their corresponding probabilities of being selected, thereby defining a marginal strategy under a Stackelberg game approach. This marginal-based approach is operationally useless for the transit operator unless a mixed strategy is returned from the marginal strategy, since what the transit operator requires is to choose every day a joint patrol path with a certain probability that contributes to its objective.

The marginal-based approach was first applied by [START_REF] Kiekintveld | Computing optimal randomized resource allocations for massive security games[END_REF] in the context of Stackelberg security games. They showed for common classes of Stackelberg security games with multiple resources that it is possible to find polynomial-size formulations for the leader's problem that only refer to marginal probabilities (marginal strategy) and that for each feasible marginal strategy there is a corresponding mixed strategy. Thus, under a marginal-based approach to define the Stackelberg game the challenge is to develop algorithms that return a mixed strategy from the marginal strategy. Unfortunately, there are examples where this approach fails, in the sense that the marginal strategy does not correspond to any mixed strategy [START_REF] Letchford | Solving security games on graphs via marginal probabilities[END_REF]). To the best of our knowledge, in the daily scheduling of unpredictable fare inspections no algorithm guarantees a mixed strategy that matches the marginal strategy resulting from a formulation of the leader's problem under a marginal-based approach. Furthermore, the algorithms that return a mixed strategy from a marginal strategy, in the context of daily scheduling of unpredictable fare inspections, are based on relaxations of the leader's problem that lack guarantee in terms of the optimality gap.

This paper addresses the fare inspection scheduling problem in POP S systems from a marginal and mixed approaches to define the Stackelberg game using an exact formulation for inspection probabilities. The leader's problem under a marginal-based approach, which only refers to the probabilities of inspection, is formulated as a single level non-linear problem (NLP) where the transit operator maximizes the revenue from ticket sales and fines collected and determines the inspection probabilities, while opportunistic passengers respond by optimizing their decision whether to buy a ticket or not, given the inspection probabilities.

We define a new heuristic for determining feasible marginal strategies based on a new relaxation of the leader's problem formulated as a linear problem (LP relaxation) which exploits the geometric structure of the nonlinear problem resulting from the exact formulation of the inspection probabilities. On the other hand, the leader's problem under a mixed-based approach, which refers to the set of joint patrol paths and their corresponding probabilities of being selected, is formulated using a column generation (CG) approach.

The master problem determines the joint patrol paths and their corresponding probabilities of being selected that maximize the transit operator's revenue and the pricing problem generating feasible joint patrol paths.

The master problem and the pricing problem are formulated as an LP and mixed integer non-linear problem (MINLP), respectively. We define a new heuristic for determining feasible mixed strategies based on a reformulation of the LP relaxation of the leader's problem under a marginal-based approach. Although the heuristics presented in this paper do not guarantee optimal marginal and mixed strategies respectively, our computational results have shown that they provide good quality solutions in terms of their optimality gap.

The main contributions of this study are summarized as follows: (i) To the best of our knowledge, it is the first time that an exact formulation for scheduling unpredictable fare inspections is presented; and

(ii) it is the first time that feasible solutions with a quality guarantee, in terms of the optimality gap, for scheduling unpredictable fare inspections are presented. In particular, we provide an exact formulation of the inspection probabilities; we define an exact formulation of the leader's problem under marginaland mixed-based approaches; we provide a new LP relaxation of the leader's problem under a marginalbased approach; we define new heuristics for returning feasible solutions to the leader's problem under each marginal-and mixed-based approaches, respectively; and we assess the quality of feasible solutions in terms of their optimality gap.

The remainder of this paper is structured as follows. In the next section, we review related works.

In Section 3, we define the leader's problem under marginal-and mixed-based approaches. In Section 4, we derive bounds for the leader's problem under a marginal-based approach and describe the heuristic for returning feasible solutions. In Section 5, we provide bounds for the leader's problem under a mixedbased approach and describe the heuristic for returning feasible solutions. In Section 6, a brief discussion of the marginal and mixed approaches to the leader's problem is presented. In Section 7, we present the computational results obtained from evaluations of our approaches. Finally, we present our conclusions and suggest future extensions to this research in Section 8.

Related work

A comprehensive review of fare evasion in public transport systems can be found in [START_REF] Barabino | Fare evasion in public transport systems: a review of the literature[END_REF], which classify the literature on fare evasion into five areas of interest: fare evader-oriented studies, criminology, economics, technological innovations, and operational research. For them, the fare inspection patrol scheduling problem is a sub-area of operations research that also includes security crew scheduling, resource allocation, allocation of inspectors on a transit network, and fare inspection strategies.

Most previous studies addressing the fare inspection scheduling problem formulate the model as a Leader-Follower Stackelberg game using a marginal-based approach. [START_REF] Jiang | Towards optimal patrol strategies for fare inspection in transit systems[END_REF] studied the random scheduling of patrols for fare inspection in a single line urban train under a marginal-based approach. They adopt a transition graph representing a space-time network where each pair of station and time point represents a node, whereas the inspection activity occurs at the edges. The marginal strategy, which only refers to marginal inspection probabilities, is represented as a flow in a transition graph subject to temporal constraints where the patrol length is limited by the working hours. Furthermore, passengers are assumed to follow a fixed path through the network. To inhibit fare evasion, the leader sets inspection probabilities for the network, to which opportunistic passengers respond by optimizing their decision about whether to buy a ticket or not, minimizing the expected cost of their trip. Using an upper bound on the inspection probabilities, they derived an LP relaxation of the leader's problem under the marginal-based approach, which can be solved using standard optimization solvers. Their experiments were conducted on several single lines of the Los Angeles Metro. The results were based on a single patrol where the fine was 66 times the ticket price. [START_REF] Jiang | Towards optimal patrol strategies for fare inspection in transit systems[END_REF] propose as future work to develop an algorithm to return a mixed strategy from the marginal strategy resulting from their LP relaxation. [START_REF] Yin | Trusts: Scheduling randomized patrols for fare inspection in transit systems[END_REF] considered the same model as [START_REF] Jiang | Towards optimal patrol strategies for fare inspection in transit systems[END_REF] but indirectly set the inspection probabilities by using the expected number of patrols in the transition graph edges. An extended transition graph was then used to include the temporal constraints on the patrols, i.e., the temporal constraints were embedded in the extended network. They derived an LP relaxation of the leader's problem under a marginalbased approach by using an upper bound on the inspection probabilities and defining an algorithm to return a mixed strategy that matches the relaxed marginal strategy resulting from their LP relaxation. However, there is no measure of the quality of their mixed strategy. Their experiments were conducted based on single lines of the Los Angeles Metro, and the results were obtained for a single patrol. [START_REF] Jiang | Game-theoretic randomization for security patrolling with dynamic execution uncertainty[END_REF] extended the approach of [START_REF] Yin | Trusts: Scheduling randomized patrols for fare inspection in transit systems[END_REF] by including uncertainty based on the Markov decision process. Uncertainty in the execution of fare inspections can result from delays, emergencies, or any event that affects the patrol's ability to carry out its fare inspection schedule. [START_REF] Jiang | Game-theoretic randomization for security patrolling with dynamic execution uncertainty[END_REF] derive an LP relaxation of the leader's problem under a marginal-based approach by using an upper bound on the inspection probabilities. They defined an algorithm based on a Monte Carlo simulation to return a robust mixed strategy without any measure of its quality in terms of the optimality gap. Delle [START_REF] Delle Fave | Security games in the field: deployments on a transit system[END_REF] proposed a multi-operation patrol scheduling system with a fare evasion module based on the formulation given by [START_REF] Jiang | Game-theoretic randomization for security patrolling with dynamic execution uncertainty[END_REF].

Unlike previous works, [START_REF] Krogvig | Fare inspection optimization in train networks[END_REF] addresses the fare inspection scheduling problem using a mixedbased approach to Stackelberg's game. Furthermore, he considers a train network where passengers can make transfers to arrive at their destination according to the transit system's daily schedule. Transfers generate a more complex spatial-time network than those studied in previous works. Other differences with previous works and that are related to the inherent structure of a train network, are that the inspection activity is performed exclusively on-board between stations and that it is not desirable to allocate multiple patrols to the same train or to have overlapping of patrols. Using a CG approach to the leader's problem under a mixed-based approach, [START_REF] Krogvig | Fare inspection optimization in train networks[END_REF] derives an LP relaxation for the pricing problem using an upper bound on the inspection probabilities. Their experiments were conducted based on the local train network around Oslo, Norway.

From the review conducted, we infer that without an exact formulation for inspection probabilities, none of the above works provides a quality measure for their solutions in terms of optimality gap. Furthermore, the development of new solution approaches of the fare inspection scheduling problem is limited without an exact formulation of inspection probabilities.

The lack of an exact formulation of inspection probabilities is also present in problems similar to scheduling unpredictable fare inspections, such as the allocation of inspectors on a transit network and the fare inspection strategies.

As in the case of the random scheduling of patrols, an efficient method of allocating inspectors in an unpredictable manner is to generate a random allocation of inspectors using the principles of game theory.

In this game, the transit operator (the leader) uses a set of inspectors who are allocated to spatial locations to inhibit evasion by transit users (the followers). The mixed strategy is defined by a set of allocations and their corresponding probabilities of being selected, while the marginal strategy only refers to inspection probabilities. It should be noted that in this problem, the inspectors do not move in the transit network, unlike what happens in the scheduling of randomized patrols for fare inspection. To the best of our knowledge, the randomized allocation inspector problem does not consider temporal constraints for inspectors. [START_REF] Borndörfer | A stackelberg game to optimize the distribution of controls in transportation networks[END_REF] studied the random allocation of inspectors to spatial locations of a transportation network in order to enforce the payment of a transit toll under marginal-and mixed-based approaches.

They adopt a directed graph as a spatial network type where inspection activity occurs on the edges. The marginal strategy is represented as a distribution of the network's inspection capacity, which defines the inspection probabilities. They study two cases for the leader's problem under a marginal-based approach.

In the first case, the leader maximizes the revenue generated by the toll, and in the second case, the leader minimizes the number of evaders. Based on an approximation of the inspection probabilities, they derive an LP relaxation for the first case and a mixed-integer linear problem relaxation (MIP relaxation) for the second case. On the other hand, the leader's problem under a mixed-based approach is formulated using a CG approach where the pricing problem, which generates inspector allocations in the network, uses an approximation of the inspection probabilities. [START_REF] Borndörfer | Optimizing toll enforcement in transportation networks: a game-theoretic approach[END_REF] extended the game-theoretic model presented by [START_REF] Borndörfer | A stackelberg game to optimize the distribution of controls in transportation networks[END_REF] to handle the case where every follower is free to choose its path in the network to reach its destination, reducing the follower's problem to the shortest path problem. Based on this simplification and an approximation of the inspection probabilities, the authors derive a MIP relaxation of the leader's problem under a marginal-based approach.

Two passengers reactions (passenger strategies) to the transit operator action are addressed in the subarea of fare inspection strategies [START_REF] Barabino | Fare evasion in public transport systems: a review of the literature[END_REF]). In the first one, namely non-adaptive strategy, passengers select a priori a route and continue along it during the trip. In the second one, namely adaptative strategy, passengers obtain information along the way and use it to update their routes. [START_REF] Correa | Fare evasion in transit networks[END_REF] studied new models for optimizing fare inspection strategies in public transportation systems under a marginal-based approach. Similar to [START_REF] Borndörfer | A stackelberg game to optimize the distribution of controls in transportation networks[END_REF], they adopt a directed graph as a spatial network where nodes are stations and edges represent trips between stations. The leader's problem under a marginal-based approach is formulated as a bilevel optimization problem. At the first level, the transit operator determines the probabilities of inspecting passengers at different locations. At the second level, opportunistic passengers respond by optimizing their routes given the inspection probabilities and travel times. They consider non-adaptive followers and a variant with adaptive followers, in which once a passenger is caught, he will continue his trip along the shortest path. [START_REF] Correa | Fare evasion in transit networks[END_REF] further considered two different settings for the leader's decision problem. A fixed-fare environment, where the ticket prices are fixed prior, and a flexible-fare setting, where the leader can determine ticket prices. Thus, they consider four cases for the leader's problem under a marginal-based approach. Using an upper bound for the inspection probabilities, they derive an LP relaxation and show that it is an upper bound for all four variants of the leader's problem. Furthermore, [START_REF] Correa | Fare evasion in transit networks[END_REF] derive exact (non-linear) formulations for two variants of the leader problem, adaptive followers with fixed-fare and non-adaptive followers with flexible-fare.

Model Formulation

In this section, we describe the transit system and formulate two optimization models for the fare inspection scheduling problem using a Stackelberg game approach. The first model relies on a marginal-based approach to define the Stackelberg game, whereas the second considers a mixed-based approach.

First, we model the transit system as a transition graph based on a daily schedule. We then define the followers and leader problems to determine an optimal marginal strategy. Finally, we provide a new formulation for determining an optimal mixed strategy. The notations used in this section are summarized in Appendix A.

Transit system

Let us consider a train system comprising a single line with a set S of stations (s = 1, ..., |S|), where the trains travel back and forth on a train line. The train line is a sequence of stations visited daily by a set R of trains (r = 1, ..., |R|) according to a daily schedule. A typical daily schedule comprises two timetables of type [t rs ] |R|×|S| , where t rs is the approximate arrival/departure time of train r in station s. The first timetable concerns trains that visit station s before station s + 1 and the second timetable is related to trains that visit station s before station s -1. The arrival/departure times between the beginning and end of the daily schedule are normalized by shifting the times so that the beginning of the daily schedule corresponds to time 0. Let τ rs be the normalized arrival/departure time of train r in station s.

A type k ∈ K of passenger is defined as a set of d k ≥ 0 passengers who follow the same sequence of stations (passenger path) according to the daily schedule. For example, passengers who start their path at station s at τ rs and end at station s ′ at τ rs ′ are of the same type. The attitude of passengers towards fare evasion can be classified in different ways [START_REF] González | Fare evasion in public transport: Grouping transantiago users' behavior[END_REF], [START_REF] Salis | Segmenting fare evader groups by factor and cluster analysis[END_REF], [START_REF] Delbosc | Four types of fare evasion: A qualitative study from melbourne, australia[END_REF], [START_REF] Hauber | Daily life and the law: Discrepancies in behavior[END_REF]). In this paper we assume that passengers may behave according to two profiles: honest passengers always pay the fees whereas opportunistic passengers make their decision about buying a ticket or not based solely on the expected cost of their trip which depends on the probability of being inspected. In particular, opportunistic passengers can either buy a ticket at price B or choose to travel without paying for the ticket but with the risk of incurring a fine F (F >> B) if they are caught. We assume that the number of type k passengers (d k , ∀k ∈ K) is known and that opportunistic passengers are uniformly distributed in the transit network. Clearly, the number of opportunistic passengers of type k is unknown. Let the discrete random variable d o k be the number of opportunistic passengers of type k. We consider that d o k follows a discrete uniform distribution between zero and

do k ≤ d k , i.e., d o k ∼ U {0, ..., do k }.
To prevent fare evasion, the line operator sets inspection probabilities in the transit network by considering a fixed set of n patrols. A patrol that follows a path can inspect the passengers on train (on-train inspection) or at the station when they depart (in-station inspection). Similar to [START_REF] Jiang | Towards optimal patrol strategies for fare inspection in transit systems[END_REF], we consider that the patrols are subject to temporal labor constraints. Let ∆ max be the length of the patrols' working day, e.g., eight hours per day (480 time units). Consequently, a patrol path cannot exceed ∆ max units of time in the transit system. On the other hand, since the number of passengers on the network depends on the time of day and patrols should not be allocated to any schedule, we consider J (j = 1, ..., |J|) time windows of ∆ max time units, where patrols can be allocated to perform their fare inspection duties. For example, if the daily schedule of the transit system lasts 24 hours, three time windows of 8 hours each can be defined, where the first time window starts at 00:00 and ends at 8:00, the second window starts at 8:00 and ends at 16:00 and the third window starts at 16:00 and ends at 24:00. Thus, a time window is defined as a fixed period of ∆ max time units where patrols can perform their inspection tasks without violating the temporal labor constraint. We consider that time windows can be partially overlapping. For example, if the following four time windows are defined: [8:00,16:00], [13:00,21:00], [18:00,2:00], and [00:00,8:00] respectively, it can be seen that the time windows are partially overlapping. Furthermore, we consider slack in the start and end of the time windows. For example, if a time window starts at 00:00 and ends at 8:00, we consider that a patrol can start its fare inspection tasks between 00:00 and 00:10 and end between 7:50 and 8:00. Let

∆ in j = τ in j -τ in j and ∆ out j = τ out j -τ out j
be the length of the slack for the beginning and end of the jth time window respectively, where τ • j and τ • j are the start and end time of the slack ∆ • j . Thus, given the temporal constraint, τ out j -τ in j = ∆ max for any j ∈ J. Let τ in js and τ out js be the times during the jth time windows when a patrol at the station s can begin and end the inspection, respectively, where τ • js = min{τ rs :

τ rs ∈ [τ • j , τ • j ]} or τ • js = τ • j + 0.5△ • j otherwise.
We assume that passengers take a fixed path at a fixed time and remain at the destination station for a minimum time △ min where they can be inspected in-station by one or more patrols. This minimum time of stay at the destination station represents the "exit" action of the passengers.

The trains, types of passenger, and patrol paths are represented in a transition graph G = (V, E) based on the train line's daily schedule, where V and E are the sets of vertices and edges, respectively. A vertex v ∈ V is defined as a station and time pair, i.e.,

V ⊃ v = (s, τ ) : s ∈ S, τ ∈ {τ rs } r∈R ∪ τ ∈ {τ rs + △ min } r∈R ∪ {τ in js } j∈J ∪{τ out js } j∈J . An edge e ∈ E is denoted as e = (v, v ′ ), where v = (s, τ ) and v ′ = (s ′ , τ ′ ).
A train edge e ∈ E is an edge from (s, τ ) to (s ′ , τ ′ ) where s ′ is either the predecessor or successor of s in the station sequence, and v = (s, τ ) and v ′ = (s ′ , τ ′ ) are two consecutive stops. An in-station edge e ∈ E is an edge from (s, τ ) to (s, τ ′ ), where τ < τ ′ and no vertex (s, τ ′′ ) exists such that τ < τ ′′ < τ ′ . To G, we add an artificial vertex v + with artificial edges to all possible vertices where a patrol can begin the inspection and a sink vertex v - with artificial edges from all possible vertices where a patrol can end the inspection. Figure 1 illustrates the path of two patrols (red and blue) on G with six stations, two time windows (j = 1, 2), seven trains in the s → s + 1 direction, and six trains in the s → s -1 direction.

In Figure 1, the red and blue patrols perform their control tasks during time window j = 1 and j = 2, respectively. Both patrols begin and end their workdays within the time slots defined for each time window. Furthermore, both patrols follow a sequence of edges that includes train edges where they make on-train inspections and in-station edges where they make in-station inspections. On the other hand, passengers of type k follow a specific sequence of train edges, where they can be inspected on-train, and finish their trip following in-station edges at the destination station, where they can be inspected in-station. More precisely, if passengers of type k finish their train edge sequence at station s in time τ rs , then the set of in-station edges that define the exit action of these passengers are those contained between (s, τ rs ) and (s, τ rs + △ min ).

It should be noted that G can be used to represent more complex systems, such as a train network, a bus system, a network bus system, or more generally, an intermodal transit system. For this, it is necessary that a daily schedule provide information on each bus or train arrival/departure time at each station in the system. In G there will be more stations and transport vehicles. Consequently, the number of vertex v = (s, τ ) ∈ V and edges e = (v, v ′ ) ∈ E is larger. The sequence of edges followed by a passenger of type k, from its origin vertex v = (s, τ ) to its destination (station s ′ ) is obtained using the shortest path algorithm, thus obtaining the destination vertex v ′ = (s ′ , τ ′ ). Since this computation must be done for every v = (s, τ ) ∈ V , the passenger types also increase in more complex transportation systems. However, it is still possible to obtain all origin-destinations by complete enumeration. We estimate that for a transit system with 6 transit lines, 77 stations, 8 combination stations and 1734 trains, operating 23 hours daily, there are approximately 480000 types of passengers, which can be computed in 40 hours.

s = 1 s = 2 s = 3 s = 4 s = 5 s = 6 s = s = s = s = s = s = v + v - △ in 1 △ in 2 △ out 1 △ out 2 τ out 1 -τ in 1 = △max τ out 2 -τ in 2 = △max

The followers minimization problem

Opportunistic passengers are assumed to be rational, meaning they decide to buy a ticket or not according to their cost. In particular, we assume that opportunistic passengers make their decision in order to minimize their expected cost.

Let W o k be equal to 1 if the opportunistic passenger of type k purchases a ticket and 0 if they wish to evade. In addition, let the random variable µ o k be the fee paid by the opportunistic passenger of type k. Thus,

µ o k = BW o k + F (1 -W o k )1 o k ,
where 1 o k is an indicator variable that is equal to 1 if an opportunistic passenger of type k is inspected during their trip; otherwise, the indicator variable is equal to 0. Let U o k be the expected value of the amount paid by an opportunistic passenger of type k, i.e.,

U o k = E(µ o k ) = B W o k + F P o k (1 -W o k )
, where P o k is the steady-state probability that an opportunistic passenger of type k is inspected during their trip. We assume a stationary state where the opportunistic passengers of type k have learned the values of the probability P o k . Consequently, the optimization problem for an opportunistic passenger of type k that involves minimizing the expected value they pay is defined as follows:

min W {BW o k + F P o k (1 -W o k ) : W o k ∈ {0, 1}} .
It should be noted that that the opportunistic passenger's decision is related to the threshold value c = B/F [START_REF] Barabino | Moving towards a more accurate level of inspection against fare evasion in proof-of-payment transit systems[END_REF], [START_REF] Barabino | Fare evasion in proof-of-payment transit systems: Deriving the optimum inspection level[END_REF], [START_REF] Boyd | Fare evasion and non-compliance: A simple model[END_REF]). Indeed, if P o k > B/F , then the opportunistic passenger of type k decides to buy a ticket (W o k = 1). By contrast if P o k < B/F , then they do not buy a ticket (W o k = 0). If we assume that this is the behavior of opportunistic passengers, then the line operator aims to define P o k , ∀k ∈ K, to discourage as many passengers as possible from fare evasion. The definition of the Stackelberg game between the line operator and opportunistic passengers differs between the marginal-and mixed-based approaches. The mixed approach defines the steady-state inspection probabilities for each type of opportunistic passenger through a set of joint patrol paths and their probabilities of being selected. By contrast, the marginal approach only refers to the steady-state inspection probabilities that contribute most to the line operator objective without determining the set of joint patrol paths and their probabilities of being selected.

Leader's problem under a marginal-based approach

Under a marginal-based approach, the leader's problem involves defining the steady-state inspection probabilities for each type of opportunistic passenger (P o k , ∀k ∈ K), assuming that the opportunistic passengers respond optimally to the leader's decision.

Let χ e be a discrete random variable that defines the number of patrols that inspect edge e ∈ E. Let H i e be the steady-state probability that i patrols inspect edge e, i.e., H i e = P(χ e = i) where i = 0, ..., n. Let X e be the steady-state expected number of patrols in edge e, i.e., X e = E(χ e ). Consequently, we have:

n i=0 H i e = 1 ∀e ∈ E, ( 1
)
H i e ≥ 0 ∀e ∈ E, i = 0, ..., n, (2)
X e = n i=0 iH i e ∀e ∈ E, (3)
where (1) ensures with a probability equal to 1 that edge e is inspected by no more than n patrols, i.e.,

P(χ e ≤ n) = 1,
f o k,e|i = 1 do k + 1 do k j=0 P ω o k,e = 0|χ e = i, d o k = j . ( 4)
.

Following the law of total probability, the steady-state probability of not inspecting an opportunistic passenger of type k on edge e ∈ E is defined as follow:

Po k,e = n i=0 f o k,e|i H i e ∀k ∈ K, e ∈ E k , ( 5
)
Po k,e ∈ [0, 1] ∀k ∈ K, e ∈ E k , ( 6
)
and the steady-state probability that an opportunistic passenger of type k is inspected is defined as follow:

P o k = 1 - e∈E k Po k,e ∀k ∈ K, ( 7
)
P o k ≥ 0 ∀k ∈ K, ( 8
)
where an opportunistic passenger of type k is not inspected if they are not controlled on any edge in their path.

As mentioned previously, a patrol path is subject to temporal constraints. However, the decision variables X e do not allow us to distinguish the patrols. Thus, we extend the graph to include explicit temporal constraints. The extended graph is denoted as G =(ν, ε) and defined as follows. We consider the previously described graph G, for which |J| time windows limit the maximum time that a patrol can remain on the network, i.e., τ out j -τ in j = △ max for any j ∈ J. Next, we partition graph G into |J| subgraphs such that subgraph j contains all vertices and edges in the interval [τ in j , τ out j ], including all edges in the set

{(v + , u) ∈ E : T (u) ∈ [τ in j , τ in j ]} ∪ {(u, v -) ∈ E : T (u) ∈ [τ out j , τ out j ]}.
Using a multi-commodity flow approach, the temporary constraints employed to ensure that the patrol duration on the path cannot exceed △ max units of time are defined by the following set of constraints:

e∈ δ+ (v) Y e - e∈ δ-(v) Y e = 0 ∀v ∈ ν, v ̸ = v + , v - (9) e∈ δ+ (v + ) Y e = n ( 10
) e∈ δ-(v -) Y e = n (11) 0 ≤ Y e ≤ n ∀e ∈ ε, ( 12
)
where Y e is the steady-state expected number of patrols on edge e ∈ ε; δ+ (v) is the set of edges that leave vertex v ∈ ν; and δ-(v) is the set of edges that enter vertex v ∈ ν. Constraints ( 9), (10), and (11) are flow conservation constraints in G. Figure 2 illustrates the expected flow of patrols at the extended graph of Figure 1.

In Figure 2, the expected number of patrols controlling time window j = 1 (red flow) and j = 2 (blue flow) are five and two respectively. Furthermore, the expected number of patrols controlling j = 1 and j = 2 satisfy constraints ( 9), (10), and ( 11).

The equivalence between extended and non-extended graphs in terms of edges results from the indexed

set E e = {e ′ = (u ′ , v ′ ) ∈ ε : T (u ′ ) = T (u), S(u ′ ) = S(u), T (v ′ ) = T (v), S(v ′ ) = S(v)} for all e = (u, v) ∈ E,
where S(v) = s. Consequently,

X e = e ′ ∈Ee Y e ′ ∀e ∈ E, ( 13
)
X e ≥ 0 ∀e ∈ E. ( 14
)
In this paper, we consider that the objective function of the line operator involves maximizing the expected revenue from ticket sales and fines collected defined as k∈K B(d k -0.5 do k ) + 0.5 do k U o k , where the first and second terms concern the expected income obtained from opportunistic and non-opportunistic passengers, respectively. Thus, the leader's problem under a marginal-based approach is defined as the following NLP:

MGP : max U,X,Y,H,P k∈K 0.5 do k U o k (15) s.t: U o k ≤ B ∀k ∈ K (16) U o k ≤ F P o k ∀k ∈ K (17)
(1), ( 2), (3), ( 5), ( 6), ( 7), ( 8), ( 9), ( 10), ( 11), ( 12), ( 13), ( 14), where the expected revenue of non-opportunistic passengers, which is a constant, is omitted from the objective function. Constraints ( 16) and ( 17) represent the optimal reaction of the followers to the leader's decision because

s = 1 s = 2 s = 3 s = 4 s = 5 s = 6 s = 1 s = 2 s = 3 s = 4 s = 5 s = 6 v + v - 5 1.5 3.5 1.5 1 2.5 0.5 2 2.5 2 1.5 2 0.5 △ in 1 △ out 1 △ in 2 △ out 2 τ out 1 -τ in 1 = ∆max τ out 2 -τ in 2 = ∆max
U o k = min W {BW o k + F P o k (1 -W o k ) : W o k ∈ {0, 1}} = min{B, F P o k } for any k ∈ K.
The leader's problem under a marginal-based approach is difficult to solve since constraint ( 7) is neither convex nor concave.

It should be noted that the line operator has no incentive to encourage evasion; on the contrary, the real objective of the line operator is to inhibit the action of as many opportunistic passengers as possible by making efficient and effective use of its resources.

Leader's problem under a mixed-based approach

A pure strategy for the line operator is a collection of patrol paths (one for each patrol), which specifies the sequence of edges that each patrol follows. Let P be the set of all pure strategies for the line operator.

Under a mixed-based approach, the leader's problem involves determining the set of pure strategies and their respective probabilities of being selected that most contribute to its objective function. Let π p ∈ [0, 1] be the probability of selecting the pure strategy p ∈ P , which can be interpreted as the frequency at which the line operator implements that joint patrol path.

Assuming the set of all pure strategies is known by the line operator, the steady-state probability of not inspecting an opportunistic passenger of type k on the edge e ∈ E and the steady-state probability of an opportunistic passenger of type k being inspected can be expressed as a convex combination of pure strategies, i.e., Po k,e = p∈P π p Po k,e|p and P o k = p∈P π p P o k|p with p∈P π p = 1, where Po k,e|p is the probability of not inspecting a passenger of type k on edge e given the joint patrol path p and P o k|p is the probability that an opportunistic passenger of type k is inspected given the joint patrol path p.

Let X e|p be the number of patrols that inspect edge e ∈ E given the joint patrol path p. Given the joint patrol paths p, the number of patrols inspecting the edge e is known for any e ∈ E. Consequently,

Po

k,e|p = f o k,e|X e|p for any k ∈ K and e ∈ E k ; and

P o k|p = 1 - e∈E k f o k,e|X e|p ∀k ∈ K. ( 18
)
Thus, the leader's problem under a mixed-based approach is defined as follows:

MXP : max U,π k∈K 0.5 do k U o k (19) s.t: U o k ≤ B ∀k ∈ K (16) U o k ≤ F p∈P π p P o k|p ∀k ∈ K (20) p∈P π p = 1 (21) π p ≥ 0 ∀p ∈ P. ( 22
)
Clearly, for a realistic public transport network, it is impossible to know every pure strategy of the line operator since the set of pure strategies P grows exponentially with the size of G, so a CG approach must be applied to solve MXP.

The CG process is defined such that an arbitrarily given subset of joint patrol paths P r (⊂ P) is considered first and further joint patrol paths are then added as needed. The CG solution procedure starts with the construction of a restricted master problem denoted as RMP(MX) by replacing P in MXP with P r . Let Z * RM P (M X) be the optimal objective function of RMP(MX), and β * k ≥ 0 and θ * are the values of the dual variables corresponding to constraints ( 20) and ( 21), respectively. Then, Z * RM P (M X) is an optimal value to MXP if all of the reduced costs are non-positive, i.e., F k∈K β * k P o k|p -θ * ≤ 0. To generate further joint patrol paths or verify the optimality of the current solution Z * RM P (M X) , we need to solve the following pricing problem:

SP(M X) : max X,Y,H,P cp = F k∈K β * k P k|p -θ * (23) s.t: e∈ δ+ (v) Y e|p - e∈ δ-(v) Y e|p = 0 ∀v ∈ ν, v ̸ = v + , v - (24) e∈ δ+ (v + ) Y e|p = n (25) e∈ δ-(v -) Y e|p = n (26) X e|p = e ′ ∈Ee Y e ′ |p ∀e ∈ E (27) X e|p = n i=0 iH i e|p ∀e ∈ E (28) n i=0 H i e|p = 1 ∀e ∈ E (29) P o k|p = 1 - e∈E k n i=0 f o k,e|i H i e|p ∀k ∈ K (30) X e|p ∈ {0, ..., n} ∀e ∈ E (31) Y e|p ∈ {0, ..., n} ∀e ∈ ε (32) H i e|p ∈ {0, 1} ∀e ∈ E, i = 0, ..., n (33)
P o k|p ∈ [0, 1] ∀k ∈ K, ( 34
)
where H i e|p is equal to 1 if edge e is inspected by i patrols on the joint patrol path p, but 0 otherwise; and Y e|p is the number patrols that inspect edge e ∈ ε on the joint patrol path p. It should be noted that

P o k|p = 1 -e∈E k Po k,e|p and Po k,e|p = n i=0
f o k,e|i H i e|p , thereby deriving constraint (30). If the optimal objective value of SP(MX) is positive, then the joint patrol path with the maximum reduced cost cp is added to RMP(MX) as a new entering joint patrol path, and the updated RMP(MX) is solved to optimality again. If this is not the case, then Z * RM P (M X) is an optimal value to MXP, i.e., Z * RM P (M X) = Z * M XP , where Z * M XP is the optimal objective function of MXP model.

Problem SP(MX) is a MINLP where constraint (30) is nonlinear. Although SP(MX) can be reformulated as a MINLP with convex objective function and linear constraints, using the change of variables introduced by [START_REF] Kocis | Global optimization of nonconvex mixed-integer nonlinear programming (minlp) problems in process synthesis[END_REF], the SP(MX) problem will still be a difficult MINLP to solve.

Bounds for the leader's problem under a marginal-based approach

The constraint (7) in MGP is neither convex nor concave, and thus the approaches developed in previous studies focused mainly on obtaining bounds for the leader's problem under a marginal-based approach. To the best of our knowledge, only relaxations have been used to obtain a bound for the leader's problem under a marginal-based approach, and no previous studies returned a feasible marginal strategy.

This section defines an LP relaxation for the leader's problem under a marginal-based approach that exploits the geometric structure of the nonlinear constraint ( 7). Furthermore, based on the solution of the LP relaxation, we define a heuristic for computing a feasible solution to the MGP model.

Upper bound for MGP based on geometric structure

By replacing (7) in the constraint ( 17), we obtain:

e∈E k Po k,e ≤ F -U o k F ∀k ∈ K. ( 35
)
Constraint ( 35) is neither convex nor concave, and the set of all Po k,e with e ∈ E k and U o k that satisfy (6), ( 16) and ( 35), which is denoted as C k , is a non-convex set. However, the complement of the set C k , i.e., the set of all Po k,e with e ∈ E k and U o k that satisfy (6), ( 16), and

e∈E k Po k,e ≥ F -U o k F
, is a convex set, which defines a particular geometry for the C k set.

The geometry of the set C k is based on the unitary hypercube defined by Po k,e ∈ [0, 1] for all e ∈ E k . The dimension of the hypercube is n k , where n k is the cardinality of E k , i.e., n k = |E k |. Constraint (35) cuts the hypercube that defines the vertices a i with i = 1, ..., n k , where a i is a vector with all components equal to 1, except the ith component is equal to

F -U o k F
. The portion of the hypercube cut by the constraint ( 35) is small because the maximum value of U o k is equal to the ticket price, i.e., max(U o k ) = B, ∀k ∈ K. Thus,

F -U o k F is close to 1 since F >> B.
To illustrate the geometry of the set C k , we consider a small example with E k = {e ′ , e ′′ } (n k = 2), as shown in Figure 3. The left-hand side of Figure 3 shows the set of all Po k,e ′ , Po k,e ′′ , and U o k that satisfy ( 6), ( 16), and ( 35), and the right-hand side shows the set of all Po k,e ′ and Po

k,e ′′ that satisfy ( 6) and ( 35) for some U o k ∈ (0, B). We generate the convex hull of the set C k by using the hyperplane defined by the vertices a 1 , ..., a n k . Thus, the hyperplane is defined as and constraint (35) can be replaced by the linear constraint:

e∈E k Po k,e = F -U o k F + n k -1,
e∈E k Po k,e -n k + 1 - F -U o k F ≤ 0 ∀k ∈ K, ( 36
) U o k Po k,e ′ Po k,e ′′ B 1 1 1 1 F -U o k F , 1 1, F -U o k F Po k,e ′ Po k,e ′′ 1 Figure 3: Illustrative example of set C k with E k = {e ′ , e ′′ }
thereby providing an upper bound for MGP. The left-hand side of Figure 4 show the convex hull for Figure 3 and the right-hand side shows the set of all Po k,e ′ and Po k,e ′′ , that satisfy ( 6) and ( 36) for some U o k ∈ (0, B). 2), ( 3), ( 5), ( 6), ( 9), ( 10), ( 11), ( 12), ( 13), ( 14), ( 16), ( 36).

U o k Po k,e ′ Po k,e ′′ B 1 1 1 1 F -U o k F , 1 1, F -U o k F Po k,e ′ Po k,e ′′
Problem RMGP is a relaxation of MGP because the objective functions are equal and the feasible region of MGP is included in that of RMGP. Thus, the optimal objective function of RMGP is an upper bound of the optimal objective function of MGP, i.e., Z * M GP ≤ Z * RM GP , where Z * RM GP is the optimal objective function of RMGP model.

Lower bound for MGP

Next, we define a heuristic to compute a lower bound on the objective value of the MGP model. Using the optimal variables for RMGP, we compute a feasible solution to MGP based on the violation of (35).

For each opportunistic passenger of type k that violates constraint (35), we compute the expected value that they pay according to:

U o k = F 1 - e∈E k Po k,e , ( 37
)
where Po k,e is the optimal variable for the RMGP model. This heuristic also has a geometric interpretation, which is illustrated using the example shown in Figure 3. Suppose that P * k,e ′ , P * k,e ′′ , and U * k define an optimal solution of the RMGP model that violates (35), as indicated in Figure 5a. To make the solution feasible for the MGP model, we determine what a passenger of type k pays according to (37), which is equivalent to displacing (35), as indicated in Figure 5b. In addition, for each passenger of type k who does not violate (35), we keep what they pay, i.e., the optimal variable U o k obtained by solving the RMGP model. We then compute the expected revenue of the line operator obtained from all passengers, which is defined by Ẑ. This heuristic is summarized in Algorithm 1, where Ẑ(k) is the accumulated expected revenue of the line operator up to the kth type of passenger.

1 1 P * k,e ′ P * k,e ′′ F -U * k F , 1 1, F -U * k F Po k,e ′ Po k,e ′′ (a) ( P * k,e ′ , P * k,e ′′ ) infeasible in MGP 1 1 P * k,e ′ P * k,e ′′ F -Û o k F , 1 1, F -Û o k F Po k,e ′

Algorithm 1 Feasible solution for MGP model

1: U o k , Po k,e ∀k ∈ K, e ∈ E k ← solve RMGP 2: k = 0 3: Ẑ(0) = 0 4: while k ≤ |K| do 5: if e∈E k Po k,e > F -U o k F then 6: U o k = F 1 -e∈E k Po k,e 7: Ẑ(k) = Ẑ(k-1) + 0.5 do k Û o k 8: else 9: Ẑ(k) = Ẑ(k-1) + 0.5 do k U o k 10:
end if

11: k = k + 1
12: end while 13: Return Ẑ = Ẑ(|K|)

New approach for determining bounds for the leader's problem under a mixed approach

The leader's problem is difficult to solve under a mixed-based approach since SP(MX) is a MINLP, so we present a new approach for determining bounds for MXP. The definition of the upper bound is based on the optimal solution of the LP relaxations RMGP, whereas the lower bound is based on the definition of a subset of joint patrol paths. In fact, it is easy to show that Z * RM P (M X) (P ′ ) ≤ Z * M XP , where Z * RM P (M X) (P ′ ) is the optimal objective function for RMP(MX) using P r = P ′ (⊂ P). Therefore, the quality of the lower bound depends on the definition of the set of joint patrol paths P ′ . In this study, we consider the set of joint patrol paths resulting from the mixed reformulation of RMGP, where the decision variables are reformulated as a convex combination of pure strategies.

Upper bound for MXP

Let us consider the convex combination of pure strategies

H i e = p∈P π p H i e|p ; X e = p∈P π p X e|p ; Y e = p∈P π p Y e|p ;

and Po

k,e = p∈P π p Po k,e|p , with p∈P π p = 1. By implementing the change of variables in problem RMGP, the resulting optimization problem can be reformulated as the following LP: 20

RMXP : max U,π k∈K 0.5 do k U o k (19) s.t: U o k ≤ B ∀k ∈ K (16) U o k ≤ F n k -F e∈E k p∈P π p Po k,e|p ∀k ∈ K (38) p∈P π p = 1 (21) π p ≥ 0 ∀p ∈ P, ( 22
)
where each pure strategy satisfies constraints ( 24), ( 25), ( 26), ( 27), ( 28), ( 29), and

Po k,e|p = n i=0 f o k,e|i H i e|p .
Similar to the leader's problem under a mixed-based approach, we define a CG-based scheme to solve RMXP, where we started by constructing a restricted master problem denoted as RMP(1) by replacing P in RMXP with P r (⊂ P). Let Z * RM P (1) be the optimal objective function of RMP(1), and β * k ≥ 0 and θ * are the values of the dual variables corresponding to constraints ( 38) and ( 21) respectively. Then, Z * RM P (1) is an optimal value to RMXP if all of the reduced costs are non-positive, i.e., cp = -(θ * + F k∈K e∈E k β * k Pk,e|p ) ≤ 0. The pricing problem is defined as the following MILP:

SP(1) : max X,Y,H,P cp = -θ * -F k∈K e∈E k β * k Pk,e|p (39)
s.t: (24), ( 25), ( 26), ( 27), ( 28), ( 29), ( 31), ( 32), (33),

Po k,e|p = n i=0 f o k,e|i H i e|p ∀k ∈ K, e ∈ E k , ( 40
) Po k,e|p ∈ [0, 1] ∀k ∈ K, e ∈ E k . ( 41
)
If the optimal objective value of SP(1) is positive, then the joint patrol path with the maximum reduced cost cp is added to RMP(1) as a new entering joint patrol path, and the updated RMP(1) is solved to optimality again. If this is not the case, then Z * RM P (1) is an optimal value to RMXP, i.e., Z * RM XP = Z * RM P (1) , where Z * RM XP is the optimal objective function of RMXP model. Since RMXP is a reformulation of RMGP, we conclude that

Z * RM GP = Z * RM XP = Z * RM P (1) . Fur- thermore, it is easy to show that RMXP is a relaxation of MXP because U o k ≤ F p∈P π p P o k|p ≤ F n k - F e∈E k p∈P π p Po k,e|p .
Therefore, the optimal value of RMXP, which is equal to the optimal value of RMGP, is an upper bound to MXP, i.e., Z * M XP ≤ Z * RM XP = Z * RM GP .

Lower bound for MXP

Let P 1 (⊂ P) be the set of joint patrol paths resulting from RMXP. The probability that an opportunistic passenger of type k is inspected on the joint patrol path p ∈ P 1 is given by ( 18) where X e|p is the optimal variable of RMXP. Thus, each joint patrol path p ∈ P 1 satisfies ( 24)-(34), and by using P r = P 1 in RMP(MX), we obtain a lower bound for MXP, i.e., Z * RM P (M X) (P 1 ) ≤ Z * M XP , where Z * RM P (M X) (P 1 ) is the optimal objective function for RMP(MX) using P r = P 1 .

It should be noted that by solving RMP(MX) using P r = P 1 , a feasible mixed strategy is obtained, i.e., a set of joint patrol paths with a positive probability of being selected. Let P 1 (⊂ P 1 ) be the set of joint patrol paths with a positive probability of being selected, i.e., P 1 = {p ∈ P 1 : π p > 0}. We also denote P 1 as the set of useful joint patrol paths. Thus, the feasible mixed strategy is defined by the set of joint patrol paths P 1 and their corresponding probabilities of being selected π p with p ∈ P 1 . The heuristic used to obtain Z * RM P (M X) (P 1 ) and the feasible mixed strategy is described in Algorithm 2.

Algorithm 2 Feasible solution for MXP model.

1: P 1 ← CG procedure: RMP(1) -SP(1)

2: P o k|p ← solve (18) ∀k ∈ K, p ∈ P 1 3: Z * RM P (M X) (P 1 ), P 1 , {π p } p∈ P1 ← solve RMP(MX) using P r = P 1 4: Return Z * RM P (M X) (P 1 ), P 1 , {π p } p∈ P1
The heuristic described in Algorithm 2 yields a feasible mixed solution characterized by a feasible mixed strategy, i.e., P 1 and {π p } p∈ P1 , and a line operator income Z * RM P (M X) (P 1 ).

6.

A brief discussion of the marginal and mixed strategy in scheduling unpredictable fare inspections.

The MGP and MXP models are exact formulations for scheduling unpredictable fare inspections from a marginal and mixed approach, respectively. The MGP model, which only refers to inspection probabilities, makes sense for the transit operator if a mixed strategy (i.e., a set of joint patrol paths and their respective probabilities of being selected) is returned from the marginal strategy resulting from MGP, since what the transit operator requires is choosing a joint patrol every day with a certain probability that contributes to its objective. Supposing MGP and MXP are two equivalent optimization problems (in the sense that from the solution of one, the solution of the other is readily found, and vice versa [START_REF] Boyd | Convex optimization[END_REF])), it could assure that for each marginal strategy resulting from MGP there is a corresponding mixed strategy resulting from MXP.

Some general mechanisms for checking the equivalence of optimization problems can be found in [START_REF] Boyd | Convex optimization[END_REF]. However, since MGP is a non-linear optimization problem, these mechanisms fail. For example, a reformulation of MGP using the convex combination of pure strategies does not yield a problem equivalent to MXP because (7) in MGP is neither convex nor concave. Therefore, it cannot be assure that there is a corresponding mixed strategy for every marginal strategy resulting from MGP.

It should be noted that RMGP and RMXP models are equivalent optimization problems because RMXP is a reformulation of RMGP. Therefore, for each marginal strategy resulting from RMGP, there is a corresponding mixed strategy resulting from RMXP. However, RMGP and RMXP are relaxations of MGP and MXP, respectively. Therefore, the marginal strategy resulting from RMGP can be infeasible for MGP, and the mixed strategy resulting from RMXP can be infeasible for MXP.

The MGP and MXP models are difficult to solve. So we define bounds that ensure the quality of the marginal and mixed feasible strategies, respectively, in terms of the optimality gap. We have shown that (i) Algorithm 1 and Z In this study, we assumed that the decision by an opportunistic passenger to evade paying a fare depends on the probability of being inspected. Therefore, the levels of evasion in the transit network depend on the inspection probabilities. Thus, returning a mixed strategy (if it exists) from the feasible marginal strategy resulting from Algorithm 1 makes sense if the evasion levels induced by the feasible marginal strategy are comparable to those induced by the feasible mixed strategy resulting from Algorithm 2.

Computational study and comments

In this section, we present our numerical results. The objective of the computational study is to measure the performance of the marginal and mixed strategies resulting from the heuristics described in Algorithms 1 and 2, respectively, under several parameter settings. The performance is measured in terms of the optimality gap, CPU times and the evasion induced by the feasible solutions resulting from Algorithms 1 and 2. Furthermore, we compare the marginal and mixed feasible strategies resulting from Algorithms 1 and 2 in terms of the evasion that each approach induces.

The computational experiments are based on the Metro Blue Line daily schedule on the Los Angeles Metro Rail line (https://www.metro.net), which has a reported average daily ridership demand of 63008. Several random instances were generated considering that the number of passengers that a patrol could inspect per minute on edge e ∈ E follows a discrete uniform distribution between 2 and 6 passengers per minute, i.e., h e ∼ U{2, ..., 6}. Furthermore, different values for the threshold c and the number of patrols were considered. We set the ticket price B = 1.5 and fine F = {75, 37.5} such that the ratios between the ticket price and fine were c = {2%, 4%}, and the number of patrols was in n = {1, ..., 11}. It should be noted that the threshold value c is 2.3% and 3% for Los Angeles Metro Rail Line and MTA of New York, respectively.

The number of passengers in the network depends on the time of day, so we define two periods of low use, three periods of medium use, and two periods of high use, as indicated in Table 1. We consider that 15% of the passenger types travel with a low use schedule, 55% with a medium use schedule, and 30% with a high use schedule. The graphs G = (V, E) and G =(ν, ε) were constructed in C. Models RMGP, RMP(1), SP(1) and RMP(MX) were solved using CPLEX 20.1. An α-Schedule stabilization technique [START_REF] Pessoa | Automation and combination of linearprogramming based stabilization techniques in column generation[END_REF]) was implemented for the CG-based schemes involving the model RMP(1) -SP(1). The time limit was set to 10800 s for CG-based schemes. For all instances and models, the termination criterion was an optimality gap of 10 -5 . All of the tests were conducted using a cluster of 11 machines where each had an Intel Core i7

2.3-GHz processor and 16 GB RAM.

Performance of the feasible marginal strategy obtained by Algorithm 1

To measure the performance of the feasible solution obtained for MGP using the heuristic described in Algorithm 1, we compute the relative optimality gap between the upper bound given by Z * RM GP and the lower bound given by the marginal feasible solution, i.e., Gap(%) = 100 × (Z * RM GP -Ẑ)/ Ẑ. Figure 6 shows the average relative optimality gap for the feasible marginal strategy under different numbers of passenger types, values for the threshold c, and patrols. Figure 6 shows that the relative optimality gap for the feasible solution to MGP increases with the threshold c but decreases with the number of patrols n. We infer from the instances tested that the heuristic in Algorithm 1 could obtain good quality feasible marginal strategies because the maximum optimality gap is 0.82%.

For each instance, we compute the evasion rate generated by the feasible solution to MGP. The evasion rate was measured as ER(%) = 100 × k∈K:U o k <B 0.5 do k / k∈K d k , where U o k is optimal variable of RMGP when an opportunistic passenger of type k does not violate constraint (35), and U o k = U o k according to (37) when an opportunistic passenger of type k violates constraint (35). Figure 7 shows the average evasion rates, induced by the feasible marginal strategy, for each passenger sample size |K| under different values for the threshold c and number of patrols. As expected, Figure 7 shows that evasion rate decreases with the number of patrols n but increases with the threshold c. For each sample of passenger types, the maximum evasion rate is reached with the maximum threshold c and minimum number of patrols, i.e., c = 0.04 and n = 1, respectively. For instance, when the train line had 30000 types of passengers (|K| = 30000), a fine equal to 25 times the fare (c = 0.04), and one patrol, the maximum evasion rate is 27.1%. It should be noted that increasing the fine decreases the evasion rate. We do not observe that an increase in the fine in proportion to the value of the ticket discourages control efforts as observed in [START_REF] Buehler | Payment evasion[END_REF].

We compute the CPU time for Algorithm 1 based on the test set of 30 instances. The average time required to compute the feasible solution for MGP was 32 s and 247 s in the worst case. The CPU time increases with the number of passenger types |K| because the number of variables in the LP relaxation RMGP is proportional to |K|.

Performance of the feasible mixed strategy obtained by Algorithm 2

In this section, set P 1 is evaluated to generate feasible solutions to the leader's problem under a mixedbased approach. We measure the relative optimality gap between the feasible solution that the set of joint patrol paths P 1 induces in RMP(MX) and the upper bound provided by the marginal solution, i.e., Gap(%) = 100 × (Z * RM GP -Z * RM P (M X) (P 1 ))/Z * RM P (M X) (P 1 ). The set of joint patrol paths P 1 and the optimal value to RMP(MX) using P r = P 1 are obtained according to the heuristic described in Algorithm 2. Figure 8 Figure 8 shows that the relative optimality gap decreases with the number of patrols n and increases with the threshold c. For each sample of passenger types, the maximum gap is reached for the maximum threshold c and minimum number of patrols, i.e., c = 0.04 and n = 1 respectively. The maximum optimality gap induced by the P 1 set is 14.2% when |K| = 10000, c = 0.04 and n = 1. Clearly, this mixed solution is not a good quality solution in terms of the optimality gap. However, it is difficult to envisage that the line operator would consider using only one patrol (n = 1) to control a train system with 17 stations and 272 trains for 23 hours. The line operator would define how many patrols to use by observing the evasion rate induced by the feasible mixed strategy. Therefore, the information in Figure 8 must be complemented with the evasion rate induced by each feasible mixed strategy.

Similarly to the feasible marginal solution, we compute the evasion rate generated by the feasible solution for MXP. The evasion rate is measured as ER(%) = 100× k∈K:U o k <B 0.5 do k / k∈K d k , where U o k is is optimal variable for RMP(MX) using P r = P 1 . Figure 9 shows the average evasion rates for each passenger sample size |K| under different values for the threshold c and numbers of patrols.

Figure 8 and 9 show that a feasible mixed strategy that induces an evasion less than or equal to 5% has approach. Thus, we defined a new heuristic to determine feasible solutions for the leader's problem under a mixed-based approach. Our computational results showed that this heuristic provides good quality solutions in terms of the optimality gap for all feasible mixed strategies that induce evasion less than or equal to 5% because the maximum optimality gap was 1.19%.

We compare the marginal and mixed feasible strategies resulting from the heuristics proposed in this study. From the computational results, we observe that the feasible marginal strategy overestimates opportunistic passenger evasion for all evasion levels less than or equal to 5%.

Several issues may be addressed in future research. The first issue is the scalability of the heuristics presented in this paper to return a feasible mixed strategy and thus address more complex networks in terms of the number of lines, duration of daily schedule, and number of vehicles. Scalability can be addressed by improving the performance of the CG-based scheme or using the Bienstock -Zuckerberg Algorithm (BZ) [START_REF] Bienstock | A new lp algorithm for precedence constrained production scheduling[END_REF]), that has proven to be an excellent alternative to the CG procedure. The second issue is related to the assumption that opportunistic passengers are rational and that their decision whether to buy a ticket or not is based purely on their expected cost. However, it is known that other factors may influence the decisions of opportunistic passengers, e.g., the quality of service as reported in [START_REF] Guarda | What is behind fare evasion in urban bus systems? an econometric approach[END_REF] and Torres-Montoya (2014). In the same line, a third issue is to consider other possible pure follower strategies, e.g., buying the ticket, following the shortest path, or evading by using a longer path. A fourth issue is related to the assumption that opportunistic passengers have complete information regarding the distribution of inspection probabilities. If we assume that the inspection probabilities perceived by passengers are different from those set by the transit operator, as in [START_REF] Avenhaus | Applications of inspection games[END_REF], the opportunistic passengers could respond suboptimally. Therefore, it would be interesting to formulate and solve more general models to produce solutions that are robust to the suboptimal behavior of opportunistic passengers.

A fifth issue is related to the inspection policy. In this study, we assumed that patrols perform inspections on-board the transportation vehicle and in-stations. If we only consider in-station inspections for the fare inspections scheduling problem, the constraints associated with the inspection probabilities can be written as linear constraints. Thus, the leader's problem under a marginal-based approach can be formulated as an LP. However, the number of inspectors in a patrol must be related to the flow of passengers leaving the train if this inspection policy is to be considered efficient. A sixth direction is the use of an exact formulation of inspection probabilities in problems similar to the scheduling of fare inspection, in order to develop new heuristics and provide a measure of quality of the obtained solutions.

TimeFigure 1 : 1 Figure 1 :

 111 Figure 1: Path of two patrols in a transit line represented by G .

  and (3) is the definition of the expected value. Let the random variable ω o k,e |χ e be the number of opportunistic passengers of type k inspected on edge e ∈ E given that this edge is controlled by χ e patrols. The conditional probability of not inspecting an opportunistic passenger of type k on edge e, which is under the control of i patrols, is defined as f o k,e|i = P(ω o k,e = 0|χ e = i). Let N e be the set of passenger types in edge e, i.e., N e = {k ∈ K : e ∈ E k } where E k is the set of edges e ∈ E followed by passengers of type k; let h e be the number of passengers that a single patrol can inspect per unit of time on edge e; and l e is the length of the edge e = (v, v ′ ), i.e., l e = τ ′ -τ where T (v ′ ) = τ ′ and T (v) = τ . We consider that ω o k,e |χ e follows a hypergeometric distribution because χ e patrols control ⌊h e l e ⌋χ e passengers in e ∈ E (without replacement) out of a total of k∈Ne d k passengers of which d o k are opportunistic passengers of type k. Conditioning on d o k , we have:

TimeFigure 1 :Figure 2 :

 12 Figure 1: Expected flow of patrols in a transit line represented by G

Figure 4 :

 4 Figure 4: Illustrative example of the convex hull for set C k with E k = {e ′ , e ′′ }

Figure 5 :

 5 Figure 5: Geometric interpretation of the heuristic for computing a lower bound of MGP

= 360 .

 360 According to the timetable, the Metro Blue Line has 17 stations (|S| = 17), and operates 23 hours each day with 272 daily trains (|R| = 272). We defined ten time windows (|J| = 10), each 360 minutes long (△ max = 360), deployed symmetrically during the 1380 minutes of the transportation system daily operations (23 hours). The time windows overlap every 120 minutes, i.e., τ • j+1 = τ • j + 120, with j = 1, ..., |J| -1, τ in 1 = 0 and τ out 1 The length of the slack for the beginning and end of the jth time window are defined as △ in j = △ out j = 10 minutes respectively. The minimum time passengers stay at the destination station is defined as △ min = 3 minutes. Using these settings, the metro line schedule is used to generate a graph G with |V | = 4355, |E| = 9178 and an extended graph G with |ν|= 11874, |ε| = 23645.

Figure 6 :

 6 Figure 6: Average optimality gap for the feasible marginal solution obtained using Algorithm 1

Figure 7 :

 7 Figure 7: Average evasion rate obtained using Algorithm 1

Figure 8 :

 8 Figure 8: Average optimality gap for the feasible mixed solution obtained using Algorithm 2.

  problem under a marginal-based approach RMGP LP relaxation of MGP model based on geometric structure MXP Leader's problem under a mixed-based approach RMP(MX) Restricted master problem of the CG-based scheme for solving the MXP model SP(MX) Pricing problem of the CG-based scheme for solving the MXP model RMXP Mixed reformulation of RMGP RMP(1) Restricted master problem of the CG-based scheme for solving RMXP SP(1) Pricing problem of the CG-based scheme for solving RMXP Sets S Set of stations indexed by s = 1, ..., |S| K Set of types of passengers indexed by k = 1, ..., |K| I Set of available patrols indexed by i = 1, ..., n R Set of trains indexed by r = 1, ..., |R| V Set of vertices of graph G E Set of edges of graph G J Set of time windows during which a patrol can begin the inspection indexed by j = 1, ..., |J| ε Set of vertices of extended graph G ν Set of edges of extended graph G E k Set of edges that passengers of type k follow in graph G N e Set of types of passengers that use edge e ∈ E, i.e., N e = {k ∈ K : e ∈ E k } E e Set of edges e ′ ∈ ε equal to the edge e ∈ E P Set of all joint patrol paths (pure strategies) for the line operator Parameters B ticket price F fine with F >> B c threshold relationship between ticket price and fine defined as c = B/F d k expected number of daily passengers of type k d o k number of daily opportunistic passengers of type k t rs arrival/departure time of train r in station s τ rs normalized arrival/departure time of train r in station s h e number of passengers that a patrol can inspect per unit of time on edge e l e length of edge e ∈ E in unit time fk,e|i conditional probability of not inspecting an opportunistic passenger of type k on edge ewhen this edge is inspected by i patrols n k cardinality of indexed set E k △ max maximum length of a patrol path △ in j length of the slack for the beginning of the jth time window opportunistic passenger of type k purchases the ticket, and 0 if the opportunistic passenger of type k wishes to evade X e expected number of patrols on edge e ∈ E Y e expected number of patrols on edge e ∈ ε H i e probability that i patrols inspected the edge e ∈ E P o k probability that opportunistic passenger of type k is inspected Po k,e probability of not inspecting an opportunistic passenger of type k on edge e X e|p number of patrols that inspect edge e ∈ E in the joint patrol path p Y e|p number of unit patrols on edge e ∈ ε in the joint patrol path p H i e|p equal to 1 if edge e ∈ E is inspected by i patrols on the joint patrol path p, but 0 otherwise Po k,e|p probability of not inspecting an opportunistic passenger of type k on edge e ∈ E given the joint patrol path p P o k|p probability that an opportunistic passenger of type k is inspected given joint patrol path p π p probability of selecting joint patrol path p Table A.3: Glossary of terms

  RM GP provide a lower and upper bound to the MGP model respectively, i.e., Ẑ ≤ Z * M GP ≤ Z * RM GP ; and (ii) Algorithm 2 and Z * RM GP provide a lower and upper bound to the MXP model respectively, i.e., Z * RM P (M X) (P 1 ) ≤ Z * M XP ≤ Z * RM GP . The heuristics described in Algorithms 1 and 2 provide marginal and mixed feasible strategies, respectively, whose relationship is unknown.

*

Table 1 :

 1 Demand schedulesAccording to the timetable for the Metro Blue Line, the maximum number of passenger types is 33682.We define random samples of |K|-size passenger types, which are distributed in proportion to the time of day, as shown in Table1. In particular, 30 random instances are evaluated (10 instances each with |K| = 10000, 20000, and 30000 types of passengers). The number of passengers of type k (d k , ∀k ∈ K), is generated randomly with a discrete uniform distribution according to the demand schedule in Table1, and the demand support presented in Table2. The average and maximum number of passengers in the 30 instances are presented in Table2.

			Time	Normalized time
	Demand	start	finish	start	finish
	Low		3:51 AM	6:29 AM	0	158
	Average		6:30 AM	7:00 AM	159	189
	High		7:00 AM	8:59 AM	189	308
	Average		9:00 AM 17:59 PM	309	848
	High		18:00 PM 19:59 PM	849	968
	Average		20:00 PM 20:59 PM	969	1028
	Low		21:00 PM 3:05 AM	1029	1397
		Demand Schedule	Total passengers
	|K|	Low	Average	High	Average	max
	10000 {1, .., 4} {4, .., 8} {8, .., 13}	63156	63272
	20000	{1, 2}	{2, .., 4}	{4, , 8}	63459	63638
	30000	{1, 2}	{2, 3}	{3, .., 5}	64523	64600

Table 2 :

 2 Demand of passengersOnce the number of passengers of type k is computed (d k , ∀k ∈ K), we consider that up to 40% of the passengers of type k can be opportunistic, i.e., d o k ∼ U {0, ..., do k } with do k = ⌊0.4d k ⌋ + 1 for any k ∈ K.

Acknowledgements

Pablo Escalona is grateful for the support of ANID, through grant FONDECYT 11200287.

an optimality gap strictly less than 1% and 2% when c = 0.02 and c = 0.04 respectively, which are very good solutions that provide the number of patrols and a feasible mixed strategy, i.e., the set of useful joint patrol paths and their respective probabilities of being selected. From Figure 10 we observe that the number of useful joint patrol paths is decreasing in the number of patrols, which is intuitive because a greater number of available patrols requires fewer joint patrol paths to achieve the desired level of evasion.

For the 30 instances in the test set, we compute the CPU time associated with Algorithm 2 to determine the feasible solutions for the MXP model. Figure 11 shows the average CPU times associated with Algorithm 2 under different number of passenger types, values for the threshold c, and numbers of patrols. Once the performance of the feasible mixed strategies resulting from Algorithm 2 has been evaluated, we illustrate its applicability with the following example. When we consider 30000 types of passengers (|K| = 30000) and a fine equal to 50 times the fare (c = 0.02), the feasible mixed strategy involving the smallest number of patrols that ensure an evasion rate less than or equal to 5% require no more than five patrols (Figure 9a) and 202 joint patrol paths (Figure 10a) to induce a maximum evasion rate of 3.4%

(average evasion rate of 3.2% according to Figure 9a). These solutions are of good quality because the maximum optimality gap is 0.79% (average optimality gap of 0.77% according to Figure 8a). Furthermore, the average time required to compute these solutions is 10800 s (Figure 11a). Similarly, when we consider |K| = 30000 and c = 0.04, the feasible mixed strategy involving the smallest number of patrols that ensure an evasion rate less than or equal to 5% requires no more than nine patrols (Figure 9b) and 174 joint patrol paths (Figure 10b) to induce a maximum evasion of 4.3% with a maximum optimality gap of 1.19% (average optimality gap of 1.17% according to Figure 8b) and an average CPU time of 10800 s (Figure 11b).

Comparing the marginal and mixed feasible strategy.

From Figures 7 and9, we observe that the evasion induced by the feasible marginal strategy decreases at a lower rate than the evasion induced by the feasible mixed strategy for all evasion levels less than or equal to 5%. For example, when we consider 30000 types of passengers (|K| = 30000) and a fine equal to 50 times the fare (c = 0.02), the evasion induced by the marginal and mixed feasible strategy considering 11 patrols are 3% and 0.1% on average respectively (Figures 7a and 9b respectively). Similarly, when |K| = 30000 and c = 0.04, the evasion induced by the feasible marginal and mixed strategy considering 11 patrols are 4.3% and 2.5% on average respectively (Figures 7b and 9b respectively).

Consequently, we infer that the evasion induced by the feasible marginal strategy resulting from Algorithm 1 overestimates the evasion of opportunistic passengers for all evasion levels less than or equal to 5%. Thus, a heuristic that returns a mixed strategy from the feasible marginal feasible strategy resulting from Algorithm 1 must consider this overestimation.

Conclusion

In this study, we considered the fare inspection scheduling problem involving unpredictable patrolling to inhibit fare evasion in POP S systems from a Stackelberg game perspective. According to the economic analysis of rational crime, we assumed that the decision by an opportunistic passenger to evade paying a fare depends on the probability of being inspected, which is determined by the transit operator using a fixed number of patrols. Under a Stackelberg game approach, two types of approaches were distinguished to determine the inspection probabilities, namely the marginal and mixed strategy. The marginal strategy only refers to the inspection probabilities in the transit network while a mixed strategy determines the inspection probabilities using a set of joint patrol paths and their corresponding probabilities of being selected.

By using a marginal-based approach to define the Stackelberg game between the transit operator and opportunistic passengers, and an exact formulation for the inspection probabilities, we formulated the leader's problem as a single level NLP. As this problem is difficult to solve, we derived a new LP relaxation of the leader's problem under a marginal-based approach that exploits the geometric structure of the problem.

Furthermore, we determined a lower bound from the new LP relaxation and then defined a heuristic to determine feasible solutions for the leader's problem under a marginal-based approach. Our computational results showed that the feasible marginal strategy determined using the new heuristic was a good quality solution where the maximum optimality gap was 0.82%. To the best of our knowledge, this is the first time the quality of a marginal strategy for the fare inspection scheduling problem has been reported.

In addition, we formulated the leader's problem under a mixed-based approach using a CG approach.

The master problem, that determines the joint patrol paths and their corresponding probabilities of being selected for maximizing the transit operator's revenue, was formulated as an LP and the pricing problem that generates feasible joint patrol paths was formulated as a MINLP. The leader's problem under a mixed-based approach is difficult to solve for realistic instances. Therefore, we provided a lower bound (feasible solution)

using the set of joint patrol paths obtained from the mixed reformulation of the LP relaxation, where the inspection probabilities were reformulated as a convex combination of pure strategies. We showed that the optimal solution of the LP relaxation is an upper bound for the leader's problem under a mixed-based


domain: phys spi

text:
Alexandra Apostoluk
email: aleksandra.apostoluk@insa-lyon.fr

Yu Zhang

Christophe Theron

Thibaut Cornier

Beata Derkowska

Malgorzata Sypniewska

Stéphane Danièle

Bruno Masenelli

Doping zinc oxide nanohybrids for application in white light emitting diodes

We present a study concerning the effect of doping in inorganic/organic ZnO/PAAH (polyacrylic acid) nanohybrids. The doping atoms vary in their ionic size, electronic valence and concentration. Some of them have been are known to provide ZnO with magnetic properties. The effect on the optical properties of the ZnO nanoparticles of three different concentrations (0.1 %, 1 % and 5 %) of dopants is compared. The luminescent properties of the undoped and doped nanohybrids are reported.

Introduction

Zinc oxide is a common direct and wide band gap semiconducting material (3.37 eV at room temperature [1]), which has usually been used for multiple applications in the UV range [2]. A good crystalline quality of ZnO is obligatory to obtain a high luminescent efficiency, but the recombination on the inevitable intrinsic defects present in ZnO crystal lattice is competing with the excitonic emission, making the efficiency of these UV devices rather low. Though a tremendous effort has been devoted to reduce the presence of these undesirable defects, they can actually be attractive as they give rise to a wide range of light emission from blue to IR, especially at the nanoscale. They can be used as phosphors in white light emitting diodes (WLEDs) and in plus, they are rare-earth-free. This fact is non negligible, as it is China who assures 95 % of the global supply in rare earth elements today.

Sample preparation

The synthesis method used reproduces the one described in our previous study, given in [3]. It is based on the of diethyl zinc (ZnEt 2 ) hydrolysis. 1.8 ml of a solution of diethyl zinc (15 wt%) in toluene is added dropwise in an aqueous solution containing 0.63 wt% of poly-acrylic acid, (PAAH).

During the synthesis process, the mixture is vigorously stirred all the time under inert atmosphere as ZnEt 2 is pyrophoric. The ethane resulting from the hydrolysis is constantly evacuated. The reaction scheme is as follows: 2) → ZnO nanohybrids Dopant salts (the source of the doping atoms) are solubilized in the PAAH aqueous solution before adding them to ZnEt 2 . After the phase (1) PAAH and the doping atom can be added (if any) -Fe 2+ , Fe 3+ , Al 3+ , Cu + , Cu 2+ , Y 3+ , among others. We also studied the doping with rare earths, for comparison. After phase (2), the obtained reaction product is washed and put at 70°C for 4 h.

ZnEt 2 + H 2 O (1) → ZnO + 2 EtH (

Optical measurements

The optical properties of the nanoparticle samples were measured using the photoluminescence (PL) set up. It consists of a continuous wave laser emitting at 266 nm (power of 8 mW, model Crylas FQCW 266-10). The emission from the sample was collected with an optic fiber, then dispersed by a spectrometer (iHR Triax 320 Jobin-Yvon) and detected using a liquid-nitrogen cooled Si CCD detector. Since our main concern is to obtain materials with a high PL yield, the photoluminescence internal quantum efficiency (PL iQY) of our samples was also measured, using an integrating sphere with the same excitation and detection set up as for the PL studies.

Results and discussion

The obtained results confirm in the first place what was also observed in the literature, that increase in the dopant concentration leads to the quenching of the visible luminescence of ZnO nanostructures, whatever the fabrication process. In our case, for some doping atoms, a low doping concentration (0.1 %) can improve or at least permits to maintain the same PL iQY, when compared to non-doped ZnO nanopowders [4]. Finally, doping in inorganic/organic ZnO/PAAH nanohybrids makes possible to tune the visible emission spectrum of this compound between 2.17 eV and 2.46 eV.

Conclusions

The degradation of photoluminescence internal quantum efficiency is not necessarily observed in then studied nanocomposites. At low doping concentration for some dopants with a small or comparable ionic radius to the one of Zn 2+ , PL iQY can be maintained or even improved, making it possible to tune the visible emission spectrum between 2.17 eV and 2.46 eV. This opens up the prospect of synthesizing phosphors without rare earths for white LEDs, whose spectrum can be rather easily tuned to fabricate warm or cold white light, by a chemical synthesis method having a low environmental impact.

Acknowledgements

Yu Zhang is grateful to the CSC (China Scholarship Council) for supporting his work with a PhD grant.