Simulation-Based Assessment of Parking Constraints for Automated Mobility on Demand: A Case Study of Zurich

Abstract

In a coordinated mobility-on-demand system, a fleet of vehicles is controlled by a central unit and serves transportation requests in an on-demand fashion. An emerging field of research aims at finding the best way to operate these systems given certain targets, e.g., customer service level or the minimization of fleet distance. In this work, we introduce a new element of fleet operation: the assignment of idle vehicles to a limited set of parking spots. We present two different parking operating policies governing this process and then evaluate them individually and together on different parking space distributions. We show that even for a highly restricted number of available parking spaces, the system can perform quite well, even though the total fleet distance is increased by 20% and waiting time by 10%. With only one parking space available per vehicle, the waiting times can be reduced by 30% with 20% increase in total fleet distance. Our findings suggest that increasing the parking capacity beyond one parking space per vehicle does not bring additional benefits. Finally, we also highlight possible directions for future research such as to find the best distribution of parking spaces for a given mobility-on-demand system and city.

1. Introduction

In many cities, privately owned cars are a dominant mode of transport. Apart from their undeniable utility for transportation, cars require roads to drive, burn fuel, emit greenhouse gases and pollutants and cause congestion. Furthermore, cars have an impact on urban life when they are not in operation but parked. Occupied parking causes additional vehicle distance and economic inefficiency. Shoup [1] provides one of the first overviews of cruising for parking and Cookson and Pishue [2] estimate that drivers spend 65 to 107 driving hours a year searching a free parking spot in major Western cities. As every location that a car owner chooses to visit requires a parking spot, the land consumption of parking spaces is significant. For instance, parking spaces consume about 14% of incorporated land [3].

With the advent of partially or fully self-driving cars, their potential to use existing infrastructure more efficiently has been studied e.g., [4]. Especially, their impact on parking and the transformation of parking space is an active research topic in recent literature [5]. Among other technological advantages, self-driving cars can be leveraged to allow for more densely packed parking lots [6]. Apart from this, the technology will change the behavior of travelers: privately owned, fully self-driving cars may reduce the cost of travel and allow owners to send their vehicle to a parking spot separate from their destination.

The implications of this ability are assessed by Zakharenko [7] based on a simplified city model. It describes a city topology with only one parameter, the distance from the city’s “port” or central location. The work predicts that in an economic equilibrium with self-driving cars, daytime parking will happen at the periphery of the city or even at the residential locations of commuters. Car owners will simply send their cars to parking lots in cheap locations to maximize economic utility. Masoud and Jayakrishnan [8] point out that for shared vehicles across households affordable parking is central to enable positive sharing effects.

The topic is discussed by Millard-Ball [9] with a slightly different angle. Based on numerical results of a traffic micro-simulation for downtown San Francisco, the authors describe the possibility that autonomous vehicles could simply be sent cruising around the block in order to avoid parking fees. By that, they would create substantial additional distance and congestion. Additionally, this option would render useless the possibility of authorities to use parking prices as a steering mechanism for private vehicle usage. Subsequently, dropping parking prices would therefore induce even more traffic.

In [10], the effect of self-driving vehicles on departure time and parking location is assessed. A parking pricing scheme is proposed that could replace a road tolling scheme and drive the transportation system towards system optimum. Price control is also an aspect in the research of Wang et al. [11] where a system dynamics model is used to equilibrate parking demand and supply in a generic network-less formulation and by Bahrami et al. [12] where a Wardrop equilibirum inculding parking choice is developed, in both cases for privately owned vehicles. Levin et al. [13] present a bi-level optimization approach which considers the choice of parking location and the design of the parking infrastructure at the same time.

In an agent-based simulation, Bischoff et al. [14] investigate the negative impact of excessive cruising in a neighborhood of Berlin with 4000 parking spaces and a total of 37,000 people traveling. Overall, an average duration of 8:50 [min] is recorded to find an empty parking space. Additional vehicle distance traveled for parking search is 2% to 4% for all strategies except for the cruise strategy that results in an increase of 80% to 110%.

Besides being available for private ownership and usage, fully self-driving cars could also be operated in a coordinated fleet by a service provider. Users would then book a vehicle in an on-demand fashion. This concept is described in literature as autonomous mobility-on-demand (AMoD). In a data analysis based approach, Kondor et al. [15] use previously developed methods of vehicle and trip shareability networks [16,17] to determine a lower bound of parking space reduction for Singapore under the assumption that a large-scale autonomous mobility-on-demand system is introduced. The presented greedy heuristic algorithm is applied to a 1.44 million trips data set. The results suggest that a 85% reduction of the current estimated minimum of 1,369,576 parking spaces can be realized if all of these trips are served by an AMoD system. A similar study [18] by the same authors focuses only on home-work commuting by shared autonomous vehicles. It projects a 50% reduction of parking needs at the expense of 2% of additional fleet distance for Singapore.

Beyond data analysis approaches, the study described by Zhang and Guhathakurta [19] presents a custom-built simulator that is applied to data for Atlanta in the United States. The authors conclude that parking land use can be reduced by 4.9% if 5% of trips are served with a mobility-on-demand system.

Wang et al. [20] present a combined consideration of three different questions in one extended simulation study for a newly planned district, Waterfront Tanjong Pagar, in Singapore. The author vary vehicles and parking bay sizes and heuristic relocation strategies that take into account available space in the bays. The vehicles may either perform “demand-based roaming”, i.e., they travel towards locations with substantial past demand and then randomly patrol these zones; they may park on-street thereby blocking the lane; or, the vehicle may also travel to a depot where it can be parked. A mixed depot/street strategy is examined as well. In Marczuk et al. [21], vehicles in a mobility-on-demand scheme operate in a “station-based” or “free-floating” mode and the latter is shown to be beneficial for the service level of the scheme. Ye et al. [22] run the agent-based micro-simulator SUMO in an evolutionary algorithm to optimally select whether lanes in a generic test network should be used for driving or parking by an AMoD fleet.

Similar problems of parking availability and matching also arise in systems without self-driving cars, notably ride-hailing or ride-sourcing systems such as Lyft. In [23], they were studied with a focus on cruising due to customer and parking search and induced congestion. Using a macroscopic conceptual model, the authors determine the relation of cruising for parking search and road capacity loss. Among other findings, they conclude that no parking spaces are needed for times when demand peaks. A related problem for ride-hailing services with a focus on the morning commute is presented in [24].

All research mentioned so far demonstrates that the fleet level decision-making related to parking of vehicles has an influence on system performance. In this work, we attempt to study this decision-making for a case study of Zurich and aim to quantify its impact with simulation methods. To achieve this, we formally introduce the process of assigning staying vehicles to free parking spots as an element of a fleet operational policy that we call “parking operating policy”. This new part of fleet operation thus composes an additional decision-making process next to the ones we have already studied, namely the assignment of free vehicles to open requests called “dispatching” e.g., [25], the assignment of idle vehicles to locations of future anticipated demand called “rebalancing” e.g., [26], the evaluation and assignment of ride-sharing opportunities [27], and the choice of vehicle routes [28].

Compared to our previous studies, we drop the assumption that as many parking lots are available as required, i.e., that vehicles have an opportunity to stop on any road at any time. Instead, we introduce limited parking capacities at every road. Then, we develop parking operating policies and assess their impact on system service level and efficiency, especially vehicle distance traveled. In doing so, we can address the currently open question if a limited number of parking spaces in a city will severely impair fleet performance or increase the cost of a coordinated mobility-on-demand system. Moreover, we assess the impact of parking space density and parking space distribution. For this purpose, we use three different parking space distributions: a uniform distribution in the network, a distribution based on available public parking and a distribution based on parking spaces currently used by a two-way shared mobility operator. Compared to the existing literature cited above we focus on a shared fleet of vehicles, which have been covered less thoroughly in terms of parking than privately owned vehicles. In terms of existing fleet-based simulation approaches, we advance the discussion by analyzing an adaptive anytime optimal algorithm to assign idle vehicles in an AMoD fleet to vacant parking spots.

The paper is organized as follows. First, the problem is formally stated in Section 2 and necessary notation is introduced. Then, two different parking operating policies are presented in Section 3. These operational policies are evaluated in simulation and compared in different scenarios in Section 4 and Section 5. A conclusive statement is provided in Section 6.

2. Problem Defintion

An operational policy guiding the behavior of a fleet of vehicles in a mobility-on-demand system is responsible for decision-making in several ways. First, an assignment of available cars to waiting customers must be determined and updated at every time instance. There are various ways of doing this, including heuristic [29] or globally optimized strategies [25,30], see [31,32] for comprehensive surveys. During large periods of the day, there are idle vehicles which are not needed to serve currently outstanding demand. These vehicles must be repositioned to locations of future anticipated demand, a process called rebalancing or repositioning. The choice of rebalancing locations can be made in various different ways, e.g., as described in [33,34,35,36]. Furthermore, possible ride-sharing opportunities may be considered with a suitable strategy, e.g., the ones compared in Ruch et al. [27] or presented by [37]. Finally, also the routing of vehicles can be determined to effect a certain behavior, e.g., the reduction of overall congestion levels [28]. In all of these aspects, the right trade-off between customer service quality including wait and travel times, vehicle distance traveled and fleet size has to be determined.

In this work, we focus on another aspect of fleet operation which has not been considered in depth until now. We consider the case in which parking spaces are limited and present according to a certain distribution, i.e., we remove the assumption that vehicles can stay on all roads at all times. This aspect is closely related to the rebalancing problem mentioned above: rebalance commands can only send vehicles to locations with free parking space or to locations at which they pick up the next customer directly.

The problem is clearly distinct from the related problem of determining the dimensions and design of pickup and dropoff zones at heavily frequented locations, e.g., train stations or airports, which becomes relevant when studying the interaction of on-demand systems and schedule-based public transport [38,39]. This is a separate problem that should be handled in a different context as it depends on many additional factors. Most of them are related to entirely new problem dimensions not related to fleet operating policies: the composition of the population (elderly people, wheel-chair drivers, kids etc.), the size of travel parties and the type of travelers (with or without luggage, work or leisure etc.), the architecture of the buildings, the safety requirements, and more.

In this work, we solely assess the case in which staying and idle vehicles can only remain at predetermined locations in the city, the parking spaces. In order to model the problem, two principal approaches can be chosen. Vehicles are prevented to stay on locations without free parking spaces with a hard constraint, i.e., any number of excess vehicles exceeding the capacity is not permitted. In our model, every parking area is placed on a distinct road $i\in \mathcal{R}$ where $\mathcal{R}$ defines the set of all such roads in the network. The number of parking spots in a parking area i is limited to a parking capacity $c_i\in \mathbb{N}$. These values are constant for the total simulation duration T. Each parking spot in an area can be occupied by a vehicle and $r_i\left(t\right)\in \mathbb{N}$ describes the number of occupied parking spots of the parking area at road i and time t.

The fleet parking problem can be seen as a modification of the transportation problem first described by Tolstoi [40] capturing the difficulty of distribution and allocation of resources. One can indicate both the density of violating vehicles as well as free parking spaces as distributions in the space of ${\mathbb{R}}^2$. In contrast to the original problem, these subsets are not of equal size. The fleet parking problem is only feasible as long as the cardinality of the set of vehicles to redistribute is always smaller or equal to the cardinality of the set of free parking spaces, i.e., as long as there is at least one free parking space per vehicle that must be relocated in the city. Having defined the fleet parking problem, we state the objective of a parking operating policy as follows:

Objective of parking operating policy: a parking operating policy must redistribute idle vehicles such that all vehicles are legally parked and all other system metrics such as wait times, vehicle miles traveled etc. are not deteriorated.

3. Parking Operating Policies

As outlined in the previous chapter, a parking operating policy must redistribute vehicles which do not have a task to pick up or drop-off a customer such that the parking capacity is not violated. Specifically, we assume an original distribution of idle vehicles to be determined by a previous element of fleet operation. This may be an algorithm determining rebalancing movements or simply dispatching dynamics resulting in vehicles being placed at trip end locations. The parking operating policy relocates vehicles from the resulting distribution in order to prevent parking space capacity violations. In the following subsections, we present two different parking operating policies which can handle this problem. The first one assumes no communication between vehicles and no availability of information about the location of free parking spaces, but it has information on the total number of parking spaces on each road.

The second policy assumes that all free parking spaces in the operating area are known to a central operator.

3.1. Diffusion (D)

The first approach is similar to a strategy chosen by many human drivers who would simply patrol the neighborhood of their destination in the search of a parking space. As some human drivers have certain preconceptions where the parking spaces are, they tend to choose the roads they drive through while searching for parking based on this knowledge. This can be considered as an advanced parking search strategy VI presented in [41]. On a fleet level, this means that vehicles that are about to stay at a location without available parking spaces are shuffled to a downstream road with a probability $p_k$ with $k\in \mathcal{K}$ referencing the downstream roads and $\mathcal{K}$ being the set of downstream roads that are directly connected to the current road. The probabilities are calculated in the following way:

• (A) If none of the downstream roads have parking spaces we define $p_k=\frac{1}{\left|\mathcal{K}\right|}$, i.e., we perform a random selection among the downstream links.
• (B) If all of the downstream links have at least one parking space, $p_k=\frac{c_k}{{\sum }_k{c}_k}$, i.e., we perform a weighted selection by capacity or the existing number of parking spaces without information on their occupancy.
• (C) If there are both downstream links with and without parking spaces, we decide with a probability $\xi$ whether to use strategy (A) based on the links without parking spaces, or strategy (B) based on all downstream links with parking spaces. Defining a non-zero probability $\xi$ prevents the vehicles from circling along closed loops of road segments in which all parking spots are occupied.

Technically, if a vehicle arrives at the final link of its current route and thereby the number of vehicles $r_i\left(t\right)$ parking on the road exceeds the capacity limit $c_i$, a sufficient number of vehicles on the link (including the ones that just arrived) are sent to a downstream link based on the probabilities described above. A vehicle is allowed to reverse its direction or to follow a new road at the crossroads, provided that this is possible at its location in the road network. This procedure is described in Algorithm 1. For all presented simulations, we use $\xi =0.1$, i.e., we perform random selection of links in 10% of the cases.

3.2. Optimal Flow Parking Assignment (LP)

The previously introduced Diffusion strategy is a local approach while the problem of vehicle redistribution can be optimized globally. One possible solution can be found with a mathematical programming approach that determines the most efficient assignment of vehicles to a given distribution of available parking spaces. Our proposed solution is a variation of the transportation problem by Tolstoi [40]. In its linear programming formulation it is known as the Hitchcock-Koopmans transportation problem [42].

To introduce the definition of the linear program, the following variables and parameters are necessary: $i\in \mathcal{R}$ is the index of a road with parking capacity that cannot accommodate all the vehicles currently staying there, and $\mathcal{R}$ the set of all such roads. Variable $j\in \mathcal{Q}$ is the index of a road j with available parking, and $\mathcal{Q}$ the set of all such roads. The variable $v_i$ counts vehicles located at road $i\in \mathcal{R}$ that must be relocated to avoid parking space violations. The number of free parking spaces in road $j\in \mathcal{Q}$ is called $f_j$. The network distance between locations i and j is introduced as ${\delta }_{ij}$. The total number of available parking spaces is $F:={\sum }_{i\in \mathcal{Q}}{f}_i$, and the total number of vehicles requiring relocation is $V:={\sum }_{i\in \mathcal{R}}{v}_i$. In the case of $F\ge V$ every relocation need can be satisfied, i.e., $v_i$ vehicles can be relocated at parking $i\in \mathcal{R}$. Otherwise, some vehicles can not receive a relocation command, but we either fall back to the diffusion strategy or make use of large depots to ensure that all vehicles can be assigned (see below). Finally, $x_{ij}$ is the number of vehicles that are sent from location i to j. Using this notation, an integer linear program determining the least cost redistribution of vehicles can be set up as follows:    

$$\begin{array}{ccc}\hfill min& {\sum }_{i\in \mathcal{R}}{\sum }_{j\in \mathcal{Q}}{\delta }_{ij}{x}_{ij}& \hfill \\ \hfill \mathrm{s}.\mathrm{t}.& {\sum }_{i\in \mathcal{R}}{x}_{ij}\le f_j& \forall j\in \mathcal{Q}\hfill \\ & {\sum }_{j\in \mathcal{Q}}{x}_{ij}=v_i& \forall i\in \mathcal{R}.\hfill \\ & x_{ij}\ge 0& \forall i,j\in \mathcal{R},\mathcal{Q}\hfill \\ & x_{ij}\in {\mathbb{N}}_0\end{array}$$

(1)

Algorithm 1 Parking Operating Policy 1: Diffusion (D)

Input:   Information on all links and vehicles   $c_i$: limited capacity for all roads i in road network Output:   R: list of relocating vehicles   $\Omega$: list of destination roads for each vehicle   At each time instance:   Initialization: 1:  $S=\left\{\right\}$: empty set 2:  for road i in road network do 3:   $s_i\leftarrow$ set of all vehicles at road i that are staying or arriving 4:   $S\leftarrow s_i$ 5:  end for  Relocation: 6:  for $s_i$ in S do 7:   if $\mathrm{size}\left(s_i\right) >c_i$then 8:    ${\Lambda }_i\leftarrow$ remove $\left(\mathrm{size}\left(s_i\right)-c_i\right)$ vehicles from $s_i$ 9:    for relocating vehicle $r_j$ in ${\Lambda }_i$ do 10:     ${\omega }_j\leftarrow$ compute downstream road based on the number of parking spaces 11:     $R\leftarrow r_j$ 12:     $\Omega \leftarrow {\omega }_j$ 13:    end for 14:   end if 15:  end for

In contrast to the original problem formulated by Hitchcock and Koopmans, the first constraint in Equation (1) is changed from equality to inequality. This constraint previously ensured that the destination capacity is not violated. As the destination set of the transportation problem is of equal size as the origin set, the sum of all demand from i to j has to be equal to the capacity of j. The parking problem instead assumes a destination set of equal or larger size than the origin set and therefore requires an inequality constraint. The problem in Equation (1) can be rewritten in standard form resulting in:

$$\begin{array}{cc}\hfill \underset{\mathbf{x}}{min}& {\delta }^{\top }\mathbf{x}\\ \hfill \mathrm{s}.\mathrm{t}.& A\mathbf{x}\le \mathbf{b}\\ & \mathbf{x}\ge 0\\ & x_{ij}\in {\mathbb{N}}_0\end{array}$$

(2)

For algebraic transformation, the following matrices and vectors are needed:    

$$\begin{array}{ccccccc}\hfill & {\mathbf{1}}_{n\times m}\hfill & \hfill =& \left[\begin{array}{ccc}1& \cdots & 1\\ ⋮& \ddots & ⋮\\ 1& \cdots & 1\end{array}\right]\hfill & \hfill {\mathbf{I}}_{n\times m}& =\hfill & \hfill \left[\begin{array}{ccc}1& 0& \cdots \\ 0& \ddots & ⋮\\ ⋮& \cdots & 1\end{array}\right]\\ \hfill & {\mathbf{0}}_{n\times m}\hfill & \hfill =& \left[\begin{array}{ccc}0& \cdots & 0\\ ⋮& \ddots & ⋮\\ 0& \cdots & 0\end{array}\right]\hfill & \\ \hfill & \mathbf{f}\hfill & \hfill =& {\left[\begin{array}{ccc}{f}_1& f_2& \cdots \end{array}\right]}^{\top }\hfill & \hfill \tilde{\mathbf{v}}& =\hfill & \hfill {\left[\begin{array}{ccc}{\tilde{v}}_1& {\tilde{v}}_2& \cdots \end{array}\right]}^{\top }\end{array}$$

Using this notation the following matrices characterize Equation (2):

$$\begin{array}{ccc}\hfill \mathbf{x}& =& {\left[\begin{array}{cccccc}{x}_{11}& x_{12}& \cdots & x_{21}& x_{22}& \cdots \end{array}\right]}^{\top }\hfill \\ \hfill \delta & =& {\left[\begin{array}{cccccc}{\delta }_{11}& {\delta }_{12}& \cdots & {\delta }_{21}& {\delta }_{22}& \cdots \end{array}\right]}^{\top }\hfill \\ \hfill A& =& \left[\begin{array}{ccc}& -{\mathbf{I}}_{\mathcal{R}·\mathcal{Q}\times \mathcal{R}·\mathcal{Q}}& \\ {\mathbf{I}}_{\mathcal{Q}\times \mathcal{Q}}& \cdots & {\mathbf{I}}_{\mathcal{Q}\times \mathcal{Q}}\\ {\mathbf{1}}_{1\times \mathcal{Q}}& {\mathbf{0}}_{1\times \mathcal{Q}·\left(\mathcal{R}-1\right)}& \\ {\mathbf{0}}_{1\times \mathcal{Q}}& {\mathbf{1}}_{1\times \mathcal{Q}}& {\mathbf{0}}_{1\times \mathcal{Q}·\left(\mathcal{R}-2\right)}\\ & & \ddots \\ -{\mathbf{1}}_{1\times \mathcal{Q}}& {\mathbf{0}}_{1\times \mathcal{Q}·\left(\mathcal{R}-1\right)}& \\ {\mathbf{0}}_{1\times \mathcal{Q}}& -{\mathbf{1}}_{1\times \mathcal{Q}}& {\mathbf{0}}_{1\times \mathcal{Q}·\left(\mathcal{R}-2\right)}\\ & & \ddots \end{array}\right]\hfill \\ \hfill \mathbf{b}& =& \left[\begin{array}{c}{\mathbf{0}}_{\mathcal{R}·\mathcal{Q}\times 1}\\ \mathbf{f}\\ \tilde{\mathbf{v}}\\ -\tilde{\mathbf{v}}\end{array}\right].\hfill \end{array}$$

The associated parameters have the following dimensions:

$$\begin{array}{ccc}\hfill \mathbf{x}& \in & {\mathbb{R}}^{\mathcal{R}·\mathcal{Q}\times 1}\hfill \\ \hfill \delta & \in & {\mathbb{R}}^{\mathcal{R}·\mathcal{Q}\times 1}\hfill \\ \hfill A& \in & {\mathbb{R}}^{\left(\mathcal{R}·\mathcal{Q}+\mathcal{Q}+2\mathcal{R}\right)\times \mathcal{R}·\mathcal{Q}}\hfill \\ \hfill \mathbf{b}& \in & {\mathbb{R}}^{\left(\mathcal{R}·\mathcal{Q}+\mathcal{Q}+2\mathcal{R}\right)\times 1}.\hfill \end{array}$$

Fortunately, matrix A is totally unimodular [43,44]. Therefore, every extreme point of the feasible region of the problem in Equation (2) is integral as long as b is integral. Thus, a relaxed version of Equation (2) with $x_{ij}\in \mathbb{R}$ can be solved with a regular solver for linear programs, but the integral solution to the original problem is obtained.

Using this optimization problem, Algorithm 2 can be introduced that redistributes vehicles according to the solution of the optimal flow problem Equation (1).

Algorithm 2 Parking Operating Policy 2: Optimal Flow Parking Assignment (LP)

Input:   Information on all links and vehicles capacities   $c_i$ of all roads Output:   ${\omega }_j$: destination of all staying vehicles   At each time instance:   Initialization: 1:  $a_i\leftarrow$ get roads, which have overflowing vehicles 2:  $f_j\leftarrow$ get roads, which have free spaces 3:  ${\delta }_{ij}\leftarrow$ calculate distance between all i and j  Relocation: 4:  if $\mathcal{R}\le \mathcal{Q}$then 5:   $x_{ij}\leftarrow$ solve optimization problem (1) 6:   ${\omega }_j\leftarrow$ relocate vehicles according to $x_{ij}$ 7:  else 8:   do not relocate vehicle 9:  end if

4. Simulation Setup

Based on simulation, we are interested to answer three different questions. We aim to understand how parking operating policies affect the system metrics—total vehicle kilometers travelled, empty vehicle kilometers travelled, and pick-up waiting times. Second, we evaluate the impact of parking space density, i.e., the number of available parking spaces per vehicle on system metrics. Finally, we consider the effect of spatial distribution of parking spaces by evaluating three different scenarios of parking spot locations, both artificially generated and based on real-world data.

The subsequent subsections provide details on the chosen simulation environment, the assessed transportation scenario and the used parking space distributions.

4.1. Simulation Environment

The simulations are carried out in AMoDeus, an open-source software tool designed to conduct research on mobility-on-demand systems, specifically on different operating policies [25]. It is based on the agent- and activity-based transport simulation framework MATSim [45], which allows for accurate simulation of road network dynamics. Its queuing-network based traffic simulator makes it possible to conduct large scale parametric studies with high spatial resolution. Furthermore, the framework allows to simulate complex traveler decisions and supply-demand interactions in a dynamic and iterative way. While this ability has recently been demonstrated in the context of AMoD [26,46,47], our research on parking policies only focuses on static demand (i.e., no decision-marking by the travelers) to study the effects of parking policies individually.

All implemented parking operating policies for the AMoDeus framework are available online as open-source code (https://amodeus.science, accessed on 5 May 2021 ). The linear program of the dynamic parking policy is solved with the open-source solver GLPK [48]. All network distances are calculated using the A*-landmark algorithm [49].

4.2. Transportation Scenario

We use a transportation scenario for Zurich, Switzerland which was first published in [47] and has been used to study the performance of AMoD dispatching algorithms in previous research. For all details on how the artificial population of households and travelers has been synthesized and how the local road infrastructure has been integrated into the MATSim model, we like to refer the interested reader to our previous publication. In the following, we will briefly introduce the simulation scenario with all aspects that are of relevance to our investigation of parking policies.

The simulation scenario covers the urban area of Zurich (see Figure 1) including exogenous traffic. In total, 122,759 travelers are simulated with 334,180 trips to be served by AMoD. Those trips represent the maximum possible demand for such a service derived from trips that were previously performed by private car or public transport. The simulation uses a fine-grained network down to residential roads as they are defined by OpenStreetMap.

In our previous study [26], the whole AMoD demand of Zurich is to be served by fleets of various sizes controlled by four different fleet operating policies. In the present experiments we limit our analysis to a basic operating policy without rebalancing functionality, namely to the Global Bipartite Matching Policy. This policy assigns available vehicles to open requests by solving a bipartite matching problem with costs between vehicles and waiting passengers described by the network distance between them. A more detailed analysis of the interplay of other fleet operational polices and parking space distributions will be an interesting topic for future research. Here, we limit the scope of this study to the well-understood and universally applicable global bipartite matching policy.

In the experiments presented in Hörl et al. [26], morning peak mean wait time is reduced from approximately 4.2 min to 3.1 min if fleet size is increased from 6000 to 9000 vehicles. A further increase to 12,000 vehicles only results in a 0.3 minute decrease in waiting time. A number of 9000 vehicles can therefore be regarded as efficient and would likely be chosen by an operator. Therefore, we limit our present analysis to this fixed fleet size.

4.3. Parking Distributions

We use three different distributions of parking spaces in our study. In all cases, we sample randomly and uniformly the analyzed number of parking spaces from an underlying spatial distribution.

In the first distribution, parking spots are uniformly distributed on all streets in the operating area. This is implemented by determining the set of all roads on which pickups and drop-offs of requests take place in the prepared simulation scenario. This distribution is denoted as (Uniform) in the results section.

The second distribution of parking spots is based on the actual distribution of parking spaces in Zurich which was published by Balac et al. [50]. Only publicly available parking spaces are considered, regardless of their cost or parking time limitations. In total 48,061 parking spots are part of the data set, their distribution is illustrated in Figure 1 in blue color. This distribution is denoted as (Public) in the results section. It is a more realistic case compared to uniform distribution, as it represents infrastructure that is already available in the city. In the experiments section (see below) a number of 36,000 is used as the upper limit of parking spaces in all simulation cases, which means that only a subset of today’s available parking spots is used in simulation.

Finally, we use the distribution of parking spots which was available to the Swiss two-way car-sharing provider Mobility in 2015. The data set has previously been used for the analysis for car sharing demand in Zurich [51]. The spatial distribution of around 190 car sharing parking locations for approx. 400 cars is shown in Figure 1. Clearly, with today’s infrastructure, the car sharing operator could not accommodate 9000 vehicles. Therefore, all simulated cases represent an upsampling of available spots. Yet, they follow a much more spatially discrete distribution than the former two cases. Therefore, they represent a spatially confined situation that an AMoD operator could possibly face. Reasons might be that public parking space in the city was blocked for commercial operators or even transformed for different use. This distribution is denoted as (Car Sharing) in the results section.

4.4. Parking Availability

To test the impacts of the parking capacity on the system metrics, the number of parking locations in the operating area is varied between 1500 and 36,000, which corresponds to four parking spaces per vehicle. It is clear that for the scenarios with the number of parking spaces above 9000 the operator can always find a parking space for all their vehicles within the service area. The Diffusion can furthermore be run without modification for numbers of parking spaces that are lower than the fleet size (as vehicles will roam). For the LP, however, behaviour in those highly constrained scenarios is defined such that only as many vehicles are matched as there are vacant parking spots. The rest of vehicles would therefore idle illegally at their current location. In our experiments, we propose two mitigation strategies: In the standard case, we fall back to using the Diffusion strategy for all vehicles that could not be matched after running the LP strategy. In two other cases, we propose depots with unlimited capacity at strategic locations in the city. The first scenario (A) considers a large deport at the airport (Figure 1) which represents a realistic scenario as the spatial capacity to accommodate a large fleet of 9000 vehicles would be given there. The second scenario (MS) proposes a depot at the main train station of Zurich in the center of the city. While the location is interesting for our analysis as it is a very central location, it is not a realistic alternative.

4.5. Summary

To summarize, we run simulation experiments with …

• … a fleet of 9000 automated taxis serving more than 300,000 requests throughout one day.
• … parking supply configurations between 1500 and 36,000 parking spots.
• … three different base distributions of parking spots (Uniform, Public, Car Sharing).

We analyze these cases either without any parking policy (baseline), or with either the local Diffusion policy or the global LP strategy. For parking supply of less than 9000 spots, the latter is run either with Diffusion as a fallback strategy or with one one of two depots at Zurich airport or the main train station.

5. Results and Discussion

As a baseline case, we evaluate a hypothetical scenario where all vehicles can be parked at the drop-off location. This means that only the global bipartite matching policy is used to guide the behavior of the fleet. Then, the same scenarios are evaluated again with added parking operating policies that determine the behavior idle vehicles. Three important metrics for the evaluation of parking distribution, capacity and strategy are used. Those are total vehicle distance, empty vehicle distance, and pick-up waiting times. Relocation of idle vehicles to parking spots, or their empty cruising induces additional vehicle distance traveled, which is an important efficiency metric of the system, both in economical and ecological terms. The vehicle distance traveled for all configurations is shown in Figure 2, and empty vehicle ratio is presented in Figure 3. As expected, all policies result in an increase of fleet distance compared to the baseline case. However, the level of increase varies. In the best case, under LP strategy and the Uniform parking space distribution with four spaces per vehicle, the total fleet distance increases by only 3%. For the situations where the number of available parking spaces is lower then the number of vehicles. LP with a depot strategies outperform both Diffusion and LP with diffusion as fallback strategies. For very small parking capacities depot at the train station performs better than the airport location. This is explained by the mono-centric characteristic of the city. While Uniform and Public perform similarly, they both outperform Car Sharing distribution. The Car Sharing distribution leads to a concentration of vehicles in very few spots and therefore increases redistribution distance.

The influence of parking operating policies is not limited to an increase in fleet distance. Waiting times as a proxy for customer acceptance and attractiveness of the service represent another important factor. Mean wait times for all configurations are shown in Figure 4. LP clearly outperforms all other strategies for Uniform and Public distributions. It is only outperformed by the Diffusion with Car Sharing distribution and parking capacity of more than one space per vehicle. LP strategy can even reduce waiting times by 50% for Uniform and Public distributions and parking capacities of less then one space per vehicle. In contrast, waiting times increase for a majority of cases by up to 31% for the Car Sharing parking space distribution when the number of parking spaces is larger than the number of vehicles in the operating area. LP with a depot strategies perform the worst in terms of waiting times of the customers. This is explained by the concentration of part of the fleet in these large depots, while in other cases the fleet is better distributed in the network ensuring better coverage and service.

These different changes in waiting times with different parking strategies and distributions can also be explained as follows. While typically in fleet control vehicles are rebalanced to locations of future anticipated demand [33,34,52,53] no rebalancing logic is used on top of the basic global bipartite matching in the present case. Idle and staying vehicles are merely sent to available parking spaces by the parking operating policies. Consequently, parking policies can be interpreted as a different form of rebalancing strategies. If the distribution of parking spaces corresponds well to the actual locations of the demand, a parking policy automatically represents a well-functioning rebalancing policy. In contrast, a strong disparity between customer requests and parking availability can turn an effective parking policy into a malfunctioning rebalancer. Additionally, the locations chosen are typically closer to the origin for higher parking space densities. For higher capacity of parking locations parked cars tend to converge to the city center (Figure 5). This makes sense as Zurich is a mono-centric city.

A similar effect can be seen for the Car Sharing distribution, which leads to a concentration of vehicles in very few spots and therefore increases waiting times, while the Public case distributes vehicles closer to the locations where requests occur frequently. This behavior makes it necessary to assess rebalancing in combination with distribution and density in parking spaces in future studies.

Finally, it is important to observe that there is no clear winning strategy that performs the best in all categories. Therefore, it is necessary to trade-off between the LP with and without the use of the depot location. For parking capacities below 9000 having a depot location at the main train station seems to outperform both the LP with diffusion as fallback and Diffusion strategy. If the parking capacity is not of a concern, increasing the parking capacity from six to nine thousand, and using LP strategy we can except to achieve a substantial decrease in average waiting time with the same level of total fleet distance.

6. Conclusions

Parking overflow mitigation is an important component of the operation of mobility-on-demand systems which was not covered by previous publications. This study closes the research gap by proposing a well-defined problem formulation to assess the effectiveness of parking policies in a mobility-on-demand system. Furthermore, three different policies for parking overflow mitigation are proposed and their effect on system performance is evaluated using three different parking space distributions.

We find that the strategy based on local diffusion of vehicles that only rely on limited information is outperformed in almost all tested scenarios by the alternative strategies that have access to global information and solve the vehicle redistribution problem using mathematical optimization. The globally coordinated policy is shown to bring benefits to the system with both diffusion as a fallback strategy and using large depot as temporary parking location. Which of these is to be used is a mater of taste, aim of the operator, or public policy. If reducing parking space in the city is the primary goal, LP with depot location at the main train station (given enough of space can be dedicated) is probably a better strategy. Otherwise, a configuration with the Uniform or Public parking distribution, parking capacity of one parking space per vehicle and LP strategy is recommended.

The findings show that wide-spread introduction of mobility-on-demand could make available a majority of parking spaces for other use in Zurich. However, this requires global coordination and global information on the distribution of free and occupied parking spaces at all times to keep other system metrics unaffected. Large-scale mobility-on-demand systems would thus require dedicated infrastructure to gain access to this information.

We suggest and plan future research in the following directions. Based on a given distribution of travel demand and under consideration of the fleet operating policy, the optimal distribution of parking spaces in a city should be evaluated. Furthermore, the mathematical optimization formulations presented in this work could be augmented by incorporating not only metrics for efficiency (e.g., fleet distance), but also considering the effects on service level directly. Parking strategies in this paper have been studied as an isolated problem, which does not consider other operational decisions of the operator like rebalancing or ride-pooling. It is, therefore, of importance to asses how the parking requirements would change when all or a combination of operational decisions are at the disposal to the operator. Finally, in the light of most recent results assessing the congestion effects of mobility-on-demand, it is very relevant to assess the effect of parking spot distribution on congestion levels in cities.