Smart Insertion Strategies for Sustainable Operation of Shared Autonomous Vehicles

Abstract

As shared autonomous vehicles (SAV) emerge as an economical and feasible mode of transportation in modern cities, effective optimization models are essential to simulate their service. Traditional optimization approaches, based on first-come-first-served principles, often result in sub-optimal outcomes and, more notably, can impact public transport (PT) operations by creating unnecessary competition. This study introduces four insertion strategies within the MATSim model of the Melbourne Metropolitan Area, addressing these challenges. Two strategies optimize SAV operations by considering overall network costs, and the other two make insertion decisions based on the available PT service in the network. The findings show that strategic insertions of the requests can significantly enhance SAV service quality by improving the vehicle load and decreasing vehicle and empty kilometers traveled per ride. The analysis indicates that these strategies are particularly effective for smaller fleet sizes, leading to an increased number of served rides and a more equitable distribution of wait times across the network, reflected in an improved Gini Index. The findings suggest that prioritization-based insertions significantly enhance service quality by prioritizing users with limited access to PT, ensuring that those with fewer PT options are served first, and encouraging a more integrated and sustainable urban transportation system.

1. Introduction

The last decade has witnessed a shift in urban transportation, primarily due to the rise and expansion of Transportation Network Companies (TNCs), commonly known as ride-hailing services (RHS), such as Uber, Lyft, and DiDi. These platforms have revolutionized mobility by leveraging advanced digital technology to connect passengers with drivers seamlessly via user-friendly mobile applications. This modern approach offers flexibility and efficiency that traditional taxis struggle to match. The attraction towards TNCs lies in their ability to provide on-demand, direct door-to-door mobility without the obligation of owning a private vehicle. The convenience, dynamic pricing strategies, and door-to-door service have accelerated adoption in cities worldwide [1].

Despite their contributions in addressing some transport inefficiencies, the rise of TNCs has also brought forth new challenges, paving the way for the emergence of shared autonomous vehicles (SAVs) as a potential solution. SAVs, a synthesis of TNCs and autonomous vehicles (AVs), promise to improve urban congestion, reduce vehicular emissions, and democratize transportation access [2]. Unlike human-operated vehicles (HOV), SAVs do not require a human driver, which significantly reduces operational costs and enables continuous operation without driver fatigue [3,4]. Therefore, SAVs are anticipated to boost mobility by cutting driver costs and overcoming human drivers’ limitations, offering cost-effective, convenient, and superior-quality transportation for various trip purposes [5]. This paper focuses on the real-time operation of SAVs. The main operational-level benefit of choosing these vehicles in this study is their ability to receive and execute operations (routes, schedules, and ride assignments) coming from the dispatcher (i.e., a central computing system, in this case) safely and near-instantaneously [6]. This characteristic allows SAVs to be more flexible in responding to demand and optimizing routes in real-time, leading to more efficient and effective transportation services [7]. This capability allows SAVs to provide more responsive and efficient services than HOVs, which are limited by human decision-making and the need for rest periods [8]. From the fleet management perspective, the most significant advantage of SAVs is their ability to consistently adhere to real-time schedule modifications and the overall operational policies set by the dispatcher. While it is possible to instruct TNC drivers to follow fleet management policies and real-time directives, their inherent authority often makes it challenging to ensure strict adherence, leading to inconsistent compliance and potentially undermining fleet operations [1]. In contrast, SAVs operate under the complete control of the fleet operator, allowing for the maximization of fleet efficiency. The fleet operator benefits from near-perfect information regarding the location and status of SAVs and user requests, along with the capability to instantaneously adjust SAV routes, schedules, and traveler assignments in real-time as new requests are received [9]. This level of control and real-time responsiveness ensures that SAVs can be managed more effectively than HOVs, leading to optimized operational performance [7]. Therefore, the strategies developed in this study utilize SAVs because the proposed prioritizations can be effectively directed towards them and reliably followed, which is essential for realizing the benefits of the proposed insertion strategies.

Despite these advantages, the growing popularity of SAVs raises concerns for public transport (PT) systems. There is a risk of unnecessary competition with PT if these services are not adequately regulated, which could counteract the benefits of PT in mitigating road congestion and offering mobility solutions for underserved populations [10]. This direct and unnecessary competition with PT services reduces PT ridership and inefficiencies in urban mobility. This competition occurs when SAVs and PT services cater to the same passengers, particularly in areas well-served by PT, undermining the role of PT in reducing congestion and providing equitable access to mobility solutions [11,12,13]. PT, capable of carrying several passengers, is often regarded as an effective mode of improving road congestion by decreasing the total vehicle kilometers traveled (VKT) [14] and is a vital link for mobility-impaired groups, filling crucial gaps in urban mobility [15]. To address these issues related to competition, numerous studies have explored the complementary relationship between SAVs and PT, where SAVs can substitute PT in low-service areas and increase the reach and flexibility of PT. SAVs and PT can complement each other by providing integrated mobility solutions. For example, SAVs can serve as first/last-mile (FMLM) connectors, enhancing the accessibility and attractiveness of PT services [16,17]. This study focuses on strategies that leverage the complementary nature of SAVs and PT to create a more efficient and sustainable urban transportation network. This synergy highlights the benefits of integrated mobility solutions and supports the concept of SAVs complementing PT services.

A study of Uber trip data in six United States and European cities found that Uber often provided shorter travel times than PT, with 13–36% of Uber trips being at least twice as fast and 0–7% of trips having no viable PT alternative within a reasonable walking distance [12]. The evidence suggests that, in many instances, PT does not represent the most effective mode of reaching the destinations quickly. Additionally, the inadequacies in FMLM connectivity are frequently insufficient to depend solely on PT for complete journeys. In this context, SAVs present a promising solution by serving areas with low PT accessibility, potentially bridging the gap between traditional PT and TNCs. Considering the discussed context, the integration of PT and SAVs should aim for two key objectives: firstly, to support PT service in low-demand areas where traditional mass transit is economically inefficient, and secondly, to function as an FMLM solution, thereby enhancing the accessibility to mass PT stations and hubs. Thus, the strategic dispatch and assignment of SAVs are crucial in achieving this integration, ensuring they complement rather than compete with PT.

While most SAVs are expected to be operated by private companies, the public sector may also run these services in the future, as they are already being implemented and are under trial in a few European cities [18,19]. When the public sector operates SAVs, their goals extend beyond mere operational costs to include broader sustainability and equity objectives [20]. Public operators aim to prioritize service quality for users with limited access to PT to address urban mobility challenges, reduce transportation-related inequalities, and support sustainable transportation goals [21]. This paper moves one step in this direction to ensure that transportation services are accessible and equitable for all users, aligning with public policy objectives that promote sustainable and inclusive urban mobility.

The assignment problem of SAVs comes under the dial-a-ride problem (DARP), a variant of vehicle routing problem (VRP) that finds optimal routes for vehicles transporting more than one rider in a vehicle [20]. While multiple traditional algorithms have been explored for SAV contexts [22], they often lack the agility for real-time, dynamic environments. The demand for algorithms that concurrently process multiple ride requests, ensuring minimal detour times and dynamic route adaptability, is evident in the literature [23]. Multiple insertion heuristics for DARPs and their extensions have been developed in the literature [24]. In response to this need, the evolution from basic to more sophisticated insertion heuristics represents a key development area in SAV dispatching.

This study diverges from the conventional approaches mainly based on sequential insertion in the literature and introduces strategic insertion methods and prioritization to advance the efficiency of SAV, particularly in integration with PT services and improving PT accessibility. This study focuses on innovative insertion strategies to optimize SAV operations while supporting PT services. Integrating PT-based strategies, such as PT-based regret insertion, which shows the potential time-saving benefit experienced by users choosing an SAV over traditional PT alternatives, into these algorithms is a novel concept introduced in this paper, with promising results. Such benefits are particularly significant for SAVs due to their autonomous nature and ability to process and act on complex data in real-time, which is the focus of this study.

The remainder of the paper is as follows. Section 2 presents a comprehensive literature review of the related studies. Section 3 explains the proposed model, followed by Section 4, which presents the proposed insertion methods with their pseudocodes and toy examples. Section 5 provides the experimental setup and case study analysis, followed by the developed demand scenario and its properties. Section 6 contains the results and findings of this study. Section 7 presents a discussion on the implications of the research, followed by a detailed conclusion in Section 8, which ends with an outlook on implications and future research.

2. Literature Review

This section provides the background on assignment strategies for SAVs and demand-responsive transport (DRT). The problem of the SAVs assignment is regarded as a variant of the DARP, which aims to determine the vehicle routes for users with specific origins and destinations [25]. DARP has different variants and applications in the literature, such as freight transportation [26], elderly or disabled personnel transport [27], hospitals [28], and schools [29]. The SAV assignment problem, while like traditional DARP, presents unique challenges: SAVs often start from random locations rather than a fixed depot and must accommodate dynamic data and time-sensitive constraints. The SAVs assignment problem is stochastic and dynamic as the quality data and evolution of data are uncertain in these problems [24,30].

Recent information and communication technology advancements have shifted focus within academic literature from offline, predetermined request scenarios to dynamic, real-time decision-making processes. This shift is crucial in addressing the unpredictable nature of SAV assignments, where the arrival of requests is not static but dynamic. As a result, SAV assignment strategies must now account for short-term decision-making, often leading to locally optimal solutions rather than globally. In this context, a significant body of research has addressed the vehicle dispatching problem with dynamic requests in the past decade [1,24].

In this context, the most common strategy in assignment studies involves simplistic first-come, first-served (FCFS) rules, often prioritizing nearest requests in assigning vehicles [6,31,32,33]. For instance, Zhang et al. [23] considered only idle vehicles in their FCFS assignment. Maciejewski et al. [31] implemented a matching strategy where idle taxis were dispatched to immediate requests. The study assigned the vehicles based on two different categories: under-supply and over-supply. In the case of an under-supply, the vehicle is assigned to the nearest request; on the other hand, in the case of an over-supply, the request is matched with the closest idle vehicle. Beyond using the nearest idle vehicles, other studies have explored dividing service regions into sub-regions for efficient assignment [34,35] and considering both idle and enroute vehicles in the assignment process [6,32]. Maciejewski and Nagel [32] presented three different dispatching strategies for taxi-dispatching problems in MATSim with immediate requests. Where the first strategy assigned travelers on an FCFS basis to the nearest idle taxi, the second and third strategies considered both idle and enroute vehicles for the matching. Hyland and Mahmassani [6] proposed six different dispatching strategies; two were FCFS-based, and the other four were optimization-based. The study concludes that if all the assigned and unassigned travelers are considered with all idle and enroute vehicles for optimization, the vehicle miles can be reduced significantly. Although to overcome the issues of matching with the nearest vehicles, multiple studies have focused on matching the idle vehicles and riders based on the shortest network path [36,37]. Several studies have adopted strategies that prioritize specific requests based on the urgency of the service needed and the availability of alternative transportation options [38,39,40]. Building on these insights, this study diverges from the traditional FCFS approach, instead emphasizing a prioritization-based approach to serve requests more strategically.

Following the earlier prioritization focus, we delve into the various heuristic approaches explored in recent years for the DARP and its applications in SAV dispatching. Notably, simple construction and insertion heuristics have been proposed for their fast and feasible solutions [41,42,43]. However, many of these algorithms address the dispatching challenges of SAVs sequentially, considering one vehicle or request at a time [44]. For instance, Billhardt et al. [45] proposed a heuristic algorithm for taxi assignment, allowing the reassignment of vehicles for improved global solutions. Bischoff et al. [46] implemented a sequential insertion heuristic in MATSim, where the requests are inserted in the vehicles’ routes on an FCFS basis and are served. Multiple studies have investigated hybrid algorithms combining various metaheuristics to optimize solutions [24,47,48]. Focusing on insertion heuristics, sequential insertion is widely recognized for its efficiency in feasible solution generation [41,42,46,49]. However, there is an emerging interest in more complex approaches, like parallel insertion, offering robust solutions [50,51,52], and regret insertion [53], which prioritizes requests based on the potential regret of not serving them promptly. Despite their potential, parallel and regret insertions have been relatively underexplored, presenting an opportunity for further investigation and application in SAV dispatching.

Numerous studies have explored the complementary relationship between SAVs and PT, highlighting how SAVs can enhance PT in low-service areas by providing FMLM access and improving overall reach and flexibility [12,54,55]. This integration has been shown to boost PT ridership, reduce car ownership, and enhance service quality in both low-demand and urban areas [16,56]. Studies have demonstrated the potential of integrating SAVs with PT to create a more inclusive and efficient urban transportation network [8,57]. To evaluate and assess this complementary nature, recent studies have focused on the design of peer-to-peer ride-matching systems for integrated PT services, highlighting innovative approaches to enhance urban mobility. These studies solve the problem of real-time matching by maximizing the number of served riders in the system while minimizing the number of transfers for riders [58,59]. Furthermore, Ma et al. [60] proposed integrated dynamic dispatch and idle vehicle relocation algorithms to provide door-to-door multimodal service in the presence of a PT network. Grahn et al. [61] considered real-world data and network dynamics to simulate multiple operational strategies for an on-demand FMLM service. Like the studies in the literature, this study uses a multimodal network, where a PT network is mapped on the road network, to design a ride-matching strategy for SAV. Despite these advancements, a notable gap remains in the literature: none of these studies have explicitly focused on utilizing PT services as a decision-making criterion for prioritizing requests in SAV systems.

This study uses the Gini index [62] to evaluate the equitable service provided by these strategies, a widely recognized measure of inequality used across various fields to assess the distribution of resources and services. The Gini index is used to evaluate inequalities across multiple fields such as energy [63], water supply [64], urban park accessibility [65], medical field [66,67], and transport [68,69,70]. In the transport industry, multiple studies have focused on assessing different inequality measures in the context of SAVs and DRT [38,71,72,73] and have proven to be an effective tool for assessing service equity. These applications demonstrate the Gini index’s capability to ensure equitable service distribution, making it a valuable metric for evaluating the equity of SAV services, as used in this paper.

In conclusion, this literature review highlights a critical need for advanced SAV assignment strategies that more effectively integrate with PT systems. Moving away from the traditional reliance on FCFS and sequential insertion methods, our study explores the potential of alternative, non-sequential insertion strategies that can improve global solutions. We specifically focus on parallel and regret-based insertions, offering a novel framework that prioritizes requests based on existing PT services and targets areas with limited PT access. This innovative approach aims to boost overall system efficiency and ensure a fairer distribution of services, especially in underserved areas. By implementing these strategies, our research aims to contribute a more cohesive and adaptive solution to urban transportation challenges.

3. Model

This section describes the proposed model and the strategies developed in this study. The studied problem is a dynamic and stochastic DARP, addressed using real-time request-vehicle matching within the MATSim simulator framework.

Table 1. Notations used in this paper.

Symbol	Description
$V$	Set of all the vehicles in the network
$R$	Set of all the requests in the network
$T$	Time of request coming to the dispatcher
$o_i$	Origin of request $i$
$d_i$	Destination of request $i$
$T_i$	Time of the request $i$ coming to the dispatcher
$w_i\left(t\right)$	Real-time wait time of request $i$
$\delta$	Assignment interval
$R_{\tau }$	Set of all requests accumulated in the assignment period of $\tau$
$V_t\left(s\right)$	The state $s$ of a request at time $t$
$w_i$	Final wait time of request $i$
$t_i$	Final in-vehicle travel time of request $i$
$x_{ij}$	Request-vehicle pair after the request insertion
$C_{ij}$	Cost of serving request $i$ with vehicle $j$
$C[R_{\tau }\ast V]$	Cost matrix with dimension $R_{\tau }\ast V$
$C_{best}\left(r_i\right)$	Best cost value for request $r_i$
$C_{second}\left(r_i\right)$	Second best cost value for request $r_i$
$Reg\left(r_i\right)$	Regret cost of request $r_i$
$R\left[R_{\tau }\right]$	Regret matrix for all the requests
$T_{PT}\left(r_i\right)$	Travel time by PT for request $r_i$
$T_{SAV}\left(r_i\right)$	Maximum allowable travel time by SAV for request $r_i$
$A\left(r_a\right)$	The accessibility score of the trip $a$.
$d_a$	Euclidean distance between the origin and destination of the trip $a$.
$S_i$	Weighted average accessibility score for zone $i$

contains the notations used in this study.

3.1. Problem Statement

Consider an SAV fleet $V=\{\mathrm{1,2},3,\dots |V\left|\right\}$ where each vehicle can accommodate up to 4 passengers. The system aims to serve a series of user requests, $R=\{\mathrm{1,2},3,\dots |R\left|\right\}$, arriving dynamically and unpredictably over a simulation period in MATSim $T=[0,t_{max}]$. The requests arrive randomly from the demand of the study and are not known to the service provider in advance. Each request has its unique origin ($o_i$) and destination ($d_i$), which can be located anywhere in the entire network. Each request has detailed information on their earliest pickup and latest drop-off times, which needs to be taken into consideration by the provider when finding a suitable vehicle for them, and they are generally different to the time the request appears, i.e., $T_i\in T$. Lund [74] introduced the Degree of Dynamism ($DoD$) metric, calculated as the ratio of dynamic demand requests ($n_d$) to the total number of requests ($n_{tot}$), where dynamic requests occur during service operation rather than before the day starts. In this study, all the requests processed are dynamic; therefore, $DoD=1$.

At time ${t>T}_i$, the request $i\in R$ has a maximum wait time ($w$) and real-time wait time $w_i\left(t\right)={t-T}_i$. At the time ${t>T}_i$, each request $i\in R$ can be in any of the four stages ${\alpha }_i\left(t\right)\in \{\mathrm{1,2},\mathrm{3,4}\}$ denoting unassigned, assigned, in-vehicle, and served, respectively. These four states correspond to the four mutually exclusive subsets of the users. Similarly, at the time ${t>r}_i$, each vehicle $j\in V$ can be in any of the three states: ${\beta }_j\left(t\right)\in \{\mathrm{1,2},3\}$ denoting idle, on-route with passengers less than capacity, and on-route with passengers equal to the capacity, respectively.

As discussed earlier, most optimization problems in the literature are sequential insertion, and the requests are considered as they come on an FCFS basis. This study uses different prioritization strategies to identify and serve the priority queues based on that. All incoming requests are collected within a fixed assignment interval, $\delta$. Let us consider $R_{\tau }$ as the set of all requests accumulated in the assignment period of $\tau$, with the formulation $R_{\tau }=\{r_1,r_2,\dots , r_n\}$, where $r_i$ represents the $i^{th}$ request, and $n$ represents the aggregated request count within the designated assignment interval. The Bellman Equation represents the method for solving the dynamic nature of a problem, as shown in Equation (1), where $V_t\left(s\right)$ represents the state $s$ of a request at time $t$ to solve a sequential optimization problem [75].

$$V_t\left(S_t\right)={ }_{\hspace{1em}a}^{Min}\{C\left(S_t,a\right)+\sum _{s^{\prime }\in S}P\left(S_t=s^{\prime }|S_t,a\right)V_{t+1}(s^{\prime })\}$$

(1)

As the service provider does not have any prior information regarding the spatial-temporal distribution and the exogenous information $P\left(S_t=s^{\prime }|S_t,a\right)$ is unknown. Hence, this study compares four different insertion strategies that differ in giving priorities to different request types and matches them based on that by minimizing the cost function $\mathrm{m}\mathrm{i}\mathrm{n}\left\{C\left(S_t,a\right)\right\}$ at the end of each assignment interval.

As mentioned earlier, the SAV assignment problem is solved after each assignment interval, where each request is assessed using different strategies, and then the matches are found for them.

3.2. Problem Formulation

This section presents the mathematical formulation of the optimization problem ${min}_a\left\{C\left(S_t,a\right)\right\}$, referred to as the SAV assignment problem. Let $w_i$ be the wait time and the in-vehicle travel time $t_i$ for each request-vehicle pair $x_{ij}$. The wait time is the time between requesting a vehicle and a vehicle picking up the passenger, and in-vehicle travel time is the time spent in the vehicle, i.e., between the pickup and drop-off of the request. The mathematical formulation of the SAV assignment problem is given as follows in Equations (2) to (6).

$$\min {\sum }_{i=1}^n(w_i\left(x_{ij}\right)+t_i\left(x_{ij}\right))$$

(2)

Subject to:

$${\sum }_{j=1}^m{x}_{ij} = 1\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\forall i\in R$$

(3)

$${\sum }_{i=1}^n{q}_i\ast x_{ij}\le Q_j\hspace{1em}\hspace{1em}\forall i\in V$$

(4)

$$w_i\left(x_{ij}\right)\ge 0\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\forall i\in R$$

(5)

$$t_i\left(x_{ij}\right)\ge 0\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\forall i\in R$$

(6)

The objective Function (2) minimizes the total travel time, estimated using two different values, i.e., wait time and in-vehicle travel time. Both times are inherently functions of the assignment decisions $x_{ij}$, i.e., the time a request waits and the subsequent in-vehicle travel time it experiences are directly influenced by which vehicle is chosen to serve the request. Constraint (3) ensures that only one vehicle is assigned to each request. Constraint (4) ensures that vehicles have a maximum capacity that is not violated. In Equation (4), $q_i$ is the demand of request $r_i$, and $Q_j$ is the capacity of the vehicle $v_j$. Constraints (5) and (6) ensure that wait and in-vehicle travel times must be non-negative.

4. Proposed Insertion Strategies

This section provides a comprehensive overview of the four proposed insertion strategies. Each strategy is explained through a toy example, a simplified, hypothetical scenario, offering a graphical representation of the strategies’ functionality.

4.1. Strategy 1: Parallel Insertion (PI)

The first strategy is PI, which simultaneously processes all incoming ride requests within the assignment interval. This strategy deploys an advanced algorithmic approach, wherein each request is concurrently inserted in the schedules of vehicles and evaluated for potential assignment to every vehicle within the network. This simultaneous analysis calculates the associated costs for each request-vehicle pairing, offering a comprehensive, global perspective on cost optimization. The algorithm forms a cost queue, a dynamic and priority-based data structure where requests are sorted based on cost-effectiveness, allowing it to prioritize requests that optimize the overall efficiency. The schedules of the vehicles are updated after each assignment to reflect real-time changes and constraints, responding to evolving network conditions.

4.1.1. Formulation

For each request $r_i\in R_{\tau }$, the request is inserted in the schedule of each vehicle $v_j\in V$, where $V$ is the set of all the vehicles in the network and a corresponding cost $C_{ij}=f(r_i,v_j)$ is estimated, where $f$ is a function to compute the cost of assigning the request $r_i$ to vehicle $v_j$. The pair with the least cost is defined as ${(r}^{\ast },v^{\ast })=\arg {min}_{ij}{ C}_{ij}$. The requests are sorted and queued based on their costs, and sequentially, the least-cost vehicle is matched with it, and the schedules are updated. Algorithm 1 contains the pseudocode for the assignment of the requests. Algorithm 2 contains the pseudocode for the PI algorithm.

Algorithm 1: Pseudocode for the assignments
1	FinalizeAssignments $({\mathit{R}}_{\mathit{\tau }},\mathit{V})$
2	for  $r\in R$  do
3	Assign  $r$ to the minimum cost vehicle  $v\in V$
4	Update the schedules
5	end for
6	Return assignments and updated schedules to the simulator

Algorithm 2: Pseudocode for the parallel insertion
1	ParallelInsertion (${\mathit{R}}_{\mathit{\tau }},\mathit{V}$)
2	If assignment Interval is here, do
3	Initialize  $C[R_{\tau }\ast V]$
4	for  $r_i\in R_{\tau }$  do
5	for $v_j\in V$ do
6	$C_{ij}$$=f(r_i,v_j)$
7	end for
8	end for
9	Sort  $R_{\tau }$ by  $C[R_{\tau }\ast V]$
10	FinalizeAssignments $({\mathit{R}}_{\mathit{\tau }},\mathit{V})$
11	end if

4.1.2. Toy Example of the Algorithm

Table 2. Cost matrix for toy examples of strategies 1 and 2.

Request	Cost
	Vehicle 1	Vehicle 2	Vehicle 3	Vehicle 4	Regret
Request 1	63	55	41	56	14
Request 2	35	37	25	48	10
Request 3	68	34	53	47	13

provides a hypothetical cost matrix indicating various costs for selecting different vehicles, referenced in the toy examples. The table’s final column lists the regret cost for each request.

Figure 1 presents the PI strategy in action. At time ${\tau }_i$, there are four SAVs, each on a predetermined route, labeled from 1 to 4, and three ride requests labeled 1, 2, and 3. Dashed lines represent potential assignments between SAVs and requests, with associated costs in minutes next to each connection.

Before the start of ${\tau }_i+\delta$, the assignments are made. Following creating the least-cost matrix, Request 1 is assigned to vehicle 4, the pairing with the lowest cost, and the vehicle schedules are updated. Requests 2 and 3 are assigned to the remaining SAVs based on the updated schedules. The figure illustrates the decision-making process, focusing on optimizing global costs without considering potential future requests.

4.2. Strategy 2: Regret-Based Insertion (RI)

The RI strategy extends PI, introducing a regret metric to optimize ride-matching decisions. The regret value for each request is calculated as the difference between its cost elements, prioritizing the request with the highest regret for insertion. In this strategy, each incoming ride request is evaluated for its optimal pairing with a vehicle and its next-best pairing option, and the regret value is calculated as the difference between these two pairings. This method minimizes potential inefficiencies caused by not selecting the optimal pairing for each request. This approach limits myopic behavior, which is common in classical insertion procedures and is especially important in mixed scheduling and routing problems with additional constraints.

4.2.1. Formulation

For each request $r_i\in R_{\tau }$, the request is inserted in each vehicle $v_j\in V$, where $V$ is the set of all the vehicles in the network. Let $C_{ij}$ be the cost of assigning the request $r_i$ to vehicle $v_j$. First, the cost of pairing each request $r_i$ to vehicle $v_j$ is estimated, which involves evaluating all possible combinations of their respective costs.

$$C_{ij}=f(r_i,v_j)$$

(7)

For each request, the best and second-best cost values are identified.

$$C_{best}\left(r_i\right)={min}_{v_j\in V}{C}_{ij}$$

(8)

$$C_{second}\left(r_i\right)={min}_{\begin{array}{c}{v}_j\in V\\ C_{ij}\ne C_{best}\left(r_i\right)\end{array}}{C}_{ij}$$

(9)

The regret value $Reg\left(r_i\right)$ for $r_i\in R_{\tau }$ can be formulated as follows:

$$Reg\left(r_i\right){=C_{second}\left(r_i\right)-C}_{best}\left(r_i\right)$$

(10)

The objective of this strategy is to prioritize requests with the highest regret values, as it indicates a significant drop in efficiency if the best pairing is not chosen. This method ensures that the most critical requests, in terms of efficiency loss, are served first, optimizing the overall network performance. Algorithm 3 shows the pseudocode of the RI implemented in this study.

Algorithm 3: Pseudocode for the regret-based insertion
1	RegretBasedInsertion (${\mathit{R}}_{\mathit{\tau }},\mathit{V}$)
2	If assignment Interval is here, do
3	Initialize  $C\left[R_{\tau }\ast V\right]$ and  $R\left[R_{\tau }\right]$
4	for  $r_i\in R_{\tau }$  do
5	for $v_j\in V$ do
6	$C_{ij}$$=f(r_i,v_j)$
7	end for
8	$C_{best}\left(r_i\right)={min}_{v_j\in V}{C}_{ij}$
9	$C_{second}\left(r_i\right)={min}_{\begin{array}{c}{v}_j\in V\\ C_{ij}\ne C_{best}\left(r_i\right)\end{array}}{C}_{ij}$
10	$Reg\left(r_i\right){=C_{second}\left(r_i\right)-C}_{best}\left(r_i\right)$
11	$R\left[R_{\tau }\right]\leftarrow Reg\left(r_i\right)$
12	end for
13	Sort  $R_{\tau }$ by  $C[R_{\tau }\ast V]$
14	FinalizeAssignments $({\mathit{R}}_{\mathit{\tau }},\mathit{V})$
15	end if

4.2.2. Toy Example of the Algorithm

Figure 2 shows the toy example of the RI strategy. Initially, at the time ${\tau }_i$, four SAVs are shown, each potentially available for pairing with any of the three incoming requests, with dashed lines connecting each SAV to each request, representing all possible assignments. Alongside each dashed line is a numerical value representing the assignment cost in minutes for that SAV-request pair.

On the right side of the diagram, before the start of ${\tau }_i+\delta$, for each request, the two least-cost SAV options are identified, and the regret value for not choosing the optimal SAV is calculated, as shown in Table 2. This leads to the formation of a priority queue, which, in this example, is ordered as requests 1, 3, and 2, and the requests are matched with the most suitable and least cost SAV, as shown in the right diagram.

4.3. Strategy 3: PT-Based Regret Insertion (PTRI)

The PTRI strategy optimizes real-time ride-matching for SAVs by incorporating a PT-based novel regret cost. This new regret cost metric quantifies the potential time-saving benefit experienced by users choosing an SAV over traditional PT alternatives. This approach aims to enhance decision-making by prioritizing ride requests that maximize the efficiency and attractiveness of using SAVs compared to PT.

4.3.1. Formulation

For each ride request $r_i\in R_{\tau }$, the maximum allowable travel time by SAV is $T_{sav}\left(r_i\right)$ and by PT is $T_{pt}\left(r_i\right)$, estimated using the router developed by Rieser et al. [76]. Assume that the regret cost of assigning the request to an SAV instead of taking PT is $Reg\left(r_i\right)$. The maximum allowable travel time by SAV for $r_i\in R_{\tau }$, which is the time without violating the time constraints, is calculated as follows:

$$T_{SAV}\left(r_i\right)=\mathsf{\alpha }\ast T_{direct,SAV}\left(r_i\right)+\beta$$

(11)

where $T_{direct,SAV}\left(r_i\right)$ is the travel time for the request $r_i$, using an unshared SAV, i.e., the real-time travel time between the origin and destination of the request. Let $\alpha$ and $\beta$ be the predefined parameters for accessibility evaluation, estimated from the $\alpha$ and $\beta$ values in MATSim [77]. Given these, the regret cost can be defined as $Reg\left(r_i\right)=T_{pt}\left(r_i\right)-T_{sav}\left(r_i\right)$. The goal of this strategy is to minimize the total regret across all ride requests, which the following objective function can represent:

$$min{\sum }_{r_i\in R_{\tau }}Reg\left(r_i\right)$$

(12)

Subject to:

$${\sum }_{v_j\in V}{x}_{ij}=1\hspace{1em}\hspace{1em}\forall i\in R$$

(13)

Here, the strategy looks for the configuration of ride assignments to SAVs that generates the lowest total regret, considering the best PT alternative for each ride request. Algorithm 4 represents the pseudocode for the PT-based regret insertion strategy.

Algorithm 4: Pseudocode for the PT-based regret insertion
1	PTBasedRegretInsertion $({\mathit{R}}_{\mathit{\tau }},\mathit{V}$)
2	If assignment Interval is here, do
3	Initialize  $R\left[R_{\tau }\right]$
4	for  $r_i\in R_{\tau }$ do
5	$T_{PT}$$\left(r_i\right)$ and  $T_{SAV}$$\left(r_i\right)$
6	$Reg\left(r_i\right)=T_{PT}\left(r_i\right)-T_{SAV}\left(r_i\right)$.
7	$R\left[R_{\tau }\right]\leftarrow Reg\left(r_i\right)$
8	end for
9	Sort  $R_{\tau }$ by  $C[R_{\tau }\ast V]$
10	FinalizeAssignments $({\mathit{R}}_{\mathit{\tau }},\mathit{V})$
11	end if

4.3.2. Toy Example of the Algorithm

Figure 3 visualizes the toy example of the PTRI strategy for ride-matching within an SAV fleet across two different time instances. In the initial state at the time ${\tau }_i$, there are four SAVs and three ride requests. Each request has two values: the best PT route’s travel time (green value) and the maximum allowable SAV travel time (red value). The regret costs, representing the time-saving potential of SAVs over PT, are calculated for each request. In Figure 3, the regret cost for request 1 would be 16 min, 7 min for request 2, and 18 min for request 3. At ${\tau }_i+\delta$, after the regret costs are calculated, the requests are prioritized based on their regret values. Request 3 has the highest regret value (18 min), so it is served first, followed by requests 1 and 2, respectively.

By calculating a regret metric based on the difference between PT and SAV travel times, the strategy strategically assigns SAVs to serve requests where they can offer a more time-efficient alternative to PT. This enhances the decision-making process and promotes using SAVs by emphasizing their time-saving advantage.

4.4. Strategy 4: Accessibility-Based Insertion (AI)

The AI strategy aims to optimize ride-matching in SAVs, emphasizing the accessibility of different urban zones developed by Tiwari et al. [78]. This strategy is designed to prioritize requests from areas with lower accessibility to PT, promoting equitable distribution of SAV services. For each trip request, an accessibility score is calculated to reflect the ease of accessing PT services within that zone. The score is computed using the formula:

$$A\left(r_i\right)=T_{alt}/T_{SAV\_max}$$

(14)

where $T_{alt}=\min \left\{T_{pt},T_{walk}\right\}$, $T_{SAV\_max}=\mathsf{\alpha }\ast T_{direct,SAV}+\beta$.

After estimating the accessibility score for each trip, the zone of origin for that trip is calculated. Then, the average zonal accessibility score for each zone is calculated using the following Equation:

$$S_i=\frac{{\sum }_{a\in i}A\left(r_a\right) \ast d_a}{{\sum }_{a\in i}{d}_a}$$

(15)

Equation (15) was formulated to estimate a consolidated accessibility score for zones by weighing individual accessibility scores, where $S_i$ is the weighted average accessibility score for zone $i$. The summation ${\sum }_{a\in i}A\left(r_a\right)\ast d_a$ indicates the sum of all the accessibility scores, taken over all trips originating from zone $i$. $A\left(r_a\right)$ represents the accessibility score of the trip $a$. $d_a$ is the Euclidean distance between the origin and destination of the trip $a$. Given the diverse range of trip lengths, a simple mean accessibility score may not adequately represent a zone’s overall accessibility. Hence, the distance between trip origins and destinations is employed as a weight to refine the final accessibility estimation for each zone.

The higher the value of $S_i$, the less accessible the zone is considered. The strategy initially focuses on serving requests from zones with the highest accessibility scores, moving towards those with lower scores. For multiple requests within the same zone, individual trip accessibility scores, $A\left(r_i\right)$, are used for prioritization. This approach ensures a more equitable distribution of SAV services, particularly in areas where access to PT is challenging.

4.4.1. Formulation

For each ride request $r_i\in R_{\tau }$, the maximum allowable travel time by SAV is $T_{SAV\_max}$ and by PT is $T_{alt}$. The accessibility score ${A(r}_i)$ for a request $r_i\in R_{\tau }$ is calculated based on the comparison of PT and SAV travel times and estimated as shown in Equation (14). Algorithm 5 contains the pseudocode for this strategy.

Algorithm 5: Pseudocode for the regret-based insertion
1	AccessibilityBasedInsertion (${\mathit{R}}_{\mathit{\tau }},\mathit{V},\mathit{Z}$)
2	If assignment Interval is here, do
3	Initialize  $A\left[R_{\tau }\right]$ and  $\mathrm{S}\left[Z\right]$
4	for  $r_i\in R_{\tau }$ do
5	$T_{pt}\left(r_i\right)$ and  $T_{sav}\left(r_i\right)$
6	$A\left(r_i\right)=T_{PT}\left(r_i\right)/T_{SAV}\left(r_i\right)$
7	$A\left[R_{\tau }\right]\leftarrow A\left(r_i\right)$
8	end for
9	for $z\in Z$ do
10	$S_z=\frac{\sum s_a{d}_a}{\sum d_a}$
11	Sort  $Z$ by  $S_z$
12	FinalizeAssignments $({\mathit{R}}_{\mathit{\tau }},\mathit{V})$
13	end for
14	end if

4.4.2. Toy Example of the Algorithm

Figure 4 demonstrates the toy example of the AI strategy for matching ride requests to SAVs, focusing on the accessibility of different urban zones. At time ${\tau }_i$, the figure is divided into four zones, separated by blue lines, with each zone labeled $Z_i$ and associated with an accessibility score. These scores represent how easy it is to access PT within that zone, with higher scores denoting lower accessibility.

At time ${\tau }_i+\delta$, the requests have been assigned to SAVs based on the accessibility scores. The strategy prioritizes requests from less accessible zones to improve regional service equity. Request 3, from Zone 3, with the highest accessibility score, indicating the least accessible area, is prioritized first. Request 2, coming from Zone 1, has the second highest accessibility score (implying lower accessibility to PT services) matched. Request 1, originating from Zone 2, which has a relatively moderate accessibility score, is matched at the end of the queue.

5. Experimental Setup

This section presents the simulator and the case study used in this paper. Furthermore, the section discusses the properties of the SAV demand. The parameters used in the simulation to evaluate the proposed strategies are also discussed.

5.1. Multi-Agent Transport Simulation (MATSim)

This study utilizes MATSim, an advanced open-source agent-based travel demand and supply simulator developed in Java [79]. MATSim, notable for its elaborate behavioral models and ability to simulate large-scale scenarios efficiently, is particularly adept at handling complex transportation studies. Each traveler is represented as an agent with specific attributes like gender, age, income, or car availability. These agents operate based on a detailed daily plan, encompassing a chain of activities and the necessary travel between them. The movements within the road network are simulated through a queue-based network simulation, allowing emergent congestion and traffic dynamics to be modeled. After simulating an agent’s full day (24 h), a score is derived from their activity participation and travel. Participating in activities earns a positive score while traveling deducts a score. Agents can modify their plans for the next iteration based on probability. They can change their plan by changing the mode and route to enhance their score. MATSim’s co-evolutionary algorithm aims to optimize these scores to achieve user equilibrium.

MATSim’s simulation of on-demand transportation services utilizes an established module for dynamic vehicle routing challenges and another for SAV simulation [32,77]. These extensions are critical for modeling the dynamic aspects of on-demand mobility, simulating different scenarios, and evaluating emerging transportation services’ commercial viability and user acceptance. When agents opt for SAV, they make an SAV ride request. This request is allocated to an SAV vehicle that can accommodate it without compromising service standards for its existing or upcoming passengers.

5.2. Case Study

This study uses an existing synthetic MATSim model of Melbourne’s Metropolitan Network [80]. The network file of the study area and the config file were taken from the base scenario, and the config file was modified according to the requirements [81]. Figure 5 shows the network of the Melbourne Metropolitan Area used as the case study in this study. The population file was generated using the base model’s Victorian Integrated Survey of Travel and Activity (VISTA 2016) and census datasets. The population contains ten percent of the sample size of the entire population. Scaling down the population has been applied in most of the MATSim studies in the literature using the scaled population [82]. The factors for flow capacity and storage capacity of links were adjusted to align with the ratio of the population sample. For instance, a 10% sample requires the application of a 0.1 network correction factor. For the scoring function in MATSim, which determines the benefits of conducting an activity and the drawbacks of traveling, we utilized the mode choice model coefficients estimated by KPMG and Infrastructure Victoria for the MABM [83,84].

5.3. Demand Estimation and Properties of Demand

This paper did not enable the mode choice model of MATSim to provide a better quantitative analysis of the strategies. This approach reduces the simulation time as the mode choice convergence is not required here; therefore, a fixed SAV demand was created and used to evaluate the strategies. The SAV demand was created using the iterative process and factoring in the service range of the SAVs [85]. By the end of the 500th iteration, 39,180 requests were created, and that demand was used to evaluate the strategies. This means there will be 39,180 potential SAV users if the SAV service is introduced in the Melbourne Metropolitan Area. Figure 6a,b show SAV’s temporal and spatial demands throughout the day. Notably, two periods of peak demand are evident: one around 8 AM and the other near 4 PM, which is similar to the travel pattern in Melbourne by car, as evident in [86].

5.4. Simulation Settings

Different fleet sizes from 250 to 2000 were tested to evaluate the strategies, where each vehicle has a maximum capacity of 4 passengers. At the start of the simulations, vehicles were randomly distributed throughout the network. To assess the feasibility of SAVs, it is assumed every customer is open to sharing their rides. The request rejection constraints were kept constant for all strategies, i.e., if a vehicle is not allotted within 10 min, and if the detour time is not more than the maximum allowable travel time using $\alpha$ = 1.5 and $\beta$ = 900, the request gets rejected [77]. The assignment interval used in this paper was 120 s, i.e., the requests are accumulated and served every 120 s.

6. Results

This section discusses the results of the developed strategies and the outcomes compared to the base case (BC), which employs the conventional sequential insertion strategy. There are multiple ways to assess and evaluate the performance of the SAVs. This study assesses the overall performance of the proposed strategies from three main perspectives: service efficiency, service externalities, and service provision equity. The findings are presented relative to the BC scenario, demonstrating the improvements achieved by the proposed strategies, with detailed results for BC in

Table 3. The results of the BC scenario for different fleet sizes.

Fleet Size	Number of Served Rides	Total Travel Time (Min)	Empty Ratio (%)	Average VKT per Ride (Km)	Average EKT per Ride (Km)	Average Vehicle Load
250	17,695	27.86	5.580	12.115	0.6761	70.78
500	29,105	26.90	5.834	11.444	0.6677	58.21
750	33,782	26.41	5.429	11.130	0.6043	45.04
1000	36,822	26.06	5.145	10.924	0.5621	36.82
1250	38,435	25.63	4.763	10.705	0.5099	30.74
1500	38,659	25.40	4.392	10.624	0.4666	25.77
1750	38,992	25.03	3.868	10.500	0.4062	22.28
2000	39,062	24.81	3.636	10.439	0.3796	19.53

. The table shows that with the increased fleet size, the number of served rides increases, and the travel time, average VKT, and empty kilometers traveled (EKT) per ride decreases. Furthermore, the vehicle load decreases, showing a low fleet utilization rate.

6.1. Service Efficiency

The main KPIs for evaluating service efficiency included in this study are the % empty ratio (i.e., % of total EKT compared to total VKT), the number of total rides served, average travel time (i.e., the sum of average wait time and in-vehicle time) and the average vehicle load (i.e., the average number of passengers served by one SAV).

Figure 7 shows the difference between the number of served rides for each strategy and BC for different fleet sizes. As can be seen, the number of served rides is higher for all scenarios for smaller fleet sizes, with PI serving the highest number of requests. It is clear from the figure that as the fleet sizes increase, the difference becomes lesser, showing that with enough fleet sizes, the prioritization effects in all the scenarios are comparable to BC, and all the scenarios serve almost the same number of rides. AI serves fewer requests than BC, as the requests from less accessible zones from far away are prioritized.

Figure 8 shows the average travel time for all the scenarios compared to BC. The results show that the average travel time is improved for all the fleet sizes in the case of PI and RI, which shows that the objective function used in these two strategies was optimized. The improvements are significant in the case of smaller fleet sizes, and the improvements become very small compared to BC for larger fleet sizes. The average travel time in the case of PTRI and AI is a little higher than BC, showing the prioritization of rides far from the areas with higher demand and towards the less PT-accessible zones.

Figure 9 shows the difference in % Empty rides for all the scenarios at different fleet sizes. As the figure shows, PI and AI have higher empty ratios for smaller fleet sizes. Still, after a specific fleet size, all the scenarios have fewer empty rides for almost the same number of requests served, as shown in Figure 7. This shows the effectiveness of prioritizations, decreasing empty rides by serving ride requests. One of the exciting observations from Figure 7 and Figure 9 is that at fleet size 750, the results have a significant drop and inclination. This phenomenon is similar to the network breakdown effect when identifying the user equilibrium [87]. This observed inflation point is context- and location-specific and can differ from other case studies. The fleet size can vary based on location-specific factors such as population density, geographic layout, PT coverage, and household car ownership. Densely populated cities may require larger fleets to meet higher demand, while less densely populated areas might need smaller fleets [36,88]. Extensive PT networks can reduce fleet size by providing complementary services [89,90].

Figure 10 shows the average vehicle load for each SAV for different fleet sizes, which is the average number of passengers one vehicle serves. The higher number shows better efficiency of the system. The figure shows that all scenarios have better vehicle load efficiency for smaller fleet sizes and are comparable for larger fleet sizes compared to BC. PI has the best efficiency compared to other scenarios as it serves more requests for all fleet sizes, as seen in Figure 7. The average vehicle load merges towards the end, as all the scenarios serve almost a similar number of rides for larger fleet sizes. It is visible that the average vehicle load is better in all the proposed strategies compared to BC, showing better fleet utilization. The findings indicate a necessary trade-off between service quality and vehicle load. As the fleet size increases, there is only a marginal improvement in service quality, whereas vehicle utilization notably decreases, leading to significant resource wastage.

6.2. Service Externalities

SAV’s service externalities refer to the costs and benefits that impact those not utilizing the service directly, such as environmental consequences. This study uses average VKT per ride and average EKT per ride as indicators of environmental effects.

Figure 11 shows the average VKT per ride. As is visible in the figure, the VKT per ride is significantly lower for smaller fleet sizes and becomes constant towards the larger fleet sizes. The average VKT per ride for PI is the best among them, as the number of rides served is higher, and the global perspective helps us reduce the total VKT for the system. However, as seen in Figure 12, the average EKT per ride is higher in the case of PI, as the global perspective requires us to match rides that can improve the overall service quality, resulting in more significant empty travel. However, this effect is reduced when global solutions are concerned, as seen in Figure 9, where the empty rides are optimized for PT. For other scenarios, the average VKT per ride has reduced compared to BC, especially for smaller fleet sizes, except for AI, as the strategy focuses on prioritizing rides in less accessible zones, which requires higher empty and total travel.

Figure 12 contains the improvements in EKT per ride for all the scenarios at different fleet sizes compared to BC; the results are similar to the average VKT per ride. The results show improvement for larger fleet sizes; the values are higher than BC for smaller sizes.

6.3. Service Provision Equity

The equity dimension relates to how the service’s costs and benefits are allocated among various groups. This study uses the Gini index to evaluate the strategies using the zonal average wait times as the income variable because they are the most used indicators in the literature. The Gini coefficient measures income distribution, which gauges the extent to which a policy is progressive or regressive and is commonly used to evaluate inequality [62]. Despite being one of the commonly-known equality measures, the Gini coefficient of inequality is scarcely used in the literature in the cases of on-demand services [91]. For the distribution of income in a population of N individuals, if $i=\mathrm{1,2},\dots .,n$, $y_i$ is the income of individual $i$, $y_j$ is the income of individual j, and $\mu$ is the mean income, and the Gini coefficient, denoted by G, is written as follows:

$$G=\frac{1}{2N^2\mu }{\sum }_i{\sum }_j\left|y_i-y_j\right|$$

(16)

Figure 13 shows the Gini index values for all the scenarios for two different fleet sizes of 250 and 1500. A fleet size of 1500 is considered for visualization as it can be seen from Table 2 that the system achieves a service rate (i.e., % of rides served) of more than 98 percent for a fleet size of 1500. As is visible in the figure, the Gini index values are lower for a fleet size of 250, showing that as the service rate is very low, the average wait times are spread evenly in the network. The values for fleet sizes of 250 range from 0.1045 for AI to 0.1066 for RI, and for a fleet size of 1500, range from 0.15872 for AI to 0.1630 for RI. The results show that the lowest Gini index value was achieved by AI for both fleet sizes, showing improved equity in the network, which means the average wait times are evenly spread throughout the network for AI. Several requests from a higher number of zones are served in the case of fleet size 1500, which is the reason for wait time differences throughout the network and higher Gini index values. The Gini index values are highest for PI and RI, as they serve more requests and focus on improving quality for individuals.

Figure 14a–c contain the zonal average wait times in the network for BC, PTRI, and AI scenarios for a fleet size of 250 vehicles. The number of served rides is under 50 percent for all scenarios for the fleet size of 250, and the wait times are higher throughout the network. Figure 14a contains the zonal average wait times for the BC scenario. As is visible in Figure 14c, the wait times in the AI scenario are more evenly spread throughout the network compared to the other two scenarios for a fleet size of 250, which is evident from Figure 13, as AI produces the least Gini index.

Similarly, Figure 14d–f contain the average zonal wait times in the network for BC, PTRI, and AI scenarios for a fleet size of 1500 vehicles. The average zonal wait times are greener than those in Figure 14a–c for a fleet size of 250 vehicles, as the availability of more vehicles improves the service quality. Like Figure 14c, the average wait times for the AI scenario in Figure 14f are spread evenly throughout the network for a fleet size of 1500, as evident in Figure 13.

7. Discussion and Implications

The proposed optimization of SAV operations through strategic insertion strategies, PI, RI, PTRI, and AI enhance SAV service quality and integration with PT. These strategies optimize SAV operations and prioritize service in areas with limited PT accessibility, addressing critical gaps in the current urban mobility landscape. We discuss the possible implications of the research on different stakeholders, both theoretically and practically.

7.1. Theoretical Implications

Our findings contribute to the theoretical framework of urban mobility by demonstrating how algorithmic insertion strategies can optimize SAV dispatching, enhance the operational efficiency and service quality of SAVs, and improve the integration between SAVs and PT. This paper extends beyond the traditional objectives of DARPs, such as minimizing time and costs in SAV operations, by embracing a broader spectrum of objectives. The results show that researchers can envision and pursue more inclusive and diverse objectives in the SAV dispatching by enhancing the integration of SAVs with PT to address operational efficiencies and social and accessibility challenges in urban mobility systems. This research shows practical examples, and the comprehensive simulation model in the backend validates the promising and practical nature of the proposed novel strategies. The strategic prioritization of ride requests from areas with limited PT access highlights the need for integrated transportation planning, contributing to closing the FMLM connectivity gap and improving PT service access, thereby fostering a more cohesive approach to multimodal transportation integration.

Additionally, this study acknowledges the dual roles of private and public operators in managing SAVs in the future. Private operators typically focus on maximizing operational efficiency and profitability, while public sector operators prioritize broader sustainability and equity goals. Legacy et al. [92] suggest that public authorities will transition from owning transportation assets to managing SAV service providers to ensure equitable and sustainable transport, mitigating potential corporate conflicts of interest. This conclusion is supported by other research advocating regulatory controls to guide the sustainable growth of these services [9,93]. These changes will bring new stakeholders into the mobility market and necessitate new forms of cooperation and legal frameworks for liability and insurance [94]. Private and public operators can collaborate through public-private partnerships (PPPs), leveraging each other’s strengths to enhance urban mobility [95]. For instance, private operators can provide efficient and cost-effective services, while public operators ensure that these services align with public policy goals and address equity concerns. Collaboration can occur in various forms, such as joint service agreements, shared infrastructure, and coordinated policy frameworks [92]. This partnership can lead to more efficient use of resources and better service provision across the board. Public operators can aim to ensure service quality and equitable access, particularly for users with limited access to PT alongside private operators, which can provide adequate service to high-demand locations. This dual focus ensures that SAVs operate efficiently and contribute to the essential goals of reducing social inequities and promoting sustainable urban development. By understanding these diverse roles and objectives, the study highlights the need for a comprehensive approach to optimize SAV operations and effectively integrate them with PT systems.

In the context of the four proposed insertion strategies, public operators could take charge of PTRI and AI strategies, focusing on equity and accessibility. In contrast, private operators could control and use RI and PI strategies, optimizing the service quality for the users. This chain of responsibilities ensures that both sectors can leverage their strengths for a cohesive urban mobility solution.

7.2. Practical Implications

Integrating SAVs with PT offers an opportunity to improve urban mobility. For urban planners and policymakers, our study underscores the importance of adopting policies encouraging SAV-PT collaborations to enhance transportation efficiency, accessibility, and sustainability. By strategically dispatching SAVs following our proposed insertion strategies, cities can significantly reduce the environmental footprint of their transportation networks. Our study has implications for four critical stakeholders in urban mobility.

First, for users, especially those in low PT-access zones, the integration facilitated by AI and PTRI strategies indicates a shift toward more equitable urban mobility solutions. These approaches aim to reduce travel times, lower commuting costs, and ensure that mobility services cater to a diverse user base. AI can be used in suburban areas where PT access is limited, ensuring that SAVs provide necessary connectivity for users. Similarly, PTRI can optimize routes in busy areas by considering PT schedules, reducing overall travel time for users. It is worth noting that prioritization of the underserved regions with SAV-PT integration strategies may lead to longer wait times for SAV services for users in well-served PT zones due to the deliberate deprioritization of these areas.

Second, TNCs and the SAV service providers benefit from adopting PI and RI strategies, which focus on improving the overall travel time costs and serving more requests, potentially increasing profitability. PI is particularly useful during peak demand times when parallel processing of requests can ensure optimal vehicle utilization. RI can effectively reduce passenger wait times during off-peak hours by prioritizing high-regret requests, making the service more attractive for service providers. TNCs can transform from competitors to valuable collaborators in urban mobility by aligning with PT and leveraging prioritization for more efficient, demand-responsive services. Service operators are encouraged to implement these strategies to plan a more integrated and inclusive service. Strategically deprioritizing specific trips can significantly enhance service for users in remote areas.

Third, PT operators can extend their service reach and appeal through SAV collaborations, particularly by incorporating FMLM services. Integrating SAVs into PT networks can extend the reach of PT services, making them more accessible and attractive to a broader user base. PTRI and AI can ensure that SAVs complement PT by providing critical FMLM connectivity, making PT more accessible and attractive. AI can prioritize service in areas with poor PT access, while PTRI can dynamically adjust SAV routes based on real-time PT availability.

Finally, the government can benefit from this study by fostering a favorable regulatory environment for SAV-PT integration. This includes offering incentives for SAVs to enhance PT accessibility and investing in the necessary infrastructure to support this integration. PI can be employed in high-demand urban areas during peak hours to manage traffic congestion and optimize fleet utilization, making it ideal for handling major events or rush hours. RI can ensure equitable service distribution by prioritizing critical requests in mixed urban-rural areas addressing transportation inequities, especially during off-peak hours. PTRI enhances FMLM connectivity in urban areas with established PT networks by prioritizing ride requests that offer significant time-saving benefits over PT alternatives, thus improving PT integration and reducing reliance on private vehicles. Finally, AI is crucial for improving accessibility in low PT-access zones, ensuring a more equitable distribution of SAV services, and promoting inclusive urban development. By employing these strategies, governments can create a more efficient, accessible, and equitable transportation network, addressing immediate and long-term urban mobility needs.

In summary, this study can pave the road for a more accessible, equitable, and cohesive urban mobility network through trip prioritization. These strategies demonstrate that trip prioritization improves user experience and holds the potential for increased profitability for operators and environmental benefits. While the optimization strategies developed in this paper focus on SAVs, they are also adaptable for TNCs with HOVs. These strategies are designed for SAVs due to their real-time operational control and compatibility with existing infrastructure. The continuous operation of SAVs without needing driver brakes maximizes fleet utilization and reduces operational costs [9]. This capability ensures higher levels of efficiency and responsiveness compared to HOVs in general, but the strategies do not strictly require any autonomous features to be implemented. This is an assumption and limitation of these strategies and our study: they do not strictly employ any properties unique to AVs and can be replicated in HOVs. The cost factors are used in the demand estimation step to generate the demand specifically for SAVs, which will change for HOVs. As the costs are higher in HOVs, the number of requests (demand) will decrease in the demand generation step, and fleet utilization will be less efficient than in SAVs. A critical aspect that would need adjustment when adapting these strategies for HOVs is estimating demand by higher fares, which will alter the mode choice and demand forecasts [2]. Prioritization can be achieved with HOVs; however, it will be less effective due to the direct control of the dispatcher over SAVs because of their autonomous nature. Therefore, the strategies presented in this paper are adaptable to HOVs, with necessary adjustments to account for the differences in operational control and cost structures.

8. Conclusions and Future Remarks

As we embrace the era of increasing vehicle automation, the emergence of SAVs promises to revolutionize our transportation systems. These SAVs, blending the convenience of shared on-demand services with the advancements of AVs, present an innovative approach to urban mobility challenges. Integrating SAVs with PT offers a promising solution to enhancing accessibility and equity in urban transportation, especially in low-density areas. However, their operation and optimization are critical tasks ensuring the service quality and performance of the SAV service. Through applying four insertion strategies, this study demonstrated the potential operational algorithms to govern SAV performance for more efficient, equitable, and accessible transportation objectives, particularly in areas with limited PT accessibility.

The strategies proposed in this paper, PI, RI, PTRI, and AI, were implemented and evaluated using the MATSim simulator within the context of the Melbourne Metropolitan Area. The first two strategies improve the service quality of SAVs, and the other two focus on improving PT accessibility throughout the network. The results demonstrated that the strategic insertion and prioritization of ride-matching in SAVs, particularly in smaller fleet scenarios, substantially improved service efficiency, as evidenced by a higher number of served rides and decreased average travel time. However, an increase in fleet size resulted in only a slight improvement in service quality and a significant drop in vehicle utilization, indicating a critical trade-off between enhancing service quality and maintaining resource efficiency. Regarding service externalities, the study observed a reduction in average VKT and EKT per ride in smaller fleets, suggesting environmental benefits. Applying the Gini index to assess service provision equity revealed that strategies such as AI prioritizing less accessible zones resulted in a more equitable distribution of wait times across the network. This finding underscores the effectiveness of strategic insertions in achieving balanced service distribution. These new strategies can potentially provide better service in the areas of low PT accessibility, and people can use these services to access PT, which is a step forward in developing sustainable transport.

Several areas are open for further investigation. Firstly, the strategies must be investigated with a mode choice model, and their effects on the iterative demand should be explored. Such analysis can illustrate how these strategies attract more users in low-demand areas, enhancing service quality. Additionally, integrating prioritization-based relocation strategies alongside current dispatching strategies could improve operational efficiency and service quality. This approach would allow for dynamic relocation and assignment of vehicles based on real-time demand, potentially reducing wait times and improving user satisfaction. Additionally, applying machine learning to prioritize and schedule trips offers another promising area for development. Moreover, the current proposed strategies do not reassign requests once they have been processed. Future research should consider these reassignments to optimize global solutions, which could significantly benefit service operators and customers by improving overall service efficiency and user experience. Finally, the methodologies used in this study for evaluating PT accessibility could be improved to offer a more detailed understanding of how SAVs can complement existing transport networks. Understanding and adding how the required fleet varies based on factors like population density, PT coverage, and household car ownership can further enhance the SAV dispatching strategies in different urban contexts. Identifying the optimal fleet sizes for various locations that balance trade-offs between metrics, such as service efficiency, environmental impact, and equity, would be a valuable direction for future research. Future research can build on the current focus by investigating additional unique properties of SAVs, such as platooning and real-time passenger matching changes for global improvements. These features could enhance efficiency and service quality, contributing to the evolving urban mobility landscape. By investigating these aspects, researchers can demonstrate how SAVs can outperform HOVs, particularly their ability to leverage advanced technologies for superior operational performance.