The Influence of Agent Models on the Complexity of Bus Routing
This work studies the complexity of several variants of bus routing, focusing on how the objective function and the models for agents'walking costs influence the problem complexity, and finds that allowing agent-specific cost models leads to hardness even on extremely limited trees such as stars.