Relocating shared automated vehicles under parking constraints: assessing the impact of different strategies for on-street parking

In Fig. 1, a schematic overview is given of the chain of operations necessary for the deployment of SAV: vehicle dispatching, vehicle routing, and vehicle relocating. Vehicle routing and vehicle dispatching are integral steps of the operation of SAV. Vehicle relocation, however, is an optional step, as it can be alternatively decided to only move the vehicle from its latest passenger drop-off location to the next passenger pick-up location once the vehicle has been dispatched to a new request (which can occur instantly in case there is a queue of unserved requests). However, adding the additional step of relocating the vehicle to a strategically chosen parking location can potentially improve the overall performance and level-of-service. Furthermore, it would also be essential for operating real-world SAV systems due to limited parking facilities in urban environments. This is especially true in times where there is little demand for the service, e.g. during off-peak hours, which results in an oversupply of vehicles.

The relocation of idle vehicles has been described by the Empty Vehicle Redistribution Problem, which falls in the category of Vehicle Routing Problems, a subcategory of the Traveling Salesman Problem (Babicheva et al. 2018). Idle vehicle relocation has also been described as the Idle Vehicle Propositioning Problem, as a subcategory of Facility Location Problems (Sayarshad and Chow 2017). These problems are NP-hard and are notoriously difficult to solve, especially in dynamic settings. For this reason, applying heuristics for the dispatching and relocation of vehicles in large cooperative fleets is the most common approach in simulation studies of large-scale on-demand transport systems.

A directed graph \( G\left( {V,E} \right) \) is used for representing the dynamic transport service network with \( E \) being a set of arcs (edges) and \( V \) being a set of vertices. Each vertex \( v \) represents an intersection between arcs and each arc e is described by its characteristics: link length, the maximum allowed driving speed, free flow capacity and the maximum parking capacity denoted by \( \kappa_{e}^{max} \). At a discrete moment in time \( \tau \), the time-dependent variables of current driving speed and the current free parking capacity \( c_{e} \left( \tau \right) \) describe the state of the arc. Furthermore, \( Z \) denotes a set of zones, described by the set of arcs present in that zone \( E_{z} \) and the time-dependent variables of the current free parking capacity of all arcs in zone z, \( c_{z} \left( \tau \right) = \mathop \sum \nolimits_{{e \in E_{z} }} c_{e} \left( \tau \right) \).

The demand for SAV has been modelled based on the general population dynamics implemented in MATSim (see Nagel et al. 2016). In MATSim, travellers follow a daily plan, which consists of a set of activities that they want to perform. For each activity, the location is known, as well as the desired start and end times and the mode the agents intend to use to reach the activity. Each traveller memorizes a set of these plans, for which the plans can vary in activity start and end times, modal choices or route choices, but always show the same sequence of activities. In the course of a repeated simulation of the same day, agents can try out different plans and improve parts of the plans according to predefined behavioural strategies also known as ‘innovation rules’. The plan selection is based on the concept of utility maximisation, as performing an activity and travelling towards an activity are scored based on their perceived utility. The repeated plan innovation and plan selection in the face of the resulting traffic states leads to an optimization of the agents’ plans through the co-evolutionary search for the resulting equilibrium (Balmer and Rieser 2009), which is de facto also leading to a user equilibrium on the road network.

The demand for SAV is expressed in the form of individual requests. Each individual request \( q \in Q \) is launched by an agent at time step \( \tau \) at a pick-up (origin) location on an arc \( e_{q}^{o} \), where \( Q \) is the set of all travel requests for SAV rides in the network under consideration. Information concerning the downstream drop-off location of a request is not used during the vehicle dispatching and relocating process. All requests that are not yet dispatched or are in the process of being dispatched are stored in the time-dependent set of open requests \( Q\left( \tau \right) \).

Each SAV follows, similarly to the travellers, a schedule for the whole day, which is imposed on it by a central dispatcher. In contrast to the travellers, who update their plans from day to day, the vehicles’ schedules are updated within each simulated day in response to passengers’ requests.

The SAV are stored in a set of vehicles \( K \). Each vehicle \( k \in K \) is described by its length, the maximum vehicle speed, its current location denoted by \( e_{k} \left( \tau \right) \) and its current dispatching status. Vehicles are grouped in subsets according to their dispatching status: the subset \( K^{serve} \left( \tau \right) \), in which all vehicles currently assigned to dispatch a request (and are therefore moving—either empty towards a pick-up point or with a passenger on-board heading towards the drop-off location) are stored, and the subset \( K^{idle} \left( \tau \right) \), in which all idle vehicles currently not assigned to dispatch a request are stored. The latter has a subdivision, the set of vehicles that are not in use and relocating according to one of the relocating strategies \( K^{reloc} \left( \tau \right) \) and the vehicles that are idle and parked \( K^{park} \left( \tau \right) \). Relocating vehicles are, despite being on the move, considered to be idle and can at any moment be diverted from their relocation path in order to serve an incoming request. It holds that \( K^{serve} \left( \tau \right) \cup K^{idle} \left( \tau \right) = K \) and that \( K^{reloc} \left( \tau \right) \cup K^{park} \left( \tau \right) = K^{idle} \left( \tau \right) \) since these sets are mutually exclusive and collectively exhaustive.

In regard to the transport service provided by the SAV envisioned in this study, many parallels can be drawn between SAV and the current taxis, which also provide on-demand transport services. For this reason, we include in the review of relocation strategies for SAV also the strategies applied to taxis today. There are multiple heuristic vehicle relocation strategies for vehicles of on-demand services, which can be divided into two groups: reactive and proactive relocation strategies (Babicheva et al. 2018). Reactive relocation means that vehicles relocate only upon passenger request, while proactive relocation strategies relocate vehicles in anticipation of future demand and/or supply states. In the latter case, the step of relocating and dispatching are interconnected. The different strategies differ also in regard to their overall goal: while some aim at increasing the chance for an individual vehicle to be dispatched to requests as often as possible, others are designed to improve the overall service of a fleet, to reduce undesired externalities or to support scheduled public transport services in regions with underdeveloped coverage, e.g. when used as last-mile service.

Two reactive relocations strategies can be distinguished: parking and cruising. Reactive strategies applying “parking” either park idle vehicles at their last drop-off location, which in the following we refer to as the strategy Remain, or send them to a taxi stand or depot. Though the reactive relocation strategy of parking at the last drop-off location is not commonly observed in the operation of demand-responsive transport services, it is often selected as a default option in simulation studies featuring SAV or similar on-demand transport services (Bailey and Clark 1992; Ben-Dor et al. 2019; Fagnant and Kockelman 2014; Maciejewski et al. 2016; Winter et al. 2017), implicating that idle vehicles park at the last drop-off location regardless of parking (capacity) constraints. The relocation strategy of Cruising is a phenomenon that can be observed in the real world when drivers of on-demand transport services are searching for potential customers while avoiding parking search and possible parking fees, as is the case for regular taxis, ride-hailing services and many para-transit services in the Global South (Anderson 2014). Idle cruising increases the driven vehicle mileage and, by this, can contribute to congestion effects, increased fuel consumption or energy usage and increased emissions. This strategy has been included in simulation studies (Zhang et al. 2016), mainly as a means for benchmarking proposed proactive relocation strategies in regard to driven mileage and service efficiency.

In this study, vehicles are assigned to incoming requests according to the “rule-based” dispatching strategy described in (Maciejewski et al. 2016; Maciejewski and Bischoff 2015). In times of oversupply of vehicles, this dispatching strategy assigns the nearest vehicle to customer requests in a first-in-first-out (FIFO) order of the requests, and in times of undersupply of vehicles assigns the next idle vehicle to the closest open customer request. In case no open requests remain to be dispatched, the vehicles stay idle at the drop-off location of the last request they have been serving, the relocation strategy applied by default in the “rule-based” dispatching strategy is thus Remain. The Remain strategy does not take into account that in the real world, parking space and road space are limited resources. Letting vehicles simply wait at their latest drop-off location is hence an unrealistic representation of the operation of SAV or other comparable mobility services. We therefore consider three more advanced relocation strategies taking parking constraints into account, which we referred to as (1) Demand Anticipation, (2) Supply Anticipation and (3) Demand–Supply Balancing. A detailed description of these strategies as used in this study and as found in the literature is provided in the following sections. The three strategies used in this study are composed of simple heuristic building blocks (described in pseudo-code in Fig. 2), making them comparable and traceable. The first strategy aims at placing idle vehicle close to future demand, the second strategy aims at distributing idle vehicles throughout the network and the third strategy aims at meeting both goals of the previous strategies by mitigating future demand–supply deficits. All strategies are put into action on a zonal level.

The relocation of an idle vehicle k is performed in all cases when there is no pending unassigned request and the vehicle in question has been serving a passenger request in the previous time step and is currently idle. The relocation strategy determines the vehicle destination link so that it moves from its current location \( e_{k} \left( \tau \right) \) to the selected destination arc \( e_{k}^{d} \). The three pro-active relocation strategies analysed in this paper are based on predictions of future demand and supply per zone, for which a rolling horizon time \( \alpha h \) is defined, where \( \alpha \) is a parameter that sets the number of horizon windows considered, each of which is \( h \) minutes long. For reasons of simplicity, we make usage of our full knowledge about future requests, the expected future demand is thus the true demand based on the agents’ plans, and not an estimation thereof. The results for this strategy, therefore, are an overestimation of the performance of this relocation strategy, which in reality will be subject to prediction errors.

There are several ways of assessing the performance of a relocation strategy, as shown in the literature overview of in Table 1. Which strategy might be chosen depends on the objective that is formulated for services operated by the SAV. Different perspectives may be considered by the various stakeholders, such as the fleet operator, customers, municipalities tendering the on-demand transport services, other road users and residents of the city where such services are operated. The relocation of vehicles impacts the service efficiency, but also service externalities and service equity. Service efficiency can be defined from a user perspective (e.g. in terms of average passenger waiting times per passenger trip) or from a supplier perspective (e.g. in terms of the ratio of vehicle–kilometres-travelled (VKT) without passengers on-board over the total VKT). The externalities of a service operated by SAV are the costs and benefits that affect those not making use of the service, which can be for example its contribution to congestion, undesired environmental effects or the use of public parking facilities. The equity dimension relates to the distribution of benefits and costs of the service over different population groups, notably as varying in their residential location. In terms of benefits, it relates to the variation in service quality as defined for instance in waiting times. In terms of costs, it relates to the distribution of congestion or the spatial pattern of the use of parking facilities. Table 1 provides a brief overview of simulation studies of on-demand transport fleets, the applied relocation strategies in these studies, and the key performance indicators employed in the assessment of the simulation results.

The daily activity plans of the agents travelling within the case study network have been specified based on the outcome of the Dutch activity-based model ALBATROSS for the base year 2004 (Arentze and Timmermans 2004). Its outcome is a travel demand model specifying the activities performed by each member of a household, including i.a. the start time and end time of the activity, the 4-digit postal code of the activity and the chosen travel mode to reach the activity location. The Dutch 4-digit postal code areas are quite large (see zonal division shown in Fig. 3). For this reason, we attributed to each activity an actual address within the postal code area at random. The ALBATROSS data set has been reduced to households in which at least one household member performs at least one activity within the municipality of Amsterdam. For computational reasons, we simulate only 20% of the population, therefore each agent is weighted by a factor of five in the simulation. In doing so, we follow common practice (see also Bischoff and Maciejewski 2016b). This results in a total of 767,495 agents (represented by 153,499) who perform a total of 3,776,805 activities on a single day and move either by car, public transport or active mode (walking and cycling combined). The majority of the agents are based in Amsterdam, but a substantial share arrives from surrounding suburbs and from nearby towns situated in the greater metropolitan area. The altered data set used in this study and a detailed description of how it has been derived is publically available (Winter and Narayan 2019).

Since automated on-demand transport services are not operational as of now, assumptions concerning their operational and technical specifications, as well as the assumptions on the passengers’ reception of such services remain speculative for the moment. For this reason, a simple scenario has been drawn regarding the technical and operational specification of SAV and their according infrastructural needs. The assumptions made on AV technology and infrastructure needs are reduced in complexity so that the simulation results remain traceable and the analytical focus can be put on the relocation strategies.

In this study, SAV are offered as an additional mode alternative to private car, public transport and active modes. In terms of vehicle technology, SAV are regarded to be similar in their performance to private cars, they achieve thus the same driving speeds and have the same physical dimensions. In this study, SAV and private cars share the same road infrastructure, it is such a simulation of mixed traffic. In operational terms, the SAV are assumed to be operated as a centrally dispatched fleet which allows for sequential vehicle sharing. Car-pooling, i.e. simultaneous vehicle sharing, is thus not considered in this study. Vehicles are assumed to fully comply to the dispatcher and operate in a collaborative scheme. In regard to their infrastructural needs, it is assumed that they share the road infrastructure built for private cars and can drive on all links of the road network.

To test the impact of the different relocation strategies, the fleet size has been set to 12,500 vehicles, which leads to an average passenger-waiting time of 4 min—a value which we selected to represent an acceptable level of service. This fleet size for SAV is approximately 2% of the simulated fleet size of private vehicles. For these vehicles, 15,000 curbside parking spots are reserved throughout the network within the limits of the city area, their location is shown in Fig. 3c. We generated these parking spots per link-arc based on the link length, which therefore determines the storage capacities for idle vehicles per link. These generated parking spots are located in the middle of arcs representing residential streets situated within the city boundaries on streets with a maximum allowed speed of 50 km/h. At the beginning of the simulated day, the SAV are parked randomly on the dedicated parking facilities, as shown in Fig. 3d. The amount of dedicated parking spots has been selected so that sufficient parking space is provided to the SAV at all times throughout the simulation, and so that in addition some extra space is available to efficiently park the vehicles according to the relocation strategies. In this scenario, parking spots can be allocated and reserved by the same central dispatcher, who also performs the request dispatching. We capped the size of the set of candidate zones considered for relocation to three (\( \zeta \) = 3).

The modal split present in the reduced ALBATROSS data set is not aligned with the modal split observed for the city of Amsterdam based on all trips taken within the city as well as trips with either their origin or destination within the city boundaries (Gemeente Amsterdam 2016). To overcome this, the plans of the agents have been calibrated by simulation based on the co-evolutionary learning process implemented in MATSim until a modal split similar to the one observed for the city of Amsterdam (including walking and cycling, which account for large shares of trips performed) has been achieved. The calibration has been performed under the conditions that the daily travel pattern remains showing two demand peaks due to commuting and that all agents reach their final destination within the simulated period. While the Amsterdam scenario has been carefully calibrated to reproduce the actual local overall modal shares, the simulated scenario has not been calibrated for more detailed traffic and travel data.

Over time, MATSim agents can alter their daily plans following a set of day-to-day learning rules. The MATSim-specific settings in regard to this simulated learning-behaviour are presented in Table 3. After a completed simulation run of one day, agents either select their next plan from a set of plans they have memorized from previous simulation runs based on the plans’ scores, or alter parts of their plan according to pre-defined plan-innovation rules (see Table 3). The learning behaviour simulated in MATSim is based on the concept of utility. The utility of performing an activity is described by the activity duration, the waiting time in case of arriving too early, a potential delay, a potential early departure and the potential reduction of the desired time spend on the activity (Nagel et al. 2016). The coefficient for the utility of performing an activity, \( \beta_{duration} \) is based on the value of the average hourly wage in Amsterdam in the year 2017, which is 16.25 Euro per hour (Gemeente Amsterdam 2018). The coefficient for arriving late is weighed three times as much as \( \beta_{duration} \), following the standard MATSim settings and the findings in Börjesson et al. (2012). The disutility of travelling depends on travel time and travel costs. The coefficient for travel time \( \beta_{travel\_time, m} \) is mode specific, while the one for travel cost \( \beta_{travel\_cost} \) is generic, based on the assumption that costs are perceived in a rational manner. Additional mode-specific preferences are represented by the Alternative Specific Constants \( (ASC_{m} ) \). The cost parameters and the mode-specific constants for travel time for the modes car, public transport, cycling and walking as well as the cost parameters are, where possible, based on values reported in literature (van Ommeren et al. 2012) and are presented Table 3.

The values for cost_SAV are based on values reported for the simulation of comparable services, which range between 14 €-cent/km and 91 €-cent/km, with most studies settling at price similar to the one used in our study (see Bösch et al. 2018; Gurumurthy et al. 2019; Simoni et al. 2019). The values for the perceived utility of SAV have been set to be the same as the ones for private car, since the way we envision this transport service is most similar to the one of the mode “car” in this model: passengers are moved inside a motorized vehicle, which is not shared with strangers, and provides an on-demand door-to-door transport service. Currently, the state-of-the-art discrete choice models comprising the choice between SAV and the other modes included in this model are not unequivocally enough to make an assertive statement about the relative difference in the perceived utility of SAV and car (Ashkrof et al. 2019; de Looff et al. 2018; Simoni et al. 2019). However, the specified behavioural model serves the purpose of creating a test-bed in which strategies for idle vehicle relocation for SAV can be analysed in regard to their service efficiency, externalities and equity. This can be achieved with the simplified model described in Tables 2 and 3. Nevertheless, given the many uncertainties linked to the user preferences towards vehicle automation in general, and shared automated vehicles in particular, we refrain from analysing the impact of the relocation strategies on mode shifts and mode shares. The latter should be included in such an analysis once more reliable mode-choice models for SAV are available. We should point out that in our case study the applied behavioural model is set in the (Dutch) context of the case study and hence the SAV is primarily in competition with the longer-distance modes ‘private car’ and ‘public transport’. As a result, the average distance for trips taken in SAV is around 12 kilometres, which lies well above the 7.5 kilometres which mark the threshold distance above which the Dutch population tends to switch from active modes (walking and cycling) to car (Ministry of Transport Public Works and Water Management 2009).

For this reason, we suppressed mode changes in the final model used to test the relocation strategies. To able to do so, we split the simulation process into three parts: (1) In the first calibration phase, we let agents incorporate SAV into their daily plans in the course of 76 repeated simulations of one day. During the cause of these simulated days, agent mode choice behaviour stabilized, leading to a modal share of 4% for SAV, which equals approximately 130,000 trips performed using SAV per day (Table 3). (2) The resulting plans of the final simulated day have been used as an input in the second simulation phase, in which the same day has been simulated in 16 runs. (3) The output of this second round has been used as an input for the final simulation, in which the same day is simulated only twice, while suppressing any mode choice innovations. The second simulation phase has proven to be necessary due to a particular feature inherent to MATSim’s Dynamic Transport Services module, which uses the exponential moving averages of link travel times over all iterations of a simulation for its dispatching algorithm. Without the intermediate step, the output of the last day of the first calibration phase would not lead to the same results of the first day of the final simulation. The applied solution to this problem has also been suggested in (Maciejewski and Bischoff 2018). The demand for SAV is shown on a zonal level in Fig. 3e, the temporal distribution of the requests for SAV are shown in Fig. 3f, in which the requests per hour per zone are stacked up on top of each other in layers.

During the learning phase of the agents, the relocation strategy of “demand-anticipation” has been applied to capture the appropriate agent learning behaviour as a response to SAV service that is subject to parking restrictions. We opted for this strategy for computational reasons, as this strategy shows the shortest computational times (see Table 3). The resulting plans of this simulation are used as an input to all following simulations testing the different relocation strategies. The input to the scenarios simulating the different relocation studies is thus the output of the simulations performed in the initialisation phases. It contains a set of agents and their activity schedules for the simulated day, including their travel behaviour. For the simulation of the relocation strategies for SAV, these plans are not altered any further, the demand for SAV is thus kept inelastic.

The service efficiency is measured in KPI describing the quality of service from a passenger’s perspective, as well as KPI showing how efficiently the transport service can be operated. For an overview of these KPI, see Table 4, as well as Figs. 4 and 5.

The externalities of SAV relocation strategies are analysed for three aspects: (1) the average driving speed as a proxy for congestion, (2) the total driven mileage as a proxy for energy consumption and potential emissions and (3) the spatial consumption of curbside parking space by SAV. For an overview of these KPI, see Table 5.

In this study, the service provision equity of the on-demand transport service operated by SAV is analysed in regard to the distribution of waiting times. As a KPI, the Gini-index for all passenger waiting times \( G_{wait} \) and for the zonal average passenger waiting times \( G_{wait, z} \) is used, which are shown in Table 6. The Gini-index (Gini 1912) is a well-known measure of inequality, often used in an economic context. A concise description of the Gini-coefficient and its applications in the field of transport as a means to measure inequality of accessibility can be found in (Ben-Elia and Benenson 2019). In short, the Gini-index is a measure of distribution, ranging from 0 to 1, with 0 indicating perfect equality and 1 perfect inequality. The closer the Gini-coefficient is to 0, the more passengers experience similar waiting times. A high Gini-coefficient, in turn, represents a situation where people differ substantially in their experienced waiting times. In this study, we use the Gini-coefficient only to describe the distribution of waiting times over the whole population, without taking into account the differences between people, such as income or mobility needs.

With shared mobility and on-demand transport services gaining steadily more ground, and the automation of vehicles pushing into the field of transport as the next ‘disruptive’ technology, the need for reliable simulation studies for testing operational strategies for AV and SAV is increasing. This study has shown that an important component of operating such vehicles in a large fleet is the relocation of idle vehicles during off-peak hours. In the urban context, space for idle vehicles is scarce and parking is often constrained. The relocation of idle vehicles is thus a necessary consequence of real-world parking constraints. For this reason, it is important to test for the impact of different relocation strategies when introducing SAV to a city, and specify them for example in a tendering process or when tailoring curbside management strategies. Including vehicle relocation under parking constraints to the simulation of the operation of SAV is thus an important step to increase the realism of the simulation and consequently improve the analysis of such transport services. For this reason, it is not the comparison between the Remain strategy and the simulated relocation per-se the subject of analysis, but rather primarily the comparison between the different relocation strategies, which take the real-life constraints caused by the scarcity of road-space and parking-space into account. However, there are two main insights gained from referencing the scenarios with pro-active relocation strategies against a situation where parking constraints are not accounted for (i.e. Remain): (1) The relocation of idle vehicles does not necessarily lead to performance gains for a fleet vehicles providing on-demand transport services. As a consequence, there is a risk of overestimating the performance of such fleets in simulations in case the relocation of empty vehicles is not accounted for. (2) Relocating idle vehicles in a pro-active manner might be outperformed by reactive relocation strategies in regard to the service efficiency and the total driven mileage. Since this finding is case-specific and depends on the spatial and temporal distribution of the demand, more research is required in order to determine the conditions under which it is favourable to apply reactive or proactive relocation strategies. A remain strategy can be feasible in certain areas where ample curbside parking facilities are available, especially if those are to be prioritized for SAV. Such areas are typically located in the outskirts of cities, which means that pro-active relocation strategies might be particularly suitable for city centres or other areas with little space and high demand. In this study, three pro-active relocation heuristics based on zonal parking availability are compared to each other, in terms of service efficiency, service externalities and service provision equity, for a case study based on the city of Amsterdam, the Netherlands. Performance differences could be detected regarding the quality of the offered service (average passenger waiting times, average trip times), the impact on traffic (local congestion, total driven mileage), the parking space usage and the spatial service provision equity (distribution of passenger waiting times).

The strategy Demand–Supply Balancing aims at reducing the deficit between future demand and future vehicle supply per zone, and thus combines the goals of the previous two strategies. The resulting KPI for this strategy are consequently also situated in most cases between those of the two previous relocation strategies, with the outcome of the Demand–Supply Balancing strategy being much closer to the one of the strategy Supply Anticipation than for Demand Anticipation. Two KPIs stand out in this regard, namely the empty driven mileage, and the passenger waiting times. This strategy leads to the highest value for VKT without passengers on board, which is caused in particular by the relocation of idle vehicles. As a consequence, this strategy also leads to the highest congestion levels in the network. At the same time, this strategy also leads to the shortest average passenger waiting times and the most equal distribution of the latter.

As shown in this study, the underlying principles of a vehicle relocation strategy impact the efficiency, externalities and equity of an on-demand service. It depends on the importance one attaches to these aspects, whether one declares one of these relocation strategies to be more beneficial than the others, since the results suggest that none of them outperforms the others in all regards. When discussing the introduction of SAV to a city, main stakeholders include the (potential) users of the transport service they offer, the operator of the service, the planning authority supervising the introduction of the new service to provide a certain level of service, and the citizens (potential non-users) in the area. From the perspective of a service operator, different relocation strategies can prove to be beneficial: Demand Anticipation allows to reduce average waiting times in high-demand areas and to reduce driven mileage, both contributing to increased service efficiency. For this reason, most current on-demand transport services operated by drivers acting as decision-making agents are dominated by this relocation strategy. When drivers are in direct competition for passengers with each other, they create a situation closer to a stochastic user equilibrium (SUE), which does not necessarily benefit the fleet as a whole. However, once the demand, and accordingly the fleet size, reaches a level that the operation of SAV causes local congestion, it can be beneficial for an operator to cap the number of idle vehicles in high-demand areas and swap to a relocation strategy which spreads out idle vehicles more, such as the strategy Supply Anticipation. Increased service efficiency is also beneficial for the users of the service in terms of reducing waiting times and in-vehicles times. For passengers requesting the service in zones with low demand, a relocation strategy distributing idle vehicles more evenly is particularly beneficial, as this reduces the waiting times that they might experience otherwise. The best results in this regard could be achieved with the strategy of Demand–Supply Balancing for the simulated case study.

When taking the perspective of a higher planning authority, for example on a municipal level, different objectives could be leading for selecting a relocation strategy. On-demand transport shows more fluctuation over time in its performance than scheduled transport, especially regarding waiting times and reliability of indicated waiting times. There is no clear consensus yet on how to benchmark average waiting times, maximum waiting times, reliability of indicated waiting times and updated waiting times for on-demand transport services. For the simulated scenarios, the service with the overall shortest trip times (waiting time and in-vehicle time combined) is achieved with the strategy Demand Anticipation. This strategy also leads to the lowest value for the total driven mileage, which can be interpreted as a proxy for energy consumption and emissions of pollutants and noise caused by this transport service. However, in regard to parking consumption, the case could be made for different strategies: Supply Anticipation and Demand–Supply Balancing lead to the much more equal occupation of parking facilities in spatial terms, which can reduce pressure on the parking facilities in popular areas like city centres, and also to a higher service provision equity. Another way to look at the bunching of idle vehicles in areas of high demand caused by the strategy Demand Anticipation could be to interpret this as a “polluter-pays” situation: if users of other modes are not affected by the parking consumption of SAV, e.g. because these park on reserved parking spots or private ground, and the local congestion the create SAV does not affect overall network flows, this could also be an acceptable solution from the perspective of a planning authority. Which relocation principle is more favourable for a city’s management of scarce parking facilities depends on the local situation, and also in regard to which potential user groups might profit most from this. As neither the strategy of Demand Anticipation nor the one of Supply Anticipation clearly outperforms the other when taking into account the holistic set of KPI presented in this paper, a compromising strategy like the Demand–Supply Balancing strategy has the potential to provide the necessary attenuation of undesired effects.

The analysis of the relocation heuristics is based on the simulation of a case study. This set-up does not allow to draw universal conclusions, and should be generalized or transferred to other contexts with caution. The main limitations of this study are linked to two input parameters: (1) the zonal division and (2) the behavioural model used to describe the users’ response in the agent-based model.

Further limitations of this study are caused by other simplifications made for the simulation of the case study, such as that parking spots are dedicated for SAV and can be reserved upfront by the operator. Future research into the distribution of parking spots for SAV and the allocation of free parking spots will be an important aspect in the development of dynamic fleet operation paradigms. This is particularly important if more than one fleet of SAV compete with each other for parking space, or if they compete with individual drivers of (non-)automated vehicles. Furthermore, the performance of the different relocation strategies for idle vehicles should also be tested for other operational scenarios, most importantly for SAV operated as a pooled service. The operational differences for pooled services mainly impact the vehicle routing problem and vehicle dispatching problem, however, also the performance of vehicle relation strategies can change due to pooling. When operating SAV as a simultaneously shared service, instead of a sequentially shared one, vehicles likely turn idle less often, and they turn idle at different locations in the network. Which relocation strategy performs best in such a setting highly depends on local conditions and should be carefully tested for the different performance indicators presented in this study. The analysis in this study is based on one specific case study in order to retrace the impact of three simple vehicle relocation heuristics. Based on this set-up, future work will investigate further the interplay between the fleet size of SAV and the number of reserved parking facilities, and curbside management strategies will be concretized in order to test the impact of parking policies for SAV.