Automated vehicles are becoming a reality. The introduction of AVs on public roads will alter the current transportation system tremendously. Expectations are that AVs will ultimately transform personal mobility from privately owned assets to an on-demand service (car pooling, ride sharing, etc. are rapidly grown in popularity). This transformation will also enhance the possibility of sharing trips, leading to Shared AVs (SAVs). Such a futuristic scenario will result in a paradigm shift in conventional mobility mentality: vehicles will be owned by transport companies and will be used to satisfy on-demand services.

The aim of this presentation is to lay foundations for fast and efficient algorithms to be used in such new driving conditions. These algorithm must solve the dial a ride problem with transfers (DARP-T), hence efficiently assigning passengers to vehicles and routes, allowing ridesharing and transfers. We have developed two integer linear models (and their `extensions'), one in continuous time and the other in discrete time, to solve the a posteriori DARP-T and test their usefulness on benchmark instances. Since the models are linear, standard branch-and-bound methods can be directly applied. Our models take into account all the aspects of the standard DARP-T and also convenient parking, service times, constraints on maximum route time-span, unserved requests, preferred arrival and departure time, and non-constant travel times. In addition, they optimize routing costs and quality of service. Our results are the starting point to validate performances of forthcoming, ad hoc metaheuristics to be used in real-life scenarios.