Universit É Pierre

Marie Curie Specialization

Aurélien Carlier

M Christian

Artigues Reviewer

M Roberto

Wolfler Calvo Reviewer

Mme Safia

Kedad Sidhoum

M Alain Quilliot

M Jakob Puchinger

M Lionel Scremin

M Witold

Klaudel Co

Renault Mme Alix

Munier-Kordon Supervisor

Roberto Wolfler Calvo D'

Monsieur Alain Quilliot

Merci À Frédéric

Sean S Merci

Nathalie L D'

DOCTOR OF SCIENCE THESIS

Je tiens à remercier en premier lieu Alix, qui a su m'apporter son soutien et sa confiance tout au long de ces trois années. Sa disponibilité et son implication m'ont toujours été d'un secours précieux et c'est avec une réelle fierté que je présente aujourd'hui les résultats de nos collaborations. Sans son appui scientifique et humain, ces travaux ne seraient pas aussi aboutis.

Je tiens en second lieu à remercier Witold pour m'avoir accordé son appui et son support dans ce projet. Malgré la distance, son intérêt constant pour le sujet et son expérience furent indéniablement bénéfiques à l'avancée des recherches. C'est avec sincérité que je tiens à lui exprimer ici toute ma gratitude.

Je tiens également à remercier chaleureusement l'ensemble des membres de mon jury de thèse. Merci à Messieurs Christian

le prix de la mobilité est fonction de la distance et du temps et non plus de la possession du véhicule. En conséquence, les utilisateurs ont tendance à utiliser moins la voiture et parcourent de plus faibles distances. Ces observations expliquent en partie la réduction du nombre de véhicules sur les routes, aidant alors à diminuer la congestion et la quantité de CO2 dégagée par les véhicules.

On distingue souvent deux types de systèmes : ceux gérés par des organisations privées et ceux s'organisant directement entre les particuliers. Dans ce manuscrit, nous nous intéressons aux systèmes dirigés par des compagnies privées, dont l'implantation est stratégiquement et majoritairement établie dans des zones urbaines denses. En France, et plus largement autour du globe, de plus en plus de compagnies conçoivent et opèrent des systèmes d'autopartage.

Le défi majeur que doit relever un opérateur consiste alors à concevoir le futur service qu'il souhaite mettre en place avant de le piloter. Cet aspect conceptuel, en avance de phase par rapport à la supervision et à la gestion dynamique de la flotte, est fondamental. La réussite financière du service et son efficacité opérationnelle sont en effet fortement liées à l'utilisation des véhicules partagés mis à disposition. En règle générale, un fort taux d'utilisation garantit l'intégrité globale du système.

Il existe aujourd'hui plusieurs modèles d'autopartage, qui peuvent tout à fait coexister ensemble au sein d'un même contexte urbain. Nous nous focalisons dans ce manuscrit sur le modèle dit "one-way" et dont la mise à disposition des véhicules s'effectue dans des stations propres à l'opérateur. Ces dernières, prévues pour le stationnement, dispose généralement de bornes de recharge lorsque la flotte de véhicules est électrique. Les systèmes one-way permettent aux usagers d'emprunter un véhicule sans la contrainte de le déposer à la station de départ, contrairement aux modèles "round-trip". Récemment, de nouveaux modèles sans station tendent à apporter de plus en plus de flexibilité pour l'usager (modèles "free-floating").

En pratique, la flexibilité des systèmes one-way a tendance à perturber la disponibilité des véhicules et des places disponibles dans les stations. Particulièrement aux horaires de pointe, il est assez courant de ne pas trouver de véhicule ou de place pour se garer et ces désagréments nuisent fortement aux usagers. Afin de maintenir un certain équilibre du système, il est possible d'inciter les utilisateurs à changer leur destination initiale pour une autre plus appropriée via une tarification plus avantageuse par exemple.

Cependant, cette méthode, dépendante de l'agrément de l'usager, est peu efficace en pratique et ne permet pas d'obtenir un contrôle suffisant du système. Ainsi, une méthode souvent employée par les opérateurs d'autopartage consiste à repositionner eux-mêmes les véhicules à des emplacements stratégiques où ils seront susceptibles d'être réempruntés. Ces opérations sont effectuées par des employés appelés jockeys. Notons que l'inclusion de ces opérations dans l'évaluation du dimensionnement du système ou de sa performance est essentielle et mise en évidence dans de nombreux travaux.

Les objectifs de la thèse consistent en l'élaboration de modèles mathématiques et de méthodes de résolution permettant d'aider un opérateur d'autopartage à concevoir son futur service de mobilité. Sur la base d'un environnement urbain connu et d'une demande en transport intégrant plusieurs modes de déplacement, les modèles proposés permettent d'évaluer le potentiel d'implantation d'un service one-way incluant des véhicules électriques. Ces modèles s'inspirent de travaux antérieurs déjà éprouvés, et leur performance est évaluée à partir de jeux de données réalistes (générés aléatoirement) et concrets (à partir d'enquêtes de déplacement).

Dimensionnement optimal du système

Le modèle mathématique présenté au Chapitre 3 évalue le nombre maximal de requêtes pouvant être satisfaites, pour un ensemble de stations fixées. La détermination d'un flot optimal permet d'évaluer le nombre minimum de véhicules et de relocalisations nécessaires à ce niveau de satisfaction de demande. Nous prouvons que tout flot réalisable peut être interprété comme un ensemble d'itinéraires de véhicules, à partir desquels peut être calculé un dimensionnement du système, i.e. le nombre minimal de places par station, de véhicules et de jockeys. D'un point de vue théorique, la complexité du problème reste encore toutefois inconnue bien que la détermination du flot réalisable est N P complexe. Un sous-cas polynomial dans lequel toutes les demandes doivent être satisfaites est cependant exposé.

Afin d'évaluer les modèles d'optimisation, un générateur de données réalistes a été développé et publié publiquement sur une plateforme open-source (voir Chapitre 2). Cet outil permet de générer un ensemble de stations réparties dans un territoire géographique donné, ainsi que des requêtes temporelles entre les stations et des temps de parcours tenant compte des effets pulmonaires de la demande de transport et de la congestion.

A partir de ces données, des instances de topologies et de tailles diverses ont été résolues à l'aide de deux solveurs distincts (GLPK et CLPEX). Une première étude sur de petites instances (i.e. 10 stations, 500 demandes journalières et un découpage temporel de 10 minutes) montre que les temps de résolution restent en deçà de la seconde. Concernant GLPK, la majeure partie du temps de calcul est monopolisé par la construction du programme linéaire (34 secondes en moyenne). D'autres implémentations ultérieures avec CPLEX ont permis de réduire ce temps de génération à une demi-seconde. vi Un résultat intéressant concernant la résolution des programmes dans leur version relaxé a également été observé. Dans près de 10% des cas, la valeur optimale obtenue n'est pas entière mais ne s'éloigne jamais de plus d'une unité de valeur de la solution entière.

Pour une instance du problème donné, la variation du nombre maximal de véhicules et de relocalisations journalières a permis de mettre en évidence une frontière de Pareto bien distincte qui confirme l'opposition de ces deux critères. Un opérateur d'autopartage peut alors aisément déterminer, pour différents niveaux de satisfaction de la demande, le compromis idéal entre ces deux objectifs.

Une autre étude faisant intervenir des relocalisations de véhicules à instants fixes de la journée (toutes les heures, toutes les deux heures, etc.) a montré que des temps de calculs bien plus intéressants pouvaient être obtenus tout en conservant une qualité de solution (nombre de demandes satisfaites) très convenable. En comparaison d'une stratégie de relocalisation toutes les 10 minutes, relocaliser toutes les heures par exemple permet d'obtenir les gains de temps de calcul qui s'élèvent à 94% en moyenne, avec un écart de valeur optimale de 1%. Ce résultat est directement lié à la réduction de densité des graphes lorsque les stratégies de relocalisation sont plus étalées dans le temps, diminuant drastiquement le nombre d'arcs et facilitant la résolution du problème.

Localisation des stations et prise en compte des contraintes énergétiques

La modélisation du problème de localisation des stations s'appuie directement sur le modèle de dimensionnement optimal précédemment étudié. Cependant, les stations ne sont plus considérées comme telles mais en tant que sites potentiels d'implantation. Le problème consiste alors à déterminer le sous-ensemble de sites, dont la dimension est donnée en paramètre, permettant de capturer le plus grand nombre de demandes, i.e. de dimensionnement optimal. L'ajout de variables booléennes et de contraintes relatives à la sélection des sites permet d'exprimer le problème sous la forme d'un programme linéaire mixte en nombre entier.

Notre aspiration à étudier ce problème avec les véhicules électriques nous a amené à adapter nos modèles de façon à tenir compte de deux composantes additionnelles : la capacité des batteries et la puissance de charge des bornes en station. La première limite la distance maximale parcourue par chaque véhicule (aujourd'hui à environ 160 kilomètres sans recharge) et la seconde influe sur le temps requis pour recharger les batteries.

Pour intégrer ces composants, il devient alors nécessaire de suivre les véhicules au cours de leur exercice journalier. Les précédents modèles ne permettant pas cette possibilité, un nouveau modèle contournant la problématique d'interprétation des flots a été élaboré puis amélioré. Une heuristique gloutonne proposée à la fin du Chapitre 3 permet en outre d'identifier une solution réalisable vérifiant les contraintes énergétiques.

Une étude d'évaluation des capacités minimales des batteries électriques est proposée au Chapitre 6. Basée sur un cas d'application concret, elle montre que des batteries d'une autonomie de 80 kilomètres suffisent dans le contexte d'un système d'autopartage comparable à ceux observés dans la réalité. Ce résultat ouvre de nombreuses ouvertures quant à l'utilisation de la capacité résiduelle non utilisée. Diverses applications sont exposées et misent en perspective à travers le point de vue des acteurs de la mobilité et de l'énergie.

Une seconde étude basée sur ce même système (15 stations, 30 véhicules et 200 demandes journalières) montre qu'un niveau de demande deux fois plus élevé peut être géré avec des capacités de batterie actuelles.

vii

Perspectives de recherche L'acquisition de données réelles

L'accès à des données réelles d'opérateurs d'autopartage reste aujourd'hui un frein à l'évaluation des modèles proposés. Bien qu'un générateur aléatoire permette de générer des données réalistes émulant certaines dynamiques de la demande en transport en zone urbaine, l'interprétation des solutions provenant de ces données reste limitée. La récente émergence de ces systèmes, à laquelle s'ajoute une évolution constante, explique en grande partie la difficulté à estimer précisément les demandes en autopartage. De plus en plus de recherches tentent cependant de capturer ces demandes spécifiques. Les résultats actuels, bien que prometteurs, restent encore inexploitables en pratique et très liés au contexte urbain. La mise à disposition de données "terrain" permettrait d'identifier certains schémas de déplacements récurrents alimentant ainsi les modèles d'estimation.

L'évaluation de la complexité des problèmes

D'un point de vue théorique, la complexité du problème de dimensionnement reste inconnue. Sa formulation admet de nombreuses similarités avec celle du flot maximal, sans qu'aucune réduction polynomiale n'ait put être mise en lumière. Le problème de circulation dans un graphe semble également présenter quelques similitudes. Il consiste en la détermination d'un flot réalisable circulant dans un graphe, sans considération de sources ou de puits. Déterminer la classe de complexité du problème de dimensionnement permettrait d'en améliorer la résolution, à plus forte raison si le problème est polynomial.

Moreover, the recent introduction of electric cars in carsharing systems brings additional technical and practical constraints. Indeed, shared vehicles spent more time on the roads and are more used than private ones. The relatively limited autonomy of today's electric batteries may restrain the service in providing reduced reachable distances and committing the vehicles to recharge, making them unavailable. Therefore, carsharing is an interesting and challenging topic, addressing various problems and dealing with strategic, tactical and operational aspect of those systems. This thesis focuses on the optimal design of one-way station-based carsharing systems. We consider the system design through two structural aspects: the optimal system dimensioning (number of parking places, vehicles, battery capacities, etc.) and the identification of appropriate stations' locations. Although the addressed problems do not directly concern the system management, some relevant aspects (like vehicle relocation operations) are nonetheless part of the models. The modelling approach uses graph theory to represent the system dynamics over time and various optimization models (ILPs and MILPs) are proposed. The objective is to deduce an optimal shape of the whole system (number of vehicles, parking places, jockeys, stations' locations, etc.) allowing to capture the maximum number of estimated time-dependent requests. Mathematical programs consider integer flow variables accounting for vehicles moving dynamically in the system. Electric vehicles are also included in an enhanced model version and context related constraints ensure that vehicles cannot travel distances exceeding their battery range. Power supply at charging points are also taken into account. Then, the optimization allows to study the impact of different power supply technologies and settle the minimal autonomy a shared vehicle necessitate in this environment.

All the models developed in this manuscript are applied to realistic case studies, using both random generated data and real estimated outputs of simulation tools. To account for the necessary vehicle rebalancing, strategies including vehicle relocation operations managed by jockeys (employees of the carsharing operator) are considered. We propose some graph simplifications reducing the problem size and leading to greatly improve solver capabilities as well as computation times. A greedy heuristic helping to quickly find feasible solutions and initialize the solver is also proposed and illustrated.

From an industrial perspective, several versions of the models have been implemented in a dedicated tool released as a Java Application Programming Interface (API). The software, today integrated into a dedicated IT platform devoted to the study of smart territories, provides ergonomic graphical interfaces and resolution methods, helping the actors of mobility design one-way carsharing systems with electric vehicles.

x

List of Figures

Context

Since the mid-twentieth century, the greater accessibility to the private car in industrialized countries has significantly improved the people mobility. In a lot of places, cars are still today the only transportation solution, especially in sparsely populated areas not or poorly served by public transport. In addition, their ability to be used on-demand and perform door-to-door travels with a certain level of comfort makes them very attractive and not easily substituted by other alternative transportation modes. The revolution that car has bought in terms of independence and transportation flexibility has far-reaching implications for the nature of societies [START_REF] Jakle | Lots of parking: Land use in a car culture[END_REF].

While this new mode of transportation greatly helped societies realize their aspiration for growth and prosperity, it also resulted in serious negative externalities. Today, most of the major urban agglomeration suffer from congestion, lack of parking spaces, air and noise pollution. [START_REF] Maibach | Handbook on estimation of external costs in the transport sector[END_REF] also identified several external costs (social, human, environmental, etc.) that can be attributed to car usage. The list includes accidents, water and soil pollution, climate change and energy dependency. As a consequence, worldwide public authorities placed the automotive in the heart of ecological concerns and over the last few years a lot of efforts are made to find alternative solutions [Mitchell, 2010]. In the last decades, sharing has become a practical answer to many global socio-economic issues. Although individual property is still predominant in our economic world, social organization has experienced that sharing information, goods or opinions can bring out sustainable answers. Environmental consciousness for instance is consistent with the idea of sharing, not only because it is a new way of consumption, but also of its implications on objects (or services) design [Ciari, 2012].

In the field of transportation, vehicle-sharing systems has emerged in the last twenty years as an innovative solution, dealing with both environmental and transportation issues. Particularly implanted in dense urban areas, they are now recognized as an additional mobility supply and a transportation mode in itself. Where traditional public transports, including buses, subways, trains and tramways fail at providing a great flexibility in terms of covered area and time availability, vehicle-shared systems bring out significant advantages. In 2007, the launch of Vélib' in Paris, France, disposed about 20,000 self-service bikes over more than 1,000 stations [START_REF] Laporte | Shared mobility systems[END_REF]. Its success has certainly asserted the idea and benefits of bicycle-sharing services around the world. Today, more than 7,000 systems involving over 800,000 bicycles are currently operational.

Almost in the same time, numerous carsharing systems has been launched and their indisputable success, mainly in north America, Europe and Asia, suggests that they will continue to expand in the coming years. Often praised and subsidized by public authorities (especially in Europe), carsharing provides the advantages of the automotive without the drawbacks of ownership. Cars are available on-demand at defined locations, and rented for short periods of time. Since each vehicle is more active on road and spend less time parked, carsharing participates to promote a more efficient and sustainable car utilisation. Recent advances in real-time Information and Communication Technologies (ICT) also reinforced the service attractiveness, providing better accessibility to manage vehicle reservations [Jorge and Correia, 2013].

In the early 1990s, due to increasing attention on environmental concerns, political authorities began to push for more fuel-efficient and lower-emissions vehicles. As a response, and driven by promising advances in batteries and energy management, automakers initiated the development of electric vehicles. Since 2008, electric cars are available to the public and as of 2015, the Renault-Nissan Alliance announced the milestone of 300,000 units sold worldwide. Include electric cars in their global fleet of vehicles came early in the history of carsharing. As reliable experimental fields, carsharing systems with electric cars actually helped popularizing the concept of plug-in electric vehicles while reinforcing their positive impact on the environment.

Fundamentally, carsharing systems embody a new paradigm with regard to car usage. Indeed, the economical model depends on the time and the distance the user travelled. Its operational principles modify drastically the way people perceive and utilize the vehicle. The standard user behaviour evolves from a property-based usage (i.e. using the vehicle because of owned it) to an utilization depending on real mobility needs. This phenomenon partly explains why carsharing users drive less and for shorter periods of time, helping to enhance traffic conditions.

Motivations

All carmakers reflect on the evolution of their business and are considering to become active actors of the mobility. They do not want to be limited to the design, the sale, the manufacture or the repairs of vehicles. The recent emergence of carsharing systems has raised a new potential business. As a complement to the offer of public transport, deliver and operate carsharing fleets, is now a promising market. To achieve these new objectives, car manufacturers have to elaborate methods and tools to assess the needs of a territory for this new mode of transport. The methods and tools need to estimate demand, assist in the design of carsharing stations but also should provide economic arguments justifying the choice of this new mode of transport. Moreover, primarily in large cities, the deployment of carsharing systems should move towards electric vehicles to take into account anti-pollution standards and even the prohibition of use of thermal motor vehicles. The energy constraints, brought by electric cars must be considered by the methods and tools. In addition, it will also be important to propose the operation methods of carsharing systems, taking into account their integration in the global system of multimodal transport.

Research scope and thesis organization

Carsharing development is literally driven by the user flexibility. The global trend to make the service more accessible greatly account for its success. Historical systems managed by private operators are said station-based. The fleet of vehicles is spread out diverse locations providing parking places and optional and specific infrastructure as charging points for electric vehicles. In this thesis, we focus on stations-based systems allowing one-way trips where users can take-off and return a car in different locations.

The scope of this thesis is dedicated to strategic and tactical problem arising in the design of those station-based one-way systems. Addressed topic include optimal system dimensioning, optimal station locations and the consideration of energy components. Some outputs of this work aim to evaluate the viability of a carsharing service with respect to a given territory and an estimation of a specific carsharing demand. Decisions are made at a high level, and measured at both macro and micro scale. The global purpose is to help decision makers to stand on the potential of such service before building and operating it.

The next Chapter is dedicated to carsharing systems and their related problems. A brief history, today's operating schemes and their benefits for the community and the environment are especially described. Then, an overview of the literature looks over various topics related to carsharing. More especially, demand modelling and strategic vehicles relocation aspects are unfolded as decisive challenges that design methods must encompass. Finally, a random generator coping the lack of available carsharing data is described. A synthesis and some outlooks are provided at the end of the chapter.

Chapter 3 addresses the system dimensioning problem for one-way carsharing systems. For fixed stations and demands, it consists in determine the relevant system components values (number of vehicles, parking places and relocation operations) allowing the system to run at its maximum efficiency. A first sight at the existing literature about this topic is first given. Then, we present a mathematical model based on time-expanded graphs and dealing with the system dimensioning optimization. The proposed model accounts for vehicle relocation operations and maximizes the total number of demands. Although its formulation is very closed to a maximum flow problem, the problem complexity is still unknown. Nevertheless, a polynomial sub-case of the problem is exhibited in the end of the chapter.

Chapter 4 is devoted to the evaluation of the system dimensioning MIP formulation. Exact methods using both open-source an proprietary solvers are evaluated through four studies. The first one computes optimal solutions maximizing the number of satisfied demands according to different values of the maximum number of vehicles and relocation operations during a day. Computation times and a 3-pareto frontier are especially analysed. Then, we evaluate the model scalability and challenge the exact method resolution on larger problem sizes. A coupling between linear program building times and graph densities is detailed. Also, important improvements applying another solver (CPLEX) are exposed. Next studies focus on vehicle relocation strategies operating the system during a typical weekday. More especially, strategies balancing the system at fixed times of the day are evaluated and compared to a baseline situation where vehicles can be relocated at any time. The third study focuses on the impact on graph density whereas the last one examines improvements on computation times.

Chapter 5 deals with the station location problem and the electric vehicle inclusion in the optimization models. An enhanced mathematical program is introduced and new decision variables cope with the selection of potential carsharing sites. Additional constraints also accounts for a limited number of jockeys operating the vehicle relocations. Besides, a dedicated reading of the problem highlights its strong dependence with previous statements and apprehends it as a generalized version of the system dimensioning model. In the second part of the chapter, we introduce components related to electric cars. More especially, the vehicle battery range and the power supply of charging points in stations are considered. Then, we discuss the various issues that arise when considering a non-unit flows, especially the flow interpretation as individual vehicle routes. We finally introduce the last MIP model including electric vehicles. To overcome the combinatorial explosion of the number of variables, some model simplifications are then detailed. In order to improve the performance of the solver, the description of a greedy heuristic terminates the chapter. The algorithm helps the solver converging to an exact solution in finding rapidly a good lower integer bound. A simple example illustrates the algorithm mechanics.

Chapter 6 is dedicated to the study of sufficient electric car batteries for the carsharing usage. The optimal system containing 30 electric vehicles is designed from data randomly generalised. The results globally reflect realistic operative indicators similar to existing carsharing systems, such as the time spent on the road (3 hours) and the average number of demand each vehicle satisfies during the day (5 demands). Moreover, specific outputs of the optimization allow to track every vehicle in the system as well as the specific amount of energy delivered in each station. Besides, the observed maximum battery range (difference between the largest and the smallest level reach during the day) allows us to state on the minimum required battery capacity. This result is especially useful for car makers wishing to dimension their vehicles for carsharing services. Finally, we analyse the consequences of an increasing number of demands on the system sustainability and optimal battery range.

Chapter 7 ends this dissertation summarizing the results of the previous chapters. Perspectives and future works are also suggested.

Bibliography of chapter 1 [Ciari, 2012] Ciari, F. (2012). Sharing as a key to rethink urban mobility: Investigating and modeling innovative transport systems. PhD thesis, ETH.

[ [START_REF] Jakle | Lots of parking: Land use in a car culture[END_REF]] Jakle, J. A. and Sculle, K. A. ( 2004). Lots of parking: Land use in a car culture. University of Virginia Press.

[ Jorge and[START_REF] Correia | Carsharing systems demand estimation and defined operations: a literature review[END_REF][START_REF] Correia | Carsharing systems demand estimation and defined operations: a literature review[END_REF]. Carsharing systems demand estimation and defined operations: a literature review. EJTIR, 13(3):201-220.

[ [START_REF] Laporte | Shared mobility systems[END_REF][START_REF] Laporte | Shared mobility systems[END_REF]. Shared mobility systems. 4OR, 13(4):341-360.

[ [START_REF] Maibach | Handbook on estimation of external costs in the transport sector[END_REF][START_REF] Maibach | Handbook on estimation of external costs in the transport sector[END_REF]. Handbook on estimation of external costs in the transport sector. CE Delft. [Mitchell, 2010]

Abstract

This chapter is dedicated to carsharing systems. A description of their operational principles and a brief history are firstly presented. More particularly, some specificities and characteristics highlight their legitimacy as interesting solutions to actual transportation issues. Then, an overview of the related literature is given. It addresses numerous problems from demand modelling to system management. Specific topics about system design will be given in the next chapters. The chapter follows with the description of a random generator produces data for one-way carsharing systems. Assumptions, operating principles and outputs are especially detailed. Finally, a summary and some outlooks are provided at the end of the chapter.

Carsharing systems

Principles and brief history

The main idea of carsharing is to share a fleet of cars between users. Basically, it's a model of car rental where people rent cars for short periods of time. Carsharing systems are mainly intended for occasional drivers whom gain the benefit of private vehicle use without the costs and responsibilities of ownership [Shaheen et al., 1998]. Its principle is based on the vehicle usage rather than vehicle possession. Costs related to insurance, maintenance, fuel (or electricity), taxes, depreciation, etc. are supported by car owners, i.e. mostly cooperative organizations or private operators. They differ and have to be distinguished from traditional auto-rental services mainly because they are oriented to short-term rentals and fuel costs are included in the rental fee. Mainly located in dense urban areas, they contribute to fill the gap between existing modes of transportation [Louvet and Godillon, 2013].

Nowadays, there are many implementations of carsharing systems adopting many different forms but generally, individuals access vehicles on an as-needed basis by joining an organisation that maintains a fleet of vehicles (essentially cars and light trucks) in a network of locations. These are usually deploy in the vicinity of public transport stations, neighbourhoods, employment centres and universities [Shaheen et al., 1998].

Although the concept of carsharing is constantly evolving, one of the most concise definition could be the one given by [Millard-Ball, 2005] which defines carshaing as "a membership program intended to offer an alternative to car ownership under which persons or entities that become members are permitted to use vehicles from a fleet on an hourly basis."

More recently, in 2010, the french law defined carsharing systems under these terms : "Carsharing is the pooling of an inland transport motor vehicles fleet for the benefit of subscribers. Each one of them can access a driverless vehicle for the ride of his choice for a limited time." [n o 2010-788 Article 54, 2010] The first experiment of carsharing is identified in [Shaheen et al., 1999] as Sefage, a Swiss company created in 1948. For a variety of reasons, almost all effort at organising carsharing organisations resulted in failure until the early 1990's. Different causes has been discussed to explain the origins of these common failures. The list includes excessive financial costs, low demand, service quality deterioration, technological limitations, as well as a restricted service area and a lack of government support [Harms andTruffer, 1998, Cousins, 2000].

Since then, many schemes of the system have been implemented and the basic concept of carsharing has evolved in many ways. Over time, profit-making organisations have emerged as the most important actors in the carsharing market, even though the number of non-commercial and cooperative organisations is still the largest. Lessons learned from unfortunate experiences combined with technological advances helped launching new carsharing programs. Historically, first successful systems started in Europe. Their development has highly contributed to spread and confirm the viability of vehicle-sharing systems across the world. Today, the actual world's leader carsharing company is Zipcar. Founded in 2000, its global vehicle fleet exceeds 12,000 vehicles and 950,000 members, mainly in the US [Zipcar, 2015].

Last decade has recorded the highest carsharing market growth. In 2007, the total worldwide number of carsharing members was estimated to 348,000 and the shared fleet of vehicles to nearly 11,700 [Shaheen and Cohen, 2007]. Almost ten years later, in 2014, these numbers are approximated to 4,94 millions ( ×14) and 92,200 vehicles respectively ( ×8) [Statista, 2016]. Numerous programs are launched here and there among all continents. It continues to expand in large part due to advanced technologies whose the greatest representatives are surely smartphones. Besides, incentive public policies allows private firms to reserve public on-street parking making the service more convenient and attractive. Propitious indicators and worldwide experts anticipate further development for the forthcoming years [Shaheen and Cohen, 2013].

Carsharing models

In this thesis, we focus on carsharing systems managed by private operators. Three different models called respectively 'Round-trip', 'One-way' and 'Free-floating' can be find around the world. They can be distinguished by their constraints related to the use of vehicles and the fact of having or not stations. In order to access the service, carsharing companies generally required members to pay a yearly registration fees. Sometimes it is a deposit that is refunded when membership ends. Then, a monthly rate based on the time spent on roads and the distance travelled testifies to the personal usage of each member.

The technology provided by the operator can vary enormously. In Europe, most operator offer different kind of vehicles, from small city cars to large cargo vehicles. Generally, members have access to vehicles on-the-go using smart cards or PIN (personal identification number). They can also make a reservation online or using (smart)phones to guarantee the availability of a vehicle. The service can sometimes be related to public transport, offering a large mobility supply to individuals.

Round-trip and one-way systems are said station-based. They involve a small to medium fleet of vehicles, available at several stations, to be used by a relatively large group of members [Shaheen et al., 1999]. Vehicles are dispersed all across the city through many indicated stations, where a fixed number of parking places stores the vehicles. Generally, carsharing companies dispose of their own dedicated parking lots situated on-street or off-street according to contractual arrangement with the entity (private or public) managing the parking. The number of lots can varies according to the size of the system and the available urban space, but since carsharing is mainly implanted in dense urban areas, stations are often small. In Paris, for instance, the number of parking places is between 4 and 7 [START_REF] Autolib | Autolib[END_REF]. Also, stationbased systems can provide additional specific infrastructure if necessary. The carsharing service Autolib' in Paris, offers charging points for electric vehicles and kiosks for customer service.

The Round-Trip system P

Historically, the first carsharing scheme to be implemented was the roundtrip system. As such, it is today the best established commercially and has been largely studied. Basically, It requires users to return vehicles to the station they were picked up. Such systems are simple to design since the incoming demand in each station is sufficient to plan vehicle stocks. The user behaviour is mainly oriented to leisure and household shopping purpose [Barth andShaheen, 2002, Costain et al., 2012].

The One-way system P P

One-way carsharing scheme is more flexible than round-trip. It allows users to pick up a vehicle from a station and return it in a different one, possibly distinct from the origin. Unfortunately, this greater flexibility comes with hard operational problems due to the uneven nature of the trip pattern in urban areas. Indeed, empty stations exclude potential requests to be satisfied. Conversely, crowded stations do not allow an incoming vehicle to park. Thus, the system imbalance must be corrected so that vehicles can be relocated to suitable places. This problem referred as the vehicle imbalance problem is discussed thereafter.

However, let notice that despite these difficulties for the operator, one-way system captures more trips than the alternative system thanks to this flexibility which is a critical factor to join a carsharing scheme [START_REF] Efthymiou | Which factors affect the willingness to join vehicle sharing systems? evidence from young greek drivers[END_REF].

The Free-floating system

Nowadays, many carsharing schemes have been tested and experimented. Although first ones have been station-based designed, we have witnessed in the last decade the emergence of carsharing models without stations. The user can picked up on-street parked vehicles owned by the system operator and parked on any legal parking space within a defined area. This new feature comes with the propensity to assign more and more flexibility to the service. Point-to-point free-floating carsharing (often referred to as flexible carsharing) corresponds to a sharing scheme where usage is typically spontaneous. Vehicle reservations are mostly made several minutes in advance. The system operator ensures a service quality based on vehicle maintenance and available parking places. The largest free-floating system is operate by car2go mainly in Germany. In 2015, the service account for more than one million members.

Positive impacts

As an innovative alternative to private car ownership, carsharing is a interesting trade off between distance and flexibility. On the one hand, the car provides the freedom to cover entire urban areas. Even with electric vehicles, for which the autonomy is limited, distances of more than 150 kilometres can be considered. On the other hand, the fact that cars are available on-demand relieves users from the rigidity of public transport timetables. Moreover, stationbased carsharing systems aim at reducing the time spent at searching for a parking lot, which is often important in dense urban areas. In France, its contribution to the global congestion is evaluated between 5 and 10% [Certu, 2012]. As a consequence, carsharing is now considered as an attractive transportation mode filling the gap between traditional public transport and private vehicle use.

In the last decade, several authors have showed that carsharing systems have positive impacts on users, the transportation system and the environment. Although not all of these commonly attested benefits are documented with empirical data, next sections present substantial agreements about carsharing on the urban mobility, financial gains and the environment.

Urban mobility

The carsharing economic model is founded on the use of the vehicles. The cost for moving from point A to point B depends on the distance and the time the user spend on the road.

As such, carsharing infers on user behaviours, whom aligned their car usage on those criterion, and therefore provides greater incentive for members to be selective about driving. In other words, members have a heightened awareness of travel costs and tend to reduce unnecessary trips to save money. A study conducted in 2004 reports that carsharing users reduce their vehicle kilometres traveled (VKT) -or vehicle miles traveled (VMT) -by 50% after joining the organisation [Cervero and Tsai, 2004]. More recent result evaluated this decrease to 27% in 2011 [Martin and Shaheen, 2011]. Another often observed outcome of carsharing is a fall in car ownership rates. The number of vehicles per household is a half lower for carsharing users than private cars users [Martin et al., 2010, Ter Schure et al., 2012]. When carsharing responds to mobility needs, members postpone or even drop the idea of buying a new car [Martin et al., 2010, Sioui et al., 2013].

Globally, each shared vehicle is used more efficiently [Litman, 2000, Schuster et al., 2005]. Because of higher utilization rates than single-user private vehicles, they spend more time on the road and less time parked (which represent for a private car almost 95% of its total use time, as mentioned in [Certu, 2013]). A direct consequence in the medium to long-run is that parking requirements in dense areas should also decrease [Mitchell, 2010], freeing urban space. Those observations argue that carsharing decreases the number of vehicles on the road. However, the less vehicles on the road, the better the traffic fluidity is. Thus, carsharing also helps reducing traffic congestion at peak times.

Economical aspects

General costs related to car ownership are commonly split into fixed and variable expenses. According to the total distance travelled, driving habits or local parking costs, the variable costs might be very different from one car owner to the other. However, the share of fixed costs, such as the purchase price of the vehicle, its depreciation over time or insurance, still remains predominant [Cordier, 2012]. In this context, embracing a carhsharing service where the price only depends on the vehicle usage can grants its users the car mobility at interesting costs.

Nevertheless, those benefits are not relevant for every car user. Basically, the less the car is used, the more carsharing services become interesting. With respect to local costs, researches have shown that car users driving less than 10,000 kilometres per year (as much as 15,000 km/y) could save money using carsharing [Litman, 2000, Prettenthaler andSteininger, 1999].

Environmental effects

Obviously, reducing the number of cars on the road have have positive environmental effects. Results of recent survey studies seem to indicate that greenhouse gas (GHG) emissions are largely reduced [Martin andShaheen, 2011, Firnkorn andMüller, 2011]. These results are reinforced with the recent emergence of electric vehicles, for which CO2 emissions are largely reduced. Besides, they provide noise reduction since electric cars are quitter than thermal ones. Moreover, the reduction of parking demand can be used to reallocate the land for additional green spaces, new mixed-use development, or other community needs [START_REF] Cohen | Carsharing: A guide for local planners[END_REF].

Related problems

Academic literature on carsharing systems is very prolific since a couple of decades. Inspired and motivated by their recent diffusion, researchers report on a large variety of topics covering system design, system management, social characterization, logistic, etc. Approaches use both qualitative and quantitative methodologies. Addressed problems are generally segmented into the following categories [Ciari, 2012]:

• Market analysis,

• Impacts of carsharing,

• Carsharing operations and management.

Although slightly outdated, this categorization is inspired by a literature review of Millard-Ball et al. [Millard-Ball, 2005]. A complete updated overview on problems arising in such systems can however be found in the work of Jorge et al. [Jorge and Correia, 2013].

In a previous talk, we have already given an overview of the positive impacts carsharing can provide. In addition, this thesis is dedicated to optimal system design and focus more particularly at the optimal dimensioning and station locations. In the next chapters, we give a deeper look about current results on those particular topics. The following sections will consequently focus on market analysis and problems related to system operations and management.

Social aspects and demand modelling

Who are the users and why they use the service are probably the major addressed questions about carsharing. Most works aim at characterize and analyse members' behaviour, so that the specific transportation demand associated to carsharing can be estimated mathematically. In the domain of transportation, this popular topic is known as the demand modelling. The outputs of such models are then used to deal with operational research problems and system management. By doing so, carsharing decision makers are endowed with accurate inputs helping the resolution of other problems more efficiently.

Unfortunately, the ability to predict the demand for carsharing still is a quite challenging and hard topic. Several reasons, manly related to the uneven nature of the demand, can explain why economists and modellers struggle to propose accurate tools [START_REF] Danielis | The potential demand for carsharing from university students: an Italian case study[END_REF]. First, the carsharing demand is highly dependant on the mobility patterns, which is partly recurrent (such as home/work travels or study commuting) and partly random. Secondly, involved decisions leading to carsharing joining are many and various. In addition, they include both quantitative and qualitative criterion. They not only depends on the price, the quality, the travel time, the trip distance and comfort, but also on the supply of the other competing or complementary modes. Finally, some side effects due to the dynamics of the system itself may influence the demand. The evolution of the service quality over time (e.g. the availability of vehicles or parking places) can fluctuate the incoming demand, making its prediction even more complex.

Using statistical data and user surveys, most studies have nevertheless demonstrated important tendencies. Basically, the average carsharing member has the following characteristics [Brook, 2004] [Millard-Ball, 2005] [Lane, 2005] [Zheng et al., 2009] [Costain et al., 2012] [Efthymiou et al., 2012]:

• age between mid-30s to mid-40s,

• people highly educated and environmentally aware,

• income higher than average.

Regarding the geographical aspects of carsharing, its usage is highly correlated with the use of public transports and most successful applications are running in dense urban areas [Cervero, 2003, Millard-Ball, 2005, Burkhardt and Millard-Ball, 2006]. Moreover, the accessibility to the stations, in terms of distance between home/work and the nearest station, is identified as a critical factor to joining a carsharing system [Zheng et al., 2009, Costain et al., 2012, Efthymiou et al., 2012].

Identify the main factors which generate and influence the demand greatly contribute to give a good prediction of a carsharing service. Stillwater et al. [Stillwater et al., 2009] compared the use of carsharing vehicles to build-environment and demographic factors in the US. They concluded that the most significant variables were: the street width (-), the provision of a railway service (-), the percentage of drive-alone commuters (-), the percentage of households with one vehicle (+), and the average age of the stations (+). Signs (-) or (+) are used to indicate whether the indicator is negatively or positively related to the carsharing demand. The street width and the percentage of drive-alone commuters may not have a clear intuitive explanation at first sight although those metrics are significantly related to the level of carsharing demand. The authors postulated that street width contains informations about pedestrian environment (where narrow streets are more pedestrian friendly) and about the land use in general (narrow streets trend to denote older residential or mixed-use development) which make sense since carsharing and walking behaviour are known to be strongly related [Cervero, 2003]. The proportion of drive-alone commuters are negatively related because these people are in general already vehicle-owners. Indeed, a high level of commuting vehicles tend to signify that the neighbourhood has a poor public transit or is already provided with high-density mode amenities. is a real challenge for the future since it's reasonable to think that one-way carsharing systems will be increasingly present in the coming years.

The vehicle imbalance problem

In one-way systems, one of the most challenging problem deals with vehicle relocations strategies. Unlike round-trip models, the departure station and the arrival station are not necessary identical. As a result, the dynamics of the system may conduct to critical situations. On the one side, empty stations prevent the members to find a vehicle, whereas on the other side, full stations prevent them to park. This property induces imbalance issues to the system and a lot of efforts are made to understand the dynamics involved and find possible solutions to handle it.

A first intuitive approach for solving the vehicle imbalance problem is to consider that the operator have to do periodic vehicle relocation operations among stations. In general, carsharing operator recruit employees (also referred as jockeys) to balance the system and avoid critical situations. Some studies, using discrete event simulation models, help operators to manage their systems minimizing the available resources (such as vehicles and staff members), while maintaining certain levels of service [Barth and Todd, 1999, Kek et al., 2006, Kek et al., 2009]. More specifically, the model presented in [START_REF] Kek | A decision support system for vehicle relocation operations in carsharing systems[END_REF] has been tested and validated using real data, a one-way carsharing company in Singapore called Honda ICVS. Proposed solutions aimed at reduce the staff cost of about 50%.

Other authors have explored the problem under the optimization methods perspective. For instance, the model proposed in [Nair and Miller-Hooks, 2011] is a stochastic mixed-integer programming (MIP) model with the objective of generating least-cost vehicle redistribution where the demand is known probabilistically. In [Smith et al., 2013], the authors find the optimal rebalancing strategy solving two different linear programs in a fluid model of the system: one in order to minimize the number of rebalancing vehicles, the other for minimizing the number of rebalancing drivers (jockeys), considering that the number of waiting customers remains bounded. The authors stated that the "two objectives were aligned" and concluded that, for Euclidean network topologies, the numbers of jockeys the systems required is between 1/4 and 1/3 of the total number of vehicles.

Very recently, [Zakaria, 2015] focuses on the logistic aspects of relocation operations, including the number of jockeys, and specific day-times for relocation and shifting operations. Different relocation policies are especially studied. The better performance at minimizing the number of rejected demands was obtain using a relocation policy where jockeys can have information on the future state of the system. Those anticipations were calculated using historical data of the system and predictions. The author suggest that applying policies based on intuitive decisions, such as distance to stations and number of cars at stations, without taking into consideration the effect of these relocation operations on the whole system will not be very efficient in reducing the number of rejected demands.

Another innovative approach is to consider that clients can be used to relocate the vehicles through various incentive mechanisms, mainly based on rewards. Prices could be used in order to encourage users to sign up to "trip splitting" and "trip joining", as showed in [Barth et al., 2004]. The principle is very simple: when users want to travel from a station with shortage of vehicles to another one with an excess they are prompted to share the ride in a single vehicle (trip joining), while, conversely, when they wanted to travel from a station with too many vehicles to one with a shortage they are encouraged to drive separate vehicles (trip splitting). Despite the fact that this strategy effectively balances the system in theory, it relies on assumptions that may be unrealistic in practice. For instance, it's not relevant if a majority of travellers value privacy and convenience over minor cost saving. Also, this scheme does not work if trip-joining policies make carsharing similar to carpooling, which has severe sociological barriers associated with riding with strangers, mainly for safety and security reasons [Chan andShaheen, 2012, Correia and[START_REF] Correia | [END_REF]). Finally, with respect to trip splitting, impossibilities could occur if users simply do not want to be divided.

A generator addressing the lack of data

As pointed out earlier, the carsharing demand is hard to model and forecast. As far as we know, there is no available model for one-way carsharing in the literature which is not context specific. Besides, operational data from carsharing operators are not accessible. Although some global indicators of the service are sometimes reported (such as the stations' locations, the number of vehicles or the number of daily requests) no private company release the details of the registered demand, mainly for users' confidentiality reasons.

The problems addressed in this thesis deal with the design of a one-way carsharing system. In this work, we consider the carsharing demand as an input of the addressed problems and, as such, need to be evaluated. This section presents the mechanics of a random data generator developed during the thesis. Basically, the generator produces time-dependant one-way carsharing demand among a set on randomly positioned stations. The provided data are used to evaluate the developed models proposed in the next chapters. The generator can be downloaded freely as an open-source software at [Carlier, 2015]. Figure 2.1 illustrates the main frame of the software. We hope that it could help the research community, stimulate system design implementations and provide benchmark data to compare methodologies.

Assumptions

Some data produced by the generator are time-dependant. The purpose of the generator is to provide temporal data during an average day. Carsharing demands and travel times are then defined over a 24 hours period, segmented into T ∈ N discrete time-steps. The total number of time-steps is user-settable. It can vary from 24 to 1440, representing respectively a time-step period of one hour and one minute.

The vehicle speed is assumed constant during a trip. Although congestion is not directly considered in the model, travel times are penalize during rush hours. Two weight factors (one for the morning, one for the evening) allow to extend any trip duration if it is performed during defined time windows.

Finally, it is also assumed that the generator neglects the time needed for some operations. For instance, the time needed to park a vehicle, borrow it or plug it into a charging point in the case of electric vehicles are not considered.

Station positioning

The first phase positions S ∈ N carsharing stations within a given territory. The area is modelled as a square, only defined by its side length expressed in metres. Then, two distinct methods, called respectively the uniform method and the centroid method, spread the stations among the territory. The uniform method merely positions randomly the stations, assigning uniform random values to the station's coordinates. The centroid method positions stations over two distinct zones: a central area (in general representing the center of the city) included in a larger one (representing the suburbs area), both defined as a square. The generation algorithm takes two additional parameters: the percentage of total area the center must represent and the probability that a station is contained in the center. Once the geographic division is made, every station is then positioned randomly in the area where it belongs. Finally, the maximum size for each station is randomly generated using a discrete uniform distribution over an integer interval given by the user.

Demand generation

The second phase generates randomly D ∈ N demands over time between stations. In a first step, the generator schedules and distributes randomly each request over time. The random demand distribution can be specified through a dedicated frame where the user can tune every level demand on an hourly basis. Because levels are considered relative to each other, their exact value are not relevant. The random distribution is obtained normalizing all the values. In practice, most profile distributions are very similar to the one presented in Figure 2.2 where two noticeable picks during morning and evening demarcate the symmetrical mobility pattern in dense area.

In a second step, the generator identifies origins and destinations of each temporal demands. Usually, in urban context, the demand goes globally in the same direction: from the suburbs to the center during the morning and from the center to the suburbs the evening. Both morning and evening rush hour slots (traffic peaks) are settable. As depicted in Figure 2.2, the morning rush is usually between 7 and 9 o'clock whereas the evening rush is between 15 and 19 o'clock. A fixed demand proportion during rushes can be specified by the user. The generator finally calculate the origin and destination stations with respect to the departure time of each demand. The travel time is deducted from the distance between stations and the average car speed. As stated previously, the time is penalized in case of traffic peaks.

Outputs

The data produced by the generator are saved as XML files. Two markup sets hold all the required information. The first one, dedicated to stations, reports the following data:

• id: the station ID,

• xPos, yPos: the station geographical coordinates,

• maxSize: the maximum number of available parking lots in the station.

The second set, dedicated to demands, includes the following data:

• id: the demand ID,

• idsOrigin, idsDestination: The IDs of departure and arrival stations,

• nbDemand: the number of individuals requested a vehicle,

• departureTime, arrivalTime (expressed in number of time-steps): time of the request and time of the expected arrival at destination.

Synthesis and outlooks

In this literature overview, we have seen that carsharing systems can be a real alternative to private vehicles. Mainly located today in dense urban area, they provide positive impacts not only on the environment but also on urban mobility. A rich literature on these topics tend to demonstrate that congestion, pollution and parking demand can be greatly enhanced with such systems. Providing an interesting trade off between the covered distance and flexibility, carsharing systems are now recognized as good solutions to deal with urban transportation problems.

Three carsharing schemes, called respectively round-trip, one-way and free-floating, are popular worldwide. Constraints on trips as well as the provided system infrastructure (stations) distinguish one from the other. The current trend is to offer more flexibility by allowing oneway trips without the obligation to parked at fixed places. In this thesis, we focus on one-way carsharing systems managed by private operators. Those station-based services allow the user to picked up a vehicle at any station and return it in a different one.

The recent emergence and diffusion of carsharing have raised various research topics covering, among other, demand forecasting, network design and system management. A first sight at the demand characterization show that the typical carsharing user is relatively young, well educated and has an income higher than average. Actually, studies trying to figure out who the users are greatly help to design accurate demand forecast models. This social characterization is essential and directly related to demand modelling research. The addressed approaches vary from linear regression and cluster analysis to more sophisticated method such as activity-based microsimulation. Unfortunately, articles reviewed on demand estimation have generally not taken into account the one-way option. Moreover, attempts to estimate the proportion of travellers that could join and use a carsharing service are very often context specific which limits the scope and the applicability of the results. Since one-way systems will continue to spread out in the near future, it will be crucial to develop realistic models that can handle those specific mechanics in a multimodal environment.

We have presented in the end of this chapter a random demand generator for one-way carsharing systems. The development of the generator was originally motivated by the lack of available data. The resulting outputs produced by the tool emulate a potential carsharing systems with stations and temporal demands during a representative period of 24 hours. The source code is freely accessible [Carlier, 2015] and we aspire that it could help and stimulates further research.

Regarding the system management aspects, the main problem faces carsharing operators is how to determine and maintain the right number of vehicles in stations so that the system efficiently satisfies the requested demands. This problem, referred as the vehicle imbalance problem, involves vehicle repositioning strategies performed by employees of the operator (jockeys) in order to provide the best operational configuration. Simulation and mathematical programming are the two most commonly used techniques for dealing with this problem. Many studies stated that the ability to balance vehicles between stations is crucial for the overall system performance. Indeed, good relocation strategies allow the system operates at a reliability level that could not be achieve otherwise.

Problems addressed in this thesis deal with the system design of a one-way carsharing system. More precisely, how to conceive the most efficient system according to a demand estimation? How many stations? Where? With how many parking slots and vehicles? Although system design problems are addressed before system management, some inner mechanics such as vehicle relocation are still relevant to be considered. In this chapter, we have intentionally eluded those particular topics because a specific literature review is provided in next of the thesis. [START_REF] Ciari | Estimation of carsharing demand using an activity-based microsimulation approach: Model discussion and some results[END_REF][START_REF] Ciari | Estimation of carsharing demand using an activity-based microsimulation approach: Model discussion and some results[END_REF]. Estimation of carsharing demand using an activity-based microsimulation approach: Model discussion and some results. International Journal of Sustainable Transportation, 7(1):70-84.

[ [START_REF] Cohen | Carsharing: A guide for local planners[END_REF] [ [START_REF] Firnkorn | What will be the environmental effects of new free-floating car-sharing systems? the case of car2go in ulm[END_REF]] Firnkorn, J. and Müller, M. ( 2011). What will be the environmental effects of new free-floating car-sharing systems? the case of car2go in ulm. Ecological Economics, 70(8):1519-1528.

[ Harms and[START_REF] Harms | The emergence of a nation-wide carsharing co-operative in switzerland. A case-study for the EC-supported rsearch project "Strategic Niche Management as a tool for transition to a sustainable transport system[END_REF][START_REF] Harms | The emergence of a nation-wide carsharing co-operative in switzerland. A case-study for the EC-supported rsearch project "Strategic Niche Management as a tool for transition to a sustainable transport system[END_REF]. The emergence of a nation-wide carsharing co-operative in switzerland. A case-study for the EC-supported rsearch project "Strategic Niche Management as a tool for transition to a sustainable transport system", EAWAG: Zürich.

Abstract

This chapter introduces the optimal system dimensioning problem arising in the design of a carsharing service. A formal statement helps to apprehend its challenging aspects and a mathematical approach using graphs expanded over time is detailed. An integer linear program considering flow variables on those specific graphs and maximizing the total number of satisfied demands is provided. We prove than any flow solution can be interpreted as vehicle itineraries and translated into an optimal system dimensioning. The end of the chapter is dedicated to the study the problem complexity and a polynomial sub-case is exhibited.

Introduction : problem description

The first part of this thesis is dedicated to the optimal design of a carsharing system when stations are fixed. We assume that a time-dependant carsharing demand can be estimated from origins to destinations. This demand covers a geographical area where a carsharing operator is interested to established its service. Without any doubt, the demand estimation model as well as the time period considered in the study are critical inputs in the decision process. This bias is discussed afterwards.

In this work, the meaning of optimality will be considered as the will to capture the maximum number of demands. Somehow, this objective is aligned with the maximization of the operator's revenues. Indeed, the more demands the systems is able to fulfil, the more profits the operator can generate. As seen in [START_REF] Jorge | Testing the validity of the MIP approach for locating carsharing stations in one-way systems[END_REF], the optimization process should also integrate vehicle relocation operations. They are the only known "technique" to re-equilibrate the system and reach a higher satisfied demand.

In the reminder of this work, this system design problem will be refer as the System Dimensioning Problem [sdp]. Its concise formulation follows:

System Dimensioning Problem [SDP]:

Considering potential one-way carsharing station locations and demands over time, what is the optimal system configuration capturing the higher number of demands?

We define a system configuration as the quantification or the numerical description of the following components:

1. the number of demands satisfied, accounting for the global satisfaction level, 2. the number of vehicles needed to run the system, 3. the vehicle relocation operations, supported by the operator. This chapter is organised as follow. Section 3.2 is devoted to a brief state of the art and related models found in the literature. Then, Section 3.3 gives a formal statement of the problem. Assumed inputs and expected outputs are especially specified. A mathematical model based on graphs expanded over time helps to represent the system dynamics. Then, an integer linear program dealing with the optimization of the system dimensioning is finally described. Particularly, it is shown that vehicles can be equivalently aggregated into flows to express all the constraints and the criteria of our optimization problem. The chapter terminates with Section 3.4 presenting a polynomial sub-case of the problem where all demands have to be satisfied. A conclusion summarizing the obtained results is finally provided.

Related work

The recent emergence of vehicle-sharing systems have greatly stimulated both industrial and academic research. In the last chapter, various topics from demand modelling to system management have been discussed. This section is dedicated to the actual knowledge about one-way carsharing system design and performance. More precisely, we focus on methodologies extracting design tendencies or structural configurations that may contribute helping carsharing companies to plan their service.

Popular approaches facing those problems are based on simulation, micro models or linear programming. [Li, 2011] presented a discrete-event simulation model to study the performance of one-way carsharing systems. The model simulates many system operations, including vehicle's pick-up and drop-off, an online reservation system and minimal vehicle relocations. The number of stations and vehicles is fixed during the simulation. The global performance of the system is evaluated through various indicators such as the average vehicle utilization, reservation acceptance rate, full parking time and operator profit. Results demonstrate that system concentricity (density of stations) and the number of parking places are important parameters improving the reservation acceptance rate and vehicle utilisation.

More recently, an agent-based simulation model developed by [Barrios, 2012] aimed to measure and predict the level of service offered to users. In this study, the carsharing scheme was assumed to be a free-floating and designed to be compared with existing services in Austin, Texas and San Diego, California. Using agent-based modelling, the author intended to observe emergent phenomena, integrating stochastic demand and users interactions. The level of accessibility (percentage of an area that is within walking distance of an available carsharing vehicle) was proposed as a metric of the system efficiency. Simulation results show that the model reasonably estimates the level of service in one-way service context. The author concluded that the model could help decision makers design the system.

Other studies, focussed on optimal policies to relocate vehicles through the system. As pointed out before, those operations are necessary to ensure that vehicles are located where they are needed. It allows the system to run at a level of efficiency unreachable otherwise [Mitchell, 2010, Nair and Miller-Hooks, 2011, Febbraro et al., 2012].

Although not exactly aligned with the purpose of dimensioning a carsharing service, several approaches present interesting models holding suitable system dynamics. Using mathematical programming, some studies tackle the problem from an operator-based perspective [START_REF] Kek | Relocation simulation model for multiple-station shared-use vehicle systems[END_REF], Kek et al., 2009] whereas others used a station-location approach [Correia andAntunes, 2012, Jorge et al., 2012]. Rather suited for the system dynamics studies, they all rely on a mathematical representation of the whole system based on time expanded graphs [Ahuja et al., 1993]. The purpose was to identify measures to maximize resources and enhance service levels. Results show that the operator profit can be improve when the system runs with suitable vehicle relocation policies.

Mathematical model

Formal problem statements

Inputs: As seen previously, the [sdp] is time-dependant. A carsharing system evolves over time. Vehicles are moving among stations, taking more or less time to join a destination according to their departure time. As a consequence, a formal description of the time component is first needed. In this work, we decided to consider a discrete set of time-steps, numbered from 1 to T ∈ N and denoted by T . The time period between consecutive steps, noted ∆t, is set constant and expressed in minutes. For relevance issues, and especially for experiment purposes, T has to cover a representative period of time, as an average weekday or an average week for instance. For the record, note that a 24 hours period segmented into 10 minutes time-steps represents a total of 144 steps (i.e. T = 144). Some discussions about the assessment of the time component are given in the next chapter.

Carsharing stations are gathered in a set called S, and also numbered with natural integers from 1 to S > 1. Each station comes with a natural integer value Z(i) > 0, the maximum capacity (in terms of number of parking places) of station i ∈ S. The set of stations' capacities is denoted by Z.

Then, D denotes a set of D carsharing demands. A demand D(i,j,t) contains the number of passengers wishing to join station j ∈ S from station i ∈ S, when the departure time at i is t ∈ T . Note here that there is no condition on the station themselves, thus allowing the potential travel to be a "round trip" or a "one-way" travel. In this latter case, i is simply equal to j.

Similarly, δ(i,j,t) represents the time spent in travel of a car-user picking up a vehicle at station i ∈ S to reach station j ∈ S, when departure time from i is t ∈ T . Usually, travel times are expressed in minutes, but for the sake of clarity, this value will be converted in number of time-steps as previously defined in T . More generally, any travel time tt min expressed in minutes can be converted using Equation 3.1.

δ(i,j,t) = tt min ∆t (3.1)
For instance, if ∆t = 10, then a 43 minutes travel will corresponds to a 5 time-steps travel. We suppose that for any triple (i,j,t) ∈ S 2 × T , δ(i,j,t) < T. This assumption comes from the fact that the highest distance from different stations is quite low (usually less than 150 or 200 kilometres) and that the time-steps are covering at least a day.

Finally, the following list summarizes the problem's inputs:

• T : the set of T time-steps;

• S: the set of S carsharing stations;

• Z: the stations' maximum capacities;

• D: the set of carsharing demands among stations and over time;

• R: the set of time-steps when the system can operates vehicle relocation operations;

• H: the set of travel times expressed in time-steps.

Outputs: A carsharing system dimensioning consists in quantifying the system components in order to get a realistic and runnable system. To be more specific, dimensioning a carsharing system expects the following output values:

• a set of satisfied demands;

• a set of vehicle relocation to be operate during the period;

• the number of parking places in each station;

• the total number of vehicles.

Statement: A formal definition of our main optimization problem, referred as the System Dimensioning Problem with vehicle relocation operations, noted [sdp] is stated in the following.

[sdp]:

Inputs: A set of S stations with their maximum capacity Z(i) ∈ Z, i ∈ S, time periods set T = {1, • • • , T}, travel times δ(i,j,t) ∈ H for each triplet (i,j,t) ∈ S 2 × T , a set D of D time-dependant demands, fixed number of vehicles V and relocation operations R.

Question: What is the maximum number of demands d ≤ D that can be captured by a vehicle routing of at most V vehicles and R vehicle relocation operations during the considered period T ?

We refer later on at SDP(T , S, Z, D, R, H, R, V ) to indicate a particular SDP instance. We will show that [sdp] belongs to N P by modelling feasible solutions as a non classical flow problem.

Time Expanded Graphs

In the Station Dimensioning Problem, time is an essential ingredient. To deal with discrete-time dynamic networks, [Ahuja et al., 1993] suggested the use of time-space networks, also referred as Time Expanded Graphs (TEGs). They are static networks constructed by expanding the original (dynamic) networks in the time dimension. The strength of such models arises from the fact that we benefit from results of static flow models while account properly for the evolution of the underlying system over time. The basic idea is to consider a separate copy of every node at every discrete time-step. Arcs that link these static "snapshots" of the network describe temporal linkage in the system.

The resulted TEG is a valued directed graph describing the original system over time. According to conventional notations, a TEG will be denoted by G = (X , A, u) where X , A and u are respectively the set of nodes, the set of arcs and the arcs' capacities. Next sections aim to describe the graph components, the methodology to build them and their interpretation in the carsharing context.

Set of nodes

Nodes in the TEG stand for carsharing stations' states over time. They are couples (i,t) where i ∈ S and t ∈ T depict the state of each station i at time t.

As shown in Figure 3.1, the S stations are represented vertically and duplicated over time following the horizontal time axis. We denoted by X the set of nodes in the TEG formally defined as:

X = S × T = {x = (i,t) | i ∈ S and t ∈ T } (3.2) The total number of node in G is |X | = S • T.
Let η and θ the functions which reciprocally return the station number and the time-step associated with every element of X :

η : X → S with x = (i,t) → η(x) = i (3.3) θ : X → T with x = (i,t) → θ(x) = t (3.4) time | 1 | 2 | t | T • • • • • • 1(1)
. . . 1)

S(

1(2) 1(t) 1(T) S(2) S(t) S(T)
In this figure, T time-steps are dispatched horizontally whereas the S stations are distributed vertically.

The graph accounts for a total of S • T nodes and each one of them represents a station's state at a given timestep.

Figure 3.1 -The TEG's node configuration.

Set of arcs

The set of arcs is denoted by A. An arc is a pair of nodes picked in X . It depicted a vehicle movement through time. It is formally defined as the following equation.

A ⊆ {a = (x,y) | x ∈ X and y ∈ X } (3.5)
In this study, we consider three temporal operations among stations: park a vehicle in a station, satisfy a carsharing demand and relocate a vehicle. Those operations are modelled with arcs in G and partitioned into tree distinct sets denoted by A 1 , A 2 and A 3 .

Stay Parked: A 1 is the set of arcs representing the possibility for the vehicles to stay parked at a station between two consecutive time-steps. Formally, every arc a = (x,y) ∈ A 1 checks the property P 1 defined as: Fulfil a demand: Arcs in A 2 are associated with a vehicle demand. Each demand D(i,j,t) > 0 given as input is modelled with an arc linking the station i at time-step t, i.e. node x = (i,t) ∈ G, to station j. The arrival time-step at station j is calculated using the known travel time δ(i,j,t) given as input and its value is t + δ(i,j,t) mod T. Formally, every arc a = (x,y) belongs to A 2 if it fits the following property P 2 :

P 1 (a) : η(x) = η(y) (3.6) θ(y) = θ(x) + 1 mod T (3.
time | 1 | 2 | t | T • • • • • • 1(1) 1(2) 1(t) 1(T) • • • • • • Figure 3.2 -Stock arcs in the TEG for a single station. time | 1 | 2 | t | T • • • • • • 1(1) 1(2) 1(t) 1(T) 2(1) 2(2) 2(t) 2(T)
P 2 (a) : D(η(x), η(y), θ(x)) > 0 (3.8) θ(x) + δ(η(x), η(y), θ(x)) = θ(y) mod T (3.9)
Figure 3.3 illustrates the construction of the demand arcs. In this basic example, two demands, D 1 = D(1,2,1) and D 2 = D(2,1,T) are represented respectively by arc a 1 = (x 1 , y 1 ) and arc a 2 = (x 2 , y 2 ). Using travel times δ 1 = δ(1,2,1) = 1 and δ 2 = δ(2,1,T) = 2 as inputs, the couple of arcs is build as follows:

x 1 = (1, 1)
y 1 = (2, 1 + δ 1 mod T = 2) = (2, 2) x 2 = (2, T) y 2 = (1, T + δ 2 mod T = 2) = (1, 2)
Relocate a vehicle between stations: A 3 represents all the possible vehicle relocation operations over time. Let define R ⊆ T , the subset of time-steps when the system could be balanced through vehicle relocation operations. Then it comes that any relocation arc can be model as arcs starting from every station at every time-steps in R.

Similarly to demand arcs, the arrival nodes are calculated taking into account travel times between stations given as input. Formally, any triple (i,j,t) ∈ S 2 × R with i = j is modelled as a vehicle relocation arc connecting node x = (i,t) to node y = (j, t + δ(i,j,t) mod T). Property P 3 ensures that any arc a = (x, y) belongs to

A 3 . time | 1 | 2 | t | T • • • • • • 1(1)
. . . 1)

S(

1(2) 1(t) 1(T) S(2) S(t) S(T) Figure 3.4 -Demand arcs in the TEG P 3 (a) : η(x) = η(y) (3.10) θ(x) + δ(η(x), η(y), θ(x)) = θ(y) mod T (3.11)
Figure 3.4 depicts the set of relocation arcs in a complete TEG where R = T . At every time-step, every station is connected to the other. In this model, a vehicle relocation operation can be performed at any time between every pair of stations. The total number of vehicle relocation arcs can be calculated using equation (3.12).

|A 3 | = |R| • S • (S -1) (3.12)
Finally, sets A 1 , A 2 , A 3 are then formally defined as:

A k = {x ∈ X | P k (x)}, ∀k ∈ {1, 2, 3}. (3.13)
Together, they form a mathematical partition of the set of arcs. Assuming that D = ∅, the three subsets hold the following relations:

1. A = 3 k=1 A k , 2. A i ∩ A j = ∅, ∀i,j ∈ {1,2,3}, i = j.
The total number of arcs is given by:

|A| = 3 k=1 |A k | = S • T + D + |R| • S • (S -1) (3.14)
where D is the number of requested demands. When R = T , and since D S 2 , then it comes that |A| = Θ(S 2 • T). In this case, we observe that |A 3 | |A 1 ∪ A 2 | and that the number of arcs is then proportional to A 3 .

| 2 | t | T • • • • • • 1(1)
. . . 1)

S(

1(2) 1(t) 1(T) S(2) S(t) S(T) (8) (8) (8) (8) (4) (4) (4) (4) (1) (2)
Legend:

i(t) Station i at time t

Stock arc

Demand arc

Relocation arc

Arcs Capacities

Associated with each arc a = (x,y) ∈ A, is given a capacity function u : A → N corresponding to a maximum number of vehicles allowed on a. It is defined as follows for any arc a ∈ A:

u(a) =      Z(η(x)) if a ∈ A 1 , D(η(x), η(y),θ(x)) if a ∈ A 2 , +∞ if a ∈ A 3 .
For any arc a = (x,y) ∈ A 1 , the maximum number of cars is the capacity of the station η(x) = η(y). It corresponds to the demand for any arc a ∈ A 2 , and it is not bounded for relocation arcs a ∈ A 3 .

Additional notations

We denote by Γ -(x) and Γ + (x) respectively the set of immediate predecessors and successors of a node x ∈ X .

Γ -(x) = {y ∈ X | (y,x) ∈ A} (3.15) Γ + (x) = {y ∈ X | (x,y) ∈ A} (3.16)
For any couple of time instants ∀(t, t ) ∈ T 2 , the number of time-steps between those two instants is defined through the following function:

ϑ : T 2 → N (t, t ) → ϑ(t, t ) with ϑ(t, t ) = t -t if t ≤ t , T + t -t otherwise.
For each arc a = (x,y) ∈ A, let us define the boolean value a as:

a = 0 if θ(x) ≤ θ(y), 1 otherwise.
The time required for a movement from x to y is then given by the function

: A → N (3.17) a = (x, y) → (a) = θ(y) -θ(x) + a • T (3.18) By extension, if µ = (a 1 , • • • , a p ) ∈ A p is a path in the TEG from x to y, the value (µ) = p i=1 (a i )
is the total time required for a vehicle going from x to y following µ. For any time value t ∈ T , let us define the set C t (µ) as the arcs a = (x,y) from µ starting at time t or earlier but ending after t. Formally,

C t (µ) = {a = (x,y) ∈ µ | ϑ(θ(x),t) < (a)}.
(3.19)

Flows and decision variables

Consider vehicles directly in the model does not seem to be a good option. Although it would be possible to create boolean variables for each node of the TEG to track and follow the movement of vehicles over the day, their number may be too large. Thus, we first introduce flow variables over arcs in the Time Extended graph. It is shown then that feasible vehicle tours can be extracted easily from any feasible flow.

The aim of our study is to compute the planning of each vehicles during the period. At any time, each vehicle is either parked in a station or in transit between two stations. Its position over the period can be modelled as a vehicle tour i.e. a circuit denoted by c = (a 1 , • • • , a p ) in the TEG. The size of any feasible solution may be highly reduced if we only consider the number of vehicles passing through each arc. Each vehicle in the system is thus associated to a vehicle tour (even if the vehicle is not used, staying in a station).

The duration of any path or circuit in a TEG may be easily evaluated. Indeed, for any couple of time instants (t, t ) ∈ H 2 , let the function ϑ : H 2 → N that computes the number of time-steps between those two instants, formally defined as follow:

ϑ(t, t ) = t -t if t ≤ t , T + t -t otherwise.
For each arc a = (x,y) ∈ A, let us define and set the boolean value a to true if θ(x) > θ(y). The effective time required for a move from x to y is then equal to

(a) = θ(y) -θ(x) + a • T. By extension, if µ = (a 1 , • • • , a p ) ∈ A p
is a path of the TEG from x to y, the value (µ) = p i=1 (a i ) is the total time required for a vehicle going from x to y following µ. Next lemma evaluates the total time of any circuit c.

Lemma 1 The total time of any circuit

c = (a 1 , • • • , a p ) ∈ A p is (c) = T × p i=1 a i . Proof. Let x i , i ∈ {1, • • • , p + 1} be the sequence of elements from X such that, x p+1 = x 1 and ∀i ∈ {1, • • • , p}, a i = (x i , x i+1 ). The total time of c is then (c) = p i=1 (a i ) = p i=1 (θ(x i+1 ) -θ(x i ) + a i • T) = T × p i=1 a i , the result.
The aim of our study is therefore to compute the planning of each vehicles during the period T . At any time, each of them is either parked in a station or in transit between two stations. Its position over the period can be modelled as a vehicle tour i.e. a circuit c = (a 1 , • • • , a p ) in the TEG. We show in the following that a feasible solution can be described by only considering the number of vehicles modelled as a flow passing through each arc.

For each arc a = (x,y) ∈ A, we call ϕ(a) the flow of vehicles transiting through the arc a. It can be interpreted as the number of vehicle staying in station η(x) between two consecutive time-steps if a ∈ A 1 , or the number of vehicle moving from station η(x) at time θ(x) to station η(y) otherwise. Since the total number of vehicles transiting by any node x ∈ X is constant, the flow verifies the following flow conservation equation:

y∈Γ -(x) ϕ((y,x)) = y∈Γ + (x) ϕ((x,y)),
(3.20)

A flow ϕ : A → N is then said to be feasible if ∀a ∈ A, its value do not exceeds its capacity, i.e. ϕ(a) ≤ u(a) and ∀x ∈ X , the flow conservation equation (3.20) is true. A feasible flow may be easily obtained from any feasible set of vehicle tours.

We prove in the following that the reverse is also true, with the consequence that any feasible solution of our problem can be described using a flow. Next lemma computes the exact number of vehicles associated to a constant unitary flow over a circuit c.

Lemma 2 Let c be a circuit and ϕ c a feasible flow such that:

ϕ c (a) = 1 if a belongs to c, 0 otherwise.
The minimum number of vehicles to insure ϕ c is (c) T .

Proof. For any time value t ∈ T , let us define the set C t (c) as the arcs a = (x,y) from c starting at time t or earlier but ending after t. Since ϑ(θ(x), t) equals the number of time steps from θ(x) to t, we get

C t (c) = {a = (x,y) ∈ c | ϑ(θ(x), t) < (a)}.
Now, since c is a circuit, the value |C t (c)| is a constant ∀t ∈ T and corresponds to the total number of vehicles needed to insure a unitary flow over c. Let us prove that |C T (c)| = a∈c a . For that purpose, setting Let suppose now that n(ϕ) > 0, thus there exists at least one arc a = (x, y) ∈ A with ϕ(a) > 0. Set µ 0 = (x, y) and let consider the sequence of paths µ i built as follows:

B(c) = {a = (x,y) ∈ c | a = 1}, we show that B(c) = C T (c). • B(c) ⊆ C T (c): if a = (x,y) ∈ B(c), then as θ(x) ≤ T, ϑ(θ(x), T) = T -θ(x). Now, since a = 1 and θ(y) ≥ 1, (a) = θ(y) -θ(x) + T ≥ 1 -θ(x) + T > ϑ(θ(x),T) and a ∈ C T (c). • C T (c) ⊆ B(c): let consider now an arc a = (x,y) ∈ C T (c). Since ϑ(θ(x), T) = T -θ(x) < (a) we get that θ(y) -θ(x) + a • T > T -θ(x)
1. Stop the sequence as soon as µ i contains a circuit c, 2. Otherwise, let ã = (x,ỹ) the last arc of µ i . Since ϕ(ã) > 0, the flow conservation equation (3.20) insures that there exists an arc a starting at ỹ with ϕ(a) > 0. We then set

µ i+1 = µ i • a.
As G has a finite number of nodes, the algorithm stops and a non empty circuit c is returned.

The flow φ defined as

φ(a) = ϕ(a) -1 if a ∈ c, ϕ(a) otherwise.
is feasible with n( φ) < n(ϕ), thus the theorem.

Note that the number of flow variables is a polynomial function on the size of the problem. This is not true anymore for vehicle tours, for which the number can be exponential. The consequence is that the determination of a flow is in N P, which is not the case for the determination of vehicle tours. Proof. Let S be a set of circuits obtained from the decomposition of ϕ following Theorem 1 and let V be the minimum number of cars associated with ϕ. By Lemmas 1 and 2, the total number of car of any circuit c ∈ S is Lastly, the total number of vehicles required at time T to reach ϕ is exactly a∈A ϕ(a) • a , the theorem.

Solution and objectives

A feasible solution of our problem consists on a set of vehicle tours, each of them modelling the situation of a car at each time step.

A feasible solution of our optimization problem is given by a set of vehicles, each of them associated with its position in the system at any time-step during the period. The first objective is to maximize the total number of satisfied demands, i.e. for which a vehicle is allocated. Besides, two other objectives must be taken into account: each vehicle in the system is associated to a fixed cost, so that the total number of vehicles must be minimized. In the same way, vehicle relocations are fundamental for increasing the number of satisfied demands with a fixed number of vehicles. However, they cost an extra charge for the operator, and thus their number should also be limited. In the following, the total number of vehicles and relocations are referred respectively by V and R. The three criteria (the demand, the number of vehicles and the number of relocation operations) can be polynomially computed from any feasible solution.

Mathematical program

The modelling of our optimization problem follows. R and V are fixed integer bounds for respectively the total number of relocation operations and vehicles. Equation

s.t.                              a∈A 3 ϕ(a) ≤ R (3.22) a∈A ϕ(a) • a ≤ V (3.23) ϕ(a) ≤ u(a) ∀a ∈ A (3.24) y∈Γ -(x) ϕ((y,x)) = y∈Γ + (x) ϕ((x,y)) ∀x ∈ X (3.25) ϕ(a) ∈ N ∀a ∈ A (3.26)

A polynomial sub-case

Although the [sdp] formulation sounds very close to the circulation problem definition, it presents some particularities that prevent us from its complexity evaluation. As far as we know, the fact that the optimization is focused on a sub-set of arcs (carsharing demand arcs) and tries to find a feasible flow in the graph is not present in the literature neither as a standard problem nor related to some known one. As a consequence, and despite our attempts, we do not succeeded in position this problem into a complexity class. Probably, reducing or transforming it into a classic flow problem may answer this question.

Nevertheless, we obtained a complexity result for a specific instance of the problem. This section aims to prove that the determination of a flow satisfying all the carsharing demands without the constraints on the total number of relocation operations or vehicles is a polynomial problem. Its formal definition, designated by [sdp-all-demands], follows.

[sdp-all-demands]:

Inputs : A Time Expanded Graph G = (X , A, u).
Question : Is there a feasible flow ϕ in G such that all the demands are fulfilled, i.e. ∀a ∈ A 2 , ϕ(a) = u(a)?

Let I be an instance of all-demands. We associate an instance of a max-flow problem f (I) which network G = ( X , A, w) is defined as follows:

1. Vertices are X = X ∪ {s , t } ∪ {s a , t a , a ∈ A 2 }. s and t are respectively the source and the sink of G, while s a and t a are two additional vertices associated to any demand arc a ∈ A 2 . Proof. Let suppose that ϕ is a feasible flow of G that fulfils all the demands, i.e. for any arc a ∈ A 2 , ϕ(a) = u(a). A flow ϕ of G may be built as follows:

Arc set is

A = A 1 ∪ A 3 ∪ {(x,
1. ∀a ∈ A 1 ∪ A 3 , ϕ(a) = ϕ(a); 2. For any arc a = (x,y) ∈ A 2 , ϕ((x,t a )) = ϕ((t a ,t )) = ϕ((s , s a )) = ϕ((s a ,y)) = u(a).
We prove that ϕ is a feasible flow of G of value a∈A 2 u(a). Indeed, let consider a node x ∈ X .

1. Let suppose first that x ∈ X . Then any demand arc a = (y,x) ∈ A 2 (resp. a = (x,y) ∈ A 2 ) of flow ϕ(a) is associated in A to an arc e = (s a , x) (resp. e = (x, t a )) with ϕ(e) = ϕ(a). Thus,

a∈Γ -( G,x) ϕ(a) = a∈Γ -(G,x) ϕ(a) = a∈Γ + (G,x) ϕ(a) = a∈Γ + ( G,x)
ϕ(a).

2. For any arc a = (z,y) ∈ A 2 , the two vertices t a and s a are such that

e∈Γ -( G,ta) ϕ(e) = ϕ((x, t a )) = ϕ((t a , t )) = e∈Γ + ( G,ta) ϕ(e)
and

e∈Γ -( G,sa) ϕ(e) = ϕ((s ,s a )) = ϕ((s a , y)) = e∈Γ + ( G,sa)
ϕ(e).

3. Lastly,

e∈Γ -( G,t ) ϕ(e) = a∈A 2 u(a) and e∈Γ + ( G,s ) ϕ(e) = a∈A 2 u(a).
The consequence is that ϕ is a feasible flow of G of value a∈A 2 u(a).

Conversely, any feasible flow of G of value a∈A 2 u(a) verifies that, for any arc a = (x,y) ∈ A 2 , ϕ((x,t a )) = ϕ((t a ,t )) = ϕ((s , s a )) = ϕ((s a ,y)) = u(a). A feasible flow for G can be easily obtained by setting:

1. ∀a ∈ A 1 ∪ A 3 , ϕ(a) = ϕ(a);
2. For any arc a = (x,y) ∈ A 2 , ϕ(a) = u(a), the theorem.

According to [Ahuja et al., 1993], the existence of a maximum-flow of a fixed value is a polynomial problem. The following corollary is thus a consequence of Theorem 3:

Corollary 1 [sdp-all-demands] is polynomial.

Conclusion

In this chapter, we presented a mathematical modelling approach to represent the dynamics of a one-way carsharing system over time and deal with the determination of an optimal system configuration when stations are fixed. The problem includes strategical vehicle relocation operations to cope with the system imbalance and is studied through the prism and recommendations of existing literature. Time expanded graphs (TEGs) are often used to model systems assuming a strong time dependency. The idea consists in construing static networks enlarged through the time dimension. Using those graphs, we proposed an integer linear program [sdp] based on a specific TEG where nodes and arcs account respectively for carsharing stations over time and vehicle operations. The ILP considers integer flow variables which can be interpreted as vehicle flows (vehicles routes or itineraries) transiting through the system over time. The objective is to found a feasible flow in the graph satisfying the maximum number of demands, modelled as a specific subset of arcs. We proved that any feasible solution can be expressed and interpreted as a set of vehicle itineraries, thereby determining the optimal dimension of the whole system.

Although the problem complexity has not been determined, a polynomial sub-case where all the demands have to be satisfied has been exhibited. However, we prove that the determination of a solution as a global flow in the graph is in N P. The next chapter examines solver capabilities and computation improvements to tackle interesting size of the problem.

Abstract

In the last chapter, we have proved that the System Dimensioning Problem [sdp] can be approached using an integer linear program. Although a polynomial sub case of the [sdp] has been highlighted, the global problem complexity is still unknown. It rises the question of an acceptable computing time and resources according to our industry context. Can the program deal with real instances, or at least realistic case studies? We propose in this chapter to evaluate the problem from a computational perspective.

Introduction

The lack of available real carsharing demand data prevents us from a meaningful confrontation between an actual operating carsharing system and an optimal system dimensioning configuration computed from the linear program solution.

We presented in Chapter 2 a random data generator that has been developed especially to cope with that lack. It defines a specific time environment, generates a random set of stations with settable maximum capacities and a realistic set of carsharing demands from origins to destinations during a typical weekday.

This chapter focuses on computational experiments based on the random data generator. It explores several computing aspects of the linear program, from the maximum problem size the program can solve to observed solver computation times. Generator parameter values will be specified at the beginning of each experiment. For more details on the random data generator, see Section 2.2 page 21. This chapter is organize as follow. Section 4.2 gives some discussion about computation times and solutions analysis of small instances, based on generated data. A 3-dimensional Pareto frontier is especially presented. Section 4.3 is dedicated to scalability experimentations, particularly the solver's performance when the problem increases in size.

First experiments and scalability

Experimental context

In this first section, all experimental results were made using an Intel(R) Core(TM) i3-3227U CPU running at 1.9GHz. The linear programs were expressed using the AMPL format [amp, ] and numerical results were obtained using the open-source solver GLPK v4.52 [glp, ].

The choice of GLPK instead of a commercial solver is mainly motivated by our industrial context. The will to transfer easily our methodology and tools in an industrial environment initially led us to use an open-source solver. Although the solutions we obtained with GLPK were quite good, some hard limitations related to the program build time lead us to use later on CPLEX, a more flexible and powerfull solver.

3-pareto fontier

First experiment aims at assessing solver computation times of "small" SDP instances. Considering S = 10 stations, T = 144 time-steps and D = 500 demands, we collected program building time and solver computation times of 30 random instances. We assumed here that the system could be balanced using vehicle relocation operations at any time-step in T (i.e. R = T ).

For those fixed SDP inputs, the corresponding TEG has: For each random instance, the solver computation determines the maximum number of carsharing demands the system is able to satisfy according to different upper bound of relocation operations (R) and the number of vehicles (C). After having tested some empirical values of R and C, we observed that setting both of them to {0, 10, • • • , 80} produce the most representative results. Based on each single instance, a total of 9 × 9 = 81 linear programs are then solved (9 values for both R and C). Table 4.1 presents the average computation time µ and the standard deviation σ for both integer linear program ILP and its relaxation to linear program LP. The minimal and maximal computation time values are also specified. Note that the linear program in this experiment contains |A| = 14,900 variables, and 1442 constraints.

• |X | = S • T = 10 • 144 = 1,
The first observation is that computation times remain quite low, in the order of a halfsecond for LPs and two seconds for ILPs. The major part is taken by the building of the mathematical program which takes 34 seconds (mostly by the conservation law's constraints) regardless of which model is built. Maintaining the same problem size, further experiments with CPLEX reduce this building time to a half-second.

Secondly, when the solver runs the LP model, almost 8 problems under 81, exactly 7,66 on average over the 30 generated instances, admit a non-integer value of the objective function. This result represents almost 10% of all instances. However, every time we get a non-integer optimal value LP * , the integer one ILP * has always the same integer part. In other words, we observed in all cases that ILP * = LP * .

Plotting the maximal number of satisfied demands found by the solver regarding different couple values (R, C) ∈ {0, 10, . . . , 80} 2 , allow us to confirm that the number of vehicle relocation operations is in opposition with the number of vehicles. Figure 4.1 shows a 3-dimensional Pareto frontier made of 81 points for a particular problem instance. The coloured layers correspond to different demand satisfaction levels. The yellow level for instance denotes a satisfaction level between 60% and 80%, whereas the green level stands for the maximal satisfaction level (100%).

In this specific case, the tradeoff between the two criteria is well highlighted. The more the number of vehicle relocation operations, the less the number of vehicle needed to run the system. For instance, 70 vehicle relocation operations with 50 vehicles allow to capture all 500 demands. Maintaining the same service quality (satisfying all the demands in this case) while decreasing the number of vehicle relocation operations imply increased at the same time the number of vehicles. Thus, 70 vehicles are needed if the system is balanced with at most 70 vehicles relocation operations. This confirms that the two criteria are in opposition and that there exists a tradeoff area between them.

Scalability study

Solving small instances of the system dimensioning problem with a linear programming approach is not a problem in itself.

Even with an open-source solver like GLPK, the obtained computation times remain in a range of a few seconds and are therefore reasonable. However, the high time needed to build the programs, due to the graph density, is certainly a challenge we have to handle.

As observed previously, its most important part comes from the formal expression of the conservation law's constraints, probably mismanaged by the solver. This second experimentation focuses on the problem scalability when the problem is growing in size. More especially, we investigate the overall program building time evolution when the number of stations and the number of time-steps increase.

In the first place, we studied systems where the number of stations and the number of timesteps respectively belong to {10, 20, . . . , 50} and {72, 144, 288}, which corresponds to time-step intervals of 20, 10 and 5 minutes. Each measure is obtained from a single instance since the time needed to build the model only depends on the size of the time extended graph. For the record, Table 4.3 presents graph densities for the different problem's sizes. First numerical results, obtained with GLPK, are presented in Table 4.2 and plotted in Figure 4.2b.

We observed that the generation time grows linearly following the number of arcs in the time extended graph. Note that for the biggest instance (S = 50 stations and T = 288 timesteps) GLPK founds a relaxed optimal solution within 1 20 minute and an integer optimal able until then within a few seconds. Now, the problem becomes the graph density, occupying a large amount of memory. For the biggest instance (S = 50, T = 288), vehicle relocation arcs represent 98% of the total number of arcs. Therefore, we suggest to increase the scalability of the method by considering for example only short distance relocation arcs or defining them at fixed time-steps.

Working on relocation operations

Previous results aimed to evaluate the scalability of the optimization model described in the last chapter. Computation times were obtained on small realistic instances with 10 stations and 144 time steps using an open source solver (GLPK). We observed that they were negligible compared to model building time and decided to study the building time behaviour when the problem grows. Using CPLEX, we have seen that the problem began to move from the program building time to the unaffordable graph density, especially the number of arcs. We suggested to use better relocation strategies in order to reduce the predominance of vehicle relocation arcs and therefore the TEG density.

The aim of this section is to study the computation times for solving exactly or approximately the optimization problem for real case instances. More precisely, following previous experiments, we show that the density of relocation arcs drastically decreases computation times without impacting the quality of the solution.

Working on relocation operations

Strategy

The experimental conditions are first presented, followed by the description of the strategies for reducing the graph density. The section ends with the impacts on solver computation time and optimal distances to the baseline situation.

Experimental conditions

Computational results, including the random data generation, were made using an Intel(R) Core(TM) i5-3337U CPU @1.80GHz. Mathematical programs were solved using the Java API of IBM ILOG CPLEX 12.5.1.

The total number of stations is fixed to 50, which corresponds to a reasonnable size for a real-life problem. A total of 500 carsharing demands (requests) are randomly generated over a typical 24 hours week day period segmented in T = 144 time-steps of 10 minutes.

Impacts on the TEG density

Baseline situation (BS is short) corresponds to instances for which relocations are generated at each times steps, i.e. every 10 minutes. As pointed before, our idea is to reduce the number of relocation arcs, which corresponds in this case to almost 98% of the total number of arcs. The goal is to accelerate the resolution of our optimization problem.

Table 4.5 presents some numerical parameters of any generated TEG. We studied four strategies (S1 to S4). Each one of them generates vehicle relocation operations respectively every 30 minutes, 1, 2 and 4 hours. The number of nodes is always equal to |X | = S × T = 50×144 = 7200, while the total number of arcs |A| decreases following the frequency of relocation operations (RF) during a day. The respective ratios of remaining arcs compared to BS (% BS) and the arcs removed (% elim) are also presented, followed by the exact number of relocation arcs (RA) and their proportion in the graph.

Reducing the number of relocation arcs decrease drastically the graph density from -65% for (S1) to almost -94% for (S4). The resulting number of arcs for the strategy (S4) represents for instance 6,21% of the BS one. Also observe that relocation arcs remain predominant, even for strategy (S4) for which they represent above 65% of the total number of arcs.

Solver computation times

Next experiment aims to evaluate the impact of the vehicle relocation arcs reduction on computation time as well as solution quality of our optimization problem. A total of 30 instances were randomly generated. The five strategies are evaluated for each of them by solving 81 linear programs corresponding to the combinational values of R and C, set as before in the range {0,10, • • • ,80}.

Table 4.6 summarizes the results. The first part of the table concerns the linear program relaxation values (LP) with real variables, whereas the second part exposes the results obtained solving exactly the mathematical program with integer flows (ILP). Columns "µ t ", "min" and "max" report respectively the average, the minimum and the maximum computation times in milliseconds while "σ t " is the standard deviation. Finally, columns "µ d " and "σ d " indicate the average distance to the solution obtained for (BS) and the corresponding standard deviation.

First note that computation times remain reasonable, even for the exact method with baseline strategy (always less than 139 seconds). However, the density reduction allows to decrease dramatically computation times. This reduction is particularly important for the exact method ILP where strategy (S1) allow to solve the program in less than 10 seconds in average. This gain is already more than 80% compared to the average computing time of the baseline situation. Also note that computation time values are almost equal for both exact or approximate solutions using (S4) strategy.

The surprise is that the optimal number of fulfilled demands are almost not impacted by the reduction of relocation arcs. The optimal values following the different strategies remain very close to the baseline one for both LP or ILP resolutions, with a gap varying from 0,4% in (S1) to 5% in (S4).

Conclusion

This chapter evaluates the [sdp] model from a computational perspective. First experiments based on random generated data studied the resolution of small instances with an open-source solver (GLPK). Computation times remained acceptable, less than a second on average, for instances with 10 stations and 10-minutes time-steps. We confirmed that the number of vehicles and the number of relocation operations were in opposition and we represented a 3-pareto barrier surface where the trade-off is well highlighted. We also observed that the major part of the computation comes from the linear program building time and not from its computation.

A second study focussing on the model scalability investigated graph densities and LP building times evolution when the problem grows in size. We show that both are highly correlated and that better generation times could be obtained using an alternative solver (CPLEX). We observed that relocation arcs played a major role in the graph densities and we thus suggested that decreasing their number considering other relocation strategies should reduce the total number of variables. Indeed, investigating strategies where relocations are made at fixed time-steps allow to highly decrease graph densities from 65% to almost 94% with respect to the previous model. Computation times obtained with CPLEX was also better than before, especially for the exact method considering integer variables. Solutions' qualities were almost not impacted by this density reduction and a maximum gap of 5% was observed with respect to the value of the optimal solution. Next chapter will now investigated the optimal station positioning and inclusion of energy components.

Part II

The Station Location Problem and energy aspects

Chapter 5

The

Abstract

This chapter is dedicated to the study of the Station Location Problem (SLP). The problem, its challenges and related work are first described. We then present a mathematical program expanding the SDP model seen in Chapter 3 and including new features in the model like the number of jockeys. Next section is dedicated to the integration of energy components in the model. After having exhibited some modelling issues with respect to the previously developed model, a enhanced linear program is presented. The latter includes battery range and power supply constraints. The chapter terminates giving some discussions and improvements about the model. More particularly, an heuristic is detailed and a basic example illustrates its mechanics.

Introduction

We have presented in Chapter 3 a mathematical linear program resolving the system dimensioning problem. The optimization dealt with the optimal sizing of a carsharing system when stations were fixed. The optimal flow circulating in the Time Expanded Graph (TEG) can be interpreted as vehicle routes and some global dimensioning parameters can be deduced from it. Until then, the problem was to assess the number of vehicles as well as the number of vehicle relocations to run the carsharing system at its better efficiency, considered in this work as the capacity to fulfil the higher number of demands. In this chapter, we intend to enhance the initial problem with two new challenged aspects.

The first one deal with stations' locations. We propose to look at the problem from a different perspective by expanding its scope to the selection of a subset of stations contributing to the better system configuration. It involves changing the concept of station to possible station location which can be also understood as possible carsharing station site. Then, the problem can be expressed as follow: among all possible S station's locations, what is the number of P ≤ S sites constituting the most effective carsharing system? From this perspective, we intend to study the decisional factor that lead to select, or not select, a site. Our expectation is to deduce from exact solutions a global scheme that could inquire the site selection without having to run an exact optimization.

The second challenge aims at introduce energy components. In the previous model, vehicles were able to transport customers from station to another without limiting the total distance they travel during the day or even during a specific trip. Nowadays, combustion cars can travelled hundred of kilometres a day without the need to refill in gasoline. Moreover, no specific infrastructure is required to accommodate such vehicles. In that sense, we assumed that vehicles were considered as combustion vehicles in our previous work.

During the last few decades, numerous environmental issues have motivated the development of alternative means of transportation. In the world of private vehicles, electric cars has regained a high interest. Carsharing operators has begun to introduce electric vehicles (EVs) in their fleet and equip station parking slots with charging points. Some of them (e.g. Autolib) even propose a vehicle fleet exclusively composed of electric cars. In this chapter, our objective is to measure the operational impact of running a carsharing system with electric cars. For the most part, we wish to address the following questions:

1. Is the lower range of an EVs really limits the global system efficiency? 2. Is the size of the electric battery well suited for carsharing usage? 3. What is the impact of the charging points' power supply?

Including battery range constraints means control their charge level at all times so that a trip can only be performed if the vehicle have sufficient energy to do it. Until then, the flow model based on TEGs describes macroscopic flows of vehicles. Even if individual vehicle routes can be extracted, the numerous possible interpretations lead us to adapt and propose an alternative mathematical model able to consider electric cars and their appropriate functional equipment. This chapter is organized as follow. The first section specifies the addressed problem and its associated constraints. Its formulation as a Mixed Integer Linear Program (MILP) is especially presented. Related variables and constraints are listed and discussed. Two mathematical models are provided and a master-slave scheme with respect to the system dimensioning problem is exhibited.

Then, section 5.3 presents how to integrate energetic components into the current models. Considering electric vehicles instead of cars propelled by combustion engines bring interesting challenges that can not be tackled with the actual models. Thus, after having selected the components we wish include and described the required graph transformations, a new enhanced linear program is exposed.

The chapter terminates giving some modelling improvements to reduce the graph density and the total number of variables. To cope with solver capabilities, a greedy heuristic is proposed and illustrated on a basic example.

The Station Location Problem

A major difficulty for an operator wishing to set up a carsharing systems is without any doubt the stations' locations over the area he wishes to cover. Assuming that potential stations' sites could be identified, the remaining problem of select the ones leading to a system that operates efficiently and captures the higher number of requests stills remain a tricky question. From a formal point of view, the problem is purely combinatorial and admits S P possible solutions, where P denotes the number of stations to chose among the S number of potential stations' sites.

We have seen previously that the System Dimensioning Problem (SDP) assumed fixed stations in its statement. In a way, the SLP will consist in relaxing this assumption and appending some decisions over the stations' locations. Its formulation will thus sounds very close to the SDP and can be stated as follow.

Station Location Problem [SLP]:

Given a set of S carsharing stations' sites, it consists in select the subset of P ≤ S possible stations' sites allowing the system to run at its maximum potential, i.e. satisfying the higher number of demands.

Inputs are very similar to the SDP. The major difference concerns the carsharing stations which are not longer fixed but are now considered as potential stations' sites. We assumed that a maximum capacity (i.e. maximum number of parking lots) could still be known for each site. Input sets are summarized in the following:

• T : the set of T time-steps;

• S: the set of S potential stations' sites;

• Z: the sites' maximum capacities;

• D: the set of carsharing demands among stations' sites over time;

• H: the set of travel times expressed in time-steps.

Similarly to the SDP, sets D and H are defined as triplets (i,j,t) ∈ S 2 × T where i and j denotes respectively the site of departure and destination and t the time-step of departure. The problem also considers some system limitations bounds. The maximum number of selected stations' sites will be denoted by P . The number of vehicle relocations operations and the number of vehicles are bounded respectively as before to the non-zeros integer values R and V . Finally, we also included another feature dealing with the maximum number of jockeys

The main stated drawback with these MIP approaches concerns the limitations of computation times and solver capability due to the problem complexity. In most cases, as the size of the problem increases, the total number of variables become unsustainable and some simplifications are often necessary. As far as we know, integrating several decisions into the same problem in a real case study context is still a real challenge in this field.

Problem modelling

The SLP appears as a master problem of the SDP. It enhances decisions on the selection of potential carsharing sites under the scope of the system dimensioning problem. As a consequence, the model used previously for the SDP seems well suited and will need some adaptations to deal with the SLP. The following sections describe the added variables and constraints as well as the graph modifications.

Decision variables

In this problem, selecting stations constitutes the main decisions. Using the previous model, it can be achieved by adding a new group of binary variables for each potential carsharing site standing for its selection in the solution. Let thus b = (b i ) i∈{1,...,S} ∈ {0, 1} S be the decisional vector of this problem, define for all i ∈ S as:

b i = 1 if the station's site i is selected, 0 otherwise.
Every vector value represents a unique system configuration. It is easy to observed here that the SDP is actually a SLP sub-problem when b is fixed to a value in {0, 1} S . The total number of active stations, P , is the number of ones in b. It can be obtained using P = S i=1 b i . Every instance of the SDP with P stations correspond to an instance of the SLP where b contains P ones.

Constraints

First, note that limiting the number of selected sites can be easily expressed by bounding the number of ones in b to P . Formally, the constraint can be written as follow:

S i=1 b i ≤ P (5.1)
Secondly, the limitation of the number of opened sites implies to close some of them. When a carsharing site is closed, no vehicle can stop or either pass through it. In our model, vehicles are represented as flows and until then, no restriction on the possibility to enter the nodes have been considered. Using the new decisional vector b, it is now easy to limit the inner (resp. outer) flow entering (resp. leaving) each nodes (carsharing sites). These constraints are defined as follows:

ϕ(a) ≤ b η(x) • u(a) , ∀a = (x, y) ∈ A (5.2) ϕ(a) ≤ b η(y) • u(a) , ∀a = (x, y) ∈ A 2 ∪ A 3 (5.3)
Constraints (5.2) limit the outer flow in every arcs of the TEG to the arc's capacity if the site is selected and zero otherwise. Similarly, if the site is active, constraints (5.3) bound the inner flow to the arc's capacity but only for demand and vehicle relocation arcs. In order not to be redundant with the previous group of constraints, only arcs where the departure station is different from the arrival station have to be considered. The TEG stock arcs are thus not involved. In addition, note that this restriction could also be appropriate to some specific demand patterns like round-trip demands for instance.

As introduced before, jockeys are essential to operate vehicle relocation operations although they constitute an additional financial charge for the operator. They represent the operatorbased approach to balance vehicle stocks through the system and correspond to periodic relocation of vehicles among stations by staff members, also known as jockeys.

In this work, we intend to limit the total number of jockeys working for the carsharing operator. To do so, we simply bound the number of vehicle relocations made at the same time. Recall first that R denotes the subset of time-steps when vehicles start to be relocated (previously defined in chapter 3, page 39). For clarity reasons, let A t 3 be the set of relocation arcs starting their operation at time t ∈ R. Formally:

A t 3 = {a = (x, y) ∈ A 3 | θ(x) = t} (5.4)
Then, the constraint under the maximum number of simultaneous vehicle relocation operations, denoted by J, follows:

a∈A t 3 ϕ(a) ≤ J , ∀t ∈ R (5.5)

Outputs and Solution

A solution to the SLP consists of assigning a stations' configuration to the carsharing system, i.e. settle the value of b ∈ {0, 1} S satisfying constraint (5.1). For any fixed value of b, which means that the stations' locations are now fixed, we can solve the system dimensioning problem upgraded with the limitation under the number of jockeys (constraint group 5.5). Its resolution gives the maximum number of demands this station configuration is able to fulfil. Then, the optimal solution of the SLP is the vector b ∈ {0, 1} S maximizing the system efficiency for fixed values of the maximal number of vehicles, vehicle relocation operations and jockeys. The expected outputs of the problem resolution are listed below:

• a system configuration, i.e. a value b ∈ {0, 1} S ,
• the vehicles' routes through the system.

As for the system dimensioning problem, we can extract a lot of information from vehicles' routes. Those extended outputs can be deduced from any solution and are summarized in the following:

• the total number of stations, vehicles and jockeys;

• the set of satisfied demands;

• the set of vehicle relocation to be operate during the period;

• the number of parking places in each station.

Mathematical program

To cope with the station location problem, we opted for the linear programming approach. The mathematical model presented thereafter is based on a enhanced model of the system dimensioning problem described in Chapter 3. The later is actually a solid basis since the two problems are linked to each other. They both rely on the time expanded graph model presented before. This time, nodes represent possible location sites for carsharing stations and a fixed number of jockeys is involved as a constraint in vehicle relocation operations. As such, they are a limit factor affecting the global optimization. Basically, the mathematical program reused the transportation network expanded over time (TEG) and its associated constraints.

We present in this section two sights of seeing the model. The first one aims at highlighting the sub-problem dependence between the [sdp] and the [slp]. Then, the full version is detailed.

The master-slave scheme

As seen in chapter 3, an instance of the [sdp] could be written as SDP(T , S, Z, D, H, R, V ). This definition can be generalized to consider different station configurations. The idea is to use the vector b as a component selector of the station set S.

S(b) = {s

i ∈ S, i ∈ {1, . . . , S} | b i = 1}
(5.6) Now, we clearly have S(b) ⊆ S, for any value of b. According to Equation (5.6), each value of b generates a fixed subset of stations picked in S. The initial set corresponds to the situation where b = 1. As a master problem, the SLP can now be formally expressed.

[SLP]: max b∈{0,1} S SDP (T , S(b), Z, D, R, H, R, V )

(5.7)

s.t.                                  S i=1 b i ≤ P (5.8) ϕ(a) ≤ b η(x) • u(a) ∀a = (x, y) ∈ A (5.9) ϕ(a) ≤ b η(y) • u(a) ∀a = (x, y) ∈ A 2 ∪ A 3 (5.10) a∈A t 3 ϕ(a) ≤ J ∀t ∈ R (5.11) ϕ(a) ∈ N ∀a ∈ A (5.12) b i ∈ {0, 1}
∀i ∈ {1, . . . , S} (5.13) Equation (5.7) stands for the maximization of the demand. The value SDP returns the maximal number of demands the resolution of the SDP linear program for the specific configuration given as parameter. Equation (5.8) limits the total number of carsharing sites to P . Equation (5.9) (resp. Equation (5.10)) prevents an inner flow (resp. outer flow) to pass through a node if not active. Equation (5.11) limits the number of simultaneous vehicle relocation operations to J. Finally, Equations (5.12) and (5.13) define the variables' domains.

The mathematical program

The detailed linear program of the [slp] is given bellow.

[SLP]: max a∈A 2 ϕ(a)

(5.14)

s.t.                                                                    S i=1 b i ≤ P (5.15) ϕ(a) ≤ b η(x) • u(a) ∀a = (x, y) ∈ A (5.16) ϕ(a) ≤ b η(y) • u(a) ∀a = (x, y) ∈ A 2 ∪ A 3
(5.17)

a∈A t 3 ϕ(a) ≤ J ∀t ∈ R (5.18) a∈A 3 ϕ(a) ≤ R (5.19) a∈A ϕ(a) • a ≤ V (5.20) ϕ(a) ≤ u(a) ∀a ∈ A (5.21) y∈Γ -(x) ϕ((y,x)) = y∈Γ + (x) ϕ((x,y)) ∀x ∈ X (5.22) ϕ(a) ∈ N ∀a ∈ A (5.23) b i ∈ {0, 1} ∀i ∈ {1, . . . , S} (5.24)
Equation (5.14) expresses the maximization of the global demand. Equation (5.15) bounds the total number of carsharing sites to P . Equations (5.16) and (5.17) limit the inner and outer flow in every arc. Those two sets of constraints express the dependence between the state of the site (selected or not) and the possibility for vehicles to parked in the station. Next, Equation (5.18) limits the maximum number of simultaneous vehicle relocation operations to J. As noted before, it can be viewed as the number of available jockeys operating each time the system is rebalancing. Equations (5.19) to (5.23) are the same as those presented in the [sdp] linear program. They respectively limit the number of vehicle relocation operations and the total number of vehicles while the next two other are classical flow constraints. Finally, Equations (5.23) and (5.24) define the variables' domains.

Adding energy components

Throughout most of our discussion to this point, we have not talk about the vehicles themselves. For the last decades, the rise of the number of vehicles on roads has grown to the point where traffic jams and pollution have become an issue. In order to reduce dependence on oil, electric cars have retrieved a high interest since 2008 [Sperling and Gordon, 2009]. This interest did not occurred just because of increasing oil prices but thanks as well to advances in batteries and energy management. Climate policies and ecology have shifted consumer preferences. The need to reduce greenhouse gas emissions seemed to be now a important concern for the car industry who gave more and more attention to it in their products. Today, more and more electric vehicles are used on the roads. As of 2016, the market share in France represent almost 1% [CCFA, 2016].

The electric cars have several benefits over conventional internal combustion engine automobiles [AVEM, 2016]. First of all, they are cleaner vehicles. Especially in cities, they help reducing significantly the air pollution. They do not emit harmful tailpipe pollutants such as particulates (soot), volatile organic compounds, hydrocarbons, carbon monoxide, ozone, lead, and various oxides of nitrogen. Depending on the nature and origin of the electricity, electric vehicles spend around 20g of CO2/km against almost 130g of CO2/km for combustion vehicles. The gap in term of environmental cost between the electric and the fuel car will become even larger with the development and the availability of renewable energies. Secondly, electric motors are more energy efficient. No consumption is made during the off-idle phase and some energy can even be recover during deceleration or braking phases [Artmeier et al., 2010]. Finally, driving an electric vehicles appeared more reliable and pleasant. People spend less time and money for repairs and vehicles are much more quieter than gasoline-powered cars.

The major drawback of an electric vehicle comes from its battery. More precisely, the distance it can travel without the necessity to recharge (also call the range of the vehicle) do not exceed 160km for a standard car in urban traffic conditions, like a Renault Zoe for instance. Thus, electric vehicles are not presently suited for long distances but are more appropriate for short travels in urban areas. Additionally, charging a vehicle can take considerable time depending on the charging technique. The time needed to recharge a battery entirely depends on the available power supply. Basically, the more the power, the quicker the battery charged. Four power tiers, expressed in kWatt (SI unit symbol: kW), are currently used in the market [de l'écologie du développement durable et de l'énergie, 2014]: home charging (3kW), quick charging (22kW) and fast charging (44kW). More recently, superchargers delivering up to 120kW are today available. Those levels allow to charge a standard battery of 22kWh within respectively 6-8h, 1-2h and 20-30 minutes. Home charging answers to the most common situations where the vehicle is parked during a long period, during the night or working time for instance. Conversely, quick and fast charging require specific electric devices to be used and are not recommended for a day to day charge. They are more suited when parking time is very limited. They grant a higher flexibility covering situations with additional non-planned kilometres.

Related work

Introducing electric cars in station-based carsharing systems brings up new practical challenges with respect to their design and the management. Actual battery range require the vehicles to charge during the day at specific charging points in stations. Moreover, depending on the system infrastructure, the power supply may induce long charging times unless expensive fast charging points are provided. In this section we give a brief overview of the emerging problems arising when electric vehicles are considered in carsharing context. Although the existing literature is today very limited, we focus in this section on two problems: the energy shortest path problem and the carsharing system design including electric vehicles.

The energy shortest path problem consists in finding the least energy consuming path between two stations. In order to maintain enough energy in vehicles and maintain their availability, the carsharing operator needs to estimate the energy consumption of each trip performed during the day. Thereby, accurate information can be provided for users (through dedicated navigation services) and for jockeys rebalancing the fleet. In earlier works, [Artmeier et al., 2010] showed that the problem is a easier variant of the constrained shortest path problem, known to be N P-hard. From this work, researchers tend to improve the problem complexity proposing more efficient algorithms and exploring other aspects and additional constraints [Eisner et al., 2011, Sachenbacher et al., 2011].

More recently, other approaches using MIP formulation [Touati-Moungla and Jost, 2012, Wang et al., 2014, Arslan et al., 2015]. Some models allow to consider multiple vehicles, involved traffic congestion and non-linear cost functions. Finding accurate linear approximations for these functions is often highlighted as a valuable improvement in future works.

Carsharing system design problem including electric vehicles is a very recent topic and very few studies try to integrate electric constraints in strategic planning decisions. [Boyacı et al., 2015] proposed a multi-objective MIP model for planning one-way vehicle-sharing systems. Vehicle relocation operations and electric vehicle charging requirements are taking onto account. However, the charge state of each vehicle's battery is not explicitly considered. The authors include vehicles charging periods with specific constraints ensuring that a vehicle stays in stations for a fixed period of time when returned from a rental operation. A real case application of their model for to Nice region (France) using data from an existing carsharing system provides useful information regarding the system performance. The trade-off between operator and user objectives exhibit the importance of vehicle relocation benefiting to both stake holders. The authors plan in a future work to couple their model with a simulation tool which providing more realistic representation of relocation operation costs and allow to consider vehicle charge level among the optimisation process.

Beyond these results globally tackling many problems individually, no combined approaches has arise. As far as we know, optimizing the global system efficiency and the station locations while taking into account explicitly battery ranges and the power supply has not been addressed. The large amount of open problems suggests that those topics may account in the near future for a rich and interesting research area.

Selected energy components and modelling issues

Opt for electric vehicles bring some important constraints, on vehicles themselves of course but also on the system (stations especially) and its dynamics. In this section we discuss some energetic components we thought essential or interesting to introduce in the optimization process.

Although not all of them were selected in the detailed model presented in the next section, we still wanted to give here some insights to be familiar with each of them. Afterwards, some modelling issues are highlighted.

The battery capacity

Despite there exists a large diversity of electric batteries, the most common are based on the lithium ion technology. Their light weight make them suitable for numerous applications such as portable devices, power tools or electric vehicles. Today, the typical battery range for carsharing electric vehicles varies on average from 160 to 250 kilometres, depending on the driving context and the weather conditions.

The power supply

For now, charging an electric car takes from 30 minutes to 6 hours depending on the charging technology. Moreover, the charge is not linear. It is very fast during approximately the 80 first percents of the battery capacity and became more and more slower until reaching the full capacity. But for reasons of simplicity, we will assume in this work that the battery charge follows a linear profile.

The discharge

Modelling the discharge of an electric vehicle can be difficult because electric cars can restore some energy during decelerating and braking phases. Additionally, note that the discharge when the vehicle is neither used or plug into a charging point is negligible, about 1 to 2% per month. In this work, we assume the battery discharge to be linear over time.

The number of charging points per station

Carsharing systems with electric vehicles have to equip their stations with charging points. During the design phase of the system, it could be interesting not to consider systematically that all the parking spot are equipped with charging points. A better solution would be providing power supply where the system need to, according to the estimated stations' attractiveness. Thereby, the operator save money while maintaining a good level of service.

Price of electricity

In France, the price of electricity constantly varies during the day. It is fixed at the European Power Exchange SE (EPEX SPOT SE), the exchange operating the power spot market for short-term trading power in some European country, including France. Integrate this price in a system design context could certainly be a interesting feature. Fostering the recharge by night for instance, when the price of electricity is the lowest, could be a significant economic argument.

Modelling issues: the flow interpretation

In a carsharing system with electric vehicles, accept or reject a request will not only depend on the vehicle availability. The battery level become a important parameter impacting the decision to provide or not the resource, in this case the electric car. It has to be sufficient enough at least to travel the distance between the origin and the destination. Whether to fulfil a request, or operate a vehicle relocation operation, we now need to track and check every single vehicle in the system over time. From a modelling point of view, we have seen previously that vehicles are considered as flows in a time expanded graph. Since then, the flow was considered as integer but not necessary unitary. This means that an optimal flow could admits some parts where

1(1) 1(2) 1(3) 2(1) 2(3) 1 1 1 1 1 1 1(1) 1(2) 1(3) 2(1) 2(3) 1 1 1 1 1 1 1(1) 1(2) 1(3) 2(1) 2(3) 1 1 1 1 1 1 Figure 5.1 -Different flow interpretations.
more than a unit flow is passing through an arc. From a system point of view, without the need to track single vehicles, it was not a problem and corresponded to merged vehicles itineraries. However, in order to identify the route of each vehicle in the system, an interpretation of the flow as a set of unit flows has to be determine.

Figure 5.1 illustrates a unit flow interpretation even when the flow is unitary. Suppose that an optimal flow admits a baseline situation, as illustrated by the above graph of the figure. This solution is feasible since the conservation flow is respected; the number of inner and outer flow is the same in each node. Now the question is to recover from this situation vehicles' itineraries as unit flow paths starting and ending at time t = 1. Obviously, a first interpretation could lead to the left figure, where the two colors indicate the vehicles itineraries. Another possible interpretation is presented in the right figure, where this time both vehicles do not end their trip in the station they came from. Note that even if both cases are feasible solutions, they do not require the same amount of energy. In the first case, the blue car will move two times, thus require more energy than the other vehicle which stays in station 1. In the other side, the situation is more equilibrated. Both vehicles move exactly one time and share the energetic requirements. As illustrated by this example, we can enumerate two conclusions. First, with a realistic size carsharing system, i.e. with much more stations and numerous time-steps, a unique feasible solution could lead to many interpretations in terms of vehicles' itineraries. Secondly, every interpretation has its own energetic impact and, besides could not be feasible in that sense.

Therefore, introduce energy components through a feasible interpretation of vehicles' itineraries do not seem a relevant and reliable solution. There is furthermore no guaranty that an optimal solution could be extracted from a solution that do not take into account the energy. We finally decided to reuse the model previously used to solve the [slp] and adapt it so that it can support and include energy constraints.

Mathematical program

The major issue underlined in the previous section concerns the flow decomposition into unitary flow paths. This decomposition is essential to follow every vehicle in the system and be able to track its batteries over time. Indeed, with electric vehicles, their availability in a station at a given time is not sufficient to ensure the travel. The battery level also take part in the decision process and assesses if the required travel could be support or not. In this section, we present how to modify the previous time expanded graph so that it can support energy components. A new mathematical model is finally presented.

Graph transformations

Avoiding the flow interpretation can be simply achieve by duplicate arcs with non unitary bound. The basic idea is to force the flow to be unitary by limiting the arcs' capacities. In fact, the system remains unchanged if we replicate each arc a ∈ A into u(a) (the arc capacity) arcs with unitary capacities. Figure 5.2 illustrates the transformation. The initial TEG introduced in Chapter 3 is transformed into a TEG where all the arcs are bounded by 1. Even the relocation arcs, where the capacities were previously set to infinity, can be unitary bounded. Again, this could be done without loss of generality since it only limit a vehicle relocation operation to be operate by only one jockey, which is realistic. This simple transformation allows now the flow to be at most unitary. Nevertheless, the operation can be achieve at the cost of a notable increase in the number of arcs. More precisely, the only set of arc impacted is the set A 1 corresponding to the stock arcs. For the record, their original number was about exactly S • T arcs. Now, the size of the new set of stock arcs, noted A 1 is exactly:

|A 1 | = S i=1 (Z(i) • T) = T • S i=1 Z(i) (5.25)
In practice, this means that the increasing factor depends on the maximum size of the carsharing stations, or sites. It will be important to keep this result in mind since the number of variables depends directly on the number of arcs.

Additional parameters

To extend the model with electric components, let's first define some parameters related to batteries and stations' power supply. All the other notations or variables have the same meaning that before. For the record, ∆t is the time period expressed in minutes between two consecutive time-steps.

The total capacity of the vehicle battery will be noted E. For sake of simplicity, this value will be expressed in kilometres but could equivalently be expressed in kiloWatts. Indeed, it is assumed that the two units are link through a linear relation. Besides, it is also assumed that all vehicles are equipped with the same type of batteries.

As said before, there exists different types of station power supply. Depending on the battery capacity, the power however can be expressed over time. Let ω(E) be the number of minutes needed to refill an empty battery to full charge.

time | 1 | 2 | t | T • • • • • • 1(1)
. . . 1)

S(

1(2) 1(t) 1(T) S(2) S(t) S(T) (2)
(2) (

(2)

(2) (2) (2)
(2)

(1)

(2) time | 1 | 2 | t | T • • • • • • 1(1)
. . . 1)

S(

1(2) 1(t) 1(T) S(2) S(t) S(T) (1)
(1)

(1)

(1) Since the vehicles now consume energy when travelling and have the possibility to recover it when parked in station, some adjustments are required. We associate with each arc a ∈ A in the new graph an additional value noted γ, standing for the energy consumption. This value expressed in kilometres will be positive when vehicles performed a trip (i.e. for demand arcs A 2 and vehicle relocation arcs A 3 ) and negative when parked in station (i.e. stock arcs A 1 ). The distance in kilometres between stations s 1 and s 2 , both in the set S, is denoted by d(s 1 , s 2 ). This value can be recovered from any mapping tool simulation giving exactly the distance between stations by road or it could more simply corresponds to the euclidean distance between them. Nevertheless, a penalty coefficient ρ ≥ 1 revised the value during rush-hours as vehicles consume more energy at lower speed travelling the same distance. Outside these periods, we set ρ = 1. Therefore, the energy consumption is formally defined as:

γ(a = (x, y)) =      - E • ∆t ω(E) if a ∈ A 1 , (5.26) ρ • d(η(x), η(y)) if a ∈ A 2 ∪ A 3 .
(5.27)

First equation (5.26) assigns to every stock arc the number of kilometres a vehicle could travel if it recharge its battery during one time-steps; stock arcs connect nodes spaced from a single time-step interval. Second equation (5.27) stands for the travel distance between stations raised by the penalty coefficient during rush periods.

Variables

The set of variables is extended to three sets. The first one remains the flow variables. Assign to every arc of the graph, they identify as before vehicles' routes through the system. Note however that now the flow do not longer need to be integer. A boolean domain is sufficient since all the arc capacities were set to 1. Next set of variables aim at avoiding path interpretations after having run the optimization process. In each node, a boolean variable A ij indicates if the flow coming from arc i is continuing to arc j. We refer to those variables as the flow affectation variables. As discussed later on, this set is probably the major drawback of this model due to the substantially augmentation of the number of variables. Their number however grows polynomially with respect to the number of arcs. Lastly, let E a the battery level of the flow (vehicle) entering the arc a. Similarly to the energy consumption, those variables are expressed in kilometres.

The three sets of variables are summarized in the following:

1. ∀a ∈ A, ϕ(a) = 1 if a flow enters arc a, (5.28) 0 if otherwise. (5.29) 2. ∀x ∈ X such that i ∈ Γ -(x) and j ∈ Γ + (x), A ij = 1
if the flow coming from arc i follows to arc j, (5.30) 0 if otherwise.

(5.31)

3. ∀a ∈ A, E a ∈ (0, E).
Obviously, the total number of variables is much more greater than before. Although flow variables and battery variables follow the number of arcs in the graph, this is not the case for the flow affectation variables. At each node x ∈ X there is exactly

|Γ -(x)| • |Γ + (x)| affectation variables that indicate the arc sequence in this specific node x. Since |A 1 | |A 2 ∪ A 3
| with the TEG transformation, their number can be approximated to

T • S i=1 Z 2 i = Θ(|A| 2 ).

Mathematical program

Using the notations above, we can formulate the energy model as follows:

[ENERGY]: max

a∈A 2 ϕ(a) (5.32) s.t.                                                                                                                E j ≤ E i -γ(i) • A ij + E • (1 -A ij ) ∀(i,j) ∈ A 2
(5.33)

E i ≤ E j + E * (1 -A ij ) ∀(i, j) ∈ A 1 × A (5.34) ϕ(a) • γ(a) ≤ E a ∀a ∈ A 2 ∪ A 3 (5.35) E a ≤ E • ϕ(a) ∀a ∈ A (5.36) j A kj = ϕ(k) ∀k ∈ A (5.37) k A kj = ϕ(j) ∀j ∈ A (5.38) a∈A 3 ϕ(a) ≤ R (5.39) a∈A ϕ(a) • a ≤ V (5.40) a∈A t 3 ϕ(a) ≤ J ∀t ∈ R (5.41) S i=1 b i ≤ P (5.42) ϕ(a) ≤ b η(x) • u(a) ∀a = (x, y) ∈ A (5.43) ϕ(a) ≤ b η(y) • u(a) ∀a = (x, y) ∈ A 2 ∩ A 3 (5.44) E a ∈ (0, E) ∀a ∈ A (5.45) A ij ∈ {0,1} ∀(i,j) ∈ A 2 (5.46) ϕ(a) ∈ {0,1} ∀a ∈ A (5.47) b i ∈ {0, 1} ∀i ∈ {1, . . . , S} (5.48)
(5.49)

As always, the objective function (5.32) maximizes the number of satisfied demands. The first six groups of constraints are related to the energy components and the flow affectation variables. Equation (5.33) defines the upper bound of the battery level. If the flow coming from arc i is continuing its path to arc j (i.e. if A ij = 1), then the battery level E j is at most the previous battery level E i minus the energy consumption when passing thought arc i (i.e. γ(i)). In the case of A ij = 0, there is no need to limit E j and its upper bound is relaxed to E i + E, a greater value than the battery capacity. Next constraints (5.34) ensures that the battery do not discharge when parked in station. After being parked in station, the battery level of each vehicle must at least equals to its value before the operation. This situation is expressed as E i ≤ E j when A ij = 1 and i ∈ A 1 . Equation (5.35) connects the battery level and the energy consumption when vehicles are travelling. It requires the battery to dispose of a sufficient level in order to achieve the trip, whether it is a demand or a vehicle relocation. Constraints (5.36) set the battery level variables to 0 if there is no vehicle passing through the arc a. Finally, constraints (5.37) and (5.38) are flow conservation constraints. As illustrated in Figure 5.3, it ensures that no more than one unit of flow is coming from the predecessors of node x. Similarly, at most one unit of flow can continue to the successor of node y after passing through the arc j.

Next equations are the same as in the station location model. For the record, note that R, V , J and P denote respectively for the maximum number of relocation operations, vehicles, jockeys and opened carsharing sites. Equations (5.43) and (5.44) forbid the inner and outer flow coming or leaving not selected sites. Finally, Equations (5.45) to (5.48) express the respective variable domains.

Discussions and improvements

Model statements

The model [energy] allows us to tackle the station location problem while taking into account energy components including the stations' power supply and vehicles' batteries. Moreover, vehicles' routes do not longer have to be deduced or calculated from an optimal flow solution. Following successive non-zero values of flow affectation variables (i.e. A ij , A jk . . . ) allow to constitute vehicle itineraries and avoid routes interpretation. Besides, any feasible solution provides the energy consumption profile of all vehicles by simply reporting every battery variable value along vehicle itineraries. As a results, this model seams promising. Unfortunately, the number of variables, directly related to the total number of arcs, has increased dramatically. More importantly, the number of arcs has already grown compared to the previous model (see. Section 5.3.3.1, page 77 about the graph transformations). We present in the following some solutions to reduce the number of variables and improve the model sustainability.

Removing the symmetries

One of the main drawback leading to the surge of the number of variables is the arc symmetries. By duplicating the stock arcs during the graph transformation phase, we created multiple equivalent situations. Indeed, the number of flow affectation variables depends on the number of inner and outer arcs in each node of the TEG. In practice, it is not necessary to create a flow affectation variable to each pairs of successive stock arcs. Perhaps the best way to understand the possible reduction is via an example. Let consider the situation depicted in Figure 5.4, where it is assumed that the arcs belong to the set of stock arcs (A 1 ). Three time-consecutive nodes are represented. The station they symbolized have a maximum capacity of two parking lots, thus nodes are link by a pair of arcs; e.g. a and c between nodes x and y. Until then, four flow affectation variables were considered: A ab , A ad , A cb , A cd . Those situations are depicted on the left side of the Figure . From a system point of view, a unit-flow leaving x, then entering y to finally arrive at node z means that a single vehicle is parked in the station during two time-steps. In this case, one of the flow affectation variable enumerated above is set to 1. However, there is no difference in term of interpretation for a unit-flow entering node y whether continuing through arc b or continuing through arc d.

In a certain way it can be viewed as a "parking slot swap". It is as if the vehicle parked in slot 1 need to change to slot 2. This distinction might be interesting if we had included the possibility to stations not to have all their parking slots equipped with power supply points. But so far, this possibility has not been assumed in the model.

As a consequence, the number of flow affectation variables can be highly reduced. Distinctive pairs of successive arcs are sufficient to cover realistic situations without reducing the possibilities. Following this idea, the number of flow affectation variables related to stock arcs decreases from

|Γ -(x) ∩ A 1 | • |Γ + (x) ∩ A 1 | = Z(η(x)) 2 to Z(η(x)) for all x ∈ X .

A greedy heuristic

Running the [energy] model induce limitations due to computation time and solver capability. In practice, even on small instances (20 stations, 15-minute time-steps and 600 daily requests), CPLEX encounters great difficulties to converge. The relaxed problem resolution is solved relatively quickly (within minutes) but fail most of the time at founding a good quality lower integer bound. To deal with this issue, we investigated an approaches based on the warm start technique. The idea is to provide the solver a solution before starting the MIP optimization.

The solution may be incomplete and, basically it consists in defining value assignments for a set of variables (discrete and/or continuous).

Because we do not have observed so far a noteworthy pattern in the solutions, it seams difficult a priori to come up with a rounded solution. We denote by rounded solution a set of variables' values coming from the optimization of a relaxed instance of the problem and then rounded following more or less sophisticated rules. In our experimentations, we only used binary rules. For instance, suppose a binary variable x. For an observed non-integer optimum value x , its rounded value is set to x if x ≤ v ∈ (0, 1) and x otherwise.

Unfortunately, neither the vehicles' trip profiles or the station attendances showed notable patterns what could help us defining that could be a good quality solution. Although we tested numerous rounding configurations, we have not succeeded in decreasing solver computation times using rounded solutions.

To cope with solving times, we finally opted for a greedy heuristic implementation. Unlike the previous solution, an heuristic benefits from a fast execution and come up with a feasible solution satisfying energy constraints. The next of the section describes the mechanics of the algorithm. A simple example running the some steps of the heuristic is finally presented.

Functional description

The main idea is to build vehicles' routes from a weight modified TEG while taking into account the energy viability of vehicles' itineraries. Since the [energy] problem aims at maximize the number of satisfied demands, the heuristic is based on a modified Dijkstra's algorithm [Dijkstra, 1959] where the weights on the arcs are set as followed:

w(a) = 0 if a ∈ A 2 , 1 otherwise.
Equivalently, we refer to w ij as the weight value between nodes i and j, i.e. w ij = w(a) for any a = (i, j) ∈ A. As a consequence, arcs are weighted according to their contribution to the objective function. By doing so, find the path with the highest number of demands arcs linking two nodes in the TEG is equivalent to find the shortest path therebetween. To deal with this shortest path problem, we have opted to use the Dijkstra's algorithm, a label-setting algorithm returning a solution in a polynomial time. However, the path may not be feasible according to energy constraints and some algorithmic adjustments are needed. It should be noted here that we actually are looking for shortest cycles, due to the Theorem 1 (page 43).

In addition to the standard distance label value d(i), we associate to each node i an energy label e(i) standing for the vehicle battery level at this node, which is an lower bound of the energy remaining in the battery for this specific node. At each iteration, and similarly to the distance label, the energy label will be updated according to the energy consumption it takes to reach adjacent nodes. Any adjacent nodes j for which e(i) -w ij < 0 can not pretend being a feasible successor of node i. As a consequence, neither its distance label nor energy label should be updated. At any intermediate step of the algorithm, the energy label of a node i stores the maximum battery level of a vehicle performing the shortest energetically viable path from the source. It is assumed that the vehicle recharged its battery when parked in station whenever it is possible.

The algorithm iterates over a set of starting nodes defined as X t = {x ∈ X | θ(x) = t}. This set represents a temporal snapshot of the system at a given time-step t ∈ T . In practice, we usually use X 1 and the algorithm tries to find as many cycles as possible from this set. The algorithm terminates when no more cycle containing demand arcs can be found. It should be noted that the problem we address here is not to find shorter paths from a source to every other nodes in the network but rather to find shortest cycles, which can be viewed as paths starting and ending at the same vertex. To solve the problem faster, the algorithm terminates the cycle search procedure as soon as the source can pretend to be selected from the list of temporary labelled nodes, even though some nodes are still in this list.

Algorithm 1 gives a formal algorithmic description of the modified Dijkstra's algorithm taking into account energy constraints.

We illustrate the mechanics of the algorithm 1 using the numerical example given in Figure 5.5. We consider the node 1 as the source node and a maximum battery capacity of 10 kilometres is assumed (i.e. E = 10). The above right figure depicts the graph topology as well as weights and energy consumption values in each arc.

Figure 5.5(a) initialize the successors' labels of the source node. Then, the algorithm permanently labels the nodes 3, 5, 6 and 2 in this given sequence. Figure 5.5(b) to (e) illustrate the operations for some of these iterations. Note in Figure 5.5(b) that d( 4) and e(4) has not been updated. Since the remaining energy at node 3 was not sufficient for the trip requirements (e(3) = 3 < γ 34 = 5), the path is not energetically viable in practice.

Finally, in Figure 5.5(f), nodes 1, 4 and 7 are equivalent choices since they all admit a distance label d(i) = 2. Because the source node (node 1) can now pretend to be permanently labeled, the cycle search routine ends in this iteration. As a result, the shortest cycle is (1, 3, 5, 6, 1) and two demands are satisfied. Note that energy constraints are satisfied since the energy label of node source is positive (e(1) = 5).

Conclusion

In this chapter, we introduced several mathematical model for solving the station location problem. This problem deals with the optimal selection of a sub-set of potential carsharing sites which maximize the global demand. A first model [slp] relies on an enhanced version of the system dimensioning model [sdp] exposed in Chapter 3 and combines diverse additional features. In particular, the model limits the total number of jockeys (employees in charge of the vehicle relocation operations) restraining the number of simultaneous vehicle relocation operations. We highlighted the dependence between both models exhibiting a master-slave scheme. Finally, a detailed [sdp] generalised version of the [slp] model was presented.

The second part of the chapter coped with the energy integration. In practice, electric vehicles bring many specific attributes involved in the design of a carsharing system. Among them, we have elected two major components: the battery range and the power supply of the charging points. The first limits the total distance a vehicle can travel without recharging while the second defines the electric rate of charge the power supply delivers. The main issue at including those parameters concerns the necessity to track every single vehicles during the period so that a trip can be rejected if the battery level is not sufficient. We have shown that the previous model [slp] was not suitable at following vehicles. More particularly, the transition from a flow-based solution to single vehicle routes cannot be achieve without an interpretation of the flow. Besides, this interpretation leading to many vehicle routes configurations has no guaranty that a energetically feasible solution can be found. As a consequence, an updated model was required.

We finally introduced the model [energy]. Based on unit-flows, the model avoids vehicle routes interpretation including rooting variables (called affectation variables) at each nodes in a modified TEG. Although vehicle routes can now be extracted very quickly, their integration in the model has lead to drastically increase the number of variables. We thus provided a new set of variables exhibiting some symmetry configurations in the graph and decreasing their number from Θ(T

• i∈S Z(i) 2 ) to Θ(T • i∈S Z(i)).
The chapter concludes with the description of a greedy heuristic, based on a modified Dijkstra's algorithm including energy components. Some limitations due to computation time and solver (CPLEX) capability pointed out the necessity to provide a feasible solution before staring the optimization. The algorithm adapts the label-setting algorithm so that the problem become a shorter path problem. The main idea is to determine feasible vehicle routes providing boolean weights on arcs so that null values are assigned to arcs contributing to the objective function. Adjustments on specific added labels aim to converge to a shorter path verifying energy constraints. A formal description of the algorithm as well as a detailed example are provided.

C ← C ∪ cycle(s); end X t ← X t -{s}; end i j (d(i),e(i)) [w ij , γ ij ]
(d(j),e(j))

Legend:

1 source 2 4 6 3 5 7 [1, -3] [0,7] [1, -3] [1, -3] [1,5] [1, -3] [1,3] [0,4] [1, -3] [1, -3] 1 2 4 6 3 5 7 (∞, -∞) (1,10) (0,3) (∞, -∞) (∞, -∞) (∞, -∞) (∞, -∞) (a) 1 2 4 6 3 5 7 (∞, -∞) (1,10) (0,3) (∞, -∞) (1,6) (∞, -∞) (∞, -∞) (b) 1 2 4 6 3 5 7 (∞, -∞) (1,10) (0,3) (∞, -∞) (1,6) (1,2) (2,9) (c) 1 2 4 6 3 5 7 (2,5) (1,10) (0,3) (∞, -∞) (1,6) (1,2) (2,9) (d

Abstract

In this chapter, we study the energetic profile of electric vehicles through a carsharing use-case. Based on a reduced version of a real carsharing service, we analyse optimal solutions given by the computation of the [energy] model. We focus the experimentations on the study of sufficient EV range in carsharing systems. Results show that decreasing actual battery range (160 km -22 kWh) by half do not alter solution quality. Outlooks toward the exhibited residual battery capacity are discussed.

Introduction

We have seen in the last chapter that running the [energy] model may be difficult according to its complexity. The size of the model depends on three parameters: the number of timesteps, the number of stations (or potential sites according to the version) and their associated maximum size (number of parking slots). Fundamentally, for large systems and narrow timesteps, the solving process may lead to impracticable computation times.

In this chapter, we study a realistic and practicable model based on 15 stations. As detailed thereafter, the data has been made so that the system could be similar to the Parisian carsharing system Autoblib' in terms of operational performance (average number of satisfied requests captured by vehicles and average daily time spent on road).

On the one hand, we have seen at the beginning of this thesis that carsharing vehicles were more used than private vehicles (see. Chapter 2, page 16). Especially the time spent on the road is much more higher due to the higher utilisation rate of the vehicle.

On the other hand, including electric constraints into the system optimization raises the question of system viability. More particularly, battery range still remains today a major concern when using electric vehicles [Franke et al., 2012]. This apprehension, also known as range anxiety, is considered as the major barrier to large scale adoption of all-electric cars. By extension, carsharing systems equipped with EVs also suffer from this psychologic side effect. Carsharing operator, as well as car manufacturers, tends to deploy different strategies to handle it. Basically, vehicle range can be extended by deploying more charging infrastructure or better guide drivers on roads with more accurate navigation tools. Besides, other strategies more focussed on battery themselves can be considered. Battery swapping technology, range extenders and the development of higher battery capacity at a cost-effective price are the main approaches.

Determining sufficient EV range has been the focus of numerous studies. Answering this question is difficult and depends not only on range needs, but also on customer preferences. Results reveal a substantial discrepancy between both notions, sometimes refer as the "range paradox" in EVs [Franke and Krems, 2013]. While currently common 160-kilometres range is generally estimated sufficient for a sizeable share of the car driving population [Pearre et al., 2011, Chlond et al., 2012], other studies report that the average customer wants a vehicle range of approximately 350 kilometres [Bunzeck et al., 2011]. However, is the battery range still sufficient in the context of urban carsharing where vehicles are more intensively used? And what could be the optimal battery size of a carsharing vehicle in the future transportation context where more and more demands will have to be satisfied?

For the most part, in this chapter we wish to address the following questions:

1. Are actual EV-battery capacities well suited for a carsharing usage? 2. What is the minimum battery-range allowing the system to run at its highest efficiency?

3. What role does the power supply plays in the system dimensioning?

The chapter is organised as follow. Section 6.2 describes the experimental context of the study. Assumptions and method are especially exposed. Next, numerical results and global indicators are presented in Section 6.3. Insights on vehicles' energetic profiles are especially detailed. Finally, Section 6.4 concludes with possible extensions and further research are discussed.

Experimental context

In the urban area of Paris, Autolib' is a carsharing service of more than 1000 stations maintaining a fleet of 3800 electric vehicles [Autolib', 2016]. As of February 2016, 4.5 trips on average are realized by each vehicle. Approximately 47 minutes are spent on road each time a vehicle is rent for a total of 3 daily hours in travel.

In this study, we intend to base our experimentations on a comparable system to Autolib', not in size but rather in term of operative indicators. Indeed, take advantage of the [energy] model while avoiding computation issues imply to limit the total number of stations, their maximum size and the time-step interval considered for the time period. This section presents some global model parameters leading after the solver computation to similar operating indicator values. Mathematical programs were solved using the Java API of IBM ILOG CPLEX 12.5.1.

Using the random data generator describes in Chapter 2, we investigate a specific carsharing use-case. It addresses a common scenario where an area poorly served by public transport is covered by two emitter poles. A maximum inter-station distance of 30 kilometres was assumed and the centroid area is 15 kilometres far from each pole. In addition, no demand intra-pole was considered. It is assumed that most people want to join the centroid in the morning while the exact reverse phenomenon is observed the evening. A total 200 demands over the day were generated between 15 geographically fixed stations. Vehicle relocation operations are defined at specific periods of the day. Basically, the system can be rebalanced by 10 jockeys during the morning (6h, 7h and 8h), around mid-day (12h, 13h and 14h) and the evening (20h, 21h and 22h). Those arbitrary hours have been considered so that jockeys' working hours can be realistic. Vehicles admit a standard battery capacity of 160 kilometres and stations are equipped with home-charging points. Loading an empty battery takes 6 hours. Finally, a maximum of 30 electric vehicles and 20 vehicle relocations during the day has been assumed.

Model parameters are summarized in the following:

• Time: ∆t = 15 and T = 96.

• Stations: S = 15 with Z(i) ∼ U [4,6], ∀i ∈ S.

• Vehicle relocation operations: R = {24, 28, 32,48, 52, 56, 80, 84, 88}.

• Energy: E = 160, ω(E) = 360.

• Demand and upper bounds: D = 200, R = 20, V = 30, J = 10.

Results and analysis

Considering a 15-minutes time-step period, the model finds the exact solution in 10 seconds. Figure 6.1 depicts both satisfied and unsatisfied demands for each hour of the day. Note that the global demand can be recovered summing the both values for each time of the day. Between midnight and 1 am for instance, two requests were generated. The optimal solution succeeded to fulfil one of the two. More globally, the demand satisfaction rate over the day stands at 88%. Numerous reasons can explain why a demand is unsatisfied. For instance , no vehicle can be available at the origin station, the remaining battery level cannot support the requested trip, or even the station of destination will not allow the car to park due to the lack of available parking slot. Nevertheless, whatever the reasons for not fulfil a request, by using an exact solving method (Branch and bound method), we make sure that the solution (i.e. this set of vehicles route configuration) is the one satisfying the maximum number of demands. Thus, vehicle routes can be made in order to anticipate future demands since all the requests over the day are known. In particular, the unsatisfied demand at midnight observed in Figure 6.1 enables the vehicle parked in the station to meet more demands later in the day.

Looking at operative indicators, the average number of trip performed by each vehicles (5,8) and the number of daily hours on road (3 hours) are aligned with those of Autolib'. However, we observed a significant difference with respect to the daily distance travelled. On average, vehicles cover 108 kilometres while Autolib' reports 44.6 kilometres [START_REF] Autolib | Autolib[END_REF]. This dissimilarity results directly from the specific geographical topology of our system where stations are distributed among distant poles. More precisely, the inter-station distance (13.7 km) is higher in our use-case than in the Autolib' system where only 363 metres separate two stations. From an energetic point of view, this observation may provide an additional interest since vehicles are limited by the range of the battery. As observed in Figure 6.2, only four vehicles (13%) need to refill during the day to perform their trips since their total travelled distance exceeds the battery capacity threshold. In that sense, the total battery capacity do not seem as an issue.

It is interesting to note that the vehicle repartition appears uniform regarding the daily covered distance and the time spent on road. Besides, the relation looks linear, following the natural intuition that the more a vehicle travels, the more time it spends on the road. A similar result can be observed regarding the distance travelled and the number of satisfied demands. The interest in using the [energy] model is its ability to track any vehicle in the system and display the associated energy consumption profile over the day. In particular, the highest energy variation sustained by the battery in an important indicator to state on the sufficient range a vehicle needs. Figure 6.3 depicts for each vehicle the observed battery level range (difference between the minimum and the maximum value) according to the number of satisfied demands during the day. Clearly, the actual 160 km battery capacity appears widely sufficient. The higher observed battery range value, standing at 75 kilometres, indicates that decreasing the battery by half do not alter the solution quality. Moreover, 80% of vehicles can operate their route with a total battery capacity of 50 kilometres. This result opens many perspectives toward the battery range in carsharing context. First, from the car manufacturer point of view, adjust vehicles' range to their daily usage may result in saving important financial costs while improving the performance of the vehicles. Indeed, reducing the battery capacity also decreases its size. A direct consequence is that the battery is cheaper and lighter. As of 2016, a standard 22 kWh battery represents 20% of the overall cost of the electric vehicle [ave, ].

Secondly, the residual capacity enhanced by results in Figure 6.3 could also be intended for other uses. Today, increasing attention is paid to include more renewable energy in the global mix consumption scheme. Many applications may arise from this highlighted available battery capacity.

A direct consequence of an overcapacity is a lower loading frequency. Technically, the lifespan of actual batteries (regardless of the technology) depends primarily on the number of charge cycles the battery experiences over time. In order to increase the battery lifespan, it is better to do micro-loadings than full charges. Indeed, going through full discharge deteriorate actual EV battery. Also, the substantial energy may supply housing needs and, more globally, every energy consumer. With the recent development of smart grid technologies, electric vehicles are no longer considered as energy consumers, but also as energy providers (see. vehicle-to-grid -V2G). In addition, reducing energy during peak hours is important and a higher electricity storage may result in performing peak curtailments.

Finally, the overall fleet stock might serve the vehicles themselves. In a same station, vehicles can charge their batteries with electricity delivered from the internal fleet stock rather than the global electric network. As a result, the carsharing system emancipate itself from the financial dependency with the transmission system operator.

Looking more closely at vehicle energy consumption, Figure 6.4 shows the consumption profile of the vehicle achieving the higher battery range; i.e. the vehicle on the right side of the Figure 6.3 performing six demands over the day. The battery level peak of 75 km is reached just before 4 pm. It is justified by the necessity to satisfy three successive demands between 4 pm and 6 pm without any time to load the battery. The peak at 20 pm is a vehicle relocation.

The red curve plot represents the electricity price variation in France during November, 10th 2015. Clearly, the time range in which the vehicle is in charge corresponds to the moments the electricity is expensive. This is due to the fact that the price follows the electricity demand, precisely similar to the travel demand. Besides, no constraints on the accurate time to charge vehicles nor relations with electricity prices are consider in the model [energy]. Further research indents to improve the consumption price charging vehicles by night when the system can benefit from low prices.

When the carsharing demand doubles to 400 daily requests, the global satisfaction rate looses 6%, reaching a value of 82%. With the same system holding 30 vehicles, this loss is understandable. On average, 11 trips are ensured by each vehicle and slightly less than six hours are spent on roads. Globally, similar profiles regarding the daily cover distance and the time spent on road are observed. Vehicles travel however 214 kilometres on average, twice more than previously and 4.5 times more than Autolib'. This time, 83% of vehicles need to charge during the day as their total cover distance exceeds the battery capacity. Interesting result can be observed in Figure 6.5 showing the range in vehicles' batteries for this demand scenario. With actual battery range (160 km), no vehicle is limited by the battery capacity to perform its route. Moreover, almost 76% of vehicles still can do it with a range of 85 kilometres.

Conclusion

With the help of the model [energy] previously introduced, this chapter studied a realistic carsharing use-case. As a first step, a scenario based on a fixed system of 15 stations and 30 vehicles investigated the electric battery usage when vehicles are requested as observed in the reality. A total of 200 daily demands allow to observe similar operational performance as the Parisian carsharing system Autolib'. Targeted indicators were the average number of satisfied demands per vehicle and the average daily hours spent on roads.

Results shown that the necessity to charge during the day, according to a standard battery capacity of 160 kilometres (22 kWh), is almost non existent. On average, a vehicle covers 108 km per day and its easy to state that starting with a full-charge battery in the morning, most of them can achieve their route at the end of the day. More interestingly, the observed maximum battery range (difference between the largest and smallest level) indicates that divided the capacity by half do not depreciate the solution quality. In other words, the exact same solution is still viable if the total battery capacity is set to 80 kilometres.

We discussed the perspectives of using this induced residual capacity. More especially, two opportunities has been highlighted. For car manufacturers, it can lead to financial costs savings; a smaller battery is both cheaper and lighter. For the system itself and its direct environment, the substantial stock of energy may be used for many other usages as load adjustments or peak levelling. Those outcomes may help urban planning policymakers design more efficient systems.

A deeper look at vehicles' energy consumption let us noticed that vehicles are not charged at appropriate periods when energy is cheap. As previous results shown, the unused battery capacity might probably help to store energy during the night when the electricity price is attractive. Further research intend to improve the energy management of the carsharing system in accordance with the costs.

Finally, we investigated the consequences of an increasing demand on the system sustainability and optimal battery range. In this second scenario with twice demands, we observed that vehicles really need to charge. However, actual battery range still appeared well suited and the maximum battery range never exceeded 160 kilometres.

Abstract

This final Chapter concludes the thesis. After recalling the addressed problems and the context of this research, main results and contributions are summarized. Some perspectives and opened problems are finally provided.

Addressed problems

The popularity of station-based carsharing systems has recently led to an increasing interest in behavioural user analysis and system management. Especially for the one-way version of the service where users are allowed to pick-up and return a vehicle at any dedicated station, the research community intensified its attention on optimal system design and optimal vehicle relocation strategies. Indeed, the uneven nature of the demand for mobility in urban areas unbalances the system bringing many operational challenges.

In this thesis, we investigated two problems arising in the design of station-based one-way carsharing systems. The first one is dedicated to the optimal system dimensioning, referred in this manuscript as the System Dimensioning Problem [sdp]. For fixed and known station locations, it aims at determine global indicators, such as the minimum number of vehicles and the optimal station capacities (number of parking places), allowing the system to run at its highest potential. Throughout this report, we considered the system efficiency (or the system potential) as the number of carsharing demands vehicles can satisfied along a specific time period. In practice, we based our experimentations on data randomly generated or estimated during a typical weekday.

The second problem deals with optimal station locations and is referred as the Station Location Problem [slp]. A key factor in increasing the performance of carsharing system is the ability to make the service accessible at relevant places. As a generalisation of the [sdp], this problem focuses on identifying the right sub-set of stations among a set of potential carsharing sites that captures the highest number of demands. Besides determining optimal system components related to the system design (e.g. the optimal fleet size, the station locations or the stations' capacities), many studies underlined that the approach must include important mechanics inherent to one-way carsharing systems. For instance, the necessity for the carsharing operator to balance its vehicle fleet during the day is absolutely necessary to achieve a good service quality. Those operations imply having its own resources (operator's employees also known as jockeys) to move vehicles among stations, generally from ones where there is an exceeding of vehicles to one in deficit. As a consequence, additional constraints coping with the total number of jockeys and total number of relocation operations were also included.

Today, carsharing operators are increasingly incorporating electric vehicles in their vehicle fleet. Despite the fact that such vehicles reinforced the positive impacts of carsharing on the environment, they also bring out some technological and practical challenges. More particularly, the battery range and the power supply at charging points may constitute significant factors to be considered in the global system design process including electric cars. The relatively limited autonomy of currently available electric cars constraint the vehicles to stay in station to be recharged. The charging time depending on the power supply granted in stations, recharging a vehicle can make it unavailable for a long time (6 hours to fully recharge a 22 kWh battery).

We recall in this chapter the main results obtained in this thesis with respect to the above mentioned problems. Both theoretical and industrial contributions are summarized. Some perspectives and future work are finally discussed.

Results and contributions

Mathematical models for carsharing system design

Linear programming is an intuitive approach often used in the literature to deal with carsharing system design. Whether to evaluate the system performance, sizing different components such as the number of vehicles or even to find accurate station locations, many studies report on a system modelling based on Time Expanded Graphs (TEG). Indeed, since carsharing systems are strongly time-dependant (users' requests, travel times, electric recharge, vehicle relocation operations, etc.), models may account somehow for their temporal evolution during the day.

Carsharing TEGs are directed weighted graphs where nodes and arcs stand respectively for carsharing stations and vehicle operations. Nodes are duplicated over a set of discrete time-steps, expanding the original network in the time dimension. Arcs describe temporal linkage between nodes (carsharing stations) and are classified into three categories according to the nature of the operation. The list includes stock arcs (when vehicles are parked in station), demand arcs (when vehicles are used to satisfy a request) and relocation arcs (when vehicles are relocated by a jockey). Considering those operations led to the fact that at any time, each vehicle is either parked in a station or in transit between two stations. Arc weights denote maximal station capacities (i.e. maximum number of parking places) on stock arcs and number of requests on demand arcs. Finally, note that considering a representative period of time makes the graph highly cyclical. Indeed, the resulting arrival time of any operation is calculated modulo the global time period. In practice, when an operation starts near the end of the day, it terminates early in the morning. Required inputs to build such TEG are temporal sets of carsharing demands, travel times between stations and vehicles relocation strategies.

Based on the TEGs representation of carsharing systems, Chapter 3 presented an Integer Linear Programming model (ILP) dealing with the [sdp]. The model considers integer flow variables over arcs accounting for vehicle flows moving in the system. The objective is to find a flow passing through the maximum number of demand arcs. Classical flow constraints (flow conservation on nodes and flow capacities on arcs) ensure the flow feasibility. Additional constraints limits the total number of vehicles relocation operations, jockeys and vehicles.

The optimal system dimensioning can then be deduced from any feasible solution. The resulting flow can be interpreted as vehicle routes, i.e. vehicle itineraries, since every unitary cycle flow represents a single vehicle moving though the system (see. Theorem 1, page 43). Looking at the maximum flow transiting in a station over time allow to deduce the minimum number of required parking places in this particular site. Finally, the total number of vehicles can be recovered from the flows passing though temporal cuts (see. Theorem 2, page 44).

Dealing with the [slp] in Chapter 5 led to enhanced the ILP model with additional variables. For this problem, instead of carsharing stations, nodes in the TEG stand for potential carsharing sites. Decisional boolean variables associated with each site indicate its operational status (selected or not selected). Dedicated constraints control the inner and outer flow at nodes so that vehicles can park or pass through stations if and only if the corresponding site is selected. Finally adding a specific constraint under the maximum number of opened sites complete the linear model. The latter produces the same outputs that the previous one and provides additional information about the opened sub-set of stations allowing the system to capture the highest number of demands.

We have seen in a dedicated part that including energy components was not possible with the current TEG. Because flows are not unitary, the interpretation of an optimal solution as a set of unitary cycles can lead to multiple possibilities. Besides, since energetic components are not considered in the ILP, there is no guaranty that the interpretation asserts the induced constraints. As a consequence, we presented in Section (5.3.3.1) a graph transformation supporting unitary flows. The ILP model is also enhanced with an additional group of decisional variables, referred as flow affectation variables, which report the direction (i.e. the upcoming arc) taken by the flow at each node of the TEG. We show that their number can be significantly reduced identifying symmetrical situations. Finally, additional costs on arcs account for the energy consumption it takes to perform the related operation. For demand or vehicle relocation arcs, the consumption is the travel distance (penalized during traffic peaks) whereas for stock arcs the negative value (negatived cost) represents the number of kilometres the battery can be recharged during one time-step. For each arcs, a dedicated variable tracks the remaining battery level of the flow passing by before the operation.

Experimental observations

According to the size of the problem, running ILP models to achieve good system configurations can take quite a long time. In our flow-based approach, the number of variables is related to the TEG density, i.e. the total number of arcs. Controlling it is fundamental to achieve real size and relevant instances of the problem.

We have seen in Chapter 3 that this density depends on three parameters: the number of stations, the number of time-steps, and the vehicle relocation strategy. Among these three factors, the number of vehicle relocation arcs plays a major role. Considering possible relocation operations at any time lead to generate TEGs where relocation arcs represent almost 98% of the global graph density. Experimental results show that a good level of the demand satisfaction can be still achieve applying vehicle relocation operations at wider time intervals, e.g. every hours. Those relocation scenarios allow to drastically reduce both graph densities and computation times while keeping a good level of service.

Introducing energy components was a tough challenge. In Chapter 6 we evaluated the [energy] MIP model on a realistic scenario based on 15 stations and 30 vehicles. Assuming electric cars with an autonomy range of 160 kilometres and charging points power supply of 3,7 kW, we observed that a half battery capacity is sufficient to achieve the highest demand satisfaction level. This residual capacity opens many perspectives and we suggested many practical benefits. For car manufacturers interesting in vehicle design for carsharing usage, it may represents significant financial savings since battery' prices still represent an important part of the global electric vehicle price. Also, the highlighted overcapacity of electric batteries brings out other advantages more oriented to the efficiency and the optimization of the whole system. Practical applications include better battery lifespan, additional energy supply to improve consumption peak curtailments and a better flexibility at managing the energy for the system itself.

Random data generator

Dealing with the lack of data is currently a critical issue. On the one hand, today's operating systems do not shared their data or open them to the community. At this time, only sporadic and limited data is available, even for research purposes. In addition, reported data (often press releases) concern the physical description of the system (number and location of stations, number of vehicles, etc.) or global statistics about operational indicators, such as the average number of requests a vehicle satisfies during a day and its average time spent on road. Neither the users daily requests, nor the detailed vehicles relocation operations are today available.

On the other hand, the actual research on demand modelling and demand estimation is not enough accurate to predict and anticipate the observed patterns in urban contexts. Numerous incentives at determining the modal part of carsharing among the global transportation demand have been carried out but in practice, their usage admits some hard limitations. Often context specific or neglecting the structural configuration of the systems (which is known to slightly influence the demand), advanced studies have not yet succeed to come up with models that accurately estimate a real carsharing demand.

In order to test and evaluate the different mathematical models, we developed and released an open-source software designed to randomly generate data for one-way carsharing systems [Carlier, 2015]. The tool positions a set of carsharing stations over a configurable territory, and generates temporal demands over the system with respect to a global demand profile. Over the day, the mobility pattern emulates a centroid configuration where most of the morning demands are oriented to the center of the city, whereas the opposite phenomenon is observed in the evening. The generator also produces travel times based on inter-station distances and an average vehicle speed. Note that they are penalized for settable pick hours (morning and evening) in order to handle and reproduce travel conditions during traffic congestion. More details are given in Chapter 2, page 21.

Industrial decision support tool

As an active actor of the numerical transformation, the IRT SystemX develops and deploys innovative services dedicated to both academic and industrial actors. In the domain of transportation and mobility, industrial challenges includes the conception of suitable transportation models at different scales, the design of modular and re-usable architectures and the develop- The mathematical linear models presented along this thesis have been implemented and integrated into this platform. As a Java Application Programming Interface (API), the tool provides functionalities and routines to build and resolve any instance of carsharing problems addressed in this manuscript. Dedicated methods allow to specify and set various problem parameters (as inputs of the problem) including upper bounds for the number of vehicles, jockeys, station capacities, vehicle relocation operations, station locations as well as carsharing demands, temporal set definition and relocation strategies. The tool also offers the possibility to produce realistic data using the random generator for one-way carsharing demand presented previously. In addition, its integration within a multi-modal demand estimation software allow to recover real data processed from mobility surveys. Although still under development, this specific part of the platform aims to extract the timestamped carsharing demand (O/D temporal matrices) from macroscopic transportation flows, providing valuable data for the carsharing application.

In practice, the carsharing API is supported by graphical interfaces which facilitate the program usage. Temporal data can be apprehended and examined through coloured maps, charts and global indicators reflecting the dynamics of the system. Outputs and results of an optimization can also be visualized in detail. Especially the vehicles itineraries and the stations' energetic consumption profile can be displayed over time. Figures 7.1 and 7.2 illustrate some graphical frames provided by the tool. Both depicted a specific carsharing use-case on the city of Paris. Figure 7.1 represents the global demand over the different districts of the city whereas Figure 7.2 shows the results of an optimization with the proportion of satisfied demands over the territory.

Perspectives

In this thesis, we addressed strategical aspects of carsharing system design problem. To come up with relevant results, the model must be set up with realistic data and deals with real size instances. Unfortunately, as said before, neither real carsharing data nor accurate estimation demand models for carsharing demand that are not context-specific and applicable for one-way travels are yet available. Hence, we believe that significant efforts in this direction may result in more valuable and accurate analysis. The random data generator as well as the software integration of the carsharing module into the estimation demand tool has been achieve in that sense and several studies are currently ongoing.

From a theoretical point of view, the [sdp] problem complexity remains unknown. Despite the fact that a polynomial sub-case has been exhibited in Chapter 3 and that the problem presents many similarities with a max-flow formulation, its exact definition does not fit with standard flow problems description. The closer formulation seems to be the one of the circulation problem where there is no sources, no sinks and attempt to find a feasible flow in the graph [Ahuja et al., 1993]. As far as we know, the objective to maximize the flow passing through a specific subset of arcs (in our case the set of carsharing demand arcs) does not exist in the literature.

With respect to the mathematical approach using linear programming, some limitations about solver capabilities have been observed and experienced in practice. Clearly, solving times depend on the available computing power and the size of the carsharing system you chose to design. The inclusion of the energy for instance requires much more memory (the TEG is larger) and generates higher solving times since the resulting problem induced more decisions. Basically, the [sdp] model can solve instances with 100 stations and 5 minutes times steps whereas [energy] model has difficulties to accept instances exceeding 20 stations and 20 minutes times steps within reasonable time. Most of the time, combinatorial issues make the solver unable to converge. Improving the heuristic proposed in Chapter 5 may help to initialise and start the exact searching method with a feasible solution. Moreover, since the solver is using a Branch-And-Cut method to deal with MIP problems, propose better node evaluations during the searching routine can be a promising feature.

2. 1

 1 Main frame of the generator. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Demand profile over the day. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 An example of a generator output producing 50 stations and 500 demands over a typical weekday. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 The TEG's node configuration. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Stock arcs in the TEG for a single station. . . . . . . . . . . . . . . . . . . . . . . 3.3 Graph representation of two demand arcs a 1 and a 2 between two stations. . . . . 3.4 Demand arcs in the TEG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 A complete TEG illustration. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 An arc transformation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.1 A coloured layer 3-dimensional Pareto frontier for a particular instance with 10 stations and 500 demands. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Similar curve shape for TEG densities (a) and GLPK building times (b). . . . . . 5.1 Different flow interpretations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 TEG transformation to support energy components. . . . . . . . . . . . . . . . . 5.3 Flow conservation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 A case of symmetry. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Illustrating the modified Dijkstra's algorithm considering energy constraints. . . 6.1 Global demand repartition between satisfied and unsatisfied demands over time according to the optimal solution based on 200 daily demands. . . . . . . . . . . 6.2 Vehicles repartition with respect to the distance covered and the time spent on road. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Vehicle repartition according to their observed battery range (difference between the largest and smallest level) and the number of satisfied requests during the day. 6.4 Energy profile of a specific vehicle during the day in relation to the electricity price variation in France (November, 10th 2015). . . . . . . . . . . . . . . . . . . 6.5 Vehicle repartition according to the observed battery range and the number of satisfied demands. Results are based on the 400-demands scenario solution. . . . 7.1 Graphical visualisation of carsharing data over the city of Paris. . . . . . . . . . . 7.2 Graphical visualisation of an optimal solution. . . . . . . . . . . . . . . . . . . . . List of Tables 4.1 GLPK computation times in seconds for small instances. . . . . . . . . . . . . . . 4.2 Generation time in seconds obtained with GLPK according to the problem's size (number of stations and times-steps). . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Graph densities according to the problem's size (number of stations and timessteps). In each cell, the above number stands for the number of nodes while the bellow one stands for the number of arcs. . . . . . . . . . . . . . . . . . . . . . . 4.4 Generation time depending on the size of the graph CPLEX (in milliseconds) . . 4.5 Graph densities according to vehicle relocation strategies. . . . . . . . . . . . . . 4.6 Solver computation times (in milliseconds) and optimal gap values compared to the baseline situation in both LP and ILP versions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Research scope and thesis organization . . . . . . . . . . . . . . . . . Bibliography of chapter 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Figure 2 . 1 -

 21 Figure 2.1 -Main frame of the generator.

Figure 2 . 2 -

 22 Figure 2.2 -Demand profile over the day.

Figure 2 .

 2 Figure 2.3 gives an example of an instance generated for 50 stations and 500 demands over the day.

Figure 2 . 3 -

 23 Figure 2.3 -An example of a generator output producing 50 stations and 500 demands over a typical weekday.

[

  Jorge and Correia, 2013] [START_REF] Correia | Carsharing systems demand estimation and defined operations: a literature review[END_REF]. Carsharing systems demand estimation and defined operations: a literature review. EJTIR, 13(3):201-220.[[START_REF] Kek | Relocation simulation model for multiple-station shared-use vehicle systems[END_REF][START_REF] Kek | Relocation simulation model for multiple-station shared-use vehicle systems[END_REF]. Relocation simulation model for multiple-station shared-use vehicle systems. Transportation Research Record: Journal of the Transportation Research Board, 1986(1):81-88. [Kek et al., 2009] Kek, A. G., Cheu, R. L., Meng, Q., and Fung, C. H. (2009). A decision support system for vehicle relocation operations in carsharing systems. Transportation Research Part E: Logistics and Transportation Review, 45(1):149-158. : problem description . . . . . . . . . . . . . . . . . . . . 34 3.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.3 Mathematical model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.3.1 Formal problem statements . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.3.2 Time Expanded Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.3.3 Flows and decision variables . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.3.4 Solution and objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.3.5 Mathematical program . . . . . . . . . . . . . . . . . . . . . . . . . .

  7) Equation (3.6) ensures that nodes x and y model the same carsharing station whereas equation (3.7) expresses the consecutive time-step relation between those station states.

Figure 3 .

 3 Figure 3.2 illustrates a single station over time where parking a vehicle is model with stock arcs. Note here that an arc exists between node 1(T) and 1(1). In our model, time-steps number T and 1 are considered as consecutive. The total number of arc in A 1 is exactly the number of nodes in the graph, i.e. |A 1 | = |X | = S × T, since every node in G have a unique adjacent stock arc in A 1 .

Figure 3

 3 Figure 3.3 -Graph representation of two demand arcs a 1 and a 2 between two stations.

Figure 3

 3 Figure 3.5 illustrates a complete TEG configuration with S stations, T time-steps and R = T .

Figure 3

 3 Figure 3.5 -Complete TEG with S stations and T time-steps. Maximum capacities for stations 1 and S are respectively 8 and 4. The two demands are the same as those in figure (3.3)(1.3).

  and thus θ(y) + a • T > T. As θ(y) ≤ T, we necessarily have a = 1 and thus a ∈ B(c). Now, by Lemma 1, |C T (c)| = a∈c a = (c) T , the lemma. Theorem 1 Any feasible solution ϕ can be decomposed into a set of circuits S such that, for any arc a ∈ A, ϕ(a) = c∈S ϕ c (a). Chapter 3 : The System Dimensioning Problem Proof. The proof is by recurrence on n(ϕ) = a∈A ϕ(a). The theorem is trivially true if n(ϕ) = 0.

Theorem 2

 2 The minimum number of vehicles required for a feasible flow ϕ equals a∈A ϕ(a) • a .

  Theorem 1, ϕ(a) = c∈S ϕ c (a). Thus,

  (3.21) is the maximization of the total demand. Equation (3.22) expresses the bound on the total number of relocation. Equation (3.23) expresses these on the total number of vehicles. Equations (3.24), (3.25) and (3.26) are lastly flow constraints. The total number of equations is around 2|A| + S × T = Θ(S 2 • T).

Figure 3 . 6 -

 36 Figure 3.6 -Transformation of an arc a = (x,y) ∈ A 2 into four arcs and two additional vertices s a and t a in G. The corresponding maximum capacities are set to u(a). Nodes s and t are unique and denote respectively the source and the sink nodes.

  t a ), (t a ,t ), (s , s a ), (s a ,y), ∀a = (x,y) ∈ A 2 }.3. Maximum capacity of arcs are w(a) = u(a) for a ∈ A 1 ∪ A 3 . Otherwise, for any arc a = (x,y) ∈ A 2 , w((x,t a )) = w((t a ,t )) = w((s , s a )) = w((s a ,y)) = u(a).

Figure 3 .

 3 Figure3.6 illustrates the graph transformation and focuses on the adding graph components for a specific carsharing demand arc a ∈ A 2 . Note that this transformation is a polynomial function and does not depend on the structure of G.

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 First experiments and scalability . . . . . . . . . . . . . . . . . . . . . 4.2.1 Experimental context . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.2 3-pareto fontier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.3 Scalability study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Working on relocation operations . . . . . . . . . . . . . . . . . . . . . 4.3.1 Experimental conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.2 Impacts on the TEG density . . . . . . . . . . . . . . . . . . . . . . . . 4.3.3 Solver computation times . . . . . . . . . . . . . . . . . . . . . . . . . .

  440 nodes, and • |A| = S • T + D + |R| • S • (S -1) = (10 • 144) + 500 + (144 • 10 • 9) = 14,900 arcs. This value is actually an upper-bound of the number of arc since D is interpreted by the generator as a∈A 2 u(a), which potentially lead to the situation where |A 2 | < D.

Figure 4

 4 Figure 4.1 -A coloured layer 3-dimensional Pareto frontier for a particular instance with 10 stations and 500 demands.

Figure 4

 4 Figure 4.2 -Similar curve shape for TEG densities (a) and GLPK building times (b).

  work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.2 Problem modelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.3 Mathematical program . . . . . . . . . . . . . . . . . . . . . . . . . . . . work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3.2 Selected energy components and modelling issues . . . . . . . . . . . . . 5.3.3 Mathematical program . . . . . . . . . . . . . . . . . . . . . . . . . . . . statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4.2 Removing the symmetries . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4.3 A greedy heuristic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Bibliography of chapter 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

trasformationFigure 5

 5 Figure 5.2 -TEG transformation to support energy components.

  Figure 5.3 -Flow conservation.

Figure 5

 5 Figure 5.4 -A case of symmetry.

Algorithm 1 :

 1 Modified Dijkstra's algorithm;Input: G = (X , A, e), a binary weighted TEG where weights are set to 0 on demands arcs and 1 elsewhere; t ∈ T defining X t = {x ∈ X | θ(x) = t}, a set of departure nodes. Output: C: a set of vehicles' routes verifying energy constraints.C ← ∅; while X t = ∅ do // Initialisation pick s ∈ X t ; S ← ∅and S ← X ; d(x) ← +∞ and e(x) ← -∞, for each node x ∈ S; foreach j ∈ Γ + (s) do d(j) ← w sj ; e(j) ← max{E, e(s) -γ sj }; pred(j) ← s; end // Cycle search routine while S = ∅ and d(s) = min{d j : j ∈ S} do let i ∈ S be the node for which d(i) = min{d j : j ∈ S}; S ← S ∪ {i}; S ← S -{i}; foreach j ∈ Γ + (i) do if d(j) > d(i) + w ij and e(j) < max{E, e(i) -γ ij } then // update distance and energy d(j) ← d(i) + w ij ; e(j) ← max{E, e(i) -γ ij }; pred(j) ← i; the cycle and update sets before iterate cycle(s) ← the shortest cycle given by the directed out-tree; if A 2 ∩ cycle(s) = ∅ and e(s) ≥ 0 then A ← A -{cycle(s)};

Figure 5

 5 Figure 5.5 -Illustrating the modified Dijkstra's algorithm considering energy constraints.

Figure 6 . 1 -

 61 Figure 6.1 -Global demand repartition between satisfied and unsatisfied demands over time according to the optimal solution based on 200 daily demands.

Figure 6 . 2 -

 62 Figure 6.2 -Vehicles repartition with respect to the distance covered and the time spent on road.

  Figure 6.3 -Vehicle repartition according to their observed battery range (difference between the largest and smallest level) and the number of satisfied requests during the day.

Figure 6 . 4 -Figure 6 . 5 -

 6465 Figure 6.4 -Energy profile of a specific vehicle during the day in relation to the electricity price variation in France (November, 10th 2015).

Figure 7 . 1 -

 71 Figure 7.1 -Graphical visualisation of carsharing data over the city of Paris.

Figure 7 . 2 -

 72 Figure 7.2 -Graphical visualisation of an optimal solution.

  [START_REF] Cohen | Carsharing: A guide for local planners[END_REF]. Carsharing: A guide for local planners. Institute of Transportation Studies.[Cordier, 2012] Cordier, B. (2012). Le coût réel de la voiture en 2012. ADETEC -Bureau d'études en Transports et Déplacements. [Correia and Viegas, 2011] Correia, G. and Viegas, J. M. (2011). Carpooling and carpool clubs: Clarifying concepts and assessing value enhancement possibilities through a stated preference web survey in lisbon, portugal. Transportation Research Part A: Policy and Practice, 45(2):81-90.

[START_REF] Costain | Synopsis of users' behaviour of a carsharing program: A case study in toronto[END_REF][START_REF] Costain | Synopsis of users' behaviour of a carsharing program: A case study in toronto[END_REF]

. Synopsis of users' behaviour of a carsharing program: A case study in toronto. Transportation Research Part A: Policy and Practice, 46(3):421-434. [Cousins, 2000] Cousins, S. (2000). Theory, benchmarking, barriers to carsharing: An alternative vision and history. Journal of World Transport Policy and Practice: Carsharing 2000-Sustainable Transport's Missing Link, pages 44-52. [Danielis et al., 2015] Danielis, R., Rotaris, L., Rusich, A., Valeri, E., and others (2015). The potential demand for carsharing from university students: an Italian case study. In Working paper of SIET 2015. [Efthymiou et al., 2012] Efthymiou, D., Antoniou, C., and Waddell, P. (2012). Which factors affect the willingness to join vehicle sharing systems? evidence from young greek drivers. In Transportation Research Board 91st Annual Meeting, number 12-1076, Washington, DC.

Table 4 .

 4 1 -GLPK computation times in seconds for small instances.

Table 4 .

 4 2 -Generation time in seconds obtained with GLPK according to the problem's size (number of stations and times-steps).

	H H T	H	H H H S	10	20	30	40	50
						138	147	310
		72	14	59
						≈ 2 30	≈ 3	≈ 5
					234	343	632	1437
	144	53
					≈ 4	≈ 5 30	≈ 10 30	≈ 24
				211	997	1417	2481	4735
	288
				≈ 2 30	≈ 16 30	≈ 23 30	≈ 41 30	≈ 1h20
	H H T	H	H H H S	10	20	30	40	50
				|X | = 720	1,440	2,160	2,880	3,600
		72
				|A| = 7,700	29,300	65,300	115,700	180,500
				1,440	2,880	4,320	5,760	7,200
	144
				14,900	58,100	130,100	230,900	360,500
				2,880	5,760	8,640	11,520	14,400
	288
				29,300	115,700	259,700	461,300	720,500

Table 4 .

 4

	solution within 1 30 minute, while the number of arcs stands around 700,000. Moreover, this
	linear relation is consolidated by the correlation coefficient (Pearson product-moment correlation
	coefficient) between GLPK generation time and the number of arcs in the graph standing at
	95,9%. This result can be easily noticeable in

3 -Graph densities according to the problem's size (number of stations and times-steps). In each cell, the above number stands for the number of nodes while the bellow one stands for the number of arcs.

Table 4 .

 4

4 -Generation time depending on the size of the graph CPLEX (in milliseconds)

Table 4 .

 4 5 -Graph densities according to vehicle relocation strategies.

Table 4 .

 4

6 -Solver computation times (in milliseconds) and optimal gap values compared to the baseline situation in both LP and ILP versions.

Chapter 7 Conclusion Contents 7.1 Addressed problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Results and contributions . . . . . . . . . . . . . . . . . . . . . . . . .

  7.2.1 Mathematical models for carsharing system design . . . . . . . . . . . . 7.2.2 Experimental observations . . . . . . . . . . . . . . . . . . . . . . . . . .

7.2.3 Random data generator . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2.4 Industrial decision support tool . . . . . . . . . . . . . . . . . . . . . . . 7.3 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Bibliography of chapter 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Another study conducted by[START_REF] Ciari | Estimation of carsharing demand using an activity-based microsimulation approach: Model discussion and some results[END_REF] uses an activity-based microsimulation model to estimate travel demand. The authors also try to understand the effects of a carsharing system on urban mobility, considering others transportation modes such as public transport, car, bicycle and walking. They suggested and evaluated a carsharing demand model using an open-source activity-based multi-agent simulator called MATSim[MATSim, 2015]. The framework simulates the daily life of individuals (agents) and produces travel demand as a side product. The system process iteratively computes transportation plans and traffic flow simulations until a relaxed state is reach. A transportation plan is a list of transportation modes deduced from a user activity-chain. Activities planned during the day by a user are selected with respect to its socio-demographic attributes. An aggregated cost function (including carsharing as a transportation mode in itself) returns a score, evaluating quantitatively the plans of each user. The agents continuously try to improve their score varying their departure time, transport modes, routes and location of some activities.The authors led to a modal split model giving plausible results in comparison with real data -the urban area of Zurich, Switzerland. According to the access to the cars and the time dependent fee structure, the model captures the proportion of the total transportation demand that could use carsharing. Although they observed general pattern of mobility at macro-scale, the authors also pointed out that results are context specific and computationally intensive.Actually, in most cases, studies are context specific. Trip patterns and travel behaviour can be different from one country to another since it is related to local and regional characteristics (culture, habits, etc.), making the standardization more complex. Furthermore, carsharing demand estimation has not so far been addressed in the literature for one-way carsharing systems, and a relevant model for such models is nowadays not available[Jorge and Correia, 2013]. This

Optimal design of a one-way carsharing system.Aurélien CARLIER

Remerciements

Bibliography of chapter 3 [Ahuja et al., 1993] Ahuja, R. K., Magnanti, T. L., and Orlin, J. B. (1993). Network flows: theory, algorithms, and applications. Prentice Hall, Englewood Cliffs, N.J.

[ Barrios, 2012] [START_REF] Barrios | On the performance of flexible carsharing: A simulationbased approach[END_REF]. On the performance of flexible carsharing: A simulationbased approach.

[ Correia and Antunes, 2012] [ Li, 2011[START_REF] Li | Design and analysis of a car sharing system offering one-way journeys[END_REF]. Design and analysis of a car sharing system offering one-way journeys.

Master's thesis, University of Wisconsin-Milwaukee. (employees of the carsharing operator). We refer to J ∈ N as the number of jockeys allowing to relocate vehicles at the same time.

Related work

Clearly, the performance of a station-based carsharing system is highly dependent on its station locations. Determining the suitable places where vehicles will be available is probably a key factor of its success. To the best of our knowledge, very few studies have been conducted on this particular topic.

[ Ion et al., 2009] proposed a dedicated multi-criteria analysis taking into account demographic economic indicators to extend an existing carsharing service located in La Rochelle, France. Each potential station site is evaluated with a score depending on the preferences of people living in the proximity area and calibrated from a real user survey using fuzzy logic. The authors stated that the resulted classification can be used in complement with the knowledge of specialists to help decision makers (urban planners, local authorities) not only for carsharing systems but also for bus station locations or bike-sharing services.

A recent study conducted by Correia and Antunes [Correia and Antunes, 2012] in 2012, inspired by [Fan et al., 2008], proposed three MIP models to find the convenient choice of locations, number and size of stations with respect to different operating schemes. The objective was to maximize the operator profit taking into account all the revenues (price paid by clients) and costs involved (vehicle depreciation, vehicle maintenance and parking maintenance). Applied on the city of Lisbon, Portugal, the results showed that the model where the carsharing operator has full control over trip selection is the one which yield the maximum profit. This was expected since it was the scheme offering the most freedom. The authors concluded that satisfying all the demand does not make sense economically and lead to severe financial looses for the private operator, even when customer trips are charged with a high price. Indeed, to reach this level of service the operator need to increase drastically its fleet size and consequently most vehicles stay idle (parked in station) during a large part of the day. As a consequence, the trip selection ability (i.e. the possibility to accept or refuse a request) seems to be crucial to achieve positive profits. Last, but not least, the authors also proved that the planning of stations location is intuitively dependent on the existence or non-existence of relocation operations which could mitigate the effect of an uneven trip pattern and so allow the supply to expand.

In another publication, [Correia et al., 2014] reused their real data set of Lisbon, Portugal, to analyse the impact of a better user flexibility on the operator's profit. They observed that vehicles are used more often when more information is provided to the user about vehicle availability at different stations of the system. However, they also noticed that those better operational results came with a greater walking and total travel times.

In general, the problem of locating carsharing stations has been addressed through a system management perspective. and most approaches use a mathematical programming formulation. Distinctions are made on objectives and operational constraints. According to studies, some are economically oriented trying to maximize the operator revenue or minimize global costs whereas others are more oriented toward the user satisfaction maximizing the service level. The overall system optimization is generally limited by budget constraints and system dynamics such as vehicle relocation operations and parking places in each station locations. Schematically, the problem is viewed through two perspective: minimizing global costs while satisfying all the demand, and maximizing the service level under budget constraints.