The real-time on-demand bus routing problem: What is the cost of dynamic requests?

The real-time on-demand bus routing problem (ODBRP) supports the online routing of buses in a large-scale ride-sharing system. Given are a set of buses with fixed capacity, a set of bus stations and a set of transportation requests, only part of which are known before the planning horizon. A request consists of a set of possible departure and arrival stations, as well as an earliest departure and latest arrival time. The aim is to (1) assign each passenger to a departure and arrival bus station and (2) develop a set of bus routes to fulfill each request within its time window while minimizing the total user ride time. Including the possibility for requests to be issued after the start of the planning horizon, i.e., when buses have already started servicing other requests, requires a dynamic re-optimization of a partially executed solution. Compared to the case in which all requests are known beforehand, the solution quality, expressed as the total user ride time, is expected to decline. This decline in objective function value can be seen as the ”cost” of the dynamic requests. In this paper, we introduce the real-time ODBRP as a new optimization problem and present a heuristic to deal with dynamic requests. In addition, an extensive set of experiments allows us to conclude that dynamic requests indeed lead to higher user ride times, especially for passengers who submit their request at the last minute. Passengers are therefore encouraged to send their request well in advance, as this results in lower and more stable user ride times, higher customer satisfaction, and higher revenues for the operating on-demand bus company.