• Editorial Board +
• For Contributors +
• Journal Search +
Journal Search Engine
ISSN : 1598-7248 (Print)
ISSN : 2234-6473 (Online)
Industrial Engineering & Management Systems Vol.18 No.2 pp.234-244
DOI : https://doi.org/10.7232/iems.2019.18.2.234

# Strategic Joining Behaviors and Optimal Control for Discrete-Time Passenger-Taxi Matching Queues

Sung Dong Moon, Doo Ho Lee*
Division of Software, Media and Industrial Engineering, Kangwon National University, Gangwon, Republic of Korea
Corresponding Author, E-mail: enjdhlee@kangwon.ac.kr
November 21, 2018 February 25, 2019 March 12, 2019

## ABSTRACT

This study explores strategic joining behaviors and optimal control for discrete-time passenger-taxi matching queues. We analyze strategic joining behaviors by passengers in both observable and unobservable cases. In both cases, we provide the equilibrium joining strategies for individual passengers and optimal joining strategies for socially concerned passengers. We also investigate the optimal taxi buffer size to maximize the social welfare from a governmental perspective. For each social welfare maximization problem, we present a simulated annealing algorithm which helps us find the optimal control scheme for our model. Finally, we conduct various numerical experiments to suggest an insightful operational control methodology.

## 1. INTRODUCTION

It often takes a long time to find a taxi at an airport, ferry terminal or railway station during peak hours. In some very touristy areas, this problem is worse given the increased numbers of passengers and visitors. As Anwar et al. (2013) noted, when too many taxis wait in a taxi queue, it reduces the number of taxis available to service the rest of the city and it also reduces the revenue of taxi drivers waiting in such queues because they forgo the opportunity to earn fares elsewhere. In contrast, when too few taxis are available, passengers are likely to endure long waits. As such, this type of matching issue between passengers and taxis has been an interesting and an important issue in the area of urban transport over the decades. How many taxis do we need at a taxi station so that waiting times are not too long? How much space should the taxi station have? How much should the taxi fare be to maximize social welfare? In this paper, we model this passenger-taxi matching problem as a matching queueing system. Our purpose is to answer the above questions and provide passengers with equilibrium and optimal joining strategies in order to coordinate passengers and taxis while also improving the performance of the system in terms of social welfare.

A matching queue, also known as a double-ended queue, was initially proposed by Kendall (1951), who introduced the matching problem between passengers and taxis. On one side is a queue of taxis and on the other a queue of passengers. A short taxi queue may inconvenience passengers in some cases, but a long taxi queue clearly does while also wasting valuable and expensive space. Moreover, both short and long queues can never coexist. In everyday life, many arrangements in a variety of fields, including communication networks, production inventory systems, and service systems, can be modelled as matching queues. According to Kendall (1951), the size of the queue is caused by the difference between the arrivals of passengers and taxis. The authors also pointed out that the mean queue length approaches zero when the two arrival rates are identical and the variance of the queue length increases infinitely. Dobbie (1961) and Giveen (1963) extended this topic to a matching queue with nonhomogeneous Poisson arrivals of passengers and taxis. Jain (1962) discussed the matching problem under the assumption that the inter-arrival time of taxis is distributed as a general distribution and only a finite capacity of taxis is available. Kashyap (1966) investigated a matching queue while assuming that there is limited waiting space both for customers and taxis, with taxis serving the passengers in bulk. An early discussion with references is given in Srivastava and Kashyap (1982). More recently, the matching queue has been applied to assembly facilities producing multipart components. Parts arrive independently according to a renewal process, but the component can only be assembled when all of the parts are present. Papers that discuss these assembly-like matching queues include those by Som et al. (1994) and Takahashi et al. (2000). Conolly et al. (2002) studied the transient behavior of a double-ended queueing system with state-dependent impatience, also known as reneging or abandonment. The taxi queue is shortened by either passenger arrival or taxi reneging events, and vice versa for a passenger queue. Based on the two-dimensional Markov chain, the authors presented a moment-generating function and first-passage times. Wong et al. (2005) adopted an absorbing Markov chain to model the search process of taxi movements and proposed a useful formulation for describing taxi urban services in a network. Crescenzo et al. (2012) dealt with a matching queue with system failures and repairs, assigning transient and steady-state probability distributions for passenger and taxi queue lengths, respectively. Afèche et al. (2014) studied the matching queue with batch arrivals and abandonment. There are two types of customers, patient ones who queue but may later abandon, and impatient ones who depart immediately if their order is not filled. The authors first established the closed-form results for the double-sided queueing model with batch arrivals and abandonment. More information on the matching queue and actual applications is available in several published studies (Perry and Stadje, 1999;Zenios, 1999;Yang et al., 2010;Yang and Yang, 2011;Wong et al., 2014;Gurvich and Ward, 2014) and the references therein.

Most of the above works focus on determining system performance measures such as queue lengths and waiting times. Although some discussed optimal control schemes, they did not consider strategic joining behaviors between passengers and taxi drivers. Because passengers and taxi drivers are both sensitive to delays, they typically decide whether or not to join a queue based on welldefined joining strategies. This can therefore be modeled as a game among arriving passengers and taxis, and the fundamental problem is to identify the Nash equilibrium. Naor (1969) was the first to show that tolls can be levied to encourage strategic customers to adopt socially optimal behavior that may not be optimal for them personally. Since then, a number of studies of strategic joining/balking behavior by customers in queueing systems have been conducted. The monograph of Hassin and Haviv (2003) summarize the main approaches and several results on various observable and unobservable queueing systems with extensive bibliographical references. Recently, equilibrium joining/balking strategies in matching queues have been the subject of growing attention. Li et al. (2016) considered a make-to-stock production system with setup costs and delay-sensitive customers. They modeled the production system as a matching M/M/1 make-to-stock queue with a two-critical-number policy. Under this policy, production starts when N customer orders have accumulated and stops immediately when the inventory level reaches S. Li et al. (2016) derived the equilibrium customer purchasing strategies and system performance metrics. Those authors also obtained the optimal values of two control variables. Shi and Lian (2016a) analyzed the strategic joining behavior of passengers in both the observable and the unobservable cases. In the observable case, those authors provided the individual equilibrium and the socially optimal joining strategies of threshold type. On the other hand, in the unobservable case, they discussed those of probability type. Further, the optimal taxi buffer size which maximizes the overall social welfare was determined from the perspective of a government (or a social planner). Shi and Lian (2016b) extended their work to the equilibrium strategies and optimal control method in a matching queue where there is limited waiting space both for passengers and taxis. They considered a centralized system and a decentralized system. In the centralized system, the government sets thresholds for both passengers and taxis to maximize social welfare. On the other hand, in the decentralized system, passengers and taxis determine whether to join a queue or not based on their individual utility functions. More recently, Wang et al. (2017) analyzed the strategic behavior and social optimization in a double-ended queue with gated policy. In Wang et al. (2017)’s model, taxis are not allowed to enter if the number of taxis reaches an upper limit (no waiting passengers) and are allowed to enter again when the number of waiting taxis is reduced to a lower limit.

Motivated by the above excellent works, this paper explores equilibrium joining strategies and social welfare maximization in passenger-taxi matching queues under a discrete-time setting. For decades, the discrete-time queue has received much attention due to its actual use in timeslotted digital communication systems and other synchronous systems (Lee, 2016), as the discrete-time queue is more suitable than the continuous-time queue for modeling systems in which the basic operational units are bits, packets and cells. The practical interest in discrete-time matching queues is not confined to taxis and passengers. The lack of radio spectrum resources has limited the sustainable development of wireless communication technologies and mobile application networks. The cognitive radio network (CRN) is the most promising candidate solution to address such spectrum shortages and inefficiencies. The main principle of a CRN is that the secondary user is intelligently aware of the environment and opportunistically occupies the ‘spectral hole’ of the privileged user. Comparing a CRN with a matching queue, the packet and the channel can be regarded as the passenger and the taxi, respectively. In a CRN, the buffer capacity of arriving packets and the number of available channels should be optimized so that spectrum allocation is realized dynamically and the overall operational profit (the energy consumption) is maximized (minimized). Due to its synchronized features, many studies have assumed discrete-time geometric distributions for packet arrival, packet transmission, packet dropping, packet retrial, channel occupation and other packet processes. By doing so, the discrete-time queue can describe coincidence events and provide the more precise performance measures of various communication systems, including CRNs (Jin et al., 2013;Jin et al., 2016;Jin and Sun, 2017;Zhao and Bai, 2017). To the best of our knowledge, no works thus far have analyzed strategic behaviors in a discrete-time matching queue. In this paper, we extend the work of Shi and Lian (2016a) to a discrete-time matching queue and depict the equilibrium joining/balking strategies of passengers as well as the optimal strategies which maximize social welfare.

The remainder of the paper proceeds as follows. In section 2, we describe the mathematical model and associated assumptions. In section 3, we derive the stationary distribution and the important performance measures. In section 4, we discuss equilibrium joining strategies used by individual and socially concerned passengers in observable and unobservable cases. We also determine the optimal buffer size from a governmental perspective. Section 5 describes the various numerical experiments conducted here and provides an insightful operational control strategy.

## 2. MATHEMATICAL MODEL AND ASSUMPTIONS

The queueing system examined under this study has the following features. Passengers arrive in groups according to a Bernoulli process with a probability of λ (0 < λ < 1). Meanwhile, taxis arrive sequentially according to a Bernoulli process with a probability of μ (0 < μ < 1). For the system to be stable, the inequality λ < μ should hold. In a discrete-time queueing system, arrivals by a taxi and a passenger can occur at the same time at the boundary of the time axis, making it necessary to determine the order of their arrivals. If a taxi and a passenger arrive at the taxi station simultaneously, it is assumed that the taxi arrives instantaneously first. Each group of passengers consists of one to five persons who can be precisely taken to their destinations by a taxi. For convenience, we regard groups of passengers as a single passenger. The passengers and taxis are queued on a firstin- first-out basis. The waiting space for taxis is finite. We define K (K ≥ 1) as the maximum number of taxis that can be accommodated at the taxi station. Because the space occupied by passengers is much smaller than a taxi, the waiting space for passengers is assumed to be infinite.

We assume that a passenger pays a taxi fare of p1 (p1 > 0) on average and receives a reward of R (R > 0) per unit time for taking a taxi. Moreover, taxis and passengers accrue waiting costs while they remain at the taxi station. Here, we define C1 (C1 > 0) and C2 (C2 > 0) as the passenger’s waiting cost per unit of time and the taxi’s waiting cost per unit of time, respectively. Each taxi spends an average of Cf (Cf > 0) on maintenance and fuel costs. Finally, to improve the quality of the taxi service and to reduce traffic congestion, the government can adjust the taxi arrival rate by imposing a tax or granting a subsidy to each taxi. We define p2 as the tax or subsidy affecting the taxi during each trip. p2 > 0 indicates a government grants subsidy to each taxi, while p2 < 0 denotes a government levy on each taxi.

## 3. QUEUEING ANALYSIS

Define $N ( t )$ as the number of the passengers or the taxis at the taxi station at time t, where N(t) > 0 indicates that the passengers are waiting for the taxis, N(t) < 0 denotes that the taxis are waiting for the passengers, and N(t) = 0 means that the taxi station is empty. Because the maximum number of taxis in the system is equal to K and the waiting space for passengers is assumed to be infinite, a stochastic process {N(t), t = 0, 1, 2, ⋯} becomes a one-dimensional discrete-time Markov chain with the state space expressed as Ω ={−K, −K + 1, ⋯, −1, 0, 1, ⋯} and its non-zero one-step transition probabilities are given by

$q − K , − K + 1 = λ , q n , n + 1 = λ μ ¯ , n ≥ − K + 1 , q n + 1 , n = λ ¯ μ , n ≥ − K , q − K , − K = λ ¯ , q n , n = λ μ + λ ¯ μ ¯ , n ≥ − K + 1$

where $λ ¯ = 1 − λ and μ ¯ = 1 − μ$. The corresponding transition diagram is shown in Figure 1.

Let πn be the stationary probability of N(t), which means that $π n = lim t → ∞ Pr { N ( t ) = n }$, with $n ≥ − K$. Then, the local balance equations governing the system are then given by

$π − K λ = π − K + 1 λ ¯ μ$
(1)

$π n λ μ ¯ = π n + 1 λ ¯ μ , n ≥ − K + 1$
(2)

Solving these equations recursively, we have

$π − K = 1 − ρ$
(3)

$π n = ( 1 − ρ ) ω n + K μ ¯ , n ≥ − K + 1$
(4)

where $ω = ρ μ ¯ / λ ¯ and ρ = λ / μ$. From (3) and (4), we calculate the mean passenger queue length L1 and the mean passenger waiting time W1:

$L 1 = ∑ n = 1 ∞ n π n = λ λ ¯ ω K μ − λ$
(5)

$W 1 = L 1 λ = λ ¯ ω K μ − λ$
(6)

From the BASTA property (Takagi, 1993), the blocking probability of an arriving taxi is $π − K$; thus, the effective arrival probability of a taxi μeff is given by $μ e f f = μ ( 1 − π − K ) = λ$. Therefore, we calculate the mean taxi queue length L2 and the mean taxi waiting time W2:

$L 2 = ∑ n = − K − 1 ( − n ) π n = K − λ λ ¯ ( 1 − ω K ) μ − λ$
(7)

$W 2 = L 2 μ e f f = K λ − λ ¯ ( 1 − ω K ) μ − λ$
(8)

## 4. OPTIMIZATION

In this section, we discuss passenger’s equilibrium joining strategies and find the optimal taxi buffer size to maximize overall social welfare. From (6) and (8), the (expected) utility functions of a passenger and a taxi are

$U 1 = R − p 1 − C 1 W 1$
(9)

$U 2 = p 1 + p 2 − C f − C 2 W 2$
(10)

### 4.1 Passenger Strategies

Upon arrival, every passenger decides whether to join the queue or balk. In the rest of paper, it is assumed that $R ≥ p 1 + C 1 / μ$, which ensures that the reward exceeds the total cost for an arriving passenger who finds the empty system. We denote Λ as the arrival rate of passengers

#### 4.1.1 Observable Case4.1.1 Observable Case

In the observable case, an arriving passenger is in-formed about the passenger queue length; hence there exist the equilibrium joining strategy of threshold type. A pure threshold strategy is specified by ne, and the join-ing/balking strategy has the form of ‘While arriving, observe the passenger queue length; join if the passenger queue length is smaller than or equal to ne and balk otherwise.’ Based on the reward-cost structure, for an arriving passenger who decides to join the queue, his/her utility is expressed as $U 1 o b ( n ) = R − p 1 − C 1 T ( n )$, where T(n) is the mean waiting time of the passenger who joins the queue, given that he/she encounters n passengers who are already existing. For T(n), it is clearly equal to the n+1 inter-arrival times of taxis; that is, $T ( n ) = ( n + 1 ) / μ$. The passenger’s utility after taking a taxi in equilibrium then equals to 0; i.e., $U 1 o b ( n ) = R − p 1 − C 1 ( n + 1 ) / μ = 0$. Solving $U 1 o b ( n ) = 0$ with respect to n, we obtain

$n e = μ ( R − p 1 ) C 1 − 1$
(11)

where the symbol $⌊ ⌋$ is a floor function.

Next, we consider that the passengers are socially concerned individuals. Socially concerned passengers who care about society will set an optimal buffer (the socially optimal threshold) for themselves to maximize social welfare. In order to maximize social welfare, we derive a stationary queue length distribution, where we define ns as the social joining strategy to be used. Therefore, the state space of the discrete-time Markov chain is . The related transition diagram is depicted in Figure 2

Define the stationary probability as $φ n = lim t → ∞ Pr { N ( t ) = n }$ for $n ∈ Ω s$. Then, the local balance equa-tions governing the system are given by

$φ − K Λ = φ − K + 1 Λ ¯ μ$
(12)

$φ n Λ μ ¯ = φ n + 1 Λ ¯ μ , − K + 1 ≤ n ≤ n s − 1$
(13)

where $Λ ¯ = 1 − Λ$. Solving (12) and (13) recursively using the conventional Birth-Death process (Ross, 1996), we have

$φ − K = 1 − σ 1 − σ γ n s + K$
(14)

$φ n = γ n + K ( 1 − σ ) μ ¯ ( 1 − σ γ n s + K ) , − K + 1 ≤ n ≤ n s$
(15)

where $σ = Λ / μ$ and $γ = σ μ ¯ / Λ ¯$ . Let bp be the blocking probability of an arriving passenger. According to our assumption with regard to the arrival order of passengers and taxis in section 2, we have $b p = μ ¯ φ n s$; thus, the effective arrival probability of a passenger α is given by

$α = Λ ( 1 − b p ) = Λ 1 − γ n s + K ( 1 − σ ) 1 − σ γ n s + K = Λ 1 − γ n s + K 1 − σ γ n s + K$
(16)

Let bt be the blocking probability of an arriving taxi. According to the BASTA property, we have $b t = φ − K$; thus, the effective arrival probability of a taxi β is given by

$β = μ ( 1 − b t ) = μ 1 − 1 − σ 1 − σ γ n s + K = Λ 1 − γ n s + K 1 − σ γ n s + K$
(17)

With (14) and (15), the mean queue lengths for a passenger and a taxi are respectively expressed as

$L 1 o b = ∑ n = 1 n s n φ n = γ K + 1 ( 1 − σ ) μ ¯ ( 1 − γ ) 2 1 − γ n s ( 1 + n s − n s γ ) 1 − σ γ n s + K$
(18)

$L 2 o b = ∑ n = − K − 1 ( − n ) φ n = 1 − σ 1 − σ γ n s + K K − γ ( 1 − K + K γ − γ K ) μ ¯ ( 1 − γ ) 2$
(19)

It follows that the social welfare function is equal to

(20)

Define $n s *$ as the socially optimal threshold strategy which maximizes the social welfare:

$n s * = arg max n s ∈ ℤ + S W o b ( n s )$
(21)

where $ℤ +$ is the positive integer set. Hence, the optimization problem in (21) becomes a nonlinear integer pro-gramming (NLIP) problem. The maximum solution $n s *$ should satisfy the following inequalities:

$S W o b ( n s * ) − S W o b ( n s * + 1 ) ≥ 0 a n d S W o b ( n s * ) − S W o b ( n s * − 1 ) ≥ 0$
(22)

or equivalently,

$n s * ( 1 − γ ) − σ γ K ( 1 − γ n s * ) ≤ M C 1 γ ≤ ( n s * + 1 ) ( 1 − γ ) − σ γ K ( 1 − γ n s * + 1 )$
(23)

where $M = Λ μ ¯ ( 1 − γ ) 2 ( R + p 2 − C f ) + C 2 γ [ K μ ¯ ( 1 − γ ) 2 − γ ( 1 − K + K γ − γ K ) ]$. From (23), it is clear that, when $Λ = μ or γ = 1$, there is no socially optimal threshold. Define δ(n) as a function of n such that $δ ( n ) = n ( 1 − γ ) − σ γ K ( 1 − γ n ) ∀ n ∈ { 0 } ∪ ℤ +$. Because

$δ ( n + 1 ) − δ ( n ) = ( 1 − γ ) + σ γ K + n ( 1 + γ ) > 0$
(24)

the function δ(n) is the increasing in n. If $δ ( 0 ) ≤ M / C 1 γ ≤ δ ( 1 ) , n s = 0$ but it is not optimal because $n s ∈ ℤ +$. Therefore, if $M / C 1 γ ≥ δ ( 1 )$, there exist a unique $n s *$ which satisfies inequalities in (22) or (23). In addition, it is easy to show that, if $M / C 1 γ ≤ δ ( n e ) ,$ then $n s * ≤ n e$; otherwise, $n s * > n e$. Finally, as $n s → ∞$, we have

$lim n s → ∞ S W o b ( n s ) = Λ ( R + p 2 − C f ) − C 1 γ K + 1 ( 1 − σ ) μ ¯ ( 1 − γ ) 2 − C 2 ( 1 − σ ) K − γ ( 1 − K + K γ − γ K ) μ ¯ ( 1 − γ ) 2$
(25)

Thus, we can set the upper bound of $n s *$ as follows:

(26)

where ε is a sufficiently small real number.

To solve (21), we introduce a simulated annealing (SA) algorithm. SA is a probabilistic search method that was introduced by Metropolis et al. (1953). Later, this method was successfully applied to solve optimization problems by Kirkpatrick et al. (1983). For more infor-mation about SA, readers may refer to Aarts and Korst (1997) and Cercignani (1998).

In Pseudocode 1, we present our SA algorithm for finding $n s *$ which maximizes the social welfare. From lines 1 to 5, we set the input parameters and generate the initial state within the search space . The explanation of the input parameters and the states are given below.

• T : temperature

• κ : cooling coefficient

• Itr : maximum number of iteration

• sbest : best stat

• scurrent : current state

• snew : neighbor state

From lines 6 to 19, the SA algorithm execution pro-cedure is described. In line 7, the cooling schedule is shown to be $1 − κ t$, where t is an iterative index. In practice, the cooling coefficient κ usually falls within 0 < κ < 0.3. In this paper, κ is set to 0.01. After the ran-dom neighbor state is generated and its social welfare value is calculated in line 8, we update the current state and its social welfare value from line 9 to line 12 based on the Metropolis criterion. We also check if the current state is the best from lines 13 to 16. Finishing the loop lines 6 to 17, we finally obtain $n s *$ and $S W o b ( n s * )$. When we assume that $R = 100 , p 1 = p 2 = 10 , C 1 = C 2 = 5 , C f = 30 ,$ $Λ = 0.5 , μ = 0.55 , and K = 10$, we obtain the socially optimal threshold strategy $n s * = 6$ with the individual equilibrium threshold strategy ne = 8. We observe that $n s * ≠ n e$, which indicates that the individual threshold strategy does not always match the socially optimal threshold strategy.

#### 4.1.2 Unobservable Case

In the unobservable case, an arriving passenger does not have any information about the passenger queue length when they decide to join or balk. The optimal decision of an arriving passenger must consider the strategies of the other passengers. Because all passengers are assumed to be indistinguishable, we consider the situation as a symmetric game among them. In the present model, there are only two pure strategies: to join or to balk. The strategy is specified by the joining probability of an arriving passenger. In the unobservable case, our goal is to identify the Nash equilibrium joining strategy of the probability type.

Suppose that all passengers follow a joining strategy Λ1. Then, the system behaves as the original, but with arrival probability is Λ1 instead of λ. For the system to be stable, we assume that $Λ 1 < μ$. The corresponding transition diagram is given in Figure 3.

We consider individual passengers. From (6), the mean passenger waiting time is expressed as

$W 1 ( Λ 1 ) = Λ ¯ 1 ω 1 K μ − Λ 1$
(27)

where $ω 1 = ρ 1 μ ¯ / Λ ¯ 1 and ρ 1 = Λ 1 / μ .$ Based on the reward-cost structure, for an arriving passenger who decides to join the queue, his/her utility is

$U 1 u n ( Λ 1 ) = R − p 1 − C 1 W 1 ( Λ 1 )$
(28)

According to (28), $U 1 u n ( Λ 1 )$ depends on Λ1. We can determine the Nash equilibrium strategy of an arriving passenger Λe. To do this, we establish the three cases below.

• Case 1:$R ≤ p 1 + C 1 W 1 ( 0 )$. In this case, even if no other passengers join, the utility of a passenger who joins the queue is non-positive. Therefore, the joining strategy with probability Λe = 0 is an equilibrium strategy, and no other equilibrium is possible. Moreover, in this case, not joining is the dominant strategy.

• Case 2:$R ≥ p 1 + C 1 W 1 ( Λ 1 )$. In this case, even if all potential passengers join, they all enjoy a non-negative benefit. Therefore, the strategy of joining with probability $Λ e = Λ 1$ is an equilibrium strategy, and no other equilibrium is possible. Moreover, in this case, joining is the dominant strategy.

• Case 3:$p 1 + C 1 W 1 ( 0 ) < R < p 1 + C 1 W 1 ( Λ 1 )$. In this case, if $Λ e = Λ 1$, then a passenger who joins suffers a negative benefit. Hence, this cannot be an equilibrium strategy. Likewise, if Λe = 0, a customer who joins obtains a positive benefit, more than by balking. Hence, this cannot be an equilibrium strategy. Therefore, there exists unique equilibrium joining probability Λe satisfying for which customers are indifferent with regard to whether they join or balk.

Next, we consider the case in which passengers are socially concerned. From (9) and (10), the social welfare function can be given by

(29)

Where $μ e f f = μ ( 1 − π − K ) = Λ 1$ according to the BASTA property. Define $Λ 1 *$ as the socially optimal joining strategy which maximizes the social welfare:

$Λ 1 * = arg max Λ 1 ∈ ( 0 , μ ) S W u n ( Λ 1 )$
(30)

Therefore, equation (30) becomes a nonlinear pro-gramming problem. The objective function in (30) is differentiable with respect to Λ1. Its second-order derivative is

$∂ 2 S W u n Λ 1 ∂ Λ 1 2 = − ω 1 K C 1 + C 2 K 2 μ − Λ 1 2 + K μ − Λ 1 Λ 1 μ ¯ + Λ ¯ 1 Λ Λ 1 Λ ¯ 1 μ − Λ 1 3 − 2 μ μ ¯ μ − Λ 1 3 ω 1 K C 1 + C 2 − C 2$
(31)

Investigating equation (31), it is possible that $∂ 2 S W u n ( Λ 1 ) / ∂ Λ 1 2 < 0 or ∂ 2 S W u n ( Λ 1 ) / ∂ Λ 1 2 > 0$ or depending on the value of $ω 1 K ( C 1 + C 2 ) − C 2 .$ For example, when $R = 1000 , p 2 = 10 , C 1 = 1 , C 2 = 50 , C f = 10 , μ = 0.5 ,$ and $K = 10 , ∂ 2 S W u n ( Λ 1 ) / ∂ Λ 1 2 Λ 1 = 0.4 = 19030 > 0$ and $∂ 2 S W u n ( Λ 1 ) / ∂ Λ 1 2 Λ 1 = 0.49 = − 299812 < 0$. Therefore, we cannot determine the convexity/concavity of $S W u n ( Λ 1 )$. To solve (30), we also use the SA algorithm. The SA algorithm to maximize $S W u n ( Λ 1 )$ is described in Pseudocode 2; it is fairly similar to Pseudocode 1 apart from several lines. Hence, we omit the details of Pseudocode 2 here. When we assume that $R = 100 , p 1 = p 2 = 10 , C 1 = C 2 = 5 , C f = 30 , μ = 0.55 ,$ and $K = 10 ,$ we obtain the socially optimal joining strategy of $Λ 1 * = 0.5118 ,$ with the individual equilibrium joining strategy of $Λ e = 0.5356.$ We observe that $Λ 1 * ≠ Λ e$, which indicates that the individual joining strategy is not always consistent with the socially optimal joining strategy.

### 4.2 Government Strategies

We will study the problem of finding an optimal taxi buffer size to maximize the social welfare and guarantee non-negative passenger/taxi utility. Following (9) and (10), the social welfare function is as follows:

(32)

At this point, we can establish the following NLIP problem to maximize the social welfare with respect to K:

(33)

In equation (33), we want to maximize the govern-ment’s social welfare. The first and second constraints guarantee the non-negative passenger and taxi utility outcomes, respectively.

Next, we address the feasibility of (33). It is easy to show that U1(K) means an increase in because $0 < ω < ρ < 1$ and

$U 1 ( K + 1 ) − U 1 ( K ) = C 1 λ ¯ ω K ( 1 − ω ) μ − λ > 0 , ∀ K ∈ ℤ +$
(34)

Thus, if we assume that $U 1 ( 1 ) ≥ 0 ,$ the first con-straint in (33) is always satisfied. Simplifying $U 2 ( K + 1 ) − U 2 ( K )$, we have

$U 2 ( K + 1 ) − U 2 ( K ) = C 2 ω K μ − 1 λ < C 2 ω μ − 1 λ = − ( 1 − ρ ) ( 1 + ρ μ ¯ ) λ λ ¯ < 0 , ∀ K ∈ ℤ +$
(35)

Therefore, U1(K) is a decreasing function of K and there exists an upper bound Kupper which satisfies the following inequality:

(36)

Assuming that $U 2 ( 1 ) ≥ 0$, the second constraint in (33) is always satisfied within the interval of . Summarizing the above analysis, the inequalities should hold for the NLIP problem in (33) to be feasible, and we can rewrite (33) as

$K * = arg max K ∈ S g S W g ( K )$
(37)

where K* is the socially optimal buffer size which maximizes the social welfare and Sg is the search space . To solve (37), we suggest the SA algorithm in Pseudocode 3. Because it is similar to Pseudocodes 1 and 2, we also omit the details of Pseudocode 3 here for brevity. Setting $R = 150 , p 1 = 30 , p 2 = 10 , C 1 = C 2 = 5 , C f = 5 , C f = 10 , λ = 0.6 ,$ and $μ = 0.62$, we obtain the socially optimal buffer size K* = 8. Additionally, the passenger and taxi utility values are $U 1 ( 8 ) = 68.97 and U 2 ( 8 ) = 12.30$, which are both non-negative numbers.

## 5. NUMERICAL EXAMPLES

In this section, we present several numerical exam-ples with which to explore the equilibrium and the opti-mal behavior of passengers in the observable and the unobservable cases and the optimal taxi buffer size from a governmental perspective.

• Example 1. This example deals with the equilibrium joining strategy of an individual passenger and the optimal joining strategy of a socially concerned passenger in the observable case. Initially, we conduct a sensitivity analysis of the taxi arrival probability μ while assuming that $R = 100 , p 1 = p 2 = 10 , C 1 = C 2 = 5 , C f = 30 , Λ = 0.5 ,$ and $K = 10$. Varying the value of μ from 0.4 to 0.6, we determine the equilibrium joining strategy ne and the optimal joining strategy $n s *$, as shown in Figure 4. We observe that both ne and $n s *$ increase monotonically as μ increases. Therefore, as taxis arrive more frequently, it is desirable to raise the passenger joining threshold in terms of both the individual utility of passengers and the overall welfare of society. We also find that $n s * ≤ n e$ because the inequality $M / C 1 γ < δ ( n e )$ holds within the interval .

Next, we consider the passenger arrival probability Λ. Here, we assume that R = 100, p1 = p2 = 10, C1 = C2 = 5, Cf = 30, μ = 0.5, and K = 10. Varying the value of from 0.4 to 0.6, we determine $n e$ and $n s *$ , as pre-sented in Figure 5. According to equation (11), is not a function of ; thus, $n e$ is always equal to $⌊ 0.5 × ( 100 − 10 ) / 5 ⌋ − 1 = 8$ . On the other hand, $n s *$ decreases monotonically as increases, which implies that as passengers arrive more frequently, the passenger joining threshold should decrease to maximize social welfare overall.

• Example 2. In this example, we investigate the equilibrium joining strategy of individual passengers and the optimal joining strategy of socially concerned passengers in the unobservable case. Initially, we conduct a sensitivity analysis of the taxi arrival probability $μ$ , where we assume that $R = 300 ,$ $p 1 = p 2 = 10 ,$ $C 1 = C 2 = 5 ,$ $C f = 30 ,$ and $K = 5.$ Varying the value of from 0.1 to 0.9, we determine the equilibrium joining strategy $Λ e$ and the optimal joining strategy $Λ 1 *$ , as indicated in Figure 6. We find that both Λe and $Λ 1 *$ increase as μ increases. Therefore, it is advantageous for passengers to arrive at the taxi station frequently in order to increase the overall social welfare as well as the utility of individual passengers when a taxi arrives frequently at the taxi station. We also find that $Λ 1 * < Λ e$, which means that the socially optimal joining probability is lower than the individual equilibrium joining probability. Finally, we note that $Λ 1 * < μ and Λ e < μ$ because the system should remain stable.

Next, we examine the effect of the taxi buffer size K on the passenger joining probabilities. We set $R = 300 , p 1 = p 2 = 10 , C 1 = C 2 = 5 , C f = 30 , and μ = 0.5$ Varying the value of Λ from 0.4 to 0.6, we define the values of Λe and $Λ 1 *$, as indicated in Figure 7. This outcome shows that both Λe and $Λ 1 *$ increase as K increases. If the taxi station can accommodate more taxis, more passengers will join the queue to use the taxi service, which benefits not only passengers but also social welfare overall. Figure 7 also confirms that $Λ 1 * < Λ e$, but as the taxi buffer size increases, $Λ 1 *$ grad-ually approaches Λe.

• Example 3. In this example, we analyze the relationship between the optimal taxi buffer size the passenger/ taxi arrival probabilities. Here, we assume that $R = 100 , p 1 = 30 , p 2 = 10 , C 1 = C 2 = 5 , C f = 10 , and λ = 0.48$. Varying the value of μ from 0.5 to 0.8, we obtain the optimal taxi buffer size K* and the maximum social welfare passenger $S W g ( K * )$ , as presented in Figure 8. When μ increases, K* decreases but $S W g ( K * )$ increases. This phenomenon can be explained as follows. As taxis arrive frequently, there are many taxis available at the taxi station; hence, the government does not need to reserve a large number of waiting spaces for taxis. This causes the overall social welfare to increase because the mean taxi waiting time decreases. In addition, when taxis arrive frequently, the mean passenger waiting time is reduced, which has a positive effect on social welfare.

Next, we consider the impact of the passenger arrival on the taxi buffer size, where we set R = 100, p1 = 30, p2 = 10, C1 = C2 = 5, Cf = 10, and μ = 0.81. Varying the value of λ from 0.65 to 0.8, we determine the values of K* and $S W g ( K * ) ,$ as shown in Figure 9. As expected, K* increases when λ increases because, as passengers arrive more frequently, more of a taxi buffer must be provided at the taxi station to reduce passenger waiting times. It is interesting to note that $S W g ( K * )$ initially increase and then sharply decreases after reaching its peak value. When λ = 0.7375, $S W g ( K * )$ reaches its highest value of 65.5042. This can be explained as follows. As passengers arrive frequently, the taxi buffer size should increase, which leads to an increase in the mean taxi waiting time. Therefore, for a large taxi buffer size, social welfare decreases.

## 6. CONCLUSION

In this work, we studied equilibrium joining strate-gies and the social welfare maximization problem in the discrete-time passenger-taxi matching queues. We ana-lyzed passenger strategic joining behaviors in observable and unobservable cases. In the observable case, we provided an equilibrium threshold-type joining strategy for individual passengers and the optimal joining strategy for socially concerned passengers. On the other hand, in the unobservable case, the probability type of strategy was determined and presented. From a governmental perspective, we established the optimal taxi buffer size which maximizes the overall social welfare while also guaranteeing non-negative passenger/taxi utility values. For all social welfare maximization problems, as the taxi fare p1 represents the transfer between passengers and taxi drivers, the objective function does not contain the terms of p1. We also conducted various numerical experiments to offer an insightful operational control strategy.

This paper analyzes passenger equilibrium and op-timality issues. There are various avenues for future research. One can conceive of the strategic and optimal joining behaviors of taxis in both observable and unob-servable cases. Given that taxi drivers are also an im-portant aspect of this system, studying this topic would be a worthy endeavor. Another interesting extension would be to extend our model to the system failure-repair mechanism and to state-dependent passenger/taxi arrivals.

An unrealistic assumption made in this study is the instantaneous service time. In reality, the loading time of the passenger to the taxi cannot be equal to zero. Therefore, the two-dimensional Markov chain considering two passenger’s states; i) waiting state in the queue and ii) loading state to a taxi, has to be analyzed and, as the result, much more complex formulas for the stationary queue length distributions and the performance measures will be derived, which also remains the future study.

## ACKNOWLEDGEMENT

This study was supported by 2017 Research Grant from Kangwon National University (No. 620170024). This work was supported by Basic Science Research through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (NRF-2018R1D1A3B07040887).

## Figure

Transition diagram for the discrete-time passenger-taxi matching queue.

Transition diagram for the discrete-time passenger-taxi matching queue with the social threshold joining strategy.

SA algorithm for finding ns*

Transition diagram for the discrete-time passenger-taxi matching queue in the unobservable.

SA algorithm for finding Λ1*

SA algorithm for finding K*

Joining thresholds vs. taxi arrival probability.

Joining thresholds vs. passenger arrival probability.

Joining probabilities vs. taxi arrival probability.

Joining probabilities vs. taxi buffer size.

Optimal taxi buffer size and maximum social welfare vs. taxi arrival probability.

Optimal taxi buffer size and maximum social welfare vs. passenger arrival probability.

## REFERENCES

1. Aarts, E. and Korst, J. (1997), Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing, John Wiley & Sons, Chichester, England.
2. Afèche, P. , Diamant, A. , and Milner, J. (2014), Double-sided batch queues with abandonment: Modeling crossing networks, Operations Research, 62(5), 1179-1201.
3. Anwar, A. , Volkov, M. , and Rus, D. (2013), Changinow: A mobile application for efficient taxi allocation at airports, Proceedings of the 16th International IEEE Annual Conference on Intelligent Transportation Systems, IEEE Press, The Hague, Netherlands, 694-701.
4. Cercignani, C. (1988), The Boltzmann Equation and Its Applications, Springer Science & Business Media.
5. Conolly, B. W. ,Parthasarathy, P. R. , and Selvaraju, N. (2002), Double-ended queues with impatience, Computers & Operations Research, 29(14), 2053-2072.
6. Crescenzo, A. D. , Giorno, V. , Kumar, B. K. , and Nobile, A. G. (2012), A double-ended queue with catastrophes and repairs, and a jump-diffusion approximation, Methodology and Computing in Applied Probability, 14(4), 937-954.
7. Dobbie, J. M. (1961), A double-ended queuing problem of Kendall, Operations Research, 9(5) 755-757.
8. Giveen, S. M. (1963), A taxicab problem with time-dependent arrival rates, SIAM Review, 5(2), 119-127.
9. Gurvich, I. and Ward, A. (2014), On the dynamic control of matching queues, Stochastic Systems, 4(2), 479-523.
10. Hassin, R. and Haviv, M. (2003), To Queue or Not to Queue: Equilibrium Behavior in Queueing Systems, Springer Science & Business Media, New York.
11. Jain, H. C. (1962), A double-ended queueing system, Defense Science Journal, 12(4), 327-332.
12. Jin, S. and Sun, Y. (2017), System model and performance estimation of dynamic spectrum allocation strategy with multi-channel and imperfect sensing, International Journal of Computer Mathematics, 94(9), 1727-1737.
13. Jin, S. , Chen, S. , and Zhang, J. (2016), Social optimization and pricing policy in cognitive radio networks with an energy saving strategy, Mobile Information Systems, 2016, Article ID: 2426580.
14. Jin, S. , Zhao, Y. , Yue, W. , and Saffer, Z. (2013), Performance analysis and optimization of an adaptive admission control scheme in cognitive radio networks, Mathematical Problems in Engineering, 2013, Article ID: 727310.
15. Kashyap, B. R. K. (1966), The double-ended queue with bulk service and limited waiting space, Operations Research, 14(5), 822-834.
16. Kendall, D. G. (1951), Some problems in the theory of queues, Journal of the Royal Statistical Society Series B: Methodological, 13(2), 151-173.
17. Kirkpatrick, S. , Gelatt, J. , and Vecchi, M. P. (1983), Optimization by simulated annealing, Science, 220(4598), 671-680.
18. Lee, D. H. (2016), On the two-moment approximation of the discrete-time GI/G/1 queue with a single vacation, Discrete Dynamics in Nature and Society, 2016, Article ID: 5345374.
19. Li, Q. , Guo, P. , Li, C. L. , and Song, J. S. (2016), Equilibrium joining strategies and optimal control of a make-to-stock queue, Production and Operations Management, 25(9), 1513-1527.
20. Metropolis, N. , Rosenbluth, A. W. , Rosenbluth, M. N. , Teller, A. H. , and Teller, E. (1953), Equation of state calculations by fast computing machines, The Journal of Chemical Physics, 21(6), 1087-1092.
21. Naor, P. (1969), The regulation of queue size by levying tolls, Econometrica, 37(1), 15-24.
22. Perry, D. and Stadje, W. (1999), Perishable inventory systems with impatient demands, Mathematical Methods in Operational Research, 50(1), 77-90.
23. Ross, S. M. (1996), Stochastic Processes (2nd ed.), John Wiley & Sons, New Jersey, USA.
24. Shi, Y. and Lian, Z. (2016a), Optimization and strategic behavior in a passenger-taxi service system, European Journal of Operational Research, 249(3), 1024-1032.
25. Shi, Y. and Lian, Z. (2016b), Equilibrium strategies and optimal control for a double-ended queue, Asia-Pacific Journal of Operational Research, 33(3), 1-18.
26. Som, P. , Wilhelm, W. E. , and Disney, R. L. (1994), Kitting process in a stochastic assembly system, Queueing Systems, 17(3-4), 471-490.
27. Srivastava, H. M. and Kashyap, B. R. K. (1982), Special Functions in Queueing Theory and Related Stochastic Processes, Academic Press, Massachusetts, USA.
28. Takagi, H. (1993), Queueing Analysis: A Foundation of Performance Evaluation, vol. 3: Discrete-Time Systems, North-Holland, Amsterdam, The Netherlands.
29. Takahashi, M. , Ōsawa, H. , and Fujisawa, T. (2000), On a synchronization queue with two finite buffers, Queueing Systems, 36(1-3), 107-123.
30. Wang, F. , Wang, J. , and Zhang, Z. G. (2017), Strategic behavior and social optimization in a double-ended queue with gated policy, Computers & Industrial Engineering, 114, 264-273.
31. Wong, K. , Wong, S. , Bell, M. , and Yang, H. (2005), Modeling the bilateral micro-searching behavior for urban taxi services using the absorbing markov chain approach, Journal of Advanced Transportation, 39(1), 81-104.
32. Wong, R. , Szeto, W. , and Wong, S. (2014), Bi-level decisions of vacant taxi drivers traveling towards taxi stands in customer-search: Modeling methodology and policy implications, Transport Policy, 33, 73-81.
33. Yang, H. and Yang, T. (2011), Equilibrium properties of taxi markets with search frictions, Transportation Research Part B: Methodological, 45(4), 696-713.
34. Yang, H. , Leung, C. , Wong, S. , and Bell, M. (2010), Equilibria of bilateral taxi-customer searching and meeting on networks, Transportation Research Part B Methodological, 44(8-9), 1067-1083.
35. Zenios, S. A. (1999), Modelling the transplant waiting list: A queueing model with reneging, Queueing Systems, 31(3-4), 239-251.
36. Zhao, Y. and Bai, L. (2017), Performance analysis and optimization for cognitive radio networks with classified secondary users and impatient packets, Mobile Information Systems, 2017, Article ID: 3613496.