Overview
The study investigates the computational complexity of bus routing problems within a network environment, focusing on how different objective functions and agent walking cost models influence this complexity. Bus routing involves planning optimal routes for a bus to transport several agents, each needing to travel from a specific starting point to a destination. Key factors considered in route planning include agents' costs for reaching bus stops, their travel time, and the energy consumption of the buses.
Research Context
Bus routing problems are characterized by the need to efficiently serve multiple agents, each with unique travel requirements. The complexity of these problems can vary significantly based on the underlying network structure and the specific assumptions made about agent behavior and cost calculations. This research specifically examines the influence of agent cost models and objective functions on the problem's computational tractability.
Approach
The researchers analyzed various problem variants, systematically exploring the impact of objective functions and agent walking cost models. They initially observed the complexity of the problem on general networks, noting that even the most straightforward agent cost model leads to computational hardness. Subsequently, the investigation shifted to networks exhibiting a tree structure, which represents a more constrained topological environment. The primary analytical method involved assessing classical NP-hardness and parameterized intractability, particularly for the natural parameter $k$, representing the number of bus stops.
Findings
- Even the simplest agent cost model results in computational hardness on general networks.
- Introducing agent-specific cost models leads to hardness, even on highly constrained tree structures such as star networks.
- Consistent agent models, where agents differ only in their starting points and destinations, can simplify the problem in certain cases.
- Allowing agents the option to choose between using the bus and walking directly to their destination can substantially increase the problem's complexity.
- A significant portion of the identified hardness results extends beyond classical NP-hardness to include parameterized intractability, specifically concerning the number of bus stops ($k$) as a parameter.