A Trilevel Programming Model and Nested Generalized Benders Decomposition for the Bus Line Contracting Problem

Contracting bus services to private operators has become a prominent strategy for improving efficiency and reducing costs in urban transit systems. However, existing research largely overlooks the fact that different bus lines exhibit heterogeneity in demand, operating cost, and profitability, which critically affects contracting decisions. This study investigates how the government can strategically determine which bus lines to contract in order to minimize total social cost while accounting for the behavioral responses of the private operator and passengers. We formulate this decision-making problem as a trilevel programming model that integrates three layers of strategic interaction: line contracting by the government, frequency setting by a profit-maximizing private operator, and route choice by passengers under a transit equilibrium assignment model. To solve the trilevel model exactly, we develop a nested generalized Benders decomposition algorithm with logic-based cuts, and we further enhance it through a relaxation-based acceleration strategy. The computational experiments demonstrate the effectiveness of the proposed algorithm and reveal valuable managerial insights; selectively contracting bus lines outperforms several alternative contracting schemes, and the resulting system equilibrium is highly sensitive to exogenous parameters. These findings highlight the importance of coordinated, system-level regulation in the design of public-private partnerships for transit planning.

History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete.

Funding: This research was supported by the National Natural Science Foundation of China [Grants T2525020, 72371221] and the Postgraduate Research & Practice Innovation Program of Jiangsu Province [Grant KYCX24_0462].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1527) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2025.1527). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.