Keywords

1 Introduction

Carsharing systems are innovative mobility services that are increasingly becoming popular in urban and sub-urban areas and have the potential to solve real-world problems of urban transports [17]. The principle of a carsharing system is that customers can rent for limited period of times a car from a fleet of shared vehicle operated by a company or a public organisation. Although carsharing services have been proposed in the early 1970s, they have emerged as a worldwide phenomenon only in the last decade. This is due to the deployment of one-way carsharing systems in which the customers are allowed to leave the rented car at a drop-off location different from the pickup location [3]. This provides an increased flexibility for the users compared to two-way systems.

Typically, one-way carsharing systems suffer from unbalance distribution of available vehicles in the service area. Specifically, some locations can be more popular than others at different times of the day (e.g., residential areas at night-time as opposed to industrial and commercial areas at peak hours). This imbalance of demand easily results into situations in which vehicles accumulates in areas where there is a lower number of rental requests, while at the same time there is shortage of vehicles where they are more needed [5]. When this happens, the operator can resort to rebalancing policies, i.e., relocation of vehicles from where they are not needed (taking into account the expected demand in the near future) with the objective of serving more effectively the travel demands. Clearly, this has a cost for the operator, thus relocation should be performed only when economically viable.

However, before the operator resorts to rebalancing, he needs to know the optimal solution for infrastructure planning, giving the high investments costs and travel demand. In other words, he needs to determine the number, size and location of parking stations to deploy in the area where the carsharing system is supposed to operate in. In the literature, this problem is generally solved considering a spatial-temporal formulation of a MILP [1, 10]. In our previous work, we formulated a set-covering model coupled with queuing theory to guarantee certain level of service to customers [8].

Different approaches for vehicle relocation in carsharing systems exist [29]. Operator-based solutions require the use of dedicated staff for executing the redistribution tasks. On the contrary, user-based solutions rely on users willing to relocate vehicles to locations where they are needed, usually on the basis of an economic incentive. However, both approaches can be costly. Furthermore, it is still uncertain whether users are willing to accept incentives for deviations from their destinations. Finally, the design of optimisation frameworks for the decision of which vehicles to relocate to which location can become intractable due to the extremely large number of relocation variables [10].

To cope with the aforementioned issues, in this paper we suggest a user-based relocation algorithm that takes a conservative stance in order to predict the excess and deficiency of vehicles. When a customer queries the carsharing system about trip he/she desire to perform, the system reacts by verifying whether the origin station is in excess of vehicle and if the destination station is in deficiency of vehicles. In this case, the system will encourage the customer to take a second vehicle so to help at the rebalancing. The possibility to drive a second vehicle assume a new class of lightweight vehicles, called ESPRIT cars, which can be stacked, recharged and driven in a road train [13]. This is supposed caters for more efficient relocations since a single customer can relocated two vehicles at the same time.

To validate the performance of the proposed relocation strategy on a meaningful case we use the city of Lyon as case study. Specifically, we use a multi-agent simulation framework that we have previously designed [23]. It is based on MATSim, a popular open-source and agent-based traffic simulation platform, which supports dynamic traffic assignment, large scenarios and detailed modelling of transportation networks [2]. Then we set up a scenario using data from the 2015 Lyon conurbation household travel survey, which provides information about more than three million trips, and public data on the Lyon’s public transit systems. Then, we analyse the impact of the infrastructure planning strategy on the user-based relocation in terms of number of rental trips and relocation trips.

The remainder of this paper is organised as follows. Section 2 provides an overview of related literature on infrastructure planning, vehicle relocation and carsharing performance evaluation. It also introduces the ESPRIT carsharing system and the user-based relocation in such a system. Section 3 sets the methodological ground of the relocation strategies on which is based this paper. Section 4 describes the Lyon case scenario, travel demand. Section 5 discusses the simulation results. Finally, the conclusion summarizes the paper and outlines future work.

2 Related Work

2.1 Models for Infrastructure Planning

Infrastructure planning tries to determine the number, size and location of parking stations in a carsharing system in order to maximise some performance measure, such as demand coverage or profit. From a general point of view, this is an instance of the facility location problem, which is an optimisation problem extensively studied in the field of logistics and transportation planning [14].

Existing planning frameworks typically rely on time-space optimisation approaches, which are models that assume a deterministic knowledge of the demand of vehicles at each time interval of the control period. For instance, A MILP formulation is used in [1] to maximise the profits of car-sharing system, which simultaneously optimises the location of parking stations and the fleet size under several trip fare schemes. The proposed model is then used to analyse a case study in Lisbon. A recent work [10] addresses the planning of an electric car-sharing system using a multi-objective MILP model that simultaneously determines the number, size and locations of stations, as well as the fleet size taking into account vehicle relocation and electric vehicle charging requirements. More recently, new modelling approaches (eg. queuing theory and fluid models) have been proposed to take into account that the demand process of customers is stochastic and exhibits seasonal effects. For instance, a closed queuing network modelling of a vehicle rental system is proposed in [16] to derive some basic principles for the design of system balancing methods. In our previous work [8], we formulated a set-covering model that minimises the cost of deployment (in terms of number of stations and their capacity) and leveraged on queuing theory to also guarantee a pre-defined level of service to the customers (in terms of probability of finding an available car/parking space).

2.2 Relocation: State of Art

Vehicle relocation strategies can be classified into the following two broad categories: (i) user-based schemes, which incentive customers to participate in the relocation program, and (ii) operator-based schemes, which leverage on dedicated staff for relocation activities.

In [20] two operator-based strategies are simulated. The shortest time strategy relocates vehicles to minimise the travel times of staff members. The inventory balancing strategy moves vehicles from over-supplied stations to stations with vehicle shortage. In [21] an inter-programming model is developed to minimise the costs associated to staff-based relocation. A similar model is developed in [19] to maximise the profit of the carsharing operator. In [25] a stochastic MIP model is formulated to optimise vehicle relocations, which has the advantage of considering demand uncertainty. A multi-objective MILP model for planning one-way car-sharing systems is developed in [10] taking into account vehicle relocation, station deployment and electric vehicle charging requirements. The design of optimal rebalancing algorithms with autonomous, self-driving vehicles has been recently addressed in [26] using a fluidic model, and [30] using a queueing-theoretical model. An alternative approach for operator-based relocation scheme consists in selecting trips so as to reduce vehicle imbalance, for instance by rejecting trips to stations with parking shortage [1, 27].

User-based relocation policies are typically considered more convenient for the carsharing operator as they do not require the use of a staff. However, it is still uncertain whether users would be willing to participate in a rebalancing program by accepting an alternative destination or a more distant vehicle [18]. For this reason, most of the studies in this field focus on designing pricing incentive policies for encouraging users to relocate the vehicles themselves [12, 15]. Clearly, the effectiveness of these schemes highly depends on users’ participation and their willingness to accept changes of their travel behaviours.

2.3 Relocation: Stackable Vehicles

The underlying design principles of cars are rapidly evolving and the design of innovative lightweight vehicles is coming to the fore of current academic and industrial research programs. The long-term vision is to reinvent urban mobility systems by leveraging on vehicles specifically designed for city use with significant smaller spatial use and carbon footprints, as well as considerably less expensive to own and operate [24]. For instance, several concept prototypes of stackable, and foldable two-seat urban electric cars are currently under development, such as the MIT BitCar [28], or EO Smart [7]. A step forward is take by the ESPRIT European Project that is designed and prototyping a new vehicle that is stackable with mechanical and electrical coupling, and it can be driven in road trains as shown in Fig. 1.

Fig. 1.
figure 1

The architecture of an ESPRIT-based car-sharing system [13].

Full size image

ESPRIT vehicles have the potential to facilitate the deployment of one-way carsharing by also supporting more efficient operational procedures. In particular, redistribution is made easier because the vehicles can be driven in a road train. As a consequence, a single staff can drive a road train of up to eight vehicles, or users may drive a road train of two vehicles with a conventional driving license. As discussed in the previous section, one of the main hurdles for user-based relocation strategies is to encourage the users to change their destination to perform a relocation task.

With ESPRIT, we can afford a different way of user-based relocation, where operator can take advantage of actual trips and augmenting their relocation efficiency by delivering two vehicles instead of just one. However, this strategy has been proven, in the following paper, to have a low impact on the total number of carsharing trips.

2.4 Simulation of Carsharing Systems

In general, evaluating the performance of a carsharing system is a difficult task due to the complex and time-variant interplay between the demand and supply processes. Specifically, the availability of vehicles in a carsharing system is intrinsically dependent on trips that are demanded by the customers and vice-versa. In addition, there are several operational conditions that add uncertainties to the system about the future location of vehicles, such as the impact of pricing schemes impact on the decisions of individual users. Therefore, a simulation approach can be very useful to cope with operation complexities and to quickly evaluate the effectiveness of different planning and operation models.

Studies of micro-simulation for performance evaluation of carsharing system has been investigated as early as 1982 [9]. During that period, there was not yet the large panel of traffic simulation tools that are existing nowadays. Thus, the critics held by the author in [9] regarding the computational complexity and availability of data should be taken in moderation. In 1999, a queuing-based transport simulation has been proposed by [4] for the assessment of the performance of a shared one-way vehicle system. Different measures of efficiency were determined, such availability of vehicles, their distribution and energy consumption, while some relocation strategies were tested. However, the simulation model is exactly predictive and does not capture the inherent uncertainty of real world systems. A more detailed carsharing simulation model and open source was introduced by [11], where it is based on multi-modal agent-based traffic simulator, such that each agent seeks to fulfils its daily plan as a set of activities connected by legs. In our previous work, we designed a similar but more sophisticated carsharing simulator [23], in such a way to separate the carsharing mobility simulation model from the operational and demand model. The purpose is to allow users test different operational models and strategies using the same tool. We have, therefore, used this simulation model to study the performance of a new carsharing system deployed in a suburban area of Lyon.

3 Relocation Strategies

The need for vehicles relocation in carsharing systems stems from the unbalance of availability of vehicles that naturally emerges at different moments of the day. A station manifesting an excess of availability of vehicles should be leveraged to provide additional vehicles to stations manifesting a deficiency of vehicles. In this work we assume that customers are encouraged to relocate a second vehicle if they are planning to make a trip between stations with an excess and a shortage of vehicles, respectively.

Defining the metric that can be used to detect whether a station has anexcess/deficiency of vehicles is not an easy task. In principle, availability might undergo large fluctuations due to a continuous stream of pickups and drop-offs of vehicles. In principle, relocating a vehicle from/to a highly variable station may negatively interfere with the natural flow of vehicles and cause a butterfly effect in the network. On the other hand, complex availability metrics would require to have additional knowledge about the carsharing system, e.g. to predict the minimum availability of vehicles over some time interval. In the following we explore both approaches. Specifically, we first propose a set of relocation policies that only rely on a simple characterisation of the carsharing dynamics based on the instantaneous number of vehicles that are available for rent at a station. Then, we descrive a more elaborated relocation heuristic, which assumes a knowledge of carsharing demand patterns.

Before describing our proposed scheme, it is also important to point out that are several business and operational factors that can affect the effectiveness of the relocation process. As a matter of fact, a relocation task is costly, since it consumes fuel and makes the vehicle unavailable during the trip period. Furthermore, a carsharing operator might want to ensure a high availability in a certain station by contrast to others following a specific marketing strategy. In this paper, we will not dive into all these complexities of real world systems, but we assume that a relocation strategy is effective if one relocated vehicle generates at least one additional trip i.e. the fraction of additional trips over the relocation trips should be superior or equal to one, as the minimum accepted performance.

3.1 Policies Based on Current System State

First of all, we describe relocation policies that do not require to maintain the past system state, or to predict the future system state. This implies that these strategies are not influenced by the history of the carsharing system, and do not rely on a knowledge of the carsharing demand. The only information that is maintained by the carsharing operator is \(v_{i}(t)\), defined as the number of available vehicles at station i at time t, and \(p_{i}(t)\), defined as the number of available parking spaces at station i at timet. Clearly, \(p_{i}(t) = c_{i} - v_{i}(t)\), where \(c_{i}\) is the capacity of station i.

The simplest relocation strategy is the uniform policy, illustrated in Algorithm 1, which incentivises each customer to take a second vehicle to his intended destination with a fixed probability \(\gamma \). Specifically, let us assume that at time t a customer generates a request for a rental vehicle from location O to location D. The central controller of the carsharing system determines the station i that is the closest to location O with an available vehicle, and the station j that is the closest to location D with an available parking space. A relocation task is assigned to the customer with probability \(\gamma \) if and only if there are at least two vehicles available at station i and there is enough available parking space at station k to accomodate the train of two vehicles.

figure a

The second relocation strategy is illustrated in Algorithm 2, and it simply restricts the relocation task to destination stations that are empty. The rationale behind this strategy is to avoid situations in which two close booking requests can not be satisfied by a system.

figure b
figure c

The third relocation strategy is the balance policy, illustrated in Algorithm 3, in which a customer takes a second vehicle to his intended destination only if this contributes to reduce the difference in the occupancy levels of the stations. The rationale behind this strategy is to use the redistribution to equalise as much as possible the utilisation of stations. This can be mathematically expressed computing the difference between the new occupancy levels that would be due to the movement of a single vehicle or a train of two vehicles. After standard algebraic manipulations it is straightforward to show that if \(v_{i}(t) > v_{j}(t) +4\) it is always beneficial to encourage a customer to take a second vehicle with him.

3.2 Policies Based on Predicted Minimum Availabilities

As noted before, the instantaneous car availability at a station is typically highly variable. We conjecture that a more reliable parameter for guiding the relocation decision is an estimates of the number of vehicles that will not be used because they are in excess with respect to the carsharing demand. This excess of vehicles can be estimated by measuring the minimum car availability over a period of time. Specifically, let us assume that the system time is divided into time intervals of duration \(\tau \). Then, let us denote with \(\alpha ^{k}_{i}\) the minimum car availability that is expected at station i during the time interval \([k\tau ,(k+1)\tau ]\). The estimation of the minimum car availability of a carsharing system that does not perform relocation, say \(\alpha ^{k,nr}_{i}\), is straightforward as it is given by

$$\begin{aligned} \begin{aligned} \widehat{\alpha }^{k,nr}_{i}(t) = \min \left\{ v_{i}(s) : s \in [k\tau ,t]\right\} . \end{aligned} \end{aligned}$$
(1)

In Eq. (3), the function \(v_{i}(t)\) is provided by historical information. On the other hand, the relocation process changes the system dynamics and observations from a system without relocation might be quite different from the ones of the system with relocation. Thus, we decide to also compute an expected minimum availability using forecasts of the carsharing demand. More precisely, let us denote with \(\alpha ^{k,r}_{i}\) the minimum availability in the time interval \([k\tau ,(k+1)\tau ]\) based on the estimated number of vehicles that will be dropped off and picked up at station i during \([k\tau ,(k+1)\tau ]\) according to the carsharing demand, and taking into account that the initial number of vehicles is \(v_{i}(k\tau )\) and the station has finite capacity \(c_{i}\). To clarify the procedure used to estimate the minimum car availability Fig. 2 illustrates an example. As shown in the figure, we consider the sequence of expected pick-up and drop-off events to estimate the future evolution of the \(v_{i}(t)\) function. Note that we discard pick-up and drop-off events that are not feasible, i.e. pick-ups that would occur when the estimated \(v_{i}(t)\) function is equal to zero, and drop-offs that would occur when the estimated \(v_{i}(t)\) function is equal to \(c_{i}\).

Fig. 2.
figure 2

Example of \(\alpha ^{k,r}_{i}\) estimation for a station with capacity equal to 3.

Full size image

Finally, we have that

$$\begin{aligned} \begin{aligned} \alpha ^{k}_{i} = \min \left\{ \alpha ^{k,nr}_{i},\alpha ^{k,r}_{i} \right\} . \end{aligned} \end{aligned}$$
(2)

Different approaches can be used to estimate \(\alpha ^{k}_{i}\). The simplest one is to use historical information about the car availability from a carsharing system in which relocation is not used. In this case, \(\alpha ^{k}_{i}\) would simply be equal to \(\min \left\{ v_i(t) : t \in [k\tau ,(k+1)\tau ]\right\} \). However, the shortcoming of this approach is that the relocation process changes the system dynamics and observations from a system without relocation are not representative of the system with relocation. In particular, rental requests that failed in the system without relocation can be successful in the system with relocation (and viceversa). Thus, we decide to use a combination of historical data and carsharing demand forecast. Specifically, let us assume that at time t, with \(t \in [k\tau ,(k+1)\tau ]\), a customer wants to pick up a car at station i. Then, we split the computation of \(\alpha ^{k}_{i}\) into two components. The first one is \(\widehat{\alpha }^{k}_{i}(t)\), which is given by:

$$\begin{aligned} \begin{aligned} \widehat{\alpha }^{k}_{i}(t) = \min \left\{ v_{i}(s) : s \in [k\tau ,t]\right\} . \end{aligned} \end{aligned}$$
(3)

In other words, \(\widehat{\alpha }^{k}_{i}(t)\) is the exact minimum availability of station i considering only the time interval \([k\tau ,t]\) and the knowledge of the real car availability given by \(v_{i}(t)\). The second one is \(\overline{\alpha }^{k}_{i}(t)\), which represents the minimum availability in the time interval \([t,(k+1)\tau ]\) based on the estimated number of vehicles that will be dropped off and picked up from station i during \([t,(k+1)\tau ]\) according to the carsharing demand, and taking account that the initial number of vehicles is \(v_{i}(t)\) and the station has finite capacity \(c_{i}\). Finally, we have that

$$\begin{aligned} \begin{aligned} \alpha ^{k}_{i}(t) = \min \left\{ \widehat{\alpha }^{k}_{i}(t), \overline{\alpha }^{k}_{i}(t) \right\} . \end{aligned} \end{aligned}$$
(4)

Following the same line of reasoning it is possible to also estimate \(\beta ^{k}_{i}\), defined as the availability parking space availability at station i during time interval \([k\tau , (k+1)\tau ]\). Intuitively, \(\beta ^{k}_{i}\) is the complement of the maximum car availability. We are now able to define a relocation policy that leverages the knowledge of the predicted minimum car and parking space availability, which is illustrated in Algorithm 4. Clearly, first the relocation strategy checks if the relocation tasks is feasible, i.e. there are at least two vehicles available at station i and there is enough available parking space at station k to accomodate the train of two vehicles. Then, the algorithm checks a similar but more restrictive condition, i.e. relocation is feasible if also minimum car and parking space availabilities are considered.

figure d

4 Case Study

4.1 Scenario

Similarly to the work previously done in [22], we will test and validate the suggested user-based relocation strategies using the Lyon case study. The operating area of the simulated carsharing system is shown in Fig. 3, and corresponds to three suburban district of the city of Lyon. The road network is constructed from OpenStreetMap data and made of 141,795 links, not only limited to the study area with green background. Regarding the public transit systems, we used data publicly available from Grand Lyon Data platformFootnote 1 to define transit routes and modes (buses, tram, underground), transit stops, as well as schedules and vehicles capacities. One of the most important modelling task is to construct the travel demand for different transportation modes. Traditionally, travel demand data is organised as trip origin/destination (O/D) matrices, which simply contain the number of trips that are taken from an origin node to a destination node in a specific period of time. However, since we use a multi-agent modelling approach, the travel demands are constructed as individual daily plan dairies, which contain sequence of activities and the preferred transportation mode for trips between activities. As for [22], we created the demand for Lyon based on used census data from the INSEE website and uses data from the Lyon Travel Diary Survey 2015. The synthetic population representing the demand is of the order of 1.4 million agents, all of whom pass through the choice model to determine the destination and mode of trips. For this model, we considered five types of facilities: home, work, education, shopping and leisure. Such that home facility represents most of the facilities with 35,853 instance, while the remaining others make up 1549 instances. The Lyon Household and travel diary survey 2015 were used to estimate coefficients for generating the synthetic population. The records were split according to whether the synthetic person had both a driving licence and the household a car or not. The trip records were fitted to a nested mode (Car or PT) and destination choice model, and the coefficients at both levels of the nest were estimated simultaneously.

Fig. 3.
figure 3

Map of the simulated area, with blue diamond referring to the Esprit stations deployed within the study area (green background). The red and grey lines refer to, respectively, the PT and car networks [22]. (Color figure online)

Full size image

The main novelty considered in this new version of the Lyon demand comparing to the one tested in [22], is at the level of the mode choice. We introduced a “walk” mode, as well as new combinations of modes, such:

  1. 1.

    Private car (car)

  2. 2.

    Park and Ride

  3. 3.

    Public Transport (pt)

  4. 4.

    ESPRIT (no Public Transport)

  5. 5.

    ESPRIT followed by Public Transport, “ESPRIT first”

  6. 6.

    Public Transport followed by ESPRIT, “ESPRIT last”

  7. 7.

    and Walk

ESPRIT first and ESPRIT last match to the concept of first and last kilometre. These trips are of particular interest. Individual agents make travel choices according to whether they have a driving licence, and whether there is car belonging to their household. If they can drive and have access to a car then all seven modes are available, but if the household does not have a car they may still choose to use ESPRIT. The choice nest takes account of their car availability status and directs the agent through the appropriate part of the choice nest accordingly. The demand contains a total number of agents of 80.740 agents and a customer base of 6.416 agents. While the modal share as shown in Fig. 4, shows Esprit share of represents 6.7% of the modal share, while private car is leading by a modal share of 64.3%, then public transport 17.3% and finally walking mode representing 11.7% of the modal split.

Fig. 4.
figure 4

Modal share of the base demand.

Full size image

In this case study we considered a scenario where 350 vehicles were deployed in 77 stations, which are represented as diamonds in Fig. 3. The deployment was undertaken following the optimal deployment strategy introduced in [6]. However, we branched off two main variants of this scenario, so to compare the impact of the ratio of the parking slots to the vehicles on the relocation strategies. We assumed, therefore, in the first variant that each of the stations have reasonably very large parking space of 20 slots, in total 1540, i.e. a ratio slot:vehicle equal to 4.4. While in the second variant we assumed a reasonably smaller parking space of 10 slots per station, in total 770, i.e. a ratio equal to 2.2. We will see in the following why this ratio has a significant impact of the performance of the relocation strategies.

4.2 Results and Discussion

Considering the environment described above, we have executed multiple simulations with different set-ups. On one hand, we have executed two simulations with no relocation strategy activated on the two different parking slots: 1540 and 770. The goal is to obtain a reference line for deducing the performance of the relocation strategies. This reference line is represented with a straight solid line on both Figs. 5 and 8. It indicates the threshold of 100% of the number of trips without relocation, and any bar plot rising above it means that the Algorithm led to new successful bookings that have failed beforehand. Both variants of parking slots have produced roughly same number of trips: Successful bookings are dependent less on parking availability than fleet size [6].

Fig. 5.
figure 5

Comparison of relocation performance when considering the four scenarios, with respect to the ratio vehicle/parking slot. Performance is measured in terms of (1) percentage of number of trips relative to a simulation without relocation (2) percentage of trips where a second vehicle has been offered to be relocated.

Full size image

On the other hand, we run a first set-up using the different relocation strategies on the two variants of slot:vehicle ratios. The purpose is to compare the performance of each strategy and the impact of the ratio. The second set-up focused on the proposed sophisticated relocation strategy, Algorithm 4. Since this algorithm depends on the predefined bin of time per contra to other algorithms. Therefore, we have tested it on a set of time bins to observe their impact on its performance.

In order to compare between the performance of the different strategies and in different time interval, we have decided to use two metrics \(M_1\) and \(M_2\):

  • \(M_1\): the difference of trips obtained from the simulation without relocation and the one with relocation. A positive difference means that the relocation decisions allowed the booking success of new trips comparing to the simulation without relocation.

  • \(M_2\): The fraction of carsharing trips that actually served for transporting a second vehicles by the agent. The purpose is to know how many relocation trips have been required to get more successful booking trips.

Fig. 6.
figure 6

Fluctuation of the sum of 30 min average availability of vehicles of all stations, for the different scenarios and solely for the case of 1540 parking slots.

Full size image
Fig. 7.
figure 7

Comparison of the ongoing activity of all carsharing trips with carsharing trips transporting a second vehicle to be relocated and solely for the case of 1540 parking slots.

Full size image

Let us start with the graph result of first set-up shown in Fig. 5. The uniform relocation strategy S1, has scored negatively in both situations, respectively \(-4.7\%\) and \(-3.0\%\) for the metric \(M_1\). While it led to the highest number of relocation such that \(M_2 > 20\%\) of the shares of the total trips that served for relocating a second vehicle. This strategy based on uniformly distributed random numbers demonstrate that it cannot be at all a solution in dealing with the relocation problem. In addition to the fact that it can not be even used as a reference strategy with which we would measure how well our relocation strategy scores in comparison to a random behaviour.

Algorithm 2 scores quite well in the case of the large parking space variant: \(M_1 = +4.7\%\) that is more than 400 additional trips. In contrast, it required \(M_2 = 13.6\%\) of relocation trips, which is around 1300 trips. This strategy that consists in prioritising empty stations has led to a ratio of approximately 1:3. In other words, the decision maker will have to relocate 3 vehicles to ensure 1 new successful booking. This strategy is costly for the carsharing operator but it can be used as strategy with lower bound performance.

The balancing relocation strategy described in Algorithm 3 scores the highest number of additional trips in case of 1540 slots: \(M_1 = +9.4\%\). To generate the additional 900 trips, the systems had to encourage around 2000 agents to relocate a second vehicle (\(M_2 = 19.4\%\)). This is equivalent to a ratio of 1:2, one additional vehicle for 2 relocation trips. In the case of 770 slots, the score is tied: \(M_1 = +0.0\%\), while \(M_2 = 16.5\%\) is still significantly high. We conclude that the three Algorithms 1, 2 and 3 all behave quite poorly when the ratio of slots to vehicles is low.

The proposed strategy based on minimum availability outperformed the other strategies in terms of \(M_1\) to \(M_2\) ratio. Even though it has scored less than strategy S3 in the case of 1540 slots: \(M_1 = +7.0\%\). Yet the second metric has a score significantly lower than the other strategies: \(M_2 = 16.5\%\), resulting in a ratio greater than 1:1. In other words, the carsharing system will require less relocation trips to generate more additional trips, in the case of a significantly large parking space availability. In the 770 slots variants, the algorithm offer poor performance, but still positive score and 1:3 ratio way better than the other algorithms.

In addition to Fig. 5, two other comparison plots were generated and depicted by Figs. 6 and 7. The average availability figure show the slight mitigation of the availability due to the relocation algorithms. While there is a drop of average availability of only 5 to 20 vehicles when comparing with the no relocation case, the Algorithm 4 remains the one with less mitigation availability relative to the three other algorithms. This observation led us to hypothesize that the poor performance of the other algorithms was due to the unavailability of vehicles due to excessive relocation decisions. This hypothesis is supported by the plots in Fig. 7, which shows that Algorithm 4 led to less relocation activities in comparison with the other algorithms.

Fig. 8.
figure 8

Comparison of fluctuation of relocation performance when considering different time bins, with respect to the ratio vehicle/parking slot.

Full size image

The results obtained with Algorithm 4 was in the case of predefined time bin of 40 min. At each start of the interval, the algorithm classifies the stations that are expected to be in excess and deficiency of vehicles. This list is not updated until the start of the next time interval. Since the minimum availability is sensitive to the time bin, we had to test the performance of the algorithm with different time bins.

The outcomes of these simulations have confirmed that (1) the ratio slots:vehicles is a sensitive factor on the performance of the relocation Algorithm 2) larger is the time interval, more conservative is the algorithm and less relocation trips were encouraged without degrading much the \(M_1\) metric. Indeed, a quick calculation of the rate of changeFootnote 2 in both cases led to a negative slope of \(-0.03\%/\mathrm{min}\) in terms of percentage of relocation trips, meanwhile the slope is no less than \(-0.01\%/\mathrm{min}\) (even positive in case of 770 slots) for the percentage of additional trips.

5 Conclusion

We have seen in this article how it is possible to achieve positive relocation performance, if the customer is encouraged to transport a second vehicle with him/her. This will be possible thanks to the ESPRIT model where it seeks to design stackable vehicles that can be driven in train of two by a customer with a car driving license. We have demonstrated that with a proper demand model and the right station deployment and parking slots to vehicles ratio, we can ensure a positive relocation performance with a ratio greater than 1:1, that is at least one additional trips is generated when relocating one vehicle, using the proposed lower/upper-bound availability algorithm. Still further studies are required to understand better the relationship between the relocation performance and the parking slots to vehicle ratio. While we aim for improving the proposed algorithm in such a way to always guarantee a ratio greater or equal to 1:1.