Queueing Models andService Management
Vol. 5, No. 2, page 1-27, 2022

QMSM
C

PU 2018

A Stochastic Analysis and Price Mechanism of Car/Ride-Share
System Considering Road Congestion
Ayane Nakamura1, Tuan Phung-Duc2,* and Hiroyasu Ando3
Graduate School of Science and Technology
Faculty of Engineering, Information and Systems
University of Tsukuba, Tsukuba, Ibaraki 305-8577, Japan
3
Advanced Institute for Materials Research
Tohoku University, Sendai, Miyagi 980-8577, Japan(Received January 2022 ; accepted July 2022)
1

2

Abstract: In this paper, we discuss Car/Ride-Share (CRS), a novel concept of transportation
service aiming to reduce the uneven distribution of cars in traditional carsharing services andthe congestion of customers and vehicles on the road. We model a scenario where CRS service
is introduced between a spot (e.g., university, company, etc.) and its nearest train station
by a bus company considering the road congestion. We propose an approximation modelthat decomposes the whole complex system into two queueing models (i.e., CRS model andRoad model). The accuracy of the approximation model is verified by extensive simulations.
Based on numerical experiments, we discuss the mean total required time (i.e., the sum of the
waiting time and the traveling time on the road) for the customers for several road congestion
levels, in other words, we discuss the optimal management policy of CRS considering
the road congestion. Interestingly, it is turned out that CRS is always effective from theperspective of the required time in the case where the road is not congested. However, theeffectiveness of CRS differs depending on the arrival rate of the customers in the congested
case; CRS is always ineffective for the low arrival rate, and the optimal occurrence rate of
CRS exists for the high arrival rate. Furthermore, we consider a price mechanism problem thatgives an attractive solution for all the bus company, car providers and customers.
Keywords: Queueing, stochastic processes, traffic, transportation.

1. Introduction
1.1. Background
There are many studies on analysis of transportation systems using mathematical models.
For example, about carsharing, the research on redistribution of the cars and optimization of
the boarding system were conducted in [7, 6]. For ridesharing, the research on drivers andriders matching optimization were conducted in [2, 11].
As the latest studies using queueing theory, Shuang et al. [19, 20] considered a bikesharing queueing model that incorporates the finite capacity at stations [19] and constructed astochastic model of bike-sharing system to show that the entropy of the bike-sharing network
is reduced, and riders experience less blocking in the network if the proportion of customers*Corresponding author
Email : tuan@sk.tsukuba.ac.jp

1

C Nakamura, Phung-Duc and Andothat use smartphone app information increases [20].
When introducing new transportations such as carsharing and ridesharing, it is necessary
to discuss the financial aspect because it is meaningless if they would be too expensive
services. For example, Hampshire et al. [9, 10] considered the sustainability of Peer-to-Peer
carsharing, where people execute carsharing using private cars, and discussed the prices andthe profits of this service by simulation experiments. In addition, various research about theprice mechanism of ridesharing have been extensively conducted. For example, Bimpikis
et al. [5] constructed a model where drivers decide whether and where to provide service
to maximize their expected earnings to discuss spatial pricing and Banerjee et al. [4] used aqueueing model to conduct an equilibrium analysis that captures incentives for both drivers
and passengers.
From a more general perspective on transportation, Daganzo et al. [8] constructed asimple model of demand-responsive transportation services, which includes as special cases
non-shared taxi, dial-a-ride and ridesharing. They also compared the existing urban transportation modes in scenarios involving different city types and levels of demand.
1.2. Outline and previous research of Car/Ride-Share (CRS)
In this paper, we consider Car/Ride-Share (CRS), a new type of shared transportation(see the detailed explanation in Section 2). CRS may be an alternative mean of efficienttransportation for buses or taxis from the perspective of the price and the waiting time andso on. In addition, CRS is expected to have many social impacts such as reducing traffic
stress of customers (i.e., reducing the waiting time), improvement of convenience for transportation and revitalization of society (i.e., feasible at a low price), economic revitalization(i.e., financial benefits for the operators of CRS and the car providers) and reducing the burden on the operators of shared transportation (i.e., solving uneven distribution of cars). We
consider a queueing model of CRS and discuss its effectiveness in this paper.
CRS is defined as a system where people carry out carsharing (i.e., the car rental for
short periods) and ridesharing (e.g., the system where people ride a car together to the destination) simultaneously using private cars. We consider a scenario where a bus company
itself introduces CRS between a train station and its nearest spot (e.g., university, company)
where a bus transportation already exists, and reduces the number of the buses i.e., it enables to secure more rest time for the drivers and may contribute to solve the labor problems
reported in [13]. This CRS system has the following three features [3].
1. Owners of private cars can get financial incentives by sharing their cars.
2. People can carry out carsharing and ridesharing simultaneously so that the disadvantage of conventional carsharing such as uneven distribution of cars does not occur,i.e., the operator does not have to redistribute the cars.
3. It might be an alternative transportation service with less financial and time burden
for existing transportations (bus in this study) in the case of congestion.
About CRS, Ando et al. [3] conducted simulation experiments and showed the decreaseof the mean waiting time for customers. Besides, Nakamura et al. [15, 17, 16] modeled2

Queueing Models and Service Management

CRS between a university and a station where a bus transportation has been existing alreadyusing queueing theory and discussed the characteristics of the system. Furthermore, [17, 16]considered various scenarios of price mechanism of CRS, where a third organization or abus company introduces this service. However, they put several assumptions, for example,
Poisson arrival of buses, the state of the station side is the number of demands of CRS; thebuses from the station are always full because of the congestion and the customers arrive one
by one to simplify the model. Besides, they did not incorporate the state of the road between
the two points to their model, and did not consider the possibility that the occurrences of
CRS cause the road congestion, which is not a good situation for the customers.
Based on the above, we assume the following conditions in our queueing model of CRS
and execute Monte Carlo simulation aiming at a more realistic discussion in this research.
1. Inter-arrivals of buses are independently and identically distributed (I.I.D) according
to Erlang distribution which can be used to approximate the fixed interval (this enables
us to discuss the influence of the uncertainty of the buses to the system by adjusting
the variance of the distribution).
2. We define the state of the station as the number of waiting customers, and do notassume that the buses from the station are always full as in [15, 17, 16].
3. The customers at the station side arrive in groups (image that people got off the train
arrive at all once).
The rest of the paper is structured as follows. In Section 2, we state the system of CRS.
In Section 3, we propose the approximate model of CRS system. In Section 4, we discuss
the price mechanism of CRS, and in Section 5, we show some numerical results. Finally, we
present concluding remarks in Section 6.

2. Car/Ride-Share (CRS) system
This section presents the mechanism of CRS. We consider a scenario in which CRS is
introduced by a bus company between a train station and a spot (e.g., university, companyetc.) where a bus transportation has been exiting already (see Fig. 1). We also assume that
there is the parking lot of the bus company for cars to carry out CRS at the spot side. In
our model, we assume that CRS, which is the system where people carry out carsharing andridesharing simultaneously by using private cars, occurs according to the following procedure (we summarize the parameters used in our model as in Table 1).
As a premise, people who came to the spot by their private cars provide these cars as
CRS car (car) in the morning (i.e., the car providers carry out Car-sharing with the bus company). Car providers can obtain financial incentives in return for lending their cars to thebus company. In this study, we assume that there are enough car providers and do not consider the possibility of the shortage of cars at the spot to carry out CRS. We assume thatthe minimum and the maximum numbers of passengers for a car are m and n, respectively.
Customers can make a group and use these cars together to move between the spot and thestation (i.e., Ride-sharing), but these cars must be returned to the spot.
3

C Nakamura, Phung-Duc and Ando

Figure 1. The schematic illustration of CRS.
At the station, groups (e.g., people who got off a train arrives at all the once) of customers
arrive according to the Poisson process with rate δ and the number of people for a group
follows an arbitrary distribution. We assume that the batch size (i.e., the number of people
in a group) X follows an arbitrary distribution, and write asxk = P(X = k),for k ∈ N.
To make it easier to analyze, we assume that it is acceptable to have up to K people atthe station at the same moment, and if there are already K people at the station side, newvisitors are blocked and go to the spot by other means of transportation, such as a taxi (we set
as large K as possible in numerical experiments). We also assume that if the number of freecapacities is less than the size of the arriving group at the station, the exceeded number ofcustomers are blocked under the assumption that the probability that each person in the groupis blocked is identical. On the spot side, customers arrive according to the Poisson processwith rate λ, and there is no buffer limit. Here, we further assume that all the customers have adriving license and do not have any preferences whether they use the bus or CRS to simplify
the discussion.
Buses depart from the spot (the station) to the station (the spot) at intervals following
Erlang distribution with rate r1(2) and shape q1(2) (this means the sum of q1(2) exponentially4Queueing Models and Service Management

distributed random variables of parameter r1(2) ). We assume that the capacity of a bus is l(note that we assume l > n) and the spot and the station are the first bus stops, i.e., a bus isempty upon arrival. People lined up at the spot continuously get on a bus on a first-come,first-served basis within the limit of the capacity of the bus.
CRS occurs from the spot at intervals following the exponential distribution with a parameter σ when both the spot and the station are congested above a certain level when there
are at least m people on both sides. Here, m is the minimum number of passengers for a car,as mentioned above. That means CRS occurs only when there are more than a certain number of passengers at both spots, i.e., CRS occurs depending on the states of the number ofpassengers at both the station and the spot. The time for the occurrence of a CRS is a randomvariable mainly due to the assumption that the operator of CRS controls the occurrences of
CRS one by one through a system, including a web application on a smartphone of users.
Hence, we assume that the CRS service is modeled as to a single server because the operator
controls the matching of CRS one by one in such a manner that the matched customers at
the spot still have an option to take a bus during the matching time. In addition, the matchedcustomers at both places leave the queue for buses and move to the free space for CRS upon
the completion of the matching and prepare to drive the car by one of these customers. Asa reason to assume the exponential distribution of the parameter σ, it is also considered thatthe time it takes for a group of passengers at the spot to arrive at the parking lot of cars fromthe free space of CRS and start driving changes depending on the situation, i.e., the locationof cars in the parking lot at the spot and the characteristics of customers. In the same way as
buses, people get on a car on a first-come, first-served basis within the limit of the capacity.
A car departing at the spot goes to the station, and after arriving at the station, those in the
car get off. Then, people waiting at the station take over the car and drive the CRS to the
spot. After the car reaches at the spot, people who ride on at the station get off and the car isreturned to its original position.
The movement on the road between two points is modeled as shown in Fig. 2 following
Vandaele et al. [21]. In this method, a part of the road between two points is considered aservice station (i.e., a single-server queue), and the service interval follows an exponential
distribution of the parameter β. The parameter β of this exponential distribution is derived
as β (number of vehicles / unit time) = SN (km / unit time) M (number of vehicles / km).
In reality, the service time distribution can be different from the exponential distribution,
but we adopt this assumption validated in [21] for the simplicity. We also assume that othervehicles (defined as general vehicles) except for the buses and CRS cars arrive at the service
station according to a Poisson process with parameter ϵus(su) .
Using the mean sojourn time in the system, the maximum traffic density of the road M(the inverse of M is considered to be the size of the service station), and the distance of theroad between the two points d, we can derive the relative speed of the vehicle on the roadsus(su) (see [21] for details). Then, we can determine the travel time required for the vehicles
on the road using sus(su) .
To summarize, the car providers share their car with other people (i.e., carsharing), andthe customers ride on the cars together (i.e., ridesharing). In other words, CRS is considered5C Nakamura, Phung-Duc and Ando

Figure 2. The schematic illustration of the modelling of the road.
as a hybrid system of carsharing and ridesharing. In this CRS system, the demands for people
who want to go to the station from the spot and the opposite one are satisfied simultaneously
under the condition that the car is returned to the spot within a certain time, i.e., uneven
distribution of cars does not occur. This CRS system may be an alternative transportationand may reduce the waiting time of customers under a situation (e.g., commuting hours in themorning) where there are not enough buses for arriving customers (we show some numericalresults about this in Section 5). Also, the owners of the cars can make money by lending
their cars to cover the cost of gasoline. It is possible to set the fee lower compared to taxi
from the customer’s perspective (we consider the price mechanism in Section 4).

3. Modelling of Car/Ride-Share (CRS)This section presents the queueing model of CRS and its analysis. The CRS system explained in the previous section is a system on a network. Furthermore, although we consider
modelling only between two points in this paper, the actual system of a multi-point model
may become even more complicated. Concretely, the difficulty of our model is how to accurately grasp the arrival processes at the service stations. That is because there are three typesof vehicles (i.e., buses, CRS cars, general cars). Therefore, it becomes a high-dimensional
queueing model. Besides, the arrival process of the service station at the road from the station to the spot depends on the traveling time it takes for CRS cars to move from the spot tothe station (Note that people always have to take over the cars at the station side and thosecars should be returned at the parking lot at the spot side). Therefore, we have to keep trackof the traveling time of each CRS in the model. However, the traveling time is a constantvalue determined from the effective speed and the distance between the spot and the station.
As a result, it is not easy to model the entire system as a Markovian queueing network model.
Besides, the simulation of the model takes a long time.
Based on the above, we present an approximate method. We break down the system
6

Queueing Models and Service Management

Table 1. The parameters used in the CRS system.
Parameters
Definitionsλ (people/h)Arrival rate of customers at the spot.
σ (veh/h)Occurrence rate of CRS.
δ (group/h)
Arrival rate of a group of customers at the station.
q1(2) , r1(2)Shape and rate parameters of Erlang distribution forthe departure interval of buses from the spot (station).
l (people)
Capacity of buses.
m (people)
Minimum number of passengers of cars.
n (people)
Maximum number of passengers of cars.
K (people)
Maximum number of customers that can exist at the station.
M (veh/km)
Maximum traffic density.
ϵus(su) (veh/h)
Arrival rate of general cars at the service station from the spot
to the station (from the station to the spot).
αus(su) (veh/h) Total arrival rate at the service station on the road from the
spot to the station (from the station to the spot). → in Section 3.2
β (veh/h)Service rate at the service stations.
SN (km/h)
Nominal speed of cars.
d (km)
Distance between the spot and the station.
sus (km/h)
Effective speed of cars on the road from the spot to the station.
ssu (km/h)
Effective speed of cars on the road from the station to the spot.
into two parts, CRS model and Road model. We then use the outputs of the CRS model toapproximate the arrival processes to the Road model. These two models are explained asfollows:
3.1. CRS modelCRS model expresses the number of waiting customers at queues for buses at both places.
It should be noted that the number of occurrences of CRS does not depend on the state of theroad. CRS occurs depending on the number of waiting customers (CRS can occur if there
are m or more customers at both places). Besides, once the matching of customers at both
places for CRS is completed, the customers leave the queue and move to the free space for
CRS even before the actual departure. Therefore, if we want to only know the number ofthe occurrences of CRS per unit time and the throughput of customers, it is possible obtainfrom only the CRS model without the road condition. Fig. 2 shows the flow of CRS model.
The CRS system can be modelled using a GI/M/1-type Markov chain where the numberof customers on the spot side is the level and other elements (i.e., phase of Erlang distributions and the number of customers at the station) are included as the phase. That is because customers arrive at the spot one by one, but they are served in batch (i.e., by buses
or CRS). We show the analysis on the model following a matrix geometric approach. Let
Z+ , I, R1 , R2 , and S denote Z+ = {0, 1, 2, . . . }, I = {0, 1, 2, . . . , K}, R1 = {0, 1, 2, . . . , r1 −7

C Nakamura, Phung-Duc and Ando1}, R2 = {0, 1, 2, . . . , r2 − 1} and S = Z+ × I × R1 × R2 , respectively. Therefore, we canrewrite S as follows.
S = {(j, ξ, ψ, ω)|j ∈ Z+ , ξ ∈ I, ψ ∈ R1 , ω ∈ R2 }Then let N (t), I(t), R1 (t), and R2 (t) express the number of the waiting people at thespot, the number of the waiting people at the station, the progress of the Erlang distribution
for the buses from the spot and that for the buses from the station at time t, respectively. It
is easy to see that {N (t), I(t), R1 (t), R2 (t)); t ≥ 0} forms a Markov chain in the state space
S. Our Markov chain is of GI/M/1-type, where N (t) is the level and {(I(t), R1 (t), R2 (t))}
is the phase. Besides, we define Lk (k = 0, 1, 2 . . .) as follows.
Lk = {(j, ξ, ψ, ω)|j = k, ξ ∈ I, ψ ∈ R1 , ω ∈ R2 }.

Lk stands for a set of all states when the level is k.
The infinitesimal generator Q of our Markov chain is given as follows.
L0
B0,0
 
 C
L1

 C

L2

..
 ..
 .
.


Lm−1 
 C

Lm
 B

Lm+1 
 B
..
 ..
 .
.

 B
Ln


Ln+1 
 C
Ln+2 
C

..
 .
.
 ..
 
Ll−n 
 C 
Ll−n+1  C
 .
..
 ..
.

 C
Ll
 

Ll+1  O
Ll+2 
 O
..
..
.
.


L0

Q=

L1
A0

B

L3
O

O
..
.
O

A0

B
...

O
O
..
.

O
O
..
.

O
C

O
O

O
..
.

C
...
O

O
O
..
.
O

C
O
..
.

O

O
...
O
O

C
..
.

...
...
...
...
...
...

Lm−1
O

Lm
O

Lm+1
O

...
...

Ln
O

Ln+1
O

Ln+2
O

...
...

Ll−n
O

Ll−n+1
O

...
...

Ll
O

Ll+1
O

Ll+2
O

O
O
...
A0

O
O
...
O

O
O
..
.
O

...
...
..
.
...

O
O
...
O

O
O
..
.
O

...
...
...
...

O
O
..
.
O

O
O
..
.
O

O
O
..
.
O

O
O
...
O
O

C0
O
...
O
O

A0
C0
...
O
O

... O
... O
..
...
.
... O
...
O
...
O
... ...
...
C0
... O

O
O
..
.
O

...
...
...
...
...
...
...

O
O
...

B

O
O
...
A0
C0

O
O
...
O
A0

O
O
...
O
O

O
O
...
O
O

O
O
...
O
O

O
O
...
O
O

O
...
...
...
...

O
...
...
...
...

C0
...
...
...

O
...
A0

O
...
O

O
...
O

O
...
O

...
...

O
...
...
...
...

O
...
C0

...

O
...
...
...
...

...
...
...
...
...
...
...

O
O
...
O
O

O
...
...
...
...

...
...
...
...
...
...
...
...

C0
...

...
...

O
O

O
O

O
O

...
...

O
O

O
O

O
O

...

O
...
C
O

O
C

...
...
...

O
...
C0
O

O
...
A0
C0

O
...
O
A0

...
...

O
...

O
...

O
...

...
...

O
...

O
...

O
...

...
...

O
...

O
...

...

O
...

O
...

C0
...

...

...
...

...
...
...

...

...
...
...

...
...

...

...

...

...

...


...

...


...

...


...

...

...


...


...

...


...

...


...
... 


... 

...

.

The block matrices stored in Q are (K + 1)r1 r2 order square matrices, and O is a zeromatrix. Letus denote the contents of block matrices where each element of A0 iswritten as
A0 = 


A0,(0,0,0),(0,0,0)

A0,(0,0,0),(0,0,1)

A0,(0,0,0),(0,0,2)

A0,(0,0,1),(0,0,0)

A0,(0,0,1),(0,0,1)

A0,(0,0,1),(0,0,2)

A0,(0,0,2),(0,0,0)..
.

A0,(0,0,2),(0,0,1)...

A0,(0,0,2),(0,0,2)...

A0,(K,r1 −1,r2 −1),(0,0,0) A0,(K,r1 −1,r2 −1),(0,0,1) A0,(K,r1 −1,r2 −1),(0,0,2)

...

...

...

...

A0,(0,0,0),(K,r1 −1,r2 −1)
A0,(0,0,1),(K,r1 −1,r2 −1)

A0,(0,0,2),(K,r1 −1,r2 −1)..
.
A0,(K,r1 −1,r2 −1),(K,r1 −1,r2 −1)





,




and the same is true for other matrices.
A0 is the matrix that summarizes all the rates that the number of people waiting at the
spot increases by one, thus the contents can be defined as follows.
A0,(ξ,ψ,ω),(ξ,ψ,ω) = λ.
Here, the elements that are not specifically defined are 0 (the same applies thereafter).
 is the matrix that summarizes all the rates that people waiting at the spot are servedCby the bus when 1 ≦ j ≦ m − 1, n + 1 ≦ j, thus the contents can be defined as follows.
8

(ξ,r −1,ω),(ξ,0,ω) = q1 .
C
1Queueing Models and Service Management

Figure 3. The flow of the CRS model.
C is the matrix that summarizes all the rates that people waiting at the spot are served
by CRS when n + 1 ≦ j, thus the contents can be defined as follows.
n ≦ ξ,C (ξ,ψ,ω),(ξ−n,ψ,ω) = σ,C (ξ,ψ,ω),(0,ψ,ω) = σ,m ≦ ξ ≦ n − 1.

B is the matrix that summarizes all the rates that people waiting at the spot are servedby the bus and CRS when m ≦ j ≦ n, thus the contents can be defined as follows.
B (ξ,ψ−1,ω),(ξ,0,ω) = q1 ,n ≦ ξ,B (ξ,ψ,ω),(ξ−n,ψ,ω) = σ,B (ξ,ψ,ω),(0,ψ,ω) = σ,m ≦ ξ ≦ n − 1.

B(0,0) is the matrix that summarizes the rates for the progress of two Erlang distributions,the rates for the arrival of the buses at both sides, and the rates for the batch arrival of people
at the station. Also, we define the diagonal elements properly so that the row sum of theinfinitesimal generator Q equals to 0 (to be the same afterward). Thus, each element can be
written as follows.
B(0,0),(ξ,ψ,ω),(ξ,ψ+1,ω) = q1 ,0 ≦ ψ ≦ r1 − 2,

B(0,0),(ξ,ψ,ω),(ξ,ψ,ω+1) = q2 ,0 ≦ ω ≦ r2 − 2,

B(0,0),(ξ,r1 −1,ω),(ξ,0,ω) = q1 ,B(0,0),(ξ,ψ,r2 −1),(ξ−l,ψ,0) = q2 ,l ≦ ξ,
9

C Nakamura, Phung-Duc and Ando

B(0,0),(ξ,ψ,r2 −1),(0,ψ,0) = q2 (1 − δξ,0 ),ξ + 1 ≦ ξ ′ ≦ K − 1,

B(0,0),(ξ,ψ,ω),(ξ′ ,ψ,ω) = δxξ′ −ξ ,B(0,0),(ξ,ψ,ω),(K,ψ,ω) = δ∞

0 ≦ ξ ≦ K − 1,

xk ,

k=K−ξ

B(0,0),(ξ,ψ,ω),(ξ,ψ,ω) = −(ξ ≦ − 1,B(0,0),(ξ,ψ,ω),(ξ′ ,ψ′ ,ω′ ) + λ).

(ξ ′ ,ψ ′ ,ω ′ )∈I×R1 ×R2(ξ ′ ,ψ ′ ,ω ′ )̸=(ξ,ψ,ω)B(k,k) and C0 are the matrices that summarize the rates for the progress of two Erlang
distributions, the rates for the bus arrival at the station and the rate for the batch arrival ofpeople at the station. Thus, each element can be written as follows.
B(k,k),(ξ,ψ,ω),(ξ,ψ+1,ω) = q1 ,0 ≦ ψ ≦ r1 − 2,B(k,k),(ξ,ψ,ω),(ξ,ψ,ω+1) = q2 ,0 ≦ ω ≦ r2 − 2,l ≦ ξ,

B(k,k),(ξ,ψ,r2 −1),(ξ−l,ψ,0) = q2 ,B(k,k),(ξ,ψ,r2 −1),(0,ψ,0) = q2 (1 − δξ,0 ),ξ + 1 ≦ ξ ′ ≦ K − 1,

B(k,k),(ξ,ψ,ω),(ξ′ ,ψ,ω) = δxξ′ −ξ ,B(k,k),(ξ,ψ,ω),(K,ψ,ω) = δ∞

0 ≦ ξ ≦ K − 1,

xk ,

k=K−ξ

B(k,k),(ξ,ψ,ω),(ξ,ψ,ω) = −(B(k,k),(ξ,ψ,ω),(ξ′ ,ψ′ ,ω′ )(ξ ′ ,ψ ′ ,ω ′ )∈I×R1 ×R2(ξ ′ ,ψ ′ ,ω ′ )̸=(ξ,ψ,ω)+(ξ ′ ,ψ ′ ,ω ′ )∈I×R1 ×R2

0 ≦ ω ≦ r2 − 2,

C0,(ξ,ψ,ω),(ξ,ψ,ω+1) = q2 ,C0,(ξ,ψ,r2 −1),(ξ−l,ψ,0) = q2 ,C0,(ξ,ψ,r2 −1),(0,ψ,0) = q2 (1 − δξ,0 ),C0,(ξ,ψ,ω),(K,ψ,ω) = δ

k=K−ξl ≦ ξ,ξ ≦ l − 1,

ξ + 1 ≦ ξ ′ ≦ K − 1,

C0,(ξ,ψ,ω),(ξ′ ,ψ,ω) = δxξ′ −ξ ,∞
C−l,(ξ,ψ,ω),(ξ′ ,ψ′ ,ω′ ) + λ),0 ≦ ψ ≦ r1 − 2,

C0,(ξ,ψ,ω),(ξ,ψ+1,ω) = q1 ,10

ξ ≦ l − 1,xk ,0 ≦ ξ ≦ K − 1,

Queueing Models and Service Management

C0,(ξ,ψ,ω),(ξ,ψ,ω) = −(C0,(ξ,ψ,ω),(ξ′ ,ψ′ ,ω′ )(ξ ′ ,ψ ′ ,ω ′ )∈I×R1 ×R2(ξ ′ ,ψ ′ ,ω ′ )̸=(ξ,ψ,ω)+

B(k,0),(ξ,ψ,ω),(ξ′ ,ψ′ ,ω′ ) + λ).

(ξ ′ ,ψ ′ ,ω ′ )∈I×R1 ×R2Then, we derive the stability condition for the existence of the steady state probability. In
our model, this condition is considered the condition that the number of customers waitingat the spot does not diverge. We define the infinitesimal generator A of the phase as follows.

A = A0 + C0 + C + C.

Assuming that the steady state probability of the phase (the number of demands at the stationand the phase of Erlang distributions) is η = (η(0,0,1) , η(0,0,2) , . . . , η(K,r1 −1,r2 −1) ), we haveηA = 0,(1)ηe = 1,(2)where 0 is a vector of zeros and e is a vertical vector of ones with an appropriate size,
respectively.
Using the probability η, we can consider that the rates at which the level (the number of respectively. Furthermore,customers at the spot) decreasing by n and l are ηCe and η Ce,
the rate increase the level by 1 is ηA0 e (see e.g., [1, 12]). Therefore, the stability conditionis expressed as follows:⇐⇒ λ < lq1

 + nηCe
ηA0 e < lη Ce



ξ∈I
ω∈R2

η(ξ,r1 −1,ω) + nσ

K  


η(ξ,ψ,ω) .

(3)

ξ=m ψ∈R1 ω∈R2

Under the stability condition, we define the steady state probabilities as follows.
π(j,ξ,ψ,ω) = lim P(N (t) = j, I(t) = ξ, R1 (t) = ψ, R2 (t) = ω),t→∞where j ∈ Z+ , ξ ∈ I, ψ ∈ R1 , ω ∈ R2 .
Next, we derive the steady state probability under the stability condition (3). It should
be noted that the right-hand side of (3) does not depend on λ and express the maximal
throughput for people from the spot. Defining πj = (π(j,0,0,0) , π(j,0,0,1) , · · · , π(j,K,r1 −1,r2 −1) ),π = (π0 , π1 , π2 , · · · ), we have the equilibrium equations as follows.
πQ = 0.

(4)

Also, from the probability normalization, we have,
πe = 1.

(5)
11

C Nakamura, Phung-Duc and Ando

Because our Markov chain is homogeneous in level (level-independent) from level m, thesteady state vectors πj (j ≥ m − 1) are written in matrix-geometric form;
πk+1 = πk R,k ≧ m − 1,and thus,
πj = πm−1 Rj−m+1 ,where R is minimal non-negative solution of (6).

j ≧ m − 1,

 = 0.
A0 + RC0 + Rn+1 C + Rl+1 C(6)

We can obtain R numerically using (7) started with R0 = O. R is determined recursively
by repeatedly using (7) until the difference of Rn and Rn+1 is e−10 or less (see Adan [1]pp.158-159).
 −1 ,
Rn+1 = −(A0 + Rnn+1 C + Rnl+1 C)C0

n = 0, 1, 2, . . . .

(7)Then, by rewriting (4), the unknown quantities π0 , . . . , πm−1 are determined by the following set of equations.
 + π2 C
 + . . . + πm−1 C
 + πm−1 RB(k,0)π0 B0,0 + π1 C
+πm−1 R2 B(k,0) + . . . + πm−1 Rn−m+1 B(k,0) + πm−1 Rn−m+2 C
 + . . . + πm−1 Rl−m+1 C
 = 0,+πm−1 Rn−m+3 C
πk A0 + πk+1 B(k,k) + πm−1 Rk+n−m+2 C
 = 0,+πm−1 Rk+l−m+2 C
0 ≦ k ≦ m − 2.

(8)

(9)

Also, we have (10) by rewriting (5) using R.
m−1

k=1

πk−1 e + πm−1 (I − R)−1 e = 1.

(10)

By solving the system of equations (8)-(10), we can determine the values of π0 , π1 , . . . , πm−1 .
Thus, the steady state probability can be determined.
Based on the steady state probability derived above, we define some performance measures. We summarize the performance measures in Table 2.
The mean number of the waiting people at the spot (E[Lu ]) is written as
E[Lu ] =

∞


jπj e

j=0

=

m−2

j=0

12



jπj e + πm−1 (I − R)−1 (m − 1)I + (I − R)−1 R e,

Queueing Models and Service Management

Parameters
E[Lu ]
E[Wu ]
E[Ls ]
E[Ws ]
E[C]
Ttotal(u)Tbus(u)TCRS(u)Ttotal(s)Tbus(s)TCRS(s)Table 2. Performance measures.
Definitions
The mean number of the waiting people at the spot.
The mean waiting time for customers at the spot.
The mean number of the waiting people at the station.
The mean waiting time for customers at the station.
The number of occurrences of CRS per unit time.
The total throughput from the spot.
The throughput by the bus from the spot.
The throughput by CRS from the spot.
The total throughput from the station.
The throughput by the bus from the station.
The throughput by CRS from the station.

where e = (1, 1, . . . , 1)⊤ .
The spot side has an infinite buffer, thus the blocking of customers does not occur. Therefore, applying Little’s law for the system consisting only the queue for bus at the spot, themean waiting time for customers at the spot (E[Wu ]) is derived as follows.
E[Lu ].
λThe mean number of the waiting people at the station (E[Ls ]) is written as
E[Wu ] =E[Ls ] =

m−2

j=0

πj eLs + πm−1 (I − R)−1 eLs ,where eLs = (e0 , e1 , . . . , eK−1 , eK )⊤ . The vectors in eLs are r1 r2 dimensional vectors, andei = (i, i, . . . , i) for i ∈ I.
The number of occurrences of CRS (E[C]) is given by
E[C] = σπm−1 (I − R)−1 eC − σπm−1 eC ,where eC is a (K + 1)r1 r2 dimensional vector and eC (ξr1 r2 +ψr2 +ω) = 1 for (ξ, ψ, ω) ∈{m, m + 1, . . . , K} × R1 × R2 . Here, the elements not specifically mentioned are 0 (sameas below).
The total throughput from the spot (Ttotal(u) ) is written as follows by the definition (inthis research, throughput is counted by the number of people served per a unit time).
Ttotal(u) = λ.
The throughput by the bus from the spot (Tbus(u) ) is written as follows.
Tbus(u) =∞min(l, j)q1 πj eTbus(u) ,

j=0

13

C Nakamura, Phung-Duc and Ando

where eTbus(u) is a (K + 1)r1 r2 dimensional vector and eTbus(u) (ξr r +(r −1)r +ω) = 1 for
1 2
12(ξ, ω) ∈ I × R2 . After some manipulation, this equation can be simplified to,Tbus(u) =

m−2

j=0

jq1 πj eTbus(u) + q1 πm−1 (I − R)−2 ReTbus(u)−q1 πm−1 Rl−m+1 (I − R)−2 ReTbus(u) .

Then, the throughput by CRS from the spot (TCRS(u) ) can be written as
TCRS(u) = λ − Tbus(u) .
The throughput by the bus from the station (Tbus(s) ) is written as
Tbus(s) =

m−2

j=0

q2 πj eTbus(s) + q2 πm−1 (I − R)−1 eTbus(s) ,where eTbus(s) is an (K + 1)r1 r2 dimensional vector and eTbus(s) (ξr r +ψr +(r −1)) = min(ξ, l)
1 2
2
2
for (ξ, ψ) ∈ I × R1 .
The throughput by CRS from the station (TCRS(s) ) is written as
TCRS(s) = σπm−1 (I − R)−1 eTCRS(s) − σπm−1 eTCRS(s) ,where eTCRS(s) is an (K + 1)r1 r2 dimensional vector and eTCRS(s) (ξr r +ψr +ω) = min(ξ, n)
1 2
2for (ξ, ψ, ω) ∈ {m, m + 1, . . . , K} × R1 × R2 .
Thus, the total throughput from the station (Ttotal(s) ) can be written as
Ttotal(s) = Tbus(s) + TCRS(s) .
Finally, the mean waiting time for customers at the station (E[Ws ]) is derived as
E[Ws ] =E[Ls ].
Ttotal(s)Here, note that this waiting time is when a customer arrives at the station to when a bus fromthe station comes or the car of CRS that the customer plans to departs from the spot (c.f., cars
are located at the spot). We consider the time it takes for a car to be delivered to a customer
at the station using the Road model in Section 4.
3.2. Road model
It is enough to analyze CRS model only to obtain the number of occurrences of CRS perunit time and the throughput of customers. However, our goal is also to determine the time ittakes for customers to travel on the road when CRS is introduced. To this end, we analyze the14Queueing Models and Service Management

Road model which expresses the road condition to obtain this information. Note that the roadcondition depends on CRS model, but CRS model does not depend on the road condition.
As described in the previous section, it is difficult to grasp the exact arrival processes at theservice stations because it becomes a high-dimensional model. To overcome this difficulty,
we simply use the performance measures obtained from the CRS model as the input value
for the Road model. Concretely, we put an approximation that the arrival processes of theservice stations follow Poisson processes with rates
q1
q2
αus =
+ E[C] + ϵus ,αsu =+ E[C] + ϵsu .
r1
r2
Since it is estimated that the ratio of buses and CRS to general vehicles which arrive according to Poisson process is not so large in reality, we adopt this approximation. By using
approximation, we can regard the service station as a simple M/M/1 queue [21] and the model
becomes easier to analyze. We also validate this approximation by simulation experimentlater.
According to queueing theory, we can derive the mean sojourn time Wus and Wsu ineach service station as
1
1
,
Wsu =
.
Wus =
β − αusβ − αsuThen, we derive the bidirectional effective speeds sus and ssu (i.e., the mean speed of carson the road) as follows.
sus =

1
,
Wus × M

ssu =1.
Wus × M

From the above results, the mean of the times for a vehicle to travel from the spot to thestation and vice versa E[Rus ] and E[Rsu ] can be derived as
E[Rus ] =d,sus

E[Rsu ] =d.
ssu

Besides, we can calculate the mean of the total required time for customers from the spot tothe station (i.e., the mean time from when a customer arrives at the spot to when he arrives
at the station) and also vice versa E[Aus ] and E[Asu ] as follows.
E[Aus ] = E[Wu ] + E[Rus ],E[Asu ] = E[Ws ] + E[Rsu ] + PCRS E[Rus ],where PCRS is the rate of customers from the station to the spot who use CRS as
PCRS =TCRS(s).
Ttotal(s)Here, note that the cars of CRS are located at the spot. As a result, only customers who use
CRS from the station have the waiting time for the car to come before they ride on it fromthe spot to the station. The analysis of the distribution of waiting time and required time isreferred to [18].
15

C Nakamura, Phung-Duc and Ando

4. Price Mechanism
In this section, we discuss a price mechanism of CRS, which gives a positive solution for
all the bus company, the customers, and the car providers. We discuss the feasibility of CRS
only using CRS model in this paper for simplicity. It is also important to discuss the pricemechanism considering the road congestion expressed by Road model and the accompanying
strategic behavior of customers, which we leave for future work.
Table 3. Parameters and Performance measures used in the discussion of the pricemechanism.
Symbols
Mbus
′
Mbus

Ttotal(s)′Ttotal(s)q1 , r 1
q2 , r 2
q1′ , r1′q2′ , r2′
F
c
V
gbus
gCRS

Definitions
Bus company’s income per unit time before the introductionof CRS.
Bus company’s income per unit time after the introductionof CRS.
The total throughput at the station before the introductionof CRS.
The total throughput at the station after the introductionof CRS.
The parameters of the Erlang distribution for the depart intervalof buses from the spot before the introduction of CRS.
The parameters of the Erlang distribution for the depart intervalof buses from the station before the introduction of CRS.
The parameters of the Erlang distribution for the depart intervalof buses from the spot after the introduction of CRS.
The parameters of the Erlang distribution for the depart intervalof buses from the station after the introduction of CRS.
Fee after the introduction of CRS (CRS and bus).
Bus fee before the introduction of CRS.
Profit that car providers get per unit time.
Gasoline cost for a bus running one way.
Gasoline cost for one CRS.

We consider the scenario where a bus company itself introduces CRS; that is, the bus
company reduces the number of buses instead of the introduction of CRS. In this scenario,
the bus company may earn more than before the introduction of CRS. Besides, it also helps
secure the rest time for the drivers and may contribute to solving labor problems.
We assume that c is the bus fee before introducing CRS; F is the fee (for both the bus
and CRS) after introducing CRS, respectively. We summarize all the parameters and performance measures used in the price mechanism in Table 3. To simplify the discussion,
we do not consider the shortage of CRS cars in this study. The schematic flow of money
distribution when CRS is introduced is as Fig. 4.
To derive the range of the executable fee, we need to solve the following two constraints.
16

Queueing Models and Service Management(i) Before the introduction of CRS.

(ii) After the introduction of CRS.
Figure 4. The money distribution diagram.
First, F needs to be cheaper than c to prevent loss to the customers by introducing CRS(condition 1). Second, the profit of the bus company increases by the introduction of CRS
while the car providers can receive the gasoline costs and the profits (condition 2). Condition
2 is needed to guarantee that CRS causes no loss for both the bus company and the car
providers. From condition 1, (11) is derived.
F < c.

(11)

Also, we obtain (12) from condition 2.
′
Mbus> Mbus′⇔ {(λ + Ttotal(s))F + gbus (q1 q1′
q2 q ′− ′ + − 2′ )} − (gCRS E[C] + V )r 1 r1 r 2 r2
q2
q1
> {min(λ, l ) + min(Ttotal(s) , l )}c
r1
r2
17

C Nakamura, Phung-Duc and Ando

⇔

Z
< F,
′
λ + Ttotal(s)

(12)

where
Z = gCRS E[C] + V − gbus (q2 q ′
q1
q1 q1′− ′ + − 2′ ) + {min(λ, l )r 1 r1 r 2 r2
r1
q2
+ min(Ttotal(s) , l )}c.
r2

The following executable fee range is obtained by summarizing the two conditions.
Z< F < c.
′λ + Ttotal(s)5. Numerical Examples
We show the results of some numerical experiments for the stability region, the throughput, the mean total required time for customers, and the executable fee. In addition to thetheoretical analysis, we also perform the Monte Carlo simulation to confirm the validity of
the analysis results and verify the details that cannot express in the analytical model. Notethat we assume that the arrival rates of buses do not change before and after the introduction′′of CRS in Sections 5.1, 5.2 and 5.3, i.e., q1(2) = q1(2), r1(2) = r1(2).
5.1. The stability region
We show the numerical results of the stability region boundary in Fig. 5 (note that thestability region is below the curves for each parameter). We fix the parameters as q1 =10, r1 = 2, q2 = 10, r2 = 2, l = 30, m = 2, n = 4 and K = 30 and after that, unlessotherwise specified, we assume that the size distribution for the batch of customers arrives
at the station side follows a uniform distribution with an average of 2.5. We can confirm
that the stability region expands as the rate for occurrences of CRS σ increases. This result
implies that the introduction of CRS allows more people to arrive at the spot i.e., higher the
maximal arrival rate of customers at the spot λ. Therefore, CRS can be considered to be ahelpful service from the perspective of the stability region. Besides, we plot the boundary
while changing the values of the customer arrival rate at the station side δ. The results showthat the stability region expands as δ increases. It is because CRS becomes likely to occur
as the number of people at the station increases.
5.2. The throughput
We discuss the throughput, in other words, the average number of people served per unit
time. Fig. 6 shows the increase of the total throughput at the station by the introduction of
CRS (i.e., the difference of Ttotal(s) before and after introducing CRS), where the horizontal
axis is the arrival rate of customers at the station δ, and we change the rate for the occurrenceof CRS σ. The other parameters are fixed as λ = 30, q1 = 10, r1 = 2, q2 = 10, r2 = 2, l =18

Queueing Models and Service Management
=0
=20
=40
=60

280
260
240
220
200
180
160
140
120
0

20

40

60

80

100

Figure 5. The boundary of the stability region.

increase of the throughput at the station

30, m = 2, n = 4 and K = 30. We can confirm that the increase of the total throughput
by CRS takes a larger value as σ becomes larger. This means that CRS is effective from theperspective of the throughput, especially when δ is large, i.e., there are many people arriving
at the station. Besides, it is confirmed that the theoretical analysis results and the Monte
Carlo simulation in the same case (sim) as we can see in Fig. 6 are consistent.
17.5

= 10
= 50
= 90
sim =10
sim =50
sim =90

15.0
12.5
10.0
7.5
5.0
2.5
0.0
0

10

20

30

40

50

Figure 6. The increase of the total throughput at the station by the introduction of CRS
against δ for various σ.
Fig. 7 also shows the increase of the total throughput by CRS in the case λ = 30, σ =50, q1 = 10, r1 = 2, l = 30, m = 2, n = 4 and K = 30. This time, we change the valueof the variance of the distribution and fix the mean for the intervals of the buses from thestation, i.e., adjusting q2 and r2 . Usually, it is expected that the buses arrive at almost fixedintervals, i.e., the variance=0. However, it is often observed that the arrival of the buses
becomes irregular due to some accidents or troubles, i.e., the variance becomes more than
0. In Fig. 7, we plot the results of the theoretical analysis and the Monte Carlo simulation(sim) of the same situation (it is confirmed that both results match), and also show the resultof the simulation in the case that the interarrivals of buses are constant (simfixed). We canconfirm that the increase of the total throughput by the introduction of CRS increases as thevariance becomes larger because more people who could not ride the bus due to missing thetiming can use CRS as alternatives. Briefly, it is implied that CRS becomes more effective
19

C Nakamura, Phung-Duc and Ando

increase of the throughput at the station

as the uncertainty of the buses increases.
Next, we consider the throughput when we change the value of the interarrival of customers and the distribution for the batch of the customers at the station in various ways.
Here, in our numerical experiment, we assume that customers on the train arrive at the station simultaneously, i.e., δ is the arrival rate of the train. Under this assumption, it can beconsidered that the variance of the interarrival of customers expresses the delay of the train
itself that directly connects to the station (i.e., primary impact), and the distribution for thebatch of the customers expresses the fluctuations in the number of passengers on the train
due to the disturbance of transportation (e.g., other trains, buses, etc.) connected to the train(i.e., secondary impact).
variance_s=0.01
variance_s=0.005
variance_s=0.003
variance_s=0.0025
variance_s=0.002
sim variance_s=0.01
sim variance_s=0.005
sim variance_s=0.003
sim variance_s=0.0025
sim variance_s=0.002
simfixed variance_s=0

8

6

4

2

0
0

10

20

30

40

50

Figure 7. The increase of the total throughput at the station by the introduction of CRS
against δ for various q2 and r2 (variance).
Fig. 8 and Fig. 9 show the throughput by CRS from the station TCRS(s) and the blocked
people per a unit time at the station (δE[X] − Ttotal(s) ), respectively, for various combinations of the interarrival (poisson, fixed) and the batch distribution (fixed, uniform, poisson).
Here, we set the mean of these distributions 6 and as the results, the variances of the fixed,
poisson, and uniform distributions become 0, 6, 10, respectively. In addition, we set theother parameters as λ = 30, σ = 50, δ = 50, m = 2, n = 4, l = 30, K = 50, q1 = 10 and
r1 = 2 unless otherwise specified, and the horizontal axis σ. Besides, we make the graphs
for each variance of the departure interval of the bus from the station.
In both Fig. 8 and Fig. 9, the changes in the batch distribution have less effect comparedto the variance of the interarrivals of the train i.e., the secondary impact has more negligible
effect compared to the primary impact, that is an intuitive result. Regarding the interarrivals,
the throughput by CRS becomes smaller and the number of blocked people becomes larger
in the case of Poisson arrival, compared to the case that the interarrival is fixed. This isbecause that the greater the variance of the interarrival, the more difficult it is to meet theconditions to occur CRS, resulting in the fact that the number of people who cannot be served
increases. About the distribution for the batch of the customers, the throughput by CRS
becomes smaller, and the number of blocked people becomes a larger when the distribution
has larger variance as well, although the value of the difference is so tiny.

20

Queueing Models and Service Management

CRS throughput at the station

40

batch=fixed, arrival=poissonbatch=uniform, arrival=poissonbatch=poisson, arrival=poisson
sim batch=fixed, arrival=poisson
sim batch=uniform, arrival=poisson
sim batch=poisson, arrival=poisson
sim batch=fixed, arrival=fixed
sim batch=uniform, arrival=fixed
sim batch=poisson, arrival=fixed

35
30
25
20
15
10
5
0

10

20

30

40

50

(i) TCRS(s) against δ (the variance of thearrival interval for buses from the station is0.01).
batch=fixed, arrival=poissonbatch=uniform, arrival=poissonbatch=poisson, arrival=poisson
sim batch=fixed, arrival=poisson
sim batch=uniform, arrival=poisson
sim batch=poisson, arrival=poisson
sim batch=fixed, arrival=fixed
sim batch=uniform, arrival=fixed
sim batch=poisson, arrival=fixed

CRS throughput at the station

40
35
30
25
20
15
10
5
0

10

20

30

40

50

(ii) TCRS(s) against δ (the variance of thearrival interval for buses from the station is0.05).

CRS throughput at the station

40

batch=fixed, arrival=poissonbatch=uniform, arrival=poissonbatch=poisson, arrival=poisson
sim batch=fixed, arrival=poisson
sim batch=uniform, arrival=poisson
sim batch=poisson, arrival=poisson
sim batch=fixed, arrival=fixed
sim batch=uniform, arrival=fixed
sim batch=poisson, arrival=fixed

35
30
25
20
15
10
5
0

10

20

30

40

50

(ii) TCRS(s) against δ (the variance of thearrival interval for buses from the station is0.002).
Figure 8. The throughput by CRS from the station for various combinations of theinterarrival of customers and the distribution for the batch of the customers.

21

C Nakamura, Phung-Duc and Ando90

batch=fixed, arrival=poissonbatch=uniform, arrival=poissonbatch=poisson, arrival=poisson
sim batch=fixed, arrival=poisson
sim batch=uniform, arrival=poisson
sim batch=poisson, arrival=poisson
sim batch=fixed, arrival=fixed
sim batch=uniform, arrival=fixed
sim batch=poisson, arrival=fixed

Number of blocked people

80
70
60
50
40
30
20
10
0

0

10

20

30

40

50

(i) The number of blocked people per a unit
time (the variance of the bus from the station
is 0.01).
90

batch=fixed, arrival=poissonbatch=uniform, arrival=poissonbatch=poisson, arrival=poisson
sim batch=fixed, arrival=poisson
sim batch=uniform, arrival=poisson
sim batch=poisson, arrival=poisson
sim batch=fixed, arrival=fixed
sim batch=uniform, arrival=fixed
sim batch=poisson, arrival=fixed

Number of blocked people

80
70
60
50
40
30
20
10
0

0

10

20

30

40

50

(ii) The number of blocked people per a unit
time (the variance of the bus from the station
is 0.005).
90

batch=fixed, arrival=poissonbatch=uniform, arrival=poissonbatch=poisson, arrival=poisson
sim batch=fixed, arrival=poisson
sim batch=uniform, arrival=poisson
sim batch=poisson, arrival=poisson
sim batch=fixed, arrival=fixed
sim batch=uniform, arrival=fixed
sim batch=poisson, arrival=fixed

Number of blocked people

80
70
60
50
40
30
20
10
0

0

10

20

30

40

50

(ii) The number of blocked people per a unit
time (the variance of the bus from the station
is 0.002).
Figure 9. The number of blocked people at the station for various combinations of theinterarrival of customers and the distribution for the batch of the customers.

22

Queueing Models and Service Management

5.3. The mean total required time for customers
This subsection shows the results of some numerical experiments of the mean total required time derived in Section 4.
Fig. 10 shows the results of the mean of the total required time for customers fromthe spot to the station E[Aus ] where we set the horizontal axis σ and change the value ofthe arrival rate of customers at the spot λ and the arrival rate of general cars at the service
station from the spot to the station ϵus i.e., this expresses how busy the road is. We set theother parameters as δ = 300, m = 2, n = 4, l = 30, K = 30, q1 = 10, r1 = 1, q2 = 10, r2 =1, SN = 60, M = 200 and d = 3. Note that the input of the simulation for the service
station on the road is the actual arrival of cars (we simply assume M/M/1 in the theoreticalanalysis) and both results match well.
The mean total required time becomes smaller as σ becomes larger due to the occurrenceof CRS when ϵus is not too high ((i), (ii) and (iii) in Fig. 10) and increases as λ increases
i.e., the number of people at the spot increases. These are natural results. Here, interestingly,
only when ϵus takes an extremely high value ((iv) in Fig. 10) within the stable conditions of
the Road model (i.e., αus < β), the graph behaves differently. The curve becomes convex
and has the optimal value of σ when both λ and ϵus take high value; that is, it is not desirable
to generate too much CRS when the road is congested. Besides, when λ is small and ϵus
is large, the total required time becomes larger as σ becomes larger i.e., it is better not togenerate CRS in this situation.
2.00
= 70
= 140

1.75

= 210
= 280

E[Aus]

1.50

1.25

1.00

sim

= 70

sim

= 140

sim

= 210

sim

= 280

0.75

0.50

0.25

0.00
0

25

50

75

100

125

150

175

(ii) ϵus =7500.

(i) ϵus =5500.
2.00
= 70
= 140

1.75

= 210
= 280

E[Aus]

1.50

1.25

1.00

sim

= 70

sim

= 140

sim

= 210

sim

= 280

0.75

0.50

0.25

0.00
0

25

50

75

100

125

150

(iii) ϵus =9500.

175(iv) ϵus =11500.

Figure 10. The mean of the total required time for customers from the spot to the station
E[Aus ].
23

C Nakamura, Phung-Duc and Ando

280

270

Upper
Lower = 60
simLower = 60

270
260

Upper
Lower = 20
Lower = 40
Lower = 60
Lower = 80
simLower = 20
simLower = 40
simLower = 60
simLower = 80

260
250

250

240

F

F

240
230

230

220

220

210

210

200

200

190

20

40

60

80

100

120

140

0

160

25

50

75

100

125

150

175

(ii) The results for various δ.

(i) The area of the executable fee.

Figure 11. The executable range of the fee F .
5.4. The range of the executable fee
In this subsection, we show the results of the numerical experiments of both the theoretical analysis and the simulation for the price mechanism of CRS where we set σ = 30, q1 =10, q1′ = 9, r1 = r1′ = 2, q2 , = q2′ = 10, r2 , = r2′ = 2, l = 30, m = 2, n = 4 and K = 30 i.e.,
we assume that the bus company decreases the number of buses from the spot to the stationby the introduction of CRS. When we set the parameters, we referred to some existing dataof gasoline costs [13].
= 20
0.40

= 40

= 60

0.35

= 20

0.225

= 40

= 60

0.200

= 80

0.25

sim

= 20

sim

= 40

sim

= 60

sim

= 80

0.20

= 80
0.175

E[Ws]

E[Wu]

0.30

0.150

sim

= 20

sim

= 40

sim

= 60

sim

= 80

0.125

0.100

0.15

0.075

0.10

0.050

0.05

0

25

50

75

100

125

150

175

(i) The waiting times of customers at the spot
E[Wu ].

0

25

50

75

100

125

150

175

(ii) The waiting times of customers at thestation E[Ws ].

Figure 12. The waiting times of customers at both sides.
We show the area of executable fees F (between Upper and Lower) in Fig. 11 (i), where
the horizontal axis is the arrival rate of customers at the spot λ. The result tends to be sointeresting and worth discussing. When λ is too small, it is difficult to meet the condition tocarry out CRS (there are m or more people at the spot). As a result, CRS becomes infeasible.
When λ gets higher, the executable range of F expands with the occurrences of CRS. However, since the arrival rate of customers at the station δ is fixed, the number of occurrencesof CRS does not change much even if only λ becomes too large. On the other hand, the bus
company’s income per unit time before the introduction of CRS (min(λ, lq1 /r1 )c) increases
in proportionally to λ. Therefore, when λ exceeds about 75, min(λ, lq1 /r1 )c increases more
rapidly than the amount obtained by the occurrences of CRS, and the range of executable F
is getting narrower. Here, we can consider the upper limit of the arrival rate of customers
24Queueing Models and Service Management

at the spot λ that can be serviced by bus as 150 (= lq1 /r1 ). Thus, min(λ, lq1 /r1 )c becomes
constant, and the total number of customers for the bus company increases compared to that
before the introduction of CRS when λ is more than 150. As a result, the range of executable
F expands monotonically.
Furthermore, we plot while changing the value of the arrival rate of customers at thestation side δ in Fig. 11 (ii). It is interesting to see that there is no feasible range (i.e., CRS
cannot be executed) if both δ and λ take small values. This result implies that the operator
should take in CRS only when there are more than a certain number of people at the stationand the spot (i.e., only the bus is enough when there are few people) considering the cost of
the operation.
Finally, we show the results of the waiting times of customers at both sides corresponding
to Fig. 11 (ii) in Fig. 12. It is interesting to see that the waiting time at the spot when λ is too
small takes high value because it is difficult to carry out CRS (see (i)) and that the waitingtime at the station has a maximum value (the point where λ is about 10). One possible reason
for the behavior of (ii) is that when λ becomes large enough to satisfy the condition for theoccurrences of CRS, the blocked person when λ is small may have to wait for the bus because
the buffer size of the station is finite. These results imply that it is meaningless to introduce
CRS when the arrival rate of the spot is so low (i.e., λ is under 10) from the perspective of
the waiting time at both sides. Also, we can confirm that CRS is a system where the fee andthe waiting times are related e.g., when CRS is feasible at low price (e.g., when δ =80), thewaiting time at the spot side is short, while the waiting time at the station becomes long. As
a future development, we are planning to consider the scenario where the operator of CRS
controls the waiting time of customers by adjusting the fee dynamically.

6. Conclusion
In this paper, we have considered a new transportation service Car/Ride-Share (CRS),
which may be alternative transportation for buses in the case of congestion. CRS has several features such that people can carry out carsharing and ridesharing simultaneously while
the uneven distribution of cars does not occur, and owners of private cars can get financial
incentives by sharing them.
We have considered the scenario where CRS is introduced between a station and a spot
(e.g., university, company, etc.) and present the approximate model, which consists of two
queuing models, the CRS model and the Road model. By some numerical experiments ofthe theoretical analysis and the simulation, it has turned out both results (theoretical andsimulation) match well and that the approximate model shows highly accurate results in ashort computation time. Also, some beneficial results have been suggested; CRS is effectivefrom the perspective of the throughput. However, CRS becomes ineffective when the roadis highly congested, etc. Besides, we also have discussed the price mechanism of CRS andhave shown that CRS is a beneficial system for all the three perspectives; passengers, thebus company, and the car providers when the number of users exceeds a certain level.
As future work, it is clear that the details (e.g., the preferences of CRS of customers, the25

C Nakamura, Phung-Duc and Ando

limitation of the number for the CRS cars) should be further studied. Especially, we havediscussed the price mechanism of CRS using only the CRS model. We also need to havea more precise financial discussion considering Road model in the future. In addition, weplan to incorporate game theory into our model to consider the possibility that customers
take strategic actions to increase each personal gain, and compare different policies for the
CRS pricing.

Acknowledgements
This work is partly supported by JSPS KAKENHI Nos. 19K12198, 18K18006, 21K11765,
JST MIRAI No. JPMJMI19B. This study is supported by F-MIRAI: R&D Center for Frontiers of MIRAI in Policy and Technology, the University of Tsukuba and Toyota Motor Corporation collaborative R&D center.

References[1] Adan, I., Leeuwaarden, V.J., & Selen, J. (2017). Analysis of structured Markov Processes. arXiv:1709.09060v1.
[2] Agatz, N., Erera, A., Savelsbergh, M., & Wang, X. (2012). Optimization for dynamic
ride-sharing: A review. European Journal of Operational Research, 223(2), 295–303.
[3] Ando, H., Takahara, I., & Osawa Y. (2019). Mobility services in university campus.
Communications of the Operations Research Society of Japan, 64(8), 447–452, inJapanese.
[4] Banerjee, S., Riquelme, C., & Johari R. (2015). Pricing in ride-share platforms: A
queueing theoretic approach. SSRN 2568258.
[5] Bimpikis, K., Candogan, O., & Saban, D. (2019). Spatial pricing in ride-sharing networks. Operations Research, 67(3), 744–769.
[6] Boyaci, B., Zografos, K. G., & Geroliminis N. (2017). An integrated optimizationsimulation framework for vehicle and personnel relocations of electric carsharing systems with reservations. Transportation Research Part B, 95, 214–237.
[7] Correia, G., & Antunes, A. (2012). Optimization approach to depot location and trip
selection in one-way carsharing systems. Transportation Research Part E, 48, 233–
247.
[8] Daganzo, C.F., & Ouyang, Y. (2019). A general model of demand-responsive transportation services: From taxi to ride sharing to dial-a-ride. Transportation ResearchPart B, 126, 213–224.
[9] Hampshire, R. C., & Gaites, C. (2011). Peer-to-peer carsharing: Market analysis andpotential growth. Transportation Research Record, 2217(1), 119–126.
26

Queueing Models and Service Management[10] Hampshire, R. C., & Sinha, S. (2011). A simulation study of peer-to-peer carsharing.
IEEE Forum on Integrated and Sustainable Transportation Systems, 159–163.
[11] Jia, Y., Xu, W., & Liu X. (2017). An optimization framework for online ride-sharing
markets. 2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS).
[12] Makimoto, N. (2001). Queueing algorithms - Matrix analytic approach. Asakura Publishing Co., Ltd., in Japanese.
[13] Ministry of Health, & Labor and Welfare. Basic statistical survey of wage structures. https://www.mhlw.go.jp/toukei/list/chinginkouzou.html, Last accessed 19 December 2020, in Japanese.
[14] Ministry of Land, Infrastructure, & Transport and Tourism, Car fuel efficiency list,
www.mlit.go.jp/jidosha/jidosha_fr10_000039.html, Last accessed 3 February 2020, in Japanese.
[15] Nakamura A., Phung-Duc T., Ando H., “Queueing analysis for a mixed model ofcarsharing and ridesharing,” Lecture Notes in Computer Science, LNCS 12023, pp.
144-157, Springer, Cham, 2020.
[16] Nakamura A., Phung-Duc T. and Ando H., “A stochastic model for car/ride-share
service by a bus company,” Proceedings of The 2020 International Symposium on
Nonlinear Theory and Its Applications, pp. 312-315, 2020.
[17] Nakamura A., Phung-Duc T. and Ando H., “Queueing analysis of a car/ride-sharesystem,” Annals of Operations Research , 310(2), pp. 661-682, 2022.
[18] Nakamura A., Phung-Duc T. and Ando H., “Queueing Analysis of a Mixed Modelof Public and Demand Responsive Transportations,” Lecture Notes in Computer Science, LNCS 13104, pp. 457-471, Springer, Cham, 2021
[19] Tao S., Pender J., “A stochastic analysis of bike sharing systems,” Probability in theEngineering and Informational Sciences, 35(4), pp. 781-838.
[20] Tao S., Pender J, “The impact of smartphone apps on bike sharing systems,” SSRN
3582275, 2020.
[21] Vandaele N., Van Woensel T., Verbruggen A., “A queueing based traffic flow model,”Transportation Research Part D, 5(2), pp. 121-135, 2000.

27

C Nakamura, Phung-Duc and Ando28