Small and large neighborhood search for the on-demand bus routing problem: A bus stop assignment and transportation problem

This article investigates a static on-demand transportation problem in which users are picked up and dropped off at existing bus stops. Specifically, the selection of bus stops for each request, along with the bus routes, is simultaneously determined by the booking system using an optimization algorithm. We focus on service quality by lexicographically minimizing request travel time (including both walking time and time spent on the bus) and total route length. We introduce a matheuristic algorithm based on small and large neighborhood search, incorporating state-of-the-art operators and a set covering component. The algorithm is tested on a new set of instances, based on real data from New York City, which we propose as a future benchmark. On our New York City instances, this algorithm outperforms prior approaches by finding feasible solutions for all instances and reducing user ride time by more than 5%; it also performs well on related benchmark problems. Additionally, we discuss implementation details for decision-makers and practitioners.