Beyond the Vehicle Routing Problem: Design of Temporal Networks for Demand-Responsive Transport

Conventional public transportation (CPT) is composed of fixed routes and fixed timetables, usually determined via long-term planning, based on nominal demand. However, during operations, demand may greatly deviate from the nominal one, causing a mismatch between demand and supply, leading to an inefficient service. On the other hand, flexible mobility services, such as Demand-Responsive Transport (DRT), adapt bus routes to the actual user demand. However, routes are calculated by solving a Vehicle Routing Problems (VRPs), which are not as effective as CPT in terms of demand consolidation, resulting in cost inefficiency. While in CPT, consolidation is obtained by forcing users to adapt to CPT by lines, VRP adapts instead to bus routes to user demand. This work introduces an alternative approach to DRT operations: different from VRP, we design a structured network describing bus routes, allowing for complex user trips, including transfers and walking legs. This enables greater consolidation and efficiency. While network design problems are limited to static networks, we propose here an original formulation to design temporal networks, which allows structured bus routes to adapt to the observed demand. We provide a proof-of-concept of the proposed approach, and show in small-scale numerical experiments that it reduces operator cost, without excessively penalizing users, compared to the classic VRP-based solution (Code available at https://github.com/XiaoyiWu21/TN4DRT).