💻 computer science

The Influence of Agent Models on the Complexity of Bus Routing

This paper investigates the computational complexity of bus routing problems on general and tree-structured networks, demonstrating that agent-specific cost models and the option to walk directly significantly increase hardness, often resulting in NP-hardness and parameterized intractability even for simple network topologies.

Original authors: Eva Deltl, Christian Komusiewicz, Jurek Rostalsky, Johannes Schröder, Luca Pascal Staus

Published 2026-08-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Eva Deltl, Christian Komusiewicz, Jurek Rostalsky, Johannes Schröder, Luca Pascal Staus

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a city planner standing before a map of streets, tasked with drawing a single bus line that will serve thousands of people. The goal is not merely to connect point A to point B, but to weave a route that balances the time passengers spend waiting and walking with the energy the bus consumes. This is a problem of optimization, a search for the best possible arrangement of stops within a complex web of roads. In the real world, every passenger is different; some live close to a potential stop and walk quickly, while others live far away or move slowly. The challenge lies in deciding where to place a limited number of stops so that the total cost to everyone—the sum of walking distances and bus travel time—is as low as possible. This is a question that sits at the intersection of geography and computer science, asking not just how to find a good solution, but whether a perfect solution can be found at all, and how difficult the search becomes as the rules of the game change.

A team of researchers from universities in Germany set out to map the difficulty of this exact problem. They treated the city's road network as a mathematical structure, where streets are lines connecting points, and they modeled the passengers as "agents" with their own specific starting points, destinations, and walking speeds. The researchers asked a fundamental question: does the complexity of finding the best bus route depend on the shape of the city's network, or on how differently the passengers move? They tested their ideas on different types of networks, ranging from the simple straight lines of a corridor to the branching structures of trees and the hub-and-spoke design of a star. Their investigation revealed that the answer is not uniform; the difficulty of the problem shifts dramatically depending on whether the passengers are all treated the same or if each has a unique walking speed, and whether they are forced to take the bus or allowed to walk directly to their destination.

The researchers discovered that if the city's network is a general, messy web of connections, the problem is already incredibly difficult to solve perfectly, even if every passenger is assumed to walk at the same speed. However, when they simplified the network to a tree-like structure, where roads branch out without forming loops, the picture became more nuanced. They found that if all passengers share the same walking speed and the goal is to minimize the total energy used by the bus and the walking of the passengers, a computer can find the perfect route efficiently. But the moment the researchers allowed each passenger to have their own unique walking speed, the problem instantly became intractable, even on the simplest tree shapes like a star, where all roads meet at a central hub. This suggests that the individuality of the passengers is a major source of complexity.

The situation changes again when the researchers considered the time passengers spend traveling. If the goal is to minimize the total time spent by everyone, including the time spent on the bus, the problem remains difficult even if all passengers are identical and the network is a simple tree. The researchers showed that the interaction between the choice of stops and the time spent traveling creates a web of dependencies that resists efficient calculation. Furthermore, they found that allowing passengers the option to skip the bus entirely and walk directly to their destination makes the problem harder in almost every scenario. In many cases, giving people the freedom to choose between the bus and walking transforms a problem that might have been solvable into one that is computationally impossible to solve perfectly for large cities.

Despite these hurdles, the team found a glimmer of hope in the most constrained environments. When the road network is a single straight line, like a long corridor, the problem becomes solvable even if passengers have different walking speeds and the goal is to minimize energy. This is a significant finding because many real-world bus routes, such as those running along a major avenue, are effectively linear. The researchers demonstrated that for these specific cases, a computer can determine the optimal placement of stops in a reasonable amount of time. They tested this approach on a real-world example, the M15 bus corridor in New York City, using data from bike trips to simulate passenger movements. By applying their algorithm to this existing route, they showed that choosing stops based on the goal of minimizing total energy yields a different set of stops than choosing based on minimizing time. The energy-focused approach tended to cluster stops more tightly, while the time-focused approach spread them out differently, proving that the choice of objective function fundamentally changes the resulting bus line.

The study concludes that there is no single rule for how hard it is to design a bus route. The difficulty is a delicate balance between the shape of the city, the uniformity of the people using it, and the specific goal the planner is trying to achieve. While some scenarios are too complex for current computers to solve perfectly, others, particularly those along straight lines, are within reach. The work serves as a guide for planners, highlighting that while simplifying the network or the passenger model can make the math easier, the real-world freedom of passengers to walk or ride, and their individual differences, are the very factors that make the problem so challenging. The researchers suggest that future work might look at other ways to simplify these models, perhaps by grouping passengers into a few categories rather than treating them as entirely unique, to see if that makes the problem solvable in more complex city layouts.

Technical Summary: The Influence of Agent Models on the Complexity of Bus Routing

Problem Definition

The paper investigates the Multi Bus Stop Problem (MBSP), a variant of public transport planning where the goal is to select a route with exactly $k$ stops in a network to serve a set of agents. Each agent $a$ has a specific start point $s_a$ , destination $t_a$ , and an individual weight function $w_a$ representing their walking costs (e.g., time or energy). The bus has its own weight function $w_b$ representing travel costs between stops.

The problem is defined on an undirected graph $G=(V, E)$ . A bus route $B$ is a sequence of $k$ vertices. Agents choose optimal stops to board and alight to minimize their total cost, which includes walking to the boarding stop, traveling on the bus, and walking from the alighting stop to the destination. The paper studies four objective functions:

$f_{energy}$ : Minimizes the sum of the total bus route cost and the total walking costs of all agents.
$f_{time}$ : Minimizes the sum of total travel costs for all agents, where the bus travel time between boarding and alighting stops is included in the agent's cost.
$g_{energy}$ and $g_{time}$ : Variants of the above where agents are allowed to walk directly from $s_a$ to $t_a$ if this is cheaper than using the bus.

The study analyzes the computational complexity of these variants based on two factors: the structure of the underlying network (general graphs, trees, paths, stars) and the model of agent mobility (arbitrary weights, consistent weights, unit weights, unweighted).

Methodology

The authors employ a combination of parameterized complexity analysis and dynamic programming.

Hardness Proofs: To establish intractability, the paper utilizes parameterized reductions from known hard problems such as Hitting Set, Clique, Independent Set, and Vertex Cover. The parameter of interest is $k$ , the number of bus stops. The authors demonstrate W[1]-hardness and W[2]-hardness, implying that fixed-parameter tractable (FPT) algorithms running in time $f(k) \cdot n^{O(1)}$ are unlikely to exist for the hard variants.
Algorithm Design: For tractable cases, the authors design dynamic programming algorithms. These often involve preprocessing the input graph (e.g., rooting trees, binarizing them, or ordering path vertices) and defining DP states that track the number of stops used, the location of the nearest bus stop within and outside a subtree, and the number of route endpoints.
Experimental Validation: The authors implement the proposed algorithms and test them on a real-world dataset: the NYC-M15 bus corridor. They compare the performance of $f_{energy}$ and $g_{energy}$ objectives against a uniform spacing baseline.

Key Contributions and Results

1. Hardness on General Graphs

Even in the unweighted case (where all edge weights are 1), the problem is computationally difficult on general graphs.

Theorem 1: MBSP with objectives $f_{energy}$ , $g_{energy}$ , and $f_{time}$ is W[2]-hard with respect to $k$ on general graphs. This is shown via reduction from Hitting Set.
Proposition 2: The only exception is $g_{time}$ in the unweighted case, which is solvable in polynomial time because agents always prefer walking directly to the bus.

2. Impact of Agent Models on Trees and Stars

The complexity varies significantly depending on the agent weight model and the network topology.

Consistent vs. Arbitrary Weights on Trees:
- Theorem 3: For consistent agent weights (all agents share the same weight function), $f_{energy}$ is solvable in polynomial time ( $O(n^4 k^2 + |A|)$ ) on trees using dynamic programming.
- Theorem 4: If agents have arbitrary weight functions, $f_{energy}$ and $f_{time}$ become W[2]-hard even on stars (a specific tree structure). This is proven via reduction from Hitting Set.
- Theorem 5: For the $g_{energy}$ objective (allowing direct walking), the problem becomes W[1]-hard on stars even in the unweighted case, proven via reduction from Clique. This highlights that allowing agents to opt-out of the bus significantly increases complexity.
Time Objectives on Trees:
- Theorem 7: Both $f_{time}$ and $g_{time}$ are W[1]-hard on stars, even with unit agent weights. The proof uses a reduction from Independent Set, exploiting the interaction between stop selection and agent travel times.
- Theorem 13: In contrast, $f_{time}$ on unweighted stars is solvable in polynomial time. The solution involves selecting the $k$ leaves with the highest demand or including the center.
- Theorem 14: However, $f_{time}$ on unweighted trees is NP-hard, proven via reduction from Vertex Cover.

3. Path Networks

Theorem 6: For paths, both $f_{energy}$ and $g_{energy}$ are solvable in polynomial time ( $O(n^3 k \cdot |A|)$ ) even with arbitrary agent weights. The algorithm fixes the rightmost stop and iterates through possibilities for the next stop.
Theorem 15: For paths with arbitrary weights, $f_{time}$ and $g_{time}$ are W[1]-hard. The reduction from Independent Set relies on the fact that determining an agent's optimal boarding/alighting stops requires knowledge of the entire set of stops.
Theorem 16: If the path is unweighted, $f_{time}$ becomes solvable in polynomial time.

4. Experimental Findings

The authors applied their algorithms to the NYC-M15 corridor with $k=10$ stops.

Both optimized objectives ( $f_{energy}$ and $g_{energy}$ ) reduced costs by approximately 16.5% and 16.8% compared to uniform spacing.
The resulting stop sets differed between the two objectives. The $g_{energy}$ objective (allowing direct walking) produced a more compact stop placement, avoiding artificially high costs for areas far from stops, whereas $f_{energy}$ distributed stops differently.

Significance and Claims

The paper claims that the complexity of bus routing is not solely determined by the network topology but is heavily influenced by the agent mobility model and the objective function.

Model Sensitivity: The authors demonstrate that "consistent" agent models (where all users have identical walking characteristics) can lead to tractable problems on trees, whereas "arbitrary" models (individualized costs) induce hardness even on simple structures like stars.
Objective Sensitivity: The distinction between minimizing total system cost ( $f_{energy}$ ) versus total agent travel time ( $f_{time}$ ) is critical. The latter is generally harder, often remaining W[1]-hard even on stars with unit weights.
Direct Walking: Allowing agents to walk directly to their destination ( $g$ variants) generally increases complexity, turning polynomial cases into W[1]-hard ones.
Practical Implication: The experimental results suggest that different objective functions lead to qualitatively different stop placements. Therefore, planners must carefully select the objective function that aligns with their specific goals (e.g., energy efficiency vs. minimizing total travel time), as a single "optimal" solution does not exist across all metrics.

The paper concludes that while efficient algorithms exist for specific restricted cases (e.g., paths with energy objectives, trees with consistent weights), the general problem is intractable, necessitating heuristics for complex real-world scenarios or further restrictions on agent models.