Approximation Algorithms for Line Planning with Heterogeneous Fleets and Multiple Resource Constraints

This paper studies line planning for urban bus networks that face multiple resource limits such as budget, labor, and emission caps while using heterogeneous fleets. The objective is to maximize total reward from serving passengers by assigning buses to candidate routes subject to capacity and resource constraints. The reward parameters are general and can encode diverse user preferences and multi-modal system configurations. Prior work typically assumes single resource constraints and homogeneous fleets, and often relies on methods that lack theoretical guarantees or computational tractability. We develop the first approximation algorithms with provable guarantees for this setting. For the cost-free variant, a randomized rounding scheme attains the optimal ratio $1-1/e$ which is tight unless $P = NP$. Leveraging this base algorithm, we derive extensions for the general case with arbitrary cost vectors, obtaining constant-factor approximation guarantees. To support large-scale application, we adapt the base algorithm to ensure computational scalability while preserving rigorous theoretical guarantees. Experiments on Greater Boston transit data demonstrate that our approach achieves 95\% to 98\% of the linear programming relaxation bound, whereas Gurobi solver fails on considerably smaller instances. Our experiments further show that heterogeneous fleets significantly outperform homogeneous ones and that multi-resource optimization is required to avoid significant resource limit violations, thereby underscoring the importance of our framework.