A routing and scheduling problem in operating integrated mobility systems

Abstract

A trend towards Mobility as a Service (MaaS) is observed in many Western countries. MaaS is a recent technological advancement that transforms mobility systems into more flexible and efficient ones by integrating different transportation modes. In this research, the focus lies on the integration of timetabled public transport (PT) and dial-a-ride (DAR) services allowing passengers to travel by a combination of these two modes. Users submit a single transportation request for their entire trip, indicating their service requirements (e.g., time windows, maximum trip duration,. . .). The routes and schedules of the demand-responsive DAR services are planned by a mobility provider. They must be aligned to the public transport timetables to allow efficient transfers and take into account the users' service level by avoiding large detours and long waiting times during transfers. From the perspective of the mobility provider, the exploitation of such an integrated mobility system leads to challenging routing and scheduling problems on the operational level. The ultimate aim of the mobility provider to is generate efficient real-time solutions in response to all user requests by optimally combining and aligning the available transport modes with each other while minimizing the operational costs and the total trip times of the users. From the users' perspective, it is important that the proposed solutions are of high quality (e.g., attractive travel times) and reliable (e.g., low risk of missed transfers). This quality experience is essential to guarantee a successful implementation of the MaaS concept on a large scale. Therefore, the main goal of this research is to develop a quick and efficient planning algorithm for integrated mobility systems that responds to all the aforementioned aspects, eventually enabling real-life systems to operate in the most efficient and user-oriented way. However, the academic literature lacks insights in (1) how the operational planning of an integrated mobility system should be designed such that operational efficiency and service quality are optimally balanced and (2) how this planning can dynamically be revised in case of unexpected events, such as delays on the PT network causing missed transfers. In this talk, the static and deterministic case of the corresponding routing and scheduling problem will first be modelled through a mixed-integer linear programming (MILP) formulation. Second, the design of a Large Neighborhood Search (LNS) framework for this problem will be discussed. To incorporate the trade-off between the operational costs and service level in the optimization process, a tailored scheduling subprocedure is presented which minimizes the sum of the users' trip durations for a given route. We will discuss experiments on small-scale artificial instances by comparing the results obtained from the LNS metaheuristic with the optimal solutions. Finally, the next steps in this research (e.g. incorporation of dynamic events, risk reduction in initial planning) will be discussed.