Eleanor Roosevelt

Khalil Gibran

Fabio Antonialli

Naouress Fatfouta

Lara Qasim

Islam Abdin

Tasneem Bani Mustafa

Sarra Fakhfakh

Bruna Cavazza

Shaohua Yu

Haythem Selmi

Selmen Boubaker

Hichem Benbitour

Gustavo Santamaria

Fardin Dashty

Sami Ozarik

Cansu Altintas

Vincent Karels

José Van Dijk-Kok

George Abo Naser

Ghazi Al Shammat

Reem Moamar

Radia Saffa

Nataliya Storozhylova

Faek Houssin

Ekaterina Arafailova

Matthieu David

Marek Rozniak

Abood Mourad

Keywords: urban mobility, synchronization, passenger and freight transportation, ridesharing, autonomous vehicles, optimization, uncertainty, heuristic approaches

The future belongs to those who believe in the beauty of their dreams.

Résumé

Avec l'augmentation progressive de la population dans les grandes villes, comme Paris, nous prévoyons d'ici 2050 une augmentation de 50% du trafic routier. En considérant les embouteillages et la pollution que cette augmentation va générer, on voit clairement la nécessité de nouveaux systèmes de mobilité plus durables, comme le covoiturage, ou plus généralement toute la mobilité partagée. En parlant de mobilité partagée, ce n'est pas seulement le partage de trajets de personnes qui ont le même itinéraire au même temps, elle inclut aussi les marchandises. Cette thèse aborde le défi de la synchronisation des flux de passagers et de marchandises dans les systèmes de mobilité urbaine et elle vise à développer des méthodes d'optimisation pour que cette synchronisation dans la mobilité partagée soit réalisable. Plus précisément, elle aborde les questions de recherche suivantes:

Q1: Quelles sont les variantes des systèmes de mobilité partagée et comment les optimiser? Q2: Comment synchroniser les déplacements de personnes et quels gains cette synchronisation peut-elle générer? Q3: Comment combiner les flux de passagers et de fret et quels sont les effets de l'incertitude sur ces systèmes? Dans un premier temps, nous étudions les différentes variantes des systèmes de mobilité partagée et nous les classifions en fonction de leurs modèles, caractéristiques, approches de résolution et contextes d'application. En nous basant sur cette revue de littérature, nous identifions deux problèmes de mobilité partagée, que nous considérons en détails dans cette thèse et nous développons des méthodes d'optimisation pour les résoudre. Pour synchroniser les flux de passagers, nous étudions un modèle de covoiturage en utilisant les véhicules autonomes, personnels et partagés, et des points de rencontre où la synchronisation entre passagers peut avoir lieu. Pour cela, une méthode heuristique en deux phases est proposée et une étude de cas sur la ville de New York est présentée. Ensuite, nous développons un modèle d'optimisation qui combine les flux de passagers et de marchandises dans une zone urbaine. Le but de ce modèle est d'utiliser les capacités disponibles sur une ligne de transport fixe pour transporter les passagers et des robots transportant des petits colis à leurs destinations finales en considérant que la demande de passagers est stochastique. Les résultats obtenus montrent que les solutions proposées par ces deux modèles peuvent conduire à une meilleure utilisation des systèmes de transport dans les régions urbaines.

Mots-clés: mobilité urbaine, synchronisation, transport de passagers et de marchandises, covoiturage, véhicules autonomes, optimisation, incertitude, méthodes heuristiques.

Chapter 1

Introduction

The aim of this chapter is to introduce the research context of the thesis, the motivation behind it, and the key research questions addressed. The main challenges that are limiting the deployment of new urban mobility services are investigated and the potential benefits of shared mobility concepts are highlighted. The chapter also introduces the research project where the thesis takes place along with the industrial partners. Finally, an overview of the thesis, introducing the objective and the main contribution of each chapter, is given.

Motivation and research context

Since the birth of the first civilized community, a set of basic human activities has emerged. In order to fulfill these activities, the need for transportation has arose and evolved over the years. Transportation can be defined as the continuous movement of people and goods from one place to another. This movement, which was mainly based on human or animal-powered transport, has witnessed a major breakthrough especially after the industrial revolution in the second half of the 18th century. With the invention of steam engines, rail transport, and aerial transport some years later, new ways for transporting both people and goods have emerged. These inventions provided more efficient and reliable means of transportation and, at the same time, played an essential role in the development of modern societies. With the opportunities that were generated by these inventions, a large portion of the world's population has been gradually moving from rural to urban areas resulting in very high urbanization rates nowadays. This considerably growing population in urban areas, which is expected to represent more than 70% of the world's population by 2050 (United Nations, 2017), is also associated with a swift growth in people demand for goods and transportation. According to OECD, 2017, the demand for urban travel will grow, with up to 95% in 2050 compared to that of 2015, reaching more than 50 000 billion passenger-kilometres in that year (Figure 1.1a).

Relatively, mobility by car will continue to grow leading to more cars driving on already congested roads. The demand for freight, represented by vehicle-kilometres in Figure 1.1b, is also expected to increase yielding additional loads to road traffic in urban areas. In addition to traffic issues, the emissions from road transport, both freight and passenger, will lead to increasingly inflated levels of pollution in big cities. Indeed, as cities become more populated, the daily demand for goods and transportation, and thus CO 2 emissions, increases giving rise to many challenges that need to be faced by local authorities and transport operators. Besides increasing demand for transport, the technological advances and innovations represent another important factor which is generating both opportunities and challenges for transportation systems [START_REF] Savelsbergh | 50th Anniversary Invited Article-City Logistics: Challenges and Opportunities[END_REF]. These

Motivation and research context

innovations have the potential to enhance the transportation service provided, but might require new regulations and infrastructures to adapt their deployment.

That said, an increasing amount of research has been directed towards either improving the existing transportation systems or introducing new, and more sustainable, ones that can answer to the rising challenges while taking into account the economical, social, and environmental concerns. These new systems must, on the one hand, provide a more efficient choice of transport mode that can adapt new technologies and services and, on the other hand, limit emissions and energy consumption. One of these innovative ideas is to synchronize people and freight transportation flows, referred to as shared mobility, so that their demands are met using less transportation resources. The concept of shared mobility refers to the shared use of available transportation resources [START_REF] Laporte | Shared mobility systems[END_REF]. With the emergence of many new shared mobility services (e.g. Vélib, Autolib and others), shared mobility has attracted the attention of the operations research community in recent years.

This is due to the set of benefits that can be obtained from applying this sharing concept in real-life transportation systems. As the concept of shared mobility contains a wide variety of systems, we propose to classify these systems in two main categories (Figure 1.2). In the first category, we consider shared mobility systems where people, with similar itineraries and time schedules, share their daily trips so that their travel costs are reduced. On the other hand, shared mobility systems in the second category are those where the transportation of passengers and freight is combined. In both cases, the synchronization of different transportation streams is a critical task that need to be addressed carefully in order to achieve the intended service performance. The aim of this thesis is thus to study shared mobility systems whether they are referred to people sharing their daily trips or to combining people and freight transportation. More precisely, we address the following research objective:

Research objective: Develop efficient models and optimization approaches for synchronizing people and freight flows in urban mobility systems.

In order to achieve the aforementioned objective, a set of research questions are identified and addressed in the corresponding chapters of the thesis. The research questions are formulated as follows:

Research question 1: What are the different variants of shared mobility systems and what methods are used to optimize them?

Research question 2: How can people trips be synchronized in a ridesharing system with autonomous vehicles and what gains can this synchronization yield?

Research question 3: How can people and freight flows be combined and what are the impacts of stochastic passenger demands on planning such a combined system? A more detailed overview on how these research questions are addressed in each one of the chapters is given in Section 1.3.

The Anthropolis research chair

This thesis is conducted as part of the Anthropolis research chair which is a research project that aims at developing human-centered approaches for urban mobility. The Anthropolis chair was established in 2015 thanks to the collaboration between the Institute for Technological Research SystemX (IRT-SystemX) and the Industrial Engineering Laboratory (LGI) of Ecole CentraleSupélec.

In addition, the Anthropolis chair is partially funded by five industrial partners which are: ALSTOM, ENGIE, Renault Group, RATP and SNCF. These partners are important actors of urban mobility in the greater Paris region. On their route towards an urban mobility transformation that meets the evolving transportation needs of inhabitants and the emerging technological advances, the industrial partners have several challenges that need to be considered. This justifies the industrial interest in the Anthropolis chair which aims to give a better understanding of these challenges and suggest solutions that can help the partners in the development of future urban mobility systems. For example, the future deployment of autonomous mobility services and their implication for people transportation as well as last-mile deliveries is one of the major points of industrial interest that we consider in this thesis (as we will see in the following chapters).

The research carried out within the Anthropolis chair can be summarized in three main research topics. These are:

• Topic 1 : User research, a traveler-centered approach of urban mobility issues.

• Topic 2 : Disruptive technologies and innovation, a technological watch of urban mobility.

• Topic 3 : Impact assessment, a measure of the impact of new solutions on business models and urban systems.

As part of the third research topic (Topic 3 ), this thesis aims at being a bridge between the industrial needs and the real-life application of new shared mobility systems in urban areas. This is done by (i) bringing insights that can help the industrial partners to tackle the increasing demand for transportation and innovation challenges in their future shared mobility systems, and (ii) developing new tools (i.e. models and optimization approaches) to operate them efficiently.

Overview of the thesis

In chapter 2, we review different variants of the shared mobility problem in which either (i) travelers share their rides for the sake of reducing travel costs, usually called ridesharing problem, or (ii) passengers and freight transportation flows are combined. These involve real-time shared mobility systems, shared autonomous mobility and crowd-sourced logistics.

We classify these variants according to their models, features, solution approaches and application context. We observe that although their application contexts might be different, these variants can share similar modeling features, formulations and solution approaches.

We then provide a comprehensive overview of the recently published papers and case studies and we summarize their different models, features and objectives. Based on this review, we identify two shared mobility problems, which we study further in this thesis, and we develop models and optimization approaches for solving them.

In chapter 3, we study a ridesharing system where individually-owned and on-demand autonomous vehicles (AVs) are used for serving passengers and the concept of meeting points is used for synchronizing their trips. We then develop a two-phase method (a pre-processing algorithm and a matching optimization problem) for assessing the sharing potential of different AV ownership models and we evaluate their matching rates and potentially saved vehicle kilometers. We analyze these ownership and sharing scenarios on a case study for New York City. The results demonstrate that sharing AV trips has the potential of increasing the system-wide matching rate as well as saving up to 23% of the overall traveled distance.

In chapter 4, we present a system that integrates freight deliveries to a scheduled line for people transportation where the aim is to use the underused capacity to transport freight simultaneously with passengers. We assume passenger demand, and thus the number of available places for transporting freight, to be stochastic. We then model this problem as a two-stage stochastic problem and we provide a MIP formulation and a sample average approximation (SAA) method along with an Adaptive Large Neighborhood Search (ALNS) algorithm to solve the stochastic optimization problem. In addition, we perform a computational study to evaluate the proposed approach as well as the impacts of stochastic passengers demand on such integrated system. The results show that the proposed heuristic approach can return solutions that are within 0.6% of the optimal solutions. The analysis also revealed that an average of 3.3% extra costs can be observed when stochastic passengers demand is realized which reflect the effect of uncertainty on the total transportation costs.

In chapter 5, we summarize the key findings and contributions of the thesis, highlight the main challenges facing shared mobility systems, and suggest potential directions for future research.

To help clarity, Table 1.1 summarizes the overview of the thesis. Column "Context" indicates the considered research context, "Methodology" gives the type of algorithm used to solve the considered problem, "Stochastic" indicates whether uncertainty is considered in the problem, and finally "Research questions" indicates which specific research questions is addressed in the corresponding chapter. The chapters of the thesis are based on the following papers: Chapter 2

Shared mobility systems

The rise of research into shared mobility systems reflects emerging challenges, such as rising traffic congestion, rising oil prices and rising environmental concern. The operations research community has turned towards more sharable and sustainable systems of transportation.

Shared mobility systems can be collapsed into two main streams: those where people share rides and those where parcel transportation and people transportation are combined. This chapter sets out to review recent research in this area, including different optimization approaches, and to provide guidelines and promising directions for future research. It makes a distinction between prearranged and real-time problem settings and their methods of solution, and also gives an overview of real-case applications relevant to the research area.

Introduction

The concept of shared mobility has gained popularity in recent years, attracting attention from the operations research community, especially after the world of transportation witnessed a mini-revolution with the launch of shared mobility services like Vélib, Autolib, Zipcar, Car2Go and others. Emerging challenges, such as growing levels of traffic congestion and limited oil supplies with their increasing prices, together with the rising environmental concerns have pushed research towards more sharable and sustainable systems of transportation. Applying this sharing concept in real-life transportation systems is expected to afford a set of potential benefits, whether for people sharing their daily trips or for combined passenger and freight transportation.

Shared mobility comes with many benefits, such as decreasing congestion and pollution levels and reducing transportation costs for both people and goods, but it also has challenges that are holding back widespread adoption. [START_REF] Furuhata | Ridesharing: The state-of-the-art and future directions[END_REF] identified three major challenges for agencies providing shared rides to passengers. These are: designing attractive mechanisms, proper ride arrangement, and building trust among unknown passengers in online systems. Thus, in order to be adopted more widely, a shared mobility service should be easy to establish and provide a safe, efficient and economical trip. As such, it should be able to compete with the immediate access to door-to-door transportation that private cars provide [START_REF] Agatz | Optimization for dynamic ride-sharing: A review[END_REF].

Another important aspect is the emergence of autonomous mobility services and their potential application to existing shared mobility systems. Fully autonomous vehicles are expected to reduce traveling costs and provide a safer and more comfortable and sustainable mode of transportation [START_REF] Meyer | Autonomous vehicles: The next jump in accessibilities?[END_REF]. If those assumptions translate to reality, autonomous vehicles will dramatically change the urban landscape, and if they can be used as a shared transportation service, they could reshape the future of shared mobility systems [START_REF] Chen | Operations of a shared, autonomous, electric vehicle fleet: Implications of vehicle & charging infrastructure decisions[END_REF].

From a logistics system perspective, swiftly-growing urbanization rates, and consequently the potential change in people's demands for goods in urban areas, justify the need to develop new urban logistics systems. These new systems should ensure efficient urban mobility, not just for people, but for goods as well [START_REF] Fatnassi | Planning and operating a shared goods and passengers on-demand rapid transit system for sustainable citylogistics[END_REF]. Thus, much of the recent research has focused on increasing the sustainability of mobility systems.

Projects have focused on improving existing transportation systems and service quality and designing new systems that can offer a more sustainable and ecological approach and thus contend with rising urban challenges. One innovative idea is to combine individual freight and passenger transportation streams in an urban area, prompting efforts to study the efficiency gains made when people and goods share rides and identify the potential challenges facing this combination.

The increasing need for new technologies and services that support the development of sustainable and innovative shared mobility systems is coupled with the need to develop new operations research models and optimization approaches. An increasing amount of research is thus directed towards building new models and methods that can efficiently operate these systems. Reviewing the literature on shared mobility systems for passenger transportation, [START_REF] Furuhata | Ridesharing: The state-of-the-art and future directions[END_REF] surveyed the existing ridesharing systems and identified their key challenges. The paper also classified these systems according to their different features, matching search strategies, pricing methods and target demand segments. [START_REF] Agatz | Optimization for dynamic ride-sharing: A review[END_REF] surveyed the different operations research models that allow travelers (drivers and riders) to be matched in real-time, and reviewed the optimization challenges that arise in such realtime systems and the methods used to operate them. A more recent survey by [START_REF] Molenbruch | Typology and literature review for dial-a-ride problems[END_REF] reviewed the literature on demand-responsive ridesharing systems, called dial-aride problems (DARPs). The authors introduce a taxonomy classifying the reviewed papers according to their real-time characteristics, service design, and solution methods. Similarly, [START_REF] Ho | A survey of dial-a-ride problems: Literature review and recent developments[END_REF] presented an up-to-date review of recent studies on dial-a-ride problems (DARPs) with their different variants and solution methodologies. Moreover, the paper introduced references to benchmark instances, investigates their application areas, and suggests directions for future research. City logistics is a major field of innovation in freight transportation, so the rising importance of sharing aspects in last mile distribution makes it equally important to investigate the latest developments in city logistics. [START_REF] Savelsbergh | 50th Anniversary Invited Article-City Logistics: Challenges and Opportunities[END_REF] reviewed the most recent trends and challenges in city logistics and identified opportunities for research. Sampaio [START_REF] Oliveira | Crowd-based City Logistics[END_REF] studied the crowd-sourcing logistics model, which aims to use available capacity on trips already taking place, called the crowd, to deliver goods in urban areas. The paper reviewed the latest developments in crowd logistics along with their different features, applications, deployment issues and impacts on city logistics.

Whereas these reviews on shared mobility have focused on either people or freight transportation considering one variant of the problem (dynamic ridesharing systems and carpooling services [START_REF] Agatz | Optimization for dynamic ride-sharing: A review[END_REF][START_REF] Furuhata | Ridesharing: The state-of-the-art and future directions[END_REF], DARPs [START_REF] Molenbruch | Typology and literature review for dial-a-ride problems[END_REF][START_REF] Ho | A survey of dial-a-ride problems: Literature review and recent developments[END_REF], city logistics [START_REF] Savelsbergh | 50th Anniversary Invited Article-City Logistics: Challenges and Opportunities[END_REF], crowd-logistics (Sampaio [START_REF] Oliveira | Crowd-based City Logistics[END_REF] and other variants), here we review different variants of the shared mobility problem for both people and goods. We thus focus on shared mobility systems where (i) travelers share their rides to reduce travel costs, usually called ridesharing systems, or where (ii) passenger and freight transportation are combined. We find that although the different variants can share similar modeling features, formulations and solution approaches, their context of application varies. For example, A DARP-based formulation can be used to model both types of shared mobility systems, but some of its features can vary depending on the context in which it is applied. We thus study these variants according to their modeling choices, defining features and solution methods, and we identify their common and varying characteristics. This survey brings several key contributions: (1) a comprehensive overview of recent papers on shared mobility for transportation of people and goods, (2) an extensive study of the different variants of the problem based on their application contexts, models, features and solution approaches, (3) an overview of the latest trends in research on real-time shared mobility systems, shared autonomous mobility and crowd-based logistics, (4) a tabulated overview for each section summarizing the reviewed papers and their problem characteristics and solution methods, and (5) a review of recent shared mobility case studies analyzed and classified according to their scope and the approaches used.

This chapter is organized as follows. In section 2.2, we present the different variants of the shared mobility problem, study their different features and modeling approaches, and explain how we build on them. In section 2.3, we focus on mobility systems that allow people to share their rides, including those with real-time settings and those that consider shared autonomous vehicles. In section 2.4, we investigate the latest developments in city logistics and go on to review the integrated passenger and freight transportation problem with its solution methods and applications. This review of the literature on ridesharing and combined systems is split into two separate sections to facilitate the organization of the survey and help readers easily identify the parts of the literature that interest them most.

In addition, each section comes with a set of case studies on the relevant shared mobility topics. Finally, in section 2.5, we summarize the key findings and suggest directions for future research.

Shared mobility problems

In this section, the different variants of shared mobility systems are reviewed and classified according to their application context (section 2.2.1). Then, an extensive review of their modeling features (section 2.2.2), objectives (section 2.2.3) and solution approaches

(2.2.4) is provided.

Background

As introduced earlier, the concept of shared mobility applies not just to people transportation but also to combined people and freight transportation to make better use of available transportation resources. The literature has introduced a number of variants of the shared mobility problem for people and freight transportation (Figure 2.1). Shared mobility systems for people transportation aim to minimize the number of vacant seats in vehicles in order to reduce the number of used vehicles, and thus traffic congestion and pollution. This can be achieved using a number of concepts, such as; ridesharing, carpooling, vanpooling, car-sharing, dial-a-ride and others. Ridesharing allows people with similar itineraries and time schedules to share a vehicle for a trip so that each person's travel costs (i.e. fuel, toll, parking expenses, etc.) are reduced [START_REF] Furuhata | Ridesharing: The state-of-the-art and future directions[END_REF].

Based on this definition, we use the term "ridesharing" throughout the thesis to represent share their trips and thus enhance their travel experience [START_REF] Agatz | Optimization for dynamic ride-sharing: A review[END_REF]. Planning for rideshared trips can be categorized into 'prearranged ', or 'static' ridesharing, and 'dynamic' ridesharing. In prearranged ridesharing, travelers' demand (drivers and riders) is known beforehand (i.e. travelers' origins, destinations, and departure and arrival times are given in advance) and can thus be used to plan their shared trips. Such prearranged services are mainly used for planning regular commuter trips as well as shared long-distance trips (e.g.

inter-city trips). However, long-distance trips generally have more flexible time schedules than commuting trips. Dynamic ridesharing focuses on matching drivers and riders onthe-fly. In other words, new drivers, offering rides, and riders, requesting rides, can enter and leave the system at any time, and the system then tries to match their trips at short notice (or even en-route). In their review of dynamic ridesharing systems, [START_REF] Agatz | Optimization for dynamic ride-sharing: A review[END_REF] focused on the optimization problem of efficiently matching drivers and passengers.

This ride-matching problem has two steps. First, it determines efficient vehicle routes, and then it assigns passengers to those vehicles taking into consideration the conflicting objectives of maximizing the number of matched travelers and minimizing the operation cost and passenger inconvenience (these real-time systems are further explored in section 2.3.2).

One variant of the ridesharing problem is called the carpooling problem. Carpooling was first introduced by large companies in an effort to encourage their employees to pick up colleagues while driving to/from work. The idea was to minimize the number of cars traveling to their sites every day [START_REF] Baldacci | An Exact Method for the Car Pooling Problem Based on Lagrangean Column Generation[END_REF]. Carpooling is generally used for commuting but has become increasingly popular for longer one-off journeys. The carpooling problem aims to determine the subsets of travelers that will share the same trip and the paths these shared trips should follow in order to maximize sharing and minimize travel costs.

In order to increase the flexibility of carpooling services, which are usually prearranged, the concept of flexible carpooling has been introduced [START_REF] Shaheen | Casual carpooling in the San Francisco Bay Area: Understanding user characteristics, behaviors, and motivations[END_REF]. Flexible carpooling, also called casual carpooling or slugging, is a semi-organized service in which destination, meeting point and departure times are all known in advance among potential participants. The main difference is that rideshares are formed spontaneously at the meeting point on a first-come first-served basis [START_REF] Chan | Ridesharing in North America: Past, Present, and Future[END_REF]. This enhanced flexibility opened the door to deploying new carpooling services, not only for daily commutes but for long-distance trips as well (see SlugLines, SmartSlug and KangaRide for example). Along similar lines, Kaan and Olinick, 2013 consider the vanpooling problem with its optimization models and solution algorithms. In this problem, commuters in the vanpool drive to an intermediate location, called a park-and-ride location, and then take a van and ride together to the target destination. Car/vanpooling, which can be operated on daily or long-term bases [START_REF] Calvo | A distributed geographic information system for the daily car pooling problem[END_REF], provide regular and cost efficient means of transportation, they do not accommodate unexpected changes of schedule. By contrast, the dial-a-ride (DARP) provides shared trips between any origin and destination in response to advanced passenger requests within a specific area (see [START_REF] Molenbruch | Typology and literature review for dial-a-ride problems[END_REF][START_REF] Ho | A survey of dial-a-ride problems: Literature review and recent developments[END_REF] for recent review). The DARP models a demand-responsive transportation mode in which the aim is to define a set of routes in order to satisfy passenger requests at minimized costs [START_REF] Masson | The dial-a-ride problem with transfers[END_REF][START_REF] Ritzinger | A survey on dynamic and stochastic vehicle routing problems[END_REF]. Each request consists of transporting a passenger from his/her origin location to his/her destination location where passengers with similar route and time preferences can share the same vehicle as long as there is capacity.

As such, solving the DARP is about minimizing the total travel distance, and thereby travel time, while respecting rider-specified time restrictions and any vehicle restriction constraints (more problem features and objectives are discussed in sections 2.2.2 and 2.2.3 respectively).

These demand-responsive systems often focus on providing service to people with reduced mobility (e.g. elderly, handicapped etc.). The main difference between a DARP and a dynamic ridesharing problem is that a driver in the DARP can provide service to a wide set of passengers, as the drivers in this case are part of the service, and thus have less restrictions regarding route and time. In contrast, a driver in a dynamic ridesharing context can only provide service to passengers with similar route and time schedules to the driver [START_REF] Gu | Algorithmic analysis for ridesharing of personal vehicles[END_REF]. In other words, in DARP, all drivers are professional and typically operate out of one or more depots, whereas in dynamic ridesharing each driver is often an individual who has a specific origin and destination and may have preferences to be considered (like a maximum detour time, maximum number of stops, etc.).

Another variant of the ridesharing problem is the shared-taxi problem introduced by Hosni et al., 2014 as a multi-vehicle dynamic DARP. In the shared-taxi problem, passengers indicate their desired pickup and drop-off locations, their earliest/latest acceptable pickup/drop-off time, and a maximum trip time. Solving the shared-taxi problem aims to optimally assign passengers to taxis and determine the optimal route for each taxi, which means this problem shares the same characteristics, such as demand-responsiveness, as the DARP. However, the main difference is that most shared-taxi services aim to minimize the response time to passenger requests whereas dial-a-ride systems aim to minimize vehicle operating cost by reducing the number of vehicles used to serve given passenger demands [START_REF] Jung | Dynamic Shared-Taxi Dispatch Algorithm with Hybrid-Simulated Annealing[END_REF]. When considering ridesharing variants, it is important to differentiate ridesharing from carsharing, which is a different concept. Carsharing is a car rental service in which people who are interested in making only occasional use of a vehicle can rent cars for short periods of time [START_REF] Agatz | Optimization for dynamic ride-sharing: A review[END_REF]. Although carsharing shares the aim of reducing car usage and increasing mobility with ridesharing, the optimization challenges that arise in both systems are different. Those challenges include, determining depot locations and assigning and redistributing vehicles among these depots. Although the carsharing concept allows people to occasionally use a network of vehicles for short periods of time, they do not necessarily share their trips with other travelers, which rules carsharing systems outside the scope of this review. Here we use the different variants of ridesharing introduced so far to classify recent studies on shared mobility systems for people transportation (see section

2.3).

On the other hand, combining passenger and freight flows has the potential to improve the performance of existing transportation services as their needs can be satisfied with fewer resources [START_REF] Trentini | Optimization of a city logistics transportation system with mixed passengers and goods[END_REF]. In this kind of combined delivery system, spare capacity in public transport systems can be used for retail store replenishment, or taxis can move or deliver freight when carrying a passenger or during idle time. In an integrated system, when transporting freight, we need to decide whether to use a pure freight or people transportation network or a combination of the two [START_REF] Savelsbergh | 50th Anniversary Invited Article-City Logistics: Challenges and Opportunities[END_REF].

This choice depends on the origin location, destination, and due time of freight. In this chapter, the focus is on systems in which people and freight transportation are combined. [START_REF] Li | The Share-A-Ride Problem: People and parcels sharing taxis[END_REF] introduced the share-a-ride problem (SARP) in which people and parcels are handled in an integrated way by the same taxi network. In this problem, a number of taxis drive around in an urban area to serve passenger requests but can also deliver some freight (parcels), from their origins to their final destinations, as long as these deliveries do not add significant extra time to their passengers' trips. Further, Ghilas et al., 2016c explored an integrated solution for simultaneous passenger and freight transportation so that fewer vehicles are required. In their problem, a set of pickup and delivery vehicles is used to serve a set of parcel delivery requests where a part of the delivery process is Chapter 2. Shared mobility systems carried out on a scheduled passenger transportation service. Trentini et al., 2015 introduced another integrated system in which goods are transported in city buses, which have some spare capacity, from a distribution center to a set of bus stops before they can be delivered to final customers by a fleet of near-zero emissions city freighters.

Increasing interest in such combined systems has led to the concept of crowd-sourced delivery. Crowd-sourcing allows activities that were traditionally performed by a certain agent or company to be outsourced to a large pool of individuals [START_REF] Goetting | Crowd-shipping: Is crowdsourced the secret recipe for delivery in the future?[END_REF], which aligns it to the concept of sharing economy. Crowd-sourced delivery, or crowd-shipping, is based on sharing excess and underused assets, which here translates as using excess capacity on journeys already taking place in order to make deliveries.

As such, crowd-sourced delivery could revolutionize delivery by increasing operational efficiency and reducing transportation costs. The problem of combining passenger and freight transportation shares many features with the ridesharing problem where only passengers are considered. However, it has some complicating features as well, such as transfers, synchronization, capacity constraints, multiple echelons, etc. [START_REF] Savelsbergh | 50th Anniversary Invited Article-City Logistics: Challenges and Opportunities[END_REF]. The key to successfully combining passenger and freight transportation is to ensure there is no significant negative effect on people when goods are transported or delivered during their journey. We explore and discuss these combined systems in section 2.4.

Modeling and features

In the shared mobility problem, a set of transportation requests, representing passengers or passengers-plus-goods, need to go from their origins to their destinations while satisfying certain criteria and respecting certain service specifications. The service provider receives these different requests and then arranges with its available transportation resources (vehicles, car parks, drivers etc.) for the delivery process. This planning of shared trips is one of the main tasks in shared mobility. In this problem, the service is shared in the sense that multiple requests might be serviced using the same resource (e.g. vehicle) at the same time. In order to establish this shared service, a set of features and constraints should be considered. Shared mobility problems are usually modeled using different vehicle routing problem (VRP) formulations that represent these features as a set of additional constraints characterizing each variant of the problem. Many of these features can be found in both ridesharing systems and systems combining passenger and freight transportation, but other features can relate to either ridesharing systems or combined systems, but not both. In the following, we summarize the different types of features and constraints reported in the literature for the shared mobility problem. Furthermore, we identify problem variants that consider each type of constraint discussed in order to get a clear picture of these variants and their common and different characteristics.

Routing constraints (RC):

In shared mobility systems, every request needs to be transported from its origin to its destination, and the origin location has to be visited first. This feature applies to both passengers and goods but can have some variations. For example, in some ridesharing applications, a passenger can be picked up or dropped off at an intermediate location, usually called meeting point, which can lead to shorter detours (Stiglic et al., 2016a). Another example is found in multi-echelon transportation systems where goods are transported through a scheduled line to a public transport station and then delivered by vehicle to their final destination (Ghilas et al., 2016b Furthermore, in demand-responsive transportation systems (including DARP and sharedtaxi systems) and many logistics systems in which a fleet of vehicles is located at specific locations (depots) and ready for service, there is an additional constraint imposed on the route each vehicle will follow: each vehicle should return to one of the depots when its trip is finished. In some simplified problem settings, a vehicle might have to return to the same depot from which it started its trip. Moreover, any shared mobility model must ensure each vehicle reaches and leaves a corresponding location (request origin or destination, depot, intermediate meeting point or a public transport station). This constraint ensures conservation of flow, and is very common in shared mobility problems. In some combined systems, passenger requests are given higher priority when building routes to serve both passengers and goods [START_REF] Li | The Share-A-Ride Problem: People and parcels sharing taxis[END_REF]. The routes are first constructed based on passenger requests, then freight requests are only inserted when passenger trips are not significantly affected.

Routing constraints are usually considered hard constraints, because violating them might lead to detached vehicle routes or a request being picked up but not delivered to destination.

Thus, these constraints need to be strictly respected when modeling and solving a shared mobility problem.

Time constraints (TC):

Besides indicating where a transportation request needs to be picked up and where it should be transported to, a shared trip must also indicate when this process can take place. This is usually done by associating a time window with each transportation request, whether for a passenger or freight. In ridesharing systems, this time window is usually given by each passenger indicating the earliest departure time from his/her origin and the latest arrival time at his/her destination. Thus, in order for a passenger to participate in a shared trip, he/she should be picked up at origin and dropped off at destination within the time window he/she has specified (Stiglic et al., 2016a). Like passenger requests, freight delivery requests may also be associated with a time window. In some cases, two time windows are used to represent these time restrictions: a pickup time window, indicating when a request should be picked up, and a drop-off time window, indicating when it should be delivered (Ghilas et al., 2016c).

In addition, there could be added restrictions on the duration of the shared trips. In most ridesharing systems, a set of drivers, offering rides, and riders, looking for rides, are matched to share their trips. In order to accommodate the riders, the driver might have to make a detour from his original itinerary and make some extra stops [START_REF] Furuhata | Ridesharing: The state-of-the-art and future directions[END_REF]. The length of this potential detour depends on how far the driver is willing to extend his/her trip time. Moreover, if drivers have sufficient time flexibility, they might provide rides to multiple riders simultaneously. Of course, pick-up and drop-off of several riders in a single trip adds layers of complexity to the planning decisions [START_REF] Agatz | Dynamic ride-sharing: A simulation study in metro Atlanta[END_REF].

Thus, a successful ridesharing respects the departure and arrival times for all participants, as well as the maximum detour time for the driver. In DARP-like systems, drivers are employed by the service provider (like in shared-taxi services), and thus have no preferences in terms of departure, arrival and detour times. In such systems, other time restrictions might be considered, such as: maximum working hours for drivers, a maximum response time for processing a passenger request, and the maximum service time for vehicles, which is usually related to recharging and maintenance operations [START_REF] Li | The Share-A-Ride Problem: People and parcels sharing taxis[END_REF]. Most of the previous scheduling constraints also apply to combined systems transporting passengers and goods through the same network. One difference is that in combined systems, every participant specifies a trip excess time which indicates his/her readiness to extend the trip in order to pick up and deliver some goods (Li et al., 2016a). Thus, successful integration of passengers and goods in a shared trip should respect the maximum extra time that participating passengers are ready to accept.

Unlike routing constraints, time constraints, also called scheduling constraints, are considered soft constraints, because violating them might not detach vehicle routes or intercept the flow, but may result in passengers or freight arriving late to their destinations, especially in real-world conditions. Violating these constraints may thus be allowed if it increases the likelihood of finding a solution, but discouraged through a penalty cost.

Capacity constraints (CC):

A capacity constraint is a factor that prevents a shared transportation resource from being overused. In ridesharing systems, a capacity constraint limits the number of passengers sharing the same vehicle at the same time to the number of vacant seats in that vehicle [START_REF] Santos | Taxi and ride sharing: A dynamic diala-ride problem with money as an incentive[END_REF]. Besides limiting the maximum number of passengers, many vanpooling systems also require a minimum number of passengers to form a vanpool for a shared trip [START_REF] Kaan | The Vanpool Assignment Problem: Optimization models and solution algorithms[END_REF]. Number of participants in a shared vanpooling trip must therefore be within these two limits. In logistics systems, a capacity constraint ensures that the volume of goods to be transported does not exceed the available space provided by the transportation service [START_REF] Savelsbergh | 50th Anniversary Invited Article-City Logistics: Challenges and Opportunities[END_REF]. This constraint holds valid whether goods are transported using a fleet of vehicles [START_REF] Li | The Share-A-Ride Problem: People and parcels sharing taxis[END_REF], public transport [START_REF] Behiri | Urban freight transport using passenger rail network : Scientific issues and quantitative analysis[END_REF] or any other transportation service. In addition, in integrated models where passengers and goods are transported together, constraints on both capacities may need to be considered. This is because most of the reviewed literature assumes that passengers and goods are transported in separate compartments (Ghilas et al., 2016a). In an uncertain environment, where passenger or freight demand is stochastic, these capacity constraints might be violated, and should thus be treated using stochastic approaches.

Cost constraints (OC):

In some problem settings, a ridesharing participant may specify a maximum travel cost that he/she is willing to pay for the shared trip, and should thus be matched to shared trips that stay under the maximum amount specified. Furthermore, in order to attract more participants, travel costs in ridesharing systems should be competitive with other modes of transportation. A good example can be found in vanpooling systems where passengers are only assigned to vanpools that are cheaper than their current commuting costs [START_REF] Kaan | The Vanpool Assignment Problem: Optimization models and solution algorithms[END_REF]. However, integrating goods delivery with passenger trips that already take place could decrease travel costs for participants and transportation costs for goods [START_REF] Crainic | Physical Internet Enabled Hyperconnected City Logistics[END_REF]. Even if passengers would have longer detours when freight delivery is added to their trip, they would still get lower travel cost than if no deliveries are added. However, the bulk of research on these combined systems does not consider travel and transportation cost as a feature or constraint in the system but more as an objective to be minimized given its importance for service operators (as we will see in Section 2.2.3).

Synchronization constraints (SC):

Many [START_REF] Fink | Column generation for vehicle routing problems with multiple synchronization constraints[END_REF]. Furthermore, when the operations performed by different transportation units need to be coordinated in terms of space and time, operation synchronization is required. In other words, a schedule for a vehicle in a shared mobility system should be built to take into account the schedules of other vehicles, so their schedules need to be synchronized. Logistics systems offer good examples of when operation synchronization is needed: for example, a system where two different vehicles arrive at different customer locations, one delivering the product and the other carrying the crew to install it [START_REF] Hojabri | Large neighborhood search with constraint programming for a vehicle routing problem with synchronization constraints[END_REF]), or a system in which multiple vehicles cooperate in order to transport one big-size cargo [START_REF] Hu | Synchronizing vehicles for multi-vehicle and one-cargo transportation[END_REF]. Another type of synchronization constraints is called movement synchronization. In some ridesharing systems where passengers are allowed to transfer from one vehicle to another on the way to their destination, the arrival and departure of vehicles to and from transfer points need to be synchronized (see [START_REF] Masson | The dial-a-ride problem with transfers[END_REF] for an example). Another example is found in multi-echelon systems where goods are transported with passengers through a scheduled transport line after being collected by a fleet of vehicles. Such systems also need to ensure synchronization between requests and the collecting vehicles, and between requests and the scheduled line departures (Ghilas et al., 2016b). Load synchronization ensures that the right amount of load is collected and delivered to a customer, or in other words, no load is lost when transferred between different transportation units. This is the case when deliveries are done using two distinct fleets of vehicles where a request is transferred from one vehicle to another at satellite locations before it can be delivered to a customer [START_REF] Grangier | An adaptive large neighborhood search for the two-echelon multiple-trip vehicle routing problem with satellite synchronization[END_REF].

The same load synchronization constraint is needed when deliveries are transferred between pickup and delivery vehicles and a public transport line in a multi-echelon transportation system. Finally, resource synchronization ensures that the use of resources common to different transportation units is limited to availability [START_REF] Drexl | Synchronization in Vehicle Routing-A Survey of VRPs with Multiple Synchronization Constraints[END_REF]. Number of drivers, vehicle fleet size, available parking slots, vacant seats for riders to share, and the available space and capacity in transportation units in both ridesharing and combined systems are all examples of limited resources whose use needs to be synchronized. [START_REF] Xiang | A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints[END_REF] considered a DARP with passenger-driver and passenger-vehicle compatibility constraints.

They classified passengers into different levels, and ruled that vehicles could only accommodate passengers of corresponding levels, i.e. a passenger can only use a vehicle of the same or higher level. As a rule, modeling synchronization constraints yields more complex and non-linear mathematical formulations (e.g. implications) which need to be handled using linearization techniques. However, these constraints are important for modeling realistic settings and, from an algorithmic perspective, can be used to decompose hard problems (e.g. they can be used as coupling constraints in a column generation based approach; see [START_REF] Fink | Column generation for vehicle routing problems with multiple synchronization constraints[END_REF].

Objective functions

Most objectives that shared mobility problems aim to optimize can be classified into two main categories; operational objectives and quality-related objectives. Operational objectives are usually about optimizing system-wide operating costs, such as minimizing vehicle miles and transportation time, maximizing the number of serviced requests, minimizing the number of required vehicles, and others. Quality-related objectives are about enhancing the quality of service provided. For example, minimizing total passenger ride or waiting time might yield a better performance from the passenger perspective but not from a system-wide perspective. Furthermore, minimizing system-wide travel time does not necessarily mean shorter travel times for every passenger. This difference between collective and individual perspectives in shared mobility systems justifies the need for methods that consider both operational and quality-related objectives. A good example can be found in [START_REF] Kalczynski | A decentralized solution to the car pooling problem[END_REF] where a decentralized approach takes carpool participant preferences into account while maintaining the same system-wide savings that can be obtained in centralized approaches.

Much of the research on shared mobility is focused on optimizing a single operational objective, but there are papers that consider multiple-objective systems combining operational with quality-related objectives. In single objective systems, service quality considerations are represented as constraints in the model to ensure a minimum service level [START_REF] Molenbruch | Typology and literature review for dial-a-ride problems[END_REF]. In other words, a set of constraints limiting passenger extra ride times, caused by deviations from their original routes, are added when optimizing the system. Likewise, most of ridesharing research has focused minimizing the system-wide travel distance (vehicle miles) or total travel time. For example, in Wolfler [START_REF] Calvo | A distributed geographic information system for the daily car pooling problem[END_REF], the system-wide travel time in a carpooling system is minimized with an added penalty cost for unserved requests. In a dynamic environment, where transportation demand is revealed in real-time, satisfying full demand may not be attainable, in which case it becomes pertinent to maximize the number of served requests as it extends the reach of the transportation service [START_REF] Berbeglia | A Hybrid Tabu Search and Constraint Programming Algorithm for the Dynamic Dial-a-Ride Problem[END_REF]. Some studies have considered maximizing the total profit obtained from the ridesharing system (see [START_REF] Hosni | The shared-taxi problem: Formulation and solution methods[END_REF] [START_REF] Guerriero | A Hybrid Greedy Randomized Adaptive Search Heuritic to Solve the Dial-a-Ride Problem[END_REF], minimizing vehicle emissions [START_REF] Atahran | A Multicriteria Dial-a-Ride Problem with an Ecological Measure and Heterogeneous Vehicles[END_REF], maximizing passenger occupancy rate [START_REF] Garaix | Optimization of occupancy rate in dial-a-ride problems via linear fractional column generation[END_REF], minimizing staff workload [START_REF] Lim | Pickup and Delivery Service with Manpower Planning in Hong Kong Public Hospitals[END_REF], and maximizing system reliability [START_REF] Pimenta | Models and algorithms for reliability-oriented Dial-a-Ride with autonomous electric vehicles[END_REF]. Most studies on combined crowd-sourced systems have focused on either maximizing the profit obtained by integrating passenger and freight flows [START_REF] Li | The Share-A-Ride Problem: People and parcels sharing taxis[END_REF] or minimizing the operational cost of these systems (Ghilas et al., 2016c), but there have been efforts to consider additional objectives, such as minimizing the number of vehicles required to operate the system [START_REF] Trentini | Optimization of a city logistics transportation system with mixed passengers and goods[END_REF] and minimizing the total wait time of demands before being serviced [START_REF] Behiri | Urban freight transport using passenger rail network : Scientific issues and quantitative analysis[END_REF]. The recent shared mobility studies listed in Table 2.2 and 2.5 have been classified using these different objectives.

As mentioned above, multi-objective systems consider a combination of two or more of the above-listed single objectives. Solving multi-objective problems requires different methods to those employed for solving single-objective problems. The literature identifies three main techniques for dealing with multi-objective problems. The first, and most popular approach is to aggregate the different objectives into a weighted-sum objective with different measures. In this approach, a weight has to be defined for each of the combined objectives.

As such, the relative importance of each objective needs to be quantifiable and well-defined.

A good example can be found in [START_REF] Kirchler | A Granular Tabu Search algorithm for the Dial-a-Ride Problem[END_REF] who used an aggregated objective function combining six different objectives: minimizing routing cost, excess ride time, passenger waiting time, route durations, early arrival times at pickup and delivery nodes, and number of unserved requests. Another example of a weighted-sum objective can be found in [START_REF] Lehuédé | A multi-criteria large neighbourhood search for the transportation of disabled people[END_REF] One drawback of the weighted-sum approach is that it might not be able to find the full set of non-dominated solutions for optimization problems in which some variables are constrained to be integers (i.e. non-convex optimization problems). In addition to weighted-sum approach, some papers consider a hierarchical, also called lexicographical, objective function. In this approach, the different objectives are ordered according to their importance, and first the main objective is optimized to generate a set of solutions, then a secondary objective is optimized whenever two solutions with the same quality, in terms of the main objective, are obtained. Stiglic et al., 2016a considered a ridesharing system with a lexicographic objective function. First, the system generates solutions that maximize the number of matched participants and then the secondary objective is used to select solutions that maximize the distance savings (see also [START_REF] Schilde | Integrating stochastic time-dependent travel speed in solution methods for the dynamic dial-a-ride problem[END_REF]. This approach is therefore efficient in problems where the different objectives can be classified into main and secondary objectives. Finally, the third approach for dealing with multi-objective problems is to obtain the set of non-dominated solutions in terms of the different criteria, called Pareto frontier [START_REF] Paquette | Combining multicriteria analysis and tabu search for dial-aride problems[END_REF]. The main advantage of this approach is that it helps decision makers analyze the relations between the different objectives, as it provides all the possible optimal solutions. However, this approach might not be applicable for dynamic shared mobility systems where decisions need to be taken in relatively short time frames, as it requires obtaining the full set of optimal solutions and a human being to select the best solution among them [START_REF] Molenbruch | Typology and literature review for dial-a-ride problems[END_REF].

Computational complexity and solution approaches

As mentioned above, the shared mobility problem is a generalization of the vehicle routing problem (VRP) and is NP-hard in general. In addition, simplified variants of the problem (e.g. with a single-driver single-rider setting, single pickup and dropoff or a singleobjective function) are still NP-hard [START_REF] Gu | Algorithmic analysis for ridesharing of personal vehicles[END_REF]. Furthermore, solving these problems becomes more complex when they have dynamic settings and stochastic input data. Thus, both exact and heuristic solution approaches have been introduced in the literature. Due to the complexity of shared mobility problems, most studies have focused on developing approximation and heuristic approaches for solving them. That said, a number of studies have developed exact methods for solving simplified variants of the problem. These exact methods are usually used to solve static problem variants with deterministic data, e.g. a column generation-based method for the carpooling problem [START_REF] Baldacci | An Exact Method for the Car Pooling Problem Based on Lagrangean Column Generation[END_REF], a branch-and-cut algorithm for a multi-vehicle static DARP [START_REF] Cordeau | The dial-a-ride problem: Models and algorithms[END_REF], a two phase method for generating optimal matches in a static ride-sharing problem (Stiglic et al., 2016a), and a branch-and-price algorithm for a crowd-sourced system with a scheduled line for transporting passengers and goods (Ghilas et al., 2016c). However, solving these static variants becomes more complex when complicating features are added to the system, such as allowing passenger transfers, integrating public transport, and considering vehicle/driver compatibility. To deal with these complex features, a number of heuristic approaches have been introduced, such as a local search strategy for a static DARP with complex constraints [START_REF] Xiang | A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints[END_REF], an Adaptive Large Neighborhood Search (ALNS) heuristic for the DARP with transfers [START_REF] Masson | The dial-a-ride problem with transfers[END_REF], a constraint-based Large Neighborhood Search [START_REF] Jain | Large neighborhood search for dial-aride problems[END_REF], an integrated column generation in a Large Neighborhood Search [START_REF] Parragh | Hybrid column generation and large neighborhood search for the dial-a-ride problem[END_REF] for a static DARP, a Lagrangian decomposition heuristic for the static shared-taxi problem [START_REF] Hosni | The shared-taxi problem: Formulation and solution methods[END_REF], and another ALNS approach for the crowd-sourced delivery system with scheduled line (Ghilas et al., 2016b).

Nevertheless, even these heuristic algorithms often have large computation times limiting the size of instances on which they can be tested, which consequently also limits their usability for large-scale and dynamic systems which need to be re-optimized at regular intervals as new transportation requests enter the system. As a result, heuristic approaches need to be improved so that good-quality solutions can be obtained in short computational times. In order to clarify how a heuristic approach can be improved to handle dynamic problem settings, we take the ALNS heuristic as an example. In a classical ALNS-based method, a set of insertion and removal operators are used to enhance a current solution.

Thus, at each iteration, one insertion operator and one removal operator are selected and applied to the current solution seeking an improvement. This process continues until an acceptable solution is found or a maximum number of iterations is reached. In order to minimize the number of required iterations, and thus the computation time, the classical ALNS can be improved by adding a score to each operator [START_REF] Masmoudi | Three effective metaheuristics to solve the multidepot multi-trip heterogeneous dial-a-ride problem[END_REF]. If using one operator, whether it is an insertion or removal operator, brings an improvement to the current solution, then the score of the operator used will be increased. The probability of using this operator in the next iterations will thus be higher, and so an acceptable solution would be reached in a shorter time.

For the uncertainty factor, more advanced techniques are needed for solving shared mobility problems with one or more source of uncertainty. This is because a solution obtained by solving the deterministic version of the problem might not be valid when uncertainty is revealed. The most common source of uncertainty lies in transportation demands, where some of the data on transportation requests is unknown at the moment the shared trips are planned. This uncertainty might be in request occurrence times or locations (Ghilas et al., 2016a). Another important aspect is the stochasticity of travel times, as traffic, accidents, and other factors make it impossible to know travel times between different locations in advance [START_REF] Heilporn | An integer Lshaped algorithm for the Dial-a-Ride Problem with stochastic customer delays[END_REF]. Due to the complexity of this uncertainty, most studies have not considered any more than one source. However, there has been some research on integrating multiple sources of uncertainty (e.g. considering stochastic travel times and delivery locations; Li et al., 2016b). For solving shared mobility problems that involve uncertainty, the literature has identified two categories of methods. The most common approach is to make a decision and then minimize the expected (recourse) costs induced by the consequences of this decision. This approach is called stochastic programming with recourse. In the second approach, called multi-scenario approach, the expected costs are estimated by evaluating a solution on a set of different scenarios. In this approach, heuristic algorithms can be efficiently used to obtain a solution each time a new scenario is tested (for more details on stochastic models and their solution approaches, interested readers are referred to [START_REF] Ritzinger | A survey on dynamic and stochastic vehicle routing problems[END_REF].

People sharing rides

This section focuses on introducing shared mobility problems for people transportation.

The idea is to, (i) investigate the potential benefits and planning aspects (Section 2.3.1),

(ii) review the modeling choices and optimization approaches in real-time settings (Section 2.3.2), and (iii) discuss the potential integration of new automated services in such shared systems (Section 2.3.3). We also provide an overview table summarizing the papers reviewed and their problem characteristics and solution approaches (Table 2.2).

Planning and potential benefits

As mentioned above, the increasing demand for passenger transportation has attracted more research into enhancing the efficiency and quality of existing public transport systems and developing new systems that can provide more sustainable solutions [START_REF] Calvo | A distributed geographic information system for the daily car pooling problem[END_REF]. Ridesharing is one opportunity to provide a reduced-cost mobility service that is as flexible as private cars but can also increase occupancy rates and decrease traffic and pollution levels [START_REF] Furuhata | Ridesharing: The state-of-the-art and future directions[END_REF].

In a ridesharing system, drivers and riders share the travel costs so that each benefits from the shared ride. Benefit can be obtained when the travel cost of a shared ride is lower than the cost of the alternative means of transport (individual car trips, taxis or public transport). While some users choose to participate in a shared ride to reduce their travel expenses, others may be motivated by the potential social and environmental benefits [START_REF] Furuhata | Ridesharing: The state-of-the-art and future directions[END_REF]. Besides the potential cost savings, ridesharing can also allow drivers to reduce their travel time because they will be able to take high-occupancy lanes reserved for vehicles with two or more occupants [START_REF] Stiglic | The benefits of meeting points in ride-sharing systems[END_REF]. Riders, on the other hand, may appreciate dispensing with the need to drive or own a vehicle. Despite its potential advantages, there are also major obstacles that prevent wider uptake of ridesharing. According to [START_REF] Furuhata | Ridesharing: The state-of-the-art and future directions[END_REF], the two main barriers to wider adoption of ridesharing are coordinating passenger trips that have similar itineraries and time schedules, and developing effective methods to encourage participation. Limited flexibility in participants' itineraries and time schedules may result in many of them not finding a match. Other issues like privacy, safety, social discomfort and pricing are also challenges for ridesharing systems. For example, a potential participant may be willing to share rides with colleagues and friends, but not with complete strangers [START_REF] Agatz | Optimization for dynamic ride-sharing: A review[END_REF]. As such, new methods for arranging the shared rides need to be developed, and reputation and profiling systems for addressing these social and privacy concerns need to be built.

In order to attract more riders and facilitate matching them in shared rides, we identify some the concepts in the literature that can help maximize the potential benefits of a ridesharing system. One of those concepts is to consider a set of meeting points where a shared ride can take place. Thus, a rider might be picked up at his/her origin location or at a pickup meeting point and dropped off at his/her destination location or at a drop-off meeting point. Meeting points would thus allow drivers to have smaller detours while maintaining a good-enough quality of service for the riders. [START_REF] Stiglic | The benefits of meeting points in ride-sharing systems[END_REF] investigated benefits of using meeting points in a ridesharing system and found that as they can lead to shorter detours, meeting points have the potential to increase the system-wide distance savings as well as the number of participants that can be matched in the system. With the aim of attracting more riders, especially from suburban areas, Stiglic et al., 2018

Real-time ridesharing

As introduced earlier in section 2.2, a real-time ridesharing system aims to bring travelers together at short notice. Furthermore, a real-time ridesharing system might need to be re-optimized at regular intervals as more travelers enter or leave the system. In addition, travelers already en route need to be notified of any change of plan at each time the system is re-optimized, as their original routes might be updated. This automated process requires efficient models and algorithms for matching drivers and riders in very short computation times. As a result, many recent studies on real-time ridesharing systems have focused on developing heuristic approaches, as they can provide good-quality solutions in relatively short computation times. Nevertheless, such systems can also be addressed by enumeration (exact) algorithms (like branch-and-bound). Due to their brute-force nature, using enumeration algorithms for such real-time systems may require an additional preprocessing effort in order to fit the short computation times needed. Some preprocessing techniques can tighten travelers' time windows, eliminating unnecessary variables and constraints and identifying inequalities for narrowing the solution space [START_REF] Liu | A branch-and-cut algorithm for a realistic dial-a-ride problem[END_REF]. For example, Agatz et al., 2011 introduced an efficient rolling horizon approach that can provide high-quality solutions for dynamic ridesharing systems where drivers and riders continuously enter and leave the system. In a later survey, [START_REF] Agatz | Optimization for dynamic ride-sharing: A review[END_REF] provided a review of the related operations research-based models in the academic literature. Here we review the more recent studies and their solution approaches. proposed different formulations for the DARP with driver consistency (DC-DARP). For solving this problem, the authors developed a large neighborhood search algorithm that finds near-optimal solutions in short computation times. [START_REF] Masmoudi | A hybrid Genetic Algorithm for the Heterogeneous Dial-A-Ride Problem[END_REF] propose three metaheuristics for solving the Heterogeneous Dial-a-Ride problem (HDARP). These are: an improved ALNS-based method, Hybrid Bees Algorithm with Simulated Annealing (BA-SA), and with Deterministic Annealing (BA-DA). More recently, [START_REF] Masoud | Using bilateral trading to increase ridership and user permanence in ridesharing systems[END_REF] proposed an exact and real-time ride-matching algorithm, and the approach maximizes the number of served riders while accounting for their travel preferences. The system also aims to minimize the number of transfers and waiting times for riders, and make their shared trips more comfortable. As ridesharing participants might not accept the matches proposed by the service provider on-the-fly, it becomes important to analyze how stable the generated matches are. For this purpose, [START_REF] Wang | Stable Matching for Dynamic Ride-Sharing Systems[END_REF] studies the stability of rideshare matches by providing several mathematical programming methods to generate near-stable matches in real-time. Their results suggested that taking stability considerations into account comes with only a small additional cost to the system-wide performance in terms of traveleddistance savings.

To conclude, the development of new methods and algorithms for providing good-quality solutions in short times is at the heart of the real-time ridesharing concept, which is why we found rising interest from the OR research community to address the optimization issues in real-time ridesharing systems. In many ridesharing systems, like in major metropolitan areas, thousands of drivers and riders might be traveling between thousands of different locations at the same time, thus creating a need for fast optimization approaches that can match their different trips quickly. Most recent studies have focused on developing Chapter 2. Shared mobility systems heuristic approaches that can solve large-scale ridesharing problems in real-time (see Table 2.2) and the door is open for introducing new heuristic techniques. In what follows, we identify possible directions for future research. First, (i), as few papers have considered synchronization aspects in such real-time systems (see Table 2.2), more research should study these aspects and introduce them in future ridesharing systems. An example would be to allow flexible driver-to-vehicle assignments and multi-depot settings which require drivers and vehicles to be synchronized. Second, (ii), very few papers have considered cost restrictions when matching travelers in share rides (cost constraints). An interesting avenue for research would be to focus more on individual traveler benefits from ridesharing beside the system-wide cost considerations. Third, (iii), decomposition techniques could be integrated into algorithms for solving multi-objective problems to consider more qualityrelated objective functions. This is because most of the reviewed papers have considered a single operational objective with a minimum service quality level due to complexity aspects (see Table 2.2). Finally, (iv) for exact approaches, we see three possible techniques to enhance their performance on responding to real-time system needs. These are: developing preprocessing techniques that can decrease the enumeration effort, decomposing the problem based on geographic partitioning or time intervals to make the size of the problem to be solved at each time smaller, and developing faster algorithms for solving the subproblem in a decomposition-based approach (e.g. branch-and-price, branch-and-cut, and so on)

where most of the computational effort is spent on solving the subproblems. That said, ridesharing systems that can handle requests dynamically are clearly gaining the upper hand. As new innovations and transport technologies are introduced, we need more research into responding to traveler needs in future real-time ridesharing systems.

Ridesharing with autonomous vehicles

Autonomous vehicles (AVs), also dubbed driverless, automated or self-driving, are an emerging technology expected to bring fundamental shifts in people transportation. AVs are expected to provide a sustainable solution that can enhance road safety levels and traffic flows, reduce fuel consumption, and thus improve passenger mobility in general [START_REF] Katrakazas | Real-time motion planning methods for autonomous on-road driving: State-of-the-art and future research directions[END_REF]. The potential deployment of autonomous vehicles in tandem with the increasing need for shared mobility services has attracted the attention of the operations research community, especially now that many large mobility providers (Tesla, Ford, Lyft and others)

have announced plans to deploy new autonomous mobility services [START_REF] Sparrow | When human beings are like drunk robots: Driverless vehicles, ethics, and the future of transport[END_REF]. Furthermore, recent studies on different cities have concluded that if AVs are shared, then the number of vehicles needed to provide service to all travelers will significantly decrease [START_REF] Levin | A general framework for modeling shared autonomous vehicles with dynamic network-loading and dynamic ride-sharing application[END_REF]. Despite their potential benefits, shared autonomous vehicles also come with security concerns. In other words, if autonomous vehicles do not prove safer than human-driven vehicles, they might not be legally viable for widespread use [START_REF] Hevelke | Responsibility for Crashes of Autonomous Vehicles: An Ethical Analysis[END_REF]. In a study assessing public interest in such new technology, Daziano determinant of the amount they are willing to pay for automation. [START_REF] Krueger | Preferences for shared autonomous vehicles[END_REF] showed that other service attributes, such as travel cost, travel time and rider waiting time, might be critical factors for uptake of shared autonomous vehicles (for related studies, see Bansal and Kockelman, 2016[START_REF] Yap | Preferences of travellers for using automated vehicles as last mile public transport of multimodal train trips[END_REF], Bansal et al., 2016[START_REF] Zmud | Towards an Understanding of the Travel Behavior Impact of Autonomous Vehicles[END_REF].

Another concern is the potential increase in vehicle miles traveled due to repositioning trips performed by shared autonomous vehicles in order to reach new travelers.

Two main AV ownership models are being considered for future transportation systems:

AVs as a public service, or privately-owned AVs. In the case of AVs as a public service, we consider a fleet of such vehicles at specific locations (depots). AVs are invoked from their stations to satisfy mobility demands in an urban area such that a single AV can serve multiple demands before going back to a depot. Privately owned AVs cannot just bring their owners from their homes to their work locations in the morning and bring them back in the evening while providing ridesharing opportunities to other users, but they can also serve other users when their owners do not need them (e.g. while they are at work). Although some companies (Tesla and Ford) have stated plans to sell AVs to consumers, many transportation companies have either explicitly stated or implicitly implies that they initially plan to use AVs to provide public transportation services rather than selling individual AVs to private consumers for personal use [START_REF] Hyland | Taxonomy of Shared Autonomous Vehicle Fleet Management Problems to Inform Future Transportation Mobility[END_REF]. Given this potential shift from a society that is heavily reliant on privately-owned vehicles to one in which transportation services are provided through fleets of vehicles operated by private companies, significant research is needed to plan such new systems and maximize their efficiency.

That said, there is a surge of interest in developing new methods for operating au- To conclude, there has been a surge in research on AVs in domains from computer science to robotics and engineering, but far less research into how to plan and operate AV services.

We believe there are two main reasons for this gap. First, most of scientific and technological advances have been made by AV manufacturers and service providers who tend to keep their methods and techniques a commercial secret. Second, many studies have suggested that the same methods and algorithms that operate conventional vehicles will continue to apply to AVs, and so a switch from conventional vehicles to AVs does not necessarily entail any real change in the way they operate in a transportation system. From a modeling perspective, this statement holds for many cases. However, there are some variations in which AV-based systems need to be considered differently. For example, privately-owned AVs might be allowed to operate while their owners do not need them, and they might be able to use dedicated roads which could reduce their traffic-related issues compared to conventional vehicles. In addition, AVs are expected to be electric, and so planning their charging and maintenance operations might require different approaches, especially as they have a different service range and they need time to recharge, which could be time-consuming at some intermediate locations [START_REF] Hiermann | Routing a mix of conventional, plug-in hybrid, and electric vehicles[END_REF]. Further research should target (i)

better understanding how AVs can be operated, owned and shared in future transportation systems, (ii) identifying their impacts on people transportation and how AVs respond to passenger mobility needs, (iii) analyzing how shared AVs perform in different scenarios and real-life situations, including varying transportation demand and network topologies, (iv) identifying the new features introduced by AVs and studying how these features could affect existing ridesharing models, and (v) introducing efficient solution approaches that can operate large-scale AV systems and factor in the critical issue of their recharging and maintenance operations.

Case studies

This section presents a set of case studies focused on analyzing different ridesharing systems and their performance and potential impacts. We consider case studies on systems that operate conventional vehicles or AVs, and classify them according to their research objectives and the approaches used. Research objectives have focused on studying either the performances, efficiencies and deficiencies of the ridesharing systems, or their impact on peoples' lives and future transport infrastructure. On the other hand, we also observe that the studies considered have used either optimization-based, simulation-based or data-analysis-based approaches to achieve the intended research objectives. We discuss the different studies and their outcomes, and provide a table classifying them into different categories.

There have been a number of recent case studies conducted to test the viability of ridesharing systems and evaluate their proposed solution approaches. [START_REF] Agatz | Dynamic ride-sharing: A simulation study in metro Atlanta[END_REF] led a study based on 2008 travel demand data from metropolitan Atlanta, and the results suggested that advanced optimization approaches have the potential to increase the participant matching rates and system-wide travel cost savings obtained in dynamic ridesharing systems. Ma and Zhang, 2017 studied traffic flow patterns in a single bottleneck corridor using a dynamic ridesharing mode and dynamic parking charges, and the results showed that system performance over the traditional morning commute may not be significantly improved when ridesharing fees and parking charges are fixed. Nonetheless, dynamic parking charges with appropriately set ridesharing fees can improve system performance in terms of vehicle miles and hours traveled and in terms of allied travel costs. [START_REF] Jiang | Large-Scale Nationwide Ridesharing System: A Case Study of Chunyun[END_REF] proposed a large-scale nationwide ridesharing system called CountryRoads which was deployed in three different years to assess system performance improvement through a case study of the 'Chunyun' spring festival travel season in China. Results indicate that the proposed system was able to attract more users, achieve a higher success matching rate, and thus contribute to an increasingly successful ridesharing experience. Ferreira and D'Orey, 2015 proposed a dynamic and distributed taxi-sharing system that was evaluated using a simulation modeling approach based on realistic taxi trips in Porto (Portugal). Simulation results showed that the system has the potential to reduce taxi fares, operation costs and total travel distance (up to 9%). Furthermore, [START_REF] Maciejewski | Large-scale microscopic simulation of taxi services. Berlin and Barcelona case studies[END_REF] Case studies on ridesharing systems (see Table 2.3) have mainly focused on assessing their performance and giving cues and clues for further research to increase their efficiency and maximize their benefits. Studies have since been conducted using optimization, simulation or data-analysis approaches, but there have been fewer recent case studies analyzing the impacts of ridesharing on transportation systems, possibly because ridesharing is not a new concept, and so the bulk of research is focused either on improving existing ridesharing systems or operating new ones rather than studying their potential impacts, which are assumed to be net-positive.

We

Diels and

Bos, 2016 discussed a potential increase of motion sickness issues in AVs. Wadud, 2017 focused on identifying which vehicle sectors would likely be the earliest adopters of full automation in the UK, and their findings suggests that households with the highest income will get higher gains from automations as they travel higher distances. Netherlands, argue that such a system is able to compete with walking mode but needs to improve its performance to be competitive with cycling. Through a case study using taxicab trip data from New York City, Ma and Zhang, 2017 concluded that an AV sharing and reservation system can significantly increase vehicle mileage rates while reducing their ownership rates. Another case study by [START_REF] Lokhandwala | Dynamic ride sharing using traditional taxis and shared autonomous taxis: A case study of NYC[END_REF] suggested that replacing traditional taxis by shared AVs in New York City could potentially reduce the fleet size by 59% while maintaining the sale service quality. The study concluded that sharing AVs can increase occupancy rate (from 1.2 to 3) and decrease system-wide vehicle distance (up to 55%) (case studies are classified in Table 2.4).

Unlike for ridesharing systems, case studies on shared autonomous mobility systems have mainly focused on studying their expected outcomes and effects on people mobility and on existing transportation systems. This may be due to the fact that the introduction of autonomous mobility services in transportation systems is a new trend in transportation research, and so its potential impacts need to be studied and carefully analyzed before it can be widely adopted. However, most of studies reviewed have used simulation-based approaches, which is evidence that these new systems are still in an early stage of research.

As a result, more research studies will be directed towards studying their operational performance as soon as they are widely deployed.

People and goods sharing rides

This section focuses on introducing shared mobility systems that combine both passenger and freight transportation. First, we set the context by reviewing the most recent concepts and trends in city logistics (Section 2.4.1). Then, the opportunities and challenges that can result from combining people and freight flows are discussed and their modeling and solution approaches are investigated (Section 2.4.2). Table 2.5 summarizes the papers reviewed with their different characteristics and methods used.

Setting the context: planning city logistics

The demand for freight transportation basically results from the need to transport goods from producers to consumers who are geographically apart. In general, this transportation chain consists of a pickup process (pre-haul or first-mile), a transportation process (long haul), and a delivery process (end-haul or last-mile) [START_REF] Steadieseifi | Multimodal freight transportation planning: A literature review[END_REF]. While freight transportation can take place in widespread geographical areas, city logistics considers the transportation of goods and their potential effects on traffic flow and congestion in urban areas [START_REF] Savelsbergh | 50th Anniversary Invited Article-City Logistics: Challenges and Opportunities[END_REF]. However, both freight transportation and city logistics aim to provide customers with the products they need at the right time and place and at low cost.

Increasing global population, and thus increasing demand for goods, together with digital revolution and technological advances are creating both opportunities and challenges for planning and improving the sustainability of urban freight systems. Given their fundamental role in providing for people's daily needs, efficient city logistics have the potential to improve quality of life for more and more people. Recent studies in this direction have focused on anticipating the future opportunities and challenges facing city logistics. In their recent review on city logistics, Savelsbergh and Van Woensel, 2016 identified the trends driving changes in city logistics: growing urban populations, increasing importance of e-commerce and swift supply chains, and the rise of the sharing economy and sustainability aspects. They claimed that sharing assets and capacities can enable higher capacity utilization, and thus reduce fleet sizes and numbers of freight movements. Besides studying the impacts of the information revolution on city logistics, Taniguchi et al., 2016 also described applications of big data and decision-support systems that can be used to enhance the design and evaluation of city logistics schemes, and gave illustrations of the need for new innovations that can help reduce the impact of freight in urban areas. One of the most common scenarios for reducing the number of freight vehicles going into cities is to consolidate goods volume at urban distribution centers, called consolidated distribution centers (CDC), which are usually located a city's borders [START_REF] Allen | The Role of Urban Consolidation Centres in Sustainable Freight Transport[END_REF]. In this scenario, cargo is delivered to a CDC by different supply chain operators, consolidated at the center, and then shipped to final customers using clean and highly utilized vehicles [START_REF] Alessandrini | Automated vehicles and the rethinking of mobility and cities[END_REF]; Figure 2.2).

The main advantage of using CDCs is that shipments can be grouped by destination into packages where every package will be transported using a vehicle. This way, the number of vehicle trips and the need for parking bays can be reduced, this affording a more efficient delivery service. In order to make it efficient, these vehicles have to be small, agile, have large enough loading capacity and comply with the environmental requirements governing energy con- For example, [START_REF] Simoni | Urban consolidation solutions for parcel delivery considering location, fleet and route choice[END_REF] proposed a heuristic approach for routing vehicles carrying parcels from CDCs to their final destinations within an urban area, and identified the most efficient and environment-friendly strategies and regulations for this delivery.

Another promising opportunity in city logistics is the deployment of autonomous mobility services. With their potential application in future freight transportation systems, AVs might be used for refilling shops from remote warehouses, performing last-mile deliveries to clients, and collecting and transporting waste and products (CityMobil (2011); [START_REF] Alessandrini | Automated vehicles and the rethinking of mobility and cities[END_REF]. However, assessing the benefits of AVs and their efficient employment and impacts on city logistics is an important topic in today's research, and still requires further investigation. Many freight transportation companies have started using unmanned ground vehicles and unmanned aerial vehicles (drones) for small parcel deliveries (see [START_REF] Otto | Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey[END_REF] for a recent review). The idea is that these relatively small unmanned vehicles will depart from warehouses or delivery trucks carrying small deliveries for individual customers.

For example, Murray and Chu, 2015 studied a problem in which delivery trucks carrying drones depart from and return to a depot. In their settings, customers are served either by delivery trucks or by drones that operate in coordination with the delivery trucks. Depending on its flight endurance, a drone has to deliver the customer's order and return to either the truck or a depot, the aim being to minimize the time required to deliver all customer orders. Such a system is thought to provide a more efficient delivery service at lower cost and with reduced environmental impacts.

Furthermore, another important innovation is the potential for delivering customer orders to more convenient locations than the home (e.g. direct delivery to a customer's car trunk [START_REF] Savelsbergh | 50th Anniversary Invited Article-City Logistics: Challenges and Opportunities[END_REF]. Thanks to new technologies, a one-time access to customer a car trunk can be granted during a specific time-period and revoked as soon as the delivery is completed. In their recent paper, Reyes et al., 2017 modeled this last-mile trunk delivery as a VRP with roaming delivery locations (VRPRDL). In their approach, the delivery locations are first optimized for a fixed customer delivery sequence in order to generate an initial route. Then, the initial route is improved by switching a predecessor's or successor's delivery location once a customer is inserted or deleted. Results reveal that trunk delivery could potentially cut distance traveled in tests with realistic instances.

In such systems, some locations may change or move as the delivery process starts (like the location of a delivery truck a drone is to return to in [START_REF] Murray | The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery[END_REF], and the roaming delivery locations in [START_REF] Reyes | Vehicle Routing with Roaming Delivery Locations[END_REF]. Although this feature might lead to more flexible deliveries, it requires more complex models and sophisticated heuristic approaches, due to the layer of complexity added by the synchronization constraints required to adapt different departure and arrival times to these roaming locations. [START_REF] Reyes | Vehicle Routing with Roaming Delivery Locations[END_REF] example, proposed a neighborhood search heuristic with a set of insertion and deletion operators, and considered the roaming delivery locations when building routes by enhancing the classical VRP insertion and deletion operators by including customer shifts to different delivery locations and consequently different time-windows within them. Thus, at each a time a new route is built, a set of alternative routes, where precisely one customer delivery location is different to the original route, are generated. However, due to the added complexity, generating these alternative routes requires additional computational effort. Building on this review of the latest trends in city logistics, we focus in the following subsection on the promising concept of integrating people and freight flows for future transportation systems development.

Combining people and freight transportation

Since both people and goods move in the urban environment, an efficient and effective transport network that ensures smooth sharing of passengers and freights is an essential element in city life [START_REF] Cochrane | Moving freight on public transit: Best practices, challenges, and opportunities[END_REF]. There is ample literature on the problem of passengers or goods transport using dedicated networks, but far less research on joint use of transport resources between passengers and goods flows. However, combined transportation systems are starting to garner increasing attention.

A combined transportation system aims to use the underused assets in public masstransport modes such as urban rail, buses or in people private-car trips to bring loads to a central station or take loads from that station to distribute it to the local neighborhood [START_REF] Crainic | Physical Internet Enabled Hyperconnected City Logistics[END_REF]. In such a system, we have a set of passengers and parcels, each having an origin location from where it should be picked up, and a destination location to where it should be carried and dropped off. We also have a transportation system, having both private and public transportation modes, which is able to transport both passengers and parcels simultaneously. Thus, the aim is to satisfy the demand of both passengers and parcels while minimizing costs and distances traveled, and therefore reduce congestion and pollution levels in urban areas. Of course, the transportation of goods must not disturb passenger trips. In other words, a passenger would accept only small deviations and short extra times for transporting parcels in the same trip. Thus, trip times that significantly exceed a passenger's usual route times in order to load and deliver parcels would likely be unacceptable. Although most problems dealing with passengers and goods transportation are NP-hard, so very difficult to solve, many studies have attempted to tackle them with different models and solution approaches. These models fall into two broad categories:

single-tiered and two-tiered models (see Figure 2.3). A single-tiered model considers a set of vehicles each having specific capacity. These vehicles are able to transport passengers and goods to their destinations while accommodating certain like passenger and parcel time windows and vehicle capacity and service time (see [START_REF] Li | The Share-A-Ride Problem: People and parcels sharing taxis[END_REF]. In a two-tiered model, combined transport of passengers and goods is achieved via the contribution of a first-tier, generally composed of a public transport line with a set of transfer points or stations, and a second tier, composed of a range of vehicles being able to transport both passengers and goods (or only goods depending on the model studied) from transfer points to their final destinations (see [START_REF] Trentini | Optimization of a city logistics transportation system with mixed passengers and goods[END_REF]. Strict synchronization between the two tiers is therefore necessary. For planning and operating such combined systems, different models and solution approaches have recently been proposed, most of which aim to minimize their operational costs, or put differently, maximize their benefits. However, some studies have considered other objectives like minimizing the number of vehicles required for making of taxis, and some parcels are delivered during these taxi trips as long as delivery does not affect the passengers significantly. Passengers thus have priority over parcels. Furthermore, the SARP assumes that a taxi cannot serve two passengers simultaneously and that a parcel cannot be served by more than one taxi, i.e. it is either served by one taxi or not served at all. Another basic assumption in SARP is that parcel transportation requests are known beforehand whereas passenger requests arrive dynamically. In addition to the SARP, the authors propose a second model, which has similar settings but with the assumption that the assignments of passengers to taxis and their delivery sequences are also given. In this case, dubbed the freight insertion problem (FIP), the problem becomes static (see Figure 2.4). Solving the FIP is about finding a way to insert parcel requests without significantly extending passenger travel times. Since routing is given, the FIP has less complexity than the SARP, and can thus be solved relatively fast, at least fast enough for solving reallife instances. To solve this problem, authors present MILP formulations for both SARP and FIP and conduct a numerical study of both static and dynamic scenarios. Given the complexity of the problem, the authors proposed an ALNS to solve it (Li et al., 2016a) The SARP study was further extended by considering two stochastic variants; one with stochastic travel times and another with stochastic delivery locations (Li et al., 2016b). In both cases, a two-stage stochastic programming model with recourse is used with the ALNS heuristic and a scenario generator. Results obtained from testing both stochastic models demonstrate that even though the convergence rate is faster, the SARP is less sensitive to the stochastic delivery locations than the stochastic travel times. The study thus concluded that considering stochastic information when modeling and planning real-life taxi-sharing systems can dramatically improve their performance over deterministic solutions. Recent research has also focused on two-tiered models. Trentini et al., 2015 introduced a combined system that uses the available capacity in a passenger bus line to transport parcels (also see [START_REF] Trentini | A shared " passengers & goods " city logistics system[END_REF]. In their problem settings, all incoming goods are stored in CDCs, then loaded on buses operating through the bus line when there is spare capacity, and finally unloaded at specific bus stops and delivered to customers using a fleet of lowemission city freighters. The proposed problem is modeled as a VRP with transfers, and a mathematical formulation is given, along with an ALNS to solve it (see [START_REF] Masson | Optimization of a city logistics transportation system with mixed passengers and goods[END_REF], for a similar system). direct and indirect shipments. In a direct shipment, a freight request is picked up at its origin and delivered to its destination using one vehicle, i.e. the scheduled line is not used.

In an indirect shipment, a freight request is picked up by a vehicle, transferred to a nearby transfer node, transported between two transfer nodes by a scheduled public transport line, and finally picked up by another vehicle and delivered to its final destination. Thus, solving the problem is about defining routes and schedules for both freight requests and delivery vehicles. In order to solve this problem, the authors proposed a branch-and-price algorithm where the pricing problem is a variant of the elementary shortest path problem with resource and precedence constraints (ESPPRPC). Due to the complexity of the problem, an ALNSbased algorithm is also proposed (see Ghilas et al., 2016b). Moreover, a stochastic version of the problem in which the demand quantity of each freight request is only revealed when the vehicle arrives at its pickup location was considered (Ghilas et al., 2016a). To consider this uncertainty, a scenario-based sample average approximation approach is introduced.

Another two-tiered crowd-sourced delivery system [START_REF] Kafle | Design and modeling of a crowdsource-enabled system for urban parcel relay and delivery[END_REF] suggested that a set of cyclists and pedestrians, called crowd-sources, might be willing to deliver small-size parcels from a delivery truck to customers living in the same neighborhood. A set of carrier trucks transport parcels to intermediate transfer points (first-tier) and then potential crowdsources perform the last-mile delivery. To solve this problem, the paper proposes a tabu search algorithm. Results show that crowd-sourcing the service can lead to lower operational costs compared with a pure-truck delivery service.

This review on systems that combine people and freight transportation shows that the topic is gaining increasing interest (see Table 2.5 for a summary). Models and algorithms for both single-tiered and two-tiered systems have been explored. Although some papers have introduced exact approaches for solving this type of problem, the bulk of the research has focused on developing heuristic approaches. This is due to the complexity of such problems which require fast optimization approaches to tackle them in short computation times. We also find that most of the papers reviewed have focused on profitability. Nevertheless, other objectives have also been considered, such as minimizing the number of vehicles needed to operate the system and the distances covered. Thus, an useful direction for future research would be to also address the environmental issues which have not yet been considered in

Case studies

Given its potential benefits, the integration of passenger and freight transportation to ensure that all requests are delivered. Gonzalez-Feliu and Mercier, 2013 studied the potential deployment of a combined people-freight approach in the city of Lyon (France) and found that it was crucial to apply an accessibility analysis that shows the attractiveness of different urban zones before this combined system can take place. Thus, the difficulty for households living at different city zones to reach their retailers should be considered when deploying the system. Wang et al., 2016 evaluated their crowd-tasking model using datasets from bus and taxi services in Singapore, and their results demonstrate that crowd-sourcing can be efficiently used in large-scale problems with real-time deliveries where this kind of service can be profitable to logistic companies as well as crowd-workers. More recently, [START_REF] Masson | Optimization of a city logistics transportation system with mixed passengers and goods[END_REF] led a case study based on a dataset derived from the city of La Rochelle (France) and found that efficient transshipment of freight from buses to city freighters is a major concern in a mixed system, as inefficient transshipment of freight between the two tiers might delay deliveries and significantly affect passenger trips. Although most case studies are ultimately optimistic over the future of combining passenger and freight flows, some of the allied concerns and practical issues still need to be investigated. These issues involve, among others, (i) security concerns, (ii) confidentiality and data privacy (like using only a barcode with limited personal information to identify parcels), (iii) the redesign of parcels with different sizes to fit in the shared transportation compartments, and (iv) uncertainties during deliveries (e.g. freight order modifications and cancellations). We would thus advocate more studies to evaluate these issues and study their impacts on the future deployment of these integrated systems.

Conclusions

This chapter reviewed different variants of shared mobility systems along with their modeling choices and solution approaches. The papers reviewed covered mobility systems where people share their rides and mobility systems where people and goods are combined.

We presented a set of case studies either analyzing shared mobility system performances or studying their potential impacts on people's lives and future transportation systems.

New shared mobility systems for both people and freight transportation have the potential to provide major societal, economic and environmental benefits. The development of algorithms for planning and operating such systems is at the heart of the shared mobility concept. This chapter highlighted a number of promising optimization opportunities and challenges that arise when developing new systems to support shared mobility. Relevant operations research models in this area have also been reviewed. Although ridesharing is not a new concept, we have seen that the interest in enhancing dynamic ridesharing systems and developing new systems for matching passengers on-the-fly continues to grow. More research is now needed on systems that consider trip synchronization and traveler cost aspects, or more generally the quality of the provided service. One of the latest big trends appears to be research on deploying new autonomous mobility services. We now need more research on how these new services can operate and how they can impact future transportation systems. As such, we propose to study a ridesharing system in which individually-owned and on-demand autonomous vehicles are used for serving passengers where their trips are synchronized using the concept of meeting points (as we will see in chapter 3). The aim is to assess the sharing potential and planning aspects of these new autonomous mobility models in a ridesharing context.

On the other hand, The potential integration of passenger and freight transportation is another promising opportunity that is steadily gaining currency. As such, more studies on developing realistic models and efficient algorithms that consider different objectives (including environmental issues) and different sources of uncertainty are also needed, along with new public policies to regulate this integration. That said, we propose to study a system that integrates freight deliveries to a scheduled line for people transportation where passenger demand is stochastic (chapter 4). The aim is to evaluate the expected benefits of this integrated system as well as the impacts of stochastic passengers demand on such integration. We believe that these new innovations provide a rich vein of research opportunities, and we anticipate that the review provided in this chapter, along with the systems studied in the next chapters, could spur more contributions in this emerging area of transportation science.

Chapter 3

Synchronizing people transportation flows

As introduced in chapter 2, the impact of autonomous vehicles (AVs) on urban mobility systems is an increasingly discussed topic in recent years. Two AV ownership models are being considered for future transportation systems. These are: autonomous vehicles as a public service or individual owning ownership. The first ownership model is based on AVs operating within an on-demand (taxi) service while the second proposes private vehicle ownership combined with offering the AV to other users when not used by its owner and thereby partially financing the vehicle's acquisition cost. In this chapter, we study a ridesharing system that uses both AV ownership models. We then develop a two-phase method for assessing the sharing potential of these different models by considering the number and distance of shared trips, and thus, evaluating the potentially saved vehicle kilometers. We analyze a set of sharing scenarios on a case study for New York City.

Introduction

Autonomous mobility services and their potential impact on existing mobility systems have been growing in popularity in recent years. According to [START_REF] Meyer | Autonomous vehicles: The next jump in accessibilities?[END_REF][START_REF] Attias | The Automobile Revolution[END_REF], fully autonomous vehicles (AVs) are expected to make traveling safer, cheaper, more comfortable, more sustainable, and thus, to reduce traveling costs. If all those assumptions are to become true, autonomous vehicles will dramatically change the urban form especially that they might be used as a shared transportation service. Thus, the potential deploy- have the priority to be served by their AVs, all users have the same priority to be served by an AV in an on-demand service. In addition, an important aspect is that an AV, whether it is individually-owned or on-demand, can be shared by multiple users. Ridesharing aims to minimize the number of vacant seats in vehicles so that the number of required vehicles is reduced. Although it may increase depreciation and risk of damage and leads to longer trips for owners, the idea of ridesharing comes with many benefits. These benefits include reducing travel cost and time, alleviating traffic congestion, conserving fuel and energy and reducing air pollution. Thus, using autonomous vehicles in a ridesharing system represents a promising opportunity in future transportation systems.

ment
Extending the work on vehicle sharing by [START_REF] Stiglic | The benefits of meeting points in ride-sharing systems[END_REF], the aim of this research is to study and compare the different ownership and usage scenarios for autonomous vehicles and assessing the sharing potential of those different variants by a case study for New York City. This chapter is organized as follows. In section 3.2, we provide an overview of related literature. In section 3.3, we describe both variants of the problem introduced earlier. The solution method we have developed is detailed in section 3.4. In section 3.5, we present the computational study we have conducted on New York City and we discuss and analyze its

1 For example, Tesla and Ford for the individually-owned AVs, and Lyft for the on-demand ones results. Finally, in section 3.6, the key findings are summarized and directions for future research are suggested. to large numbers of passengers and trips, and on the other hand, dynamically generates optimal routes with respect to online demand and vehicle locations. Their algorithm, which applies to fleets of autonomous vehicles, starts from a greedy assignment and improves it through a constrained optimization, quickly returning solutions of good quality and converging to the optimal assignment over time. Their approach is based on the idea of decoupling the problem by first computing feasible trips from a pairwise shareability graph and then assigning trips to available vehicles.

Background

In this chapter, we consider a simplified ridesharing setting in which only one pickup and one drop-off is allowed during a shared trip. Thus, riders sharing the same trip will be all picked up at the same pick-up location and all dropped off at the same drop-off location. For this purpose, we define a set of fixed locations where pickups and drop-offs can take place, or in other words, a set of meeting points. The idea of using meeting points goes in hand with the original work, by [START_REF] Stiglic | The benefits of meeting points in ride-sharing systems[END_REF], that we extend in this research. In their paper, the authors propose a two-phase algorithm that optimally matches drivers and riders in largescale ridesharing systems with meeting points where the aim is to investigate the potential benefits of introducing meeting points in such a ridesharing system. Unlike the original research which considered commuter morning trips, we propose a heuristic approach that extends the proposed approach. We focus on studying the sharing potential of autonomous vehicles through comparing their different ownership models and usage scenarios on a full day time horizon where demands are known beforehand. The originality of this research is that it proposes an approximation approach that allows us to analyze a large number of ridesharing scenarios for AVs where most of the available research on this domain uses simulation-based approaches (see Bischoff and Maciejewski, 2016c[START_REF] Chen | Operations of a shared, autonomous, electric vehicle fleet: Implications of vehicle & charging infrastructure decisions[END_REF], Zhang et al., 2015a[START_REF] Fagnant | The travel and environmental implications of shared autonomous vehicles, using agent-based model scenarios[END_REF]. While considering travel costs is not in the scope of this work, we focus on studying the number of matched participants as well as the system-wide distance savings through a case study for New York City.

Problem description

In this chapter, we consider two ownership models for AVs; individually-owned and ondemand service. There are two main differences between these two ownership models. The difference is illustrated in Figure 3.1 where each node represents a meeting point (MP), the origin or destination of an owner or a rider, or a depot. Owner's are denoted with o's and riders are denoted with r's. In the individually-owned case, AVs are based at their owners' home locations and the owners have a higher priority to be served by their own AVs.

Additionally, owners can indicate how much extra time they can afford to accommodate a shared ride. On the other hand, all users have the same priority in the on-demand case and AVs are located at certain locations (depots) waiting for requests. Nonetheless, both cases have similar problem settings and will be modeled and solved by the same solution approach (section 3.4). As mentioned above, we consider a full day planning horizon where transportation demands are known in advance. For example, an individually-owned AV brings its owner (o1) from his home to his work in the morning and brings him back home in the evening while offering rides to other potential riders (r1,r2 and r3) (Figure 3.1a). Riders are picked up and dropped off at their home/destination locations or at feasible meeting points (MPs). We call this kind of trips one-way trips, where the origin and the destination of the trip are two different locations. One-way trips represent mainly, but not only, morning and evening commutes. Furthermore, the individually-owned AV can serve riders (r4, r5 and r6) while its owner (o1) is at work and must return to him before he finishes his work. We call this kind of trips, where AVs depart from and return to the same location, round trips. In the on-demand AV case (Figure 3.1b), AVs are based at service centers (C) and waiting for incoming requests. AV#2, for example, departs from its center, serves riders (r4, r5 and r6), and once all riders are dropped off, it returns to the center. We can observe that an on-demand AV trip has similar characteristics to the round trip in the individually-owned AV case. In both cases, multiple (consecutive) shared trips may take place but only one pickup and one drop-off are allowed during each shared trip (In Figure 3.1, riders r4 and r5, sharing the same trip, are picked up and dropped off at the same meeting point). Furthermore, since AVs are assumed to be electric ones, both individually-owned and on-demand AVs cannot be in service for more than a certain amount of time because they need to be recharged. Thus, an individually-owned AV is assumed to be recharged at its owner home location (during the night) and work location (during the day). Similarly, on-demand AVs are assumed to be recharged at their depots. The main difference is that when an individually-owned AV is doing a round trip, it has a time window specified by its owner.

Thus, if the owner is willing to allow his AV to serve other potential riders, the AV is only available while its owner does not need it and must return to him before he needs it again.

These additional time restrictions are considered in the proposed model. For the sake of simplifying the problem, we assume that all AVs have the same capacity and that traveling (either walking or driving) occurs at a constant speed. However, most of those assumptions can be relaxed so as to cover a more realistic settings.

Notation and parameters

In this problem, a set of trip announcements S is considered. Every announcement s ∈ S is characterized by: an origin o s , a destination d s , an earliest departure time e s and a latest arrival time l s . The set of announcements S is partitioned into two subsets; O ⊂ S set of trip announcements by the owners and R ⊂ S set of trip announcements by the riders. While on-demand AVs are located at different centers (depots) and ready to serve riders, owners specify when and where their owned AVs are available for sharing (for example, during a morning trip from home to work or a day trip while owner is at work). Thus, every owner i ∈ O specifies the maximum trip duration T i , which implies the extra time he accepts to accommodate a shared trip, and the number of available seats C i , which indicates the maximum number of riders his AV can accommodate. On the other hand, every rider j ∈ R specifies the maximum distance m j that he is willing to walk to and from a meeting point.

Furthermore, we denote the origin and the destination of a trip announcement s ∈ O ∪ R with o s and d s . In addition, distances and travel times between every two locations are considered. Thus, we denote the distance from location i to location j with δ i,j and the travel time between them with t i,j . A set of meeting point locations M is given. A rider can be picked up at his origin or at one of his feasible pickup meeting points and dropped off at his destination or at one of his feasible drop-off meeting points. A feasible meeting point is a point which the rider can reach in an acceptable walking distance (i.e. less than the maximum walking distance that he specified). As such, we denote the set of feasible pickup meeting points for a rider j with M p j := {k ∈ M |δ o j ,k ≤ m j } and the set of feasible drop-off meeting points for rider j with M

j := {(k, l)|k ∈ o j ∪ M p j , l ∈ d j ∪ M d j }.
Thus, a rider j can be picked up at his origin o j or a meeting point in M p j and dropped off at his destination d j or a meeting point in M d j . Finally, the service time at each meeting point m ∈ M , which is the time needed for riders to get into and out the AV, is denoted by τ m .

Definition of a feasible match

A match is a combination of an owner i ∈ O, a set of riders J ⊂ R and a trajectory that indicates the route which the AV will follow during the trip which is represented by a meeting point arc a ∈ A. In order for a match (i, J, a) to be feasible, it must have the following properties:

• Capacity feasible:

A feasible match must satisfy the capacity constraint of the AV, or in other words, the number of riders that can participate in the trip must be less than or equal to the number of available seats specified by the AV owner i. Thus, if the owner i is not participating in the trip (round trip), then the number of available seats will be equal to the AV capacity:

|J| ≤ C i (3.1)
• Time feasible:

A feasible match must satisfy the time-window constraints of its participants. A match is time-feasible if it respects, for all its participants, the earliest departure times from their origin locations and the latest arrival times at their destination locations and, for the owner, the maximum trip duration. In order to check time feasibility of a match (i, J, a), Stiglic et al., 2015 suggested to construct an implied time window [e k p , l k p ] at the pickup meeting point k for each participant p (either i or j ∈ J) in the match. Following their proposition, e k p represents the earliest departure time possible for participant p from the pickup meeting point k, such that: e k p = e p + t op,k , where e p is the earliest departure time of participant p and t op,k is the travel time between participant origin o p and the pickup meeting point k. In addition, l k p represents the latest departure time possible for participant p from the pickup meeting point k, such that:

l k p = l p -(τ k + t k,l + τ l + t l,dp )
, where l p is the latest arrival time of participant p, t k,l is the travel time between pickup and drop-off meeting points (k, l), t l,dp is the travel time between the drop-off meeting point l and participant destination d p , and τ k and τ l represent the service time at meeting points k and l respectively. Thus, in a time feasible match, the intersection of the implied time windows has to be non-empty, which implies that:

max(e k i , max j∈J e k j ) ≤ min(l k i , min j∈J l k j ) (3.2)
Where max(e k i , max j∈J e k j ) is the earliest time, and min(l k i , min j∈J l k j ) is the latest time, at which the shared ride can depart from meeting point k. In addition, a time feasible match should respect the maximum trip duration specified by the owner, thus:

t o i ,k + τ k + t k,l + τ l + t l,d i ≤ T i (3.3)
In other words, the sum of travel times between different locations (i.e. owner origin to pickup meeting point t o i ,k , pickup meeting point to drop-off meeting point t k,l , and drop-off meeting point to owner destination t l,d i ) and service times at meeting points (i.e. τ k and τ l )

must not exceed the maximum trip duration (T i ) that the owner can accept to accommodate the shared ride.

• Distance feasible: Since only one pickup and one drop-off are allowed in a shared trip, then the meeting point arc a should be feasible to all riders J ⊂ R in a feasible match (i, J, a). Thus, the pickup and drop-off meeting points shaping arc a should be at feasible walking distances for all riders participating in the feasible match:

a ∈ j∈J A j (3.4)
Furthermore, a distance-feasible match must achieve a distance saving compared to the case of non-shared (individual) trips. Consider the example in Figure 3.2 with one owner o 1 , two riders r 1 , r 2 , a pickup meeting point and a drop-off meeting point (numbers above arcs represent distances between locations). If each traveler will drive individually from his origin to his destination then the overall traveling distance will be 10 + 10 + 10 = 30. On the other hand, if a shared trip will take place (bold arrows) then the overall traveling distance will be 8 + 10 + 8 = 26. As such, the shared trip has the potential of reducing the overall traveling distance, and thus, the match has a positive distance saving. A match between owner i and riders in J ⊂ R on a meeting point arc a = (k, l) has an associated distance

saving of σ (i,J,a) = δ o i ,d i -(δ o i ,k + δ k,l + δ l,d i ) + j∈J δ o j ,d j , where (δ o i ,d i + j∈J δ o j ,d j )
is the travel distance of individual (non-shared) trips of participants (including owner and riders' trips), and (δ o i ,k + δ k,l + δ l,d i ) is the travel distance of the shared trip. Thus, the match is feasible if σ (i,J,a) > 0:

σ (i,J,a) > 0 (3.5) st. σ (i,J,a) = δ o i ,d i -(δ o i ,k + δ k,l + δ l,d i ) + j∈J δ o j ,d j
As a result, a match is feasible when it respects capacity, time and distance constraints.

With every feasible match, two values are associated; the number of participants and the distance saving. By solving this problem, we aim at finding the set of matches that maximizes the number of matched participants as we will see in the following section.

Matching problem

The matching problem is formulated as a maximum weight bipartite matching problem.

A node is created for each owner i ∈ O and for each rider j ∈ R. An edge connecting node i and node j is added if there is a feasible match between owner i and rider j. Furthermore, nodes representing a set of riders in R are also created and an edge connecting owner i and a set of riders is added if a feasible match between them exists. Each edge e has two weights associated with it: the number of participants in the match v e , and a distance saving σ e . Let E represent the set of all edges in the bipartite graph and let the binary decision variable x e for edge e ∈ E indicate whether the edge is chosen in an optimal matching ( x e = 1 ) or not

( x e = 0 ). In addition, let E i and E j represent the set of edges in E associated with owner i and rider j. Thus, the matching problem with the objective of maximizing the number of matched participants (Z) can be formulated as the following integer program:

max Z = e∈E v e x e (3.6) subject to e∈E i x e ≤ 1 ∀i ∈ O (3.7) e∈E j x e ≤ 1 ∀j ∈ R (3.8)
The objective function (3.6) maximizes the number of matched participants. Constraints (3.7) and (3.8) assure that each owner and each rider is only included in at most one match in a final matching.

Solution approach

As it was defined earlier, a match is a combination of an owner, a set of riders and a meeting point arc where the shared ride can take place. As such, the problem is to find the set of those matches in which as many travelers (owners and riders) as possible are matched and participating in shared rides. In order to solve this problem, we propose a heuristic algorithm. The proposed approach is an extension of the two-phase algorithm introduced by [START_REF] Stiglic | The benefits of meeting points in ride-sharing systems[END_REF]. The two phases are: generating feasible matches and selecting the best among them through a matching problem. In the first phase, we look for feasible matches for every owner iteratively and we add them to the matching problem. Then, the matching problem aims at selecting the best matches such that each owner/rider is matched at most once in a final solution. Our approach aims to maximize the number of matched participants. It is important to mention that the main driver of our algorithm design is the fast execution times. This allows us to test and analyze various scenarios of the problem.

In the first phase, the aim is to find the set of feasible matches. For this purpose, the algorithm considers owners one by one and tries to build feasible matches with potential riders. If a feasible match is found, an edge, linking the matched participants (owner and riders), is added to the matching problem with two associated coefficients; the number of participants and the potential distance savings. On the other hand, the algorithm finds for every rider, according to the maximum walking distance that the rider accepts, the sets of feasible pickup and drop-off meeting points (section 3.4.1). Furthermore, once an owner is considered, the algorithm checks whether his trip offer is a one-way trip or a round trip and generate his feasible matches accordingly (sections 3.4.2, 3.4.3 respectively). We extend the original algorithm presented in [START_REF] Stiglic | The benefits of meeting points in ride-sharing systems[END_REF], which only considers one-way trips, by allowing AVs to perform round trips. Thus, the proposed algorithm aims at generating feasible solutions for both one-way and round trips at short computational times.

Determine feasible meeting point arcs for a rider

In order to generate feasible matches, the algorithm defines the set of feasible meeting point arcs for every rider. In other words, the sets of meeting points where a rider can be picked up and dropped off need to be defined. For this purpose, we store the set of meeting points in a k-d tree data structure. k-d trees have the ability of performing n nearest neighbors search and fixed-radius near-neighbor search in logarithmic time [START_REF] Bentley | K-d trees for semidynamic point sets[END_REF].

Thus, we use the k-d tree to find, for each rider j, the meeting points that are accessible from his origin o j and destination d j within an acceptable walking distance (less than m j ).

Once feasible meeting points for rider j are known, a set of feasible meeting point arcs is constructed by combining every possible pair of feasible pickup and drop-off meeting points. is time feasible, the algorithm proceeds to calculate its associated distance saving. If the combination has a positive distance saving, it will be temporarily conserved while the other feasible meeting point arcs of the rider are checked. A match combining an owner, a rider and a meeting point arc that has the best distance saving will be added to the set of feasible matches. Afterwards, the algorithm will consider the next rider similarly until the whole set of riders is checked and all feasible single-rider matches are added. Once all feasible single-rider matches are added, the algorithm will try to find feasible multi-rider matches and add those found to the matching problem (Figure 3.4, see also Appendix A.1).

Algorithm

As mentioned above, the algorithm aims to look for the feasible matches for every single owner and then passing those feasible matches to the matching problem which will choose the best among them. The algorithm takes an instance as input (see Figure 3.6). The instance is composed of three sets: set of owners O, set of riders R and a set of meeting points M . The algorithm starts by storing meeting points in the k-d tree so they can be rapidly retrieved later. In the next step, the algorithm will search the k-d tree in order to find the feasible pickup and drop-off meeting points, and thus the feasible meeting point arcs, for every rider.

Once the feasible meeting point arcs of every rider are found, the algorithm considers owner trip announcements one by one and checks whether it is a one-way or round trip. If it is one-way trip, the algorithm finds all feasible single-rider matches, then two-riders matches, etc., until the available capacity is reached. If a feasible match is found, an edge is added to the matching problem with two associated coefficients; the number of participants and the potential distance savings. On the other hand, if the considered owner trip announcement corresponds to a round trip, the algorithm selects a set of riders as artificial owners. Thus, a sequence of artificial owner trips will be constructed as long as the original time window specified by the "real" owner can still be respected. Those constructed artificial owner trips are one-way, and thus, feasible single and multiple rider matches are computed in a similar manner (Figure 3.6, see Appendix A.2 for the detailed algorithm).

Early checking for feasible matches

When the number of participants (owners and riders) is relatively large, it can become computationally prohibitive to find all their feasible matches. This huge computational effort is illustrated by the fact that the algorithm will have to check for every owner, all rider feasible meeting point arcs. Thus, reducing the number of meeting point arc feasibility checks has the potential of accelerating of the algorithm. For this purpose, [START_REF] Stiglic | The benefits of meeting points in ride-sharing systems[END_REF] suggests that if we assume that the rider travels to the boundary of his walking range at vehicle speed and there is no feasible match under that assumption, then there is no feasible match when the rider is walking. Thus, there will be no need to check all his feasible meeting point arcs (see Figure 3.7). is the longest distance a rider j is willing to walk to and from a meeting point. From Figure 3.7, it is obvious that there cannot be a feasible match between owner i and rider j if the trip time when rider j is picked up and dropped off at the boundary of his acceptable walking distance is longer than the maximum trip duration that the owner i can accept:

(t o i ,o j -t max j ) + (t o j ,d j -2t max j ) + (t d j ,d i -t max j ) > T i (3.9)
Thus, only if this infeasibility check indicates that there may be a feasible match between owner i and rider j, the algorithm proceeds to examine the possible matches for each meeting point arc. As such, the number of meeting point arc feasibility checks can be reduced.

Results and discussions

In this section, the results of a computational study are reported. The aim of this computational study is to test the proposed solution approach and to assess the sharing potential of the different ownership and usage scenarios using datasets for New York City. For generating one-way trip announcements, their origin and destination locations, earliest pickup and latest drop-off times have to be defined. Origin and destination locations are generated based on the original locations that are available for each taxicab trip. Since taxicab trip time records represent the actual departure and arrival times, we extend them by a 30 minutes time flexibility parameter in order to be matched in a shared trip [START_REF] Stiglic | The benefits of meeting points in ride-sharing systems[END_REF]. We thus deduct 15 minutes from the actual departure time and add 15 minutes to the actual arrival time so that the difference between the latest arrival time and the earliest departure time is equal to the sum of the actual trip duration and the time flexibility parameter. For owner trips, we assume that owners, who wish to participate in a shared ride, are not willing to extend their original trip time by more than 20 minutes.

Parameters and instance generation

The capacity of the AVs, whether they are individually-owned or on-demand, is assumed to be the same. Thus, if AV owner is participating in the trip (one-way trip), then he has a capacity of 3 spare seats. Furthermore, if the owner is not participating in the trip (round trip), then we assume that the AV has 4 spare seats to accommodate riders. In addition, we assume that the maximum walking distance that riders are willing to walk to and from a meeting point is 0.5 kilometer (see Table 3.1).

For generating round trip announcements, we assume that not all owners, having a morning trip with an earliest departure time between 5 and 9 am, from their homes to their work locations, are willing to let their AV serve others while they are at work. For this purpose, we randomly select 25% of those morning trips and we accordingly generate their relative round trips. We thus consider that the origin, which is also the destination, of the generated round trip is the owner work location. We also assume that the earliest departure time for a round trip to be 15 minutes later than the arrival of the owner to his work location (for example, if the owner arrives to his work location at 8:30 am, then his AV will be available for service at 8:45 am). Furthermore, we assume that an AV should return to its owner before 4 pm because he needs it to get back to his home. As mentioned before, individually-owned AVs are assumed to be recharged at their owner home/work locations and that their round trips should not be longer than 6 hours because they need to be recharged. On the other hand, on-demand AVs are recharged at predefined service centers, where they are located, and should return to their centers at most after 6 hours in service so that they can be recharged. We assume that an on-demand AV needs 2 hours in order to be fully recharged before it gets back in service.

Moreover, we assume that AVs circulate at a fixed speed (24 km/h) and that riders move at 4 ft/s walking speed [START_REF] Laplante | The continuing evolution of pedestrian walking speed assumptions[END_REF]). The service time, which is the time needed for riders to get in or out the AV at a meeting point, is assumed to be 2 minutes.

For calculating travel distances between different locations, we use the haversine formulation (which computes the great circle distance between two points).

Finally, we generate, for each of the instances, four variants in which the owner-to-rider ratio is different (see Table 3.2). In the first variant we generate an equivalent number of owner and rider trip announcements where the number of riders increases to twice, four times and ten times the number of owners in the second, third and forth variant respectively. The goal of generating those different variants is to see how increasing the demand could affect the different elements of the analysis and compare the results obtained by testing instances with different owner-to-rider ratios. In addition, a higher demand better reflects city-wide mobility where thousands of trips take place every day. We also provide a set of scenarios by which each one of the instances is tested as we will see in the following section.

AV usage scenarios:

As mentioned above, the main aim of this research work is to analyze the different ownership models and their different usage scenarios. We thus consider different scenarios for testing each instance. The idea is to start with a scenario in which we only have individually-owned AVs (IO AVs) and the set of riders. We then assume that a set of those owners (10% of them at each scenario) are not willing to use their own AV, or in other words, they are willing to be picked up by an AV as potential riders. As such, they are added to the set of riders. Moreover, we replace those owner trip announcements by a number of on-demand AVs (OD AVs) which are based at the predefined service centers.

Therefore, 10% of the owner trip announcements are randomly selected, transfered into rider trip announcements, and replaced by a set of on-demand AVs. The process of generating scenarios continues until all owner trip announcements are replaced by on-demand ones and all travelers participate as riders (see Table 3.3 for an example). Furthermore, three different rates for replacing individually-owned AVs with on-demand ones are considered. We consider that each added on-demand AV replaces one, two or five individually-owned ones (1-to-1, 1-to-2 and 1-to-5 replacement rates). For example, in Table 3.3, 150 individually-owned AVs are replaced by the same number of on-demand AVs at each scenario (1-to-1 replacement rate). Relatively, the number of on-demand AVs replacing the 150 individually-owned ones will drop to 75 and 30 with 1-to-2 and 1-to-5 replacement rates (respectively). Regardless of the replacement rate used for generating the different scenarios, replaced owner trip announcements are all considered as riders.

Meeting points:

In order to test the generated instances and their scenarios, a set of meeting points, where riders can be picked up and dropped off, is needed. As such, we generate the required meeting points based on actual public transport stations in New York (Figure 3.8a). Those data records, which are provided by the Metropolitan Transportation Authority MTA, capture New York transit subway and bus locations (see Appendix B.2). In order to have a minimal and well-distributed set of locations, we filter the available locations and we eliminate some of them such that a minimum distance of 500 meters between every pair of locations is guaranteed. Without filtering those locations, the number of feasible meeting point arcs for each rider will dramatically increase, and thus, generating feasible matches will be computationally prohibitive. The choice of using public transport stations as meeting points comes with two main benefits. First, they are well distributed around the city, and thus, cover the studied area especially that their locations are available. Second, those stations are accessible by different modes of transportation (e.g. subway, bus, etc.). As such, considering them as meeting points opens the door for integrating the use of autonomous vehicles with other transportation modes in future research.

On-demand AV depots:

For the on-demand AVs case, we need to define a set of locations (depots) where the ondemand AVs can be located. For this purpose, we fix four locations corresponding to actual taxi-service and car-service centers in New York City (one center in Manhattan ("Lower East Side Car Services"), two centers in Queens ("Liberty Taxi NYC" and "Athena Car

Service") and one center in Brooklyn ("Eastern Car Service") (Figure 3.8b). On-demand AVs are invoked from these centers to serve requests and get back to their centers once their trip is finished.

Performance

The algorithm for generating feasible matches is implemented in Java 1.8.0. For solving the matching problem, CPLEX 12.6 is used. Instances were tested on a quad-core i5-5300U machine with 8 GB of RAM. The base case instance, with 1-to-1 owner-to-rider ratio (Table 3.1), solves in less than 7 minutes while instances with 1-to-2, 1-to-4 and 1-to-10 ownerto-rider ratios solve in less than 12, 25 and 90 minutes respectively. CPLEX solves the matching problem in a few seconds for different instance sizes. Most of the computational time is thus spent generating feasible matches for one-way and round trips. However, these relatively short running times suggest that our approach is suitable for approximating dynamic operations where instances with a much smaller set of trip announcements have to be solved at any one time.

Experiments

The solution approach that we have implemented provides a good basis because it allows us to test instances with different sizes, scenarios and replacement rates in relatively short computational times. We use the generated instances and the set of solutions (matches)

provided by the algorithm to compute and evaluate a number of metrics that can help us in conducting the intended analysis. We use the following metrics in our analysis: the number of participants, the matching rate for riders, the average number of used AVs, the average system distance savings, the average number of served participants per AV (PpV), the average traveled distance per vehicle (DpV) and the average extra travel time for participants. All metrics are measured at different scenarios. As such, the x-axis in the following graphs represents the different usage scenarios, or in other words, the percentage of on-demand AVs that are available for service at each of the scenarios. Furthermore, we analyze their values over different replacement rates (1-to-1, 1-to-2 and 1-to-5, as introduced earlier in this section).

As introduced in section 3.3.3, every feasible match is associated with the number of travelers that are participating in it and the matching problem aims at maximizing the overall number of participants in the system. Thus, a participant is a traveler (owner or rider) who is participating in the system. Furthermore, since an owner uses his own AV to travel, we always consider owners as participants even if they are not matched in a shared trip. On the other hand, a rider is considered as participant only if he is matched in a shared trip.

Participation and matching rate:

Results, obtained by averaging the 16 instances with different owner-to-rider ratios, indicate that when the number of available on-demand AVs increases, the number of matched participants increases as well (Figure 3.9). This applies to the four owner-to-rider ratios when each on-demand AV is replacing one, two or five individually-owned AVs. We observe that when the number of riders becomes four or ten times the number of owners with 1-to-5 replacement rate, the number of participants decreases in scenarios with more than 80% of on-demand AVs (Figure 3.9g & 3.9j). This is due to the large number of riders and the fewer number of AVs which is not sufficient for serving this increasing demand.

Another important metric is rider matching rate. This metric represents the percentage of riders that are matched in the system. Thus, only riders are included. The goal of measuring this metric is to observe how the different scenarios and replacement rates could affect the number of riders that are successfully matched in a shared ride.

As for the number of matched participants, results indicate that as more on-demand AVs are replacing individually-owned ones, the rider matching rate increases (Figure 3.9). This is mainly because on-demand AVs have a higher flexibility in terms of time constraints (unlike the individually-owned where owner preferences have to be respected). Thus, an ondemand AV can provide service to a larger number of potential riders. We also observe that the convergence towards the 100% matching rate is faster when the number of owners and riders are equal (Figure 3.9b). When the number of riders becomes higher, the convergence becomes relatively slower (Figure 3.9e). Furthermore, with 1-to-4 and 1-to-10 owner-torider ratios, the matching rate does not converge when five IO AVs are replaced by one OD AV. This is due to the lack of enough AVs to serve the increasing demand (Figure 3.9h & 3.9k). If we take the 1-to-1 owner-to-rider ratio as an example (Figure 3.9b), we observe that satisfying all rider requests is obtained with the three different replacement rates but in different scenarios. Thus, for satisfying the demand in this case, we need the percentage of on-demand AVs to be at least: 10% of the available AVs with 1-to-1 replacement rate, 20%

with 1-to-2 replacement rate, or 50% with 1-to-5 replacement rate. On the other hand, for the 1-to-4 owner-to-rider scenario (3.9h), satisfying rider requests can be achieved by having at least 30% OD AVs with 1-to-1 replacement rate or 60% OD AVs with 1-to-2 replacement rate but cannot be achieved with 1-to-5 replacement rate (similarly for 1-to-10 ratio, Figure 3.9k). This observation can help in fixing the number of on-demand AVs needed to fully satisfy the demand in each one of the instances. This is illustrated by the number of used AVs at each of the scenarios (Figure 3.9c,3.9f,3.9i,3.9l for the different owner-to-rider ratios). Since the number of available AVs depends on the replacement rate used at each scenario, the presented graphs correspond to 1-to-1 replacement rate (blue line with circled points). If we consider instances with 1-to-1 owner-to-rider ratio as an example (Figure 3.9b & 3.9c), in the first scenario (where around 1500 IO AVs are available), we still have about 20% of rider demands which are not served. In the second scenario, when 10% of the available IO AVs are replaced by a similar number of OD AVs, rider demands are totally satisfied and the number of used AVs starts to decrease. As such, we observe that not all the added OD AVs are actually used, or in other words, fewer number of OD AVs is needed to satisfy all demands in this scenario. When more OD AVs are added in the later scenarios, the number of used AVs keep decreasing while the 100% matching rate is maintained. In the last scenario, where riders are served by OD AVs only, we observe that around 250 OD AVs (out of 1500 that are available for service) were used to satisfy all demands. A similar observation can be seen for instances with larger owner-to-rider scenarios. As such, in a fully on-demand scenario, around 350, 600 and 900 OD AVs are needed to fully satisfy rider demands with 1-to-2, 1-to-4 and 1-to-10 owner-to-rider ratios (Figure 3.9f,3.9i,3.9l respectively). However, the decreased number of used AVs while maintaining high matching rates means that an on-demand AV is serving more rider requests and doing longer trips than an individually-owned one.

In order to compute the average number of participants that are served by an AV, or in ). This increase is obtained, not just because an on-demand AV is serving more riders and thus traveling for longer distances to cover the increasing demand, but also because of the empty trips that an on-demand AV might have to do between two consecutive shared rides (an empty trip appears after an AV drops off one, or more, rider and heads to pick up the next one) or when departing/returning to its owner (or depot) location. Thus, reducing the distance covered by those empty trips, which mainly appear in round trips for both IO and OD AVs, represents a challenge in such systems and an opportunity to enhance the service and maximize its benefits if it is treated efficiently. One way to reduce the effect of empty trips is to consider a more realistic ridesharing settings where riders can be picked up and dropped off dynamically at any time during AV trip.

As a result, the increasing rider matching rate illustrates the potential benefit of having a fleet of on-demand AVs replacing individually-owned ones. In addition, replacing individually-owned AVs with on-demand ones has the potential of decreasing the overall number of AVs circulating in the system. However, the previous observations indicate that when the demand becomes higher, a fully on-demand AV system, especially with high replacement rates, might not be able to satisfy all rider requests. Thus, a minimum number of AVs circulating in the fleet need to be ensured.

Distance saving rate:

One important metric of the analysis is the potential distance saving that might be obtained when ridesharing takes place. For calculating the saving, we compare two distances:

the actual distance covered by all AVs for accommodating the shared rides (distance-withsharing, introduced earlier), and the overall distance if all participants will do individual trips with no sharing at all (called distance-with-no-sharing). The distance-with-no-sharing is actually the sum of origin-to-destination distances of all participants (owners and riders).

As such, the distance saving is calculated as follows; distance-saving = 1 -(distance-withsharing / distance-with-no-sharing).

Results illustrate the benefit of ridesharing in terms of distance saving. We can observe that sharing AVs, whether they are individually-owned or on-demand, has the potential of saving 19 to 23 % (21.5% in average) of the overall traveling distance (see Figure 3.11a) when compared to a system in which no sharing takes place. This considerable distance saving rate can be observed in all scenarios and with the different replacement rates. Nonetheless, results show that the saving rate is higher when an on-demand replaces more IO AVs (1-to-5 replacement rate). This is due to the relatively larger number of available AVs in the first two replacement rates. As such, a larger number of riders might be picked up and dropped off at their origin and destination locations, and thus, the distance saving ratio will be less.

Fagnant and Kockelman, 2014 suggest that a shared AV can replace around 11 conventional vehicles, but might add up to 10% travel distance compared to non-shared AV trips. This difference between our results and theirs is due to three main reasons. The main reason is that we use meeting points to match different participants, while in their paper, a shared AV should pass by rider origin and destination locations. Thus, meeting points can lead to shorter detours and better distance savings. The second reason is related to trip patterns.

While we consider short trips around city center (with average trip distance of 3.64 km), in However, our results are consistent with the original study, by [START_REF] Stiglic | The benefits of meeting points in ride-sharing systems[END_REF], where 27 to 29% distance savings were obtained. This small difference (between 19 to 23% savings in our case, and 27 to 29% in their case) is due to round trips, which require more relocation empty-AV trips, that do not exist in the original study. Another important reason is that we consider a single objective which is to maximize the number of participants where the original study considered an additional objective which is maximizing distance saving. To cope with that, we consider this additional objective and we solve the problem in a lexicographical fashion. This means that the model will first maximize the number of participants, and then, select the solution with the highest savings such that the obtained number of participants is maintained.

Looking at the results, we observe that the average distance saving increases to 23.4%

when the second objective is considered (compared to 21.5% with a single objective) (Figure 3.11b). This slight increase indicates that the algorithm is able to find multiple solutions with the same number of participants but with different distance saving rates. Once the second objective is added, the model can select the solution with the highest saving while maintaining the same level of service in terms of served participants and matching rates.

In addition, it was observed earlier that a minimum number of available AVs is needed to ensure the satisfaction of rider demands. Our results show that having a larger number of AVs in the fleet might not lead to a better distance saving ratio unless the use of available seats in each AV is maximized. In other words, a critical key for a successful ridesharing system is to minimize the number of used AVs while maintaining the quality of the provided service.

Average detour time: As for AV owners, results indicate that they will have up to three minutes of additional travel time when matched in a shared ride compared to their non-shared trips. This additional time, which demonstrates the detour an AV should perform to transport potential riders, decreases as more on-demand AVs enter the system (Figure 3.12, in 100%

on-demand AV scenario, all owners participate as riders). Although sharing trips impose additional travel time to owner trips, they will still have reduced trip costs and they might benefit from reserved lanes for vehicles with multiple travelers. On the other hand, our results indicate that the average extra travel time for the rider decreases when the number of on-demand AVs increases (Figure 3.12). This is due to the flexibility that on-demand AVs provide where the possibility of picking up and dropping off a rider at meeting points that are relatively close to his origin and destination locations becomes more probable. Thus, in a sharable on-demand service, a rider will be matched to a closer meeting point, and thus, the extra time needed to travel from his origin to his destination will be decreased, or in other words, a better ridesharing experience can be achieved.

Considering traveler preferences:

In a shared work with some colleagues, we conducted a survey to evaluate the willingnessto-use of shared on-demand AVs in greater Paris region [START_REF] Maghraoui | Shared Autonomous Vehicle Services and User's Taste Variation : A Survey and Model Applications[END_REF]. One of the important outcomes of the survey is that 40% of the participants have expressed that they are ready to pay an extra fee (20% of their shared trip cost) in order to have a private on-demand AV (i.e. no sharing with other travelers). As aforementioned, we consider that all traveler demands are homogeneous, or in other words, no traveler profiles or preferences are considered in the original model. We try in this section to have a closer look on what effects can be observed when these preferences are considered in the system. We believe that the intended observations will help service operators to better understand the impact of traveler profiles on their future AV-based systems.

Based on the results obtained from the survey, we assume that 40% of participants are willing to pay an extra fee to get a private on-demand AV service (i.e. 100% on-demand AV scenario is considered here). We refer to these participants as VIP travelers. Every VIP traveler will be served separately using on-demand AVs. For the rest, non-VIP travelers, the system will continue to match them in shared trip. In order to analyze the impact of introducing traveler profiles on operator benefits, we assume the AV transport cost per kilometer to be 0.2e/km2 . In addition, the traveler cost per km is considered to be 0.2e/km for non-VIPs and 2.24e/km for VIPs3 (i.e. 20% more than the normal fee). Results of averaging different instances with 3000 travelers (only riders in this case) indicate that the general benefit of the service operator might decrease by up to 4% when 40% of travelers are assumed to be subscribed to the VIP service. Although VIP travelers pay extra charges for the service, the operator will also have some additional costs which are related to the higher number of on-demand AVs needed to operate the service. More precisely, an on-demand

AV that was able to serve 2 or 3 travelers in the original case, might have to serve only a VIP traveler in the second case which might increase the system-wide vehicle-miles and thus increase the operational cost of the service.

From travelers point of view, results indicate that introducing traveler profiles into the system has the potential to enhance the quality of the service provided. On the one hand, VIP travelers will have a more comfortable, and relatively shorter travel times, as they will be transported directly from their origins to their destinations. On the other hand, the average detour time and the average waiting time (at meeting points) for non-VIP travelers will decrease by 11% (≈0.37 min) and 5.5% (≈0.21 min) respectively. To conclude, introducing traveler profiles to the system can increase the overall satisfaction of VIP travelers as well as having a positive effect on non-VIP travelers in terms of their detour and waiting times.

However, this means that service operators might need to invest 4% of their benefits in order to provide an enhanced travel experience for their travelers.

Conclusions

In this study, a heuristic approach for studying and comparing the different ownership models for autonomous vehicles has been introduced. The proposed approach consists of two phases: an identification phase for generating the set of feasible matches, and an optimization phase, for selecting the best among them. The algorithm was tested with different scenarios and replacement rates using instances generated based on New York City taxicab datasets.

Results of the analysis indicate that sharing AVs has the potential of increasing the number of participants and the matching rate for riders as well as the number of participants that can be served by an AV. Although shared AVs might have to circulate for longer distances, sharing rides can save up to 23% of the overall traveling distance which has a considerable impact on traffic in New York City. In addition, our results suggest that a system, in which on-demand AV service is partially or fully used and shared, has a better performance than a system in which only individually-owned AVs are used. The advantages of the shared on-demand AV service are illustrated in higher rider matching rates, fewer number of AVs needed to satisfy the demand, better distance saving rates and shorter travel times. In addition, this study suggest that fleet sizing, the efficient planning of AV trips, and the use of meeting points are important factors in a successful ridesharing system in which autonomous vehicles operate.

Since we build our analysis on a set of assumptions that simplify the problem, the door is always open for considering different and more realistic settings. As such, we point out some future research directions: (1) In this chapter we considered a static ridesharing setting in which travel demands are known in advance and only one pickup and one drop off are allowed. Thus, an interesting research direction would be to consider more realistic ridesharing settings in which travelers (owners and riders) are matched on-the-fly, (2) since autonomous vehicles will be electric ones, a promising research direction would be to consider recharging operations when building shared rides, and (3) how to consider different approaches for calculating travel distances. We believe that this study will help in better understanding the potential deployment of autonomous vehicles with their different ownership models, and thus, promote more research towards studying this emerging technology.

Introduction

The demand for freight transportation basically results from the need of transporting goods from producers to consumers who are geographically apart. In general, this transportation process consists of picking up products at their producer locations (pre-haul ), transporting them (long-haul ), and delivering them to final consumers (end-haul ) at the right time and place and at low costs [START_REF] Steadieseifi | Multimodal freight transportation planning: A literature review[END_REF]. The increasing demand for goods in urban areas, together with the emerging information and technological advances are creating both opportunities and challenges for planning urban freight systems [START_REF] Savelsbergh | 50th Anniversary Invited Article-City Logistics: Challenges and Opportunities[END_REF]. One of these promising opportunities is to use the low-utilized people transport systems (e.g. off-peak hours of urban rail, buses or private-car trips) to also transport goods. A successful integration of these transportation streams can enhance the service quality of their existing transportation systems as well as their systemwide gains. For example, spare capacity in public transport systems can be used for retail store replenishment [START_REF] Trentini | Optimization of a city logistics transportation system with mixed passengers and goods[END_REF] or a taxi can deliver freight when transporting a passenger or during idle time [START_REF] Li | The Share-A-Ride Problem: People and parcels sharing taxis[END_REF].

In such combined systems, we have a set of passengers and parcels that need to be transported simultaneously from their origins to their destinations. This combination can lead to minimizing vehicle-miles traveled, traffic congestion and pollution levels in urban areas.

It can also yield some travel cost reductions for passengers. However, such a system must ensure that the transportation of goods does not disturb passenger trips. In other words, a passenger would accept only small deviations and short extra times when transporting some parcels in the same trip (i.e. trip times that exceed passenger usual route times significantly might not be acceptable).

In this chapter, we consider an integrated system in which a set of freight requests needs to be transported from their origins to their destinations. We use a fleet of grounded and autonomous pickup and delivery (PD) robots where a public transportation service (e.g. a set of shuttles, referred to as scheduled line (SL)) can be used as part of PD robot's journey1 . Most research considers that passengers and goods are transported separately. However, we consider that passengers and PD robots (carrying goods) share the same capacity. This implies that a freight request can be served in one of two ways: (1) a direct delivery (where only a PD robot is used) or (2) transferred through SLs (where both PD robots and SLs are used). Therefore, a parcel might be picked up at its origin location by a PD robot, transported through the scheduled line with passengers, and delivered to its final destination by the PD robot. In order to guarantee an acceptable service quality for passengers, they are assumed to have a higher priority to use SL service. In other words, PD robots are only able to use SLs when there are free places available (i.e. not used by any passengers).

A similar system is considered by Ghilas et al., 2016a where a scheduled line service is used along with a fleet of heterogeneous vehicles to serve a set of freight requests. In their system, the exact quantities demanded by each customer are only learned upon vehicles' arrival at the corresponding pickup locations. Unlike their problem settings, we consider that freight quantities are known in advance. In addition, we consider that passengers demand for transportation is only learned upon the shuttles' arrival to each SL station. Since passengers and PD robots share the same capacity on SLs, the number of available places

for PD robots at each SL departure is thus stochastic. Depending on the actual passengers transport demand, there are two possible violation outcomes: (i) the PD robot is not able to take the next SL departure due to the high passenger demand at the corresponding station, and (ii) the PD robot needs to get off the SL at an intermediate station, where passengers demand is high, in order to give its place to a passenger. When these route failures occur, a number of recourse actions are needed in order to recover feasibility. Applying these recourse actions might lead to extra handling and transportation costs compared to their original routes.

The key contributions of this chapter are as follows. First, we model the proposed pickup and delivery problem as a two-stage stochastic problem. The first stage consists of defining routes for PD robots carrying freight requests. These routes are evaluated over a set of scenarios and their associated recourse costs are calculated in the second stage.

The overall objective is to minimize the overall transportation costs (i.e. the sum of the first-stage routing costs and the second-stage recourse costs). Second, we propose a sample average approximation (SAA) method along with an Adaptive Large Neighborhood Search (ALNS) algorithm for solving the stochastic optimization problem. Finally, we provide a computational study to quantify the impact of passengers demand realization on such combined systems. This is achieved by comparing the solutions obtained when deterministic and stochastic versions of the problem are solved. While the potential benefits of integrating parcel deliveries to SL service were extensively studied in Ghilas et al., 2016b, in this paper we aim at studying the impacts of stochastic passenger demands on this system with different SL frequencies and capacities.

This chapter is organized as follows. In section 4.2, we provide an overview of related literature. In section 4.3, we describe the problem, provide a mathematical formulation for it, and introduce an algorithm to evaluate its solutions and calculate their recourse costs.

The proposed solution method is detailed in section 4.4. In section 4.5, we present the computational study and analyze its results. Finally, in section 4.6, the key findings are summarized and directions for future research are suggested.

Background

An increasing amount of research is being directed recently towards studying and developing new transportation systems that integrate passenger and freight flows. These systems can be classified into single-tiered and two-tiered systems. In single-tiered systems, a set of vehicles transport passengers and goods to their destinations while taking into account some considerations (e.g. request time windows, vehicle capacity, etc.). On the other hand, passenger and freight flows are combined in two-tiered systems thanks to the contribution of a first-tier (e.g. a public mass-transport line), and a second-tier (e.g. a fleet of vehicles)

that performs the last-mile deliveries to customers (see [START_REF] Mourad | A survey of models and algorithms for optimizing shared mobility[END_REF] for a recent review).

Regarding single-tiered systems, [START_REF] Li | The Share-A-Ride Problem: People and parcels sharing taxis[END_REF] introduced the Share-a-Ride Problem (SARP) in which passenger and freight requests are transported using a fleet of taxis driving around in a city. As passenger requests are given a higher priority, some parcels are delivered during taxi trips in case this delivery does not affect the passengers significantly.

For solving the SARP, a MILP formulation, that extends the classical Dial-a-Ride problem, along with an Adaptive Large Neighborhood Search (ALNS) method were proposed (see also Li et al., 2016b). Their results demonstrated the benefits of such combination in terms of transportation costs and traveled distances. These benefits were observed by comparing results to those where passenger and freight requests are served separately. In another study, [START_REF] Arslan | Crowdsourced Delivery -A Pickup and Delivery Problem with Ad-hoc Drivers[END_REF] presented an event-based rolling horizon framework that dynamically assigns parcel deliveries to self-employed drivers who are willing to earn some extra money by making deliveries on their way to home or work. In addition, the authors proposed a heuristic recursive algorithm for solving the routing subproblem. Their results demonstrated that this integrated delivery can potentially reduce last-mile delivery costs as well as the system-wide vehicle miles. [START_REF] Archetti | The Vehicle Routing Problem with Occasional Drivers[END_REF] considered a similar singletiered model where a set of occasional drivers is used to supplement the service provided by delivery vehicles and dedicated drivers. Occasional drivers are those willing to make a single delivery using their own vehicle. The authors modeled this problem as a Vehicle

Routing Problem (VRP) with occasional drivers and proposed a heuristic approach that uses variable neighborhood and tabu search strategies for solving it. Their results showed that introducing more occasional drivers to the system can decrease the total transportation cost and the number of dedicated drivers required. Moreover, Wang et al., 2016 presented a single-tiered model where last-mile deliveries are performed by a large-pool, a crowd, of citizen workers. The proposed model was formulated as a network min-cost flow problem and solved using an iterative pruning technique. Furthermore, [START_REF] Dayarian | Crowdshipping and Same-day Delivery: Employing In-store Customers to Deliver Online Orders[END_REF] suggested that potential customers can express their interest to participate in making deliveries on their way home. The authors proposed a tabu search heuristic method for generating vehicle routes.

On the other hand, some recent studies have focused on studying two-tiered systems.

Fatnassi et al., 2015 introduced an integrated system where passengers and goods are transported to intermediate points using a first-tier (train, bus or truck line), and then delivered using a fleet of electric vehicles (second-tier). The authors proposed a forward periodicoptimization approach which showed that the proposed system can achieve a potential gain in terms of service time and energy consumption. Another study, by [START_REF] Masson | Optimization of a city logistics transportation system with mixed passengers and goods[END_REF], considered a combined system that uses the available capacity in a passenger bus line to transport parcels to specific bus stations where a fleet of low-emission freighters delivers them to final customers. The paper formulated the system as a Vehicle Routing Problem with transfers and proposed an ALNS-based heuristic to solve it (see also [START_REF] Trentini | Optimization of a city logistics transportation system with mixed passengers and goods[END_REF]. Similarly, Ghilas et al., 2016b introduced a two-tiered system where parcels are delivered by a fleet of vehicles such that a part of the delivery process is carried out on a scheduled line of public transport. The paper modeled this integrated system as Pickup and Delivery Problem with Time Windows and Scheduled Lines (PDPTW-SL) and introduced an ALNS-based algorithm for solving it. Their results showed that an average cost savings of 10% can be achieved thanks to the use of the scheduled line compared to a pure-freight delivery system. Moreover, [START_REF] Kafle | Design and modeling of a crowdsource-enabled system for urban parcel relay and delivery[END_REF] suggested that parcels can be transported to was introduced in order to consider this uncertainty. After reviewing the related literature, we provide a detailed description of the considered problem along with the method used to solve it in the following sections.

Problem Description

Consider a set of shuttles that operate on a scheduled line (SL) service in both directions.

This service consists of a set of physical transfer nodes (i.e. stations) S, where passengers take shuttles as part of their trip to their final destinations, and a set of physical scheduled lines E linking different transfer nodes. Between every pair of transfer nodes i, j ∈ S, there are two scheduled lines with opposite directions (i, j), (j, i) ∈ E. Shuttles move through the scheduled line in fixed routes. Every shuttle moving through scheduled line (i, j) has a capacity Q ij , indicating the number of available places, and a schedule K ij , indicating its departure times at origin transfer node i (denoted by p w ij , e.g. the second departure from s 1 to s 2 is p 1 s 1 ,s 2 = 60 time units). Moreover, shipping one unit of package on scheduled line (i, j) is associated with a cost η ij per unit. In addition, a fleet of autonomous, pickup and delivery (PD) robots are located at transfer nodes. Each PD robot v ∈ V is assigned to a depot (i.e. transfer node) o r ∈ S and has a capacity Q v and a maximum service distance δ v indicating the maximum distance it can go from a transfer node to a request pickup or destination location. Each PD robot is associated with a routing cost per time unit θ v . Depending on the availability of vacant places in SLs, PD robots carrying freights may travel with passengers between different transfer nodes. A freight, carried by a PD robot, can thus be transported by a shuttle between two transfer nodes as part of its journey.

Indeed, allowing passengers and PD robots to travel simultaneously aims at using the spare capacity in shuttles especially that loading (and unloading) these robots into shuttles at transfer points come with relatively short service times. As a result, delivering a request to its final destination can be done in either direct or indirect way (see Figure 3.1). In a direct delivery, a request is picked up by a PD robot at its origin and delivered directly to its final destination without the use of the scheduled line (Figure 3.1a; request a 1 is picked up at its origin o a 1 by a PD robot coming from transfer node s 2 , and delivered to its final destination d a 1 before the PD robot returns to transfer node s 3 ).

It is important to mention that a direct delivery is only feasible if the distance between the transfer node and request origin/destination, and between request origin and destination locations is less than the maximum distance the robot can travel. In Figure 3.1b, if the distance between o a 1 and d a 1 is greater than the robot maximum service distance, a direct delivery cannot be performed and the SL service must be used. On the other hand, in an indirect delivery, a request may be collected by one PD robot, transferred through the scheduled line and delivered afterwards to its final destination by the same PD robot (Figure 3.1b, request a 1 is picked up at its origin o a 1 by a PD robot, brought to transfer node S 2 , transported through the scheduled line from s 2 to s 3 and finally delivered to its final destination d a 1 by the PD robot).

Since passengers and PD robots are using SLs simultaneously in indirect deliveries, we assume that a passenger or a PD robot needs one place in a shuttle while passengers have higher priority to be transported. We also assume that PD robots cannot take over more than a fixed number of places in each shuttle (e.g. if the shuttle capacity is 10 places, PD robots can take over at most 3 places). We assume that each PD robot can serve only one freight request at a time. In other words, a PD robot can only pickup one request from its origin to a transfer point and deliver it from a transfer point to its final destination during one single trip. This assumption can be relaxed so as to consider more realistic settings in which a PD robot can perform multiple pickups and deliveries during a single trip.

Furthermore, the following set of assumptions is used throughout the chapter:

• SLs are assumed to be homogeneous in terms of frequency and capacity.

• We assume that all the shuttles operating on SLs have the same capacity. Each shuttle is thus assumed to have a maximum number of places to transport both passengers and PD robots.

• We assume that a PD robot might return to a different station than the one it departed from (as it is the case in Figure 3.1a) after delivering its request (i.e. relocation operations are not considered).

• As PD robots are likely to be electric ones, a PD robot is assumed to be fully charged at each time it departs from a transfer node for picking up or delivering a request and that this charge is enough to perform its trip (recharging operations are not considered).

• It is also assumed that each PD robot has a storage compartment (where parcels are stored during the robot trip) and those compartments are assumed to be homogeneous.

• Regarding freight demands, it is assumed that the exact quantity and delivery time windows of each request are known beforehand.

• In addition, we assume that each demand unit corresponds to a package of a standardized small size so that it can fit in robot storage compartments (content, nature and weight of the package are disregarded).

• Finally, we assume that travel and service times are known beforehand and remain unchanged during the planning horizon. replication is assigned to one request, and only that specific request can travel on the assigned scheduled line (Figure 4.2b). As such, the set of all replicated scheduled lines is denoted by F (i.e., { (1a,2a), (1b,2b), (2a,3a), (2b,3b), (3a,4a), (3b,4b), (2a,1a), (2b,1b), (3a,2a), (3b,2b), (4a,3a), (4b,3b) } in Figure 4.2b). Furthermore, the set of replicated SLs associate with request r is given as F r (e.g., in Figure 4.2, F a = {(1a, 2a), (2a, 1a), ..., (3a, 4a), (4a, 3a)}).

In addition, the set of replicated SLs related to the replicated transfer node t is given as F t (e.g. F 1a = {(1a, 2a), (2a, 1a)}). Finally, F ij includes all replicated SLs associated with a physical SL (i, j) ∈ E (e.g. F 1,2 = {(1a, 2a), (1b, 2b)} and F 2,1 = {(2a, 1a), (2b, 1b)}).

Furthermore, each transfer node in S (i.e. nodes 1, 2, 3 and 4 in Figure 4.2a) is copied n times. Hence, we denote the set of all replicated transfer nodes by T (i.e. {1a,1b,2a,2b,3a,3b,4a,4b} in Figure 4.2b). In addition, we use ψ t , ∀t ∈ T as the physical transfer node represented by the replicated transfer node t (e.g. ψ 1a = ψ 1b = 1).

T =
Thus, set T t is {i ∈ T | ψ i = ψ t and i = t}, ∀t ∈ T (e.g. T 2a = {2b} in Figure 4.2b). The proposed pickup and delivery problem can be defined on a digraph G = (N , A) where N = P D T , represents the set of graph nodes (i.e. request origins, destinations and replicated transfer nodes), and A ≡ A 1 ∪ A 2 ∪ A 3 represents the set of feasible arcs connecting different graph nodes, where:

• A 1 = ((P ∪ D) × (P ∪ D)) \ {(r + n, r) : r ∈ P} • A 2 = {(i, j) : i, j ∈ T , (ψ i , ψ j ) / ∈ E} • A 3 = ((P ∪ D) × T ) \ ({(j, r) : r ∈ P, j ∈ T r } ∪ {(r + n, j) : r ∈ P, j ∈ T r })
As can be seen in Figure 4.3, subset A 1 represents arcs linking request origin and destination nodes, subset A 2 represents arcs linking replicated transfer nodes, and subset A 3 links request origin and destination nodes to transfer nodes.

For modeling the problem, we introduce two binary variables; x v ij equals to 1 if arc (i, j) is used by PD robot v and 0 otherwise, ∀(i, j) ∈ A, v ∈ V, and q vw ij equals to 1 if replicated scheduled line (i, j) is used by PD robot v that departs from node i at time p w ij and 0 otherwise, v ∈ V, (i, j) ∈ F i j, w ∈ K ij . In addition, we introduce two timing variables; β i indicates the departure time of a PD robot from node i, and γ v i which indicates the departure time of a PD robot v ∈ V from replicated transfer node i (notations and variables used in this chapter are summarized in Table 4.1). As the problem has been described and basic variables and notations have been introduced, we present the two-stage stochastic model in the following two subsections.

The first-stage model

M in

(i,j) ∈ A v ∈ V θ v t ij x v ij + E [ Q ( δ ,
v ∈ V Q ij Capacity of scheduled line (i, j) ∈ E. Q v Capacity of PD robot v ∈ V. o v Origin location of PD robot v ∈ V. t ij
Travel time from node i to node j. s i Service time at node i.

Decision variables:

x v ij = 1 if arc (i, j
) is used by robot v, and 0 otherwise. q vw ij = 1 if replicated scheduled line (i, j) is used by robot v that departs from node i at time p w ij , and 0 otherwise.

Timing decisions: β i

Departure time of a robot from node i. γ v i departure time of robot v ∈ V from transfer node i.

x v ij = 1 ∀j ∈ P ∪ D (4.2) i∈N x v ovi ≤ 1 ∀v ∈ V (4.3) i∈N v∈V x v it ≤ 1 ∀t ∈ T (4.4) j∈N x v ij - j∈N x v ji = 0 ∀i ∈ N , ∀v ∈ V (4.5) t∈T x v it - t∈T x v tj = 0 ∀v ∈ V, ∀(i, j) ∈ P × D (4.6) t ij x v ij ≤ δ v ∀i, j ∈ N , ∀v ∈ V (4.7)

Capacity constraints

i∈T v∈V

d j x v ij ≤ Q v ∀j ∈ P (4.8) Scheduling constraints v∈V x v ij = 1 =⇒ β j ≥ β i + t ij + s j ∀i, j ∈ N (4.9)
β r+n ≥ β r + t r,r+n + s r+n ∀r ∈ P (4.10)

e i ≤ β i -s i ≤ l i ∀i ∈ P ∪ D (4.11)
Synchronization constraints

w∈K ψ i ,ψ j q vw ij = x v ij ∀v ∈ V, (i, j) ∈ F v (4.12) q vw ij = 1 and x v ij = 1 =⇒ γ v i = p w ij ∀v ∈ V, (i, j) ∈ F v , w ∈ K ψ i ,ψ j (4.13)
Decision variable domains

x v ij ∈ {0, 1} ∀(i, j) ∈ A, v ∈ V (4.14) q vw ij ∈ {0, 1} ∀v ∈ V, ∀(i, j) ∈ F v , w ∈ K ψ i ,ψ j (4.15) β i ∈ R + ∀i ∈ N (4.16) γ v i ∈ R + ∀v ∈ V, i ∈ T (4.17)
The objective function (4.1) minimizes the total costs of operating PD robots and the recourse costs incurred by SL capacity violations. In the recourse function, δ is the given routing vector, ξ is the set of scenarios, and η is the cost vector for using the scheduled lines per unit shipped. For the scheduling constraints, constraints (4.9) ensure that if arc (i, j) is used by PD robot v, the departure time of v from node j should be greater than or equal to the sum of v departure time from node i, the travel time from i to j, and the service time at node j.

Precedence relations for each request (i.e. request origins should be visited before their destinations) are considered in constraints (4.10). Constraints (4.11) enforce time window restrictions on request pickup and delivery. In order to synchronize PD robot trips and the scheduled line, constraints (4.12) and (4.13) ensure that the departure time of a PD robot at a transfer node is equal to the SL departure time at that transfer node (i.e. their departures are synchronized).

We note that constraints (4.9) and (4.13) are formulated as implications, and thus, need to be linearized. Using standard linearization techniques, we express them by one or two linear inequalities, as follows:

β j ≥ β i + t ij + s j -M ij (1 - v∈V x v ij ) ∀i, j ∈ N (4.18) γ v i ≤ p w ij + M i (2 -q vw ij -x v ij ) ∀v ∈ V, (i, j) ∈ F v , w ∈ K ψ i ,ψ j (4.19) γ v i ≥ p w ij -M i (2 -q vw ij -x v ij ) ∀v ∈ V, (i, j) ∈ F v , w ∈ K ψ i ,ψ j (4.20)

The second-stage decisions

Due to the uncertainty, the SL capacity might be violated each time a shuttle arrives at a transfer node. This is because passenger demands are unknown by the time of the planning and are assumed to follow a known probability distribution. In other words, the SL service might not be sufficient for the actual passengers demand and PD robots (4.21).

Given the routing solution vector δ, indicating PD robot routes and schedules from the first-stage, the aim of the second-stage is to evaluate this solution over a set of scenarios and calculate the expected recourse cost (E [ Q ( δ , ξ , η ) ]). At this stage, a scenario indicates the realized passengers demand at each departure from a transfer node, and thus, the number of available places for transporting PD robots.

r∈P (a,b)∈F ij q rw ab > Q w ij ∀(i, j) ∈ E, w ∈ K ij (4.21)
Since the number of available places at each shuttle is only revealed upon the shuttle's arrival time at a transfer node, capacity violations might occur at the corresponding transfer node (denoted as failure point). Depending on passenger demand realizations, these capacity violations might occur in two different situations:

• Situation#1 : After picking up a request and bringing it to a transfer node, a PD robot may not be able to take the next SL departure at that transfer node due to the high passenger demand (passengers are prioritized over PD robots).

• Situation#2 : After taking a shuttle to travel between two transfer nodes as part of its trip, a PD robot may need to get off the SL at an intermediate transfer node due to high passengers demand. In this case, the PD robot needs to give its place to one of the passengers who are willing to take the SL at that transfer node.

In both situations, the same capacity violation is obtained: not enough capacity for transporting PD robots with passengers through the SL service. A set of corrective (or recourse) actions needs to be applied in order to recover feasibility, which might lead to additional costs. We consider the following recourse actions to deal with both situations leading to capacity violation outcome. These are:

• Action#1 : If the PD robot cannot take the current departure at the failure point due to high passengers demand, it is transported using the subsequent service of the scheduled line. In other words, the PD robot waits for the next shuttle arriving to the failure point. This recourse action comes with no extra costs as long as waiting the next departure does not violate request delivery time window.

• Action#2 : If waiting the next shuttle departure leads to violating the capacity of the subsequent SL service or request delivery time window. If the distance between failure point and request destination is less than the maximum service distance that the PD robot can handle, the PD robot delivers the request to its final destination by itself. This recourse action implies some additional costs since a PD robot might have to perform a longer trip than planned.

• Action#3 : If none of the first two recourse actions can be applied, the request is served by an outsourced service (a dedicated vehicle). This service transports the request from failure point to its final destination. The extra cost implied by using this outsourced service depends on the distance that the outsourced vehicle has to travel. Another important issue is to rank or schedule PD robots that are waiting to take the scheduled line at one transfer node, according to some criteria. The model needs to decide which PD robots have the priority to be transported in case the realized number of available places in a shuttle is insufficient (situation#1 ). For this purpose, we sort PD robots at each transfer node according to the earliest delivery date of the requests they carry. The PD robot carrying request with the earliest delivery date is thus the first to be transported when a shuttle with available places arrives to the corresponding transfer node. A similar issue appears when some PD robots need to get off a shuttle at an intermediate transfer node to give space to more passengers (situation#2 ). Therefore, the model also needs to determine the order in which PD robots are asked to get off a shuttle at a certain intermediate transfer node. In this latter case, PD robots already in shuttle are sorted according to their latest delivery date (i.e. PD robot carrying request with the latest delivery date has to get off the shuttle first). It is important to mention that we do not consider the case where a PD robot is asked to get off to allow another one (with an earlier delivery date) to take it's place. PD robots are thus asked to get off only to give place to passengers.

To summarize, the recourse function checks if there are capacity violations at each SL departure. In case SL capacity is violated at a given departure, PD robots that are waiting at the corresponding transfer node, referred to as at-node PD robots, are sorted according to the earliest delivery date of their carried requests. In addition, PD robots that are already in-shuttle are sorted according to the latest delivery date of their requests. Then, at-node and in-shuttle PD robots that cannot take the shuttle at the current departure are assigned to the next departure (action#1 ) since it does not imply extra costs. If waiting for the next departure leads to violating the request's time windows, the recourse function checks if some PD robots can deliver their requests from the corresponding transfer node to their final destination (action#2 ).

Finally, the still remaining requests (i.e. that could not be served using neither action#1 nor action#2 ) are outsourced using dedicated delivery vehicles (action#3 ). As a result, depending on actual passenger demand, (i) some at-node PD robots might be able to take SL next departure while others might have to wait, (ii) all at-node PD robots might not be able to take the next shuttle while no in-shuttle PD robots are asked to drop off, or (iii)

all in-shuttle PD robots may have to drop off from the shuttle and join the waiting PD robots at the corresponding transfer node. The algorithm for calculating the recourse cost of a given routing solution is outlined in Figure 4.4 (see also Appendix A.3 for the detailed recourse function).

Solution Approach

In this section, we present our solution approach. This consists of a scenario-based Sample Average Approximation (SAA) framework (Section 4.4.1), and an ALNS-based heuristic, to solve the corresponding SAA problems (Section 4.4.2).

The sample average approximation method

The Sample Average Approximation (SAA) method is an iterative approach for solving stochastic optimization problems. It aims at approximating the expected objective function of the stochastic problem using a sample average estimate derived from a random sample [START_REF] Verweij | The Sample Average Approximation Method Applied to Stochastic Routing Problems : A Computational Study[END_REF]. While the set of possible scenarios might be very large, the SAA iteratively solves the problem using smaller and more tractable sets of scenarios (referred to as SAA problems), and obtains candidate solutions along with their respective optimality gaps.

The method starts by generating a large set of scenarios Ω and iterates until the value of the optimal solution is approximated by solving the stochastic problem with smaller sample sets. At each iteration l, a sample set of scenarios ω l : |ω l | << |Ω| is generated from the larger set Ω and the corresponding SAA problem is solved using the ALNS heuristic. The obtained solution x l with objective value f l ω l is then evaluated using the recourse function in order to determine an upper bound f Ω (x l ) for the generated set of scenarios Ω:

f Ω (x l ) = CalculateRecourseCost(x l , Ω) (4.22)
Afterwards, a statistical lower bound, denoted by f ω l (x l ), for the optimal solution value of sample ω l is calculated by averaging the objective function values obtained in previous iterations:

f ω l (x l ) = 1/l l i=1 f i ω l , (4.23)
where f i ω l is the objective function value obtained at iteration i. To the best of our knowledge, this is the most commonly used approach in the literature for approximating a statistical lower bound in SAA-based methods (see also [START_REF] Verweij | The Sample Average Approximation Method Applied to Stochastic Routing Problems : A Computational Study[END_REF]Ghilas et al., 2016a). Once both bounds are obtained ((4.22),(4.23)), the SAA gap is calculated as follows:

(ω l , Ω) = f Ω (x l ) -f ω l (x l ) (4.24)
The process continues until the best gap (ω, Ω) is found and the corresponding best solution is returned (see Figure 4.5, and Appendix A.5 for the detailed algorithm).

ALNS heuristic

An ALNS heuristic algorithm is used to generate routing solutions of minimum total cost. The heuristic is used in combination with the recourse function (Algorithm 3) in order to compute the recourse cost of a generated solution. The main idea of the ALNS is to iteratively apply a set of removal and insertion operators on an initial solution until the best solution is found (Figure 4.6). The algorithm starts by generating an initial solution indicating initial PD robot routes.

The algorithm then applies a removal operator to remove one PD route from the initial solution. The removed PD route is then reconstructed and reinserted to the solution using an insertion operator and a new solution is obtained. The operators are dynamically selected according to their past and current performances through a roulette-wheel mechanism. In other words, each operator, removal or insertion, is associated with a score that is increased at each time this operator leads to a better solution, and a probability that indicates how likely this operator is to be selected in the next iteration. This means that operators with better scores have a higher probability to be used by the algorithm. In order to build their scores, operators are selected randomly in the first 100 iterations. The roulettewheel mechanism is then used based on the calculated operator scores. Once applying these operators yields an improvement, the new solution is stored, and the best solution is updated. The algorithm continues until either a maximum number of iterations or a certain number of iterations with no improvement is reached (see Appendix A.4 for the detailed algorithm).

Generating initial solutions:

Since we use simplified problem settings, in which only one pickup/delivery per PD robot trip is allowed, we start with a simple heuristic to generate initial feasible solutions. This heuristic is composed of two main steps:

1. We start by selecting requests that can be delivered directly by a PD robot depending on the distance between their origin and destination locations (direct delivery). These direct PD robot routes are then added to the initial solution.

2. For the other requests (indirect delivery), indirect PD robots are constructed by randomly assigning them to one of the feasible pickup/drop-off transfer nodes while respecting their time restrictions.

To this end, the feasibility of the returned solution, in terms of request time windows and SL departure times, is assured. This initial feasible solution can then be improved by the ALNS operators as it does not lead to min-cost PD robot routes. We describe the removal and insertion operators used by the ALNS algorithm in the following subsections.

Removal operators:

• Random removal (R1): This operator removes a randomly selected robot route (request) from the solution which helps in diversifying the search for a better solution.

• Limited random removal (R2): This operator is similar to R1 but it limits the number of times a robot route (request) is removed in the last 100 iterations. For other requests, which their counts have not reached the specified limit, R1 is applied.

• Tabu-based removal (R3): This operator also keeps a record of robot route removal counts for the last 100 iterations (as R2 ) and removes those with the smallest frequency of removal rate. This operator also helps in diversifying the search.

• Early-SL-depart removal (R4): This operator removes the robot route with the shortest waiting time at the pickup transfer nodes from the solution. The request waiting time at a specific transfer node is obtained from the difference between its arrival to that transfer node and its departure from it (i.e. a PD robot might have to wait at a transfer node until the next SL departure).

• Late-SL-depart removal (R5): Unlike R4, this operator removes the robot route with the longest waiting time at transfer nodes from the solution.

Insertion operators:

• Pickup Transfer-node insertion (I1): This operator reconstructs a robot route by assigning it to a different pickup transfer node than the one it was assigned to before being removed. This operator helps diversifying the search by leading to different transportation costs (i.e. operational and recourse costs). This potential improvement highly depends on SL and PD robot transshipment costs as well as the maximum service distance of PD robots which can limit the feasibility of this assignment.

• Drop-off Transfer-node insertion(I2): This operator reconstructs a robot route by assigning it to a drop-off transfer node that is different than the one it was assigned to before being removed. Similar to I1, this operator can lead to different transportation costs.

• Early-SL-depart insertion (I3): This operator reconstructs a robot route by assigning it to the same pickup transfer node but with an earlier departure time. Indeed, changing the SL departure to which a PD robot is assigned, leads to different recourse costs as passengers demand varies between different SL departures.

• Late-SL-depart insertion (I4): Unlike I3, this operator reconstructs a robot route by assigning it to the same pickup transfer node but with a later departure time. This operator is also important for solving the stochastic optimization problem as it leads to different recourse costs.

That said, these operators are used by the heuristic to remove and insert robot routes to a current solution. They provide a reasonable choice for our problem settings where only one request is served during a PD robot trip. The heuristic can thus be extended by considering different operators when PD robots are allowed to perform multiple pickups and deliveries at one trip (see operators at Ghilas et al., 2016b;Ghilas et al., 2016a).

Computational study

In this section, an extensive computational study to assess the performance of the proposed solution approach is presented. First, we explain how we generate test instances and we describe the different parameters used (Section 4.5.1). We then show how we generate the set of scenarios used by the SAA algorithm for solving the stochastic problem (Section 4.5.2). Afterwards, we analyze the performance of the proposed heuristic approach along with the different operators used, and compare the results obtained from solving the stochastic problem with those of the deterministic one (i.e. when no uncertainty is considered). Finally, we study the impacts of the considered source of uncertainty on the obtained solutions with different settings (Section 4.5.3).

Parameters and instance generation

For testing the proposed solution approach, we generate instances with different network topologies and freight request distributions. Generated instances are named as P_D_r_n,

where P represents the network topology, D is the geographical distribution of freight requests, r is request nodes range from transfer nodes, and n is the number of freight requests.

Since the proposed model can adapt different network topologies, we generate instances with line (referred to as "L") and triangular (referred to as "T") topologies (Figure 4.7a & 4.7b).

While the number of SLs is different, instances with either topology have the same char- We consider a planning horizon of 600 time units where SL departure interval is set to 30 time units (i.e. there is a shuttle departing from each transfer node every 30 time units). We consider that this frequency is enough to cover passengers demand through SL.

We The capacity of each PD robot and the quantity of each freight request are set to 1.

This means that each PD robot can serve one freight (i.e. any freight request) at a time.

The capacity of shuttles on SL is set to 10 places for both passengers and PD robots where PD robots can take up to 3 places (different limits are analyzed in section 4.5.3). Regarding transportation costs, we assume the time unit cost for PD robots to be 0.5 unit. This cost includes energy consumption, insurance and transportation expenses induced when PD robots are used. In addition, the time unit cost of using SL service is set to 1 unit. This cost includes loading, unloading, and transportation expenses each time a PD robot uses the SL service. Finally, the recourse cost of using the outsource delivery service is assumed to be 3 units (different SL and robot shipment costs were analyzed in Ghilas et al., 2016b).

As introduced in section 4.4.2, we consider two stopping criteria for the heuristic method.

These are: the maximum number of ALNS iterations which is set to 10 000 iterations, and the maximum number of consecutive iterations with no improvement which is set to 50 iterations. In addition, the score of an operator is increased by 1 if it leads to improving the current solution, and by 3 if a new best solution is found. For the SAA algorithm, the size of the large set of scenarios (Ω) is set to 10 000 scenarios while the size of the smaller sample (ω) is set to 50 scenarios. Finally, the number of SAA iterations is set to 10 (SAA parameters are fixed based on (Li et al., 2016b;Ghilas et al., 2016a) where similar problems and solution methods are considered). The set of parameters used in the computational study along with their values are presented in Table 4.2.

Scenario generation

In order to test the proposed SAA algorithm, we need to generate a large set of scenarios which represent the realized passengers demand at each SL departure. The actual passengers demand helps the algorithm to decide whether PD robots can be transported through SLs or some recourse actions need to be applied. For this purpose, passengers demand is assumed from S 2 to S 3 as there are no available places for them, while there are 3 available places at the fourth departure etc.

Experiments

The algorithms developed in this paper (i.e. recourse, ALNS and SAA algorithms) are implemented in Java 1.8.0. CPLEX 12.6 solver is used for solving the MIP formulation. Instances are tested on a quad-core i5-5300U machine with 8 GB of RAM. We study the efficiency of the proposed ALNS approach by comparing its results to those obtained with CPLEX solver and analyzing the performance of its operators. We then examine the stochastic solutions obtained by the SAA algorithm, compare them with the deterministic ones, and analyze the impact of different levels of passengers demand, SL frequency and capacity on the obtained solutions.

Analyzing ALNS performance:

The results of solving instances with up to 100 freight requests are presented in Looking at table 4.3, we observe that the proposed ALNS is always able to find a solution that is identical to the optimal one obtained by solving the MIP in terms of direct and indirect deliveries. In addition, the ALNS is able reach the optimal solutions (Gap = 0) for all instances with less than 40 freight requests. For instances with more than 40 requests, the ALNS is still capable of finding solutions that are within 0.6% of the optimal solutions.

Moreover, the proposed heuristic returns solutions for instances with 100 requests for which CPLEX is not able to find optimal solutions. This is due to the increasing complexity of the problem (i.e. number of variables) when the number of freight requests gets larger. Since the numbers of direct and indirect deliveries are the same in both solutions, this small gap indicates that there are very few requests that could have been assigned to another pickup or drop-off transfer node so that some costs can be saved. We also observe that total costs are generally lower for instances with clustered request distribution (L_C & T_C). This can be explained by the likelihood of performing direct deliveries which is higher in clustered instances, while requests are more scattered in randomly distributed instances (Table 4.3, "# dir."). This can also be reflected by the increasing number of unserved requests in randomly distributed instances. In this latter case, some requests cannot be brought to transfer nodes due to PD robot distance limitations. Another observation is that the total costs are generally higher in line networks than in triangular ones. This indicates that a triangular network might provide a better coverage to the service area while reducing transportation costs.

The base case instances, with 10 freight requests, solve in few seconds with CPLEX.

This amount of time increases as the number of freight requests increases. We observe that instances with line network topology need longer time to be solved to optimality than those with triangular topology (an average of 6.3 mins for triangular instances with 60 requests compared to 39.5 mins for same instances with line topology). The reason is that the number of transfer nodes, and thus the number of variables and graph edges, is bigger in instances with line topologies. This observation also gives an indication that a triangular network topology might be more effective in terms of computational efforts needed to solve its instances. On the other hand, the proposed heuristic solves the different instances in very short running times (1.38 seconds in average) while maintaining near-optimal solutions.

These short running times suggest that our approach is suitable for approximating optimal solutions for the stochastic problem where instances have to be solved over a large set of scenarios in the SAA method. Considering removal operators (Table 4.4), we observe that operators R1, R2 and R3 are the most frequently used. This is mainly because these three operators randomly select robot routes (requests) and are used to diversify the search for a better solution.

We also observe that I1 and I2 are the most frequently used insertion operators (Table 4.5). This indicates that operators which assign robot route to an earlier, or later, SL departure (i.e. I3 and I4) are used less than other operators which assign it to a different pickup, or drop-off, transfer node.

Analyzing SAA performance and stochastic solutions:

In order to quantify the impact of stochastic passengers demand, we solve the instances, introduced earlier in Table 4.3, using the proposed SAA algorithm. Results are presented in Table 4.6 where the first three columns represent the usage frequency of recourse actions 1, 2, and 3 (respectively) as a percentage of the total number of times recourse actions were used for each instance. The total transportation cost is then given along with the associated operational and recourse costs. The additional cost induced by uncertainty is then calculated by comparing the total cost of the stochastic solution with that of solving the deterministic version of the problem using the heuristic (given in Table 4.3).

In table 4.6, we observe that the realization of passengers demand can add an average of 3.3% to the total transportation cost. This increase is due to the recourse actions that are used to correct the interrupted robot routes. Indeed, when passengers demand is revealed, the actual number of places for PD robots at each SL departure might not be sufficient and recourse actions need to be applied adding extra expenses to the total transportation cost.

Since the recourse function applies recourse actions one by one to recover feasibility, one can observe that action#1 is the most frequently used among the other recourse actions (93.6% in average). This is because this recourse action uses the subsequent SL service (i.e. waiting the next SL departure) which does not imply additional transportation costs. We also observe that action#2 is not frequently used by the algorithm (only 1.1%). This indicates that a direct PD robot delivery, from failure point to request destination, is not feasible in most of the time due to PD robot distance limitations. Most of the added recourse costs are thus induced by action#3 as it guarantees the feasibility of all interrupted deliveries using the outsourced service. Regarding network topology, we observe that the average added cost for instances with line topology is lower than those with triangular topology (2.5% compared to 3.8%). This is because the number of stations in triangular network is less than that of the line network. As a consequence, the number of PD robots at each station is larger in a triangular network and the likelihood of applying recourse actions (i.e. to recover capacity violations at each SL departure) is thus higher. We analyze in the following the impacts of uncertainty under different settings including passengers demand and SL frequency and capacity.

Analyzing uncertainty with different levels of passengers demand

In the original setting, we generate SAA scenarios assuming that passengers demand follows a discrete triangular distribution with a mean value b = 6 (Figure 4.8a). In this section, we analyze the different levels of passengers demand by testing the algorithm with different mean values (b = 2, 4, 6&8 respectively). As the mean value increases, the probability of having a large passengers demand at each SL departure becomes higher. This reflects a real-life case where passengers demand changes over day hours which can limit the integration of PD robot deliveries into the system. The aim of this analysis is thus to investigate the potential impact of these different levels of passengers demand. This is done by performing ten runs of the algorithm for each demand level and taking the average (Figure 4.9). Results show that the total transportation costs increases as passengers demand becomes higher (Figure 4.9a). This increase is mainly induced by the recourse actions that are used more frequently. Relatively, the average added costs slightly increase from 3.14% to 3.39% when passengers demand level goes from 2 to 8 (Figure 4.9b). These observations are important for two main reasons. First, the increasing transportation costs indicate that allowing PD robots to be transported with passengers through SLs might not always be efficient when passengers demand is high (e.g. morning and evening peak hours). In other words, this combination can prove most efficient during day hours when the probability of having free places in SLs is bigger. Second, the use of the outsourcing delivery service (action#3) will increase in peak hours as the subsequent service might also be fully charged with passengers. This means that road traffic can increase as more vehicles are circulating in the system to deliver freight requests that could not be transported using SL service.

However, SL combined service still yields many benefits compared to existing freight delivery services, but these benefits can be maximized in off-peak hours.

Analyzing uncertainty with different SL frequencies:

As aforementioned, we consider the SL departure frequency to be 30 time units. We investigate in this section the impact of SL frequency on the total transportation cost. For this purpose, we run the algorithm with SL frequency of 20, 30, 40, 50 and 80 time units and we take the average of ten runs of the algorithm for each SL frequency (Figure 4.10).

We observe that the total transportation costs increases as SL departures become less frequent. This can be explained by the fact that less frequent SL departures lead to more PD robots waiting at each transfer node which means a higher possibility of having SL capacity violations (Figure 4.10a). On the other hand, with a more frequent SL service (e.g. 20 time units), the total costs decreases as less recourse actions are needed. This can also be observed by looking at the average added costs with different SL frequencies (Figure 4.10b). While increasing the SL frequency to 20 time units can reduce the added costs (up to 0.09%) compared to the original ones, decreasing the frequency can yield a slightly increasing added costs (up to 0.03%, 0.11% and 0.21% for 40, 50 and 80 SL frequencies respectively). However, increasing SL frequency might also lead to additional costs for SL operators as more shuttles are circulating in the system (e.g. energy, driver wages etc.).

Although freight transportation costs can be decreased by making SLs more frequent, it might not be profitable for SL operators especially at passengers off-peak times. On the other hand, reducing SL frequency can also lead to many passengers left unserved at SL stations. To conclude, increasing, or decreasing, SL frequency need to take into account the varying levels of passengers demand.

Analyzing uncertainty with different SL capacities:

As introduced earlier, we assumed that PD robots can take up to 3 places in shuttles.

In this section, we investigate the effect of changing the maximum number of places allowed for PD robots on the total transportation costs. As such, we take the average of ten runs of the algorithm with up to 5 maximum places (Figure 4.11).

Looking at the obtained results, we observe that allowing more PD robots at each SL departure has a positive effect in terms of the total transportation costs and the average added costs. This positive effect is justified by a lowering of 0.07% and 0.1% on the added costs when up to 4 or 5 PD robots are allowed at each SL departure. This means that with an extra capacity for PD robots, stochastic solutions become cheaper and less capacity violations can be encountered. However, this might also have a negative effect on the number of PD robots that have to get off at an intermediate transfer node where passengers demand is high leading to many waiting PD robots at that node.

Conclusion

In this chapter, a transportation service that combines passenger and freight flows has been studied. The associated optimization problem has been formulated as a pickup and delivery problem with time windows, scheduled lines (PDPTW-SL) and stochastic passengers demand. An MIP formulation along with ALNS-based heuristic approach have been introduced. For dealing with uncertainty, a sample average approximation method and a recourse algorithm have been developed. An extensive computational study to evaluate the performance of the proposed approaches and their different components has been presented.

Results of testing instance with up to 60 freight requests showed that the proposed heuristic approach can return solutions that are within 0.6% of the optimal solutions. The analysis also revealed that an average of 3.3% extra costs can be observed when stochastic passengers demand is realized. These additional costs reflect the effect of uncertainty on the total transportation costs. Analyzing the impact of different SL frequencies and capacities, the results demonstrated the positive effect of increasing the frequency of SL departures and the maximum capacity for PD robots on the system.

Since we build our analysis on a set of assumptions that simplify the problem, there are still a number of challenges facing the deployment of such integrated transportation system.

Here we outline some directions for future research: (1) We assumed in this chapter that each PD robot can only serve one freight request at a time due to the complexity of the considered problem. A more realistic setting would be to allow multiple request pickup and delivery per PD robot trip. This gives rise to the challenge of coupling, or synchronizing, both pickup and delivery routing problems as the same PD robot performs them. (2)

Another interesting direction would be to study the impact of such integrated service on passenger transportation on a daily horizon in which their demand varies during day hours.

Finally, (3) Since we consider one source of uncertainty in this chapter, which is passengers demand, it is also important to look at other sources of uncertainty like travel times. As PD robots are operating in an urban area, many external factors might affect their travel time and speed. We believe that this study helps in a better understanding of the potential deployment of such integrated systems, and thus, promote more research towards studying this emerging trend in city logistics and transportation.

Chapter 5

Conclusions

In this chapter, we summarize the key findings and main contributions of the thesis. In addition, we take the aforementioned research questions one by one and we show how they were addressed. We also describe how addressing these research questions has contributed to the fulfillment of the overall research objective of the thesis. We then highlight the main challenges facing research in this area and suggest potential directions for future research.

Key findings and contributions

In dense urban areas, where there is a wide variety of public and private transportation services (e.g. bus, taxi, metro, tram, bike etc.), passenger and freight flows overlap to a significant extent. This lack of synchronization between different transportation flows is increasing traffic congestion and pollution levels in already congested and polluted urban areas. This issue becomes more critical when we take into account the increasing urbanization rates and the growing demand for urban transportation. With the introduction of new technologies and innovative mobility systems, such as autonomous vehicles and crowd-sourced delivery services, the need for new shared mobility systems becomes more essential. These systems have the potential to enhance the quality of the service provided while reducing its negative effects from the operational, economical and environmental aspects.

To cope with this reality, this thesis aims at giving a deeper understanding and a wider overview of the actual opportunities and challenges facing the development of shared mobility systems, and at the same time, developing models and optimization methods that can deal with their synchronization issues. In the following, we describe how the different research questions were addressed along with their contribution to the overall objective of the thesis.

Research question 1: What are the different variants of shared mobility systems and what methods are used to optimize them?

In chapter 2, a thorough insight on the different variants of shared mobility systems is given. This review covers mobility systems where people share their rides and mobility systems where people and goods streams are combined. The chapter also provides an extensive study of their constraint types and objectives along with modeling and solution approaches that are used to operate them. The latest trends in shared mobility (e.g. autonomous mobility, combined freight delivery and others) are then investigated and the recently-published papers and case studies are summarized in overview tables. The review provided in this chapter highlights some research gaps that we believe more research is needed to address them. For example, considering synchronization issues in shared mobility models, operating autonomous vehicles in a ridesharing context, integrating freight delivery to passenger transportation with stochastic aspects, and others. This helps us in identifying some interesting directions for our research.

Research question 2: How can people trips be synchronized in a ridesharing system with autonomous vehicles and what gains can this synchronization yield?

Based on the review provided in chapter 2, in chapter 3 we study a ridesharing system where individually-owned and on-demand autonomous vehicles (AVs) are used for transporting passengers. Passenger trips are synchronized using the concept of meeting points which indicate where riders can be picked up and dropped off during a shared trip. We propose in this chapter a two-phase approach for matching potential participants in shared trips. The proposed approach consists of, first, an algorithm for generating the set of feasible matches that respect time restrictions of the participants, and second, a matching optimization problem for selecting the best among them. Through a case study on New York City, the obtained results demonstrate that an average of 21% saving in terms of system-wide vehicle-miles can be achieved when passenger trips are shared (i.e. synchronized). The results also show that a system, in which on-demand AV service is partially or fully used and shared, has a better performance than a system in which only individually-owned AVs are used. This observation is important for AV operators as it helps them in building their future automated services.

Research question 3: How can people and freight flows be combined and what are the impacts of stochastic passenger demands on planning such a combined system?

In chapter 4, we consider the problem of synchronizing passenger and freight flows in urban areas. In order to tackle this problem, we study a transportation system in which the delivery of small parcels is integrated into a scheduled line service (SL) for passenger transportation. For solving the problem, we propose a MIP formulation that contains a set of routing, timing and synchronization constraints. We then develop an ALNS-based heuristic method that uses a set of removal and insertion operators to enhance an initial solution.

Results of testing instances with up to 60 freight requests demonstrate the efficiency of the proposed approach as it can return solutions that are within 0.6% from the optimal ones. In order to study uncertainty, we consider that passengers demand is stochastic. This means that the actual number of available places for transporting freight with passengers is only revealed upon SL departures. We develop a sample average approximation method that can deal with this stochastic aspect and quantify its effects on the system. We study the impact of uncertainty by comparing the obtained stochastic solutions to the deterministic ones, and analyzing different SL capacities for transporting freight. The analysis suggests that an average of 3.3% extra costs can be observed when stochastic passengers demand is realized which reflect the effect of uncertainty of the total transportation costs. Results also indicate the positive effect of allowing more SL capacity for transporting freight.

Research objective: Develop efficient models and optimization approaches for synchronizing people and freight flows in urban mobility systems.

As aforementioned, this thesis aims at studying shared mobility systems and developing efficient approaches for operating them. In order to better understanding the concept of shared mobility, the thesis provides a detailed classification and an comprehensive overview of its variants based on their features, context of application, objectives, characteristics, models and solution methods. Then, the problem of synchronizing passenger and freight flows is tackled by studying two different transportation systems. For both systems, the focus is on developing heuristic approaches that are able to find near-optimal solutions at short computational times. As shown throughout the thesis, the results of testing the proposed systems show the potential gains that can be obtained when passenger and freight flows are synchronized. We believe that these gains can give an important indication for service operators as the proposed systems are not yet fully operational in real-life and more research is still needed to quantify their benefits.

It is also important to mention that the proposed systems do not aim at replacing the existing services for passenger and freight transportation. In contrast, they represent an opportunity to complement them and open the door towards a new generation of shareable and sustainable systems of transportation. For example, shared AVs are not expected to replace public transport or eliminate private car ownership, but they might provide a supplementary service in city centers where private cars usage is limited. Similarly, integrating the use of small robots for last-mile delivery with a scheduled transportation service might not affect passenger transportation but can reduce delivery trucks movements in urban areas.

Challenges

There is a set of challenges that are facing shared mobility systems and limiting their deployment. These challenges are mainly due to the complexity of real-life systems and the need for relevant regulations and infrastructures to accommodate them. Due to this complexity, we made some assumptions throughout the thesis to simplify the considered problems and can still represent the reality.

In chapter 3, we assume that an individually-owned AV can serve other travelers while its owner does not need it. This assumption might rise many questions regarding security and maintenance issues (e.g. cleaning AV after each use). We also assume that passengers demand is known in advance. In order to establish a successful AV service, such a system must be able to match passengers on-the-fly and at very short service times. In such realtime service, uncertainty in travel times (i.e. due to traffic congestion, accidents, etc.) and recharging operations also need to be considered when building such a system. Similarly in chapter 4, assuming that PD robots can use SL service with passengers means that SL shuttles and stations need to be equipped with loading and offloading infrastructure that allows this process to take place. In addition, such a combined service is limited to small parcels which might also rise a security issue. As for uncertainty, we assume that passengers demand at each SL departure to be stochastic while freight request quantities and robot travel times are known in advance. These different stochastic aspects might represent a challenging issue that limits the deployment of such a combined service in congested urban areas.

Generally, planning shared mobility systems become more complex when more realistic problem settings are considered. The number of transportation units (e.g. AVs, SLs, PD robots, etc.), the number of transportation requests to be served, and the availability of transportation resources, all represent important determinant in the complexity of the considered problem, and relatively, the approach used to solve it. While studying simplified for each transfer node t in S do 6: let W t be the set of PD robots waiting at transfer node t: W t ⊂ P 7:

for each scheduled departure p w t,t+1 at t do 8:

let I w t be the set of PD robots already in shuttle at p w t,t+1

9:

rank PD robots in W t according to their requests earliest due dates Question 3: Comment combiner les flux de passagers et de fret et quels sont les effets de l'incertitude sur ces systèmes? Au chapitre 4 (Chapter 4), nous considérons le problème de la synchronisation des flux de passagers et de marchandises dans les zones urbaines. Afin de résoudre ce problème, nous étudions un système de transport dans lequel la livraison de petits colis est intégrée à un service de navette pour le transport de passagers. Ensuite, nous proposons une formulation mathématique contenant un ensemble de contraintes de routage, du temps, et de synchronisation. Nous développons par la suite une méthode heuristique de recherche de voisinage (ALNS) qui utilise un ensemble d'opérateurs de suppression et d'insertion pour améliorer une solution initiale. En testant des instances contenant jusqu'à 60 demandes de fret, les résultats démontrent l'efficacité de l'approche proposée, car elle permet de trouver des solutions à moins de 0.6% des solutions optimales. En outre, pour tenir compte de l'incertitude, nous considérons que la demande des passagers est stochastique. Cela signifie que le nombre réel de places disponibles pour le transport de fret n'est révélé qu'au moment du départ des navettes. Nous développons donc une méthode d'approximation (Sample Average Approximation SAA) capable de traiter cet aspect stochastique et de quantifier ses effets sur le système. Nous étudions ensuite l'impact de cette incertitude en comparant les solutions stochastiques obtenues aux solutions déterministes et en analysant les différentes capacités de navette pour le transport de fret. L'analyse suggère qu'une moyenne de 3.3% de coûts supplémentaires peut être observée lorsque la demande stochastique de passagers est réalisée, ce qui reflète l'effet de l'incertitude des coûts de transport généraux. Les résultats indiquent également l'effet positif de permettre une plus grande capacité dans les navettes pour le transport de fret. The rise of research into shared mobility systems reflects emerging challenges, such as rising urbanization rates, traffic congestion, oil prices and environmental concerns. The operations research community has turned towards more sharable and sustainable systems of transportation. Although shared mobility comes with many benefits, it has some challenges that are restricting its widespread adoption. More research is thus needed towards developing new shared mobility systems so that a better use of the available transportation assets can be obtained. This thesis aims at developing efficient models and optimization approaches for synchronizing people and freight flows in an urban environment. First, we review different variants of the shared mobility problem where either travelers share their rides, or the transportation of passengers and freight is combined. We then classify these variants according to their models, solution approaches and application context and we provide a comprehensive overview of the recently published papers and case studies. Based on this review, we identify two shared mobility problems, which we study further in this thesis. Second, we study a ridesharing pro-blem where individually-owned and on-demand autonomous vehicles (AVs) are used for transporting passengers and a set of meeting points is used for synchronizing their trips. We develop a two-phase method (a pre-processing algorithm and a matching optimization problem) for assessing the sharing potential of different AV ownership models, and we evaluate them on a case study for New York City. Then, we present a model that integrates freight deliveries to scheduled lines for people transportation where passengers demand, and thus the available capacity for transporting freight, is assumed to be stochastic. We model this problem as a two-stage stochastic problem and we provide a MIP formulation and a sample average approximation (SAA) method along with an Adaptive Large Neighborhood Search (ALNS) algorithm to solve it. We then analyze the proposed approach as well as the impacts of stochastic passengers demand on such integrated system on a computational study. Finally, we summarize the key findings, highlight the main challenges facing shared mobility systems, and suggest potential directions for future research.

Universit é Paris-Saclay

Espace Technologique / Immeuble Discovery Route de l'Orme aux Merisiers RD 128 / 91190 Saint-Aubin, France

( a )

 a Figure 1.1: Urban passenger and freight demand -2050 projection (OECD, 2017)

Figure 1 . 2 :

 12 Figure 1.2: Main categories of shared mobility systems

  Chapter 2: A. Mourad, J. Puchinger and C. Chu, A survey of models and algorithms for optimizing shared mobility, Transportation Research Part B, 2019. https://doi.org/10.1016/j.trb.2019.02.003. Chapter 3: A. Mourad, J. Puchinger and C. Chu, Owning or sharing autonomous vehicles: comparing different ownership and usage scenarios, Minor revision in European Transport Research Reviews, 2019 Chapter 4: A. Mourad, J. Puchinger, T. Van Woensel, Integrating autonomous delivery service into a passenger transportation system, Submitted to International Journal of Production Research, 2019 In addition, the different elements of the research conducted in this thesis are presented in the following conferences: A. Mourad, J. Puchinger, C. Chu. Privately owned autonomous vehicles in a ride-sharing application. 18ème Conférence annuelle de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF), 2017, Metz, France. A. Mourad, J. Puchinger, C. Chu. Owning or sharing autonomous vehicles: comparing different ownership and usage scenarios. Vehicle Routing and Logistics optimization (VeRoLog), 2017, Amsterdam, Netherlands. A. Mourad, J. Puchinger, T. Van Woensel. Combining people and freight flows using a scheduled transportation line with stochastic passenger demands. 20ème Conférence annuelle de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF), 2019, Le Havre, France. A. Mourad, J. Puchinger, T. Van Woensel. Combining people and freight flows using a scheduled transportation line with stochastic passenger demands. 7th INFORMS Transportation Science and Logistics Society Workshop (TSL), 2019, Vienna, Austria. O. Al Maghraoui, R. Vosooghi, A. Mourad, J. Kamel, J. Puchinger, F. Vallet, B. Yannou. Shared Autonomous Vehicle Services and User's Taste Variation: A Survey and Model Applications. 22nd EURO Working Group on Transportation Meeting (EWGT), 2019, Barcelona, Spain.

Figure 2 . 1 :

 21 Figure 2.1: Shared mobility -Problem variants

  tonomous vehicles. Such methods consist of finding a path between different locations and determining the safest and most feasible itinerary.[START_REF] Hyland | Taxonomy of Shared Autonomous Vehicle Fleet Management Problems to Inform Future Transportation Mobility[END_REF] introduced a taxonomy for classifying vehicle fleet management problems to inform future research on autonomous vehicle fleets. Their paper reviewed the existing categories to classify scheduling and routing problems, then refine some of them as they relate to the AV fleet problem, and proposed novel taxonomic categories for classifying AV fleet management problems.[START_REF] Kümmel | Framework for automated taxi operation: The family model[END_REF] proposed a framework for AVs based on the model of a family (where the father is provider of physical services, the mother is strategic manager, and the children are individual AVs). In this decentralized model, vehicles are allowed to inter-negotiate while the fleet manager can set fleet strategies and pre-allocate vehicles to locations where increasing demand is expected. In another framework for modeling shared AVs,[START_REF] Levin | A general framework for modeling shared autonomous vehicles with dynamic network-loading and dynamic ride-sharing application[END_REF] proposed a heuristic for dynamically constructing shared rides using AVs. The proposed approach consists of a dispatcher that checks whether there is any AV that is already located or en route to where a travel demand has appeared and then assigns the AV to carry the longest-waiting traveler. Furthermore, other travelers are allowed to join the shared trip if they are traveling to the same or close-enough destination, although priority remains with the travelers already in the vehicle. Alonso-Mora et al., 2017 proposed a mathematical model for a large-scale real-time ridesharing system that dynamically finds optimal routes for vehicles serving online requests while taking into account their actual locations. Their algorithm, which applies to fleets of AVs, uses constrained optimization to improve an initial greedy assignment and return good quality-solutions that converge to the optimal assignment over time. In addition,[START_REF] Pimenta | Models and algorithms for reliability-oriented Dial-a-Ride with autonomous electric vehicles[END_REF] considered a dial-a-ride system in which a set of small AVs operates between different sections in a closed industrial site. For routing decisions, the paper proposes a heuristic approach based on GRASP and an insertion mechanism. Another study, byMa et al., 2017, introduced a linear programming model for an AV sharing and reservation (AVSR) system in which travelers book AVs in advance and the system arranges their routes and schedules. Chen et al., 2017 studied potential use of AVs and presented a mathematical framework for designing AV zones in a general network. The paper also provides a numerical study to demonstrate the performance of the proposed model.

  conducted a study to evaluate a rule-based dispatching algorithm that manages a fleet of shared taxis based on data collected by local taxi services in Berlin and Barcelona. Results indicated that despite its simplicity and efficiency, rule-based dispatching suffers from a limited planning horizon. Linares et al., 2017 studied a dynamic ridesharing system architecture that considers the Metropolitan area of Barcelona as a case study, and. results showed that this transportation mode has the potential to reduce traffic flow and pollution levels in big cities while offering travelers shorter travel times.Using data collected by surveying more than 500 respondents in Turin and Rome,[START_REF] Gargiulo | Dynamic Ride Sharing Service: Are Users Ready to Adopt it?[END_REF] tested and evaluate a dynamic ridesharing service called VirtualBus.They found that users' main concerns were privacy, trust, and reliability of planning. More recently,[START_REF] Wang | How much is trust: The cost and benefit of ridesharing with friends[END_REF] investigated the cost and benefits of ridesharing with friends through a study on travel demands in the Yarra Ranges (Australia). Their study revealed that limiting ridesharing to friends while rejecting strangers might reduce ride choices and increase detour distances but it does not generate significantly higher costs. Furthermore, prioritizing friends can substantially increase matching rate. In an effort to understand how urban parameters affect the fraction of individual trips that can be shared (or 'shareability'),[START_REF] Tachet | Scaling Law of Urban Ride Sharing[END_REF] conducted a study based on millions of taxi trip records in New York City, San Francisco, Singapore and Vienna with the aim of computing the shareability curves for each city.Other case studies have focused on studying ridesharing system impacts on existing transportation systems. Martinez, 2015 used a simulation-based procedure to evaluate the impacts of introducing a shared-taxi system in Lisbon.[START_REF] Barann | An open-data approach for quantifying the potential of taxi ridesharing[END_REF] conducted another study using more than 5 million taxi trips in New York City and found that ridesharing could potentially save over 2 million kilometers of travel distance per week, which would significantly decrease CO 2 emissions. Similarly,[START_REF] Yu | Environmental benefits from ridesharing: A case of Beijing[END_REF] evaluated the direct environmental benefits of ridesharing in Beijing, and found that it enabled energy savings, distance savings, and lower CO 2 emissions.Stiglic et al., 2016b studied the impact of driver and rider flexibility in an enhanced dynamic ridesharing experience and found that suggested driver and rider flexibility on departure/arrival times was important to ridesharing system success, but that driver flexibility in terms of accepting detours was even more important. Thus, the benefits and positive impacts of ridesharing are linearly correlated to the flexibility of ridesharing participants.

  now have two decades of extensive research into ridesharing systems, but little research on autonomous mobility services for future transportation systems. To fill this gap, a number of recent studies have focused on new driverless services and their potential impacts on urban mobility. Gruel and Stanford, 2016 identified the long-term effects of introducing driverless cars and explored the conditions that would make them beneficial or damaging in transportation systems. The study also investigated how automation could increase the attractiveness of traveling by car. Smolnicki and Sołtys, 2016 studied different autonomous mobility solutions and discussed their impacts on metropolitan spatial structures. Talebpour and Mahmassani, 2016 studied the influence of AVs on traffic flow stability and throughput and found that AVs can improve stability and be more effective in preventing shockwave formation and propagation. Meyer et al., 2017 simulated the influence of AVs on the accessibility of Swiss municipalities, and concluded that AVs could dramatically increase accessibility rates and even replace public transport outside dense urban areas. Correia and Arem, 2016 explored the possibility of replacing individually-owned conventional vehicles with autonomous ones and what it would mean for traffic flow and parking demand in a city. Considering the city of Delft in the Netherlands as case setting, they showed that despite increased traffic congestion due to empty vehicle relocation trips, vehicle automation could lead to more trip requests satisfied while reducing travel costs. Milakis et al., 2017 investigated future development opportunities for AVs in the Netherlands and gave estimates for the potential impacts on transport planning, traffic management and travel behavior over time horizons up to 2030 and 2050. Exploring the impact of shared AVs on urban parking demand, Zhang et al., 2015b suggested that for AV adopter-users, up to 90%of parking demand might be eliminated (also see Le[START_REF] Vine | Autonomous cars: The tension between occupant experience and intersection capacity[END_REF].[START_REF] Harper | Estimating potential increases in travel with autonomous vehicles for the non-driving, elderly and people with travel-restrictive medical conditions[END_REF] studied the influence of travel with AVs for the elderly and people with travel-restrictive medical conditions and found a 14% increase in annual vehicle miles traveled for the United States population 19 and older. Furthermore,[START_REF] Aria | Investigation of Automated Vehicle Effects on Driver's Behavior and Traffic Performance[END_REF] investigated AV effects on driver behavior and traffic performance, and the simulation results revealed that the positive effects of AV on roads are especially highlighted when the road network is crowded.

Figure 2 . 2 :

 22 Figure 2.2: Consolidated Distribution Center (CDC) with vehicle deliveries

Figure 2

 2 Figure 2.3: Single-tiered and two-tiered transportation systems

Figure 2 . 4 :

 24 Figure 2.4: An illustrative example of the SARP and the FIP[START_REF] Li | The Share-A-Ride Problem: People and parcels sharing taxis[END_REF]

  [START_REF] Fatnassi | Planning and operating a shared goods and passengers on-demand rapid transit system for sustainable citylogistics[END_REF] proposed another two-tiered shared passengers and goods model with a first tier (train, bus or truck line) transporting passengers or goods to connection points where a second tier, consisting of a set of small electric and AVs moving on a specific guideway then transport them to their final destinations. The paper uses a forward periodic-optimization approach to solve this dynamic problem.[START_REF] Behiri | Urban freight transport using passenger rail network : Scientific issues and quantitative analysis[END_REF] studied the freight-rail transport scheduling problem in which existing urban rail is used for transporting freight. In their model, one rail line is considered. On this line, there are several stations where freight can be loaded and unloaded. Freights are brought to these stations by truck at different time windows in a day. To solve this problem, the paper proposes two heuristic approaches: a dispatching rule-based heuristic and a singletrain decomposition-based heuristic. Similarly, Ghilas et al., 2016c considered a system in which freight requests are delivered by a set of vehicles such that a part of the transportation process is carried out on a scheduled public transport line. To model this two-tiered system, the paper introduces the pickup and delivery problem with time windows and scheduled lines (PDPTW-SL). In this problem, two options are considered for transporting freight:

  the literature. We would prone the following broad areas for future research: (i) developing efficient solution algorithms (exact and heuristic) for combined people-and-freight systems, (ii) extending the existing models by introducing multiple objectives related to profit, operational costs, environmental impacts, etc., (iii) developing more flexible models and efficient algorithms that consider the different sources of stochastic information (travel times, traffic jams, freight demands etc.), (iv) improving the dynamic (real-time) framework of such systems by adding new techniques and strategies (leading to shorter service times, strong synchronization between different tiers in two-tiered models, etc.), (v) introducing new public policies to regulate the potential integration of goods delivery in existing public transport systems, (vi) focusing more on increasing passenger satisfaction and reducing the potential inconvenience that might arise in such systems, and finally (vii) studying the potential deployment of automated services and their impacts on the future development of such combined systems.

  streams has been assessed in a number of studies in the last three years. Most of these studies have focused on analyzing the performance of such integrated systems and evaluating their operational gains compared to the existing transportation systems. A good example can be found in[START_REF] Fatnassi | Planning and operating a shared goods and passengers on-demand rapid transit system for sustainable citylogistics[END_REF] which considers a case study on the town of Corby (UK). The results demonstrate potential benefit of implementing a combined system in terms of service time, energy consumed, noise and carbon emissions compared to classical transportation systems.Ghilas et al., 2016a suggested these combined systems can bring up to 16% savings on overall operational cost. Considering real taxi trips in the San-Francesco area,Li et al., 2016a showed that a mixed-taxi service can outperform the other transportation systems available in the local urban area, but also highlighted two key factors to help maximize the gain obtained by such a service: analysis of the spatial characteristics of requests before implementing the service, and availability of a traditional freight service

  of autonomous vehicles going in hand with the increasing need for shared mobility services have attracted the attention of the operations research community especially after many large mobility operators (Tesla, Ford, Lyft and others) have declared their plans for deploying new autonomous mobility services. Different ownership models and usage scenarios have been introduced by various actors. 1One ownership model is based on the idea that autonomous vehicles will be individuallyowned. Thus, every user might have his own AV. Additionally, this model proposes that an individually-owned AV can serve other users during the time its owner does not need it. This might be the case when an AV owner is at work and the AV is not in use. Such an ownership model can help in partially financing AV acquisition cost. Another ownership model is to consider a fleet of on-demand (robotaxi) AVs. In this model, AVs are invoked from their stations (depots) to satisfy mobility demands such that one single AV can serve multiple demands before getting back to the station. Unlike the first model where owners

  Recent studies on autonomous mobility have focused on either assessing public opinions regarding AVs or studying the potential impacts of introducing such a new service on existing urban mobility systems. In a recent study,[START_REF] Daziano | Are consumers willing to pay to let cars drive for them? Analyzing response to autonomous vehicles[END_REF] observed the willingness to pay for partial or full automation through collecting and analyzing answers to a vehicle-purchase choice experiment focused on energy consumption and autonomous features. Another study, conducted by Bansal and Kockelman, 2016, surveyed respondents across Texas to understand their opinions about such a new technology. Their study showed that affordability and equipment failure are Texans' top two concerns regarding AVs. On studying AV potential impact, Bischoff and Maciejewski, 2016c simulated a city-wide replacement of private cars with a fleet of autonomous taxis in Berlin. Their simulation suggested that a fleet of 100 000 vehicles will be enough to replace private cars in Berlin at a high service quality for customers. Considering that AVs can be used as a shared mobility service, Fagnant and Kockelman, 2014 suggested that each shared AV can replace around 11 conventional vehicles, but adds up to 10% more travel distance than comparable non-shared AV trips resulting in overall beneficial emissions impacts. Moreover, Zhang et al., 2018 developed models to examine how much vehicle ownership reduction can be achieved once private conventional vehicles are replaced by AVs and the spatial distribution of unoccupied vehicle-miles-traveled (VMT) accompanied with the vehicle reduction. Their results showed that more than 18% of the households can reduce vehicles, while maintaining the current travel patterns. Furthermore, Loeb et al., 2018, simulated performance characteristics of shared AV fleets serving travelers across the Austin, Texas 6-county region where a set of charging stations with different charging times were considered. Their results suggested that reducing charge times does lower fleet response times (to trip requests), but increasing fleet size improves response times the most. Another research, by Krueger et al., 2016, concluded that service attributes including travel cost, travel time and waiting time may be critical determinants of the use and acceptance of shared AVs. Their results implied also that the adoption of shared AVs may differ across cohorts, whereby young individuals and individuals with multimodal travel patterns may be more likely to adopt shared AVs. Additionally, Milakis et al., 2017 used scenario analysis to identify future deployment paths of automated vehicles in the Netherlands. According to their scenarios, fully automated vehicles are expected to be commercially available between 2025 and 2045, and to penetrate the market rapidly after their introduction. On exploring the impact of shared AVs on urban parking demand, Zhang et al., 2015a showed, through an agent-based simulation approach, that 90% of parking demand for clients who adopt the system might be eliminated at low market penetration rate. In addition, Harper et al., 2016 estimated bounds on the potential increases in travel in a fully automated vehicle environment due to an increase in mobility from the non-driving and senior populations and people with travel-restrictive medical conditions. Their results estimate 14% increase in annual vehicle-miles-traveled for the US population 19 and older.Therefore, the study of the potential impacts of introducing AVs in urban mobility systems associated with assessing their sharing potential are at the heart of nowadays research regarding autonomous mobility. Although research on studying the impacts of deploying AVs has been growing in popularity in recent years, less amount of research on how to plan and operate their trips is yet available. This is mainly because most scientific advances for operating AVs have been done by AV manufacturers and service providers who do not always publicly unfold the details of their approaches and algorithms due to commercial sensitivity. In addition, some studies suggested that methods and algorithms that operate conventional vehicles can still be applied to autonomous vehicles. However, an increasing effort is being directed recently towards building new methods for planning AV trips. For this purpose, Hyland and Mahmassani, 2017 propose a taxonomy for classifying AV fleet management problems to inform future research on autonomous vehicle fleets. In their paper, they review the existing categories for classify scheduling and routing problems, refine some of them as they relate to the AV fleet problem and propose novel taxonomic categories for classifying AV fleet management problems. On planning new infrastructures to adapt and promote the deployment of AV technology, Chen et al., 2017 presented a mathematical framework for the optimal design of AV zones in a general network. Their framework is based on, first, a mixed routing equilibrium model which captures different routing behaviors (within and outside AV zones), and mixed-integer bi-level programming model to optimize the deployment plan of AV zones. In their general framework for modeling shared autonomous vehicles,[START_REF] Levin | A general framework for modeling shared autonomous vehicles with dynamic network-loading and dynamic ride-sharing application[END_REF] propose a heuristic for dynamically constructing shared rides using autonomous vehicles. The proposed approach consists of a dispatcher that checks whether there are any AVs that are already located or en route to where a travel demand has appeared and then assigns the AV to carry the longest waiting traveler. Furthermore, other travelers are allowed to join the shared trip if they are traveling to the same, or a close, destination giving the priority to travelers already in the vehicle because they have been traveling. In addition,[START_REF] Kümmel | Framework for automated taxi operation: The family model[END_REF] introduce a theoretical framework for autonomous vehicles based on the model of a family (the provider of physical services as the "father ", the strategic manager as the "mother ", and the individual AVs as the "children"). Their model allows vehicles to negotiate among them in a decentralized fashion and, at the same time, it allows the fleet manager to set fleet priorities and pre-allocate vehicles in locations of expected future demand. Moreover, Alonso-Mora et al., 2017 propose a general mathematical model for real-time high-capacity ridesharing that, on the one hand, scales

  Figure 3.1: Different ownership models

  d j := {k ∈ M |δ k,d j ≤ m j }. Furthermore, we use the concept of meeting point arc introduced in Stiglic et al., 2015. A meeting point arc a ∈ A denotes a combination of a pickup meeting point and a drop-off meeting point. As such, the set of feasible meeting point arcs for rider j is A

Figure 3 . 2 :

 32 Figure 3.2: Distance feasible match -Positive distance saving

  Figure 3.3: Generating feasible matches

Figure 3 . 4 :

 34 Figure 3.4: Algorithm 1 -Find-Owner-Feasible-Matches

Figure 3 . 6 :

 36 Figure 3.6: Algorithm 2 -Match-Generation

Figure 3 . 7 :

 37 Figure 3.7: Early checking -infeasibility check of a match

For

  generating the required instances, Taxi and Limousine Commission (TLC) trip record datasets for New York City are used (see Appendix B.1). The taxi trip records include fields capturing pickup and drop-off times and locations, trip distances, fares and other related fields. We use these trips to generate owner and rider trips according to different usage scenarios.Since the set of meeting points is predefined and used for all instances, taxicab trips are interpreted and processed in order to generate a set of owner trip announcements and a set of rider trip announcements for each instance over a full-day time horizon. Therefore, we generate 16 different streams of trips based on datasets obtained during different working days (1, 3, 5, 7 December 2016) as follows.

  Figure 3.8: Generating meeting points and AV depots

  other words, Participant-per-Vehicle (PpV), we divide the average number of participants by the average number of used AVs in each of the scenarios (i.e. PpV = number-of-participants / number-of-used-AVs). As such, results indicate that the average number of participants served by an AV gradually increases as more on-demand AVs becomes available and shared (While an individually-owned AV is serving 2 participants in average in 0% on-demand AV scenario, an on-demand AV is serving up to 13 participants in average in 100% on-demand AV scenario) (Figure3.10a). This observation also goes in hand with the increasing matching rates presented earlier.

( a )

 a Figure 3.10: Participant and Distance per Vehicle (%)

( a )

 a Figure 3.11: Average Distance Saving (%)

Finally

  , we consider the average extra travel time for participants (owners and riders) which indicates the extra travel time a participant will have in his trip in order to be matched in a shared ride. Thus, this extra time is obtained by comparing the actual travel time of the participant in a shared ride with the travel time of a direct trip from his origin location to his destination location (no sharing takes place).

Figure 3 .

 3 Figure 3.12: Average Extra Travel Time per Participant (mins)

  intermediate points using a set of carrier trucks, and then delivered by a set of potential cyclists and pedestrians who are living in the same neighborhood. The authors proposed a tabu search algorithm for solving the asoociated optimization problem. Their results demonstrated that the use of potential cyclists and pedestrians can reduce the operational costs by 9.25% compared to a truck-based delivery system. As for studying uncertainty in such combined systems, Li et al., 2016b extended the SARP, introduced earlier, by considering two stochastic variants. The first variant considered the travel times to be stochastic while the second considered stochastic delivery locations. For solving both variants, a two-stage stochastic programming model with recourse is used with the ALNS heuristic and a scenario generator. Through an extensive experimental study on both stochastic models, the paper concluded that the stochastic travel times have a more noticeable effect on the SARP than the stochastic delivery locations. In addition, Ghilas et al., 2016a extended their two-tiered model by considering stochastic demand quantities of freight requests which are only revealed upon the vehicle's arrival to their pickup locations. A scenario-based sample average approximation approach

  Figure 4.1: Request service modes: direct & indirect delivery

( a )

 a Figure 4.2: Scheduled line with four replicated transfer nodes

Figure 4 . 3 :

 43 Figure 4.3: An example network with s replicated nodes and two requests

Figure 4 . 4 :

 44 Figure 4.4: Calculate-Recourse-Cost Algorithm

Figure 4 . 5 :

 45 Figure 4.5: Sample Average Approximation (SAA) Algorithm

Figure 4 . 6 :

 46 Figure 4.6: Adaptive Large Neighborhood Search (ALNS) Algorithm

  acteristics. In addition, each instance contains up to 60 freight requests where their origin and destination nodes are distributed over 200 x 200 Euclidean space. We consider three different distributions of freight requests (inspired from Ghilas et al., 2016a). These are: C -freight request origin and destination nodes are clustered within at most 30 time units around transfer nodes (Figure 4.7a), RC -request nodes are randomly clustered within at most 50 time units to one of the available transfer nodes (Figure 4.7c), and UR -freight requests are uniform-randomly distributed over the considered space (Figure 4.7d). As PD robots are located at transfer nodes, we consider up to three PD robots at each transfer node.

Figure 4 . 7 :

 47 Figure 4.7: Instances with different network topologies and request distributions

  to follow a discrete triangular distribution for a given minimum value a = 0, mean b = 6 and a maximum value c = 10 (Figure 4.8a).

( a )

 a Passengers demand distribution (b) An example of SAA scenario

Figure 4 . 8 :

 48 Figure 4.8: SAA scenario generation

( a )

 a Figure 4.9: Passengers demand analysis

( a )

 a Figure 4.10: SL frequency analysis

( a )

 a Figure 4.11: SL capacity analysis

A. 3

 3 Ch. 4: Calculate-Recourse-Cost Algorithm Algorithm 3 Algorithm for calculating the average recourse cost of a given routing solution 1: procedure Calculate-Recourse-Cost(routing solution δ, set of scenarios ξ) 2: initialize recourse cost: E [ Q ( δ , ξ , η ) ] ← 0 3: let c(δ) be the routing costs of solution δ 4:for each scenario s in ξ do 5:

  The ALNS Framework 1: procedure ALNS-Heuristic(Set of removal operators O R , set of insertion operators O I ) operator r * ∈ O R with probability P r * 6:apply operator r * to current solution to obtain a partially destroyed solution 7: select an insertion operator i * ∈ O I with probability P i * 8: apply operator i * to repair the partially destroyed solution and get new solution 9: if new solution is better than current solution then 10: current solution ← new solution 11: if current solution is better than best solution then Sample Average Approximation (SAA) Algorithm 1: procedure Sample-Average-Approximation(sample size |Ω|, large set of scenarios Ω , number of iterations m) problem using ALNS to get routing solution x m 7: Calculate-Recourse-Cost(δ, Ω) → get upper bound for Ω 8: calculate lower bound for ω by averaging objective values of previous iterations 9: calculate SAA gap using upper bound and lower bound exemple, examiner les problèmes de synchronisation dans les modèles de mobilité partagée, utiliser des véhicules autonomes dans un contexte de covoiturage, intégrer la livraison du fret au transport de passagers avec des aspects stochastiques, etc. Cela nous aide à identifier des pistes intéressantes pour notre recherche.Question 2: Comment synchroniser les déplacements de personnes et quels gains cette synchronisation peut-elle générer? En basent sur la revue présentée en Chapitre 2 (Chapter 2), nous étudions en chapitre 3 (Chapter 3) un système de covoiturage dans lequel des véhicules autonomes (AV), à la demande et individuels, sont utilisés pour transporter les passagers. Les trajets des passagers sont synchronisés en utilisant le concept de points de rencontre qui indique où les passagers peuvent être pris en charge et déposés au cours d'un trajet partagé. Pour opérer un tel système, nous proposons dans ce chapitre une approche en deux phases pour mettre en correspondance des participants potentiels lors de voyages partagés. L'approche proposée se compose, d'une part, d'un algorithme permettant de générer l'ensemble des correspondances possibles qui respectent les contraintes de temps des participants, et, d'autre part, d'un problème d'optimisation de la correspondance permettant de sélectionner les meilleurs. À travers une étude de cas sur la ville de New York, les résultats obtenus démontrent qu'une moyenne de 21% d'économies en termes de kilomètres parcourus par véhicule-système peut être réalisée lorsque les trajets de passagers sont partagés (i.e. synchronisés). Les résultats montrent également qu'un système, dans lequel un service à la demande et partagé est utilisé partiellement ou totalement, offre de meilleures performances qu'un système dans lequel seuls des véhicules individuels sont utilisés. Cette observation est importante pour les opérateurs de services autonomes, car elle peut les aider à créer leurs futurs services automatisés.

L

  'objectif de recherche: L'objectif de cette thèse est de développer des modèles et des approches d'optimisation pour la synchronisation des flux de personnes et de fret dans les systèmes de mobilité urbaine. Cette thèse vise à étudier les systèmes de mobilité partagée et à développer des approches efficaces pour les exploiter. Afin de mieux comprendre le concept de mobilité partagée, la thèse fournit une classification détaillée et un aperçu complet de ses variantes en fonction de leurs caractéristiques, contexte de l'application, objectifs, caractéristiques, modèles, et méthodes de solution. Ensuite, le problème de la synchronisation des flux de passagers et de fret est abordé en étudiant deux systèmes de transport différents. Pour les deux systèmes, l'accent est mis sur le développement d'approches heuristiques capables de trouver des solutions quasi optimales à des temps de calcul courts. Les résultats des systèmes proposés justifient les gains potentiels pouvant être obtenus lorsque les flux de voyageurs et de marchandises sont synchronisés. Nous pensons que ces gains peuvent donner une indication importante aux opérateurs de services, surtout que les systèmes proposés ne sont pas encore pleinement opérationnels dans la vie réelle et que des recherches supplémentaires sont encore nécessaires pour quantifier leurs avantages. Il est également important de dire que les systèmes proposés ne visent pas à remplacer les services existants pour le transport de passagers et de marchandises. En revanche, ils représentent une opportunité de les compléter et d'ouvrir la voie à une nouvelle génération de systèmes de transport partageables et durables. Par exemple, les véhicules autonomes partagés ne sont pas censés remplacer les transports en commun ni éliminer la possession d'une voiture privée, mais ils pourraient fournir un service supplémentaire dans les centresvilles où l'utilisation de la voiture privée est limitée. De même, l'intégration de petits robots, utilisés pour la livraison du dernier kilomètre, dans un service de transport pour les passagers vise à réduire les déplacements de camions de livraison dans les zones urbaines. Enfin, nous résumons les principales conclusions et contributions de la thèse, soulignons les principaux défis auxquels sont confrontés les systèmes de mobilité partagée et proposons des pistes pour les recherches futures dans ce domaine (Chapter 5). Mots cl és : mobilit é urbaine, synchronisation, transport de passagers et de marchandises, covoiturage, v éhicules autonomes, optimisation, incertitude, m éthodes heuristiques R ésum é : Avec l'augmentation progressive de la population dans les grandes villes, comme Paris, nous pr évoyons d'ici 2050 une augmentation de 50% du trafic routier. En consid érant les embouteillages et la pollution que cette augmentation va g én érer, on voit clairement la n écessit é de nouveaux syst èmes de mobilit é plus durables, comme le covoiturage, ou plus g én éralement toute la mobilit é partag ée. En parlant de mobilit é partag ée, ce n'est pas seulement le partage de trajets de personnes qui ont le m ême itin éraire au m ême temps, elle inclut aussi les marchandises. Cette th èse aborde le d éfi de la synchronisation des flux de passagers et de marchandises dans les syst èmes de mobilit é urbaine et elle vise à d évelopper des m éthodes d'optimisation pour que cette synchronisation dans la mobilit é partag ée soit r éalisable. Dans un premier temps, nous étudions les diff érentes variantes des syst èmes de mobilit é partag ée et nous les classifions en fonction de leurs mod èles, caract éristiques, approches de r ésolution et contextes d'application. En nous basant sur cette re-vue de litt érature, nous identifions deux probl èmes de mobilit é partag ée, que nous consid érons en d étails dans cette th èse et nous d éveloppons des m éthodes d'optimisation pour les r ésoudre. Pour synchroniser les flux de passagers, nous étudions un mod èle de covoiturage en utilisant les v éhicules autonomes, personnels et partag és, et des points de rencontre o ù la synchronisation entre passagers peut avoir lieu. Pour cela, une m éthode heuristique en deux phases est propos ée et une étude de cas sur la ville de New York est pr ésent ée. Ensuite, nous d éveloppons un mod èle d'optimisation qui combine les flux de passagers et de marchandises dans une zone urbaine. Le but de ce mod èle est d'utiliser les capacit és disponibles sur une ligne de transport fixe pour transporter les passagers et des robots transportant des petits colis à leurs destinations finales en consid érant que la demande de passagers est stochastique. Les r ésultats obtenus montrent que les solutions propos ées par ces deux mod èles peuvent conduire à une meilleure utilisation des syst èmes de transport dans les r égions urbaines. Title : The synchronization of shared mobility flows in urban environments Keywords : urban mobility, synchronization, passenger and freight transportation, ridesharing, autonomous vehicles, optimization, uncertainty, heuristic approaches Abstract :

Table 2

 2

	Variant	Goods	On-	Daily	Long-	Pre-	Real-
		trans-	demand	com-	distance	arranged	time
		port		mute
	Carpooling
	Flexible Carpooling
	Vanpooling
	Prearranged Ridesharing
	Long-distance Rideshar-
	ing
	Dynamic Ridesharing
	DARP
	Shared-Taxi
	Combined Delivery
	Share-a-Ride Problem
	Crowd-sourcing

.1: Shared mobility variants for people transportation -Different characteristics

Table 2

 2

	.1 gives a roll-up summary of the different variants of recent shared mobility prob-
	lems. Below we give a more detailed analysis of these variants and the modeling approaches
	and optimization methods commonly used.

Table 2

 2

	Method	Scope Assessing system performance	Studying impacts
	Optimization-based	Agatz et al., 2011 Jiang et al., 2017	Stiglic et al., 2016b Lee and Savelsbergh, 2015
			Agatz et al., 2011
			Maciejewski et al., 2016
	Simulation-based		Ferreira and D'Orey, 2015	Martinez, 2015
			Linares et al., 2017
			Ma and Zhang, 2017
			Tachet et al., 2017
	Data-analysis-based	Liu and Li, 2017 Sanchez et al., 2016 Gargiulo et al., 2015	Barann et al., 2017 Yu et al., 2017
			Wang et al., 2017

.3 gives a roll-up summary of the case studies presented.

Table 2

 2

.3: Case studies -Ridesharing systems

Table 2

 2

	Method	Scope	Assessing system performance	Studying impacts
	Optimization-based	Ma et al., 2017	Correia and Arem, 2016
				Gruel and Stanford, 2016
			Bischoff and Maciejewski, 2016a	Zhang et al., 2015b
			Fagnant and Kockelman, 2016	Talebpour and Mahmassani, 2016
			Chen et al., 2016b	Fagnant and Kockelman, 2014
	Simulation-based		Bischoff and Maciejewski, 2016b Chen and Kockelman, 2016	Milakis et al., 2017 Harper et al., 2016
			Levin and Boyles, 2015	Meyer et al., 2017
		Scheltes and de Almeida Correia, 2017	Diels and Bos, 2016
			Lokhandwala and Cai, 2018	Aria et al., 2016
				Smolnicki and Sołtys, 2016
				Alessandrini et al., 2015
	Data-analysis-based	-	Fagnant and Kockelman, 2015
				Wadud, 2017

.4: Case studies -Shared autonomous mobility Studies on the deployment of AVs in shared mobility systems include

Chen et al., 2016a

who ran a simulation study on the city of Austin, Texas. The results suggested that AVs offer a viable alternative to private vehicle travel (also see

[START_REF] Fagnant | The travel and environmental implications of shared autonomous vehicles, using agent-based model scenarios[END_REF][START_REF] Fagnant | The travel and environmental implications of shared autonomous vehicles, using agent-based model scenarios[END_REF][START_REF] Chen | Operations of a shared, autonomous, electric vehicle fleet: Implications of vehicle & charging infrastructure decisions[END_REF]

. The study revealed that each shared AV can replace 5-9 privately owned vehicles while serving 96-98% of trip requests. Bischoff and Maciejewski, 2016c led a similar study on the city of Berlin, Germany, simulating the replacement of hundreds of thousands of vehicles all around the city by a fleet of autonomous taxis. Results suggested that the car fleet in Berlin can be replaced by a fleet of 100,000 autonomous taxis while maintaining high service quality for customers (also see

Bischoff and Maciejewski, 2016b)

. Another study, by Scheltes and de Almeida Correia, 2017, simulated a system in which the last-mile segment of train trips was carried out by a fleet of fully autonomous vehicles. Results obtained from applying the simulation model on Delft,

  . A set of backup vehicles is operated to cover parcel requests that cannot be delivered by ad-hoc drivers. Furthermore, the paper presents an event-based rolling horizon framework that dynamically matches tasks to drivers at each time a new delivery request or driver arrives throughout the day, as well as exact and heuristic recursive algorithms for solving the routing subproblem. Results show that using ad-hoc drivers can potentially reduce last-mile delivery costs as well as system-wide vehicle mileage.[START_REF] Archetti | The Vehicle Routing Problem with Occasional Drivers[END_REF] considered a similar problem to[START_REF] Arslan | Crowdsourced Delivery -A Pickup and Delivery Problem with Ad-hoc Drivers[END_REF] but in their setting, a service provider uses not only a fleet of delivery vehicles and dedicated drivers but also a set of occasional drivers who are willing to make a single delivery using their own vehicle. Making these deliveries should not significantly extend the trip time for the occasional driver, who can then receive a small cost compensation for each delivery they perform.. To model the

	Arslan et al., 2016 proposed another single-tiered model in a study on the concept of
	crowd-sourcing delivery, which aims to make parcel deliveries using excess capacity on trips
	that already take place (see Mladenow et al., 2015; Goetting and Handover, 2016 for recent
	reviews of the latest crowd-sourced delivery models). For this purpose, the paper considered
	a decentralized model that automatically matches parcel delivery requests to potential ad-
	hoc drivers. Parcel deliveries are made by self-employed drivers who are willing to earn extra
	money on their way to home or work. The drivers indicate their origin and destination
	locations, their vehicle capacity, and a time window. Likewise, parcel delivery requests

also have time windows that state when they should be picked up and delivered. Thus, a delivery is possible if there is a feasible match between driver's time window and parcel's time windowproblem,

[START_REF] Archetti | The Vehicle Routing Problem with Occasional Drivers[END_REF]

introduced a new variant of the classical capacitated VRP called the 'vehicle routing problem with occasional drivers'. The paper also presents a heuristic approach in which variable neighborhood and tabu search strategies are combined to produce good quality solutions.

[START_REF] Wang | Towards enhancing the last-mile delivery: An effective crowdtasking model with scalable solutions[END_REF]

presented a crowd-tasking model in which last-mile deliveries are performed by a crowd of citizen workers, and proposed to formulate the model as a network min-cost flow problem and use an iterative pruning technique to make the network manageably small. Dayarian and Savelsbergh, 2017 proposed another crowd-sourced service in which customers can deliver some online orders. Potential customers express an interest to participate in making deliveries on their way home, and thus supplement a set of dedicated drivers performing the service, with vehicle routes generated using a tabu search heuristic. A number of papers have considered transporting freight by the same rail network as passengers (see

[START_REF] Steadieseifi | Multimodal freight transportation planning: A literature review[END_REF][START_REF] Cochrane | Moving freight on public transit: Best practices, challenges, and opportunities[END_REF][START_REF] Ozturk | An optimization model for freight transport using urban rail transit[END_REF]

, but they are outside our scope as the models do not integrate passengers and freight in the same trip (i.e. rail is used during passenger off-hours).

Table 3

 3

	.1: Base case instance characteristics
	Trip pattern: short trips around city center	Parameters
	Average number of participants	3042
	Average number of owners	1519
	Average number of riders	1522
	Owner-to-rider ratio	1 : 1
	Average trip distance for participant	3.64 km
	Average trip time for participant	9.04 mins
	Max. walking distance to/from a meeting point	0.5 km
	Walking speed	4 ft/s
	Vehicle speed	24 km/h
	Max. time flexibility of an owner	20 mins
	AV capacity	4

Table 3

 3

	.2: Instances with different owner-to-rider ratio
		1-to-1 1-to-2 1-to-4 1-to-10
	Average number of participants 3043	4564	7609	16435
	Average number of owners	1519	1519	1519	1519
	Average number of riders	1523	3045	6090	14915

Table 3

 3

	.3: Base case instance with different usage scenarios and 1-to-1
		replacement rate
	Scenario # IO AVs # OD AVs # Riders
	100% IO	1510	0	1522
	90% IO	1360	150	1672
	80% IO	1210	300	1822
	70% IO	1060	450	1972
	60% IO	910	600	2122
	50% IO	760	750	2272
	40% IO	610	900	2422
	30% IO	460	1050	2572
	20% IO	310	1200	2722
	10% IO	160	1350	2872
	0% IO	0	1510	3022

Table 4

 4

	.1: Notations and Variables
	subject to
	Routing and flow constraints
	i∈N v∈V

  ) ensure that the same PD robot that picked up the request at its origin, will proceed to deliver it to its final destination (i.e. this set of constraints couple the pickup and delivery trips of PD robots). Constraints (4.7) ensure that the maximum travel distance that PD robots can perform is respected. Since requests demand is known beforehand, constraints (4.8) ensure that the capacity of PD robots is respected at each time they pickup a request.

	In this problem, we have four sets of constraints: routing, capacity,
	scheduling, and synchronization constraints. As for routing and flow constraints, constraints
	(4.2) state that all request pickup and delivery nodes (origins and destinations) are visited
	exactly once by a PD robot. Constraints (4.3) ensure that each PD robot must leave its
	depot at most once. Constraints (4.4) ensure that each replicated transfer node is visited at
	most once. Flow conservation for PD robots is considered in constraints (4.5). Constraints
	(4.6

  generate request pickup and delivery time windows randomly with an average width of 40 time units. A minimum of 100 time units is also assured between the end of pickup time window and the start of delivery time window. Service time at each location (i.e. pickup, drop-off or transfer node locations) is set to three time units. This service time represents the time needed for a PD robot to pick up or deliver a freight request, or to get in or off a shuttle at a transfer node. Table 4.2: Set of parameters used in the computational study

	Parameter	Value Parameter	Value
	PD robot cost	0.5	Num. iterations no improvement	50
	SL cost	1	The size of the large set of scenarios	10 000
	Outsourcing cost	3	The size of the sample set of scenarios	50
	PD robot capacity	1	Number of ALNS iterations	10 000
	SL capacity	10	Number of SAA iterations	10
	Max. num. places for PD robots	3	Score for new best solution	3
	Freight request quantity	1	Score for improving current solution	1

Table 4 .

 4 3 (results obtained by CPLEX are in bold). In this table, # dir. indicates the number of direct deliveries, # ind. indicates the number of indirect deliveries, and # usv. indicates the number of unserved freight requests. In addition, Cost column represents the total transportation costs obtained by the ALNS heuristic and CPLEX (respectively) while Gap (%) column gives the optimality gap percentage between them. Finally, CPU column indicates the execution time needed to run both approaches, and # iter. column gives the number of ALNS iterations performed.

Table 4

 4

.5: The performance insertion operators

  let ∆ t be the realized number of passengers waiting for service at t

	10: 11: 12:	rank PD robots in I w t according to their requests latest due dates if |W t | > Q w ij then add PD robots to SL in order until Q w ij is reached
	13:	for each excessive PD robot do
	14:	if direct delivery from t to destination is possible then
	15:	update recourse cost according to the extra traveled distance by
	PD robot
	16:	else
	17:	add PD robot to W t
	18:
	19: 20:	if |∆ t | -Q w ij > 0 then for each robot in I w t do
	21:	if direct delivery from t to destination is possible then
	22:	update recourse cost according to the extra traveled distance by
	PD robot
	23:	else
	24:	add PD robot to W t
	25:	for each PD robot in W t do
	26:	if time window is violated then

This price is set based on: http://cityobservatory.org/what-price_autonomous_vehicles/

These travel costs were set using the average monthly subscription price (220e) that was used in the survey[START_REF] Maghraoui | Shared Autonomous Vehicle Services and User's Taste Variation : A Survey and Model Applications[END_REF]

This integrated system was inspired from Toyota new e-Palette concept in which small delivery robots travel with passengers in autonomous shuttles moving around in a city: https://newsroom.toyota.co.jp/ en/corporate/20546438.html

Acknowledgements

Generate feasible matches for a round trip

If the considered offer is a round trip (Figure 3.3b), the algorithm selects a set of artificial owners in order to construct a concatenation of one-way trips (See Figure 3.5a). The idea is to choose one rider to be a temporal owner of the AV which will pick him up at his origin location and drop him off at his destination location. In this case, this selected rider will be considered as a new "artificial" owner of the AV and the algorithm will then try to match him with other potential riders. Once the first artificial owner is considered and matched, the algorithm will add other artificial owners as long as the AV can still return to its real owner (or equivalently to its depot in the on-demand case) at the specified latest arrival time. The choice of which rider to be selected as the next artificial owner is made in a greedy fashion (see Figure 3.5b). The earliest departure time of the rider and the time that the AV needs to arrive at his origin location are considered. Thus, the rider that can be served the earliest is chosen. In this example, rider a1 is chosen as the next artificial owner because the AV can arrive to his origin location at 9:25 (Earliest departure from the depot at 9:00 + 25 mins traveling to a1 origin location) and his earliest departure time is 9:00. Thus, his trip can start at max(9:00,9:25) = 9:25 where a2 and a3 trips can start at 9:30 and 12:30 respectively. So, a1 is chosen because his trip can be started the earliest. The process of assigning artificial ownership to riders continues until there is only time for the AV to return to its original location (In the example, the AV must return to its origin o before 5 pm). This greedy choice is made as we want to approximate a dynamically operating ridesharing system in which a vehicle is assigned to a first customer and then others are added as soon as their requests arrive. Once all round trips are transferred into sequences of one-way trips, they can be treated similarly (section 3.4.2). Thus, the algorithm will look for all their feasible matches and add those found to the matching problem. Synchronizing people and freight transportation flows While a ridesharing system for people transportation is considered in chapter 3, we study in this chapter an integrated system in which a set of freight requests need to be delivered using a fleet of grounded pickup and delivery (PD) robots where a public transportation service (referred to as scheduled line (SL)) can be used as part of PD robot's journey. As both passengers and PD robots (carrying freight) share the available capacity on SLs, we consider that passengers are prioritized and that their demands are stochastic. Thus, the number of available places for PD robots is only revealed upon SL departure. We first formulate this problem as a Pickup and Delivery Problem with Time

Windows and Scheduled Lines (PDPTW-SL). We then introduce a sample average approximation (SAA) method along with an Adaptive Large Neighborhood Search (ALNS) algorithm for solving the stochastic optimization problem. Finally, we present an extensive computational study for assessing the impact of uncertainty on such integrated system.

problems with deterministic setting helps in evaluating the potential benefit of new shared mobility systems, considering the stochastic aspects represent a key-factor for successfully operating them in real-life context.

Further research directions

The research presented in this thesis can be extended in many directions. In this thesis

we focused on evaluating the potential benefits of two transportation systems from the operational point of view. We thus believe that this thesis has opened the door for many interesting research topics.

For the ridesharing model with AVs, an interesting direction for further research is to consider dynamic aspects of the problem so that participants are matched at short notice.

Another possible research direction is to consider AV recharging operations in the planning of their routes. Moreover, considering unexpected events that can affect AV travel times (i.e.

uncertainty) also represents an important extension as it can give a more realistic view of the system. From a methodological point of view, developing an exact approach for solving the problem might be very helpful as it can be used to generate bounds and evaluate the performance of the proposed heuristic approach.

Regarding the integration of passenger and freight flows, the proposed system can also be extended in many ways. One of them is to study stochastic travel times and their impact on the system. These stochastic travel times include those for PD robots and those for SL (i.e. SL departures might also be affected by accidents, congestion, etc.). From a methodological point of view, the system can be extended to allow multiple pickup and deliveries during a PD robot trip. This extension requires modifying the routing constraints of the model which would complicate the problem even more. Another methodological extension is consider different recourse actions which might affect the overall transportation costs of the system.

Appendix A

Appendix A: Algorithms store meeting points in k-d tree;

3:

for each rider in instance.R do 4:

query k-d tree and find feasible meeting point arcs for rider ;

5:

for each owner in instance.O do 6:

if owner trip is a one-way trip then 7:

add owner trip to one-way trips;

8:

else //then it is a round trip 9: origin = owner.origin;

10:

sort riders with respect to their distance from origin; //increasing order 11:

while it is possible to add new artificial trips do 12:

pick rider from the sorted list of riders; //starting with first, second .. etc.

13:

if rider is time compatible then 14:

add a new trip with rider as an artificial owner ;

15:

Find-Owner-Feasible-Matches(artificial owner )

16:

exclude rider from instance.R and from the sorted list; sort riders with respect to their distances from origin;

19:

for each owner in one-way trips do 20:

Find-Owner-Feasible-Matches(owner ) As the number of trip records in every dataset is very large and some of them might be incomplete (e.g. the departure or arrival time of a trip might not be indicated), we make sure to filter these records and take those which contain all the required information. This verification is done using a method (implemented in Java) that reads trip records from excel files, filter them, and generate instances of different sizes. Ce chapitre propose également une étude approfondie de leurs types de contraintes et de leurs objectifs, ainsi que des approches de modélisation et de résolution utilisées pour les exploiter. Ensuite, les dernières tendances en matière de mobilité partagée (mobilité autonome, livraison combinée de fret, etc.) sont examinées et les articles et études de cas récemment publiés sont résumés dans des tableaux récapitulatifs. La revue présentée dans ce chapitre met en évidence certaines lacunes de la recherche qui, à notre avis, doivent être