Optimizing Fleet Size in Point-to-Point Shared Demand Responsive Transportation Service: A Network Decomposition Approach

Abstract

With increasing urbanization and the demand for efficient, flexible transportation solutions, demand-responsive transportation services (DTRS) has emerged as a viable alternative to traditional public transit. However, determining the optimal fleet size to balance the investment and operational revenue remains a significant challenge for service providers. In this article, we address the optimization of fleet size in point-to-point shared demand DRTS, which widely operates within many cities. To capture the uncertain passenger demands in the future when planning the fleet size currently, we model this problem with a framework of two-stage stochastic programming with recourse. Fleet sizing decisions are made in the first stage before the uncertain demands are revealed. After the uncertainty is revealed, the second stage involves making additional decisions to maximize operational revenue. The objective is to optimize the total revenue of the first-stage decisions and the expected revenue of the recourse actions. To solve this practical problem, we resort to the Model Predictive Control method (MPC) and propose a network decomposition approach that first converts the transportation network to a nodal tree structure and then develops a Nodal Tree Recourse with Dependent Arc Capacities (NTRDAC) algorithm to obtain the exact value of the expected recourse functions. In the experiments, NTRDAC is able to produce results within seconds for transportation networks with over 30 nodes. In contrast, a commercial solver is only capable of solving networks with up to five nodes. The stability tests show that NTRDAC remains robust as the problem size varies. Lastly, the value of the stochastic solution (VSS) was evaluated, and the results indicate that it consistently outperforms the expected value solutions. Numerical experiments show that the performance of the NTRDAC algorithm is quite encouraging and fit for large-scale practical problems.

1. Introduction

The rapid growth of urbanization and the increasing demand for flexible and efficient transportation solutions have highlighted the importance of demand-responsive transportation services (DRTS). Unlike traditional fixed-route transit systems, DRTS offers a dynamic and adaptive approach to public transportation, optimizing routes and schedules based on real-time passenger demands. This flexibility not only improves the user experience but also has the potential to enhance operational efficiency and reduce environmental impacts.

Demand responsive transportation, also known as flexible transportation, contains many patterns or forms of services to adapt to the demand of passengers, such as dial-a-ride [1,2], microtransit [3,4], point-to-point shuttle [5,6], feeder [7,8], ridesharing and carpooling [9,10], ride-hailing [11,12], etc. [13,14]. Among these service forms, point-to-point shuttle services have soared recently in practice. These services provide customers with direct routes between major transit points, benefiting service operators greatly by allowing them to select only feasible, well-defined locations where safe boarding and alighting are possible [15]. Furthermore, these services are designed for passengers to enhance connectivity within the transportation network, making it easier to transfer between transit points, such as airports, train stations, bus terminals, local attractions, central business district areas (CBDs), residential areas, etc. According to the research by Kjoerstad and Renolen [16], customers exhibit a high valuation of their time when utilizing transportation services. Their study results show that customers prefer using direct transit modes 1.8 to 5.0 times more than non-direct ones that require a 5 min wait at an interchange point. This preference increases to 2.5 to 9.2 times if the waiting time reaches 10 min. Before launching a point-to-point DRTS, service providers must make a critical decision on fleet size—determining how many vehicles to invest in—while considering current investment and potential future operational revenue.

Real-world examples regarding point-to-point shuttle services can be seen in many cities. For instance, in Zhuhai, China, a service provider, Zhuhai Airport Express (https://www.51sfbus.com/sflv-plus/#/rentcar/search?btntabModel=0 accessed on 20 July 2024 via WeChat browser), offers point-to-point on-demand transportation between several points within Zhuhai City, such as Chimelong Ocean Kingdom (local attraction), Gongbei Port (transportation terminal of railway and bus), Jida (Central Business District), and several resident areas. In Australia, Con-x-ion (https://www.con-x-ion.com/point-to-point accessed on 20 July 2024) provides many point-to-point routes, mostly from Brisbane Airport to many local attractions nearby. Figure 1 is a screenshot from Con-x-ion’s website showing the mini-van used for this service and their popular service routes.

Con-x-ion’s point-to-point routes create a DRTS network, allowing passengers to travel between various transit points. For example, consider five transit points: Brisbane, Noosa, Sunshine Coast, Caloundra, and Mooloolaba. In this DRTS network, passengers can travel between any two points, with each point serving as both a starting and an ending location. From each starting point, there are four direct routes connecting to the other four points. This DRTS network is depicted in Figure 2.

A critical challenge in implementing DRTS, especially for strategic planning, is determining the optimal fleet size [17]. An inadequately sized fleet can lead to service delays, increased operational costs, and unsatisfied customer demand, while an oversized fleet may result in underutilization of resources and unnecessary expenditures. Therefore, optimizing fleet size is essential to balance service quality with cost-effectiveness. In this study, we use the framework of two-stage stochastic programming with recourse to capture the feature of DRTS where future demands are uncertain when planning the fleet size in the first stage. The first-stage decision involves selecting an initial fleet size, while the second-stage decisions adjust operational strategies based on realized demand scenarios. To ensure that the system responds effectively to demand fluctuations, we integrate control mechanisms that manage fleet deployment dynamically. These control strategies are embedded in the second stage, where operational adjustments are made in response to actual demand, which is unknown during the initial fleet sizing stage. The stochastic nature of demand is modeled through a set of possible future demand scenarios, estimated using historical data and forecasting techniques. This ensures that the fleet size determined in the first stage is robust against various demand patterns, with the flexibility to adjust operations in the second stage based on the actual demand realization. Furthermore, for the aforementioned real-world problems, the large number of transit points where these shuttle services operate would make solving this large-scale practical stochastic programming problem very time-consuming or even infeasible to be optimal. To tackle this problem, we introduce a network decomposition method tailored to efficiently obtain the exact value of the expected recourse functions.

The contributions of this paper are threefold: (i) To the best of our knowledge, this is the first work to address the large-scale practical problem of optimizing fleet size in DRTS, considering vehicle investment and operational revenue resulting from uncertain passenger demands. (ii) The network decomposition method presented in this article relaxes the nodal tree recourse algorithm by allowing the arcs’ capacities, which are random variables, to be dependent. (iii) This article presents a pragmatic practice bridging the gap between theory and real-world application.

The rest of this paper is organized as follows. Section 2 reviews the related literature. Section 3 introduces the notation and describes the two-stage stochastic formulation. Section 4 details the network decomposition method, and numerical experiments are provided in Section 5. Finally, Section 6 concludes this paper and discusses several extensions and future research directions.

2. Literature Review

Fleet size optimization problems have recently attracted much interest in the research domain, particularly within DRTS. These services, offering flexible routing and scheduling based on real-time uncertain demand, present unique challenges and opportunities for service providers in fleet management. In this section, we review the literature related to fleet sizing problems and classify the literature based on their objective and the literature regarding the solution technique to stochastic programming.

The first stream of papers investigates the correlation between fleet size and other parameters. Daganzo and Ouyang [18] present a general analysis framework for systems providing non-shared and shared services. With agent-based simulations, they investigate the relationship between travel time and fleet size at different demand density levels. Their research insights can be used to explore operation and pricing strategies for taxi companies and government agencies. Hörl et al. [19] study the performance of different fleet sizes and operational policies based on simulation scenarios by MATSim 0.10. Their results indicate that a fleet size of 7000–14,000 vehicles in Zurich, Switzerland, could serve 90% of requests. In these articles, fleet size is important but only serves as an exogenous variable or model parameter instead of a decision variable.

The second stream of research focuses on optimizing fleet size using different models and methods, where fleet size is one of the model decision variables. Shehadeh et al. [20] study the fleet size and allocation optimization problem for on-demand last-mile transportation services under passenger demand uncertainty. They propose and analyze a two-stage stochastic programming model and a robust optimization model where the two-stage stochastic programming model is solved by the sample average approximation (SAA) approach. They resort to the SAA approximation approach because obtaining an optimal solution to the stochastic programming model is complex. Beaujon and Turnquist [21] also investigate a fleet size and allocation problem under uncertainty where the uncertainties are related to demands of loaded vehicles and travel time between origin points to destination points. To solve the problem, they propose a network approximation method to compute the probability density functions of net vehicles at period t, where they argue that the normal probability density function can represent it. The pitfall of this model is that it ignores the demand uncertainty of passengers, which is the core feature of DRTS. Winter et al. [22] present an automated demand-responsive transport system (ADRTS) for a campus–train station shuttle service to evaluate the system’s performance. They compute the required minimal fleet size while achieving expected results, such as cost savings and reduction in passenger waiting time. The model only considers a single pick-up and drop-off station, and the method they apply to obtain this result is simulation, so the result is not promising for practical DRTS problems. Diana et al. [23] study the problem of determining the number of vehicles needed for DRTS with predetermined quality for the customers in terms of waiting time at the stops and maximum allowed detours. They formulate the problem with a probability model and intend to analyze the impact of fleet size on the customers’ waiting time. The objective is to provide an estimation of the required size of the fleet in different scenarios. The critical assumption of their paper is that there is no sharing among different customers for vehicle capacity, where the fleet has to be dispatched exclusively based on the list of requests, such as in the taxicab system, which is different from that of shared DRTS. Militão and Tirachini [24] introduce an optimal fleet size problem for a shared door-to-door DRTS to minimize the total costs for operators and customers. The decision variables are vehicle capacity and fleet size for human-driven and automated vehicle operations. They analyze the relevant variables using data from a large-scale agent-based simulation (ABS) applied to Munich. However, the outcomes of ABS can be susceptible to initial conditions and parameter settings, making it challenging to validate and generalize results. Furthermore, ABS can be computationally intensive, particularly when simulating large numbers of agents or when the model includes detailed interactions and stochastic elements. Even though fleet size is one of the decision variables in their models, these models do not consider the investment associated with the fleet.

Stochastic programming (SP) is a well-established mathematical framework for optimizing decision making under uncertainty. Model predictive control (MPC) is an advanced control strategy commonly used in dynamic systems where decisions are made based on the prediction of future system behavior over a finite horizon [25]. The key idea is to use a mathematical model of the system to predict its future states and solve an optimization problem at each decision step. In stochastic programming, uncertainty is modeled explicitly, typically through probabilistic scenarios or distributions. The optimization considers multiple possible future scenarios, incorporating uncertainty into the decision-making process. The complexity of these problems, mainly due to numerous scenarios (known as the curses of dimensionality [26]), has driven the development of various solution techniques. The techniques for solving stochastic programs can be classified into two groups.

The first group of methods aims to speed up the convergence or reduce the number of scenarios. These methods typically turn the original problem into huge deterministic problems by using the samples from the distribution of the random coefficients, such that different techniques have been developed to deal with convergence. For example, Benders decomposition, also known as the L-shaped method, first divides the original problem into a master problem and a subproblem, then feasibility and/or optimality cuts are imposed iteratively to obtain the optimal solution [27,28]. Iterations exist in the scenario aggregation method. To compute an implementable solution, this method typically starts with a relatively small subset of scenarios and includes additional constraints iteratively [29,30]. For the stochastic decomposition methods, their objective is to obtain the lower bounds of the expected recourse function using cutting planes [31,32]. The abovementioned methods are usually used to accelerate convergence speed and are generally not practical for large-scale dynamic network problems. Readers are recommended to refer to Birge and Louveaux [33] for details. On the contrary, another technique, called scenario reduction, aims to reduce the problem size instead of solving large deterministic problems. Dupačová et al. [34] present the idea of scenario reduction, aiming to generate a natural probability metric as an approximation metric to obtain the closest subset from a larger superset of scenarios. However, ensuring the quality of solutions with the reduced scenarios is the most challenging, such that different methods related to scenario reduction on measuring the similarity between the original set and the reduced set have been suggested [35,36].

The second group of methods leverages the special structure of stochastic problems, especially those related to network recourse problems. The strategy of these methods is first to decompose the original problem into several tractable subproblems and then solve those subproblems instead of tackling the original one. For example, Wallace [37] introduces a method of using piecewise linear functions to approximate the expected recourse function for the network recourse problem. Powell and Cheung [38] introduce a TREC algorithm to obtain the exact value of the expected recourse function as a scalar supply of resources for a tree recourse problem. Their experiments show that the TREC algorithm fits large-scale practical problems. After that, they present a network recourse decomposition approach to applying the TREC algorithm for a two-stage dynamic network problem [39]. However, the TREC algorithm’s condition is that each arc’s random capacity must be mutually independent. In this article, we adopt the strategy from the TREC algorithm and propose our algorithm, which can handle dependent random arc capacities.

In summary, while some articles have explored fleet sizing optimization, many do not account for both the investment required for the fleet and the uncertainty of demand in their models. Moreover, the development of practical algorithms for obtaining the exact value of the expected recourse functions, particularly for large-scale, real-world DRTS problems, has not been previously addressed. The innovations of this study are summarized in

Table 1. A comparison between our research and existing studies for optimizing fleet size.

Author(s)	Investment Incorporated	Obtain Exact Value	Insensitive to Input Data	Stable to Problem Size
Militão and Tirachini [24]	🗸	×	×	🗸
Diana et al. [23]	×	🗸	×	🗸
Winter et al. [22]	×	×	🗸	🗸
Beaujon and Turnquist [21]	×	🗸	×	🗸
Shehadeh et al. [20]	🗸	×	🗸	×
Our study	🗸	🗸	🗸	🗸

.

3. Problem Formulation

Consider a transportation service provider who plans to operate a point-to-point shuttle service within a city. Assume the service provider has chosen $\mathcal{N}$ well-defined locations, such as airports, train or bus stations, and local attractions, as transit points. We also assume that the fare from point $i\in \mathcal{N}$ to point $j\in \mathcal{N}$ for each customer, denoted as $f_{ij}$, has been set. Passengers place orders on their mobile phone, and their arrival at each transit point $i\in \mathcal{N}$ destined to point $j\in \mathcal{N}$, denoted as $d_{ij}$, is the demand for shuttle service, which is a random variable. Its distribution is known to the service provider. To fulfill these random demands, the provider plans to purchase s identical vehicles, each of which has H available seats, which we call vehicle capacity. The challenge to this service provider is determining the optimal s to maximize the profit, which is the revenue from serving customers minus the investment in these s vehicles.

This fleet size optimization problem can be modeled as two-stage stochastic programming with recourse. The decision to determine s, the fleet size, is called the first-stage investment decision, which is to be taken without full information on the random customer demands $d_{ij},i\in \mathcal{N},j\in \mathcal{N}$. Later, full information is received on the realization of random demands. Then, second-stage or dispatching actions $x_{ij},i\in \mathcal{N},j\in \mathcal{N}$ are taken, which generates revenue from these s vehicles. We first state our assumptions before presenting the mathematical model.

Assumption 1. 

Order rejections are allowed for service providers.

Assumption 2. 

The distribution of random demands and the depreciation of each vehicle are considered within the same period, such as an hour.

Assumption 3. 

Decisions are made only once within a time period.

The first assumption says that the service provider is allowed to reject orders. This mechanism is because passengers have many alternatives in transportation, and the private sector operates the shuttle service, so maximizing revenue is one of the critical objectives. Recently, many studies have investigated this mechanism [24,40,41]. The second assumption is made to simplify our presentation. Since the distribution of random demands has to be estimated for a certain period, having the depreciation of each vehicle representing the investment for the same period will significantly facilitate our model and computation. The third assumption is to keep the network size manageable and avoid the details of making decisions multiple times within a time period [42].

Let $\omega \in \Omega$ be an outcome of a probability space ($\Omega ,\mathcal{F},\mathcal{P}$) for the passenger demands in the second stage. The parameters and variables for the two-stage stochastic programming model are summarized in

Table 2. Notations.

		Description
Parameters	$\mathcal{N}$	Set of transit points, $\mathcal{N}=\{1,2,...,N\}$.
	H	Available seats per vehicle, also known as vehicle capacity.
	g	The depreciation of each vehicle for a certain period.
	$c_{ij}$	Cost of each trip from point i to point j for each vehicle.
	$f_{ij}$	Fare of each passenger from point i to point j.
	$d_{ij}\left(\omega \right)$	Passenger demands from point i to point j under
		realization $\omega$ for a certain period.
Intermediate	$v_i\left(\omega \right)$	Available vehicle at point i under realization $\omega$.
variable
Decision	s	Fleet size in first stage.
variables	$x_{ij}\left(\omega \right)$	Number of vehicles dispatched from point i to point j in
		second stage under realization $\omega$.

.

To ease our presentation, we define the available vehicle vector $\mathit{V}=(v_i:i\in \mathcal{N})$ and the passenger demands vector $\mathit{D}\left(\omega \right)=(d_{ij}\left(\omega \right):i\in \mathcal{N},j\in \mathcal{N})$. The two-stage fleet size optimization problem can be formulated as

$$\begin{array}{c}\hfill max-g·s+{\mathbb{E}}_{\omega }\left[Q(\mathit{V},\mathit{D}(\omega \left)\right)\right],\end{array}$$

(1)

subject to

$$\begin{array}{c}\hfill \sum _{i=1}^N{v}_i=s,\end{array}$$

(2)

$$\begin{array}{c}\hfill s\ge 0,s\in \mathbb{Z}\end{array}$$

(3)

where for a given available vehicle vector $\mathit{V}$ and a particular realization $\omega$, $Q(\mathit{V},\mathit{D}(\omega \left)\right)$ is the value of a maximization problem which is defined as follows:

$$\begin{array}{c}\hfill Q(\mathit{V},\mathit{D}\left(\omega \right))=max\sum _{i=1}^N\sum _{j=1}^N\left(-c_{ij}·x_{ij}\left(\omega \right)+f_{ij}·min\{H·x_{ij}\left(\omega \right),d_{ij}\left(\omega \right)\}\right),\end{array}$$

(4)

subject to

$$\begin{array}{c}\hfill \sum _{j=1}^N{x}_{ij}\left(\omega \right)=v_i,\forall i\in \mathcal{N},\end{array}$$

(5)

$$\begin{array}{c}\hfill x_{ij}\left(\omega \right)\ge 0,x_{ij}\left(\omega \right)\in \mathbb{Z},\forall i\in \mathcal{N},\forall j\in \mathcal{N}.\end{array}$$

(6)

The problem defined by Equations (1)–(6) is a typical two-stage stochastic program with network recourse, where (1)–(3) are called the first-stage problem and (4)–(6) are called the second-stage problem. The expectation functional ${\mathbb{E}}_{\omega }\left[Q(\mathit{V},\mathit{D}(\omega \left)\right)\right]$ is called the expected recourse function. The objective function (1) is profit maximization, which consists of the depreciation of vehicles and the expected recourse revenue. Constraint (2) is to force the total available vehicles to be equal to the fleet size, and (3) is the non-negativity constraint. The state vector $\mathit{V}$ stores the available vehicles for stage two, and it is the only variable that communicates information to the second stage. The expected recourse function (4) is determined by solving the second-stage problem for each scenario $\omega$ according to the available vehicle supplies $\mathit{V}$. Constraint (5) enforces that the total number of vehicles dispatched from point $i\in \mathcal{N}$ must be those vehicles available at point $i\in \mathcal{N}$, and Constraint (6) ensures that the number of dispatched vehicles must be a positive integer. It is worth noting that to deal with the expression $min\{H·x_{ij}\left(\omega \right),d_{ij}\left(\omega \right)\}$, we just need to replace this expression with intermediate variables $q_{ij}\ge 0$ and add two constraints, $q_{ij}\le H·x_{ij}\left(\omega \right)$ and $q_{ij}\le d_{ij}\left(\omega \right)$, where $\forall i\in \mathcal{N},\forall j\in \mathcal{N}$. In this way, problems (4)–(6) become common recourse problems.

Finding exact optimal solutions to stochastic programs is generally intractable due to the uncertain demands that increase the number of scenarios exponentially. In this point-to-point shuttle service case, if the service provider operates at $N=10$ transit points, which generates 9 shuttle service routes in each point $i\in \mathcal{N}$ (from point i to other points $j\in \mathcal{N}$ except point i itself), the total number of shuttle service routes is 90. Assume that each random passenger demand, $d_{ij},i\in \mathcal{N},j\in \mathcal{N}$, is a discrete random variable and takes four possible values on average. The total number of scenarios is $4^{90}=2^{180}$, which is intractable. In this article, we resort to the model predictive control method (MPC), where a decision is made at time t by solving a typically approximate model over a horizon $(t,t+L)$. Specifically, in our model, to determine the fleet size s in the first stage, we have to evaluate the value function ${\mathbb{E}}_{\omega }\left[Q(\mathit{V},\mathit{D}(\omega \left)\right)\right]$ parameterized in s in the second stage. In the following Section 4, we present a network decomposition method tailored for this type of network recourse problem to efficiently obtain the exact value of the expected recourse functions. The workflow of the network decomposition method, consisting of four steps, is illustrated in Figure 3. Step 2, solving a single-root-node problem, is to compute ${\mathbb{E}}_{\omega }\left[Q_i(v_i,\mathit{D}\left(\omega \right))\right]$, $\forall i\in \mathcal{N}$. Repeating step 2 for all nodes $i\in \mathcal{N}$ can obtain ${\mathbb{E}}_{\omega }\left[Q(\mathit{V},\mathit{D}(\omega \left)\right)\right]$, which is the main purpose of step 3.

4. Recourse Problem Decomposition

This section elaborates on the network decomposition method tailored for network recourse problems. First, in Section 4.1, we analyze the separability of the network, which enables us to deal with each transit point separately. Second, in Section 4.2, for completeness, we review an idea of the nodal tree algorithm which we leverage to obtain the exact value of the expected recourse function for a nodal tree structure recourse problem. Third, in Section 4.3, we elaborate on our algorithm extended from the nodal tree algorithm. Finally, we present the solution technique to the first-stage problem in Section 4.4.

4.1. Separability of Transit Points

It is reasonable to assume that passengers’ arrival to transit points (transit points and nodes are interchangeable in this article) are independent, and the random demands, $d_{ij},i\in \mathcal{N},j\in \mathcal{N}$, are independent discrete random variables too. The rationale behind this assumption is that in a real-world application, a common service provider often serves a large number of independent passengers [42]. For the second-stage recourse problem, this independence enables us to decompose the network recourse problem by transit points, meaning we can treat each transit point separately. With this separability property, the expectation expression in Equation (1) can be rewritten as

$$\begin{array}{c}\hfill {\mathbb{E}}_{\omega }\left[Q(\mathit{V},\mathit{D}(\omega \left)\right)\right]=\sum _{i=1}^N{\mathbb{E}}_{\omega }\left[Q_i(v_i,\mathit{D}\left(\omega \right))\right].\end{array}$$

(7)

Equation (7) provides a favorable method to obtain the recourse function’s expected value, enabling us to handle individual transit points separately. Since each transit point $i\in \mathcal{N}$ is identical, we focus on one of the transit points $i\in \mathcal{N}$ only, which means we can turn to solving the single-root-node recourse problem rooted at node $i\in \mathcal{N}$. The structure of this single-root-node recourse problem is illustrated in Figure 4.

4.2. Solution Technique to Nodal Tree Recourse Problems

This subsection briefly reviews the solution technique to nodal tree recourse problems introduced by Powell and Cheung [38], which we leverage to solve our single-root-node recourse problem.

A nodal tree recourse problem is defined as follows. Consider a directed one-level tree (we say a tree has n levels if n is the depth of the tree) rooted at node r with independent random arc capacities ${\xi }_i$ such as the one depicted in Figure 5. The total supply to this tree, entering the root node, is S. For a given realization $\omega$, a unit of flow traversing a path (link connecting the root node to a leaf node) will result in a certain cost $c_i$. Assume all m paths have been ranked by their costs in ascending order, meaning $c_1<c_2<...<c_m$. We wish to find the expected total cost of the tree problem as a function of the scalar supply.

Let us define

$$f_n=\mathrm{flow}\mathrm{on}\mathrm{path}n.$$

For a given realization $\omega$, the nodal tree recourse problem is

$$\begin{array}{c}\hfill Q(S,\xi \left(\omega \right))=\underset{f_n\left(\omega \right)}{min}{c}^{T}f\left(\omega \right),\end{array}$$

(8)

subject to

$$\begin{array}{c}\hfill \sum _{n=1}^m{f}_n\left(\omega \right)=S,\end{array}$$

(9)

$$\begin{array}{c}\hfill 0\le f_n\left(\omega \right)\le {\xi }_n\left(\omega \right),n=1,2,...,m.\end{array}$$

(10)

To solve the problems (8)–(10), assigning flow to the paths in their ranking greedily can obtain the optimal solution. This optimal policy enables us to solve the problem efficiently. Define the following:

• $\varphi (k,n)=P$ {the kth unit of flow entering node r takes the nth path}, which we call a routing probability;
• $G\left(k\right)=$ expected marginal cost for the kth unit of flow entering node r;
• $Z^n=$ the total capacity of the first n ranked paths.

Therefore, $Z^n$ can be computed by

$$\begin{array}{c}\hfill Z^n=\sum _{i=1}^n{\xi }_i,\end{array}$$

(11)

and $\varphi (k,n)$ can be obtained by

$$\begin{array}{c}\hfill \varphi (k,n)=P\{(Z^n\ge k\}-P\{Z^{n-1}\ge k\}.\end{array}$$

(12)

With the routing probability $\varphi (k,n)$, $G\left(k\right)$ can be calculated by

$$\begin{array}{c}\hfill G\left(k\right)=\sum _{n=1}^m{c}_i·\varphi (k,n).\end{array}$$

(13)

Finally, the expected value of the recourse problem, $\widehat{Q}\left(S\right)$, can be obtained easily by

$$\begin{array}{c}\hfill \widehat{Q}\left(S\right)=\sum _{k=1}^{S}G\left(k\right).\end{array}$$

(14)

Equation (11) holds under the condition that random arc capacities are mutually independent. The theory behind Equation (12) is that the greed algorithm holds for this nodal tree problem, meaning that the probability of the kth unit taking the nth path is the one that the total capacity of the first n paths must be greater or equal to k, and the total capacity of the first $n-1$ paths must be less than k. Mathematically, it is $\varphi (k,n)=P\{Z^n\ge k\mathrm{and}{Z}^{n-1}<k\}$. Since the random arc capacities are mutually independent, such that the probability of $Z^n\ge k$ and $Z^{n-1}<k$ is independent, this means that $\varphi (k,n)=P\{Z^n\ge k\}·P\{Z^{n-1}<k\}=P\{Z^n\ge k\}·(1-P\{Z^{n-1}\ge k\})$. Finally, suppose the total capacity of the first $n-1$ paths is greater than or equal to k, which indicates that the total capacity of the first n paths must be greater than or equal to k (with probability of 1), such that $P\{Z^n\ge k\}·P\{Z^{n-1}\ge k\}=P\{Z^{n-1}\ge k\}$. For proof details, we recommend readers refer to [38].

The solution to the nodal tree recourse problem provides an efficient method for calculating the expected value of the recourse function. In Section 4.3, we propose a process to convert the single-root-node recourse problem to a nodal tree structure.

4.3. Conversion of Single-Root-Node Recourse Problems

This subsection presents the procedure to convert the single-root-node recourse problem to the nodal tree structure. Three factors need to be considered for a nodal tree problem. The first is the supply to the root node, the second is the revenue of each path, and the third is the random capacity of the corresponding path. Since the vehicles $v_i$ are scalar supplies entering into the root node, we focus on how to compute the revenue and capacity for each path.

To begin with, we present the converting processes with a single leaf node $j\in \mathcal{N}$, which means we first focus on the path from root node i to leaf node j. The passenger demand on this path is $d_{ij}$, a discrete random variable. The fare for each passenger is $f_{ij}$, and the cost for each vehicle traversing this path is $c_{ij}$.

We start with the computation of the path revenue. Vehicles carrying $h=1,2,...,H$ passengers departed from node $i\in \mathcal{N}$ to node $j\in \mathcal{N}$ generate different revenue, denoted by $r_{ij}\left(h\right)$, which can be calculated by $r_{ij}\left(h\right)=h·f_{ij}-c_{ij}$, where $h=1,2,...,H$ and H is the total available seats of each vehicle. It is natural to consider creating H paths rooted at node $i\in \mathcal{N}$ pointing to node j, such that the revenue of each path can be determined by $r_{ij}\left(h\right),h=1,2,...,H$, respectively. Duplicating the leaf node $j\in \mathcal{N}$ $H-1$ times creates H leaf nodes $j_h,h=1,2,...,H$ and generates a nodal tree. This nodal tree structure, rooted at node $i\in \mathcal{N}$ and ended in leaf nodes $j_h,h=1,...,H$ with total H paths and corresponding revenue $r_{ij}\left(h\right)$, is depicted in Figure 6.

Now, we turn to compute each path’s capacity, denoted by ${\xi }_{ij}\left(h\right)$, which is a random variable capturing the number of vehicles carrying $h=1,2,...,H$ passengers given the passenger random demand $d_{ij}$. The policy of assigning passengers to vehicles determines the number of vehicles used and the number of passengers carried in each vehicle. Since our objective is to maximize operational revenue, a passenger assignment policy exists to achieve this, as stated in Proposition 1.

Proposition 1. 

For any realization ω, given passenger demands, the optimal policy of passenger assignment to vehicles is to assign more passengers to a departing vehicle until its seats are all occupied.

Proof. 

Assume there are $d_{ij}\left(\omega \right),i\in \mathcal{N},j\in \mathcal{N}$ passengers waiting at transit point $i\in \mathcal{N}$ under realization $\omega$, and assume there are $h=0,1,2,...,H-1$ passengers having been assigned into vehicle k. The revenue of this transportation is $r_{ij}\left(h\right)=f_{ij}·h-c_{ij}$. If we assign additional $\Delta h>0$ passengers into vehicle k, the marginal revenue $MR\left(P_{ij}\right)={\displaystyle \frac{r_{ij}(h+\Delta h)-r_{ij}\left(h\right)}{\Delta h}}=f_{ij}\ge 0$. It means assigning more passengers into this vehicle k can achieve positive marginal revenue, such that the optimal policy is to assign more passengers into a vehicle until it is fully loaded.    □

Proposition 1 indicates, given passenger demands $d_{ij}\left(\omega \right),i\in \mathcal{N},j\in \mathcal{N}$ under realization $\omega$, if $k\ge 1$ vehicles have been dispatched from point i to point j, there is at the most one of these k vehicles which is not fully loaded. So, the number of fully loaded vehicles under realization $\omega$ can be obtained by ${\xi }_{ij}\left(H\right)=\lfloor {\displaystyle \frac{d_{ij}\left(\omega \right)}{H}}\rfloor$, where $\lfloor X\rfloor$ means to round down X, and H is the available seats of a vehicle. The number of the not fully loaded vehicles is 1, which carries the remainder of passengers ${\xi }_{ij}\left(h\right)=d_{ij}\left(\omega \right)$$mod$ H, where operator “$mod$” is the modulo operation, and $h\in \{1,...,H-1\}$. In this way, passenger demands $d_{ij}\left(\omega \right)$ can be converted to vehicle demands under any realization $\omega$, which can be expressed mathematically as

$$\begin{array}{c}\hfill {\xi }_{ij}\left(h\right)=\left\{\begin{array}{c}\lfloor {\displaystyle \frac{d_{ij}\left(\omega \right)}{H}}\rfloor ,\mathrm{f}\mathrm{u}\mathrm{l}\mathrm{l}\mathrm{y} \mathrm{l}\mathrm{o}\mathrm{a}\mathrm{d}\mathrm{e}\mathrm{d} \mathrm{v}\mathrm{e}\mathrm{h}\mathrm{i}\mathrm{c}\mathrm{l}\mathrm{e}\mathrm{s} \mathrm{c}\mathrm{a}\mathrm{r}\mathrm{r}\mathrm{y}\mathrm{i}\mathrm{n}\mathrm{g} h=H \mathrm{p}\mathrm{a}\mathrm{s}\mathrm{s}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{e}\mathrm{r}\mathrm{s},\hfill \\ 1,\mathrm{v}\mathrm{e}\mathrm{h}\mathrm{i}\mathrm{c}\mathrm{l}\mathrm{e} \mathrm{c}\mathrm{a}\mathrm{r}\mathrm{r}\mathrm{y}\mathrm{i}\mathrm{n}\mathrm{g} \mathrm{t}\mathrm{h}\mathrm{e} \mathrm{r}\mathrm{e}\mathrm{m}\mathrm{a}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{r} h=d_{ij}\left(\omega \right)mod H \mathrm{p}\mathrm{a}\mathrm{s}\mathrm{s}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{e}\mathrm{r}\mathrm{s},\hfill \\ 0,\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}.\hfill \end{array}\right.\end{array}$$

(15)

With Equation (15), passenger demand $d_{ij}\left(\omega \right)$ can be converted to vehicle demand ${\xi }_{ij}\left(h\right),h=1,2,...,H$ for any realization $\omega$. In a nodal tree structure, these vehicle demands are represented by paths rooted at node $i\in \mathcal{N}$ pointing to leaf nodes $j_h\in \mathcal{N},h=1,2,...,H$. The number of passengers carried determines the ranking of these paths. Corollary 1 states that the ranking of these paths is from i -> $j_H$ down to i -> $j_1$. The symbol “x -> y” represents the path from root node x to leaf node y.

Corollary 1. 

Assume a nodal tree structure rooted at node $i\in \mathcal{N}$ with H leaf nodes $j_h\in \mathcal{N},h=1,2,...,H$. Path i -> $j_h$ represents carrying $h=1,2,...,H$ passengers. The ranking of these paths according to path revenue in descending order starts from the path i -> $j_H$ down to the one i -> $j_1$.

Proof. 

Since the path revenue is calculated by $r_{ij}\left(h\right)=f_{ij}·h-c_{ij}$, if $h^{\prime }>h$, we must have $r_{ij}\left(h^{\prime }\right)>r_{ij}\left(h\right)$. Because $H>H-1>...>1$, the ranking of paths according to path revenue in descending order is from path i -> $j_H$ down to the one i -> $j_1$.    □

Proposition 1 and Corollary 1 provide a method to convert the passenger demands to vehicle demands where multiple paths represent the vehicle demands. The single-root-node recourse problem rooted in node $i\in \mathcal{N}$ pointing to node $j\in \mathcal{N}$ with random passenger demands $d_{ij}$ can be represented by a nodal tree structure with root node i and leaf nodes $j_h,h=1,2,...,H$. The path revenue is $r_{ij}\left(h\right)$ and the corresponding path capacity is ${\xi }_{ij}\left(h\right)$ where $h=1,2,...,H$. The idea of this conversion is illustrated in Figure 7. For a better understanding of this converting process,

Table 3. An example of the converting process.

Possible Value of ${\mathit{d}}_{\mathit{ij}}$	Corresponding  Probability	Path Capacities ${\mathit{\xi }}_{\mathit{ij}}\left(\mathit{h}\right)$
		${\mathit{P}}_{\mathbf{1}}$	${\mathit{P}}_{\mathbf{2}}$	${\mathit{P}}_{\mathbf{3}}$	${\mathit{P}}_{\mathbf{4}}$
		${\mathit{\xi }}_{\mathit{ij}}\left(\mathbf{4}\right)$	${\mathit{\xi }}_{\mathit{ij}}\left(\mathbf{3}\right)$	${\mathit{\xi }}_{\mathit{ij}}\left(\mathbf{2}\right)$	${\mathit{\xi }}_{\mathit{ij}}\left(\mathbf{1}\right)$
3	0.1	0	1	0	0
5	0.3	1	0	0	1
6	0.4	1	0	1	0
9	0.2	2	0	0	1

shows an example with the discrete random variable $d_{ij}$ taking four possible values and the capacity of vehicle $H=4$. The ranking of these four paths is $P_1>P_2>P_3>P_4$, corresponding to vehicles carrying $h=4,3,2,1$ passengers, respectively.

The example in Table 3 shows that the numbers of vehicles ${\xi }_{ij}\left(h\right)$ dispatched from node $i\in \mathcal{N}$ to node $j\in \mathcal{N}$ carrying $h=\{1,2,3,4\}$ are also discrete random variables. Let us take ${\xi }_{ij}\left(4\right)$ and ${\xi }_{ij}\left(3\right)$, for example: the result indicates that the distribution of ${\xi }_{ij}\left(4\right)$ is $\left\{\right(0,0.1),(1,0.7),(2,0.2\left)\right\}$ and ${\xi }_{ij}\left(3\right)$ is $\left\{\right(0,0.9),(1,0.1\left)\right\}$. However, we cannot obtain the total capacity of the first two paths, $P_1$ and $P_2$, by summing ${\xi }_{ij}\left(4\right)$ and ${\xi }_{ij}\left(3\right)$ directly because they are not independent. Proposition 2 provides an efficient approach to compute the total capacity of the first n paths.

Proposition 2. 

For a sorted nodal tree rooted at the node $i\in \mathcal{N}$ pointing to H leaf nodes $j_h,h=1,2,...,H$, assume the random variable $d_{ij}$ takes $T<\infty$ possible values. Given all paths’ capacities ${\xi }_{ij}\left(h\right)$, where $h=1,2,...,H$, if the first n paths include those paths i -> $j_H$, i -> $j_{H-1}$,..., i -> $j_h$, then the distribution of the total capacity of the first n paths $Z_{ij}^n$ can be computed by $P\{Z_{ij}^n=k\}={\sum }_{T}P\{{\sum }_{x=h}^H{\xi }_{ij}\left(x\right)=k\}$.

Proof. 

Assume all paths rooted at point $i\in \mathcal{N}$ pointing to leaf nodes $j_h,h=1,2,...,H$ have been ranked in descending order. According to Corollary 1, the path to point $j_H$ must be ranked first and followed by paths to node $j_{H-1},j_{H-2},...,j_1$. According to Proposition 1, each outcome of $d_{ij}$ can be converted to $\xi ij\left(h\right),h=1,2,...,H$. the value of the first n paths $Z^n$ is ${\sum }_{x=h}^H{\xi }_{ij}\left(x\right)$ because the first n paths contain those paths i -> $j_H$, i -> $j_{H-1}$,..., i -> $j_h$. Since ${\xi }_{ij}\left(x\right),x=h,h+1,...,H$ are discrete variables taking finite possible values, the probability of $P\{Z^n=k\}$ can be computed by summing up those corresponding probabilities over all outcomes T on ${\sum }_{x=h}^H{\xi }_{ij}\left(x\right)=k$, which is $P\{Z_{ij}^n=k\}={\sum }_{T}P\{{\sum }_{x=h}^H{\xi }_{ij}\left(x\right)=k\}$.    □

Proposition 2 provides an efficient approach to obtain the total capacity of the first n paths, $Z_{ij}^n$. Let us demonstrate the calculation using $Z_{ij}^2$. Since the possible values of $Z_{ij}^2$ are taken from ${\xi }_{ij}\left(4\right)+{\xi }_{ij}\left(3\right)$, it means $Z_{ij}^2$ can take the values of 1 or 2, and the probability of $Z_{ij}^2$ taking the value of 1 is the sum of all corresponding probabilities where ${\xi }_{ij}\left(4\right)+{\xi }_{ij}\left(3\right)=1$, which are $0.1$, $0.3$, and $0.4$. The calculation is the same for $Z_{ij}^2$, taking the value of 2, which is $0.2$.

Table 4. Results of the total capacity of the first n paths.

n	Paths Included	Distribution of ${\mathit{Z}}_{\mathit{ij}}^{\mathit{n}}$
1	$P_1$	$\left\{\right(0,0.1),(1,0.7),(2,0.2\left)\right\}$
2	$P_1,P_2$	$\left\{\right(1,0.8),(2,0.2\left)\right\}$
3	$P_1,P_2,P_3$	$\left\{\right(1,0.4),(2,0.6\left)\right\}$
4	$P_1,P_2,P_3,P_4$	$\left\{\right(1,0.1),(2,0.7),(3,0.2\left)\right\}$

shows the results of $Z_{ij}^n$ in the example shown in Table 3.

With Proposition 2, we can obtain the first n paths’ total capacity $Z_{ij}^n$ efficiently for a nodal tree rooted at node $i\in \mathcal{N}$ with leaf nodes $j_h\in \mathcal{N},h=1,2,...,H$, even though these paths’ random capacities are not independent. It extends the one introduced by Powell and Cheung [38], where their algorithm is restricted by the condition that all random arc capacities are mutually independent. However, the approach in Proposition 2 can only apply to computing the total capacities of the first n paths for a single leaf node. Since a single-root-node recourse problem generally contains multiple leaf nodes, we state an approach in Proposition 3 to compute a nodal tree rooted at node $i\in \mathcal{N}$ with multiple leaf nodes $j\in \mathcal{N}$. To ease our presentation, we present this recourse problem with two leaf nodes $j\in \mathcal{N}$ and $k\in \mathcal{N}$, which relates to passenger demands $d_{ij}$ and $d_{ik}$. It is worth noting that this is not a limitation of our approach.

Proposition 3. 

Assume a nodal tree $T_i$ rooted at node $i\in \mathcal{N}$ contains two leaf nodes $j\in \mathcal{N}$ and $k\in \mathcal{N}$. Duplicating leaf nodes j and k $H-1$ times, respectively, creates two new nodal subtrees $T_{ij}$ and $T_{ij}$ rooted at node i with $2H$ paths and leaf nodes $j_h,h=1,2,...,H$ and $k_h,h=1,2,...,H$, respectively. Assume all paths in $T_i$ have been sorted in descending order by their revenue $r_{ij}\left(h\right)$ and $r_{ik}\left(h\right)$, where $h=1,2,...,H$, and the first n paths contain paths i -> $j_H$,i -> $j_{H-1}$,...,i -> $j_{h1}$ and i -> $k_H$,i -> $k_{H-1}$,...,i -> $k_{h2}$, such that the total capacities of the first n paths $Z_i^n$ can be obtained by $Z_i^n=Z_{ij}^{h1}+Z_{ik}^{h2}$.

Proof. 

For the nodal subtree $T_{ij}$ rooted in node $i\in \mathcal{N}$ destined to leaf nodes $j_h,h=1,2,...,H$ where all paths have been ranked by their revenue in descending order, if the first n paths contain i -> $j_H$, i -> $j_{H-1}$,..., i -> $j_{h1}$, the total capacity of these paths is $Z_{ij}^{h1}$. It is the same for the nodal subtree $T_{ik}$ rooted at node $i\in \mathcal{N}$ destined to leaf nodes $k_h,h=1,2,...,H$. if the first n paths contain i -> $k_H$, i -> $k_{H-1}$,..., i -> $k_{h2}$, then the total capacity of these paths is $Z_{ik}^{h2}$. Since passengers’ demands $d_{ij}$ and $d_{ik}$ are independent, it means $Z_{ij}^{h1}$ and $Z_{ik}^{h2}$ are also independent. As a result, $Z_i^n=Z_{ij}^{h1}+Z_{ik}^{h2}$.    □

A general single-root-node, multiple-leaf-node network recourse problem can be converted to a general nodal tree structure, and Proposition 3 provides an efficient way to compute the total capacity of the first n paths $Z_i^n$ for a general nodal tree recourse problem. To ensure feasibility, a common technique is adding a virtual uncapacitated path with zero revenue into the nodal tree, representing that the service provider can hold as many vehicles at transit points $i\in \mathcal{N}$ but generate no revenue. Since this virtual path is uncapacitated, we need to calculate the total capacities of all sorted paths from the first path until reaching the virtual one. Furthermore, in our general single-root-node recourse problem, since the fleet size is a decision variable, the terminate criteria in computing $G_i\left(k\right)$ can be set to $G_i\left(k\right)\le 0$. The rationale behind this setting is that the $v_i>k$ vehicles at transit point $i\in \mathcal{N}$ can only generate zero revenue.

A complete but simple example to demonstrate the whole computation process is presented in the following. Suppose a single-root-node recourse problem with a root node i and two leaf nodes j and k. Passenger demands $d_{ij}$ and $d_{ij}$ are discrete random variables that take on two possible values each, which are $\left\{\right(5,0.4),(7,0.6\left)\right\}$ and $\left\{\right(7,0.3),(8,0.7\left)\right\}$, respectively. Fares $f_{ij}$ and $f_{ik}$ are 4 and 5. Vehicle traversing costs $c_{ij}$ and $c_{ik}$ are 7 and 8. Assume the vehicle capacity $H=4$. We first convert the passenger demands to vehicle demands, shown in

Table 5. Convert passenger demand $d_{ij}$ to vehicle demand ${\xi }_{ij}$.

Possible Value of  ${\mathit{d}}_{\mathit{ij}}$	Corresponding Probability	Path Capacities ${\mathit{\xi }}_{\mathit{ij}}\left(\mathit{h}\right)$
		${\mathit{P}}_{\mathbf{1}}^{\mathit{j}}$	${\mathit{P}}_{\mathbf{2}}^{\mathit{j}}$	${\mathit{P}}_{\mathbf{3}}^{\mathit{j}}$	${\mathit{P}}_{\mathbf{4}}^{\mathit{j}}$
		${\mathit{\xi }}_{\mathit{ij}}\left(\mathbf{4}\right)$	${\mathit{\xi }}_{\mathit{ij}}\left(\mathbf{3}\right)$	${\mathit{\xi }}_{\mathit{ij}}\left(\mathbf{2}\right)$	${\mathit{\xi }}_{\mathit{ij}}\left(\mathbf{1}\right)$
5	0.4	1	0	0	1
7	0.6	1	1	0	0

and 

Table 6. Convert passenger demand $d_{ik}$ to vehicle demand ${\xi }_{ik}$.

Possible Value of  ${\mathit{d}}_{\mathit{ij}}$	Corresponding Probability	Path Capacities ${\mathit{\xi }}_{\mathit{ik}}\left(\mathit{h}\right)$
		${\mathit{P}}_{\mathbf{1}}^{\mathit{k}}$	${\mathit{P}}_{\mathbf{2}}^{\mathit{k}}$	${\mathit{P}}_{\mathbf{3}}^{\mathit{k}}$	${\mathit{P}}_{\mathbf{4}}^{\mathit{k}}$
		${\mathit{\xi }}_{\mathit{ik}}\left(\mathbf{4}\right)$	${\mathit{\xi }}_{\mathit{ik}}\left(\mathbf{3}\right)$	${\mathit{\xi }}_{\mathit{ik}}\left(\mathbf{2}\right)$	${\mathit{\xi }}_{\mathit{ik}}\left(\mathbf{1}\right)$
7	0.3	1	1	0	0
8	0.7	2	0	0	0

.

Next, we compute the path revenue $r_{ij}\left(h\right)$, $r_{ik}\left(h\right)$, and the first n paths’ total capacities $Z_{ij}^n$, $Z_{ik}^n$, where $h=1,2,3,4$. Results are shown in

Table 7. Path revenue $r_{ij}\left(h\right)$ and the first n paths’ total capacity $Z_{ij}^n$ for nodal subtree $T_{ij}$.

n	Path Revenue	Distribution of ${\mathit{Z}}_{\mathit{ij}}^{\mathit{n}}$
1	9	$\left\{\right(1,1.0\left)\right\}$
2	5	$\left\{\right(1,0.4),(2,0.6\left)\right\}$
3	1	$\left\{\right(1,0.4),(2,0.6\left)\right\}$
4	−3	$\left\{\right(2,1.0\left)\right\}$

and 

Table 8. Path revenue $r_{ik}\left(h\right)$ and the first n paths’ total capacity $Z_{ik}^n$ for nodal subtree $T_{ik}$.

n	Path Revenue	Distribution of ${\mathit{Z}}_{\mathit{ik}}^{\mathit{n}}$
1	12	$\left\{\right(1,0.3),(2,0.7\left)\right\}$
2	7	$\left\{\right(2,1.0\left)\right\}$
3	2	$\left\{\right(2,1.0\left)\right\}$
4	−3	$\left\{\right(2,1.0\left)\right\}$

.

Finally, we add a virtual path to this nodal tree, where the path capacity is ∞ and the path revenue is 0. We sort all paths according to their revenue, and the resulting nodal tree is depicted in Figure 8.

With the sorted nodal tree, we can calculate the first n paths’ total capacity $Z^n$ according to Proposition 3. The results are shown in

Table 9. Path revenue $r_i\left(n\right)$ and the total capacity of the first n paths for nodal tree $T_i$.

n	Path Revenue ${\mathit{r}}_{\mathit{n}}$	Computation of ${\mathit{Z}}^{\mathit{n}}$	Distribution of ${\mathit{Z}}^{\mathit{n}}$
1	12	$=Z_{ik}^1$	$\left\{\right(1,0.3),(2,0.7\left)\right\}$
2	9	$=Z_{ik}^1+Z_{ij}^1$	$\left\{\right(2,0.3),(3,0.7\left)\right\}$
3	7	$=Z_{ij}^1+Z_{ik}^2$	$\left\{\right(3,1.0\left)\right\}$
4	5	$=Z_{ik}^2+Z_{ij}^2$	$\left\{\right(3,0.4),(4,0.6\left)\right\}$
5	2	$=Z_{ik}^3+Z_{ij}^2$	$\left\{\right(3,0.4),(4,0.6\left)\right\}$
6	1	$=Z_{ik}^3+Z_{ij}^3$	$\left\{\right(3,0.4),(4,0.6\left)\right\}$
7	0	Terminate	$\left\{\right(\infty ,1.0)$}

.

Based on the total capacity of the first n paths, we can compute the routing probability $\varphi (k,n)$ by equation $\varphi (k,n)=P\{(Z^n\ge k\}-P\{Z^{n-1}\ge k\}$. $Z^0=0$ since it means no path in the nodal tree. The results of $\varphi (k,n)$ are shown in

Table 10. Results of ${\varphi }_i(k,n)$ and $G_i\left(k\right)$ for nodal tree $T_i$.

	${\mathit{\varphi }}_{\mathit{i}}(\mathit{k},\mathit{n})$							Value of
k	n = 1	2	3	4	5	6	7	${\mathit{G}}_{\mathit{i}}\left(\mathit{k}\right)={\mathit{r}}_{\mathit{n}}·{\mathit{\varphi }}_{\mathit{i}}(\mathit{k},\mathit{n})$
1	1.0	-	-	-	-	-	-	12.0
2	0.7	0.3	-	-	-	-	-	11.1
3	-	0.7	0.3	-	-	-	-	8.4
4	-	-	-	0.6	-	-	0.4	3.0
5	-	-	-	-	-	-	1.0	0.0

, and we terminate these computations when $G\left(k\right)\le 0$.

The pseudo-code for obtaining $\widehat{Q}\left(v_i\right)$, which we call the Nodal Tree Recourse with Dependent Arc Capacities (NTRDAC) Algorithm 1, is outlined as follows.

Algorithm 1: NTRDAC algorithm for a nodal tree $T_i$ rooted at node $i\in \mathcal{N}$.

Step 1: Set $n=0$; $h_N=0$; $Z^n=(0,1.0)$; Step 2: Convert $d_{ij}$ into ${\xi }_{ij}\left(h\right),j\in \mathcal{N},h=1,2,...,H$ by Equation (15); Step 3: Compute $Z_{ij}^h,j\in \mathcal{N},h=1,2,...,H$ by Proposition 2; Step 4: Set $n=n+1$; Step 5:    Set $h_j=$ index of the last path in nodal subtree $T_{ij}$ included            by the first n paths of nodal tree $T_n$, where $j\in \mathcal{N}.$ Step 6:    Compute $Z^n$ by Proposition 3 where $Z^n={\sum }_{x\in h_j,j\in \mathcal{N}}{Z}_{ij}^x$; Step 7: Repeat step 4 to step 6 until reaching the uncapacitated path; Step 8: Compute $\varphi (s,n)$ using Equation (12); Step 9: Compute $G_i\left(k\right)$ by Equation (13) until $G_i\left(k\right)\le 0$.

4.4. First-Stage Problem

The NTRDAC algorithm enables us to obtain the exact value of $E_{\omega }{Q}_i(v_i,\mathit{D}\left(\omega \right))$ efficiently by a function $\widehat{Q}\left(v_i\right)$, where $v_i$ is the scalar supplies (vehicles) to the transit point $i\in \mathcal{N}$. Equation (14) states that $\widehat{Q}\left(v_i\right)={\sum }_{k=1}^{v_i}G\left(k\right)$, such that the first-stage problem can be turned into a deterministic mixed integer programming (MIP) optimization problem by replacing $E_{\omega }{Q}_i(v_i,\mathit{D}\left(\omega \right))$ with $\widehat{Q}\left(v_i\right)$.

Let us define $y_i^k=$ the number of vehicles dispatched at transit point $i\in \mathcal{N}$ taking path k (decision variables).

The first-stage problem can be reformulated as follows:

$$\begin{array}{c}\hfill max-g·s+\sum _{i=1}^N\sum _{k=1}^{v_i}{y}_i^k·G_i\left(k\right),\end{array}$$

(16)

subject to

$$\begin{array}{c}\hfill \sum _{i=1}^N{v}_i=s,\end{array}$$

(17)

$$\begin{array}{c}\hfill 0\le y_i^k\le 1,\forall i\in \mathcal{N},k=1,2,...,v_i,\end{array}$$

(18)

$$\begin{array}{c}\hfill s\ge 0,s\in \mathbb{Z}.\end{array}$$

(19)

The first-stage problem (16)–(19) is a common deterministic MIP problem that can be solved efficiently by commercial solvers, such as Cplex 12.6 or Gurobi 10.0.

5. Numerical Experiments

In this section, we conduct numerical experiments to evaluate the efficiency of the NTRDACA algorithm by reporting its CPU time for several test problems of different sizes. Afterward, to assess the value of the stochastic solution (VSS), we compare the results obtained by the decomposition method with those achieved by solving expected value models that replace all random variables with their expected values. All experiments are conducted on a DELL personal computer with an Intel Core i3-6100 CPU and 12 GB RAM. The program is coded in Java 8, and the heap space limitation is set to 700 MB.

5.1. The Efficiency of NTRDAC Algorithm

We evaluated the speed of the NTRDAC algorithm for six different sizes of problem. Three parameters determine the scale of these problems: (i) total number of transit points M, (ii) number of possible values that random arc capacities take on K, and (iii) total number of available seats per vehicle H. The total number of paths, calculated by $M·(M-1)$, is the critical factor affecting the computation time because the number of scenarios is calculated by $K^{M·(M-1)}$, which will increase exponentially as M increases. For the random capacity of each arc, we truncate a Poisson variable $\xi$ at k if k is the largest integer such that $P\{\xi \ge k\}<0.0001$. The Poisson variables’ means range from 3 to 20, with each arc taking a random value. We simulate each test case 10 times and report the average CPU time.

Table 11. Efficiency of NTRDAC algorithm for recourse problems.

Problems					CPU Time (s)
Test Case	No. of Nodes	No. of Possible Values	Total Scenarios	NTRDAC Algorithm	Gurobi (DEP)
1	3	3	729	0.001	13.62
2	4	2	4096	0.001	345
3	5	2	$2^{20}$	0.004	–
4	10	5	$5^{190}$	0.018	–
5	15	10	${10}^{210}$	0.054	–
6	30	15	${15}^{870}$	0.915	–

The symbol “–” indicates an error due to a Java heap size overflow.

summarizes the CPU times and problem settings.

Table 11 shows that our proposed NTRDAC algorithm performs quite well, especially for real-world large-scale problems. First, it can obtain the exact value of the recourse problems as the numeration process does. Second, it can achieve the results quickly and be stable even though the scenarios increase exponentially. Finally, in the last test case, with 30 nodes and 15 possible values of each arc capacity, resulting in ${15}^{870}$ scenarios, our NTRDAC algorithm can still achieve the expected value in less than one second. In real-world applications, a shuttle service transportation network with 30 transit points typically covers most areas within a city. The ability to efficiently solve such a large-scale problem demonstrates that the NTRDAC algorithm is suitable for practical use. In contrast, when using a commercial solver like Gurobi to tackle the same problem, solutions can only be obtained for much smaller instances—those with fewer than five nodes and each random variable taking three possible values. This highlights the curse of dimensionality, where the problem size grows exponentially with the square of the number of nodes in this model.

5.2. The Value of Stochastic Solutions (VSSs)

In this subsection, we aim to evaluate the value of the stochastic solution (VSS). All arc capacities are generated with truncated Poisson random variables as we did in Section 5.1. We vary the number of nodes and cost matrix to generate different test cases. For each test case, we first use the NTRDAC algorithm to obtain the exact value of the recourse functions for the second-stage problem, then we solve the first-stage problem and obtain the solution $S_{Decom}^1$ for the first stage. After that, we replace the random arc capacities with their expected values in the second stage, then we solve the deterministic equivalent problem and obtain the expected value solution $S_{EV}^1$ for the first stage. Taking these two different solutions for the first-stage problem, which is the fleet size $S_{Decom}^1$ and $S_{EV}^1$, we apply the Monte Carlo simulation method for the second stage. That is, we randomly pick one of the values of arc capacities for all arcs in the second stage, which creates a scenario. For each scenario, we solve this deterministic network flow problem and obtain the expected total revenue $R_{Decom}^2$ and $R_{EV}^2$ corresponding to having $S_{Decom}^1$ and $S_{EV}^1$ vehicles, respectively. Comparing $-g·S_{Decom}^1+R_{Decom}^2$ with $-g·S_{EV}^1+R_{EV}^2$, we achieve the value of the stochastic solution. We take 1000 scenarios in each simulation.

Table 12. Results of the value of stochastic solution.

Problems		EV Solution		Stochastic Solution		VSS
Test Case	No. of Nodes	Fleet Size	Total Revenue	Fleet Size	Total Revenue
1	5	16	455.37	20	495.32	39.95
2	10	88	2791.89	97	2885.35	93.46
3	30	887	29,989.94	912	30,230.29	240.35

shows the test cases and the value of the stochastic solution, where the positive values of VSS indicate that the stochastic solutions are better than the expected value solutions. The reason is stochastic solutions account for the uncertainty in the data and decision-making process, leading to more robust and flexible outcomes.

5.3. Managerial Application

In this section, we focus on the managerial application of the NTRDAC algorithm, which is crucial for practitioners. Specifically, we examine the total expected profit by varying the vehicle capacity H, while keeping the random passenger demands consistent across all test cases. We use synthetic data to simulate the decision-making process for selecting vehicle types and fleet size prior to launching the transportation service. The random passenger demands are generated in the same manner as described in Section 5.1. The results are presented in

Table 13. A comparison of expected profits generated by different types of vehicles for 30 transit points.

Vehicle Capacity $\left(\mathit{H}\right)$	Fleet Size $\left(\mathit{s}\right)$	Expected Total Profit
4	912	30,388.63
6	816	59,698.29
11	628	85,149.58
17	509	86,647.13
33	430	79,292.92
50	313	61,991.54

.

According to the results in Table 13, investments in vehicles with a capacity of 17 yields the highest profit, with a capacity of 11 being the second-best option. This may be due to the fact that the random passenger demands follow a Poisson distribution with means that are close to these vehicle capacities. In practice, the distribution of estimated passenger demands may vary and be more general. The NTRDAC algorithm can easily adapt to any general distribution by approximating them with discrete random variables, taking K possible values. As K increases, the accuracy of the approximation improves.

6. Conclusions

This paper addresses a fleet size optimization problem with uncertain passenger demands over point-to-point shared demand responsive service. We propose a stochastic programming framework to model this problem. The key idea is to obtain the exact value of the expected recourse functions in the second stage. We achieve this through a tailored Nodal Tree Recourse with Dependent Arc Capacities (NTRDAC) algorithm. The NTRDAC algorithm extends the TREC algorithm but relaxes the restrictions that all random arc capacities must be independent. Before applying the efficient NTRDAC algorithm, we introduce a conversion process that converts the random passenger demands to random vehicle demands represented by random arc capacities. This conversion is a critical process in generating the nodal tree. The NTRDAC algorithm simplifies the first-stage problem to a deterministic integer programming problem, which can be solved efficiently. Numerical experiments demonstrate that the NTRDAC algorithm can efficiently obtain the exact value of the recourse functions, indicating that our algorithm is quite suitable for large-scale practical problems. For practitioners, implementing the NTRDAC algorithm for real-world fleet size optimization problems is straightforward. By using random demand estimates from forecasts or historical data, the optimal results can be computed by selecting different vehicle capacities and their corresponding parameters, such as depreciation and trip costs.

Considering homogeneous resources is one limitation of this research, and extending the model to accommodate more complex network structures for realistic problems, such as incorporating multiple types of vehicles and allowing backlogged demands, is a promising direction. A potential research direction could explore how to decompose heterogeneous resources and efficiently manage unfulfilled demands from previous stages.