  Public transit systems in urban areas usually require large state subsidies,
primarily due to high fare evasion rates. In this paper, we study new models
for optimizing fare inspection strategies in transit networks based on bilevel
programming. In the first level, the leader (the network operator) determines
probabilities for inspecting passengers at different locations, while in the
second level, the followers (the fare-evading passengers) respond by optimizing
their routes given the inspection probabilities and travel times. To model the
followers' behavior we study both a non-adaptive variant, in which passengers
select a path a priori and continue along it throughout their journey, and an
adaptive variant, in which they gain information along the way and use it to
update their route. For these problems, which are interesting in their own
right, we design exact and approximation algorithms and we prove a tight bound
of 3/4 on the ratio of the optimal cost between adaptive and non-adaptive
strategies. For the leader's optimization problem, we study a fixed-fare and a
flexible-fare variant, where ticket prices may or may not be set at the
operator's will. For the latter variant, we design an LP based approximation
algorithm. Finally, using a local search procedure that shifts inspection
probabilities within an initially determined support set, we perform an
extensive computational study for all variants of the problem on instances of
the Dutch railway and the Amsterdam subway network. This study reveals that our
solutions are within 95% of theoretical upper bounds drawn from the LP
relaxation.
