WP1 - Plénière 5 / Plenary 5

Public transit systems are critical to the health and prosperity of cities and their populations. Yet, in many cities they face challenges related to government funding and decreased ridership. Vehicle-based transit systems can be placed on a spectrum. On one end are door-to-door, dial-a-ride-type systems that provide custom service to individual riders on-demand. While convenient for riders, such systems are expensive and difficult to scale. On the other end are fixed line bus systems that visit a fixed set of stops according to a pre-defined schedule to provide standardized service to many riders at once. While more economical and scalable, rider adoption depends in part on whether riders find such a service convenient. We consider a Demand Adaptive System that combines features of both systems. Namely, while a bus visits a fixed set of stops according to a pre-defined schedule, it can also take detours to provide custom service to individualized requests when they arise.

We study stochastic and dynamic optimization-based approaches to derive tactical and operational plans for a single bus line in such a system. For tactical planning, we consider the problem of determining the set of fixed stops on a bus line that minimize a weighted combination of vehicle transportation and passenger out-of-route costs. Further, the chosen set of stops must enable the service of a pre-defined percentage of uncertain passenger demand. We model this problem as a variant of the Stochastic Traveling Salesman Problem and present exact and heuristic algorithms for solving instances of this model. We demonstrate the effectiveness of both algorithms on adaptations of benchmark instances from the TSP literature to this problem. For operational planning, we consider the online optimization problem of determining the customer requests involving non-fixed stops a bus should serve as they arrive over time. Requests are chosen to maximize ridership while ensuring the bus schedule is still observed. We model this problem as a Markov Decision Process and present multiple parallelizable look ahead-type rolling horizon approaches to provide near real-time responses to individual requests. We demonstrate the effectiveness of these approaches on instances derived from the operations of a transportation provider in Munich, Germany.