Performance Evaluation of Different Dispatching Rules and Heuristics in a Fully Automated Parking System

1Introduction

The exponential growth of vehicles exacerbates urban traffic congestion and parking challenges. As cities face diminishing space amid population growth and increased motorization rates, the construction of multi-story parking systems becomes imperative (Buehler et al., 2017; Pypno, 2008). These systems alleviate space constraints by utilizing vertical structures. Over the past two decades, advancements in technology have propelled the widespread adoption of Fully Automated Parking Systems (FAPS) worldwide. FAPS integrate software systems with mechanical lifts and pallets to efficiently store and retrieve vehicles in multi-level modular garages, achieving up to 84% space utilization (Serpen and Dou, 2015). Apart from optimizing space, FAPSs offer time and energy savings by eliminating the need for searching available parking slots. Despite their advantages, high setup costs and prolonged service times during rush hours pose challenges. The extended waiting times can be attributed to technical issues, poor planning, and customer-related concerns. Without well-coordinated schedules and operational planning to complement mechanical and technological advancements, customer dissatisfaction due to prolonged wait times cannot be mitigated.

While the design of FAPS presents its own set of challenges, ensuring efficient operation is equally crucial for optimizing system performance. This study focuses on developing dispatching rule-based algorithms to efficiently manage vehicle allocation and retrieval in FAPSs. These operational challenges involve complex tasks such as assignment sequencing and real-time task management, which are inherently combinatorial and uncertain. To address these issues, the study employs dispatching rules and heuristics, supported by a simulation model that considers dynamic and stochastic factors. Through rigorous testing, the study identifies the most efficient operating rules among various strategies for FAPS. Overall, this research contributes to optimizing FAPS operations and fills a crucial gap in the literature on operational planning and control in FAPSs. It underscores the importance of integrating customer behaviour and real-time dynamics into the development of dispatching rules, with statistical analysis providing robust support throughout the study.

The structure of the paper is outlined as follows: In Section 2, the problem is elucidated, and contributions to the existing literature gap are underscored. Section 3 delineates the candidate dispatching rules and heuristics. Section 4 introduces the research methodology, including modelling assumptions and system parameters. Section 5 presents the results of the simulation study, assessing the performance of dispatching rules and heuristics, along with a performance analysis. Finally, Section 6 provides a summary of the research and draws general conclusions.

2The Problem Statement and Literature Review

The technological advancements of the last two decades and the benefits of FAPS have made FAPS more attractive all over the world. Still, these systems have some issues that should be handled. As a relatively new and promising topic, problems of these systems are getting more attention from researchers (Y. Chen et al., 2021; Debnath and Serpen, 2015; Mirzaei et al., 2017; Serpen and Dou, 2015; Wu et al., 2019; Yalcin et al., 2018; Zhang et al., 2020). The FAPS design is one of the challenging issues due to the conflict between space utilization and simplicity of operations. The concern of this research is the management of operations, including operational planning and control.

2.2FAPS Operational Planning Problems

Fig. 1

The basic process flow diagram of FAPSs.

The car parking and retrieval process executed in FAPS can be summarized as follows: drivers leave their cars in the entrance bay. Then, vehicles are transported to one empty slot by the robot (carrier) without a driver based on arbitrary or predetermined rules. Later, when the customers return and want to retrieve their cars, they are taken from their parking slots and moved to the exit bay. The basic process flow diagram, which comprises the main operations and constitutes the core of the algorithms, is presented in Fig. 1.

Sequencing of the requests: Car storage and retrieval operations in Fully Automated Parking Systems (FAPS) typically follow a First-Come-First-Served (FCFS) approach. However, alternative heuristic or dispatching rules could potentially enhance performance, contingent upon specific system features and customer profiles. Unfortunately, limited research has been conducted on sequencing problems. Chen and Sun (2017) compared FCFS with cross-access strategies regarding customer waiting time, while Chen et al. (2021) analysed the effects of prioritizing customers who pre-book appointments, using similar performance criteria.

The allocation of cars: The car allocation problem involves determining the most suitable slot for storing each vehicle, often employing a nearest-available-slot approach. This allocation decision significantly influences subsequent operations and must be treated as an optimization problem rather than a simple decision. Although Chen et al. (2021) examined the impact of a dedicated storage policy, they did not address the optimal allocation of individual cars. A study resembling this research was conducted by Y. Chen et al. (2021), Serpen and Debnath (2019), where they utilized a genetic algorithm to determine the optimal parking location for each car in a rotary parking system, minimizing overall parking and pickup times.

Table 1

Summary of the research on FAPS’ operational planning problems.

Reference	Focus	Key findings
Y. Chen et al. (2021), Mirzaei et al. (2017), Serpen and Debnath (2019), Wu et al. (2019), Yalcin et al. (2018), Zhang et al. (2020)	FAPS design issues	Technological advancements have made FAPS more attractive worldwide.
Chen and Sun (2017), Serpen and Dou (2015)	FAPS design efficiency	Different designs (circular vs. rectangular) impact space efficiency and operations.
Chen and Sun (2017)	Sequencing problems	Compared FCFS and cross-access strategies for customer waiting time analysis.
Chen et al. (2021)	Sequencing problems	Analysed the impact of priority for pre-booked customers on performance criteria.
Wu et al. (2019)	Allocation of cars	Employed a genetic algorithm to minimize parking and pickup times for rotary systems.
Kuda et al. (2022)	Demand-supply imbalance	Investigated the imbalance between FAPS demand and supply.
The present study	Sequencing and allocation problem	The performance evaluation of dispatching rules designed to optimize the sequencing of requests and the allocation of FAPSs.

As evident from the literature summarized in Table 1, prior studies predominantly concentrate on the design and technological aspects of Fully Automated Parking Systems (FAPS). However, scant attention has been paid to operational challenges such as low efficiency and extended service times. In contrast, this study shifts the focus towards operational optimization, specifically addressing sequencing and optimal allocation decisions for tower-type FAPSs. Notably, the primary contribution lies in approaching these issues from a customer-centric perspective. To the best of our knowledge, the only study addressing the demand-supply imbalance in FAPSs is conducted by Kuda et al. (2022).

3Candidate Dispatching Rules and Heuristics for FAPS’s operations

Fully Automated Parking Systems (FAPSs) are akin to warehouses equipped with Automated Storage and Retrieval Systems (AS/RS). Both systems feature automated carriers transporting items between entry-exit points and predetermined locations without operator intervention (Roodbergen and Vis, 2009). Despite these parallels, their operational environments diverge significantly. Warehouses encompass diverse material flows and activities, including receiving, storage, order picking, and shipping, alongside ancillary tasks like breakbulk consolidation, sorting, sequencing, batching, and routing (Bartholdi and Hackman, 2011; Manzini, 2012). In contrast, FAPSs involve a simpler process flow focused on allocation, parking, and retrieval, with limited managerial decision-making, resulting in lower system control and flexibility. This reduced flexibility is compounded by the nature of the entities handled in FAPSs.

Unlike the products/materials in the warehouses, the nature of each vehicle stored in the FAPSs is entirely different. It can be expressed that the most critical point where FAPSs and warehouses are inherently separated from each other is the control of entities and events in these systems. There is complete or partial control over how many products/materials will arrive and when the products will be picked up and shipped. However, there is no chance to decide how many vehicles will arrive in the system, how long each car will be parked, and when it will depart.

This paper manages this uncertainty in an ideal way and provides an adequate level of control through the different dispatching rules. In addition to being one of the most important sources of uncertainty, the customer structure/profile is also an essential factor that pressures FAPSs. FAPSs are in direct connection with the end customers. The customer’s request must be quickly and properly responded to as soon as it is realized. In the case of this dynamic and uncertain structure, it is not easy to perform operations effectively and efficiently. Table 2 summarizes the difference in characteristics of the warehouse and fully automated parking systems.

Consequently, numerous effective policies and strategies are proposed in the literature to address warehouse operations like storage and retrieval processes. However, even though FAPSs are like automated warehouse systems in terms of design, their unique operations and entity structure make it impossible to utilize some good-working operational policies and rules in warehouses. There is no chance of batching the items (vehicles) in FAPSs since each item should be handled separately. Here, it can be thought that parking operations are conducted as a single order having a single item. Thus, only some sequencing rules fitting parking lot operations like FIFO and NIF could be used as dispatching rules in these systems. Similarly, there are numerous ways to determine appropriate storage locations in warehouses, such as random storage, closest open location storage, dedicated storage, full turnover storage, and class-based storage. Still, the first two worked in FAPSs because they handled independent and unique items (vehicles).

Considering the system and process characteristics of FAPSs, the candidate dispatching rules described in Table 3 can be used for operational problems. These proposed rules are compiled for specific tower-type FAPSs with a single depth shelve, a single entry-exit bay, and a single transporter lift that can move vertically and horizontally in two dimensions. In the case of different system features (e.g. multiple entry-exit points and transporters, multi-depth selves), there will be a need for different dispatching rules to meet plan and control requirements. Depending on the process flow (see Fig. 1), the next request to be handled, whether parking or retrieval, must be decided. Due to the specific attribute (single entry-exit point) of the system considered in the study, it is impossible to rearrange the sequence of parking requests because they are already in a physical queue formed based on first-come, first-served (FCFS). Therefore, there is only one decision related to parking requests in this situation: the assignment of a parking slot for each car parked. On the other side, customers do not wait in a physical queue when they retrieve their vehicles. Thus, an additional sequencing rule (except for FCFS) can be set to determine the next retrieval in case of more than one retrieval request in the queue. Once the next retrieval request is selected, the car can be picked up from its parking slot and left at the exit bay.

4Research Methodology and Modelling Assumptions

The system features, such as the shape of the building, the number of entry-exit points, etc., are the parameters related to the building structure. In contrast, utilized transport systems like puzzle type, tower type with single or multiple depth selves, etc., correspond to technical specifications. Another parameter should be considered when designing and operating the system. This parameter is the customer profile related to customer density and customer behaviours, such as the arrival/departure patterns, parking duration, etc. All these system parameters should be considered carefully when addressing operational decision problems. The proposed rules that help to sequence the requests and assign cars to an appropriate place are embedded in the main control algorithm, as shown in Fig. 2, to ensure the planning and control of FAPSs.

Fig. 2

Main control algorithm and embedded heuristics and rules.

It was mentioned that two performance metrics would be used to evaluate the success, namely the average waiting time of the customers (customer satisfaction) and the total distance covered in the system (efficiency of the system). In this context, “the total distance travelled in the system”, which has a deterministic structure and directly affects the customers’ waiting time, is considered “the objective function” when deciding on the optimal location. Let’s assume that Transport(x,y,z)t[TeX:] $\textit{Transport}{(x,y,z)_{t}}$ is the starting position (coordinates) of the carrier/transporter and Transport(x′,y′,z′)t′[TeX:] $\textit{Transport}{({x^{\prime }},{y^{\prime }},{z^{\prime }})_{{t^{\prime }}}}$ is the position of the carrier at the end of the transportation process. Vx[TeX:] ${V_{x}}$, Vy[TeX:] ${V_{y}}$, Vz[TeX:] ${V_{z}}$, gives the velocity of the carrier on x–y–z axis, respectively. In this case, Δd[TeX:] $\Delta d$ represents the distance travelled by the transporter to perform the transaction (whether parking or retrieval), and Δt[TeX:] $\Delta t$ represents the time spent on the transaction. Depending on the system parameters, the distance and time covered in each allocation and retrieval operation are calculated according to the equations below. Also, a nomenclature Table A1 is given in Appendix A.

Equations (1) and (2) ensure to measure performance criteria related to the distance travelled and the time spent for each transaction. The total distance travelled in the system and the total transaction time can be calculated by Eqs. (3) and (4), respectively. Where Dtotal[TeX:] ${D_{\textit{total}}}$ represents “total distance”, Ttotal[TeX:] ${T_{\textit{total}}}$ represents “total time” for the transactions. Sets of PT[TeX:] $\textit{PT}$ and RT[TeX:] $\textit{RT}$ include parking and retrieval transactions, respectively, and Nt[TeX:] ${N_{t}}$ is the total number of transactions within the considered period. Consequently, the mean distance travelled per transaction and mean time spent per transaction (operation) can be calculated by equations (5) and (6).

The performance criterion related to customer satisfaction is measured by the customer waiting time. However, previous studies mainly related considered customer waiting times to solely retrieval transactions (Debnath and Serpen, 2015; Serpen and Debnath, 2019). In this study, we consider and plan both parking and retrieval transactions at the same time. Based on previous studies, we used the following two equations to calculate customer waiting times through the parking (7) and retrieval (8) operations, respectively. Here, wip[TeX:] ${w_{i}^{p}}$ and wir[TeX:] ${w_{i}^{r}}$ represents waiting time of transaction i for parking and retrieval respectively. tia[TeX:] ${t_{i}^{a}}$ is request time and tid[TeX:] ${t_{i}^{d}}$ is actualization time o of transaction i.

In detail, tia[TeX:] ${t_{i}^{a}}$ represents the customer’s arrival time at the system, and tid[TeX:] ${t_{i}^{d}}$ represents the customer’s departure time from the system for each request. Ca[TeX:] ${C_{a}}$ represents the set of customers parking their cars, while Cd[TeX:] ${C_{d}}$ represents the set of customers retrieving their cars. Based on these assumptions, the average waiting times per customer are calculated as follows: Na[TeX:] ${N_{a}}$ is number of customers arrived and Nd[TeX:] ${N_{d}}$ is number of customers departed, which represents each number of parking or retrieval transactions. Average waiting times per parking Wp[TeX:] ${W^{p}}$ and retrieval operation Wr[TeX:] ${W^{r}}$ are calculated by Eqs. (9) and (10). Finally, W gives (11) the average waiting time per transaction (operation).

In the next step, a simulation model is constituted to test the developed algorithm’s validity and evaluate the performance of dispatching rules, as the simulation is probably the most convenient tool for analysing such dynamic and stochastic systems. The developed simulation model and its important components are presented in Fig. 3. Based on the problem structure, on the one hand, physical and technical features of the considered FAPS and customer profile details are inputs of the simulation model. However, the next operation that will be handled and the place where the car will be placed constitute decision variables of the system. Finally, the efficiency of the candidate dispatching rules will be evaluated depending on performance measurements (system’s output), like average customer waiting time and the average distance travelled in the system.

Fig. 3

The main components of the developed simulation model.

Considering the importance of the system parameters, it becomes more critical to consider their deterministic and stochastic natures when providing inputs to the simulation model. Therefore, the following section and subsections provide detailed information about the assumptions and other specifications of the FAPS considered in the experimental case study.

4.1System Parameters of the Experimental Study

It is possible to examine the parameters related to FAPSs in two categories as deterministic and stochastic system parameters. For the first group of parameters, the related values are (mostly) certain, and the acquisition of data is relatively easy. However, the second group of parameters is difficult to collect, and the collected raw data is not suitable for direct use. There is a need for additional analyses to produce proper data for the system. Hence, the parameters of the FAPS considered in the experimental study are examined in two subsections as follows.

4.1.1Deterministic System Parameters

The physical and technical features of the system are the members of the first group parameters. The size and layout of the slots and building, the speed of the transporters and other mechanical equipment, and the capacity of the system – the number of slots, are parameters that should be identified properly. These kinds of parameters have deterministic values, which are decided during the design and installation phase. The other design assumptions related to the system considered for the experimental study can be summarized as follows. The FAPS has:

• ✓ Rectangular design;

• ✓ Multi-story structure;

• ✓ Single entrance/ exit point;

• ✓ Single aisle;

• ✓ Single depth slot layout;

• ✓ Single transporter (robot) moving vertically on the z-axis and horizontally on the x-axis;

• ✓ Conveyors move horizontally on the y-axis.

The following floor structure representation (Fig. 5) might help to comprehend the system’s dimensions. The horizontal moves carried out on each floor are considered on the (x−y)[TeX:] $(x-y)$ axis, whereas the vertical moves between floors are considered on the z-axis. In this case, the transporter is responsible for vertical and horizontal transportation on the z-axis and x-axis, respectively. Once the transportation on the x-axis is ended, the conveyors execute the horizontal Transport on the y-axis. When ignoring the acceleration and deceleration, it is assumed that the speed of the transporter and conveyors on the corresponding axis is constant and the same as 0.5 meters in a second. Additionally, Fig. 4 demonstrates the floor layout in terms of slots. The single entry-exit bay is located on the ground floor, and the cars are rotated in this bay so that they can be inserted into slots and then transported to the upper floors. Similarly, the cars are rotated in the same bay at the end of the retrieve operation so that drivers can leave the system. Because of these rotations, the bay has a square shape of 8×8[TeX:] $8\times 8$ m size. Except that all other slots are identical and have the same size indicated in Fig. 8. As a final issue, the specified multi-story FAPS consists of 10 floors. There are 10 slots on each floor, 5 of which are located at the right and left of the aisle. In total, the capacity of the considered tower type FAPS is 100 slots, namely 100 cars.

Fig. 4

Floor structure and slot layout of the considered FAPS.

4.1.2Stochastic System Parameters

In addition to the physical and technical data, data including required information about the customer also should be provided before investigating system performance. Therefore, a detailed customer analysis should be carried out when designing the system and setting technical parameters. An accurate analysis is a key factor that leads to the efficient design and operating system. The number of customers, arrival and departure times, parking durations of the customers take probabilistic values within a day. For example, in rush hours, when people commute to and from work, the parking and retrieval demand would be quite high, whereas other hours would be relatively balanced but never known exactly. Similarly, the parking durations differ from customer to customer and are generally not predictable. Therefore, to construct a reliable simulation model of the system and ultimately give credible results, actual data about the customer’s behaviours should be obtained and analysed. With this motivation, real data is provided from a FAPS located in Izmir/Alsancak. The provided data consists of customer records belonging to the first 3 months (January, February, and March) of 2017, and the following statistical information is extracted from these records.

• 1. The number of customers;

• 2. The arrival and departure patterns of these customers, and

• 3. How long they parked their cars (parking durations).

Primarily, these records are filtered and cleaned to ensure proper data sets, which enable us to carry out overall analyses and, consequently, statistical analyses. Input Analyser of Arena^® Simulation Software is utilized to determine the relevant statistical distributions of the customer profile. The software applies different goodness-of-fit tests like Chi-Square and Kolmogorov-Smirnov to the given data file and determines the distribution that will best fit the data. All applicable distributions are fitted to the data, and then the distributions are sorted based on their corresponding square errors (Chung, 2003; Gingu and Zapcui, 2015; Rockwell Automation, 2022). In this way, the most suitable distribution functions for the case of Izmir are discovered. The detail of all analyses is clarified in the following subsections. The software (Arena input analyser) applies the goodness of fit tests for all possible distributions and suggests the best-fit distribution function of the data based on square error. The detail of best-fit functions for the case of Alsancak FAPS are introduced in Table 4.

Analysis of Customer Numbers. The system at issue was used by more than 30 000 customers, according to the data for three months. Daily customer arrivals (demand) in the examined data varied from 92 to 578. This great variability leads to investigating the cause of this situation and to finding out if variability depends on some variables.

Fig. 5

The number of customers based on days of the week.

The first analysis carried out on charts (Fig. 5a) showed that there is no great difference between months in terms of the number of customers. However, the same data, when visualized depending on the day of the week, indicates that the number of customers differentiates according to the days of the week. A similar week pattern is observed within the three months (Fig. 5b), except for very limited cases. In the graphs J represents January, F: February, M: March and J1 represents 1st week of January, J2: 2st week of January, etc. It is explicitly seen that there is a pattern for the week, in which the number of customers is varied on different days.

The next step is statistically analysing the number of customers varied on days of the week to determine the probability distribution functions that belong to each day. With the help of the Input Analyser of Arena^® software, it is possible and easy to determine the best distribution function that represents the data set belonging to each day. The distribution functions are produced by using 12 samples (12 weeks’ data) of each day to represent the variance of customer numbers depending on the days of the week. Based on the given data, the number of customer arrivals fits the triangular distribution (Monday, Thursday, Saturday) and the beta distribution (Tuesday, Wednesday, Friday) for six days of the week, and only Sunday fits the normal distribution. Parameters of all distribution functions are provided by the software. The statistical test (Kolmogorov–Smirnov goodness-of-fit) results indicate a good fit for all cases according to acceptable SSE values. SSE is defined as the sum of {fi−f(xi)}2[TeX:] ${\{fi-f(xi)\}^{2}}$ for overall histogram intervals and primarily represents the quality of a curve fit (Arena^®). Thus, these distribution functions could be utilized in the simulation model to generate different customer numbers to ensure the validity of the experimental study and its results.

Analysis of Arrival and Departure Patterns of Customers. 

Fig. 6

Arrival and departure pattern of the customers based on days of the week.

Customer arrivals and departures are not balanced in a day due to rush hours. Based on the commute to work, mostly, the number of parking requests is higher than retrieval requests in the early morning and vice versa towards evening. This situation is valid for the downtown areas where the car parking problem is an important issue. Of course, there are exceptions to these behaviours due to residents settled near the FAPS and who park their cars after work. Considering all these situations, the density of requests within a day should be analysed carefully. In this respect, based on the data provided from the Alsancak FAPS, customer arrival and departure times belonging to one week are visualized in Fig. 6. In addition to the pattern that depends on work hours, a different parking and retrieval pattern arises on Friday and Saturday nights because customers’ behaviour is changed at the weekend. Parking requests are increased after 19:00, and some of the retrieval’s requests sag to after midnight between 00:00–04:00. Sunday has a quite different pattern from the arrival and departure patterns observed on other days. Less number of customers and more balanced but more irregular arrival/departures are observed throughout the day. In addition to the pattern that depends on work hours, a different parking and retrieval pattern arises on Friday and Saturday nights because customers’ behaviours are changed on weekends. Parking requests increase after 19:00, and some of the retrieval’s requests sag after midnight between 00:00–04:00. On the other hand, Sunday has a quite different pattern from the arrival and departure patterns observed on other days. Less number of customers are observed with more irregular arrival and departures.

To uncover underlying patterns and trends, we analysed the relevant dataset using Arena^® Input Analyzer. It’s important to note that, unlike traditional queuing theory, we do not consider inter-arrival times for FAPSs. This is because FAPS environments do not exhibit homogeneous customer distributions throughout the day, leading to varying arrival patterns. Instead, our approach focuses on analysing empirical arriving and departure data to model customer behaviour. This allows us to develop dispatching rules that better reflect real-world scenarios and enhance system efficiency (Büchel and Corman, 2020; Guo et al., 2016; Ingvardson and Nielsen, 2018). Therefore, for enhanced practicality, this study considers the time of day rather than inter-arrival times of customers, analysing the number of requests arriving at these specific moments. Table 4 demonstrates that all distribution functions exhibit a good fit based on SSE values. As previously outlined, the parameters and predicted variables of these distribution functions pertain to continuous time intervals spanning from 00:00 to 24:00. It is noteworthy that while the same distributions exhibit different parameters, there exists a diverse range of arrival distribution patterns such as Gamma, Beta, and Triangular. This underscores the necessity of incorporating customer attributes into the simulation model based on different days of the week.

Table 4

The best-fit distribution function for customer’s behaviours.

		Distributions’ parameters	Distribution function	6SSE
Distribution functions of customer numbers that are used in the experimental study	Monday	1Triangular f(x;a,b,c)[TeX:] $f(x;a,b,c)$	TRIA(294,383,419)[TeX:] $\text{TRIA}(294,383,419)$	0.056548
	Tuesday	2Beta f(x;α,β)[TeX:] $f(x;\alpha ,\beta )$	139+301∗BETA(1.25,0.413)[TeX:] $139+301{\hspace{0.1667em}^{\ast }}\hspace{0.1667em}\text{BETA}(1.25,0.413)$	0.057014
	Wednesday	2Beta f(x;α,β)[TeX:] $f(x;\alpha ,\beta )$	299+142∗BETA(0.884,0.563)[TeX:] $299+142{\hspace{0.1667em}^{\ast }}\hspace{0.1667em}\text{BETA}(0.884,0.563)$	0.044574
	Thursday	Triangular f(x;a,b,c)[TeX:] $f(x;a,b,c)$	TRIA(299,427,482)[TeX:] $\text{TRIA}(299,427,482)$	0.016156
	Friday	2Beta f(x;αbeta)[TeX:] $f(x;\alpha \hspace{0.1667em}beta)$	282+253∗BETA(1.09,0.414)[TeX:] $282+253{\hspace{0.1667em}^{\ast }}\hspace{0.1667em}\text{BETA}(1.09,0.414)$	0.044131
	Saturday	1Triangular f(x;a,b,c)[TeX:] $f(x;a,b,c)$	TRIA(387,559,578)[TeX:] $\text{TRIA}(387,559,578)$	0.083642
	Sunday	3Normal f(x;μ,σ)[TeX:] $f(x;\mu ,\sigma )$	NORM(177,49.9)[TeX:] $\text{NORM}(177,49.9)$	0.045688
Distribution functions of arrival patterns of the days	Monday	4Gamma f(x;k,θ)[TeX:] $f(x;k,\theta )$	2+GAMM(11.5,1.02)[TeX:] $2+\text{GAMM}(11.5,1.02)$	0.003987
	Tuesday	2Beta f(x;α,β)[TeX:] $f(x;\alpha ,\beta )$	7+16∗BETA(2.13,2.43)[TeX:] $7+16{\hspace{0.1667em}^{\ast }}\hspace{0.1667em}\text{BETA}(2.13,2.43)$	0.004665
	Wednesday	3Gamma f(x;k,θ)[TeX:] $f(x;k,\theta )$	GAMM(13.7,1.04)[TeX:] $\text{GAMM}(13.7,1.04)$	0.004272
	Thursday	2Beta f(x;α,β)[TeX:] $f(x;\alpha ,\beta )$	24∗BETA(6.07,4.11)[TeX:] $24{\hspace{0.1667em}^{\ast }}\hspace{0.1667em}\text{BETA}(6.07,4.11)$	0.006749
	Friday	1Triangular f(x;a,b,c)[TeX:] $f(x;a,b,c)$	TRIA(7,11.3,24)[TeX:] $\text{TRIA}(7,11.3,24)$	0.004850
	Saturday	4Gamma f(x;k,θ)[TeX:] $f(x;k,\theta )$	−0.001+GAMM(2.28,6.69)[TeX:] $-0.001+\text{GAMM}(2.28,6.69)$	0.008231
	Sunday	1Triangular f(x;a,b,c)[TeX:] $f(x;a,b,c)$	TRIA(−0.001,19,24)[TeX:] $\text{TRIA}(-0.001,19,24)$	0.030448
Distribution functions of departure patterns of the days	Monday	2Beta f(x;α,β)[TeX:] $f(x;\alpha ,\beta )$	−0.001+24∗BETA(4.58,2.29)[TeX:] $-0.001+24{\hspace{0.1667em}^{\ast }}\hspace{0.1667em}\text{BETA}(4.58,2.29)$	0.005597
	Tuesday	3Normal f(x;μ,σ)[TeX:] $f(x;\mu ,\sigma )$	NORM(16.4,4.41)[TeX:] $\text{NORM}(16.4,4.41)$	0.003739
	Wednesday	3Normal f(x;μ,σ)[TeX:] $f(x;\mu ,\sigma )$	NORM(16.1,4.41)[TeX:] $\text{NORM}(16.1,4.41)$	0.015429
	Thursday	3Normal f(x;μ,σ)[TeX:] $f(x;\mu ,\sigma )$	NORM(16.1,4.43)[TeX:] $\text{NORM}(16.1,4.43)$	0.006464
	Friday	3Normal f(x;μ,σ)[TeX:] $f(x;\mu ,\sigma )$	NORM(15.5,5.88)[TeX:] $\text{NORM}(15.5,5.88)$	0.011663
	Saturday	2Beta f(x;α,β)[TeX:] $f(x;\alpha ,\beta )$	−0.001+24∗BETA(0.983,0.789)[TeX:] $-0.001+24{\hspace{0.1667em}^{\ast }}\hspace{0.1667em}\text{BETA}(0.983,0.789)$	0.015944
	Sunday	1Triangular f(x;a,b,c)[TeX:] $f(x;a,b,c)$	TRIA(−0.001,19,24)[TeX:] $\text{TRIA}(-0.001,19,24)$	0.030448
Distribution functions of parking durations of customers depending on days of the week	Monday	5Lognormal f(x;μ,σ)[TeX:] $f(x;\mu ,\sigma )$	LOGN(2.96,3.26)[TeX:] $\text{LOGN}(2.96,3.26)$	0.004684
	Tuesday	5Lognormal f(x;μ,σ)[TeX:] $f(x;\mu ,\sigma )$	LOGN(2.79,2.75)[TeX:] $\text{LOGN}(2.79,2.75)$	0.001334
	Wednesday	4Gamma f(x;k,θ)[TeX:] $f(x;k,\theta )$	GAMM(1.52,1.69)[TeX:] $\text{GAMM}(1.52,1.69)$	0.013259
	Thursday	5Lognormal f(x;μ,σ)[TeX:] $f(x;\mu ,\sigma )$	LOGN(2.6,2.97)[TeX:] $\text{LOGN}(2.6,2.97)$	0.000498
	Friday	5Lognormal f(x;μ,σ)[TeX:] $f(x;\mu ,\sigma )$	LOGN(2.91,2.58)[TeX:] $\text{LOGN}(2.91,2.58)$	0.003551
	Saturday	4Gamma f(x;k,θ)[TeX:] $f(x;k,\theta )$	GAMM(1.77,1.92)[TeX:] $\text{GAMM}(1.77,1.92)$	0.011073
	Sunday	5Lognormal f(x;μ,σ)[TeX:] $f(x;\mu ,\sigma )$	LOGN(3.28,3.09)[TeX:] $\text{LOGN}(3.28,3.09)$	0.004846

¹Triangular distribution: lower limit a, upper limit b and mode c, where a<b[TeX:] $a\lt b$ and a⩽c⩽b[TeX:] $a\leqslant c\leqslant b$.

²Beta distribution: 0⩽x⩽1[TeX:] $0\leqslant x\leqslant 1$ and α,β>0[TeX:] $\alpha ,\beta \gt 0$ where α,β[TeX:] $\alpha ,\beta $ are shape parameters.

³Normal distribution: μ = mean, σ = standard deviation.

⁴Gamma distribution: k,θ>0[TeX:] $k,\theta \gt 0$ where k shape, θ scale parameters and k∗θ=μ[TeX:] $k{\hspace{0.1667em}^{\ast }}\hspace{0.1667em}\theta =\mu $ (mean).

⁵Lognormal: 0⩽x[TeX:] $0\leqslant x$ and μ = mean, σ = standard deviation.

⁶SSE: Sum of Square Error = {fi−f(xi)}2[TeX:] ${\{fi-f(xi)\}^{2}}$.

Analysis of Parking Durations. Parking duration is a critical factor influencing both customer departure patterns and the efficiency of allocation decisions within the system. Figure 7 depicts customer behaviours concerning parking durations, revealing that the majority of customers park their cars for less than 10 hours, with many not exceeding 5 hours. While some cases extend beyond 20 hours, they are less frequent. Furthermore, distinct duration patterns emerge for different days of the week. Statistical analysis of these patterns enables the derivation of probability distribution functions and their respective parameter values, as presented in Table 4.

Fig. 7

Parking duration of the customers based on days of the week.

There are two distribution functions which are Lognormal and Gamma, that can represent parking duration patterns for all days of the week with quite low SSE’s values. The mean of the samples (μ) and standard deviation (σ) are the parameters of Lognormal, whereas shape (k) and scale parameters (θ), where ∗θ=μ[TeX:] ${^{\ast }}\theta =\mu $, are used in Erlang. As a practical interpretation, the discovered functions show that the mean parking duration and the variance of these durations are varied by day.

4.2Verification and Validation of the Simulation Model

So far, all analyses have been carried out to provide the required inputs for the simulation model that will be employed to compare the performance of different dispatching rules. The simulation model is built on physical-technical details and actual customer data. However, at this point, there is an important decision about the simulation modelling approach. There is no doubt that discrete event simulation is suitable for FAPSs as variables change at discrete times and by discrete steps. There are two simulation modelling approaches which are terminating or non-terminating simulation modelling. Terminating systems have initial starting conditions, a natural terminating event. However, non-terminating systems generally can either have a terminating event but keep entities in the system between periods and not have a terminating event and run continuously (Chung, 2003). Considering customer behaviours and discovered data patterns, it could be concluded that FAPSs should be modelled as a terminating system. However, we know that FAPSs are commonly open 7/24[TeX:] $7/24$ most of the time, and customers can leave or retrieve their car at any time of the day. Besides, interdependent events may not end within a day. A good example of this situation is that the customers leave their cars for the night and retrieve their cars early when commuting to work. Another example is that some customers retrieve their cars a couple of days after leaving. All these circumstances indicate that the FAPSs are continuous systems, even though their parameters have a discrete nature. The features of the simulation model developed in this study can be summarized as follows:

• • The non-terminating simulation model of the system is developed.

• • The capacity of the considered system and the density of the customers are balanced. That means that customer arrivals generally do not exceed the capacity at any time.

• • The customers waiting for parking in the queue do not leave the system or are not rejected unless the capacity is full.

• • The stochastic parameters of the model, which are related to customers, are varied depending on the days of the week.

The simulation model is developed in MATLAB environments based on these facts and assumptions. Although the actual simulation study will be conducted for 6 months, the model is run for two weeks (14 days) here to check the pattern of system parameters and verify the simulation model. The state variables that denote the number of cars in the system (a), the average time spent per operation (b), and the average customer waiting time per operation is depicted hourly through the simulation run length in Fig. 8. In addition to the number of cars in the system, Fig. 8(a) also indicates arrival and departure patterns. The relevant graph also shows that the model’s customer behaviours are reflected successfully with the help of the distribution functions. Besides, the same Fig. 8 proves that the system never turns to the starting condition at any time, which means the FAPS is a non-terminating system. Fig. 8(b)–(c) reveal that the system reaches a steady state after 100 h (4 days) after the zero initial states. This period is entitled a warm-up period, and the effect of this period should be eliminated from the overall system (Özgün and Barlas, 2009). Thus, the simulation run length should be determined appropriately to ensure accurate results free of starting conditions. Previous research suggests at least a ten-times warp-up period for non-terminating simulation models (Chung, 2003).

Fig. 8

An overview of the system at the end of the 14 days simulation run. a) the number of cars in the system, b) the average time spent per operation, c) the average customer waiting time per operation.

A long simulation run enhances the quality of the results. Hence, the simulation run length is determined as six months (180 days) as approved by the system manager. To improve the quality and reliability of the outcomes, 10 replications, each of six months’ length comprising the January-June period, are performed based on the customer data provided. The performance of the dispatching rules proposed operations is evaluated based on the average of these 10 replications introduced in Table 5.

Table 5

All possible combinations of the proposed dispatching rules and their performance results.

5Results and Discussions of the Simulation Study

When dealing with a multi-objective problem, it entails considering a diverse set of solutions rather than favouring just a single solution. No single solution within this set can be deemed universally better than another, as each solution may outperform the others in certain aspects or objectives while lagging in others. This collection of solutions is referred to as non-dominated solutions. When these solutions are graphically depicted in the objective-functions space, they collectively form what is commonly known as the Pareto front (Carneiro de Albuquerque et al., 2012).

In our case, for all performance criteria related to customers’ waiting time and system utilization, the rules with the minimum values are preferable to others. According to the Table 5, the inner rules that support PRF and RRF rules do not significantly impact the performance. On the other hand, the average results demonstrate that the combination of the allocation rule and FCFS sequencing rule outperforms all other combinations. The average waiting time and distance travelled per operation are selected as performance criteria (objective functions) and represent the performance of the 24 rules combination summarized in Table 6. The Pareto graph of these two objective functions is depicted in Fig. 9.

Fig. 9

The Pareto chart based on two objectives for 24 rule combination.

Figure 9 shows how the performance of RAS, NAS, and FAS, which are allocation strategy (rule), stacks up. According to the figure, the combination of NAS Pareto-optimal strategy and FCFS used with NAS appears as a Pareto-optimal combination. The difference between these three allocation strategies can be neglected since the difference can be derived from the stochastic nature of the system parameters. Thus, it should be investigated whether the difference between the three allocation rules seen in Fig. 9 is statistically significant. For this purpose, the two main performance metrics, average waiting time per operation and average transfer distance per operation, are analysed.

Fig. 10

The results of Friedman’s Two-Way Analysis for allocation rules.

The sample size for all examples is 96 (see Table 5), so the Shapiro-Wilk test should be used. For all variables, the significance level (p<0.05)[TeX:] $(p\lt 0.05)$ suggests strong evidence of non-normality. For this reason, a non-parametric two-way variance analysis like Friedman Test, the Kendall’s W test, and the Cochran’s Q test for more than two related samples should be used when examining the research question: “Is there a statistically significant difference between the performance of three allocation rules?” (Eymen, 2007; Neuhäuser, 2012). The differences between performance metrics are investigated by mentioned statistical methods in SPSS and results are shared in Fig. 10. As described in the table generated by SPSS, the null hypo study “the distribution of RAS, NAS, and FAS is same” is rejected since (p<0.05)[TeX:] $(p\lt 0.05)$, which means performance of allocation rules show statistically meaningful differences.

5.1Comparison of Allocation and Sequencing Rules’ Performances

The best results were obtained by applying NAS and FCFS dispatching rules for allocation and sequencing decisions. Therefore, additional analysis is conducted in this section to determine whether one of these rules is responsible for good performance results. First, the results are analysed according to allocation dispatching rules. In this regard, the results are compiled under the allocation rules of RAS, NAS, and FAS to eliminate the impact of all sequencing decision rules.

Table 7

The overall performance of allocation rules.

The values for each allocation rule are calculated by averaging across all 8 sequencing rule combinations. Table 7 presents the computed average values, indicating the overall performance of each allocation strategy. Results demonstrate that the FAS strategy is the least efficient, while the NAS strategy stands out as the most effective. Additionally, the superiority of strategies is evident, with NAS>RAS>FAS, as each outperforms the others across all performance criteria. In contrast, when a similar process is carried out for sequencing rules, and the average performance values are computed as in Table 8, it is seen that no sharp line exists among sequencing strategies. The compiled results again clearly reveal that the PRF sequencing rule increases the number of rejected customers compared with other sequencing rules.

Table 8

The overall performance of sequencing rules.

Sequencing rules	# of customers			Customer wait
Simulation of the 6-month period	Total # of served customers	Total # of rejected customers	Average # of customers per day	Average wait for parking	Average wait for retrieval	Average wait per operation
Average of FCFS	29514.43	4.73	163.97	2.53	3.39	2.96
Average of NRF	29601.17	3.27	164.45	4.97	2.42	3.70
Average of PRF	29592.28	60.78	164.40	1.32	5.96	3.67
Average of RRF	29605.78	2.37	164.48	5.12	2.40	3.76

Sequencing rules	System utilization
Simulation of the 6-month period	Trans dist. (m) per operation	Trans time (min) per operation	∗Daily trans dist. (m)	∗Daily trans times (min)	Total trans dist. (km)	Total trans times (h)
Average of FCFS	91.27	3.31	14939.28	541.70	2689.07	97506.18
Average of NRF	92.78	3.36	15268.48	552.80	2748.33	99504.54
Average of PRF	91.61	3.32	15070.46	546.19	2712.68	98314.79
Average of RRF	92.89	3.36	15289.84	553.52	2752.17	99633.89

As another issue, unlike the allocation rules, it is impossible to mention the exact superiority of sequencing rules. However, if the performance criteria are examined under two separate groups, it may be possible to refer to an exact order for system utilization criteria as FCFS > PRF > NRF > RRF. But the same situation is not valid for customer waiting times, and the best performance values belong to different sequencing rules. Besides, there are no significant differences between the performances of sequencing strategies, even between the best and worst performance values related to each criterion.

Table 9

Impact ofallocation and sequencing rules/strategies on performance improvement.

	Variation of allocation rules		Variation of sequencing rules
	Min imp. (%)	Max imp. (%)	Min imp. (%)	Max imp. (%)
Customer wait	37	63	1	21
System utilization	15	36	0	2

To figure out the limited impact of the sequencing strategies on the performance of the system, the improvement variation provided by implementing sequencing rules could be compared with the allocation rules. In the situation presented in Table 9, the best possible improvement achievable by changing the sequencing strategy is around 21%, while implementing the best allocation strategy can yield up to 63%. Although it has been discussed literally in the problem statement section, this result numerically proves the importance and great impact of the allocation decisions for FAPSs. That means if the assignment/allocation problem of FAPSs is studied more intensively, a significant improvement can be created in the operational efficiency of FAPSs. In this respect, future research directions can be shaped based on this fact.

5.2Analysis of Dispatching Rules Under Different Conditions

This section investigates the performance of the dispatching rules utilized for allocation and sequence decisions under different conditions such as arrival rates, parking duration, and arrival patterns. The values of parameters, except for the investigated one, are kept constant to ensure reliable results. The analysis of different customer arrival rates demonstrates that the NAS allocation rule performs better as the customer arrival rate increases. As customer parking durations increase, the differences in performance between allocation rules decrease, but NAS remains the best-performing rule. The arrival pattern of customers throughout the day also significantly impacts system performance, highlighting the importance of well-tailored allocation strategies to improve customer satisfaction. Details of the experiments are presented in each relevant case.

5.2.1Performance Analysis Based on Mean Arrivals

When examining the performance of the allocation and dispatching rules, thoroughly the same distribution functions related to the arrival pattern and parking durations are used in the simulation study. However, the average number of customers who arrive each day is altered systematically to analyse the impact of customer arrival on the performance of rules. The performance of allocation and sequencing rules depending on daily customer arrivals varied from 90 to 640 are illustrated in Fig. 11 and Fig. 12.

The relative performance of allocation rules RAS, NAS, and FAS in terms of capacity utilization (e.g. the total number of customers served, rejected, and left the system due to long queues) and system efficiency is seen in Fig. 11. The results show that NAS outperforms the other as the customer arrival rate increases. On the other side, there is no distinct superiority between dispatching rules (Fig. 12), but the aggregate performance of FCFS is better than the other.

Fig. 11

Performance of Allocation Rules in terms of capacity utilization and system efficiency.

Fig. 12

Performance of Sequencing Rules in terms of capacity utilization and system efficiency.

5.2.2Performance Analysis Based on Mean Duration

In the evaluation of allocation and dispatching rules, consistent distribution functions are employed for arrival patterns and rates in the simulation study. The average parking duration per customer is systematically adjusted to assess the influence of parking durations on rule performance. Figures 13 and 14 depict the performance of allocation and sequencing rules across duration patterns, ranging from 0.7 to 12.6 hours on average per customer.

Fig. 13

Performance of Allocation Rules in terms of capacity utilization and system efficiency.

Fig. 14

Performance of Sequencing Rules in terms of capacity utilization and system efficiency.

The relative performance of allocation rules RAS, NAS, and FAS in terms of capacity utilization (e.g. the total number of customers served, rejected, and left the system due to long queues) and system efficiency in Fig. 13. The results show that NAS outperforms the other in all performance criteria. However, as the customer’s parking duration increases, the difference between the allocation strategies decreases. When dispatching rules are investigated in Fig. 14, FCFS and NRF outperform the other rules, especially in terms of capacity utilization, the difference between the rules is decreased as customers leave their cars for a long time.

5.2.3Performance Analysis Based on Duration Pattern

The distribution functions related to system inputs are preserved, and only the mean values have been modified so far. In the following subsection, the parameter values of the functions are altered to provide the same mean value but with different standard deviations. The performance of the rules is discussed as the standard deviation (std) of the function is increased/decreased. The beta distribution function has a good fit for customer parking durations. The functions and their parameter values are given in Fig. 15.

Fig. 15

The distribution function used for parking durations and its parameter values.

As seen in Fig. 16, all rules have better performance in case of the customer’s parking durations have a wide range and are relatively steady. But the impact of the deviations is higher on capacity utilization efficiency while relatively lower on system efficiency. Also, Fig. 17 shows that the efficiency of the sequencing rules is affected by the deviation in parking duration more than the allocation rules.

Fig. 16

Performance of Allocation Rules in terms of capacity utilization and system efficiency.

Fig. 17

Performance of Sequencing Rules in terms of capacity utilization and system efficiency.

5.2.4Performance Analysis Based on Arrival Patterns

Finally, the last analysis of the customer arrival pattern within a day is carried out. The arrival pattern of the customers fits the Beta distribution, too. The considered functions and their parameter values are given in Fig. 18. Here, the performance of the rules is analysed for a relatively regular arrival pattern (beta1) and a rush-hour pattern (beta3). As shown in Fig. 19, the efficiency of the allocation is highly affected by the arrival pattern of the customer. Moreover, the arrival pattern directly affects customer satisfaction level since the system cannot respond to requests as the arrival rate of the customer increases in a small-time interval. The same effect is observed for sequencing rules with a difference, these groups of rules have more impact on system efficiency as the arrivals are getting the rush pattern as seen in Fig. 20.

Fig. 18

The distribution function used for parking durations and its parameter values.

6Conclusion and Future Work

The interest in FAPSs is increasing worldwide, but academic/scientific studies on this subject are still limited, and there is a research need in this area. In the scope of this paper, a generic algorithm is developed to provide planning and control of operations in fully automated parking systems. Different dispatching rules that can be utilized for assignment/allocation and request sequencing decisions are identified. Also, a simulation model is designed to test the performance of the distribution rules and heuristics.

Fig. 19

Performance of Allocation Rules in terms of capacity utilization and system efficiency.

Fig. 20

Performance of Sequencing Rules in terms of capacity utilization and system efficiency.

This study’s key contributions include the integration of customer behaviour into dispatching rules through a sophisticated simulation model for Fully Automated Parking Systems. It introduces novel dispatching rules and evaluates their impact on system performance, highlighting the importance of allocation decisions. However, limitations exist concerning the scope of dispatching rules, generalizability to different FAPSs, external factors, and the absence of real-world implementation, suggesting opportunities for future research to address these constraints and enhance FAPS operational efficiency.

In conclusion, this study provides valuable insights into the dispatching rules used in fully automated parking systems. The combination of the NAS allocation rule and FCFS sequencing rule exhibits superior performance in terms of customer waiting times and system utilization. The research emphasizes the critical role of allocation decisions in determining operational efficiency, urging future research to focus on optimization in this area. By optimizing allocation strategies, FAPSs can achieve significant improvements in their overall performance, ultimately enhancing customer satisfaction and system effectiveness. With this motivation, a novel allocation procedure is planned to be developed in future studies. The proposed approach could be performed on the same case, and the results obtained from the case can be discussed in detail.