Keywords: Carsharing, Multi-Objective Optimization, ILP, Greedy Search, Memetic algorithm

Acknowledgment

Firstly, I would like to express my deepest sincere gratitude to my advisor Prof. Alexandre Caminada for the continuous support of my Ph.D study, from the early beginning until the last moment. Thank you for your patience, motivation, expertise and immense knowledge.

Your guidance helped me throughout the entire time of research and writing of this thesis.

I have learned a lot from you on both personal and professional level. I could not imagine having a better advisor and mentor for my Ph.D study.

My sincere thanks also goes to my co-advisors, Dr. Laurent Moalic for his valuable advices and the long discussions that inspired my research with brilliant ideas and new perspectives. Also, to Dr. Mohamad Dib, who expressed great trust in my skills from the beginning and always supported, and motivated me during the research years. Without their precious support, it would not be possible to conduct this research.

A special thanks to Dr. Raed Kouta who motivated and encouraged me all the time and who inspired me to add a new perspective to my thesis.

Besides my advisors, I would like to thank the rest of my thesis committee: Prof. Laetitia Jourdan, Prof. Fabien Leurent, Prof. Mohamad Khalil and Prof. Michel Basset, for their insightful comments and encouragement, but also for the wonderful questions that motivated me to widen my research from various perspectives. I am also grateful to the president of the Lebanese French University (ULF) Dr. Mohamad Salhab who supported my research and was always beside me to obtain my PhD. I also cannot forget the dean of the Lebanese French University Dr. Ahmad Rafhi who believed in me, supported and motivated me to pursue my research studies.

A special thanks goes to AUF (Agence Universitaire de la Francophonie) for the Mobility Scholarship that they offered to me during my three years of research. Their financial support facilitated my stay in France and allowed me to be in longer contact with the v vi French experts, which added a great value to my thesis.

I also thank my fellow labmates for the great discussions, for the sleepless nights we were working together, and for all the fun we have had during research studies. Also, I thank my colleagues in the computer science department who made my stay in France feel like home. In addition, I thank my colleagues in the Lebanese French University, their support was a great motivation for me.

I thank Ahlam Elsarraj for her precious help and I am also thankful to everybody who supported me and motivated me during my research.

Thank you Fadila Khawli, for all your love and support.

Last but not the least, I would like to thank my amazing family: my parents, my brothers and my sisters for supporting me spiritually throughout writing this thesis and my life in general, I undoubtedly could not have done this without you.

Introduction N owadays, cars are at the core of environmental concerns due to their significant contribution to the environmental problems that affect our globe. Most of the major cities worldwide suffer from congestion, vehicles emissions, lack of parking spaces and noise pollution. Over the last few years, cities have started to think differently about private car usage and have provided new solutions that reduce car ownership while simultaneously offering private car advantages. For instance, the concept of carsharing service is one of these solutions that can contribute positively to solve these problems.

In this chapter, we start by introducing the carsharing concept as an innovative mobility service starting from 1948 when it appeared for the first time until its current situation in 2015. Then we describe the three carsharing models and how they work. After that, the benefits and impacts of carsharing are presented. In the related research section we provide an overview of the different research topics that are related to carsharing. The last section of this chapter is dedicated to the summary.

1.1/ Context

It is straightforward that convenient transportation systems are crucial for supporting the economic development of cities [START_REF] Reno | Economic impact of public transportation investment[END_REF], [START_REF] Rodrigue | The geography of transport systems[END_REF]. Generally, people in urban areas commute using different modes of transportation such as public transport buses, trains, taxis, private cars, bikes, etc. Private cars are more attractive to users for their high flexibility and comfort. However, the increasing number of private cars has serious consequences related to environmental issues, traffic and parking congestion [Katzev, 2003]. Then, numerous efforts have been made to motivate people to use more sustainable modes of transportation like biking, walking or the use of public transportation facilities when possible. In June 2007, the launch of Vélib' in Paris was very successful. 20,000 self-service bikes were deployed over 1500 stations [Meunier, 2014].

Within the first year, the number of subscribed members exceeded 200,000 members and the bikes have been used 26 million times. The success of this system has motivated cities all over the world to adopt this idea of sharing vehicles, which includes carsharing, bikesharing and other vehicle sharing concepts. Carsharing is one of the innovative solutions that can contribute in promoting sustainable car use. Many studies stated that private cars spend most of their time parked, since many car owners use their cars occasionally. Thus, in this case, one shared car can replace many private owned ones. Carsharing offers on demand access for cars distributed in a defined urban area. Therefore, carsharing systems offer the benefits of owning a private car without actually having to buy it. Carsharing is based on the model of Pay As You Go service, so users do not have to afford all the fees of owning a car like insurance and maintenance, they just pay during the time they access the service as an alternative of ownership in a market shift as predicted in "the age of access" [Rifkin, 2000]. Usually, users of this kind of systems rent cars for short periods of time. It is a complementary solution for the existing public transportation facilities. It offers the comfort and flexibility of private cars and the reduced costs of public transportation. According to Navigant Research, global carsharing service revenues will grow up to US$6.2 billion by 2020 [Navigant Research, 2013]. This kind of system has been implemented since the end of forties in Europe [START_REF] Shaheen | A short history of carsharing in the 90's[END_REF]. However, they were not successful since it was not easy to monitor the system and protect it from vandalism.

Thanks to the advances in Information and Communications Technology (ICT), better facilitation, monitoring and management of reservations and payment operations of these systems have become available [START_REF] Jorge | Carsharing systems demand estimation and defined operations: a literature review[END_REF]. System operators and users are able to locate the stations and check the availability of vehicles in real time. In our study, we are dealing with one-way carsharing systems. Unlike round-trip carsharing systems, one-way carsharing systems allow users to take a car from a station and to drop it off in any other one. Although the one-way option makes the system more attractive to users, carsharing operators encounter difficulties in maintaining enough numbers of vehicles in stations to satisfy user demands. If stations are full, users who want to drop off their cars at the destination station cannot find a free parking place. On the other hand, user demands to take a car from empty stations will not be satisfied. When this imbalance problem occurs often, system users tend to lose interest in the idea of using the system since it is not reliable and available when they need it. Recently, vehicle-sharing systems have generated a great interest of research in its different majors to solve the problems that arise upon operating these systems. In this paper, we will focus on the problem of car relocation in order to meet user demands. In one-way carsharing systems, the relocation problem is technically more difficult then the relocation problem in bikesharing systems. In the latter, we can use a truck to move several bikes at the same time, while we cannot do this in carsharing system because of the size of cars and the difficulty of loading and unloading cars.

1.2/ Research scope

Defining station locations is an important strategic decision that plays an important role in the success of carsharing systems. The location of station should consider the user preferences as well as operator preferences. Several studies are presented for this topic; mathematical models, heuristics and simulation models are presented. The proposed mathematical models combine many objectives such as maximization of operator profit and demand satisfaction. In aggregated objective functions, a weight value is associated to each objective in order to obtain one fitness value for the model. The choice of the weights of each objective can be considered also as another optimization problem. However, the aggregated objective value can sometimes be misleading and cannot show all the possible solutions. In this context, [START_REF] Moalic | A multiobjective memetic algorithm for solving the carsharing problem[END_REF] have presented a multiobjective approach for locating stations in one-way carsharing systems. The study used three objectives to locate the stations based on the estimated users demands in order to maximize the satisfaction of users demands and minimize the imbalance of cars inventory at each station.

The question of optimal fleet size and model has also been the subject of many studies.

Making the good choice of fleet size can highly affect the level of service. Another, impor-tant topic that was studied is the optimal fleet distribution that contributes in maintaining a good level of service. Based on demand estimation and probabilities, some models were presented in order to determine the optimal fleet size that maximized the operator profit. Some proposed models used approximation methods to solve this problem. However, simplification hypotheses were often used to make the problem solving easier. Few analysis were found on the effect of fleet size, number of stations, number of parking spaces and the demand variation on the total number of rejected demands.

In the problem of cars relocation in one-way carsharing system, many studies showed the effect of relocation operations in increasing the level of service and decreasing waiting time. Different mathematical and simulation models were discussed. Several relocation tactics were suggested such as trip splitting and joining, dynamic price and offering alternative departure station or destination station based on the need of cars at the stations.

However, these tactics depend on user participation, which is not often guaranteed. Researchers have focused on the static cars relocation. During the night, the client activity can be neglected, which makes the relocation operations easier. However, during the day when the high demand activity occurs, cars relocation operation cannot disregard the dynamic demand variation and future potential demand. Logistic aspect of relocation operations that includes the staff size, relocation times and shifting time, seems to need more research, and this is the topic of our research work. Since mathematical models of carsharing networks cannot handle the growing size of networks, heuristics approaches for large networks are needed to provide good solutions in a reasonable time. Therefore we work on both single and multiobjective optimization problems, which refer to the mathematical formulation, data analysis and algorithms development.

1.3/ Organization of the thesis

In the second chapter, we present an overview on the state of the art for the carsharing.

We start by describing the carsharing models and their benefits on the individual and the environmental levels. Then we move to the related research. In this section we presented the different research papers that concern the demands forecasting, the station locations, the parameters that affect the carsharing performance and the relocation operations from an operator based and user based approaches. After that, we present a quick overview on the bikesharing related research. At the end of the chapter a synthesis for the chapter is offered.

In the third chapter, we present a physical and mathematical model for the relocation problem in one-way carsharing systems. The proposed model accounts for vehicle and staff rebalancing during each time of the day in order to minimize the number of rejected demands and the needed relocation operations. Then we present the mobility data used in the study. We present data analysis to study the effect of system parameters on the total number of rejected demands. To overcome the high computation time required by exact solvers, a heuristic approach is developed followed by a comparison between the results of CPLEX and greedy search. We also present a study of the stochastic demand variation of the relocation operations.

In the fourth chapter, we present a multiobjective local search approach for the relocation problem in one-way carsharing systems. We consider three objectives for the relocation problem, which include the minimization of the number of remaining rejected demands, the staff size and the total time needed to perform the relocation operations. The multiobjective approach allows the carsharing operators to discover different possibilities of relocation decisions through the Pareto front solutions. Therefore, decision makers can see the most convenient relocation staff allocation that is profitable for the system. Two algorithms are used to solve the problem: NSGA-II and a memetic algorithm, which is a combination of NSGA-II and a local search. The approach is validated through many quality indicators to evaluate the quality of provided solutions.

At the end of the thesis, we provide conclusions and findings of the presented works, we finish by suggested perspectives, and future works.

State of the art

2.1/ Brief history of carsharing

In the following, we present the chronological evolution of carsharing systems since the early programs until the recent growth. Then we provide a description of the existing carsharing models and the benefits of this kind of mobility services. After that, we present an overview of related literature. At the end of this chapter we provide a summary for this chapter followed by a brief description of the next chapters.

2.1.1/ Early programs

The concept of carsharing has appeared for the first time through the "Sefage" cooperative program that started in Zurich, Switzerland in 1948 and served until 1998 [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 main motivation behind this idea was an economic reason [START_REF] Shaheen | Carsharing in europe and north american: past, present, and future[END_REF]]. The price of cars was not affordable for all. Hence, some individuals started to share vehicles between each other. Years after, several countries had initiated new carsharing experiments that stopped later. The list includes European programs such as Procotip in Montpelier, France (1971to 1973), Witkar in Amsterdam, Netherlands (1974to 1988), Green Cars in Great Britain (1977to 1984), Bilpoolen in Lund, Sweden (1976to 1979), Vivallabil in Orebro, Sweden (1983to 1998), and Bilkooperativ in Gothenburg, Sweden (1985to 1990) ( [Britton, 2000], [Van Winkel, 2012], [Cousins, 2000], [START_REF] Martin | Carsharing's impact on household vehicle holdings: results from a north american shared-use vehicle survey[END_REF]). The United States as well joined the list of countries that attempted carsharing experiments with dif-CHAPTER 2. STATE OF THE ART ferent programs such as the Mobility Enterprise program handled by researchers from Purdue University in West Lafayette, Indiana (1983Indiana ( to 1986)), "Short-Term Auto Rental Service (STAR)" was launched in San Francisco (1983Francisco ( to 1985) ) [START_REF] Shaheen | Carsharing in europe and north american: past, present, and future[END_REF].

First carsharing programs had different forms and used different technologies. For instance, Protocip, was the first project that started to use technology to let users pay for usage by distance using tokens for in-vehicle "meters" [Britton, 2000]. Shared electric cars appeared in Witkar project where electric car usage was limited to the city center.

The STAR project was established for the residents of large apartment complex. The aim of the Mobility Enterprise program was to promote fuel-efficient cars and to reduce car ownership. The project has also offered shared vehicles for special purposes such as large sedans and station wagons [Millard-Ball, 2005]. [START_REF] Shaheen | One-way carsharing's evolution and operator perspectives from the americas[END_REF] It is good to note that almost all these projects had failed and stopped a few years after their starting. This common failure has been associated with different causes. The list of possible reasons includes, organizational and planning, marketing and financial management, and technical and limited technology problems. Moreover, the restricted area of service and the lack of support from the local government can also be added to this list [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]], [Cousins, 2000].

Later, the experience acquired after the past carsharing experiences (table 2.1) combined with the advances in communication technology led to several successful carsharing programs such as Mobility Carsharing in Switzerland and stattauto in Germany (Berlin) in 1987 and 1988, respectively. The success of the concept of carsharing systems in Europe, has highly contributed to spreading the vehicle-sharing systems across the world.

2.1.2/ Recent Growth

Early carsharing programs were almost about demonstration projects that were established to study this new concept, the required technology and how people perceive this new mobility service. These first projects that started in Europe have made the idea of carsharing more popular and paved the way to permanent carsharing programs to take place in different countries across the world. Nowadays, carsharing systems exist in the five continents.

In the 1990s, professional carsharing started in North America and Asia then Australia A summary of the carsharing growth is provided in Figure 2.1 in [START_REF] Jung | [END_REF].

The estimated number of carsharing membership in October 2012 was 1,788,000 members sharing over 43,550 vehicles distributed over 27 countries in 5 continents. Carsharing members were mainly shared between North America (50.8%) and Europe (38.7%).

However, Europe has a better member-vehicle ratio with 47.0% of carsharing fleets while North America has 36.2% (shaheen and cohen 2012a).

A new estimation of carsharing members can be found in figure 2.1. We can clearly see that the carsharing membership in 2014 has exceeded the double membership in 2012. We have different carsharing models: [START_REF] Optymo | Auto libre-service[END_REF] Examples of large-scale carsharing companies include Zipcar, which is one of the largest carsharing companies in the world, Mobility (Switzerland), Car2go and Flinkster. In round-trip carsharing, users cannot leave the car in another station, which is not very convenient for some users. To make carsharing more flexible, some station-based carsharing companies offer one-way trips for their users. In this model, users can pick up a car from a station and leave it in any other station. For instance, Autolib' is an example of carsharing companies that offers one-way trips in Paris, France since 2011. In March 30 2015, Autolib' included 3239 electric cars distributed on 937 stations and 78648 mem-bers. Autolib' is considered as one of the largest one-way carsharing system in the world.

1. Station-based 2

2.2.2/ Free-floating carsharing

Unlike station-based carsharing systems, free-floating carsharing allows users to pick up and return their rented car to any legal parking space within a defined area. This kind of system is more convenient to users, since they do not have to stick to defined stations to park or to pick up a car. However, the convenient station-less strategy generates a problem of locating the cars. This problem is mitigated by using onboard tracking systems that allow users to locate cars through web and smartphone platforms or using a hotline service. In this model of carsharing, members cannot make a reservation in advance.

Reservation is limited to 15 or 30 minutes before picking up the car. Currently, we can find free-floating carsharing in many countries in Europe and North America. With its minute based pricing, free-floating carsharing services may be considered as the complement system to the existing station-based, when cars are used for short time.

2.2.3/ Peer-to-peer carsharing

Peer-to-peer carsharing (also known as person-to-person carsharing) is a model of nonprofessional car rental where individuals share their cars that are owned collectively or by one of them for short periods of time. Usually, in this model of private carsharing, car usage is covered by an insurance contract, which is in most cases mutually concluded between individuals. Unlike other carsharing models, peer-to-peer carsharing users have to exchange car keys in person. Generally, person-to-person carsharing users belongs to the same neighborhood between acquaintances or even it can be organized at regional or national level using web platforms as Tamyca and Autonetzer [START_REF] Gossen | Latest trends in car-sharing. Corpus-The SCP Knowledge Hub[END_REF].

2.3/ Benefits and impacts of carsharing

Carsharing can be considered as an innovative mobility service that has many benefits for individuals who use the service and for the environment as well. Carsharing is a new concept that separates the use of car from its ownership. Therefore, it is an attractive cost-saving solution for users that do not depend on private cars and use it occasionally.

2.3.1/ Individual benefits

Owning a private car grants its users the convenient of mobility whenever they want.

However, this convenience costs money and time. A car needs a parking, an insurance and maintenance operations periodically and other unexpected expenses. In general, there are two category of expenses related to car ownership:

1. Variable expenses that are dependent on the car use, such as fuel, maintenance, parking, etc.

2.

Fixed expenses that include the purchase price, insurance, etc. They constitute almost 60% of the total cost that should be paid regardless if the car owner uses the car or no. Nevertheless, most of private cars pass the most of their time parked.

In a city, that has a good public transportation network and where finding a parking spot is not easy, private car usage becomes occasional. Consequently, using carsharing instead is considered as a complementary affordable mobility solution that may replace the car ownership for some individuals. In carsharing, users pay just for the time they use the car.

By this way, fixed costs of owning a car are shared also between the users of the system and by the car operator.

It is good to note that carsharing is not always an economic solution in all the scenarios.

For instance, private car would be less expensive for an individual who highly depends on his car and has a high VKT (Vehicle Kilometers Traveled) since as much as VKT increase, the cost of the vehicle will decrease. Although it is not easy to determine a number of VKT from which private cars become economic for users, however some studies estimate that starting from ≈ 8,000 Km/year private car would be a better choice [Millard-Ball, 2005] as shown in figure 2.6 (VMT: Vehicle Miles Traveled), this value depends on the fixed and variable costs in each country. It complements the multi-modal mobility offer with its high flexibility and affordability.

This complementary criterion makes carsharing a good alternative to private car ownership since its users will have all the possibility to commute between the different modes of transportation based on their needs. By this way, individuals who intend to buy a new car will postpone or even drop the idea of buying a new car when they have a good alternative. Consequently, carsharing can contribute in mitigating the increase in the number of private cars [Loose, 2010]. Moreover, since carsharing shifts the fixed cost of owning a car to variable cost, users tend to reduce the unnecessary VKT to save money as they are fully aware of the real cost of each ride. Unlike private car owners who tend to use their car intensively even when it is not required, carsharing users tend to choose the best combination of the available public transportation. Therefore, since carsharing is motivating individuals to use public and non-motorized transport, it contributes in decreasing the private car ownership, congestion, parking space and even in decreasing transport related gas emissions [START_REF] Martin | The impact of carsharing on public transit and non-motorized travel: An exploration of north american carsharing survey data[END_REF].

2.4/ Related research

Recently, vehicle-sharing systems have generated a great interest of research in its different majors to solve the problems that arise upon operating these systems. In our study, we are concerned with one-way station based carsharing systems. Nevertheless, as described earlier there are free-floating carsharing systems that do not use stations (e.g. car2go).

Many problems related to the carsharing system operation have arisen upon their launch.

The main problem that we deal with it in this study is related to car imbalance in stations.

A high number of cars in a station means that arriving clients will not find a parking space;

however, an empty station prevents a client from using the system.

In the literature, researchers have dealt with this topic from different perspectives. Some papers have studied the impact of this new system on the urban mobility. Others are looking to find the best rates to apply on the system in an intelligent way that increases the carsharing operator profit. One more important question is how to model and estimate the demand. Demand modelling is a common studied problem in transportation fields.

A good demand modelling will help operations research specialists to solve other problems more efficiently. Operations research related problems include locating stations for a carsharing system, fleet management, and carsharing system growth.

The main problem that concerns our study is the cars relocation problem. How to maintain a good number of cars in each station at each time of the day. Unlike bikesharing systems, carsharing operators cannot use a truck to relocation cars for problems related to car's size and complicated logistics related to cars loading and unloading. Thus, carsharing operators recruit employees to relocate cars between stations. Cars relocation operations suggests many problems that should be studied:

1. What is the best number of employees that should be recruited?

2. How they should relocate cars between stations?

3. From which station to which station? In figure 2.8, we see the most common research topics that concern the carsharing systems.

In the following will try to make an overview over the different related research in the literature.

2.4.1/ Forecasting demands and attractiveness factors

Demand forecasting is one of the most important topics that allow carsharing operators to estimate user demands and therefore improve carsharing system availability. Therefore, understanding users' characteristics and who might use the system is one of the key factor for the success of carsharing. Many research papers use the average value of population characteristics based on a sample of carsharing users. However, other works refer to more advanced techniques to come up with better conclusions.

In his thesis, [KEK GEOK [START_REF] Kek Geok Hoon | Decision support tools for car sharing systems with flexible return time and stations[END_REF] [ [START_REF] Stillwater | Carsharing and the built environment: A gis-based study of one us operator[END_REF] studied the impact of built environment, neighborhood features and demographic factors on the use of carsharing vehicles over a period of 16 months for an urban carsharing operator in the United States. They used GIS-based multivariate regression to explain the average monthly hours of carsharing use. The results in this study confirmed that the demographic factors do not have direct impact on the success of carsharing locations. The authors also concluded that the most important factors that may affect positively on the carsharing use are the average age of the stations, the availability of light railway service only. As these factors get higher, the demand gets higher.

However, the percentage of households that have one vehicle, the percentage of drive-solo commuters, street width affects negatively the carsharing use: as these factors get higher, the demand gets lower.

In another study during the same year, [START_REF] Catalano | Car sharing demand estimation and urban transport demand modelling using stated preference techniques[END_REF] In a study that occurred in a university community, [START_REF] Zheng | Carsharing in a university community: Assessing potential demand and distinct market characteristics[END_REF] the resulting models were applied to predict the carsharing potential market share under varied conditions. The study concluded that the status of the individual at the university (e.g., student, staff, faculty member) had a high impact on his willingness to accept the carsharing: percentage of students that are willing to use the carsharing system is greater of the percentage of faculty members. The study also showed that other variables could contribute in the people decision-making. These variables include individual' income, vehicle ownership, the ease of access of the carsharing cars and people attitude towards transportation and environment.

In their study, [De Lorimier et al., 2013] The first type concerns the high frequency-users who were using the system for nearly 2.2 transaction per week (14% of the members). While the second type refers to the low-frequency users who were doing almost 0.4 weekly transactions (86% of the members). Based on the distance traveled, two main behaviors were observed: either urban distances during the week, or long distances one day of the week. Using the dominant cluster concept, authors revealed that almost 62% of the times members had similar usage weeks.

[ [START_REF] Ciari | Estimation of carsharing demand using an activity-based microsimulation approach: model discussion and some results[END_REF]] used an activity-based micro simulation model to estimate the potential of carsharing travel demand. They implemented their model using MATSim (Multi-Agent Transport Simulation) that has been adapted to model the carsharing mode. The simulation scenario concerned about 160000 agents in the urban area of Zurich, Switzerland.

The study was concerned only about the demand in the carsharing system regardless the number of available cars. A round-trip carsharing system has been considered for this study. Station are considered to always be able to satisfy the demand (no reservation was required since cars are always available). The results of the simulation were compatible with the reality under the chosen specification detail. Nonetheless, authors insisted on the necessity of adding further analysis and improving the model to add real carsharing characteristics to the simulation, especially the adding the capacity of the stations and the number of vehicles.

In order to analyze the carsharing activity persistency, [START_REF] Morency | Understanding members' carsharing (activity) persistency by using econometric model[END_REF] used a two-stage approach to estimate the probability that each member to be active in a month using a binary probit model. Then in the second stage, they estimated the probability of an active member to use the service multiple times per month (frequency of use), using a random utility-based model. The model was estimated using empirical 40 months of data from one of the largest carsharing company in North America. Results show that the activity persistency of members is positively influenced by their usage activity in the four previous months. This effect related to the previous months decreases over the time. On the other side, authors also stated that some attributes of the members (gender, age, and language spoken at home) could affect their behaviors.

2.4.2/ The performance of carsharing systems [Barrios, 2012] proposed an agent-based model to evaluate the level of service provided to users in a flexible carsharing system where cars can be dropped off in any eligible parking area. In this type of carsharing systems, users do not have to reserve a car in advance or drop the driven car to its origin location. Due to the disproportionate demand distribution spatially and temporally, some places tend to accumulate cars while others will not have any available car, which causes a logistic problem of cars redistribution in order to meet users demand. This study used the accessibility as the main measure of effectiveness. It refers to the proximity of users to an available car within a walking distance. Simulation results have been compared with the four real carsharing systems (car2go) that are operating in Austin, California, Texas and San Diego. The author concluded that the simulation model could serve as a tool for the decision makers in order to make planning decisions.

[ Matthew Petering, 2014] have developed a discrete event simulation model to analyze the performance of a one-way carsharing system. The study concerns a system that has a defined number of cars, stations with limited number of parking spaces and trips are assigned based on an online reservation system. The authors concluded based on five experiments, that there are many factors that affect the financial and the operational performance of the system. These factors include the number of vehicles, the number of parking spaces in each station, the number of parking spaces, the variation of demands on stations and the inclusion of the time required to park the car in the reservation sys-tem. The proposed simulation models can serve as important tools to assess the potential of carsharing systems under certain conditions. The decision makers can use these tools when the carsharing system is in a planning phase. However, these approaches did not discuss the problem of car relocation operations.

2.4.3/ Stations location

When a carsharing operator wants to create a new carsharing service, some strategic decisions have to be made at the very early stage of the construction. These decisions concern the station locations, size, fleet size, etc. A station location can be related to the estimation of the demand, which is affected by various parameters that reflect the attractiveness of a location such as socio-economic and geographic profile, the accessibility of this location and its other neighborhood transportation modes, etc. Choosing a good station location plays a crucial role in the success of a carsharing system. Several studies have dealt with this problem in order to choose the best station locations (references to be added). Nair et Miller-Hooks (2014) presented a model that is used to optimize the performance of one-way vehicle sharing systems. In order to maximize revenues, vehicle sharing operators aim to identify the optimal system configurations that include station locations, vehicles inventories, and station size. For this sake, the authors developed a bi-level mixed-integer program that guarantees the equilibrium design of a shared-vehicle system. The upper level concerns the possible operator decisions such as station locations, initial capacities, and the initial number of vehicles in stations. While the lower level is related to users' decisions that are represent the demand. Different tests were applied on random networks in order to determine the optimal network configurations. In this study, CPLEX was used to solve the problem. The authors stated that their study could be improved by using a variable demand.

Kumar et Bierlaire (2012) proposed a mathematical model to analyze the performance of a round-trip electric carsharing system and to identify the best locations for the service.

The authors aimed a two-fold objective; the first is to analyze the performance of the carsharing system at each station to extract the main factors that increase the attractiveness and therefore the demand, while the second is to use the found factors to choose future station locations in order to maximize system performance. The study took place in Nice,

France. The authors stated that the mathematic modelling should be supported by the local business knowledge and other real world intuition.

[ [START_REF] Moalic | A multiobjective memetic algorithm for solving the carsharing problem[END_REF] presented a multiobjective memetic algorithm for locating stations in a one-way carsharing system. The proposed method used a genetic algorithm combined with a local search to solve a multiobjective problem. The mobility data was built using GIS Shapefiles, survey data and socio-economical information collected by professionals in regional planning. The authors considered three objectives for locating the stations.

The first objective aims to maximize the mobility flow between stations, while the second objective is used to balance the input and output demand, and the last objective is to guarantee a uniform flow along the day. A platform has been developed as a simulation tool and for result analysis. The decision-making tool can reflect the mobility in spatial and time dimensions. The proposed approach showed a very good performance for the memetic algorithm in solving a multiobjective problem.

2.4.4/ Relocation operations in carsharing systems

In one-way carsharing system, users can pick up a car from a station and drop it in any other station. The number of available cars in each station will vary based on the departure and the arrival of cars from each station at each time of the day. The demand for taking or returning cars in each station is often asymmetric and is fluctuating during the day. Therefore, some stations will accumulate cars and will reach their maximum capacity preventing new arriving cars from finding a parking place. While other stations will become empty which lead to the rejection of new users demand to take a car. There are many research papers that have dealt with the problem of rebalancing cars over the stations in order to meet with users demands. Many strategies have been proposed and studied and tried to mitigate this problem. Some approaches concerned the rebalancing techniques; others were targeted to build models to the complex dynamics of one-way carsharing systems. to the imbalance problem. Based on preliminary results, the author concluded that the framework was able to model delays and simulate the essential dynamic behavior that is compatible with real systems. He also stated that the model still needed to be completed with more details and a fine-tuning for the parameters; the model has also to be compared with real data. Limitations of the studied approach are related to fact that system dynamics simplifies the real system behavior. Many aspects of the real system have been omitted such as relocation technique, new reservation requests, maintenance operations, etc., which could probably lead to exaggerated results.

As described earlier, one of the main problems of one-way carsharing operations is the vehicle imbalance problem. Due to uneven demand spatially and temporally, the cars quickly become disproportionally distributed. To mitigate this problem, cars need to be CHAPTER 2. STATE OF THE ART relocated in order to satisfy user demands. Many approaches are proposed in the literature for cars relocation operations some approaches are user based, others are operator based.

The characteristics of each approach will be discussed in the next sections.

2.4.5/ Operator based relocation operations [START_REF] Dror | Redistribution of selfservice electric cars: A case of pickup and delivery[END_REF]) presented a study for the relocation problem in one-way electric vehicle sharing system in Praxitele, France. The authors suggested a fleet of finite capacity to redistribute cars over the stations. The problem was modeled as pickup and delivery and formulated as a mixed integer programming. A heuristic approach A * was used to solve the problem.

[ [START_REF] Barth | Simulation model performance analysis of a multiple station shared vehicle system[END_REF]] developed a queuing-based discrete event simulation model to analyze the performance of multiple station carsharing system with one-way trips. Different scenarios were used to evaluate the system under different parameters that represent the travel demands for the different seasons. The study was applied on a resort community in Southern California. To assess the performance of the system, several measures of effectiveness were calculated focusing on the average waiting time and the number of required relocation operations to decrease the wait time. In this study, the authors concluded that the vehicle-to-trip ratio, the adopted relocation strategy and the charging scheme have a high impact on the system performance. They also presented a cost analysis that showed that carsharing systems could be very competitive with the existing transportation systems. In order to define the best combination of system parameters, the simulation model performs an impractical number of runs to try all the possible combinations. To overcome this problem, [START_REF] Kek | A decision support system for vehicle relocation operations in carsharing systems[END_REF] proposed a new approach that is based on the simulation model developed in [START_REF] Kek | Relocation simulation model for multiple-station shared-use vehicle systems[END_REF]. The authors developed a three-phase decision support system that helps the carsharing operator in choosing the best combination of system parameters that improves the performance of the system. During the first phase, which is called trend filter, an optimizer is used to find the lowest cost of resource allocation, based on system operating parameters and usage patterns as input. The optimizer is based on a mathematical model for the relocation problem. In the second phase, a series of heuristics are used to revise the schedule of the maintenance and relocation activities. In this phase, the trend optimizer suggests the recommended operating parameters such as shift hours, relocation thresholds, and number of employees. In the last phase, the recommended parameters are evaluated in the simulation model that is developed in [START_REF] Kek | Relocation simulation model for multiple-station shared-use vehicle systems[END_REF] to evaluate the performance of the system under the parameters obtained in phase two.

The set of recommended parameters suggested by the three-phase decision support system using again operational data from Honda ICVS, could lead to a 50% reduction in the staff cost, an improvement in the zero-vehicle time and full-port time and decrease in the number of relocations between 37.1% and 41.1%. This decision support system can assist carsharing operators in choosing the best system parameter combination that decrease operational cost and increase system level.

In 2010, Wang et al. developed a microscopic traffic simulation model for a dynamic car relocation in a carsharing system to forecast and improve the relocation operations. The study concerns a carsharing system in a highly populated suburban area in Singapore.

The model is composed of three components. The first component is a microscopic traffic CHAPTER 2. STATE OF THE ART simulation that models real traffic situations. While the second component is used for forecasting the demand using an aggregate approach. The forecasting model used the total number of cars picked off and returned to each station. The last component is responsible for the car relocation operations. The results showed that is possible to improve the system performance. However, the system consisted of only four stations with twelve cars each, which is smaller than the most of carsharing operators.

In their work, [START_REF] Cucu | Management of a public transportation service: carsharing service[END_REF] proposed a new approach to help decision makers to maintain a balanced number of cars in each station and to evaluate the potential of new locations for carsharing stations. The authors developed a fuzzy logic algorithm that is based on the preferences of potential customers (departure time, weather conditions, day of the week, traffic conditions) to forecast clients demands. Then an estimation of the need of each station for cars at each period of the day was performed in order to take good decisions for cars relocation operations. The authors concluded that a good estimation of client demands is crucial for improving the level of service and relocation operations of a carsharing system.

[ [START_REF] Nair | Fleet management for vehicle sharing operations[END_REF] developed a stochastic, mixed-integer linear programming model with a joint chance constraint in order to plan the vehicle relocation operations. This model aims to minimize the cost of these operations and to guarantee the satisfaction of a proportion of all near-term demand scenarios. The model takes into account the particular aspect of stochastic demand and provides partial redistribution plans for relocation operations when the cars supply and demand at each station are not symmetric. The model was tested with real data from a carsharing system that was operated by Honda Motor (ICVS)

in Singapore and was used for the study of [START_REF] Kek | A decision support system for vehicle relocation operations in carsharing systems[END_REF]; the system stopped and

was not operational at the moment of this study. The study showed that the proposed relocation operations that consider the demand uncertainty could highly increase the level of service of the carsharing system.

[ [START_REF] Smith | Rebalancing the rebalancers: optimally routing vehicles and drivers in mobilityon-demand systems[END_REF] presented a study for the problem of relocating the employees in charge of the relocation operations in a one-way carsharing system. A relocation employee, which is called a balancer, can drive a car alone from a station to another station or he can act as a taxi driver if there is a need for him on the destination station. The study that is based on a fluid model focused on the optimization of the relocation operations in order to reduce the number of relocation vehicles and the employees who drive these vehicles. Based on simulation results, authors proposed a minimum number of drivers and vehicles to maintain a good level of service of the system. The simulations suggested that the number of relocation employees required for the relocation operations should be between 1/3 and 1/4 of the number of the vehicles in Euclidean network topologies.

2.4.6/ User based relocation operations

As described earlier, carsharing operators can recruit employees to relocate cars over the stations. However, the relocation operations could also use the clients themselves for the relocation operations.

[ [START_REF] Uesugi | Optimization of vehicle assignment for car sharing system[END_REF] proposed a new approach for balancing cars in one-way carsharing system. They developed a method to optimize the parked cars distribution by grouping and ungrouping reservation requests based on the need for cars. In a grouping operation, the system suggests that, users who are going to the same destination station, to use one car instead of many (if it is possible), so just one car will leave the departure station and one car will arrive to the destination station. However, in an ungrouping operation, the system suggests that users who are willing to share one ride to go to a destination station to take many cars (if it is possible) instead of just one car so that many cars will leave the departure station and many cars will arrive to the destination station. Generally, a grouping operation intends to reduce cars depletion at the departure station and avoid station saturation at the destination station while an ungrouping operation intends to decrease the number of cars in the saturated stations and increase the number of cars in stations in needs for a car. The simulation results showed that the proposed method could be efficient in rebalancing the cars over the stations. Nonetheless, the authors insisted on the importance of the incentives to motivate users to accept the system decisions. They also stated that the study should be tested with real data.

[ [START_REF] Barth | User-based vehicle relocation techniques for multiple-station shared-use vehicle systems[END_REF] studied the relocation operations in multiple station one-way carsharing system. To solve the vehicle distribution problem, carsharing operators can recruit employees to relocate cars and to maintain a balanced number of cars in each station.

However, this option increases the operational cost of system and its implementation requires a high logistic level. However, in this study, the authors proposed the users themselves instead of recruited employees to handle the relocation operations. Their approach is based on two user-based relocation techniques: trip splitting and trip joining. In trip splitting the system asks users who are willing to share a ride to take many cars instead of one when more cars are needed at the destination station. On the other side, in trip joining the system urges users who are going to the same destination to share one car instead of a car of each user. This approach has been implemented on a real electrical carsharing system at the university of California-Riverside. The results showed that user-based relocation techniques could lead to 42% reduction in the number of relocation operations.

Although grouping and ungrouping operations showed a good performance in balancing cars over the stations, this option cannot work unless if users accept the proposed operation. However, this is not guaranteed for all users due to privacy and convenience issues. In a recent study, [START_REF] Weikl | A practice-ready relocation model for free-floating carsharing systems with electric vehicles -mesoscopic approach and field trial results[END_REF] studied the relocation operations in free-floating carsharing systems that operates electric and conventional vehicles. They proposed two types of relocation operations: macroscopic relocation operations, which refer to moving vehicles between defined geographic zones, while microscopic relocation operations stand for moving vehicles within each zone. The proposed method accounts for refueling, charging and service trips for both models of vehicles. Zones are categorized and analyzed based on historical data. The model provides macroscopic optimized relocation operations supported by microscopic relocation steps. The authors stated that the proposed approach is practice-ready and does not require high computation time and therefore it could be implemented for large-scale scenarios. The model has been tested in a free-floating carsharing system in Munich, Germany with three real tests. According to authors, the model results

were promising in the last test where the net profit increased and the mean idle time for vehicles decreased.

2.4.6.1/ Using incentives

In his book "Reinventing the Automobile: Personal Urban Mobility for the 21st Century", [Mitchell, 2010] proposed a dynamic pricing scheme to urban mobility systems that use intelligent vehicles such as carsharing. The idea is based on the possibility that a user would replace his origin/destination point to another near origin/destination point based on cheaper system suggestions. In a carsharing system, the rental price would change according to need for cars at each station in order to make the carsharing use more efficient.

This strategy can contribute in reducing the number of relocation operations required to balance the vehicles on stations.

[ [START_REF] Febbraro | One-way carsharing: solving the relocation problem[END_REF] proposed a user based relocation technique for one-way carsharing systems. The authors used discrete event systems to simulate the complex dynamics of carsharing system. The proposed approach is based on the participation of the users in order to perform the relocation operations. This method is expected to increase the flexibility of the carsharing system and to decrease the cost of the relocation operations. In their study, the authors considered a carsharing system that does not have defined station locations, but instead the operation area is divided into zones where users can park their vehicles anywhere inside them. An integer linear programming model has been used to define the zones that are chosen in a way that increases client demand satisfaction. Users have to make trip reservation by communicating their trip origin and destination points to the system. The system may propose a new near origin or new destination with discounted price based on the need for cars. The study used fifteen different scenarios modeling the probability of clients' acceptance for the proposed system relocation operations. Results

showed that user based relocation operations could increase the availability of cars at the stations and decrease the number of cars required to satisfy clients' demands.

[ [START_REF] Jorge | Trip pricing of one-way station-based carsharing networks with zone and time of day price variations[END_REF] showed that trip pricing highly contributes in balancing vehicle stocks and therefore in increasing the profit the carsharing operator.

Although incentive based approaches are proved to improve the relocation operations, it has some limitations such as the difficulty of finding convenient alternative origin or destination stations for users. Moreover, it is not easy to provide dynamic real time trip pricing since it requires a high level of communication technology in order to communicate the state of the system and calculate prices based on that.

2.4.6.2/ Full control on reservation requests

Besides operator and user based car relocation operations, carsharing operators can contribute in reducing the imbalance problem by having full control on users reservation requests. Trips that are advantageous to have good balance of cars are accepted while trips that contribute in increasing the imbalance problem are rejected. In the following, we present some papers that followed this approach to mitigate the imbalance problem.

[ [START_REF] Fan | Carsharing: Dynamic decision-making problem for vehicle allocation[END_REF] studied the dynamic decision-making of the vehicle allocation problem in a carsharing system. The authors developed a multistage stochastic linear integer model with recourse that can take into consideration the demand uncertainty using Poisson distribution. The proposed stochastic method is based on the Monte Carlo sampling to model the carsharing dynamic allocation problem in space and time. The method has been tested in a pilot study that is a five-stage experimental network having four carsharing locations.

Results showed that the proposed method could highly contribute in optimizing vehicles allocation and that the algorithm could be used for real life carsharing system.

Later on, [Fan, 2013] followed his study by developing another stochastic optimization framework for the dynamic vehicle allocation problem. In this study, instead of Monte Carlo sampling, the authors considered that the demand is distributed discreetly, which enabled them to solve the stochastic optimization problem using complete scenario-tree.

The computational results showed that this method is also capable of providing highquality solutions that could be tested in real world carsharing systems. However, the solver presented a high computational time even with several simplification conditions. [Fan, 2014] pursued his research by another study in 2014 by developing a new stochastic optimization approach to the strategic vehicle allocation problem in one-way carsharing systems. Using this method, the operator should be able to handle the demand uncertainty, accept or refuse vehicle reservations and optimize vehicle relocation operations in time and space in order to decrease the cost of operating the carsharing system. The author tested the developed approach with a seven-stage network that is constituted of four stations. Results showed that proposed method could deliver high quality solutions. The study has been concluded by a suggestion to test the model with real-world applications and to validate results with historical data.

[ [START_REF] Correia | Optimization approach to depot location and trip selection in one-way carsharing systems[END_REF] proposed an optimization approach to depot location and trip selection in one-way carsharing systems. The authors developed three Mixed-Integer Linear

Programming models in order to maximize the profits and to decrease the operation cost of the carsharing system under three different trip selection schemes. The first scheme considers that the operator has a full control on reservation acceptance or rejection through central request management in order to maximize profit. While in the second scheme all the reservation requests between any pair of stations will be accepted. The third scheme is a mix between the first two schemes where the operator could reject reservation requests only when the pick-up station does not have any cars. The study has been implemented for the municipality of Lisbon, Portugal as a case study. Results emphasized on the high im-pact of the trip selection scheme on the gained profit of carsharing systems. For instance, the trip selection scheme that accepts all reservation requests is proved to engender a high financial loss. It was also shown that the choice of stations parameter configurations such as number, location and size could decrease the financial also.

2.4.7/ Optimal fleet size and service availability [START_REF] George | Fleet-sizing and service availability for a vehicle rental system via closed queueing networks[END_REF] studied the problem of defining the optimal fleet size in vehicle sharing system and its relation to the vehicle availability at each station. The authors proposed a closed queuing network model of the system. Based on this model, it was possible to estimate the vehicle availability in a given station with respect to fleet size. The developed framework allows analyzing the stations behavior regarding vehicle availability and then it can help carsharing operators in designing good balancing methods. In order to define the optimal fleet size, a profit-maximizing optimization problem has been presented. The problem was solved using approximation methods. The model had some limitations such as the absence of relocation operations and the infinite stations capacity.

[ [START_REF] Cepolina | A new shared vehicle system for urban areas[END_REF] proposed a simulation study for a shared vehicle system in an urban area. The study presented a method that is based on Simulated Annealing algorithm to optimize the fleet size and its vehicle distributions among stations. The objective was to minimize the cost of the carsharing system, which includes the management cost of the transportation system and the cost of total users waiting time. The study has been supported by a simulation model that tracks each user and each vehicle. This work concerns the Genoa city center in Italy where real data was collected for the study. Results were compatible with other research papers that dealt with the same topic.

2.4.8/ Carsharing network growth [START_REF] Fassi | Evaluation of carsharing network's growth strategies through discrete event simulation[END_REF] presented a study for evaluating round-trip carsharing network's strategies using discrete event simulation. The proposed strategies include adding a new station, increasing the capacity of a station and merging, demerging carsharing stations, etc. The carsharing operators need to adjust the number of stations and their capacities based on the users demand variation. Authors proposed this model to help decision makers in choosing the best network growth strategies that meet users' demand. The study has been applied

for a region of Communauto's Montreal (Québec, Canada) where different scenarios have been compared for different potential strategies.

2.5/ Bikesharing related research

Besides fitness improvement, biking has been always considered as an ecological transportation mean that contributes in reducing air pollution and energy consumption. Hence, different policies and initiatives are proposed to promote biking for public use as a complementary mobility service for the existing multimodal transport in urban areas ( [START_REF] Pucher | Integrating bicycling and public transport in north america[END_REF]) . Recently, many cities over the world have added bikesharing systems into their transportation system offer ([DeMaio, 2009]; [START_REF] Shaheen | Bikesharing in europe, the americas, and asia: past, present, and future[END_REF]).

A bikesharing system offers self-service bikes for eligible users. Bikes are located into different stations in an urban area. Generally, bikesharing users can take a bike from a station and return it to any other station. The operation of this kind of systems implies different logistics problems that are similar to those encountered in carsharing systems.

For instance, one of the common problem is the imbalance in the bikes stocks in the stations: a user who arrives to a station should be able to find a bike when he arrives to a station, and he should find an available parking space in the station when he wants to return his bike. This imbalance problems encountered in bikesharing and carsharing systems are similar, however the relocation operations used to redistribute bikes and cars is not the same. In bikesharing case, a truck can relocate many bikes together at the same time to solve imbalance problems in several stations. However, this is not possible in the carsharing system where the use of track might not be possible due to car's size and the difficulty of moving many cars together. In the following, we present a brief overview of some research topics that dealt with bikesharing problems.

2.5.1/ Strategic design and planning decisions

Researchers have addressed bikesharing from its different perspectives. Some papers studied system design issues related to bikesharing such as bike lanes and paths [START_REF] Dill | Bicycle commuting and facilities in major us cities: if you build them, commuters will use them[END_REF]; [START_REF] Moudon | Cycling and the built environment, a {US} perspective[END_REF]; [START_REF] Petritsch | Bicycle level of service for arterials[END_REF];). While other papers addressed the factors that affect the demand and the attractiveness of bikesharing systems ( [START_REF] Hunt | Influences on bicycle use[END_REF]; [START_REF] Wardman | Factors influencing the propensity to cycle to work[END_REF]). In addition, bike-transit integration ( [START_REF] Taylor | Analysis of stated preferences for intermodal bicycle-transit interfaces[END_REF]; [START_REF] Brons | Access to railway stations and its potential in increasing rail use[END_REF]; [Martens, 2004] and [Martens, 2007]).

[ [START_REF] Lin | Strategic design of public bicycle sharing systems with service level constraints[END_REF] addressed the strategic design of public bikesharing systems based on service level constraints. They presented a mathematical model that aims to locate stations and determines their number. In addition, the proposed model suggests the bike lanes and paths between each pair of stations. Then [START_REF] Lin | A hub location inventory model for bicycle sharing system design: Formulation and solution[END_REF] proposed a similar approach for the strategic design of bikesharing system based on a hub location inventory model that considers the bikes stock at each station to ensure a good level of service.

[ [START_REF] García-Palomares | Optimizing the location of stations in bike-sharing programs: a gis approach[END_REF] presented a model that aims to optimize the location of stations in bikesharing systems using a GIS approach. The model can forecast the spatial distribution of the bikesharing demand as well as defining station locations and capacity, and the characteristics of the demand for stations. [START_REF] Sayarshad | A multi-periodic optimization formulation for bike planning and bike utilization[END_REF] proposed a mathematical model for the optimization of bikesharing system's design in small communities. The model tries to optimize fleet size in order to increase the service level and to decrease the number of relocation operations.

2.5.2/ Bike relocation problem

Other papers addressed the bike relocation problem in bikesharing systems. There are two types of relocation operations: static and dynamic. In static relocation, bikes are relocated between stations when the demand is in its lowest levels in order to anticipate user demands later on. However, dynamic relocation is performed multiple times during the day depending on the urgent need for bikes in stations.

2.5.2.1/ Static relocation

[ [START_REF] Benchimol | Balancing the stations of a self-service bike hire system[END_REF] presented a study for the static relocation problem in a bikesharing system where the operator uses one truck for the relocation operations.

[ [START_REF] Chemla | Self-service bike sharing systems: simulation, repositioning, pricing[END_REF] proposed an optimization model to solve the relocation problem in bikesharing systems. They modeled the problem as a many to many pickup and delivery.

One single capacitated vehicle is used to relocate bikes in order to reach target bikes stocks at each station. The authors stated that the problem is NP-hard since it gathers several NPhard problems. A relaxation of the problem was solved using a branch-and-cut algorithm.

[Dell' Amico et al., 2014] also addressed the bike sharing rebalancing problem. They presented four mixed integer formulations to model the problem. Branch-and-cut algorithms were used to solve each of them. [START_REF] Forma | A 3-step math heuristic for the static repositioning problem in bike-sharing systems[END_REF] proposed a 3-step matheuristic for the static rebalancing problem in bikesharing systems. The bike relocation operations are performed using trucks that load and unload bikes from stations. In a first step, the model creates clusters of stations based on geographic and bikes inventory needs. Then, in the second step, the model calculates an estimation of bikes inventory for each station in each cluster and required relocation decisions between the clusters are defined. In the last step, final relocation decisions are defined with respect to decision proposed in step 2

or between stations in the same cluster.

2.5.2.2/ Dynamic relocation

Research papers that deal with dynamic relocation problem in bikesharing systems are not abundant. [Lu, 2013] and [START_REF] Sayarshad | A multi-periodic optimization formulation for bike planning and bike utilization[END_REF] showed the importance of good relocation operations for the service level in bikesharing systems. The models did not consider the relocation operations in details concerning the vehicle routing problems.

On the other side, the proposed models used aggregated cost of unmet demands and relocation operations. Other papers addressed the relocation problem with more details. [START_REF] Contardo | Balancing a dynamic public bike-sharing system[END_REF] proposed a mathematical model to solve the dynamic bike relocation problem in bikesharing systems. The authors used Dantzig-Wolfe decomposition and Benders decomposing to obtain the lower bounds and feasible solutions in short computing time. The bikesharing relocation problem has been addressed also in [START_REF] Caggiani | A dynamic simulation based model for optimal fleet repositioning in bike-sharing systems[END_REF], [START_REF] Chemla | Self-service bike sharing systems: simulation, repositioning, pricing[END_REF] and [START_REF] Pfrommer | Dynamic vehicle redistribution and online price incentives in shared mobility systems[END_REF].

2.6/ Synthesis

In this chapter, we presented an overview of carsharing and related research works. In this thesis, we focus on one-way carsharing systems where carsharing users can take a car from a station and return it to any other station. The main problem that faces carsharing operators is how to maintain an enough number of cars in each station in order to satisfy users demands when they arrive to stations to take a car or when they want to return back the car when they finish using it. We presented many research papers that addressed different problems related to the operation of carsharing system. The main covered topics concern demand forecasting, factors that affect the demand, network design, station locations and car relocation, which is our subject in this thesis.

Authors Covered topics

Proposed approach carsharing models [START_REF] Bonsall | Microsimulation of organised car sharing-model predications and policy implications[END_REF] Testing different scenarios, strategies, locations, scales and prices

Microsimulation

Round-trip [Bonsall, 1982] Modelling organised carsharing systems and comparing model predictions with actual performance Microsimulation Round-trip [START_REF] Arnaldi | Simulation models for french praxitele project[END_REF] Simulation of carsharing systems Simulation One-way [START_REF] Dror | Redistribution of selfservice electric cars: A case of pickup and delivery[END_REF] Operator-based relocation operations Optimization One-way [START_REF] Barth | Simulation model performance analysis of a multiple station shared vehicle system[END_REF] Operator-based relocation operations

Queuing-based discrete-event simulation

One-way [START_REF] Barth | Performance evaluation of a multi-station shared vehicle system[END_REF] User-based relocation operations Trip joining One-way [START_REF] Barth | User-based vehicle relocation techniques for multiple-station shared-use vehicle systems[END_REF] User-based relocation operations Simulation One-way [START_REF] Kek | Relocation simulation model for multiple-station shared-use vehicle systems[END_REF] Operator-based relocation operations

Discrete-event simulation

One-way [START_REF] Uesugi | Optimization of vehicle assignment for car sharing system[END_REF] User-based relocation operations Simulation One-way [START_REF] Stillwater | Carsharing and the built environment: A gis-based study of one us operator[END_REF] Environmental and demographic factors that affect the usage of carsharing

Regression analysis

Round-trip [START_REF] Catalano | Car sharing demand estimation and urban transport demand modelling using stated preference techniques[END_REF] Estimation of carsharing demand for carsharing

Random utility model

Not defined [START_REF] Fan | Carsharing: Dynamic decision-making problem for vehicle allocation[END_REF] Trip selection Optimisation One-way [START_REF] Zheng | Carsharing in a university community: Assessing potential demand and distinct market characteristics[END_REF] Carsharing market Regression analysis Not defined [START_REF] Kek | A decision support system for vehicle relocation operations in carsharing systems[END_REF] Operator-based relocation operations Optimisation and Discrete-event simulation One-way [START_REF] Wang | Dynamic relocating vehicle resources using a microscopic traffic simulation model for carsharing services[END_REF] Operator [START_REF] Ciari | Estimation of carsharing demand using an activity-based microsimulation approach: model discussion and some results[END_REF] Estimation of carsharing demand Activity-based simulation Round-trip [Papanikolaou, 2011] Describing the functioning of oneway carsharing systems System Dynamics One-way [START_REF] George | Fleet-sizing and service availability for a vehicle rental system via closed queueing networks[END_REF] Performance of a carsharing system Discrete-event simulation Oneway/ Roundtrip [START_REF] Nair | Fleet management for vehicle sharing operations[END_REF] Operator-based relocation operations Optimisation One-way [START_REF] George | Fleet-sizing and service availability for a vehicle rental system via closed queueing networks[END_REF] Optimal fleet size and servic availability closed queueing network model/optimzation One-way [START_REF] Morency | Understanding members' carsharing (activity) persistency by using econometric model[END_REF] Behaviour of carsharing users Random utility model Round-trip [Barrios, 2012] Level of service offered to users Agent-based simulation model One-way [START_REF] Smith | Rebalancing the rebalancers: optimally routing vehicles and drivers in mobilityon-demand systems[END_REF] Operator-based relocation operations Optimisation One-way [START_REF] Correia | Optimization approach to depot location and trip selection in one-way carsharing systems[END_REF] Trip selection and station location Optimisation One-way [START_REF] Fassi | Evaluation of carsharing network's growth strategies through discrete event simulation[END_REF] Evaluating network growth strategies

Discrete-event simulation

Round-trip [START_REF] Cepolina | A new shared vehicle system for urban areas[END_REF] Optimal fleet size and vehicle distributions

Optimization and simulation

One-way [Fan, 2013] Trip selection Optimization One-way [Fan, 2014] demand uncertainty and trip selection Optimization One-way [START_REF] Bruglieri | The vehicle relocation problem for the one-way electric vehicle sharing: An application to the milan case[END_REF] Operator-based relocation operations Optimization One-way [START_REF] Nourinejad | Vehicle relocation and staff rebalancing in one-way carsharing systems[END_REF] Operator-based relocation operations Optimisation One-way [START_REF] Weikl | A practice-ready relocation model for free-floating carsharing systems with electric vehicles -mesoscopic approach and field trial results[END_REF] Operator-based relocation operations Optimization One-way [START_REF] Jorge | Trip pricing of one-way station-based carsharing networks with zone and time of day price variations[END_REF] Trip pricing Optimization One-way Table 2.4: Summary of the studies presented (adapted from [START_REF] Jorge | Carsharing systems demand estimation and defined operations: a literature review[END_REF])

Exact and Heuristic Approaches for the relocation problem I n the previous chapter we have presented a general introduction of carsharing systems and an overview of the literature for the related research. This chapter tackles the relocation problem in one-way carsharing systems. For this sake we propose two approaches for solving this problem: an exact approach and a greedy search algorithm. Then, we provide different results and analysis for these two approaches to highlight the particular aspects related to this problem. In the literature, papers do not emphasize on the workload and cost of employees recruited to relocate cars between the stations, the objective in this chapter is to bring the attention to the complexity of these operations. This chapter is structured as follows. The next section presents a physical description for the relocation problem. This is followed by the formulation of an Integer Linear Programming model, which is an exact approach for solving the problem. After that, we propose a greedy algorithm and three relocation policies for solving the problem. Then, the platform and mobility data used for this study are described, followed by a statistical analysis using ANOVA and multiple regression methods. After that, we present different results and analysis to compare and evaluate the proposed approaches. Finally, the chapter conclusion is provided.

3.1/ Introduction

The relocation problem in carsharing systems has been the subject of many research papers. In this chapter we deal with the relocation problem in one-way carsharing systems. This kind of system has many stations which are usually located in different zones within an urban area. Each station has a fixed number of parking spaces to park the cars belonging to the fleet of the carsharing service. One-way carsharing systems offer the flexibility to drive a car from a station and leave it in any other station unlike the round-trip service where users must return the cars to the station of departure.

Due to asymmetric demand, some stations will accumulate cars preventing users who want to return their car from finding a free parking space. While other stations will not have any available car so users demands to take a car from these stations will be rejected as well. When users demands, to take a car or to return it, are frequently rejected, users tends to drop the idea of using the service that is not available when they want it. Subsequently, the system will fail to keep a good level of service and eventually the service will stop. For this reason, carsharing operators recruit employees to relocate cars between the stations in order to guarantee a good level of service.

The relocation operations add another cost on the carsharing operators since they require hiring more employees to handle these operations. Consequently, carsharing operators aim to optimize these operations in order to find a good compromise between a good level of service and low cost of relocation operations.

As described earlier in the literature section, there are many papers dealing with the relocation problem in carsharing system. In this chapter, we are dealing with the relocation problem in one-way carsharing systems. A physical and a mathematical description are provided for our problem. Then we proceed with a greedy algorithm for rebalancing the cars over the stations with comparison of three proposed relocation policies. After that we provide a description of the data that we use for our study. ANOVA and multiple regression are used to analyze the data and to build a model that predicts the number of rejected demands in a carsharing system. Then, a comparison and analysis are provided to evaluate the proposed greedy and the exact model that is solved using CPLEX. A synthesis for this chapter is provided at the end. Carsharing systems are increasing in size, e.g., Autolib' is an electric carsharing service operating in Paris, France; this service has more than 3305 cars distributed over more than 975 stations (July 2015).This huge number of stations and cars, makes the problem solving with an exact solver impossible in a reasonable time.

In an attempt to cope with this problem, our greedy algorithm proves that is takes few seconds to deliver competitive relocation plans when comparing the results with those of CPLEX.

3.2/ Physical description for the relocation problem

In this section, we are dealing with one-way carsharing systems, which consists of many stations scattered in an urban area. Each station has a maximum number of parking places.

System users can take a car from a station and return it to any other station. When a user arrives at an empty station to drive a car, his request will be rejected. On the other side when a user wants to return a car to a station that is full, his request will be rejected as well. Users expect that cars are always available in stations when they need it, and they expect to find a free parking place at the destination station when they want to return the rented car as well. However, maintaining this level of service is not an easy task.

Carsharing operators recruit employees to relocate cars between the stations in order to satisfy the users' demands; in the following, we refer to these employees by "jockeys".

However, when the operator fails to solve this imbalance problem, users tends to abandon the system, which leads to potential system failure.

We modeled our one-way carsharing system by a simple time-space network. To simplify the idea, an example of a simple carsharing system is provided below. In Table 3.1, we see the number of available vehicles av i t in each station i for each time step t. We have three stations S 1 , S 2 and S 3 . At time t = 0, we have the initial number of available vehicles in each station. Table 3.2 shows the number of cars out i t that users would like to take from each station at each time step. Table 3.3 shows the number of cars in i t that users would like to return to each station at each time step. In Table 3.4, we see the number of rejected user demands to take a car because a station is empty outR i t while Table 3.5 shows the

av i t = av i t-1 + (in i t -inR i t ) -(out i t -outR i t ) (3.1)
In equation (3.1), available vehicles in station i at time t is equal to the number of available vehicles at the same station in the previous time step added to the number of arriving cars to the same station at time t minus the number of cars that could not be returned because the station is full. Then, we subtract the number of cars that go out of the station minus the number of rejected requests to take a car out of the station because there is a lack of cars. As we can see in Table 3.4, we have one rejected demand in station S 2 at time t = 6.

This rejected demand occurs because station S 2 does not have any vehicle at t = 5 and the request for departing vehicles is one at t = 6. On the other side, we see in Table 3.5 that we have one rejected demand in station S 1 at time t = 6 since this station has four vehicles at t = 5 and there are two requests to return cars at t = 6.

3.3/ Overview on relocation mechanisms in one-way carsharing systems

As described earlier, due to asymmetric user demands in one-way carsharing system, some stations have an excess of cars so arriving users who want to park their cars are rejected, while other stations are empty so users demands to take a car from these stations are rejected as well. In these two situations, the number of cars in some stations need to be adjusted by moving cars in an intelligent way from overfull stations to stations that are in need for more cars. The relocation operations are required to decrease the rejection of users' demands to take a car or to return it to a station. There are different car relocation mechanisms proposed in the literature. In [START_REF] Barth | User-based vehicle relocation techniques for multiple-station shared-use vehicle systems[END_REF], authors proposed two relocation techniques namely towing and ridesharing to do the relocation operations.

3.3.1/ Towing

In towing technique, cars are relocated from one station to another using cars that are allocated for this task or even using cars from the system if they are available. Two towing techniques are proposed:

• Electronic towbar towing techniques that were discussed in [START_REF] Massot | Praxitèle: preliminary results from the saint-quentin station-car experiment[END_REF],

for which no mechanical linkage is required to connect the vehicles. Vehicles are equipped with sensors and control system so they can follow each other under their own power, allowing moving several vehicles by using only one driver.

• Mechanical towing was also used in another study [START_REF] Barth | User-based vehicle relocation techniques for multiple-station shared-use vehicle systems[END_REF] where each vehicle could be towed to another vehicle using a towing hitch that could be found in front and back.

3.3.2/ Ridesharing

In ridesharing technique, one or more relocation employees drive separate vehicles and then they share one vehicle to return. The return of the relocation employees can also be provided by another relocation employee or even by sharing a ride with a regular user trip. As described earlier in chapter 2, the system users can contribute in the relocation operation by responding to the operator suggestions to join or to split a trip based on the need for cars in the departure and in the destination station.

In our study, we consider that the relocation employee uses a scooter that can be folded easily in the car trunk as in figure 3.1. So a relocation operation starts when the relocation employee goes by using his scooter to the overfull station. Then he puts his scooter in the car trunk and drive the car to another station that needs a car and so on.

3.4/ Integer Linear Programming formulation

Starting from [START_REF] Kek | A decision support system for vehicle relocation operations in carsharing systems[END_REF], the relocation problem can be modeled as a two dimensional time-space matrix of size N × T , where N is the total number of stations S = {1, 2, .., N} and T is the number of time steps in the day starting from 1 to T . Each element of the matrix represents a station S i at time t. For each station s ∈ S we generate T nodes to represent that station at each time t. Then we put all the S × T nodes in one row vector V = (1 1 , ..., 1 T , ..., N 1 , ..., N T ). During the day, we consider that an employee is involved in three types of activities:

1. Relocating: is the action taken by the jockey to move a car from a station i to another station j.

2. Moving: is the action taken by the jockey to move himself from his current station to another station in order to begin a relocation activity.

3. Waiting: when the jockey is not involved in relocating or moving activities we say that the jockey is waiting.

Therefore, to represent these activities we generate three sets of arcs in the time-space network. For each node i t ∈ V, we construct an arc wa that represents a waiting activity between i t and i t+1 ; we call this set WA = {..., wa(i t , i t+1 ), ...}. Then, for each node i t in V, we construct N -1 arcs ma to represent moving activities between station i and j, ∀ i, j ∈ S , i j, from time step t to time step t+t i j where t i j is the number of time steps needed to go from station i to station j; we name this set MA = {..., ma(i t , j t+t i j ), ...}. In the same way of moving activities, we build N -1 arcs ra to represent relocation activities for each station, and we denote this set RA = {..., ra(i t , j t+t i j ), ...}. We represent the available staff that will be involved in doing these activities by a set E = {1, ..., e, ..., W} where W is the maximum number of available employees. We have formulated our relocation problem as an Integer Linear Programming Model. We used six decision variables:

• u e : Binary variable, that takes the value 1 if the employee e is used during the day and 0 otherwise.

• wait e i t i t+1 : Binary variable associated with the set of waiting activities WA. It takes the value 1 if employee e has been waiting at station i from time step t to t + 1 and 0 otherwise.

• move e i t j t+t i j : Binary variable associated with the set of moving activities MA. It takes the value 1 if employee e has been moving from station i to station j, from time step t to t + t i j and 0 otherwise.

• rel e i t j t+t i j : Binary variable associated with the set of relocation activities RA. It takes the value 1 if employee e has been relocating a car from station i to station j, from time step t to t + t i j and 0 otherwise.

• outR i t : Integer variable to represent the number of rejected demand to take a car out of a station i at time step t.

• inR i t : Integer variable to represent the number of rejected demand to return a car into a station i at time step t.

In the other hand, here are the input parameters that will be used for the model:

• av i 0 : Number of available vehicles at time step 0 in the station i.

• out i t : Number of demands to take a car out of a station i at time step t.

• in i t : Number of demands to return a car into a station i at time step t.

• p i : Number of parking slots in the station i.

• cMove i j : Cost of a moving or relocating activity from station i to station j.

• cStaff e : Cost of using one staff during the day.

• cRejectFull : Cost of rejecting a client demand for returning a car into a station.

• cRejectEmpty : Cost of rejecting a client demand for taking a car from a station.

In addition, we used one dependent variable:

• av i t : Number of available vehicles at station i at time step t.

The ILP model for the problem is:

Min Z = cMove i j ( (i t ,
- (i t , j t+t i j )∈RA rel e i t j t+t i j = 0 ∀ i t ∈ V, e ∈ E, t > 1 (3.4
)

av i t = av i t-1 + (in i t -inR i t ) -(out i t -outR i t ) + ( j t-t i j ,i t )∈RA e∈E rel e j t-t i j i t - (i t , j t+t i j )∈RA e∈E rel e i t j t+t i j ∀ i t ∈ V (3.5) av i t ≤ p i ∀ i t ∈ V (3.6) inR i t ≤ in i t ∀ i t ∈ V (3.7) outR i t ≤ out i t ∀ i t ∈ V (3.8) u e ∈ {0, 1} ∀ e ∈ E (3.9)
wait e i t i t+1 ∈ {0, 1} ∀ (i t , i t+1 ) ∈ WA, e ∈ E (3.10) move e i t j t+t i j ∈ {0, 1} ∀ (i t , j t+t i j ) ∈ MA, e ∈ E (3.11
)

rel e i t j t+t i j ∈ {0, 1} ∀ (i t , j t+t i j ) ∈ RA, e ∈ E (3.12) inR i t ≥ 0 ∀ i t ∈ V (3.13) outR i t ≥ 0 ∀ i t ∈ V (3.14) av i t ≥ 0 ∀ i t ∈ V (3.15)
The objective function (3.2) minimizes the weighted aggregation of the number of rejected demands to take or to return a car, the number of employees and the number of move and relocation operations needed to reduce the number of rejected demands. Constraint (3.3) is used to make sure that each employee is involved in only one activity at a time and it is used to set the variable u e to 1 if the employee e is used at t = 1. Constraint (3.4) is used to make sure that an employee will not start a new activity until he finished the previous one and to guarantee a continuity for the employee's activities once started at t = 1. We used Constraint (3.5) Based on this model, we can estimate the number of variables that are generated. For a carsharing system that has 18 stations and for 14 jockeys, we have the following variables:

• the size of u e is: |E| = 14

• the size of wait e i t i t+1 is: As a summary, the Autolib' problem has:

|S | × |T | × |E|
• 6,217,344,040 binary variables

• 259,200 integer variables Given this huge number of variables, one can imagine that an exact approach is not capable of solving this problem in a reasonable time. Consequently, a heuristic approach seems to be a good choice to cope with this problem.

3.5/ Greedy Algorithm for the car relocation problem For some configurations, CPLEX takes more than two days to deliver a solution and for other configurations, we could not get any results using this solver. In figure 3.2, we see CPLEX execution time when solving the relocation problem of a simple carsharing system that has 18 stations with 10 parking places for each, and 83 cars with an average of 12 trips per each car. We notice that CPLEX execution time tends to increase dramatically when we increase the number of jockeys. The long execution time to solve the relocation problem using CPLEX pushed us to think about a different approach that solves the relocation problem in a faster time but not in an optimal way. For this sake, we developed a simple greedy algorithm that tries to reduce the number of rejected demands using the minimum number of relocation operations. Each relocation operation consists of two steps: in a first step, the jockey chooses the station where he will take a car, then in a second step, he chooses the station where he will drop that car in order to regain the balance of the system.

It is important to note that it is possible to change the relative MIP gap tolerance in CPLEX in order to reduce the execution time if the solver finds a relatively satisfactory solution.

For example when we set this value to 0.06, CPLEX will stop the optimization process once it finds a feasible integer solution that is proved to be within 6% of the optimal. The default value of this value is 1e-04. It was tested that even when changing this value to 9%, the solver execution time decreases but stays relatively long.

In this next section, we propose different relocation policies or heuristics from the problem and then we implement these approaches using a greedy algorithm in a policy pattern to measure the effect of each policy on the total number of rejected demands. When we run the greedy algorithm, it takes at most one second to build a non-optimal solution for the most complicated configurations that we generated using our platform, using any of the three policies.

3.5.2/ Relocation Policies

The choice of relocation policy plays a major role in reducing the number of rejected user demands and therefore in increasing client satisfaction. We tried different approaches for our greedy algorithm:

• Policy 1: The jockey moves one car from the nearest station to his current station, and if several, the one having the highest number of cars, to the nearest station, and if several, to the one having the lowest number of cars.

• Policy 2: The jockey moves one car from the station having the highest number of cars, and if several, the nearest station, to the station having the lowest number of cars, and if several, at the nearest stations.

• In this policy, the priority is given to the time needed to move between the stations. For each operation decision, the jockey chooses the operation that takes the shortest possible time with the aim of maximizing the number of relocation operations that can be done during the day. As the first step of each relocation operation, the jockey selects the nearest station to his current location and he takes a car from this station. If many stations have the same distance, he selects the station that has the highest number of cars. Then, in a second step, the jockey selects the nearest station again and if he finds many, he selects the station that has the lowest number of cars. For example, we see in figure 3.3 a representation of this policy with four stations. Each station is represented by a disc that contains the station name and the number of available cars at the specified time. In our example, during the first step, the jockey goes to the nearest station from his location which is S 3 . This moving activity is done without a car from the system. Then, during the second step, the jockey drives a car from the selected station S 3 to the station S 1 , since it is the nearest station at first and because it has the lowest number. In this policy, the priority is given to rebalance the number of cars between the stations, with the goal of regaining balance for the stations. This approach is similar to the previous one, but here, we reverse the order of choosing the stations in each step. As the first step of the relocation operation, the jockey finds the list of stations having the highest number of cars, and then he chooses the nearest station among this list. Then, in the second step, the jockey looks for the list of stations having the lowest number of cars, and then he chooses the nearest station amongst this list. As we can see in figure 3.4, the jockey chooses station S 2 in the first step since it has the highest number of cars, while the choice in the second step remains the same since station S 1 has the lowest number of cars. In this policy, we consider that the jockey has an estimation of what will happen in the future, so he can foresee the rejected demands even if they occur after several time steps.

In addition, in this policy the jockey can see the effect of each relocation operation on the whole system, so he can avoid removing or adding cars to some stations when it can lead to car shortage or car saturation respectively. In this approach, the jockey tries to solve the maximum number of rejected demands in each relocation operation. As the first step in a relocation operation, the jockey looks for the list of stations having the soonest rejected demands as a result of stations filling up (inR i t > 0) and the list of stations that can provide cars to other stations in the future. Then, in a second step, the jockey looks for the list of stations having the soonest rejected demands because stations are empty (outR i t > 0) and the list of stations that may need cars in the future. From these lists, the relocation operation is planned in a way that reduces the maximum number of rejected demands while avoiding that these operations will cause future rejected demands. When choosing the best relocation operation, if we have many possibilities that reduce the same number of rejected demands, we privilege the operation that reduces rejected demands in the nearest stations and the soonest possible. In figure 3.5 we propose the flow chart to implement Policy 3 in a greedy algorithm. A greedy algorithm makes the optimal choice at each iteration up to the local optimum. 3.6/ Experimentation and results

3.6.1/ Mobility Data

The mobility data used for this study consists of survey data and socio-economical information collected by professional for regional planning purposes. This data describes people mobility flows in a region of 20 km x 10 km in Paris. This area is divided into a grid of equal cell sizes. Each cell has two characteristics:

• Terrain type: to describe the dominant structure type of the area associated to the cell (roads, buildings, houses, business center, commercial center, etc.)

• Attraction weight: based on the terrain type and survey data, this information attributes a dynamic attraction weight to each cell for each 15 minutes of the day People mobility between different cells is represented by a 3D matrix F = ( f i, j,t ), where f i, j,t represents the number of people who want to move from cell i to cell j at time t.

We consider t to be a period of 15 minutes during the day, which makes 96 time periods.

Then the flow mobility data is plotted on a map using GIS shapefiles. As a result, 400 cells have been detected as a potential origin or destination point knowing that some cells are eliminated because of their geographical nature e.g. lakes, plains, etc. The final flow mobility data consists of 400 x 400 x 96 elements, which makes 15,360,000 records to represent how people move during the day.

3.6.2/ Platform for Locating Stations

In [START_REF] Moalic | A multiobjective memetic algorithm for solving the carsharing problem[END_REF], our team developed a platform for locating stations for a carsharing system in the region of our study. This platform takes advantage of the mobility data that we described earlier in section 3.6.1. To locate the stations, a multiobjective memetic algorithm has been implemented in the platform. The algorithm optimizes three objective functions:

• Objective 1: The location of the stations should maximize the mobility flow between the cells.

• Objective 2: The location of the stations should maximize the balance between the ingoing and outgoing flows in each station (embedded relocation optimization policy).

• Objective 3: The location of the stations should minimize the standard deviation of the flows in order to obtain a uniform flow during the day.

Each cell is considered to cover the demand in a radius of 300 meters. Special filters and probability distribution are applied on the mobility data to forecast the potential users for the service. A study has been carried out with the carsharing operator to set the desired system parameters.

3.6.3/ Dataset Analysis

We used this platform described in section 3.6.2 to generate the data for this study. The generated dataset consists of the four matrices described in section 3.2. For each generated dataset, we use four parameters:

1. Total number of cars in the system, referred by V.

2.

Total number of stations in the system, referred by S .

3. Average number of trips per car during a day, referred by M.

4. Number of parking spaces in each station, referred by P.

The platform is used to find the optimal locations of stations in a new carsharing system within an urban area. Given a combination of the described parameters (V, S , M, P), this platform locates the stations in a way that covers the maximum user demands while respecting the predefined objectives. The platform constitutes our source of data that will be used in the optimization process. Before proceeding with the optimization methods, we start by analyzing the data in order to better understand the behavior of the carsharing system under different combinations of parameters.

In the following, we develop a model using the Design Of Experiments (DOE) analysis ( [Voss et al., 1999]) and multiple linear regression methods to induce a mathematical model from different scenarios of carsharing configurations. The model can be used later to predict the number of rejected demands for any combination of carsharing system parameters that fall in the studied range. This information can serve later to estimate the number of employees needed to relocate the cars between the stations.

3.6.3.1/ Design of Experiments plans

As described earlier, we use the platform developed by our team to generate the data. We use four parameters as input for the platform and we get the 4 different matrices as output.

As we can see in figure 3.6, the platform also gives the total number of rejected demands that is calculated based on the generated matrices. We use the design of experiments Factor P M S V P M S V P M S V P M S V P M S V Level 1 4 3 18 30 6 6 12 39 4 3 20 50 7 5 18 80 7 4 18 80 Level 2 5 6 20 45 12 12 20 50 6 6 22 60 8 6 20 90 8 6 20 90 Level 3 6 9 22 60 18 18 28 61 8 9 24 70 9 7 22 100 9 8 22 100 Table 3 to the total number of potential trips between the different stations.

These two indications allow building a new synthetic variable X that will be used later on in this chapter:

X = M × V S × P (3.16)
This variable can be considered as an indication to the "stress level" imposed on the carsharing system by the chosen parameters. It represents the total number of trips per parking.

When the low level values of the S × P parameters is less than 160, we consider that the scenario belongs to small cities. While when that value is 160, we consider that the scenario belongs to intermediate cities. The remaining scenarios belong to medium cities.

Scenarios for large cities are not provided because of platform limitations. We also vary the other parameters to test the system under different demand intensity (3 to 21) and different number of vehicles (30 to 350).

For this purpose, we used eleven scenarios that yield a total number of 891 experiments.

Each scenario has 81 experiences as described earlier. A statistical analysis is done for each scenario based on the recommended steps for the design of experiments [Voss et al., 1999]. We start by the analysis of the effect of each factor on the average and on the variability of the results (rejected demands). We refer to the effect of a factor by its name in lowercase (s, m, p, v). Effects on the variability are reflected by a global percentage effect. This percentage reflects the influence indicator of each factor on the output. When the sum of the effect percentages of the four factors is greater than 90%, this indicates that these factors alone control the output. Otherwise, an evaluation of the interaction between these factors is needed. An interaction is considered as internal noise in an optimization process. Indeed, an interaction is a source of non-controllable (directly) variability. An ideal configuration (in engineering) consists in finding that the chosen factors, with at most the simple interactions of first degree, are controlling the process (by explaining at least 90% of the output). In our case, the simple interactions of first degree are s × m, s × p, s × v, m × p, m × v and p × v. In this case, it is recommended to proceed with statistical analysis to evaluate the reproducibility of the observed results. This analysis is called analysis of variance (ANOVA) [Voss et al., 1999].

It consists in evaluating the significance of the selected effect factors (and their interactions) compared to the non-selected variability sources that are called "residual". This significance is measured by the statistical test of Fisher-Snedecor [Voss et al., 1999].

In most of the studied scenarios, the test indicated that the four chosen factors were enough to explain more than 90% of the output. In the other cases, the four factors supported by their simple interaction of first degree, were necessary to explain more than 90% of the output. Table 3 These results clearly prove that a global behavior model is possible. We build this model in a polynomial form to calculate the number of rejected demands (RD) using the standard model of polynomial regression as shown in equation 3.17. The values of α i are obtained using the method of least squares.

RD = α 0 + α 1 P + α 2 M + α 3 S + α 4 V + α 5 P.M + α 6 P.S + α 7 PV + α 8 M.S + α 9 M.V + α 10 S .V (3.17) Table 3.11 shows that there is a good correlation between the experimental results and those obtained using the model, which proves the good quality of the model.

Sc1 Sc2 Sc3 Sc4 Sc5 Sc6 Sc7 Sc8 Sc9 Sc10 Sc11
Correlation coefficient between the experiments and the models 0.982 0.987 0.984 0.978 0.973 0.979 0.961 0.940 0.960 0.981 0.975 Table 3.12: Global correlation between different scenarios Table 3.12 shows that, despite the difference between the levels of responses obtained with each scenario, there is, however, a good linear correlation between the results of the different scenarios.

Also, when visualizing the rejected demands vectors in the standardized form, an overall similarity of the observed results is identified as we can see in figure 3.7, the values are contained between a range of ±σ RD (between the two red lines y = x + 1 and y = x -1).

The standardized form is obtained using the formula in equation 3.18. The coefficients α(i) obtained in each scenario and by monomial are thus considered as responses for a given interval of stress level. The three levels of the stress level considered in each scenario are X 1 , X 2 and X 3 . Table 3.14 summarizes the coefficients α(i) described earlier.

S tandardized RD

S ci = RD S ci -RD S c i σ RDS ci (3.18) -2 -1 0 1 2 3 4 -2 -1 0 1 2 3
Based on this observation, a multilinear regression is performed to obtain a relationship SC3 3,7 3,8 3,8 224,567891011121314151617181920217 52,234567891011121314151617185 49,453 3,2345 8,8 SC4 1,3 2,7 4,1 47,789 40,3452 30,455 26,015 SC5 3,3 2,5 2,2 129,2 112,4 45,8 12,01234567893 39,5678910111213142 SC6 2,8 2,4 2,2 269,3 237,0 147,7 28,6 127,3 SC7 1,3 2,0 2,3 206,5 205,6 162,3 5,6 155,7 SC8 1,0 1,9 2,1 297,9 295,7 175,12345678910111213141516174 159,9 SC9 4,3 5,4 5,8 865,1 734,1 90,9 44,9 58,1 52,4 SC10 1,9 2,7 3,3 60,5 -20,9 51,0 -11,4 23,3 -14,8 1,0 -5,3 -8,7 16,0 -1,0 SC11 2,1 2, 4 2,5 132,6 -50,4 107,0 -17,4 26,8 -43,7 6,6 -9,5 -14,4 21,4 -3,1

Table 3.14: Summary of α i coefficients of each scenario between each α i and the variable "stress level". This relationship takes the form of the polynomial below:

α i = β i0 +β i1 X 1 +β i2 X 2 +β i3 X 3 +β i4 X 1 X 2 +β i5 X 1 X 3 +β i6 X 2 X 3 +β i7 X 2 1 +β i8 X 2 2 +β i9 X 2 3 +β i10 X 1 X 2 X 3 (3.19)
Table 3.15 shows the coefficients β i j that allow to predict the α i based on a given range of X which is the stress level. Thus, for a given set of X 1 , X 2 and X 3 , we can obtain the values of β i , which in their turn allow the calculation of the correspondent α i . Once the values of α i are calculated, we can calculate the number of rejected demands.

This approach was validated on our chosen scenarios in addition to other new scenarios. As aforementioned, we have a platform that we use to generate demand data for a car sharing system for any given configuration of parameters. This same tool estimates the number of rejected demands for this same configuration. Our work aimed to study the influence of the main used factors on the number of rejected demands. We opted for different representative configurations of small and medium cities for which different scenarios are studied. We proved that for any configuration of the given parameters, the number of rejected demands is predictable ( and with high confidence) using a model that considers the main factors (P, T, S and V proposed by the decision maker) and their simple interactions.

In addition, similarities in the behavior of the results were identified. This result allows us to offer a unified view of the different configurations. This is achieved by means of a synthetic variable called "stress level". This variable is an indication of the issue or the problem that the platform is trying to optimize. This issue is about satisfying the biggest number of user demands for trips between stations while minimizing the number of rejected demands. The implemented models allow the estimation of the number of rejected demands with a high level of confidence and this for any combination of dimensional and operational parameters of a carsharing system in small or medium cities.

3.6.4/ Comparison of Relocation Policies

In this section we compare the performance of the relocation policies, proposed in section 3.5.2, in reducing the number of the rejected demands. To recall the definition of each policy:

• Policy 1: The jockey moves one car from the nearest station to his current station, and if several, the one having the highest number of cars, to the nearest station, and if several, to the one having the lowest number of cars.

• Policy 2: The jockey moves one car from the station having the highest number of cars, and if several, the nearest station, to the station having the lowest number of cars, and if several, at the nearest stations.

• Policy 3: The jockey moves one car from the station having the soonest rejected demand because it is full to the station having the soonest rejected demand because it is empty.

In figure 3.8, we see a comparison of the three policies described earlier for the relocation problem, these results concern a generated dataset for a carsharing system which has 20 stations with 10 parking places each and 150 cars with an average of 9 trips/car per day.

As we can see, the performance of policy 1 and policy 2 is rather similar at first, then when we increase the number of jockeys over 19, policy 1 and policy 2 start to generate new rejected demands rather than reducing them. Policy 1 is worse than policy 2 in reducing the number of rejected demands. This difference is expected, since policy 2 prioritizes the relocation operations which tends to rebalance the system's vehicle inventory.

The increase in number of remaining rejected demands is due to bad relocation decisions that cause new rejected demands to appear in the future. However, policy 3 performs much better than the other two policies. We can explain this by the fact that the jockey has estimated the future rejected demands, which enables him to take the best relocation decision that reduces the maximum number of rejected demands without causing new rejected demands in the future. Using this policy, the jockey relocates cars only when he is sure that the relocation operation will reduce the number of rejected demands, otherwise he waits for the right moment for the relocation operations. This is clearer in figure 3.9

where we see that the number of relocation operations using policy 1 and policy 2 is quite constant. However, the number of relocation operations in policy 3, tends to decrease as the number of remaining rejected demands decreases. From those results, we may state that short term relocation decisions to get immediate results in car rebalancing, which is the approach mainly used by operators today, is not the best way to do relocation. As we can see in the subsection 3.6.4, the comparison of the performance of the three proposed policies shows that policy 3 is the best approach for the relocation problem. In the remaining part of this chapter, our greedy algorithm implements the policy 3 exclusively.

In order to assess the performance of our greedy algorithm we solved the same problem with the same data with CPLEX. Figure 3.10 shows that the results of the greedy algorithm are competent with the results obtained by CPLEX; especially the greedy algorithm takes less than one second to deliver a solution while CPLEX may take a long time before delivering a solution as shown in section 3.5.

3.6.6/ Stochastic Data Results

After solving the relocation problem using our greedy algorithm and CPLEX, each jockey is affected to a path that should be followed in order to reduce the total number of rejected demands. This path is constituted of a series of relocation operations to be done during the day. A relocation operation tells the jockey from which station and when, a car should be moved, and to which station and when, it should be dropped off. Using policy 3, the number of remaining rejected demands and the number of needed relocation operations decreases when we increase the number of jockeys as we can see in figure 3.8 and figure 3.9. In order to measure the robustness of the resulted relocation operations, we used a special Gaussian method to add stochastic noise to the input data for the incoming and outgoing cars; knowing that the added stochastic noise does not exceed 10% of the original data. The aim of the stochastic noise is to add to the system uncertainty about user decisions to take/drop or not a car at given station at a given time. In figure 3.11 we see an example of stochastic input data modification on the number of incoming cars at a station in our carsharing system. After that, we apply the resulted relocation operation plan using the original data to the stochastic modified input data regardless of the number of available cars; we call this step blind relocation. As we can see in figure 3.12, the number of remaining rejected demands still decreases when we increase the number of jockeys with stochastic input data. However, as much as we increase the number of jockeys, it increases the difference between remaining rejected demands when using the original data and remaining rejected demands using the stochastic modified data (see both curves with triangles). This is due to the fact that each stochastic modification on the input data, in any station at any time step, will be aggregated and propagated to all the following time steps that concern this station. Thus, since we used the number of available vehicles in each station at each time step to make the decision of the relocation operation, the resulted relocation operations can lose its efficiency drastically when the input data of user demands is changed. In another step, we change our greedy algorithm by integrating lower and upper threshold values for the number of cars in the station. The lower threshold is used to avoid relocating a car from a station when the number of available vehicles in the station before the relocation operation is less than or equal to the lower critical threshold. In this example, we set this value to one. That is if the station has only one car before the relocation operation, then the algorithm does not apply the relocation in that station. The upper threshold value is used to avoid relocating a car to a station when the number of available cars in the destination station is greater than or equal to the upper critical threshold. In this example, it is set to the maximum number of places in the station minus one. As we can see in the chart below, the performance of the threshold strategy in terms of reducing the number of rejected demands (curves with squares) is worse than without threshold constraints. In addition, we can see in figure 3.13 that the threshold values do not bring improvement for the blind relocation on stochastic data comparing to blind relocation without using threshold values. In both cases, the difference in the number of reduced rejected demands starts to be small when the number of jockeys is small, but gets bigger as we increase the number of jockeys. On the other side, we notice that the number of relocation operations when using threshold values, is less than the number of relocation operations without using threshold values since threshold add a constraint on the decision of a relocation operation until all rejected demands problems are solved for 16 jockeys as we can see in figure 3.14. We have shown that when using the policy 3 or the exact model, if we increase the number of jockeys, the number of rejected demands decreases. However, the cost of relocation operations increases as well. In our study, we consider that we are using each jockey for the whole day, which is impractical. However, in real life there will be staff shifts that depend directly on the demands and needs of relocation operations. In the literature, relocation operations that are carried out at night are called static relocation since user demands for cars is considered negligible during this period. Static relocation is necessary to provide the stations with the appropriate number of cars for the next morning. In static relocation, there are no time window constraints to deliver cars to stations at specific times, unlike cars relocation during the day where some stations have urgent needs for cars to satisfy user demands on time. In our approach, relocation operations are carried out during the day. When analyzing the time at which the rejected demands are solved using our greedy algorithm with policy 3, we get the histogram in figure 3.15. This histogram compares the total number of reduced rejected demands per hour of the day when using 15 jockeys for the whole day and when using them from 7:00 to 19:00. When analyzing the histogram in figure 3.15 we can detect some relocation patterns during the day. There are some periods of high activity such as the period from 8:00 to 10:00 and from 17:00 to 19:00. There are also periods of low activity such as period from 11:00 to 16:00. These patterns can be explained by the fact that these intervals correspond to periods of high mobility of customers in the morning when they go to work and in the evening when they come back home. On the other side, we notice that when we limit the working time until 19:00, the number of reduced rejected demands in the late hours (17:00 to 19:00) increases. This can be explained by the fact that the jockey can anticipate rejected demands and reduce them even before their occurrences, knowing that the number of reduced rejected demands at any time t of the day, does not only represent the number of reduced rejected demands that occur at time t, but it also includes the anticipated rejected demands that occur in the future but reduced by relocation operations performed at time t.

Thereby, the effort needed for the jockeying operations varies during the day; likewise, the number of jockeys should vary as well. Thus choosing the appropriate number of jockeys per time interval is a key factor to reduce the cost of jockeying operations. In another experience, we divided the working time of jockeys into three periods with an interruption of work between them:

1. From 7:00 to 9:00 2. From 11:00 to 13:00 3. From 17:00 to 19:00 Then we compared the performance of the jockeys in this case with their performance when they work from 7:00 to 19:00. As we can see in the chart below, even when we divide the working time into three periods, the number of reduced rejected demands decreases. However, the slope is smaller since the number of working hours is smaller. We conclude that the company must evaluate the cost of rejected demands in regard to the cost of the jockeying hour and the time period of work of each jockey.

3.7/ Synthesis

One-way car sharing systems are attractive to users who want to do one-way trips, since it is flexible and available on the go. However, the imbalance in car inventories that occurs during the day due to one-way trips at some stations makes the system unavailable for users when they need it. Car relocation operations seems to be essential to mitigate this problem and thus to increase client satisfaction. In this chapter, we compared three different policies of car relocation. We found that the performance of policy 3 where the jockey has information on the future state of the system based on historical data and predictions, is much better than the two other policies that do not consider any future information. We can conclude that applying policies that are based on intuitive decisions such as distance to the 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. In addition, these policies lead to a bigger number of relocation operations, which increases the total operation cost of the system. A relocation policy that takes in consideration historical data to make future estimation is crucial in reducing the number of rejected demands.

On the other side, we see that jockeys have inactivity periods when there is no need for relocation operations. Analyzing these periods, suggests that working hours of each jockey can be reduced and so, we can decrease the car sharing operation cost. In addition, we found that the effectiveness of the resulted relocation operations is highly dependent on the input data even when we use threshold values for the relocation operations. In a different perspective, we performed a data analysis using the design of experiments and multilinear regression methods. The data analysis resulted in a global model that allows the estimation of the global number of rejected demands for any combination of dimensional and operational parameters of a carsharing system in small and medium cities, and with high confidence. Having this information can help the decision makers to have an idea about the car relocation work load that is needed to decrease the rejected demands.

The car relocation problem in a

Multi-Objective perspective

4.1/ Introduction

In chapter 3, we provided a physical description and a mathematical model for the car relocation problem in one-way carsharing system. Then we proposed a greedy approach for solving this problem. The proposed greedy search method proved its performance regarding the execution time and the quality of generated solutions in a comparison with an exact solver. A simple analysis of the results shows that our proposed methods did not treat the multiobjective aspect of the car relocation problem. In our greedy search algorithm, our objective was to minimize the number of rejected demands. However, it is important to integrate other objectives. Therefore, in this chapter we propose a multiobjective approach for solving this problem. To our knowledge, this is a first work that deals with the multiobjective aspect of the car relocation problem in one-way carsharing system.

In the following, we provide an overview of the methods and approaches used to solve and evaluate the multiobjective optimization problems. Then we present a description for the multiobjective car relocation problem in one-way carsharing system including the different objectives that we fixed for our study. After that, we propose two algorithms for solving this problem: the well known genetic approach NSGA-II, and a memetic algorithm which is a hybrid approach combining genetic and local search approaches. Then we provide a description for the genetic operators that will be used in our algorithms and a local search procedure that we integrate in our memetic algorithm. Finally, we compare and analyze the performance of the developed algorithms based on the selected quality indicators. Results show that the memetic algorithm can provide very good solutions for our problem in terms of diversity and intensity. These solutions can be used by decision makers to build their strategy of the car relocation operations.

4.2/ Basic concepts for mono and multi objective optimization

Operations research has always been interested in solving mono-objective optimization problems; research is still going to improve the existing methods and to find new solutions for this kind of problems. However, in real life, most of the complex optimization problems have many criteria to optimize. Therefore, mono-objective optimization methods are not enough for solving all of the encountered optimization problems. Dealing with the multi-objective aspect of an optimization problem makes the solutions more realistic, and helps the decision makers to take better decisions that are more precise, based on a broader sight for the different criteria and for the different alternatives of solving the problem subject of the study. Multi-Objective Optimization (MOO) finds its application in different and varied domains (e.g., transportation, logistics, bioinformatics, telecommunication, etc.). In multiobjective problems, we usually deal with conflicted objectives.

For example, if we want to buy a ticket to fly to a far country, we have many criteria to take into consideration: should we choose the ticket that has cheapest price, or the lowest number of stops or the fastest time, the comfort or the timing? For instance, if we want to get the fastest flight, the price will be high and so on for the other criteria; that is how objectives may become highly conflicting. In mono objective optimization, we work on one single objective function; hence, there is one optimal solution. However, in MOO we have several optimal solutions, depending on the combination of the criteria and it is up to the decision maker preferences to select a solution that is good for him.

4.2.1/ Mono-objective optimization Definition 1: Mono-Objective Problem

In the general case, a mono-objective problem consists in maximizing (or minimizing) an objective function f (x):

OP =          max z = f (x) sub ject to : x ∈ X (4.1)
x is the vector of k decision variables x = (x 1 , x 2 , . . . , x k ) while X refers to the set of feasible solutions.

Definition 2: global optimum

In an optimization problem, we denote a solution x * as global maximum if and only if:

∀x ∈ X : f (x * ) ≥ f (x) (4.2)
These definitions concern mono-objective optimization but it is not the case for multiobjective optimization.

4.2.2/ Formulation of a Multi-objective optimization problem

As described earlier, in MOO we try to optimize conflicting objectives simultaneously.

We can represent a MOO problem as below:

MOP                  max z = f (x) where f (x) = ( f 1 (x), f 2 (x), ..., f n (x)) sub ject to : x ∈ X (4.3)
With n ≥ 2 the number of objective functions, X is the set of feasible solutions in the decision space, x = (x 1 , . . . , x k ) ∈ X is the vector that represents the decision variables.

In the case of combinatorial problems, X is a discrete set. Furthermore, Z is the set of feasible solutions in the objective space (cf. section 4.2.3), Z ⊆ R n such as Z = f (X). The main difference with mono-objective optimization lies in the fact that f (x) takes its values in R n and not in R.

4.2.3/ Decision space VS objective space

The decision space contains all the variables x = (x 1 , . . . , x k ) ∈ X of dimension k. These variables represent the solutions for the problem in the decision space. The objective space, also called criteria space, of dimension n enables us to visualize the evaluations of the solutions from the decision space. among them, it is not often possible to do it using the currently available hardware and computational capacity. An exhaustive exploration of all the possible solutions for an optimization problem is not always feasible in a reasonable time. Thus, the calculation time is a major constraint to take into consideration when solving an optimization problem. Depending on the optimization problem, an acceptable calculation time of a solution varies from few milliseconds (e.g. in the case of an urgent situation on board of an airplane) to several weeks (e.g. in the case of a strategic decision of finding the best locations for the stations in a new carsharing system).

4.2.5/ Complexity of a problem

In this section, we will present a quick overview of the basics of computational complexity theory related to decision problems. More details can be found in the famous book of [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]. When solving a decision problem, we often call for algorithms at a given time. Although, the concept of algorithms has been used for centuries, it has not been really formalized until the appearance of Turing machine. An algorithm is generally considered efficient if its complexity is bounded with a polynomial function depending on the size of data set instance.

Definition 3: Class P

In computational complexity theory, class P contains all the decision problems that can be solved by a deterministic Turing machine in a polynomial time.

However, there are many decision problems which they do not have any known polynomial algorithm.

Definition 4: Class NP

In computational complexity theory, class NP represents all the decision problems that can be solved by a nondeterministic algorithm in polynomial time.

It is good to know that a problem that belongs to the class P, does not necessary mean that it can be solved by a deterministic program in a reasonable time. Conversely, some instances of problems of class NP can be solved by a deterministic algorithm. In the same context, we can also mention the NP-complete problems. In this class, we find the hardest problems from the NP class, which have at least the same difficulty of other problems that belong to the same class. Hence, any problem that belongs to NP class can be transformed into NP-Complete problem using polynomial reduction.

4.2.6/ Exact problem solving: deterministic approach

When solving an optimization problem, we try to explore the whole search space in order to choose the optimum. However, this is not always possible. These approaches, which are often based on tree traversing or searching algorithm, have the advantage of delivering an exact optimal solution. As an alternative of exhaustive search space exploration, other algorithms rely on problem properties to guarantee an optimal solution. For instance, simplex algorithm is a very popular algorithm for linear programming. It can traverse efficiently the convex hull of the search space to find an optimal solution. However, this algorithm is applicable on problems that are guaranteed to have this convex property.

Likewise, the Branch and Bound algorithm, is based on an implicit enumeration. The search space is divided into multiple sub-problems (separation) that are evaluated using usually a linear programming relaxation or a Lagrangian relaxation. We can also mention other approaches like dynamic programming, which usually refers to simplifying a complicated problem by breaking it into simpler sub problems using a recursive method.

Another example, the polyhedral methods can be used by adding some constraints that make the feasible region convex.

4.2.7/ Approximation methods: (Meta)heuristics

When the existing exact approaches cannot solve a problem due to very long computation time, we turn to approximation methods that often can deliver a sufficiently good solution. These approximation methods are called heuristics. The idea behind these methods is to propose an approximate solution of best possible quality in a limited time, using the special properties of the studied problem. Greedy algorithms are typical example of simple heuristics that work by making iteratively local optimum choices in the hope of finding the global optimum. This generic process is to be adapted based on the structure of the problem. This property characterizes a heuristic: it is defined based on the properties of the problem. Although a heuristic is often considered as stochastic approach, it is important to note that it can be deterministic. Metaheuristics differ from heuristics by their abstraction level. Whereas a heuristic is very problem dependent, a metaheuristic can be adapted to a very large number of different problems. For example, local search and genetic algorithms are considered as metaheuristics.

4.2.8/ Dominance and Pareto optimality

As described earlier, in multi-objective optimization, there is no one unique solution, but instead, we have a set of best trade-off solutions. The absence of total order relation between the solutions of a MOP leads to define a partial order relation between the solutions. In this context, Pareto [Pareto, 1896] proposed a hierarchical approach that allows to determine if a solution is a best trade-off. In the following definitions, we consider a maximization problem.

Definition 5: Pareto Dominance

Let z and z ∈ Z two solutions in the objective space. We say that z dominates z iff ∀i ∈ {1, 2, ..., n}, z i ≥ z i and ∃ j ∈ {1, 2, ..., n} such that z j > z j .

The relation "z dominates z " is denoted as z z . This relation of dominance is extended to the decision space: let x, x ∈ X two solutions that belong to decision space and that verify f (x) f (x ). In this case, we say that x dominates

x or x x .

Definition 6: Non dominated or Pareto optimal solution

Let z ∈ Z a solution in the objective space. We say that z is a non-dominated solution iff ∀z ∈ Z, z z. As far as that goes to the decision space, let x ∈ X a solution in the decision space, we say that x is a non-dominated solution iif ∀x ∈ X, x x. These solutions are called Pareto optimal.

Definition 7: Incomparable

Let z, z ∈ Z two solutions in the objective space. z and z are said to be incomparable iif z z and z z. This concept is extended to the decision space, we say that x and x (elements of X) are incomparable iif f (x) and f (x ) are incomparable.

Definition 8: Pareto optimal set

Based on the previous definitions, the Pareto optimal set is defined as follows:

X P = {x ∈ X | x ∈ X, x x}.
Definition 9: Pareto front Given a Pareto optimal set X P , the Pareto front is defined as follows:

Z P = { f (x) | x ∈ X P }.
* = (z * 1 , . . . , z * n ) such that z * i = max x∈X f i (x)
, ∀i ∈ {1, . . . , n}.

4.3.1.1/ Aggregation method

The aggregation method is one of the first method used to solve multi-objective problems.

Using this method, a multi-objective problem is transformed into a mono-objective problem by combining all the objective functions f i into a single objective function f generally in a linear aggregation:

F(x) = n i=1 λ i f i (x) (4.4)
Where the weights λ i ∈ [0.

.1] and

n i=1 λ i = 1.
One of the main characteristics of the aggregation method is that optimal solutions depend directly on the used coefficients. The weight vector define a hyperplane in the objective space. An optimal solution z * is the point where the hyperplane has a common tangent with the feasible space. When the feasible space is concave, many optimal solutions exit.

As we said before, the main drawback in using this method lies in the choice of the λ vector. A good knowledge of the problem is required to be able to quantify and choose the preference values for each objective.

It is good to note that fixing the λ vector, prematurely and strongly narrows the search space. This is why this method is often used with a dynamic λ. Particularly in [START_REF] Ishibuchi | A multi-objective genetic local search algorithm and its application to flowshop scheduling[END_REF], the aggregation method is used in a hybrid algorithm, mixing genetic and local search. For each parent selection, λ is regenerated randomly. Furthermore, if the objectives are not in the same scale, it is highly probable that an objective becomes over-represented or under-represented in the aggregated objective function. It is recommended that all objectives to be in the same range of values. To cope with this problem, a normalization of the objectives is recommended. Thus, the aggregated function can be modified, if it is needed, expressed as:

F(x) = n i=1 c i λ i f i (x) (4.5)
Where c i refer to the constants used to normalize the objectives. We often use the ideal point to assign values for these constants. Once the objectives are aggregated, all the approaches that can be used to classic mono-objective optimization can be used to solve the problem. For instance, local search is used in the method TPLS [START_REF] Paquete | A two-phase local search for the biobjective traveling salesman problem[END_REF],

also we can find Tabu mechanisms [START_REF] Gandibleux | A tabu search procedure to solve multiobjective combinatorial optimization problems[END_REF] and the use of the tabou method in MOTS [Hansen, 1997]. The MOSA method [START_REF] Ulungu | Mosa method: a tool for solving multiobjective combinatorial optimization problems[END_REF] is based on the simulated annealing. Finally, many genetic algorithms are also used in conjunction with the aggregation method, such as [START_REF] Yang | Evolution program for bicriteria transportation problem[END_REF] for the bi-criterion transportation problem.

4.3.1.2/ The ε-constraint method

In this approach, only one objective is chosen for the optimization process. However, constraints are applied on the other objectives to guarantee a satisfactory quality of defined objectives.

MOP k (ε)                  max z = f k (x) such that : x ∈ X s.t. f j (x) ≥ ε j , j = 1, ..., n where j k (4.6)
ε is the constraints vector for each objective:

ε = (ε 1 , ε 2 , ε k-1 , ε k+1 , ε n )
This process can be described as follows:

• Solve the problem for the main objective function f i only;

• Define the desired ε i value. It refers to the acceptable level of degradation (e.g. we want at least 80% of optimality);

• Solve the problem for the secondary objective function f j with constraint ε i on f i ;

• Define the desired ε j value. And so on . . .

We can find many studies that used the ε-constraint method. Here also the MOP is transformed into a mono-objective problem, existing approaches such as genetic algorithm, local search, etc. are frequently used.

4.3.1.3/ Goal programming

In this approach, we set an artificial point that we hope to reach in the objective space.

Thereby, the decision maker fixes the aimed goal for each objective. The initial MOP is then transformed into a mono-objective problem that integrates in its formulation the concept of the goal that we want to reach. For instance, another problem may arise to minimize the deviation from the goal. The formulation of the problems becomes:

MOP(z G )              min n j=1 f j (x) -z G j P 1 P such that : x ∈ X (4.7)
In this new formulation of the MOP, the goal is defined in z G . Here, the Tchebycheff measure is used to calculate the distance to the goal, with 1 ≤ p ≤ ∞. In the case of p = 2 the Tchebycheff measure becomes the Euclidean distance. Here also, the choice of the right parameters is crucial to have good results. A bad choice of the goal can alter considerably the obtained results. In particular, when the goal is inside the feasible region, the algorithm may find solutions that are not Pareto optimal. However, the choice of the goal depend on the decision maker and requires a very good knowledge of the problem.

Usually, the goal is fixed using the ideal point. We can find many studies that used the goal programming method such as [Coello, 1998].

4.3.2/ Non-Pareto approaches

The category includes methods that consider all the objectives in one algorithm, without transformation of the MOP into a mono-objective problem. However, unlike the Pareto approaches, which are more common, the non-Pareto approaches treat each objective separately. In this section, we present just one algorithm VEGA (Vector Evaluated Genetic Algorithm) [Schaffer, 1985], which is the first GA that is really multiobjective. In this algorithm, the selection operator is based on only one objective, independently of the others. In each generation, the population is divided into n groups where n in the number of the objective functions. Each group is evaluated according to its associated objective.

Thereby, individuals of the group i are evaluated according to the objective f i . Each individual is assigned to a group randomly in each iteration. Thus, each individual will be assigned potentially to a different group during each generation, hence it will evaluated to each objective.

The main drawback of this approach lies in the fact that each objective is treated separately. The selection of individuals is based on only one objective, which leads to choose the best individuals for this objective only. Consequently, trade-off solutions are not promoted. To cope with this problem, an approach that treats all the objectives simultaneously is necessary. Pareto approaches fall in this category.

4.3.3/ Pareto approaches

These approaches use the dominance relation in the algorithm process. Thus, solutions are not evaluated toward just one objective function; instead, they are evaluated with trade-off solutions that implies all the objective functions. Many Pareto algorithms have arisen after the introduction of the concept of the rank dominance of a solution in the first papers that discussed the Pareto [Golberg, 1989]. Since, Pareto concept implies the use of populations, we find many GA that belong to this family. However, as we will see in the next sections, Pareto approach also includes local search algorithms that are based on the concept of the Pareto, as well as hybrid algorithms. More recently, indicators based methods arise in this category. Instead of evaluating the solutions of the population, we evaluate the population itself based on the chosen indicators.

4.3.3.1/ Pareto Genetic Algorithms

The ranking operators: Since a multiobjective solution cannot be evaluated against its objective functions as we do in mono-objective problems, it is important to define a metric capable of representing the quality of a solution. Thus, several methods have been proposed and are often associated with the commonly used GA. The main three methods that are listed in [START_REF] Zitzler | Indicator-based selection in multiobjective search[END_REF] are presented below:

1. Dominance rank: for a given solution s, the dominance rank is defined by the num-ber of solutions that dominate s, incremented by 1 [START_REF] Fonseca | Genetic algorithms for multiobjective optimization: Formulationdiscussion and generalization[END_REF]. Thereby, solutions of rank 1 are non-dominated solutions. As much as the number of solutions that dominate a solution s increases, its rank is worsened. The dominance rank was originally applied in the MOGA method (Multiobjective Genetic Algorithm) [START_REF] Fonseca | Genetic algorithms for multiobjective optimization: Formulationdiscussion and generalization[END_REF].

2. Dominance count: on the contrary of the dominance rank, dominance count is the number of solutions that are dominated by the solution s. A high rank refers to a good solution quality.

3. Dominance depth: in this approach, solutions are grouped in Pareto fronts [Golberg, 1989], Non-dominated solutions in the population are assigned the value 1, and then they are removed from the population. The new non-dominated solutions are assigned the value 2, and then they are removed from the population as well. And so on, until that all the solutions of the population are assigned a value. In order to distinguish solutions that belong to the same front, we use complementary mechanisms, as we will see in the next sections. This definition of the dominance depth is used in NSGA algorithms (Non-dominated Sorting Genetic Algorithm) [START_REF] Srinivas | Muiltiobjective optimization using nondominated sorting in genetic algorithms[END_REF] and NSGA-II [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: Nsga-ii[END_REF].

N.B: It is possible to combine different dominance evaluations methods. This was done in SPEA [START_REF] Zitzler | Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach[END_REF] and SPEA2 [START_REF] Zitzler | Spea2: Improving the strength pareto evolutionary algorithm[END_REF] where the dominance depth and the rank dominance are used together. Recent research papers use new types of dominance such as ε-dominance [START_REF] Deb | Evaluating the εdomination based multi-objective evolutionary algorithm for a quick computation of pareto-optimal solutions[END_REF], or even g-dominance [START_REF] Molina | g-dominance: Reference point based dominance for multiobjective metaheuristics[END_REF].

In the following, we describe some well-known genetic Pareto algorithms.

NSGA-II (Non-dominated Sorting Genetic Algorithm) [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: Nsga-ii[END_REF] is a well known genetic algorithm often used in the literature to solve MOP. This second version of NSGA [START_REF] Srinivas | Muiltiobjective optimization using nondominated sorting in genetic algorithms[END_REF] uses two criteria to assign a fitness value for the solutions. As first step, solutions are grouped in fronts using the dominance depth [Golberg, 1989]. This first criterion reflects the quality of the solutions concerning the convergence. In a second step, each solution of each front is evaluated in terms of the density of solutions in close proximity, using the crowding distance function. This second criterion reflects the quality of the solutions concerning the divergence. Thus, NSGA-II can be characterized by:

• Rapid sorting of non-dominated solutions depending on the dominance depth.

• An estimation of the density related to the neighborhood of each solution, generally denoted crowding distance.

• Bi-level sorting: based on the dominance depth first, and then based on the crowding distance for solutions of the same front.

In this algorithm, two populations are used, one for parents P and another one for children Q, each of size N. We denote R the population that results from the union of P and Q, with |R| = 2N. Elements of each population evolve over the time, we note P t , Q t and R t , the state of each set at time t. Population are used as following:

1. Reduction of R t . Solutions of R t are distributed into the dominance fronts F i , then solutions of each front are ordered based on the crowding distance. The N best solutions, starting from the best front are preserved in P t+1 .

2. Parents selection. Parents are selected using binary tournament among the solutions of P t+1 .

3. Creation of Q t+1 . Children are generated by the means of crossover and mutation that should be defined according to the problem.

Algorithm 1, which will be used later in this thesis, formalizes these steps.

N.B: the crowding distance of a solution s is calculated as the average length of the sides of the hypercube (e.g. Figure 4.3) defined by the nearest next and previous adjacent solutions of the same front in the objective space.

Algorithm 1 Pseudocode for NSGA-II Require: Population size N, number of generations nbGen /*A time limit can replace nbGen */ 1: P ← init(N) /*initialize the population P with N random individuals */ 2: Q ← ∅ /*initialize an empty population for children */ 3: eval(P) /*eval is used for the evaluation of each individual */ 4: for i=1 to nbGen do [Talbi, 2009] SPEA2 (Strength Pareto Evolutionary Algorithm) [START_REF] Zitzler | Spea2: Improving the strength pareto evolutionary algorithm[END_REF] is an improved version of SPEA. In addition to the population P that serves to select the parents of the GA, this approach uses a complementary archive A, of fixed size, to stock N A non-dominated solutions during the search. If the number of non-dominated solutions is less than N A , the archive is completed with the best dominated solutions of the population P, based on the dominance count criterion. To do so, each solution s of the population P ∪ A is assigned a value g(s) that corresponds to the number of the solutions of P ∪ A that are dominated by s: g(s) = |{s : s ∈ P ∪ A and s s }| (4.8)

The fitness value h(s) assigned to a solution s is equal to the sum of g(s ) for each s that dominates s:

h(s) = s ∈ P∪A, s s g(s ) (4.9)
Thereby, a non-dominated solution s has h(s) = 0. On the contrary, as much as h(s)

increases, the solution s gets worse.

Although the dominance count tends to allow a certain diversity, however it privileges the intensification. To distinguish solutions having the same dominance count, SPEA2

integrates another mechanism in order to promote solutions diversity. It is an adaptation of the method of kth nearest neighbor [Silverman, 1986], where the density of a point is inversely proportional to the distance that separates it from its kth nearest neighbor. The density of a solution is described by:

D(s) = 1 σ k s + 2 (4.10)
With : σ k s being the distance that separates the solution s from its k nearest neighbor. kth is generally fixed to the value of √ N + N A , where N is the size of the population P and N A is the archive size. The global fitness value used in SPEA2 is then:

F(s) = h(s) + D(s) (4.11)
ε-MOEA (ε-MultiObjective Evolutionary Algorithm). This algorithm proposed in [START_REF] Deb | Towards a quick computation of well-spread pareto-optimal solutions[END_REF]] is similar to SPEA, with the integration of the concept of εdominance. Thereby, as in the case of IBEA that will be described in next sections [START_REF] Zitzler | Indicator-based selection in multiobjective search[END_REF], the idea is to enhance the rank dominance by adding the diversity property. The search space is divided into sub spaces, defined as hyperboxes; each con-tains at most one solution. This concept guarantees a good coverage of the search space.

Here also, two populations evolve in parallel. The population P for the genetic algorithm itself, and the archive population A to stock the non-dominated found solutions. In each iteration, two individuals a and p are selected from A and P respectively, to create k children c i , with i = 1...k. It is good to note that a is randomly selected. However, p is selected after a binary tournament selection. Children c i have the possibility to integrate both population based on different criteria. The criterion used to integrate P is the dominance in the sense of the Pareto. However, to integrate the archive, a more selective criterion is used, which is the ε-dominance.

Therefore, there are three cases for the integration of c i into P:

• If c i dominates at least one solution of P, it replaces randomly one of these dominated solutions

• If c i is dominated by at least one solution of P, it is rejected

• Otherwise, c i replaces a randomly chosen solution from P Likewise, there are three cases for the integration of c i into A:

• If c i dominates at least one solution of A, it replaces all the dominated solutions in A

• If c i is dominated by at least one solution of A, it is rejected.

• Otherwise, c i replaces a randomly chosen solution from A.

SEEA (Simple Elitist Evolutionary Algorithm) proposed by [START_REF] Liefooghe | Metaheuristics and cooperative approaches for the bi-objective ring star problem[END_REF]] is a genetic approach that does not require fixing parameters. It is particularly suited to solve problems for which the evaluation of the solutions requires little time. In this case, it has the advantage of quick convergence. In this approach, parents are directly issued from the archive A. Therefore, there is no other populations other than the archive. In each generation, N solutions are chosen randomly from A. They provide parents to undergo crossover and mutation operations. The obtained children c i are integrated in the archive based on their dominance criterion:

• If c i is dominated by an element from A, it is rejected

• If c i dominates solutions from A, it replaces all the dominated solutions in A

• Else c i is integrated into A 4.3.3.2/ Local search approaches
Unlike the GA, which are well known for solving MOP, local search approaches are less common, at least for Pareto approaches. Indeed, as we have seen earlier, the concept of Pareto supposes to have a population, which makes it particularly suitable for GA. Nevertheless, it is still possible to perform a local search; therefore, one solution will be used, on the basis of dominance relation, so through a population. Local search algorithms, in their operation mode, require a neighborhood function.

Definition 12: Neighborhood function

A neighborhood function N is a function X → 2 N , that for each solution x ∈ X, it assigns a certain number of solutions N(x) ⊂ X. Thereby, N(x) is the neighborhood of x, x ∈ N(x) is a neighbor of x.

The approaches that are based on the transformation of MOP into a mono-objective problem described earlier, can be used jointly with the archiving of non-dominated found solutions. Therefore, it will be possible to evolve the mono-objective local search according to archive construction. For instance, the weights used to combine the objective function in the aggregation method can be fixed to allow the local search to move away from the archive already constituted. In this section, we will describe only the approaches that integrates the domination concept. This class of problems is denoted as DMLS (Dominance-based Multiobjective Local Search) in [START_REF] Liefooghe | Metaheuristics and cooperative approaches for the bi-objective ring star problem[END_REF]. Approaches of type DMLS have a common characteristic of using an archive of non-dominated solutions that we aim to improve. Generally, the idea is to consider archived solutions, to explore their neighborhood, and to update the archive with new non-dominated found solutions. In this case, the archive size is variable. The algorithm stops spontaneously when the neighborhood of all the solutions is visited.

PLS (Pareto Local Search) [START_REF] Paquete | Pareto local optimum sets in the biobjective traveling salesman problem: An experimental study[END_REF] using an archive A which is initialized with a first random solution, marked as unexplored. In each iteration, a solution s ∈ A is randomly chosen between the unexplored solutions. The complete neighborhood of s is then explored, all solutions s ∈ V(s) are candidates to integrate the archive. If there is not any solution of A that dominates s , s is added to A. Every solution of A dominated by s is then removed from the archive. This local search technique is particularly prevalent to treat MOP.

4.3.3.3/ Indicator based optimization

Indicators based approaches are undoubtedly one of the main topics that are studied recently. Indicators are often used to evaluate the performance of a set of solutions, but they can also be incorporated within the algorithm itself. Approaches of this type are particularly valued since they can take the preferences of the user during the search mechanism.

Indicator based approaches can use GA or local search as described in the following.

IBEA (Indicator Based Evolutionary Algorithm) proposed by [START_REF] Zitzler | Indicator-based selection in multiobjective search[END_REF] is an indicator based evolutionary algorithm. So far, we have seen that genetic approaches based on ranking operators are very efficient in terms of intensification. However, they need complementary mechanism to improve the diversity of the solutions. Here the problem is solved when using a binary indicator I that has to be defined based on the need to the intensification and diversification in the algorithm. Therefore, I represents the goal that the algorithm aims to reach. It allows to determine, for each solution x of the population P, its contribution in order to reach the goal. Thereby, the fitness F(x) assigned to x corresponds to the contribution brought by this solution to the population. As much as its fitness increases, x is more important for the population. The formulation F(x) is:

F(x) =
x ∈P\{x} -e -I(x ,x)/k (4.12)

With k being a scaling factor.

The selection operator is a binary tournament based on the fitness F. When all the generation of the children is obtained, the population is reduced to its initial size N. This re-duction is achieved by the successive removal of the worst individuals, with fitness values being updated after each removal. Although, this method does not impose any particular indicator, in [START_REF] Zitzler | Indicator-based selection in multiobjective search[END_REF] ε-additive indicator is proposed: (4.13) This indicator calculates then the minimal translation required in order to z weakly dominates z . Anyway, it is good to note that we can use any other indicator depending on the desired effect.

I ε+ (z, z ) = max i∈{1,...,n} {z i -z i }
IBMOLS (Indicator-Based evolutionary Multi-Objective Local Search) is based on IBEA method [START_REF] Zitzler | Indicator-based selection in multiobjective search[END_REF] to define an indicator based local search, which is not imposed by the algorithm. Hence, this indicator depends on the objective that we want to reach.

IBMOLS uses an indicator I and an initial population P of size k (that can contain k random solutions). During each iteration, the complete neighborhood of each solution of P is explored. All the neighbors might be integrated into the population P. Nondominated solutions by P will be added to the population. A new added solution will remove all the dominated solutions in the population. If the population exceeds its size, we choose the worst solutions in the population and we remove them until we reach the declared size k.

IBMOLS algorithm stops when we cannot add any solution from the neighborhood of the archive.

4.3.3.4/ Hypervolume indicator based approach

The hypervolume is the most used indicator for the evaluation of multiobjective optimization algorithms. In [START_REF] Brockhoff | Analyzing hypervolume indicator based algorithms[END_REF], a detailed analysis is provided for these approaches. In this GA, the selection operator is based on the hypervolume indicator (maximization of the dominated hypervolume) combined with a sorting on the non-domination. We can also find the MO-CMA-ES (MultiObjective-Covariance Matrix Adaptation-Evolution Strategy) that is based on the mono-objective algorithm CMA-ES.

Finally, [START_REF] Zitzler | The hypervolume indicator revisited: On the design of pareto-compliant indicators via weighted integration[END_REF] proposed a methodology that allows to define a quality measure based on the hypervolume.

4.3.3.5/ Hybrid approaches

As described earlier, there are several approaches for solving optimization problems.

These approaches include mathematical programming, constraint programming, machine learning, population based meta-heuristics and single solution based meta-heuristics.

These different approaches have been used separately to solve optimization problems.

However, in the last years, hybrid metaheuristics attracts researchers for their proved efficiency in solving difficult optimization problems. So far, we have presented many methods to solve MOP. The early hybrid approaches were introduced in the nineties. They consisted of combining one of the described method with an element from another method. In this context, these methods can be classified into one of the approaches described earlier, but also to more than one approach. Moreover, it is possible to integrate a heuristic with an exact method. The hybrid approaches as well as the indicators based approaches, are very attracted to researchers. The hybridization of heuristics proved its efficiency in the mono-objective context and now it is used for MOP. When the hybridization consists of adding a local search into a genetic algorithm, often replacing the mutation operator, we call this category of algorithms memetic algorithms and that will be our contribution to the car relocation MOP.

4.4/ Multi-objective optimization for car relocation problem in one-way carsharing system

So far, we presented a greedy search algorithm for the car relocation problem in oneway carsharing system. The algorithm proves his efficiency in reducing the number of rejected demands when we compare it with an Integer Linear Programming model for the same problem. However, the comparison of these two approaches considers only one objective which is the number of rejected demands with regard to the number of jockeys used for these operations. These methods return a planning for the operations that a jockey should perform in order to reduce the number of rejected demands. A relocation planning consists of a schedule for the car relocation operations that should be done during the day.

When we solve the car relocation problem using the two approaches described earlier, we consider that a jockey is working all the day, regardless of the number of operations he is doing. However, while analyzing the planning, we notice that the schedule for some jockeys is scattered all over the day. For example, even if a jockey has to do two operations only, one at the beginning of the day and another one at the end of the day, the jockey will be counted as any other jockey that has a schedule full of relocation operations during the whole day. For that reason, when we present the solutions provided by the two developed approaches for the decision makers, we are missing one important aspect of the problem, which is the total time spent by jockeys for the relocation operations plan. Adding a new constraint for the Integer Linear Programming model makes the problem much harder and getting results for real dataset using an exact solver in reasonable time is not feasible currently. On the other hand, the results provided by the aggregated ILP model, do not show the Pareto optimal solutions. To our knowledge, there is no study that deals with the multi-objective aspect of the car relocation problem in one-way carsharing system.

Therefore, we decide to develop a Multi-Objective Optimization algorithm that tackles this problem from this perspective. For this task, we start by describing the algorithms used for solving the problem. Then, we introduce the car relocation problem from a multi-objective perspective, after that we describe the three objective functions and then we propose two algorithms to solve the problem, and finally we conclude by results and analysis.

4.4.1/ Problem formulation

In our study, we consider one-way carsharing system. In this kind of mobility services, the system has N stations. Each station has a fixed number of parking spaces. As described earlier, carsharing operators recruit employees to relocate cars between stations in order to reduce the number of rejected demands for taking a car or returning it to a station. Each car relocation operation op(i, j) starts when a jockey goes from his current location to station i where he will take a car, then it ends at a destination station j where the jockey will deliver that car, with i j. The duration of each relocation operation depends on the time needed to move between the stations. For this sake, we have a time matrix that contains the time needed to move between each pair of stations during the day based on the distance between these stations. For a carsharing system that has N stations we have N × (N -1) relocation possibilities (since moving a car from a station i to the same station i does not make sense). Then, we put all the possible combinations of operations in one array that we name OP = (. . . , op k (i, j), . . .

4.4.2/ Objective functions

In chapter 3, we presented an Integer Linear Programming model for the relocation problem. The defined objectives were aggregated in a single objective function. In the following, we recall some definitions from the ILP model described in chapter 3. For each station s ∈ S we generate T nodes to represent that station at each time t. Then we put all the S × T nodes in one row vector V = (1 1 , ..., 1 T , ..., N 1 , ..., N T ). We define a relocation activity as the action taken by the jockey to move a car from a station i to another station j. Therefore, to represent the relocation activities we generate a set of arcs in the timespace network. For each node i t in V, we construct N -1 arcs ra to represent relocation activities between station i and j, ∀ i, j ∈ S , i j, from time step t to time step t + t i j

where t i j is the number of time steps needed to go from station i to station j; we name this set RA = {..., ra(i t , j t+t i j ), ...}. We represent the available staff that will be involved in doing these activities by a set E = {1, ..., e, ..., W} where W is the maximum number of available employees.

We used six decision variables of which we mention 4 variables that we will use later in this section:

• u e : Binary variable, that takes the value 1 if the employee e is used during the day and 0 otherwise.

• rel e i t j t+t i j

: Binary variable associated with the set of relocation activities RA. It takes the value 1 if employee e has been relocating a car from station i to station j, from time step t to t + t i j and 0 otherwise.

• outR i t : Integer variable to represent the number of rejected demand to take a car out of a station i at time step t.

• inR i t : Integer variable to represent the number of rejected demand to return a car into a station i at time step t.

In this study, we present a Multi-Objective Optimization algorithm where we consider three objectives to minimize.

4.4.2.1/ Minimize the total number of remaining rejected demands: f 1 As described earlier, the relocation operations are necessary to reduce the number of rejected demands. The impact of each relocation operation a k at time t can be measured by the number of reduced or generated rejected demands ∆ a k t , ∆ a k t ∈ [-2, +2]. In the best case, ∆ a k t can reduce two rejected demands (-2 rejected demands). However, ∆ a k t can generate two rejected demands (+2 rejected demands) when we make a bad relocation decision. To calculate the total number of remaining rejected demands f 1 , we do the summation of the impact of each relocation operation ∆ a k t in each list of relocation operations L t , then we add the initial number of rejected demands R i .

f 1 = R i + L t ∈P a k t ∈L t ∆ a k t t ∈ TS (4.14)
Since the objective of the relocation operations is to reduce the number of rejected demands, we make sure to remove any operation that generates additional rejected demands.

Thus, we only keep operations that reduce the value of f 1 .

To relate to the ILP model described in chapter 3, f 1 can be expressed as follows: ), then we should increment the correspondent two elements of the array U. However, for reasons of simplicity we also increment one more element to count the time needed to move from the destination station of the current operation to the next departure station of the next operation (we fixed this value to one). When we get the updated vector U of needed jockeys at each time step, we can get the value of the second objective function f 2 by calculating the maximum value in the array U:

f 1 = ( i t ∈ V outR i t + i t ∈ V inR i t ) ( 4
f 2 = max t (u t ) ∀u t ∈ U (4.16)
To relate to the ILP model described in chapter 3, f 1 can be expressed as follows: We propose the algorithm 2 to calculate the total operation time of jockeys using the array U described earlier. It starts by the initialization of the used variables. Then, in each iteration, the algorithm calculates the operation time for a jockey and adds it to the total time. We consider that the working time of a jockey j starts when he begins his first operation t u t min of the day and ends at the arrival time of his last performed operation t u tmax .

f 2 = e∈E u e (4.
In the proposed algorithm 2, we start by looking for the first index of the first and the last operation of the day in the U vector that contains the number of operations that should be done at each time step. The difference between these two values represents the working time for a jockey. After that, we decrement the elements in U vector by 1 if u t > 0, starting from the index of the first operation until the index of the last operation. To calculate the working time w j of a jockey j, we use the formula:

w j = t u tmax -t u t min + 1 (4.18)
We calculate the total working time of jockeys by doing the summation of all jockeys working time:

f 3 = j∈ [ 1; f 2]
w j (4.19) To relate to the ILP model described in chapter 3, f 1 can be expressed as follows: ) ∀ i t ∈ V, e ∈ E, (i t , j t+t i j ) ∈ RA (4.20)

f 3 = e∈E (t
In the next two sections, we propose two metaheuristics to solve the multiobjective car relocation problem: the classical NSGA-II and a hybrid memetic algorithm as a hybrid approach. We start by NSGA-II, which will be our reference algorithm to compare the memetic algorithm that will be described after.

U[i] ← U[i] -1 10: end if 11:
end for 12: end while 13: return T ime parameter needed to be chosen a priori. It has the advantage of simplicity and good performance. This algorithm is often used as a reference to compare the performance of new algorithms. Algorithm 1 recalls the pseudo code for NSGA-II in the general case.

In the following, we will describe the genetic operators that we defined in the NSGA-II.

Firstly, we present an individual coding, then we describe the selection, crossover and the mutation operators.

4.4.3.1/ Individual Coding

A good solution representation is a key factor in developing efficient evolutionary algorithms. The encoding of the solution should enable us to ease crossover and mutation operations, as well as perform easy fitness calculation. In our case, a solution s for the car relocation problem consists of a list of relocation operations that are carried out by jockeys during each time step of the day, S = (L 1 , . . . , L T ). Each list of relocation operations L t contains the indices of the relocation operations that are necessary to reduce the number of rejected demands, L t = {. . . , k, . . . }. The size of each list L t varies between 0 and R max where R max is the maximum number of rejected demands for the whole day before starting the relocation operations. A possible representation for car relocation plan may look like as shown in table 4.1.

L 1

(1,3) (1,3) (1,2) ... L t [START_REF]Definition: Ideal point[END_REF][START_REF]Definition: Pareto Dominance[END_REF] A chromosome is composed of T genes where each gene corresponds to a list of relocation operations L t . A relocation operation is represented by its index from the array OP which is the array of all possible combinations of relocation operations. For example, the line L 1 in table 4.1 corresponds to relocation operations to do at time step 1, which are moving two cars from station 1 to station 3 and another car from station 1 to station 2.

4.4.3.2/ Crossover and selection Operators

In genetic algorithms, we use crossover operator in order to generate a new population by combining individuals from the current population between each other, in an analogy of the biological crossover. When we want to do the crossover, we have to select individuals from our population for the reproduction in the hope of obtaining new chromosome (offspring) that holds the best characteristics of both parents. There are many selection methods such as Roulette Wheel Selection (RWS), Elitism Selection, Rank Selection, Binary Tournament, etc. In our case, we use Binary Tournament, which is defined for NSGA-II as a selection operator: we select two individuals randomly from the population then we compare them. The dominant individual is selected to be the first parent. We do the same process for the second parent. Binary tournament is not a very selective method.

In that way, NSGA-II avoids the premature convergence.

When we get the pair of parents, we apply the crossover operator. Unlike the selection operator, there is no particular crossover operator defined for NSGA-II. It depends on the studied problem. In our case, we propose a hybrid method for crossover, which is a combination between two points crossover and uniform crossover as shown in figure 4.4. First, we start by randomly selecting two points for the crossover then we exchange the parts between these two points. After that, we apply the uniform crossover on the remaining parts, which consists on exchanging bits randomly between the two parents. In this way, the proposed crossover operator offers a balance between the uniform crossover that breaks the sequence of operations (high diversification) and the two points crossover that maintains a sequence bloc of operations (weak diversification). The rate of crossover application has to be defined for each problem.

4.4.3.3/ Mutation operator

After the crossover, the mutation operator is used to maintain a genetic diversity in the population by changing one or more genes to new values that we may not find in the parents genes. Usually, mutations occur according to a low mutation probability called mutation rate. In general, we have different methods to apply a mutation depending on the encoding of the solution. For example, in binary encoding, we can apply a simple mutation by inverting the selected bits as shown in figure 4.5. In our model, we use a special mutation adapted to our problem representation. For this sake, we choose two random genes from the selected chromosome then, for each selected gene, we apply our dedicated mutation operator, which consists of adding an operation if the gene does not have any operation, otherwise we randomly select an operation that belongs to this gene and we replace it by another operation selected randomly. When we add or replace a relocation operation, we check if the new operation causes new rejected demands. In this case we remove that operation. That way, the proposed mutation operation can add, replace or remove a relocation operation. We propose to choose two genes for the mutation operator in order to increase the diversification effect, since we find that mutating just one operation is not enough regarding the total number of operations.

Offspring1 after mutation: Mutation point

4.4.4/ Memetic algorithm

A memetic algorithm (MA) was introduced for the first time by [Moscato et al., 1989].

According to its definition, a MA consisted of modified version of a genetic algorithm where a local search is integrated. Hybrid approaches have proved their efficiency in solving single objective optimization problems. As a result, researchers were interested in testing the effect of metaheuristics hybridization on the solving MOP. In general, the mechanism consists on adding a local search in a genetic algorithm. The genetic algorithm plays the diversification role. It enables the algorithms to discover more zones in the research space. For every found solution, local search is used to improve its quality and therefore pushing it to the Pareto front.

In a multiobjective context, an algorithm has the role of finding the "best" possible set of non-dominated solutions. In general, Pareto set refers to the feasible non-dominated solutions that cover the entire search space. However, in real life optimization problems, it is not often easy to obtain all the solutions that belong to the Pareto front. Nevertheless, in most cases we use Pareto front when we want to describe the best found non-dominated solutions.

In the literature, there are several terms used to refer to memetic algorithms. In our work we use the MOGLS (Multi-Objective Genetic Local Search), which is used by [Talbi, 2013]. MOGLS algorithms are based on two main operators: evolutionary operator that is used to explore the search space, and local search operator that works on the improvement of the found solutions. The general scheme of a memetic algorithm is presented in Algorithm 3.

Algorithm 3 General form of a memetic algorithm MOGLS Require: N the size of the population, nbGen the number of generations /*A time limit or a any termination condition can be used to replace the nbGen */ 1: P 0 ← init(N) /*Initialize the population P with N random individuals */ 2: P 0 ← ∅ /*An empty population for children */ 3: eval(P 0 ) /*evaluate objectives for each individual */ 4: for i = 1 to nbGen do Select P i from (P i-1 ∪ P i ∪ P i ) 10: end for It is important to note that there are different methods to apply a local search in a GA. Therefore, local search can be used with a probabilistic factor just like a mutation, or when the algorithm reaches a given number of generations. Likewise, local search can be applied on every created individual. The choice of how to use the local search and how to maintain an equilibrium between the genetic operator and the local search is crucial to obtain good results.

When designing an algorithm for solving an optimization problem, it is important to study how it processes the search space based on the intensification and diversification aspects.

In a genetic algorithm, the crossover and the selection operators are considered as intensification operators while the mutation is used for diversification. However, in a memetic algorithm, roles are exchanged between mutation and crossover: the mutation operator (LS) becomes an intensification operator while the crossover operator become a diversification operator. From this perspective, a memetic algorithm can be considered as an improved version of population based local search where the crossover operator is used to diversification and the local search is used to ameliorate the found solutions.

4.4.4.1/ Genetic operator in memetic algorithm

There are many genetic approaches that are used in multi-objective context (Multi-Objective Evolutionary Algorithm -MOEA) that can be hybridized with local search approaches. SPEA and NSGA-II are frequently used for this type of hybridization [START_REF] Zitzler | Spea2: Improving the strength pareto evolutionary algorithm[END_REF], [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: Nsga-ii[END_REF]). Other approaches can be used as well, a list of these approaches can be found in [START_REF] Coello | Evolutionary algorithms for solving multi-objective problems[END_REF]. In general, MOEA constitutes a good base for applying a local search in population based MOPs. In hybrid approaches, we still find the traditional genetic operators: selection and crossover. However, the mutation operator is often used to apply the local search.

In our case, the genetic algorithm that is used as a base for the memetic algorithm is NSGA-II [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: Nsga-ii[END_REF], for its simplicity and its good performance. In the next section we will describe the local search that will be used in our memetic algorithm.

4.4.4.2/ Local search procedure to improve solutions

There are many local search metaheuristics that can be applied to solve multi-objective optimization problems. For instance, Dominance-Based Local Search Approaches [START_REF] Liefooghe | Metaheuristics and cooperative approaches for the bi-objective ring star problem[END_REF] delivers very good results for this type of problems. These approaches can be integrated in memetic algorithms. For example, M-PAES is a modified version of PAES, which is adapted to memetic algorithm [START_REF] Knowles | M-paes: A memetic algorithm for multiobjective optimization[END_REF]. However, adding a sophisticated local search metaheuristic to a genetic algorithm can make the memetic algorithm complicated in terms of implementation and execution. Hence, a simple local search algorithm combined with genetic operators can be more efficient in solving MOPs.

There are different approaches for applying a local search algorithm in memetic algorithm.

We can sequentially process each objective separately, or we can treat all the objectives together by random weighting to push the found solutions to Pareto front. In a priori optimization, decision makers can focus on the search in a sub-search space that is interesting for them. When the algorithm processes solutions during local search procedure, it might encounter new non-dominated solutions. These new solutions can be simply moved to the archived set or they can be added to the current population, however this may affect the population diversity. Other approaches just add the last found solution to the current population based on a minimal distance with the already found solutions. On the other side, it is important to choose the duration of the local search. This duration depends on the chosen approach. For instance, in some algorithms, few iterations are enough while in other approaches the local search keeps processing solutions until finding the local optimum, or based on other criteria.

In our local search procedure, the problem is turned into a mono-objective problem where the fitness value is equal to the weighted sum of the different criteria with respect to the chosen search direction, which is randomly generated and defined by the weights vector ω.

Each non dominated solution found during the local search is added to the archive. In that way, the archive is built using directly from the local search procedure. The last solution found in the local search procedure (local optimum) is added to the population used in genetic algorithm in order to be used to build the next generation.

In our case, we use a local search that belongs to the First Improvement Hill Climbing (FIHC) category. This type of local search successively accepts the first neighbor that has a better fitness. This way, a partial neighborhood exploration is done during each iteration. The algorithm stops when it cannot find any new improved solution, which is the local optimum. A local search is formally defined by the couple (Ω, V) where Ω is the set of feasible solutions (decision space) and V is the neighborhood structure V : Ω → 2 Ω that assigns for each solution s ∈ Ω a set of neighbors V(s). Therefore, the algorithm stops when the algorithm finds the local optimum s * , that is reached if and only

if ∀ s ∈ V(s * ), f (s) ≥ f (s * ).
In our case, the neighborhood of a solution s is defined as the set of solutions s that can be obtained by adding or removing an operation from the solution. In a more formal way, this relation can expressed as:

V(s) = {s | d(s, s ) = 1} (4.21)
Where d(s, s ) is the Hamming Distance between s and s . When all the operations in s and s are the same then d(s, s ) = 0. While d(s, s ) = 1 when there is one operation in difference between s and s . We also note that changing the time of operation goes into two steps: removing the operation then adding it in a different time step.

In our memetic algorithm, the local search procedure is performed through three steps as

shown in algorithm 4:

In the first step, the algorithm uses the list of the relocation operations that can decrease the number of rejected demands, obtained using the algorithm described in Policy 3 (cf.

3.5.2). The algorithm calculates the weighted fitness of the solution after adding each operation from this list until finding an improvement. The algorithm will keep any operation that improves the fitness of the solution while it disregards the others.

Then in the second step, the local search procedure calculates the weighted fitness after removing each operation of the solution. If the fitness is not improved, the algorithm restores that operation. In addition, in the third step the algorithm evaluates the fitness of the solution after changing the time of each operation (forward or backward through the time). If the fitness is not improved, the algorithm restores the old value of time.

Every time the fitness is improved, the solution is added to the archive if it is not dominated by any other solutions while all dominated solutions are removed. However, just one solution will be modified in the genetic population.

4.4.4.3/ Memetic algorithm process

In a memetic algorithm, there are three main steps:

1. Selection of parents p 1 and p 2 The main difference between this algorithm and NSGA-II, is the integration of the new function improveChildren. This function applies the local search on all the individuals of the population Q. The selection and the crossover operators are applied in the function buildChildren. However, the mutation operator is omitted since it is replaced by the local search.

4.5/ Experimentations

In the previous sections, we provided an introduction for the main approaches used to solve a multiobjective optimization problem (MOP). Solving a MOP goes through two steps. In the first step, the algorithm provides the list of non-dominated trade-off solutions. While in the second step, the decision maker choses the best solution that meets his preferences to solve the problem. In this chapter, we focus on the process of building the list of non-dominated solutions. Each solution of the Pareto set has a correspondent solution in the objectives space. When we want to evaluate an algorithm, usually we use a set of benchmark problems. In our case, NSGA-II serves as the reference algorithm for the result analysis in comparison with the proposed memetic algorithm.

4.5.1/ JMetal framework

JMetal is an open source object oriented framework based on Java for multiobjective optimization using metaheuristics [START_REF] Durillo | jmetal: A java framework for multi-objective optimization[END_REF]. This framework is provided with many state-of-the-art algorithms, benchmark problems, and different quality indicators that are used to evaluate the performance of MOP. We use this framework to develop, experiment and to study our algorithms in order to solve the multiobjective optimization carsharing problem. The framework also facilitates the development of experimental studies with special tools that are dedicated for this purpose. It also offers the feature of statistical analysis of the experimentation results. In addition, this framework allows running experiments in parallel to exploit the multi-core processors in order to reduce the execution time of the used algorithms.

The object-oriented architecture of JMetal allows an easy integration of new components or reuse of existing features. The concept is that an Algorithm solves a Problem using a SolutionSet and different Operators. Where n is the number of solutions contained in the Pareto front and d i the Euclidean distance in the objective space between each solution of the Pareto front and its nearest solution in the approximation set.

4.5.2.4/ Spread

The spread indicator measures the spread level of the solutions that belong to an approximation set according to the Pareto front. It is defined as below: The hypervolume indicator computes the volume in the objective space of the space covered by the set of non-dominated solutions A of an approximation set. This indicator is very popular in the literature since it reflects the quality of an approximation based on two criteria: diversity and convergence. In its unary form, the hypervolume is calculated based on a reference point Z re f ("anti-optimal" or nadir point) which refers to the worst possible point in the objective space as shown in the figure 4.9 where we deal with a minimization problem. A hypercube v i is formed of each solution s i ∈ A and the reference point Z re f , as diagonal corners. The hypervolume is the union of all hypercubes: problem. Thereby we can compare the relative performance of the algorithms. This is our approach for the car relocation problem.

∆ = d f + d l + N-1 i=1 d i -d d f + d l + (N -1) d ( 4
HV = volume         |A| i=1 v i         (

4.5.4/ Algorithms parameters

In our thesis, we compare two algorithms for solving the multiobjective carsharing problem: NSGA-II and memetic. We have to choose the most suitable values for the genetic parameters such as mutation probability, crossover probability and population size. A good choice of these parameters highly affect the performance of the algorithm. For this sake, we define different combinations of these three parameters then we use a class that is defined in the JMetal platform for this purpose. The concept is to launch the algorithms many times with different parameters combinations. After that, we compare the results using the values of performance indicators that are defined in the platform. The configuration that is associated with the best performance indicators values is considered to have the best parameters settings. Since the proposed algorithms are stochastic, we run our algorithms 5 times for each combination before comparing the results. After that, we compare the results of each algorithm for each configuration based on the quality indicators.

The values of the parameters that are tested together for NSGA-II and MA are shown in Therefore we test 10 levels of population, 5 levels of crossover and 6 levels of mutation probabilities. That is 300 combinations (10 × 5 × 6) tested for NSGA-II algorithm and 50 combinations (10 × 5) for the memetic algorithm, since the local search replaces the mutation for all the individuals and is applied in a systematic way to offsprings.

We start by running the NSGA-II algorithm over the 300 combinations with 5 runs for each. The average and the standard variation of the hypervolume are used to rank the performance of these different parameters combinations based on the hypervolume indicator.

The best 5 combinations are shown in table 4.4. On the other side, we run the 50 experiments of the memetic algorithm with 5 runs for each combination parameters. Here also, we rank the experiments based of the HV indicator.

The best 5 combinations are shown in table 4.5. stagnate after the 125 seconds of execution when it reaches the 0.52 level.

On the other side, we notice that the evolution of the number of solutions in both algorithms has the same trend over the time. It is also clear that sometimes the number of solutions in the archive of the NSGA-II algorithm is greater than the number of solutions in MA. However, these solutions have of lower quality as indicated by the hypervolume and as will be shown in the next paragraphs. Next, we compare the approximation sets obtained using both algorithms based on the best combination chosen for each algorithm in section 4.5.4. Since it is not easy to compare solutions of multiobjective problems in a 3-D space as shown in figure 4.11, we propose to plot each two objectives on a 2-D chart in order to make the comparison more readable.

In figure 4.12, we see a two objectives comparison between the solutions generated by Starting the thirteenth jockey, the algorithm starts to generate solutions with zero rejected demands, which is consistent with the value of the number of jockeys required to solve all the rejected demands in chapter 3 using an exact or a greedy approach.

In figure 4.13, the working time is plotted against the number of jockeys. Here also, the number of jockeys can be associated with different values of working time depending on the value of the third objective. This proves the ability of the algorithm to generate different solutions for the same number of rejected demands depending on the dedicated working time.

In the last combination of objectives, we plot the working time against the number of remaining rejected demands (figure 4.14). As we can observe, the solutions quality of MA is much better than those of the NSGA-II algorithm regarding the total working time objective. The MA can generate solutions that solve all the rejected demands using a lower value of working time. It is also important to note that even when NSGA-II uses a greater working time, it cannot go under 31 rejected demands. In this chapter, we started by an overview of the state of the art for the multiobjective optimization problems. Different approaches for solving this kind of problems are presented then we discussed the common quality indicators that are used to evaluate the performance of the multiobjective problems.

After that, we tackled the multiobjective approach for solving the one-way car relocation problem. A multiobjective approach allows the decision makers to take decisions concerning the car relocation problem based on different solutions possibilities obtained for the different objectives. We fixed three objectives that include the number of remaining rejected demands, the number of jockeys used for the relocation operations and the total time used by these jockeys. For this sake, we propose to apply two algorithms namely NSGA-II and MA. The NSGA-II is used as a reference to compare the performance of MA. To set the genetic parameters of our algorithms, we ran the algorithms for many times and for different parameter combinations, and then we choose the best combinations based on the hypervolume indicator.

General conclusion and perspectives

In this thesis, we deal with the car relocation problem in one-way carsharing system. Our work concerns the optimization of the car relocation operations in the aim of efficiently redistributing the cars over the stations with regard to user demands, which are time and space dependent. We tackle this problem using different optimization approaches. We start by presenting the physical description and a mathematical model for the problem.

Then, we develop a greedy search algorithm to solve our problem and we compare the results with an exact solver. After that, we analyze the data generated by the platform that we use to obtain the input data for our approaches. The platform is developed by our team in order to locate stations in an urban area based on surveys data and socioeconomical information. Using ANOVA and multilinear regression methods, we build a model that is able to estimate the number of rejected demands of a carsharing system based on one synthetic variable used for this purpose. Finally, we propose a multiobjective optimization approach to solve our combinatorial problem. We model the problem in the form of a multiobjective problem that we solve using NSGA-II and memetic algorithms.

5.1/ Main contributions 5.1.1/ Greedy and exact approach for solving the car relocation problem

After presenting the state of the art of the carsharing system, we did the physical description for our car relocation problem in one-way carsharing system. Then we presented an Integer Linear Programming model (ILP) for this problem. When we tried to solve our mathematical model using an exact solver (CPLEX), we observed that the solver takes a long time to deliver the solutions. To cope with this problem, we developed a greedy search algorithm for the car relocation problem. Then we present three different car relocation policies that we implement in our greedy search algorithm. The comparison between the three policies shows that car relocation operations that do not consider future demands are not effective in reducing the number of rejected demands. Our algorithm generates relocation plans in few seconds. The generated solutions using a good relocation policy are competitive with those of the exact solver. We also tested the proposed approaches by adding stochastic modification on the input data. Results prove that the robustness of the two presented approaches to solve the relocation problem is highly dependent on the input demand even after adding threshold values constraints.

5.1.2/ Data model to estimate the number of rejected demands in a carsharing system

In a previous work, our team developed a platform to locate stations for a new one-way carsharing service based on different parameter configurations. We use this platform to generate data that constitutes the input for our approaches developed for solving the car relocation problem. Our statistical model aims to study the influence of the different parameters (number of stations, number of parking spaces in each station, number of cars in the system and the average number of trips per car) on the total number of rejected demands in the system. We analyzed eleven scenarios that represent different configurations for small and medium cities. We proved that for any configuration of the given parameters (proposed by the decision maker) that fall in the range of the scenario, the number of rejected demands is predictable (with high confidence) using a statistical model built on that model. After that, we observed a common behavior for the studied scenarios. This finding pushed us to think of a unified view of the different scenarios. Using a synthetic variable, called "stressed level" that reflects the scale of the problem of the rejected demands, we build a unified model that allows the estimation of the number of rejected demands for any given combination of dimensional and operational parameters of carsharing systems in small and medium cities. This information is important for the decision makers in order to estimate the number of rejected demands and so to choose an adequate relocation strategy.

5.1.3/ A multiobjective approach for the car relocation problem

In the fourth chapter, we proposed a multiobjective approach to solve the car relocation problem in one-way carsharing system. We modeled our problem in a multiobjective form where we fixed three objectives: the number of remaining rejected demands, the number of jockeys and the total working time. A special representation has been proposed for the problem that is adopted to MOP. After that, we propose two multiobjective algorithms to solve our problem: NSGA-II and memetic. NSGA-II is used as reference to compare the performance of our memetic algorithm. In order to choose the genetic parameters for our algorithms, we ran them with different parameters combinations for many times, then we choose the best parameters that yield the best results based on the hypervolume indicator.

Once we have set the genetic parameters, we did a comparison between the performances of the two algorithms. Based on the comparison of the approximation sets generated by both algorithms, we can notice that the solutions generated by the memetic algorithm are much better than those of NSGA-II. This is proved by the results of the comparison of quality indicators calculated for both algorithms. These results show that the memetic algorithm seems to be promising to generate good multiobjective solutions for the car relocation problem in one-way carsharing system.

5.2/ Perspectives and future works

In this thesis, we tackled many aspects of the car relocation problem in one-way carsharing system. For each studied topic, different perspectives can be proposed in order to improve the quality of the proposed methods or to propose other topics that are missing in this study. Here, we propose perspectives that we consider interesting and that are compatible with our contributions in this thesis. It is important to note that it was not possible for us to obtain real data from an operational carsharing system and therefore a validation of the proposed methods with a real data is still an interesting task to do.

5.2.1/ A multiobjective approach with stochastic demand data

To evaluate the robustness of our greedy search algorithm and the exact solver, we added stochastic noise to the input data and then we compared the effect of this stochastic data variation (less than 10%). Results showed that even a minimal stochastic data variation could highly decrease the performance of tested approaches. In a future work, we aim to develop a multiobjective stochastic approach that is able to adapt itself to a defined level of stochastic data variation. Furthermore, there is a need to use the real distance when the jockey moves from the destination station of the last relocation to the departure station of the next relocation operation. A more detailed analysis for other algorithms and other network configurations is required to explore the capacity of this approach in solving the car relocation problem in one-way carsharing system.

5.2.2/ A decision support tool to choose the strategy of the relocation operations

There are two steps to solve a multiobjective problem. First, we start by generating the solutions and then, in a second step we should present these solutions in a decision tool that allows the decision makers to choose the best solutions that fit their preferences. A good decision tool allows broader sight for the decision makers so they can choose the best relocation strategy for their carsharing service. This tool should propose different relocation strategies for different periods of the day and for different number of jockeys.

The time objective can be used to change the total working time per jockey. By this way, a jockey can be recruited for full time, halftime or both of them depending on the chosen system configuration. Carsharing is a new mobility service that offers the same advantages of owning a private car without actually having to buy it. Users can have access to vehicles on the go with or without reservation. Each station has a maximum number of parking places. In one-way carsharing system, users can pick up a car from a station and drop it in any other station. The number of available cars in each station will vary based on the departure and the arrival of cars on each station at each time of the day. The demand for taking or returning cars in each station is often asymmetric and is fluctuating during the day. Therefore, some stations will accumulate cars and will reach their maximum capacity preventing new arriving cars from finding a parking place, while other stations will become empty which lead to the rejection of new users demand to take a car. Users expect that cars are always available in stations when they need it, and they expect to find a free parking place at the destination station when they want to return the rented car as well. However, maintaining this level of service is not an easy task. For this sake, carsharing operators recruit employees to relocate cars between the stations in order to satisfy the users' demands.

Our work concerns the optimization of the car relocation operations in order to efficiently redistribute the cars over the stations with regard to user demands, which are time and space dependent. In one-way carsharing systems, the relocation problem is technically more difficult than the relocation problem in bikesharing systems. In the latter, we can use trucks to move several bikes at the same time, while we cannot do this in carsharing system because of the size of cars and the difficulty of loading and unloading cars. These operations increase the cost of operating the carsharing system. As a result, optimizing these operations is crucial in order to reduce the cost of the operator. In this thesis, we model this problem as an Integer Linear Programming model. Then we present three different car relocation policies that we implement in a greedy search algorithm. The comparison between the three policies shows that car relocation operations that do not consider future demands are not effective in reducing the number of rejected demands. Results prove that solutions provided by our greedy algorithm when using a good policy, are competitive with CPLEX solutions. Furthermore, adding stochastic modification on the input data proves that the robustness of the two presented approaches to solve the relocation problem is highly dependent on the input demand even after adding threshold values constraints. After that, the analysis of variance (ANOVA) and the multilinear regression methods were applied on the used dataset in order to build a global model to estimate the number of rejected demands. Finally, we developed and compared two multi-objectives evolutionary algorithms to deal with the decisional aspect of the car relocation problem using NSGA-II and memetic algorithms.

  joined the club in 2003. Then, Sao Paulo in Brazil was the first city to start carsharing mobility service in Latin America. Recently, South Africa launched the first carsharing network in Africa in June 2015, which is called Locomute based in Johannesburg.

Figure 2 . 1 :

 21 Figure 2.1: Chronological development of carsharing [Alexander Jung, 2014]

Figure 2 . 2 :Figure 2 . 3 :Figure 2 .

 22232 Figure 2.2: Evolution of carsharing membership worldwide. (Source: Statista 2015)

. Free-floating 3 .

 3 Peer-to-peer 2.2.1/ Station-based carsharing In this model of carsharing, cars are scattered all across the city through many designated stations. Each station has a fixed number of parking spaces. Usually only round-trip reservations are allowed. Users have to return the car to the same station where they took it. Carsharing operators often provide different models of cars to fit their user needs as shown in figure 2.4. For example, in Belfort, France, the Optymo transportation network, which is operated by SMTC, handles the public transportation for individuals. It offers buses, bikes and carsharing in a complementary fashion. The offered carsharing service is station-based. In a free and simple registration, users can have access on their fleet of cars that can be found on a walkable distance in pre-defined stations in the city. There are five types of cars available for use as indicated in the figure below.

Figure 2 . 4 :

 24 Figure 2.4: Optymo fleet[START_REF] Optymo | Auto libre-service[END_REF]

  Car2go, DriveNow and Multicity are examples of free-floating carsharing services. This model can be considered as a flexible version of station-based carsharing system. Generally, in this model, users are billed to the minute and their fleets almost have one model of car. Forthese reasons, this model of carsharing is most suitable for short term rental, for young users that are familiar with technology. Free-floating carsharing grew hugely since its introduction in 2008. More than 1,450,000 members (40% of market share) are registered with free-floating carsharing services worldwide([Car2Go, 2014];[START_REF] Bmw Group | Drivenow electrifies london: Premium carsharing service extends its fleet to include the bmw i3[END_REF]

Figure 2 . 5 :

 25 Figure 2.5: An example of free floating carsharing service:Car2Go [Car2Go, 2014]

Figure 2 . 6 :

 26 Figure 2.6: Cost per VMT: When carsharing becomes more profitable[Millard-Ball, 2005]

Figure 2 . 7 :

 27 Figure 2.7: Carsharing fills the gap in the multimodal transport

  presented a hybrid forecasting model based on multilayer perceptron model neural network and Holt's model (MLP-H Filter). The model was used to forecast trips in multiple stations one-way carsharing system. The model was trained using several months of real operational data and then validated using real data from Honda ICVS. The model could forecast the net flow of vehicles in three hours rolling horizon at each station. Results showed that the MLP-H filter could increase the average forecast accuracy by 0.27 vehicles/3 hours and 0.04 vehicles/3 hours respectively from the linear Holt's model and the multilayer neural network method.

  estimated the carsharing market potential. The study took place at the university of Wisconsin-Madison in the United States. The authors used a stated preference survey technique. A survey was conducted to study the transportation habits and carsharing preferences. Based on the survey data, a set of probabilistic models were built to estimate the willingness of an individual that belongs to the university community to join a carsharing program and finally

  were looking to the main factors that affect vehicle usage and availability in Communauto carsharing network in Montreal, Québec. The study used real data provided by the carsharing operator in order to develop a multilevel regression model to analyze vehicle usage and a logistic regression model to analyze vehicle reliability. The study concluded that the size of the stations has the major impact on both variables: vehicle usage and availability. A station that has a big number of parking places can offer more car options and more places for cars. On the other side, both variables are affected by the dominant season: the availability of vehicles decreases in the summer, which required an increase in the number of cars in each station and the number of stations. The vehicle age plays an important role also in increasing the availability and decreasing the usage since carsharing users are attracted by new cars. Adding child seats had similar impact of the vehicle age, it increases availability and decrease usage. This may be explained by the demographic characteristics of carsharing users in the region of the study.[[START_REF] Morency | Typology of carsharing members[END_REF] used data mining techniques (k-means algorithm) to suggest a typology of carsharing members. Three years of continuous data from the Montreal carsharing company has been used in this study to analyze users behavior concerning their number of transactions and distance travelled. Two main types of users were depicted.

Figure 2 . 9 :

 29 Figure 2.9: A causal loop diagram for the imbalance problem[Papanikolaou, 2011]

[

  [START_REF] Nourinejad | Vehicle relocation and staff rebalancing in one-way carsharing systems[END_REF] developed a joint optimization model for car relocation and staff balancing problem in one-way carsharing systems. During car relocation operations, the balancers themselves become unevenly distributed between the stations and need to be rebalanced. This study presented a two integrated multi-traveling salesman problem formulations for both car and staff relocation problems. The study was prepared for a case study of Car2Go carsharing system in Toronto. The purpose of the study is to propose a tool that helps decision makers of carsharing system in making strategic decisions such as the staff size and the fleet size. Results showed that when the fleet cost increases the fleet size decreases unlike the staff size that increases. It was also indicated that vehicle relocation and staff rebalancing time increases when the vehicle cost increases. On the other hand, when the demand increases the fleet size increases, however staff size is less influenced.

  0 ... ...

Figure 3 . 1 :

 31 Figure 3.1: An example of a folding scooter from MIT's 'Smart Cities'

3. 5

 5 .1/ Motivation Behind the Greedy Algorithm As described earlier in section 3.4, we modeled the relocation problem as an Integer Linear Programming model. We solve the model using CPLEX 12.4 on a PC that has an Intel Core i5-3550 CPU (3.30 GHz) with 16 GB of RAM. After running the model through different configurations, we noticed that the execution time tends to increase dramatically when we increase the number of jockeys involved in the relocation operations. The execution time depends also on the number of stations, the average number of trips per car and the number of parking spaces in each station; which are factors that affect the global number of rejected user demands to get or to return a car into a station at a specified time of the day.

Figure 3 . 2 :

 32 Figure 3.2: CPLEX execution time when solving the relocation problem (18 stations, 10 places per station, 12 trips per car, 83 cars)

Policy 3 :

 3 The jockey moves one car from the station having the soonest rejected demand because it is full to the station having the soonest rejected demand because it is empty. NB: In our examples (figure 3.3 and figure 3.4), we consider that the only car movements are done by jockeys for relocation purposes.3.5.2.1/ Policy 1

Figure 3 . 3 :

 33 Figure 3.3: Simple relocation operation using Policy 1

Figure 3 . 4 :

 34 Figure 3.4: Simple relocation operation using Policy 2

Figure 3 . 5 :

 35 Figure 3.5: Flowchart of the Relocation Algorithm using Policy 3

(Figure 3 . 6 :

 36 Figure 3.6: Factors used to generate the data

Figure 3 . 8 :Figure 3 . 9 :

 3839 Figure 3.8: Comparison of the performance of the three relocation policies

Figure 3 . 10 :

 310 Figure 3.10: CPLEX VS our greedy algorithm results (18 stations, 10 places per station, 88 cars and 12 trips per car)

Figure 3 . 11 :Figure 3 . 12 :

 311312 Figure 3.11: Stochastic data variation on the number of incoming cars from 11:00 to 18:00 in one station

Figure 3 . 14 :

 314 Figure 3.13: Effects of threshold values and stochastic data on the number of remaining rejected demands

Figure 3 . 15 :

 315 Figure 3.15: Number of solved rejected demands in each hour of the day using 15 jockeys

Figure 3 . 16 :

 316 Figure 3.16: Number of remaining rejected demands when varying the jockey working hours

Figure 4 .Figure 4 . 1 :

 441 Figure 4.1: Decision space vs. Objective space

Figure 4 . 2 :

 42 Figure 4.2: Pareto dominance and Incomparable solutions

Figure 4 .

 4 Figure 4.2 shows a set of solutions in the objective space. Red squares represent nondominated solutions (in the case of a maximization problem with objectives f 1 and f 2 ), while blue squares stand for dominated solutions. Starting from the blue square in the center, the gray box contains solutions that are dominated by that solution while the green box contains solutions that dominate it. In this figure, we can see two virtual points, which are frequently used:

  ) /* by rank, and then by crowding distance in each rank */ 11: P ← P[0 : N] 12: Q ← buildNextGeneration(P) /* Binary Tournament Selection, Recombination and Mutation */ 13: end for

Figure 4 . 3 :

 43 Figure 4.3: Ranking method in NSGA-II[Talbi, 2009]

  17

) 4 . 4 . 2 . 3 /

 4423 Minimize the total working time of jockeys: f 3

Figure 4 . 4 :

 44 Figure 4.4: Crossover operation

Figure 4 . 5 :

 45 Figure 4.5: Mutation operation

2 . 3 . 4 Figure 4 . 6 :Algorithm 5

 234465 Figure 4.6: Selection and crossover followed by a local search

Figure 4 .

 4 7 shows the class diagram of the jMetal 4.5.2.2/ Generational Distance (GD)The generational distance indicator was proposed by[Van Veldhuizen et al., 1998]. This indicator measures the average distance (in objective space) between the approximation set and the Pareto front as shown in the equation 4.23. The smaller the value of GD is, the better the approximation is. When all the approximation solutions are found in the Pareto front the value of GD is 0. n being the number of solutions contained in the approximation set and d i the Euclidean distance in the objective space between each solution of the approximation set and its nearest solution in the Pareto front. 4.5.2.3/ Inverted Generated Distance (IGD) IGD is a modified version of GD where this indicator calculates the average distance between the Pareto front and the approximation set instead of the average distance between the approximation set and the Pareto front.

  .25) Where d i is the distance between two adjacent solutions, d is the average value of these distances, d f and d l are the Euclidean distances between the extreme solutions of the Pareto front and the approximation set. A spread value of zero refers to an ideal distribution.

Figure 4 . 8 :

 48 Figure 4.8: Distances from extreme solutions[START_REF] Durillo | jmetal: A java framework for multi-objective optimization[END_REF]

Figure 4 . 9 :

 49 Figure 4.9: Hypervolume indicator (HV)

Figure 4 . 10 :

 410 Figure 4.10: Hypervolume indicator (HV)

  NSGA-II and those generated by the MA. The number of rejected demands is plotted against the number of jockeys. As we can see, most of the solutions obtained with the MA dominate the solutions obtained using NSGA-II algorithm. As shown, the same number of jockeys may be associated with different number of rejected demands. Obviously, this can be explained by the fact the third objective is not shown. The lowest values of remaining rejected demands for each number of jockeys are associated with the highest values of working time for this number of jockeys. The comparison also shows that MA succeeds to generate solutions that cover the best values for the rejected demands objective.

Figure 4 . 11 :

 411 Figure 4.11: Solutions in 3-D space

Figure 4 . 12 :Figure 4 . 14 :Figure 4 . 13 :

 412414413 Figure 4.12: Number of rejected demands according to the number of jockeys

5. 2 . 3 /

 23 An enhanced data model to estimate the number of rejected demands When analyzing the number of rejected demands generated by our platform for different configurations of carsharing system, we could build a statistical data model that can estimate (with high confidence) the number of rejected demands for any combination of operational and dimensional parameters. These parameters include the number of stations, the number of parking places per station, the number of cars and the average number trips per car. The chosen values for these parameters should be limited in the same range of the values defined in the tested scenarios in our study. In a future work, we aim to expand our model to include the number of jockeys involved in the relocation operations and the total working time allocated for the relocation operations. The new model can be integrated in the decision tool so the decision makers can estimate the number of rejected demands for any combination of parameters described earlier in addition to the choice of the number of jockeys and the total allocated time for the relocation operations. Putting these features together in addition to a good graphical simulation tool can offer an excellent decision tool for the carsharing decision makers.Document generated with L AT E X and: the L AT E X style for PhD Thesis created by S. Galland -http://www.multiagent.fr/ThesisStyle the tex-upmethodology package suite -http://www.arakhne.org/tex-upmethodology/ Abstract:

  As described earlier, carsharing is a new mobility service that offers the same advantages of owning a private car without actually having to buy it. Carsharing operators maintain a fleet of cars that are available for use to their members who usually pay yearly registration fees, a monthly membership and are billed on the usage according to time spent and

3

shows the number of vehicles (in thousands) used in carsharing market worldwide. We can also see that the number of vehicles involved in carsharing has highly increased since 2006.

2.2/ Carsharing models distance traveled. What makes the carsharing more convenient is that members do not have to care about insurance, maintenance and even fuel price, which are included in the usage fees and shared between all members. Usually carsharing companies provide a short-term car rental. Members can have access to vehicles on the go or according to a reservation in advance via telephone, smartphones or website; cars are available 24 hours a day, 7/7. The fleet of cars is usually spread in a way that every potential member can have a car in his neighborhood at a convenient walkable distance.

table 2 .

 2

			2.
		207+ Megane Bipper 508 308CC
	Hour fees (euro)	1	1	1	2	2.5
	Km fees (euro) 0.20	0.20	0.20 0.30	0.35

Table 2 . 2 :

 22 Optymo carsharing usage fees

Table 2 . 3 :

 23 Impacts of carsharing in Europe and North America[START_REF] Cohen | Worldwide carsharing growth: an international comparison[END_REF]

  published a study that uses the stated-preference survey technique (SP) and transport demand modelling to analyze and forecast the choice of travel mode of the urban commuters in Palermo, Italy. Almost 500 respondents participated in the survey that contained a stated preference if four different transportation alternatives: public transportation, private car, carsharing and car pooling. A random utility model was developed based on this data. The study estimated that the carsharing use would increase up to 10% in the future if policies of limiting private transport use will be applied.

  presented a new approach for trip pricing in one-way multiple stations carsharing network. Authors developed a mixed integer non-linear programming (MINLP) model, which is called Trip Pricing Problem for One-Way Carsharing Systems (TPPOCS). The model aims to set the best trip prices in order to maximize the profit. It

has been solved using an iterative local search metaheuristic. The proposed metaheuristic was applied on a theoretical carsharing network of 75 stations in Lisbon (Portugal). Authors stated that the model could be applied on different carsharing network sizes. Results

Table 3 .

 3

1: Number of Available Cars

Table 3 . 2 :

 32 Number of Requests for Departing Cars

Table 3 . 3

 33

: Number of Requests for Arriving Cars number of rejected demands to return a car because a station is full inR i t for each time step. In this example, we consider that the maximum number of parking spaces is five. It is obvious that the values in these 5 tables must be non-negative. The input for the system consists of the initial number of available vehicles at t = 0 and the values in Table

3.2 and Table 3.

3. While all other values are calculated based on the aforementioned input. To calculate the number of available vehicles we use this equation:

Table 3 . 5 :

 35 Number of Rejected Demands Because a Full Station

  to calculate the number of available vehicles at each station at each time step. It depends of the number of available vehicles in the previous time step, the number of vehicles moving in/out of the station by the customers and the number of vehicles relocated in/out of the station by the employees. Constraint(3.6) is used to make sure that the number of available vehicles at a station cannot be greater than the capacity

	of the station. Constraints (3.7) and (3.8) ensures that the number of rejected demands at
	a station cannot exceed the demand itself. Constraints (3.9)-(3.12) force their variables
	to take binary values, while constraints (3.13)-(3.15) make sure that their variables are
	non-negative.

  To give an idea about a real problem size, let's take the example of Autolib' that we mentioned in chapter 2. Autolib' is a carsharing company that offers one-way trips in Paris, France since 2011. In March 30 2015, Autolib' had 3239 electric cars distributed on 937 stations and 78648 members. Autolib' is considered as one of the largest one-way carsharing system in the world. If we consider that the Autolib' recruits 40 jockeys and 900 stations, the problem will have the following number of variables:

	• 846,734 binary variables
	• 5,184 integer variables
	900 × 96 = 86, 400
	• the size of av i t is: |S | × |T |
	900 × 96 = 86, 400

18 × 96 × 14 = 24, 192 • the size of move e i t j t+t i j is: |S | × (|S | -1) × |T | × |E| for the worst case where all t i j = 1 18 × 17 × 96 × 14 = 411, 264 • the size of rel e i t j t+t i j is: |S | × (|S | -1) × |T | × |E| for the worst case where all t i j = 1 18 × 17 × 96 × 14 = 411, 264

• the size of outR i t is: |S | × |T | 18 × 96 = 1, 728 • the size of inR i t is: |S | × |T | 18 × 96 = 1, 728 • the size of av i t is: |S | × |T | 18 × 96 = 1, 728

As a summary, for this example, the problem has: • the size of u e is: |E| = 40 • the size of wait e i t i t+1 is: |S | × |T | × |E| 900 × 96 × 40 = 3, 456, 000 • the size of move e i t j t+t i j is: |S | × (|S | -1) × |T | × |E| for the worst case where all t i j = 1 900 × 899 × 96 × 40 = 3, 106, 944, 000 • the size of rel e i t j t+t i j is: |S | × (|S | -1) × |T | × |E| for the worst case where all t i j = 1 900 × 899 × 96 × 40 = 3, 106, 944, 000 • the size of outR i t is: |S | × |T | 900 × 96 = 86, 400 • the size of inR i t is: |S | × |T |

table 3

 3

	Scenario 1	Scenario 2	Scenario 3	Scenario 4	Scenario 5

.6, table

3.7 and table 3.8

. S × P refers to the total number of parking spaces for all stations. Likewise, M × V refers

  .6: Scenarios for small cities

		Scenario 6
	Factor	P M S	V
	Level 1 10 4 16 50
	Level 2 20 11 29 104
	Level 3 30 18 42 158

Table 3 . 7 :

 37 Scenario for intermediate city

	Scenario 7		Scenario 8		Scenario 9		Scenario 10		Scenario 11
	Factor P M S	V	P M S	V	P M S	V	P M S	V	P M S	V
	Level 1 4 3 70 200 10 8 23 107 6 6 70 300 10 6 18 83 10 3 30 100
	Level 2 7 6 80 225 11 9 26 120 9 12 80 325 20 12 30 120 20 12 60 185
	Level 3 10 9 90 250 12 10 29 133 12 18 90 350 30 18 42 157 30 21 90 270

Table 3 . 8 :

 38 Scenarios for medium cities

Table 3

 3 .9 shows a part of the design of experiments plan for scenario 4.

	P M S	V Rejected Demands
	7 5 18 80	72
	8 5 18 80	58
	9 5 18 80	51
	7 6 18 80	88
	8 6 18 80	77
	9 6 18 80	64
	.	.	.	.	.
	.	.	.	.	.
	.	.	.	.	.
	7 7 22 100	178
	8 7 22 100	156
	9 7 22 100	141

Table 3 .

 3

9: Design of experiments plan of scenario 4

Table 3 .

 3 .10 summarizes the results of the performed analyzes and the reproducibility test (ANOVA) for scenario 4.

	Factor	Effect on the	Effect	%:	cumulative	Degree	Variance	Observed	F-Test,	Test
		average (α 0 )	on the	S S /S S T	%	of Free-	of fac-	repro-		90%
		= 96.69	vari-			dom :	tor	ducibility	confi-
			ability			DF	(MS ):	level	(FS	dence
			(S S )				S S /DF	test):MS /MS E
	a (=p)	-14.13 (=α 1 ) 10780.91 8.44	8.44	1	10780.91 161.95		2.78	significant
	b (=m)	36.65 (=α 2 )	72526.69 56.80	65.24	1	72526.69 1089.47		2.78	significant
	c (=s)	-11.48 (=α 3 ) 7118.52 5.57	70.81	1	7118.52 106.93		2.78	significant
	d (=v)	22.69 (=α 4 )	27789.35 21.76	92.58	1	27789.35 417.44		2.78	significant
	ab	-2.89 (=α 5 )	300.44	0.24		1	300.44	4.51		2.78	significant
	ac	2.53 (=α 6 )	230.03	0.18		1	230.03	3.46		2.78	significant
	ad	-3.97 (=α 7 )	568.03	0.44		1	568.03	8.53		2.78	significant
	bc	-1.53 (=α 8 )	84.03	0.07		1	84.03	1.26		2.78	not significant
	bd	9.75 (=α 9 )	3422.25 2.68		1	3422.25 51.41		2.78	significant
	cd	-2.44 (=α 1 0) 215.11	0.17		1	215.11	3.23		2.78	significant
	Error		4659.93 3.65		70	66.57(MS E )
	Total	S S T	127695.28 100		80

10: ANOVA table for scenario 4

Table 3 .

 3 11: Correlation coefficient between the experiments and the models

		Sc1 Sc2 Sc3 Sc4 Sc5 Sc6 Sc7 Sc8 Sc9 Sc10	Sc11
	Sc1	1 0.95 0.95 0.91 0.9 0.92 0.89 0.89 0.83 0.9478 0.8966
	Sc2	1	0.87 0.88 0.87 0.86 0.82 0.85 0.93 0.9481 0.9291
	Sc3		1	0.89 0.83 0.89 0.87 0.84 0.74 0.9046 0.8217
	Sc4			1	0.86 0.92 0.94 0.9 0.78 0.9246 0.8392
	Sc5			1	0.97 0.92 0.94 0.84 0.9406 0.9223
	Sc6			1	0.97 0.93 0.79 0.9564 0.9126
	Sc7			1	0.95 0.74 0.9088 0.8305
	Sc8			1	0.8 0.8951 0.8386
	Sc9			1	0.8918 0.9059
	Sc10			1	0.9626
	Sc11			1

Using the model obtained for each scenario to predict the rejected demands for any combination of variable values is possible. The only condition is to choose the value of the variables in the range of the chosen factors levels in each scenario.

Table 3 .

 3 13: Scenario 4 with the new variable X

	Sc1
	Sc2
	Sc3
	Sc4
	Sc5
	Sc6
	Sc7
	Sc8
	Sc9
	Sc10
	Sc11
	y=x+1
	y=x-1
	Linear (Sc1)
	Linear (Sc2)
	Linear (Sc3)
	Linear (Sc4)
	Linear (Sc5)
	Linear (Sc6)
	Linéaire (Sc7)
	Linear (Sc8)
	Linear (Sc9)
	Linear (Sc10)
	Linear (Sc11)
	Linear (y=x-1)
	Linear (y=x-1)

Figure 3.7: Standardized representation of results vectors with their respective trendlines

This observation justifies the building of a single model that relates the different polynomial models obtained earlier to establish a unified model. We build this model using the variable "stress level" described earlier. Each scenario is thus no more represented by its 4 variables and 3 levels, but only by the three levels corresponding to the stress level variable. The table below summarizes the values of this new variable for scenario 4.

Table 3 .

 3 15: α i as a function of β i

				α 0	α 1	α 2	α 3	α 4	α 5	α 6	α 7	α 8	α 9	α 10
	β 0	I		-100664.80 40457.36 -77948.10 45453.45 -51568.11 30137.92 -8696.45 11836.62 37555.14 -35651.89 4523.31
	β 1	X 1	-4384.63	1313.51	-2586.70	1540.19	-1794.76	1028.29	-311.52	337.36	1240.02	-953.70	32.79
	β 2	X 2	126194.32 -49529.56 95799.14 -55424.16 62953.03 -37108.70 10688.67 -14275.37 -45730.89 42768.31 -5198.17
	β 3	X 3	-13055.15	4373.16	-8737.62	4693.75	-5031.18	3400.42	-965.79	976.76	3789.08	-2764.53	-62.25
	β 4	X 1 X 2	-32756.23 14198.52 -29400.50 17342.73 -18891.65 10263.32 -2705.10 4034.24	14240.17 -14444.58 1763.46
	β 5	X 1 X 3	12244.75	-5505.06 11777.39 -7015.33	7539.33	-3924.61	996.24	-1565.12 -5739.19	6021.72	-740.79
	β 6	X 2 X 3	-24914.81 11176.13 -24166.38 14109.28 -14752.59 7953.67 -1954.23 2953.44	11485.33 -11738.15 1079.88
	β 7	X 1	2	7528.34	-3205.55	6605.26	-3928.40	4297.70	-2320.96	618.94	-912.82	-3226.77	3240.26	-400.86
	β 8	X 2	2	-7951.85	2057.94	-1667.48	886.43	-2276.81	1899.91	-849.93	922.77	893.33	-222.45	468.28
	β 9	X 3	2	7658.76	-3300.17	7130.32	-4097.10	4253.41	-2373.10	587.57	-835.08	-3324.44	3282.03	-239.54
	β 10 X 1 X 2 X 3	4348.65	-1756.14	3385.61	-1969.93	2267.44	-1309.26	376.12	-526.88	-1632.92	1589.64	-227.86

Table 3 .

 3 16: Two new scenarios for validation is observed with all configurations already processed and analyzed (See table3.17).

		P	8	9	10 Total number of parking spaces	184	234	290
	SC new1	M 8 S 23	9 26 29 10		Total number of trips (M × V)/(P × S )	800 4.3478 4.2308 4.1379 990 1200
		V 100 110 120			X			X 1	X 2	X 3
		P	4	6	8	Total number of parking spaces	80	150	232
	SC new2	M 3 S 20	5 25 29 7		Total number of trips (M × V)/(P × S )		180 2.25	325 2.1667 2.1121 490
		V 60	65 70			X			X 1	X 2	X 3
		SC1	SC2		SC3	SC4	SC5	SC6	SC7	SC8	SC9	SC10 SC11
	SC new1 0.9265 0.8632 0.9133 0.8885 0.9558 0.9726 0.9365 0.9219 0.7650 0.9361 0.8814
	SC new2 0.9107 0.8511 0.8943 0.8556 0.9573 0.9583 0.9140 0.9157 0.7655 0.9197 0.8673

These two new scenarios are presented in table 3.16.

The obtained results are compared to those of other scenarios. A good overall correlation

Table 3

 3

.17: Correlation of the new scenarios with the old ones 3.6.3.2/ Summary of data analysis

Number of incoming cars Time of the day Number of incoming cars in the original data Number of incoming cars after adding 10% stochastic variation

	14
	12
	10
	8
	6
	4
	2
	0
	11:00	11:15	11:30	11:45	12:00	12:15	12:30	12:45	13:00	13:15	13:30	13:45	14:00	14:15	14:30	14:45	15:00	15:15	15:30	15:45	16:00	16:15	16:30	16:45	17:00	17:15	17:30	17:45	18:00

  ). Each element of OP has an index k that refers to one relocation operation, k ∈ [1, N × (N -1)]. Relocation operations can take place at different times of the day. In our study, we represent a day by T time steps TS = {1, . . . , t, . . . , T } where each time step t lasts for 15 minutes.

  .15) 4.4.2.2/ Minimize the number of jockeys involved in the relocation operations: f 2To calculate the number of jockeys needed to reduce the rejected demands, we create an array of integers U to count the number of jockeys involved in relocation operations during each time step. We refer to this array by U = u 0 , . . . , u t , . . . , u T . As aforementioned, a jockey starts a relocation operation at the departure time t and finishes it at the arrival time to the destination station at time t+t i j where t i j is the time needed to move from station i to station j. For each accomplished relocation operation, we increase the correspondent u t values in the range [t, t + t i j ]. For example, if a jockey starts a relocation operation at time t = 1 and he needs two time steps to arrive to the destination station (t i j

  4.4.3/ NSGA-II for the car relocation problemAlthough there are many genetic algorithms that can be used in a multi-objective context, NSGA-II is considered a very popular non-dominated sorting genetic algorithm for solving MOP. It is an improved version of NSGA that integrates elitism and with no sharing Algorithm 2 Calculation of the total working time of jockeys Require: U /*U is a vector that contains the number of jockeys needed for the relocation operations during each time step */ 1: T ime ← 0 /*Set total time to 0 */ 2: t u t min = 0 /*Set initial value for t u t min */ 3: while t u t min -1 do

	4: 5:	t u t min ← index of first occurrence of u t 0 /* -1 if no value found */ t u tmax ← index of last occurrence of u t 0 /* -1 if no value found */
	6: 7: 8:	T ime ← T ime + (t u tmax -t u t min ) + 1 for i = t u t min to t u tmax do if U[i] > 0 then
	9:

Table 4 . 1 :

 41 Representation of a carsharing plan during a day

	(6,5) (2,4) (3,7)
	...
	L T -1 (2,6)
	L T

table 4

 4

	.3.
	Population Crossover Probability Mutation Probability
	2000	1	0.6
	1500	0.9	0.5
	1000	0.8	0.4
	500	0.7	0.3
	300	0.6	0.2
	200		0.1
	100
	50
	25
	10

Table 4 . 3 :

 43 Tested values of the parameters for NSGA-II and MA

Table 4 .

 4 6: Results for 5 runs of NSGA-II and memetic algorithms after two minutes and 30 seconds of running time

	NSGA-II NbSol	HV	GD	IGD	Spread Epsilon
	1	1160 0.49632 0.00304 0.00332 0.65236 0.11538
	2	1086 0.48773 0.00294 0.00344 0.64520 0.11218
	3	1076 0.50601 0.00298 0.00303 0.63196 0.12500
	4	1083 0.50165 0.00294 0.00314 0.68354 0.10700
	5	1258 0.49610 0.00276 0.00297 0.70454 0.12179
	Min	1076 0.48773 0.00276 0.00297 0.63196 0.10700
	Max	1258 0.50601 0.00304 0.00344 0.70454 0.12500
	Mean	1132.6 0.49756 0.00293 0.00318 0.66352 0.11627
	SD	77.96 0.00686 0.00011 0.00019 0.02975 0.00725
	Memetic NbSol	HV	GD	IGD	spread Epsilon
	1	1024 0.59720 0.00049 0.00143 0.64825 0.02000
	2	1023 0.59821 0.00047 0.00138 0.71926 0.02000
	3	950	0.59809 0.00048 0.00178 0.59643 0.02000
	4	973	0.59913 0.00046 0.00119 0.68447 0.01923
	5	999	0.59665 0.00046 0.00196 0.61199 0.02000
	Min	950	0.59665 0.00046 0.00119 0.59643 0.01923
	Max	1024 0.59913 0.00049 0.00196 0.71926 0.02000
	Mean	993.8 0.59786 0.00047 0.00155 0.65208 0.01985
	SD	32.18 0.00096 0.00001 0.00031 0.05070 0.00034

Definition 11: Nadir point

The nadir point, frequently denoted by z n , is composed of the worst values for each objective: z n = (z n 1 , . . . , z n n ) such that z n i = min x∈X f i (x), ∀i ∈ {1, . . . , n}.

4.3/ Metaheuristics for the multiobjective problems

There are multiple approaches proposed in the literature for solving Multi-Objective problems (MOP). These methods are classified into three main categories:

• Approaches that are based on the transformation of a MOP into a mono-objective problem. Here we can find methods that are based on the aggregation of the objective functions f i into one function f . However, this requires a good understanding of the studied problem in order to choose the desired values for the coefficient or weight of each objective function.

• Non-Pareto Approaches. In this category, all the objectives are treated separately.

• Pareto approaches: This class of algorithms treats all the objective functions at the same time, taking advantage of the non-dominance concept.

Many studies in the literature prove that Pareto approaches are generally more efficient to solve multi-objective problems. There are also hybrid approaches that offer many advantages and allow the use of the mechanisms that we can find in the classic heuristics.

In many cases, as in the mono-objective case, Hybrid approaches outperforms the pure metaheuristics, as in [START_REF] Knowles | M-paes: A memetic algorithm for multiobjective optimization[END_REF], [Jaszkiewicz, 2002], [START_REF] Deb | Controlled elitist non-dominated sorting genetic algorithms for better convergence[END_REF]. In this thesis, we use the Pareto approaches for solving the car relocation problem.

4.3.1/ Mono-Objective Transformation approaches

These approaches often offer simple methods to solve a MOP. In this case, we evade the complexity related to the decision making when we have conflicting objectives. There are methods that fall in this category like as aggregation methods, e-constraint and goal programming methods.

framework.

4.5.2/ Performance Indicators

In mono-objective optimization the evaluation of algorithms is easy since algorithms have one value for one optimal solution (maximum in case of a maximization problem and minimum in case of a minimization problem). However, this is not the case in MOP

where each solution has k values for k objectives, and each algorithm generates trade-off solutions that constitute an approximation of the Pareto Front.

4.5.2.1/ Epsilon

The epsilon indicator has been presented in [START_REF] Zitzler | Performance assessment of multiobjective optimizers: an analysis and review[END_REF]. This indicator has two versions: multiplicative and additive. In its additive version, the epsilon indicator is used to calculate the minimum translation factor ε that should be added to every solution of an approximation A in order to dominate solutions of the Pareto front. This indicator can be defined as follows:

The smaller the value of ε is, the better the approximation is. It is good to note that a normalization of the objective functions is required in order to obtain efficient results when the scale is not the same for all the objective functions.

4.5.5/ Comparison of algorithm results

In order to evaluate the performance of the multiobjective approach for the car relocation problem, we use the best combination of parameters obtained for each algorithm in section 4.5.4. The results concern a carsharing system that is composed of 18 stations with 10 parking spaces each, having a fleet of 88 cars with an average of 12 trips per car during the whole day. As we can see, the hypervolume of solutions obtained by the MA is always higher than the hypervolume of solutions obtained by NSGA-II. We can also notice that after the first two seconds only, the hypervolume of the of MA solutions has the same level of the hypervolume of solutions obtained by the NSGA-II solutions after 30 seconds of algorithm run. After that, the hypervolume related to the MA starts to stagnate after 40 seconds when it reaches the 0.6 level. While the hypervolume of the NSGA-II algorithm starts to

The comparison of the approximation sets obtained by both algorithms shows that the solutions generated by the MA are much better than the solutions generated by NSGA-II.

This observation is proved by the comparison of the different quality indicators values that are used to compare the performance of each algorithm.

Results show that the MA is promising to generate very good solutions for the multiobjective car relocation problem in one-way carsharing system. These findings are motivating to continue the research on this approach for solving the car relocation problem in order to explore the capacity of this approach and to work on a decision maker tool that facilitates the decision making for carsharing operators.

List of Algorithms