Subsidy Allocation Problem with Bus Frequency Setting Game: A Trilevel Formulation and Exact Algorithm

Typically, governments subcontract the operation of urban bus systems to several bus operators. In particular, the government aims to promote the service quality for passengers by introducing competition among bus operators and subsidizes bus operations to ensure affordable fares. However, most existing studies about subsidy allocation typically do not account for the competitive factors among bus operators and thus may underestimate the associated benefits. In this study, we investigate how the government allocates subsidies to minimize social costs, taking into account the competition among bus operators and passenger route decisions. We describe this problem as a trilevel optimization model and use a game-theoretic approach to characterize the market equilibrium of bus operators. Next, we transform the trilevel model into a mixed-integer programming problem with quadratic constraints and solve it using an exact algorithm with acceleration techniques. The results of numerical experiments demonstrate the computational efficiency of the proposed algorithm. Several valuable insights are derived: First, lines served by competing bus operators typically do not require subsidies. Second, competitive behavior decreases social costs (including bus operating costs and passenger travel costs) more effectively in cities in which the passengers assign higher value to time. Third, the competitive behavior may be guided by exogenous parameters, such as ticket prices, to approximate the optimum of urban bus systems.