The Station Location Problem and energy aspects 

Get Complete Project Material File(s) Now! »

The Round-Trip system

Historically, the first carsharing scheme to be implemented was the round- trip system. As such, it is today the best established commercially and has been largely studied. Basically, It requires users to return vehicles to P the incoming demand in each station is sufficient to plan vehicle stocks. The user behaviour is mainly oriented to leisure and household shopping purpose [Barth and Shaheen, 2002, Costain et al., 2012].

The One-way system

One-way carsharing scheme is more flexible than round-trip. It allows users P to pick up a vehicle from a station and return it in a different one, possibly distinct from the origin. Unfortunately, this greater flexibility comes with hard operational problems due to the uneven nature of the trip pattern
P in urban areas. Indeed, empty stations exclude potential requests to be satisfied. Conversely, crowded stations do not allow an incoming vehicle to park. Thus, the system imbalance must be corrected so that vehicles can be relocated to suitable places. This problem referred as the vehicle imbalance problem is discussed thereafter. However, let notice that despite these difficulties for the operator, one-way system captures more trips than the alternative system thanks to this flexibility which is a critical factor to join a carsharing scheme [Efthymiou et al., 2012].

The Free-floating system

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

Positive impacts

As an innovative alternative to private car ownership, carsharing is a interesting trade off between distance and flexibility. On the one hand, the car provides the freedom to cover entire urban areas. Even with electric vehicles, for which the autonomy is limited, distances of more than 150 kilometres can be considered. On the other hand, the fact that cars are available on-demand relieves users from the rigidity of public transport timetables. Moreover, station-based carsharing systems aim at reducing the time spent at searching for a parking lot, which is often important in dense urban areas. In France, its contribution to the global congestion is evaluated between 5 and 10% [Certu, 2012]. As a consequence, carsharing is now considered as an attractive transportation mode filling the gap between traditional public transport and private vehicle use.
In the last decade, several authors have showed that carsharing systems have positive im-pacts on users, the transportation system and the environment. Although not all of these commonly attested benefits are documented with empirical data, next sections present substan-tial agreements about carsharing on the urban mobility, financial gains and the environment.

Urban mobility

The carsharing economic model is founded on the use of the vehicles. The cost for moving from point A to point B depends on the distance and the time the user spend on the road.
As such, carsharing infers on user behaviours, whom aligned their car usage on those criterion, and therefore provides greater incentive for members to be selective about driving. In other words, members have a heightened awareness of travel costs and tend to reduce unnecessary trips to save money. A study conducted in 2004 reports that carsharing users reduce their vehicle kilometres traveled (VKT) – or vehicle miles traveled (VMT) – by 50% after joining the organisation [Cervero and Tsai, 2004]. More recent result evaluated this decrease to 27% in 2011 [Martin and Shaheen, 2011]. Another often observed outcome of carsharing is a fall in car ownership rates. The number of vehicles per household is a half lower for carsharing users than private cars users [Martin et al., 2010, Ter Schure et al., 2012]. When carsharing responds to mobility needs, members postpone or even drop the idea of buying a new car [Martin et al., 2010, Sioui et al., 2013].
Globally, each shared vehicle is used more efficiently [Litman, 2000, Schuster et al., 2005]. Because of higher utilization rates than single-user private vehicles, they spend more time on the road and less time parked (which represent for a private car almost 95% of its total use time, as mentioned in [Certu, 2013]). A direct consequence in the medium to long-run is that parking requirements in dense areas should also decrease [Mitchell, 2010], freeing urban space. Those observations argue that carsharing decreases the number of vehicles on the road. However, the less vehicles on the road, the better the traffic fluidity is. Thus, carsharing also helps reducing traffic congestion at peak times.

Economical aspects

General costs related to car ownership are commonly split into fixed and variable expenses. According to the total distance travelled, driving habits or local parking costs, the variable costs might be very different from one car owner to the other. However, the share of fixed costs, such as the purchase price of the vehicle, its depreciation over time or insurance, still remains predominant [Cordier, 2012]. In this context, embracing a carhsharing service where the price only depends on the vehicle usage can grants its users the car mobility at interesting costs.
Nevertheless, those benefits are not relevant for every car user. Basically, the less the car is used, the more carsharing services become interesting. With respect to local costs, researches have shown that car users driving less than 10,000 kilometres per year (as much as 15,000 km/y) could save money using carsharing [Litman, 2000, Prettenthaler and Steininger, 1999].

Environmental effects

Obviously, reducing the number of cars on the road have have positive environmental effects. Results of recent survey studies seem to indicate that greenhouse gas (GHG) emissions are largely reduced [Martin and Shaheen, 2011, Firnkorn and Müller, 2011]. These results are re-inforced with the recent emergence of electric vehicles, for which CO2 emissions are largely reduced. Besides, they provide noise reduction since electric cars are quitter than thermal ones. Moreover, the reduction of parking demand can be used to reallocate the land for additional green spaces, new mixed-use development, or other community needs [Cohen et al., 2008].

Related problems

Academic literature on carsharing systems is very prolific since a couple of decades. Inspired and motivated by their recent diffusion, researchers report on a large variety of topics covering system design, system management, social characterization, logistic, etc. Approaches use both qualitative and quantitative methodologies. Addressed problems are generally segmented into the following categories [Ciari, 2012]:
• Market analysis.
• Impacts of carsharing.
• Carsharing operations and management.
Although slightly outdated, this categorization is inspired by a literature review of Millard-Ball et al. [Millard-Ball, 2005]. A complete updated overview on problems arising in such systems can however be found in the work of Jorge et al. [Jorge and Correia, 2013].
In a previous talk, we have already given an overview of the positive impacts carsharing can provide. In addition, this thesis is dedicated to optimal system design and focus more particu-larly at the optimal dimensioning and station locations. In the next chapters, we give a deeper look about current results on those particular topics. The following sections will consequently focus on market analysis and problems related to system operations and management.

Social aspects and demand modelling

Who are the users and why they use the service are probably the major addressed questions about carsharing. Most works aim at characterize and analyse members’ behaviour, so that the specific transportation demand associated to carsharing can be estimated mathematically. In the domain of transportation, this popular topic is known as the demand modelling. The outputs of such models are then used to deal with operational research problems and system management. By doing so, carsharing decision makers are endowed with accurate inputs helping the resolution of other problems more efficiently.
Unfortunately, the ability to predict the demand for carsharing still is a quite challenging and hard topic. Several reasons, manly related to the uneven nature of the demand, can explain why economists and modellers struggle to propose accurate tools [Danielis et al., 2015]. First, the carsharing demand is highly dependant on the mobility patterns, which is partly recurrent (such as home/work travels or study commuting) and partly random. Secondly, involved decisions leading to carsharing joining are many and various. In addition, they include both quantitative and qualitative criterion. They not only depends on the price, the quality, the travel time, the trip distance and comfort, but also on the supply of the other competing or complementary modes. Finally, some side effects due to the dynamics of the system itself may influence the demand. The evolution of the service quality over time (e.g. the availability of vehicles or parking places) can fluctuate the incoming demand, making its prediction even more complex.
Using statistical data and user surveys, most studies have nevertheless demonstrated im-portant tendencies. Basically, the average carsharing member has the following character-istics [Brook, 2004] [Millard-Ball, 2005] [Lane, 2005] [Zheng et al., 2009] [Costain et al., 2012] [Efthymiou et al., 2012]:
• age between mid-30s to mid-40s.
• people highly educated and environmentally aware.
• income higher than average.
Regarding the geographical aspects of carsharing, its usage is highly correlated with the use of public transports and most successful applications are running in dense urban areas [Cervero, 2003, Millard-Ball, 2005, Burkhardt and Millard-Ball, 2006]. Moreover, the accessi-bility to the stations, in terms of distance between home/work and the nearest station, is iden-tified as a critical factor to joining a carsharing system [Zheng et al., 2009, Costain et al., 2012, Efthymiou et al., 2012].
Identify the main factors which generate and influence the demand greatly contribute to give a good prediction of a carsharing service. Stillwater et al. [Stillwater et al., 2009] compared the use of carsharing vehicles to build-environment and demographic factors in the US. They concluded that the most significant variables were: the street width (−), the provision of a railway service (−), the percentage of drive-alone commuters (−), the percentage of households with one vehicle (+), and the average age of the stations (+). Signs (−) or (+) are used to indicate whether the indicator is negatively or positively related to the carsharing demand. The street width and the percentage of drive-alone commuters may not have a clear intuitive explanation at first sight although those metrics are significantly related to the level of carsharing demand. The authors postulated that street width contains informations about pedestrian environment (where narrow streets are more pedestrian friendly) and about the land use in general (narrow streets trend to denote older residential or mixed-use development) which make sense since carsharing and walking behaviour are known to be strongly related [Cervero, 2003]. The proportion of drive-alone commuters are negatively related because these people are in general already vehicle-owners. Indeed, a high level of commuting vehicles tend to signify that the neighbourhood has a poor public transit or is already provided with high-density mode amenities.
Another study conducted by Ciari et al. [Ciari et al., 2013] uses an activity-based micro-simulation model to estimate travel demand. The authors also try to understand the effects of a carsharing system on urban mobility, considering others transportation modes such as public transport, car, bicycle and walking. They suggested and evaluated a carsharing demand model using an open-source activity-based multi-agent simulator called MATSim [MATSim, 2015]. The framework simulates the daily life of individuals (agents) and produces travel demand as a side product. The system process iteratively computes transportation plans and traffic flow simulations until a relaxed state is reach. A transportation plan is a list of transportation modes deduced from a user activity-chain. Activities planned during the day by a user are selected with respect to its socio-demographic attributes. An aggregated cost function (including carsharing as a transportation mode in itself) returns a score, evaluating quantitatively the plans of each user. The agents continuously try to improve their score varying their departure time, transport modes, routes and location of some activities.
The authors led to a modal split model giving plausible results in comparison with real data – the urban area of Zurich, Switzerland. According to the access to the cars and the time dependent fee structure, the model captures the proportion of the total transportation demand that could use carsharing. Although they observed general pattern of mobility at macro-scale, the authors also pointed out that results are context specific and computationally intensive.
Actually, in most cases, studies are context specific. Trip patterns and travel behaviour can be different from one country to another since it is related to local and regional characteristics (culture, habits, etc.), making the standardization more complex. Furthermore, carsharing de-mand estimation has not so far been addressed in the literature for one-way carsharing systems, and a relevant model for such models is nowadays not available [Jorge and Correia, 2013]. This is a real challenge for the future since it’s reasonable to think that one-way carsharing systems will be increasingly present in the coming years.

The vehicle imbalance problem

In one-way systems, one of the most challenging problem deals with vehicle relocations strate-gies. Unlike round-trip models, the departure station and the arrival station are not necessary identical. As a result, the dynamics of the system may conduct to critical situations. On the one side, empty stations prevent the members to find a vehicle, whereas on the other side, full stations prevent them to park. This property induces imbalance issues to the system and a lot of efforts are made to understand the dynamics involved and find possible solutions to handle it.
A first intuitive approach for solving the vehicle imbalance problem is to consider that the operator have to do periodic vehicle relocation operations among stations. In general, carsharing operator recruit employees (also referred as jockeys) to balance the system and avoid critical situations. Some studies, using discrete event simulation models, help operators to manage their systems minimizing the available resources (such as vehicles and staff members), while maintaining certain levels of service [Barth and Todd, 1999, Kek et al., 2006, Kek et al., 2009]. More specifically, the model presented in [Kek et al., 2009] has been tested and validated using real data, a one-way carsharing company in Singapore called Honda ICVS. Proposed solutions aimed at reduce the staff cost of about 50%.
Other authors have explored the problem under the optimization methods perspective. For instance, the model proposed in [Nair and Miller-Hooks, 2011] is a stochastic mixed-integer pro-gramming (MIP) model with the objective of generating least-cost vehicle redistribution where the demand is known probabilistically. In [Smith et al., 2013], the authors find the optimal rebalancing strategy solving two different linear programs in a fluid model of the system: one in order to minimize the number of rebalancing vehicles, the other for minimizing the num-ber of rebalancing drivers (jockeys), considering that the number of waiting customers remains bounded. The authors stated that the “two objectives were aligned” and concluded that, for Euclidean network topologies, the numbers of jockeys the systems required is between 1/4 and 1/3 of the total number of vehicles.
Very recently, [Zakaria, 2015] focuses on the logistic aspects of relocation operations, in-cluding the number of jockeys, and specific day-times for relocation and shifting operations. Different relocation policies are especially studied. The better performance at minimizing the number of rejected demands was obtain using a relocation policy where jockeys can have infor-mation on the future state of the system. Those anticipations were calculated using historical data of the system and predictions. The author suggest that applying policies based on in-tuitive decisions, such as distance to stations and number of cars at stations, without taking into consideration the effect of these relocation operations on the whole system will not be very efficient in reducing the number of rejected demands.
Another innovative approach is to consider that clients can be used to relocate the vehicles through various incentive mechanisms, mainly based on rewards. Prices could be used in order to encourage users to sign up to “trip splitting” and “trip joining”, as showed in [Barth et al., 2004]. The principle is very simple: when users want to travel from a station with shortage of vehicles to another one with an excess they are prompted to share the ride in a single vehicle (trip joining), while, conversely, when they wanted to travel from a station with too many vehicles to A generator addressing the lack of data one with a shortage they are encouraged to drive separate vehicles (trip splitting). Despite the fact that this strategy effectively balances the system in theory, it relies on assumptions that may be unrealistic in practice. For instance, it’s not relevant if a majority of travellers value privacy and convenience over minor cost saving. Also, this scheme does not work if trip-joining policies make carsharing similar to carpooling, which has severe sociological barriers associated with riding with strangers, mainly for safety and security reasons [Chan and Shaheen, 2012, Correia and Viegas, 2011]). Finally, with respect to trip splitting, impossibilities could occur if users simply do not want to be divided.

A generator addressing the lack of data

As pointed out earlier, the carsharing demand is hard to model and forecast. As far as we know, there is no available model for one-way carsharing in the literature which is not context specific. Besides, operational data from carsharing operators are not accessible. Although some global indicators of the service are sometimes reported (such as the stations’ locations, the number of vehicles or the number of daily requests) no private company release the details of the registered demand, mainly for users’ confidentiality reasons.
The problems addressed in this thesis deal with the design of a one-way carsharing system. In this work, we consider the carsharing demand as an input of the addressed problems and, as such, need to be evaluated. This section presents the mechanics of a random data generator developed during the thesis. Basically, the generator produces time-dependant one-way carsharing demand among a set on randomly positioned stations. The provided data are used to evaluate the developed models proposed in the next chapters. The generator can be downloaded freely as an open-source software at [Carlier, 2015]. Figure 2.1 illustrates the main frame of the software. We hope that it could help the research community, stimulate system design implementations and provide benchmark data to compare methodologies.

Assumptions

Some data produced by the generator are time-dependant. The purpose of the generator is to provide temporal data during an average day. Carsharing demands and travel times are then defined over a 24 hours period, segmented into T ∈ N discrete time-steps. The total number of time-steps is user-settable. It can vary from 24 to 1440, representing respectively a time-step period of one hour and one minute.
The vehicle speed is assumed constant during a trip. Although congestion is not directly considered in the model, travel times are penalize during rush hours. Two weight factors (one for the morning, one for the evening) allow to extend any trip duration if it is performed during defined time windows. Finally, it is also assumed that the generator neglects the time needed for some operations. For instance, the time needed to park a vehicle, borrow it or plug it into a charging point in the case of electric vehicles are not considered.

Table of contents :

1 Introduction 
1.1 Context
1.2 Motivations
1.3 Research scope and thesis organization
2 Background 
2.1 Carsharing systems
2.1.1 Principles and brief history
2.1.2 Carsharing models
2.1.2.1 The Round-Trip system
2.1.2.2 The One-way system
2.1.2.3 The Free-floating system
2.1.3 Positive impacts
2.1.3.1 Urban mobility
2.1.3.2 Economical aspects
2.1.3.3 Environmental effects
2.1.4 Related problems
2.1.4.1 Social aspects and demand modelling
2.1.4.2 The vehicle imbalance problem
2.2 A generator addressing the lack of data
2.2.1 Assumptions
2.2.2 Station positioning
2.2.3 Demand generation
2.2.4 Outputs
2.3 Synthesis and outlooks
I The System Dimensioning Problem 
3 The System Dimensioning Problem 
3.1 Introduction : problem description
3.2 Related work
3.3 Mathematical model
3.3.1 Formal problem statements
3.3.2 Time Expanded Graphs
3.3.2.1 Set of nodes
3.3.2.2 Set of arcs
3.3.2.3 Arcs Capacities
3.3.2.4 Additional notations
3.3.3 Flows and decision variables
3.3.4 Solution and objectives
3.3.5 Mathematical program
3.4 A polynomial sub-case
3.5 Conclusion
4 Some SDP experiments 
4.1 Introduction
4.2 First experiments and scalability
4.2.1 Experimental context
4.2.2 3-pareto fontier
4.2.3 Scalability study
4.3 Working on relocation operations
4.3.1 Experimental conditions
4.3.2 Impacts on the TEG density
4.3.3 Solver computation times
4.4 Conclusion
II The Station Location Problem and energy aspects 
5 The Station Location Problem and energy aspects 
5.1 Introduction
5.2 The Station Location Problem
5.2.1 Related work
5.2.2 Problem modelling
5.2.2.1 Decision variables
5.2.2.2 Constraints
5.2.2.3 Outputs and Solution
5.2.3 Mathematical program
5.2.3.1 The master-slave scheme
5.2.3.2 The mathematical program
5.3 Adding energy components
5.3.1 Related work
5.3.2 Selected energy components and modelling issues
5.3.3 Mathematical program
5.3.3.1 Graph transformations
5.3.3.2 Additional parameters
5.3.3.3 Variables
5.3.3.4 Mathematical program
5.4 Discussions and improvements
5.4.1 Model statements
5.4.2 Removing the symmetries
5.4.3 A greedy heuristic
5.4.3.1 Functional description
5.5 Conclusion
6 Electric battery range study 
6.1 Introduction
6.2 Experimental context
6.3 Results and analysis
6.4 Conclusion
7 Conclusion 
7.1 Addressed problems
7.2 Results and contributions
7.2.1 Mathematical models for carsharing system design
7.2.2 Experimental observations
7.2.3 Random data generator
7.2.4 Industrial decision support tool
7.3 Perspectives
General bibliography 

GET THE COMPLETE PROJECT