pith. sign in

arxiv: 2311.03327 · v4 · submitted 2023-11-06 · 🧮 math.OC

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

Hongyi Jiang , Igor Averbakh , Samitha Samaranayake This is my paper

Pith reviewed 2026-05-24 05:47 UTC · model grok-4.3

classification 🧮 math.OC
keywords line planningapproximation algorithmsrandomized roundingheterogeneous fleetsresource constraintsbus networksinteger linear programmingurban transit
0
0 comments X

The pith

A randomized rounding scheme achieves the optimal 1-1/e approximation ratio for the cost-free line planning problem and extends to constant-factor guarantees when costs are arbitrary.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops the first approximation algorithms with provable guarantees for maximizing passenger rewards when assigning heterogeneous buses to pre-specified routes under capacity limits and multiple resource constraints such as budgets and emissions. For the cost-free case the method uses randomized rounding to reach the ratio 1-1/e, which is tight unless P equals NP. The same base routine is extended to handle general cost vectors while retaining constant-factor performance, and a scalable variant is shown to solve large instances. Experiments on real transit data confirm that the approach reaches 95 to 98 percent of the LP relaxation value and that both fleet heterogeneity and multi-resource modeling matter in practice.

Core claim

For the cost-free variant of the line planning problem, a randomized rounding scheme attains the optimal approximation ratio of 1-1/e, which is tight unless P=NP. Leveraging this base algorithm yields constant-factor approximation guarantees for the general case with arbitrary cost vectors, all while respecting capacity and multiple resource constraints in an integer linear program with general reward functions.

What carries the argument

Randomized rounding applied to the LP relaxation of the integer linear program that encodes route assignments, passenger rewards, and the full set of capacity and resource constraints.

If this is right

  • Heterogeneous fleets produce substantially higher total reward than homogeneous fleets under the same resource limits.
  • Optimizing over multiple resources simultaneously avoids large violations that single-resource models permit.
  • The scalable adaptation of the rounding routine solves instances far larger than those solvable by exact MIP solvers while staying within a few percent of the LP bound.
  • The constant-factor extensions apply directly once any linear cost structure is added to the model.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same rounding template could be tested on related network design problems that share the structure of selecting subsets of routes under knapsack-style constraints.
  • The inapproximability result for the cost-free case suggests that any future exact or near-exact method would need to exploit special structure beyond the general ILP formulation.
  • If the pre-specified route set is itself generated by a heuristic, the overall guarantee would be the product of the rounding ratio and the route-generation quality.

Load-bearing premise

The line planning problem can be modeled as an integer linear program whose objective is a general reward function subject to capacity and multiple resource constraints, with candidate routes given in advance.

What would settle it

A concrete small instance of the cost-free problem on which the randomized rounding procedure returns a solution whose expected reward is strictly less than (1-1/e) times the optimum, or a polynomial-time algorithm that beats the 1-1/e ratio on all instances.

Figures

Figures reproduced from arXiv: 2311.03327 by Hongyi Jiang, Igor Averbakh, Samitha Samaranayake.

Figure 1
Figure 1. Figure 1: The workflow of the section. 9 [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: An illustration for the proof of Theorem [PITH_FULL_IMAGE:figures/full_fig_p018_2.png] view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper studies the line planning problem for urban bus networks with heterogeneous fleets and multiple resource constraints (budget, labor, emissions). It models the problem as maximizing a general reward function (encoding passenger preferences) subject to capacity and resource limits on pre-specified candidate routes, and develops approximation algorithms: a randomized rounding scheme claimed to achieve the tight 1-1/e ratio for the cost-free case, constant-factor extensions for arbitrary costs, and scalable variants. Experiments on Greater Boston data show the algorithms reach 95-98% of the LP relaxation bound where Gurobi fails, and demonstrate benefits of heterogeneous fleets and multi-resource optimization.

Significance. If the approximation guarantees hold under the stated modeling assumptions, the work would be significant as the first set of provable approximation algorithms for line planning with heterogeneous fleets and multiple simultaneous resource constraints. The experimental results on real transit data, including near-LP performance and solver comparisons, provide concrete evidence of practical relevance and would strengthen the contribution.

major comments (1)
  1. [Abstract] Abstract: the claim that a randomized rounding scheme attains the optimal ratio 1-1/e (tight unless P=NP) for the cost-free variant is stated for a 'general reward function' encoding arbitrary preferences. Standard analyses of randomized rounding (or continuous greedy) yield 1-1/e only when the objective is monotone submodular; for truly arbitrary rewards the problem reduces to a general ILP without this guarantee. This modeling assumption directly underpins the central theoretical result and requires explicit clarification or proof that the reward is submodular.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful review and for identifying this key point about the modeling assumptions. We address the comment below and will make the necessary revisions to clarify the conditions under which the approximation guarantee holds.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the claim that a randomized rounding scheme attains the optimal ratio 1-1/e (tight unless P=NP) for the cost-free variant is stated for a 'general reward function' encoding arbitrary preferences. Standard analyses of randomized rounding (or continuous greedy) yield 1-1/e only when the objective is monotone submodular; for truly arbitrary rewards the problem reduces to a general ILP without this guarantee. This modeling assumption directly underpins the central theoretical result and requires explicit clarification or proof that the reward is submodular.

    Authors: We agree that the 1-1/e guarantee via randomized rounding requires the objective to be monotone submodular. In the model, the reward function is defined to be monotone submodular (e.g., as a coverage function over passenger groups that can be expressed as a non-negative linear combination of submodular set functions). The term 'general' is used to indicate that the specific form can encode diverse preferences, but always within the monotone submodular class. For non-submodular rewards the guarantee would not apply. We will revise the abstract, introduction, and model section to explicitly state the monotone submodularity assumption, justify why it is appropriate for passenger preference modeling, and note that the ratio is tight under this condition. This revision will be incorporated. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation relies on standard rounding techniques

full rationale

The provided abstract and description show the paper modeling the problem as an ILP with general rewards, then applying a randomized rounding scheme to obtain the 1-1/e ratio for the cost-free case and deriving constant-factor extensions. No self-definitional steps, fitted inputs renamed as predictions, or load-bearing self-citations appear. The central claims are presented as applications of known approximation methods to the stated formulation without reducing to their own inputs by construction. This matches the reader's assessment of score 2.0 and is self-contained against external benchmarks such as standard submodular maximization results.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The paper does not introduce new parameters or entities; it builds on existing integer programming formulations and approximation techniques from prior literature.

pith-pipeline@v0.9.0 · 5758 in / 1062 out tokens · 36284 ms · 2026-05-24T05:47:48.340655+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

  1. [1]

    Probabilistic properties of the dual structure of the multidimensional knapsack problem and fast statistically efficient algorithms

    Igor Averbakh. Probabilistic properties of the dual structure of the multidimensional knapsack problem and fast statistically efficient algorithms. Mathematical Programming , 65(1-3):311--330, 1994

    work page 1994

  2. [2]

    Data-driven transit network design at scale

    Dimitris Bertsimas, Yee Sian Ng, and Julia Yan. Data-driven transit network design at scale. Operations Research , 69(4):1118--1133, 2021

    work page 2021

  3. [3]

    Submodular function maximization via the multilinear relaxation and contention resolution schemes

    Chandra Chekuri, Jan Vondr \'a k, and Rico Zenklusen. Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM Journal on Computing , 43(6):1831--1879, 2014

    work page 2014

  4. [4]

    Maximizing non-monotone submodular set functions subject to different constraints: Combined algorithms

    Salman Fadaei, MohammadAmin Fazli, and MohammadAli Safari. Maximizing non-monotone submodular set functions subject to different constraints: Combined algorithms. Operations research letters , 39(6):447--451, 2011

    work page 2011

  5. [5]

    A threshold of (n) for approximating set cover

    Uriel Feige. A threshold of (n) for approximating set cover. Journal of the ACM (JACM) , 45(4):634--652, 1998

    work page 1998

  6. [6]

    A unified continuous greedy algorithm for submodular maximization

    Moran Feldman, Joseph Naor, and Roy Schwartz. A unified continuous greedy algorithm for submodular maximization. In 2011 IEEE 52nd annual symposium on foundations of computer science , pages 570--579. IEEE, 2011

    work page 2011

  7. [7]

    Tight approximation algorithms for maximum separable assignment problems

    Lisa Fleischer, Michel X Goemans, Vahab S Mirrokni, and Maxim Sviridenko. Tight approximation algorithms for maximum separable assignment problems. Mathematics of Operations Research , 36(3):416--431, 2011

    work page 2011

  8. [8]

    Incidence matrices and interval graphs

    Delbert Fulkerson and Oliver Gross. Incidence matrices and interval graphs. Pacific journal of mathematics , 15(3):835--855, 1965

    work page 1965

  9. [9]

    Approximation algorithms for capacitated assignment with budget constraints and applications in transportation systems

    Hongyi Jiang and Samitha Samaranayake. Approximation algorithms for capacitated assignment with budget constraints and applications in transportation systems. In International Computing and Combinatorics Conference (COCOON) , pages 94--105. Springer, 2022

    work page 2022

  10. [10]

    Maximizing submodular set functions subject to multiple linear constraints

    Ariel Kulik, Hadas Shachnai, and Tami Tamir. Maximizing submodular set functions subject to multiple linear constraints. In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms , pages 545--554. SIAM, 2009

    work page 2009

  11. [11]

    Approximations for monotone and nonmonotone submodular maximization with knapsack constraints

    Ariel Kulik, Hadas Shachnai, and Tami Tamir. Approximations for monotone and nonmonotone submodular maximization with knapsack constraints. Mathematics of Operations Research , 38(4):729--739, 2013

    work page 2013

  12. [12]

    Non-monotone submodular maximization under matroid and knapsack constraints

    Jon Lee, Vahab S Mirrokni, Viswanath Nagarajan, and Maxim Sviridenko. Non-monotone submodular maximization under matroid and knapsack constraints. In Proceedings of the forty-first annual ACM symposium on Theory of computing , pages 323--332, 2009

    work page 2009

  13. [13]

    GTFS developers

    Massachusetts Bay Transit Authority . GTFS developers . Accessed August 2, 2018, 2014

    work page 2018

  14. [14]

    Randomized algorithms

    Rajeev Motwani and Prabhakar Raghavan. Randomized algorithms . Cambridge university press, 1995

    work page 1995

  15. [15]

    Real-time approximate routing for smart transit systems

    No \'e mie P \'e rivier, Chamsi Hssaine, Samitha Samaranayake, and Siddhartha Banerjee. Real-time approximate routing for smart transit systems. Proceedings of the ACM on Measurement and Analysis of Computing Systems , 5(2):1--30, 2021

    work page 2021

  16. [16]

    Line planning in public transportation: models and methods

    Anita Sch \"o bel. Line planning in public transportation: models and methods. OR spectrum , 34(3):491--510, 2012

    work page 2012

  17. [17]

    Planning the route system for urban buses

    Lionel Adrian Silman, Zeev Barzily, and Ury Passy. Planning the route system for urban buses. Computers & operations research , 1(2):201--211, 1974

    work page 1974