Abstract
A system manager makes dynamic pricing and dispatch control decisions in a queueing network model motivated by ride hailing applications. A novel feature of the model is that it incorporates travel times. Unfortunately, this renders the exact analysis of the problem intractable. Therefore, we study this problem in the heavy traffic regime. Under the assumptions of complete resource pooling and common travel time and routing distributions, we solve the problem in closed form by analyzing the corresponding Bellman equation. Using this solution, we propose a policy for the queueing system and illustrate its effectiveness in a simulation study.
Similar content being viewed by others
Notes
The customer demand rate in region i, \(\lambda _i(t)\), depends only on the price \(p_i(t)\).
One can assume \(c_i \ge p_i^* = \Lambda _i^{-1}(\lambda _i^*)\) naturally, where \(\lambda ^*\) is defined in Eq. (23) below.
In particular, for all j, \(\mu _j^* = \sum _{i=1}^{I}\lambda _i^* A_{ij}\). This is true because there exists only one i such that \(A_{ij} \ne 0\) for each \(j=1,\dots , J\). That is, an activity only uses one server. In matrix notation, \(\mu ^* = A^{\prime }\lambda ^*\), where \(A^{\prime }\) is the transpose of A.
Based on intuition from the classical \(M/M/\infty \) queue, this condition implies that the steady-state fraction of jobs in the infinite-server node under the nominal processing plan is equal to one as the number of jobs in the system grows, i.e. as \(n\rightarrow \infty \).
For simplicity, we use the preliminary results from Ata et al. [8] to estimate \(\lambda ^n\) and q (based on a four-year dataset from January 2010 to December 2013). In doing so, we focus on the day shift of the non-holiday weekdays.
The estimated performance and the corresponding confidence interval for the sensitivity analysis is also based on 10 macro-replications where each replication has a run-length of 1000 h (and the statistics of the first 200 h are discarded as a warm-up period).
In particular, the remainder term is given by
$$\begin{aligned} R_{\lambda ^*, 3}\left( \frac{1}{\sqrt{n}}\zeta ^n(s)\right) =\sum _{\begin{array}{c} \alpha _1,\dots , \alpha _I\in \left\{ 0,1,2,3\right\} \\ \text {s.t. }\alpha _1+\cdots + \alpha _I = 3 \end{array}} \frac{\partial ^3 \pi \left( \lambda ^* + \frac{C}{\sqrt{n}}\zeta ^n(s)\right) }{\partial x_1^{\alpha _1}\partial x_2^{\alpha _2}\cdots \partial x_I^{\alpha _I}} \prod _{i=1}^{I}\frac{\left( \frac{1}{\sqrt{n}}\zeta _i^n(s)\right) ^{\alpha _i}}{\alpha _i!}\quad \text {for some}\quad C\in (0,1). \end{aligned}$$
References
Abramowitz, M., Stegun, I.A.: Handbook Mathematical Functions with Formulas, Graphs, and Mathematical Tables. Dover Publications, New York (2003)
Adusumilli, K.M., Hasenbein, J.J.: Dynamic admission and service rate control of a queue. Queueing Syst. 66(2), 131–154 (2010)
Afèche, P., Liu, Z., Maglaras, C.: Ride-hailing networks with strategic drivers: the impact of platform control capabilities on performance. Working Paper (2018)
Afèche, P., Liu, Z., Maglaras, C.: Surge pricing an dynamic matching for hotspot demand shock in ride-hailing networks. Working Paper (2022)
Ata, B.: Dynamic power control in a wireless static channel subject to a quality-of-service constraint. Oper. Res. 53(5), 842–851 (2005)
Ata, B.: Dynamic control of a multiclass queue with thin arrival streams. Oper. Res. 54(5), 876–892 (2006)
Ata, B., Barjesteh, N.: Dynamic pricing of a multiclass make-to-stock queue. Working Paper (2020)
Ata, B., Barjesteh, N., Kumar, S.: Enhancing equitable access to taxis in NYC through search friction reduction and spatial pricing. Working Paper (2019)
Ata, B., Barjesteh, N., Kumar, S.: Dynamic matching and centralized relocation in ridesharing platforms. Working Paper (2020)
Ata, B., Kumar, S.: Heavy traffic analysis of open processing systems with complete resource pooling: asymptotic optimality of discrete review policies. Ann. Appl. Probab. 15(1A), 331–391 (2005)
Ata, B., Harrison, J.M., Shepp, L.A.: Drift rate control of a Brownian processing system. Ann. Appl. Probab. 15(2), 1145–1160 (2005)
Ata, B., Field, J., Lee, D., Tongarlak, M.H.: A dynamic model for managing volunteer engagement. Working Paper (2021)
Ata, B., Lin, W.: Heavy traffic analysis of maximum pressure policies for stochastic processing networks with multiple bottlenecks. Queueing Syst. 59, 191–235 (2008)
Ata, B., Olsen, T.L.: Near-optimal dynamic lead-time quotation and scheduling under convex–concave customer delays. Oper. Res. 57(3), 753–768 (2009)
Ata, B., Olsen, T.L.: Congestion-based leadtime quotation and pricing for revenue maximization with heterogeneous customers. Queueing Syst. 73(1), 35–78 (2013)
Ata, B., Shneorson, S.: Dynamic control of an \(M/M/1\) service system with adjustable arrival and service rates. Manag. Sci. 52(11), 1778–1791 (2006)
Ata, B., Tongarlak, M.H.: On scheduling a multiclass queue with abandonments under general delay costs. Queueing Syst. 74(1), 65–104 (2013)
Ata, B., Zachariadis, K.E.: Dynamic power control in a fading downlink channel subject to an energy constraint. Queueing Syst. 55(1), 41–69 (2007)
Banerjee, S., Freund, D., Lykouris, T.: Pricing and optimization in shared vehicle systems: an approximation framework. Oper. Res. 70(3), 1783–1805 (2021)
Banerjee, S., Kanoria, Y., Qian, P.: Dynamic assignment control of a closed queueing network under complete resource pooling. Working Paper (2020)
Banerjee, S., Riquelme, C., Johari, R.: Pricing in ride-sharing platforms: a queueing-theoretic approach. In: Proceedings of the Sixteenth ACM Conference on Economics and Computation, pp. 639–639 (2015)
Bateman, H., Erdélyi, A.: Higher Transcendental Functions. McGraw-Hill, New York (1953)
Bell, S.L., Williams, R.J.: Dynamic scheduling of a system with two parallel servers in heavy traffic with resource pooling: asymptotic optimality of a threshold policy. Ann. Appl. Probab. 11(3), 608–649 (2001)
Bell, S.L., Williams, R.J.: Dynamic scheduling of a parallel server system in heavy traffic with complete resource pooling: asymptotic optimality of a threshold policy. Electron. J. Probab. 10, 1044–1115 (2005)
Bertsimas, D., Jaillet, P., Martin, S.: Online vehicle routing: the edge of optimization in large-scale applications. Oper. Res. 67(1), 143–162 (2019)
Besbes, O., Castro, F., Lobel, I.: Surge pricing and its spatial supply response. Manag. Sci. 67(3), 1350–1367 (2021)
Besbes, O., Castro, F., Lobel, I.: Spatial capacity planning. Oper. Res. 70(2), 1271–1291 (2021)
Billingsley, P.: Convergence of Probability Measures, 2nd edn. Wiley, New York (1999)
Bimpikis, K., Candogan, O., Saban, D.: Spatial pricing in ride-sharing networks. Oper. Res. 67(3), 744–769 (2019)
Bramson, M.: Stability of Queueing Networks. Springer, Berlin (2008)
Bramson, M., Dai, J.G.: Heavy traffic limits for some queueing networks. Ann. Appl. Probab. 11(1), 49–90 (2001)
Bramson, M., Dai, Williams, R.J.: Two workload properties for Brownian networks. Queueing Syst. 45(3), 191–221 (2003)
Braverman, A., Dai, J.G., Liu, X., Ying, L.: Empty-car routing in ridesharing systems. Oper. Res. 67(5), 1437–1452 (2019)
Browne, S., Whitt, W.: Piecewise-linear diffusion processes. In: Dshalalow, J.H. (ed.) Advances in Queueing: Theory, Methods, and Open Problems, pp. 463–480. CRC Press, Boca Raton (1995)
Cachon, G., Daniels, K., Lobel, R.: The role of surge pricing on a service platform with self-scheduling capacity. Manuf. Serv. Oper. Manag. 19(3), 337–507 (2017)
Castillo, J.C., Knoepfle, D., Weyl, G.: Matching in ride hailing: wild goose chases and how to solve them. Working Paper (2021)
Çelik, S., Maglaras, C.: Dynamic pricing and lead-time quotation for a multiclass make-to-order queue. Manag. Sci. 54(6), 1132–1146 (2008)
Chen, Q., Lei, Y., Jasin, S.: Real-time spatial-intertemporal dynamic pricing for balancing supply and demand in a network. Working Paper (2020)
Chen, M.K., Sheldon, M.: Dynamic pricing in a labor market: surge pricing and flexible work on the Uber platform. In: Proceedings of the 2016 ACM Conference on Economics and Computation (2016)
Dai, J.G., Lin, W.: Maximum pressure policies in stochastic processing networks. Oper. Res. 53(2), 197–218 (2005)
Dai, J.G., Lin, W.: Asymptotic optimality of maximum pressure policies in stochastic processing networks. Ann. Appl. Probab. 18(6), 2239–2299 (2008)
Ethier, S., Kurtz, T.: Markov Processes: Characterization and Convergences. Wiley, New York (2005)
Garg, N., Nazerzadeh, H.: Driver surge pricing. Manag. Sci. 68(5), 3219–3235 (2021)
George, J.M., Harrison, J.M.: Dynamic control of a queue with adjustable service rate. Oper. Res. 49(5), 720–731 (2001)
Gokpinar, B., Selcuk, C.: The selection of prices and commissions in a spatial model of ride-hailing. Working Paper (2019)
Ghosh, A.P., Weerasinghe, A.P.: Optimal buffer size for a stochastic processing network in heavy traffic. Queueing Syst. 55(3), 147–159 (2007)
Ghosh, A.P., Weerasinghe, A.P.: Optimal buffer size and dynamic rate control for a queueing system with impatient customers in heavy traffic. Stoch. Process. Appl. 120(11), 2103–2141 (2010)
Guda, H., Subramanian, U.: Your Uber is arriving: managing on-demand workers through surge pricing, forecast communication, and worker incentives. Manag. Sci. 65(5), 1995–2014 (2019)
Harrison, J.M.: Brownian models of queueing networks with heterogeneous customer populations. In: Fleming, W., Lions, P.-L. (eds.), Stochastic Differential Systems, Stochastic Control Theory and Applications, IMA Volumes in Mathematics and its Applications, vol. 10, pp. 147–186. Springer, New York (1988)
Harrison, J.M.: The BIGSTEP approach to flow management in stochastic processing networks. In: Kelly, F.P., Ziedins, I., Zachary, S. (eds.), Stochastic Networks: Theory and Applications. pp. 57–90. Oxford University Press (1996)
Harrison, J.M.: Heavy traffic analysis of a system with parallel servers: asymptotic optimality of discrete-review policies. Ann. Appl. Probab. 8(3), 822–848 (1998)
Harrison, J.M.: Brownian models of open processing networks: canonical representation of workload. Ann. Appl. Probab. 10(1), 75–103 (2000)
Harrison, J.M.: A broader view of Brownian networks. Ann. Appl. Probab. 13(3), 1119–1150 (2003)
Harrison, J.M.: Brownian Models of Performance and Control. Cambridge University Press, Cambridge (2013)
Harrison, J.M., Wein, L.M.: Scheduling networks of queues: heavy traffic analysis of a simple open network. Queueing Syst. 5(4), 265–280 (1989)
Harrison, J.M., Van Mieghem, J.A.: Dynamic control of Brownian networks: state space collapse and equivalent workload formulation. Ann. Appl. Probab. 7(3), 747–771 (1997)
Harrison, J.M., López, M.J.: Heavy traffic resource pooling in parallel-server systems. Queueing Syst. 33(4), 339–368 (1999)
He, L., Hu, Z., Zhang, M.: Robust repositioning for vehicle sharing. Manuf. Serv. Oper. Manag. 22(2), 241–256 (2020)
Hosseini, M., Milner, J., Romero, G.: Dynamic relocations in car-sharing networks. Working Paper (2021)
Hu, B., Hu, M., Zhu, H.: Surge pricing and two-sided temporal responses in ride-hailing. Manag. Serv. Oper. Manag. 24(1), 91–109 (2022)
Hu, M., Zhou, Y.: Dynamic type matching. Manag. Serv. Oper. Manag. 24(1), 125–142 (2021)
Iglehart, D.: Limiting diffusion approximations for the many server queue and the repairman problem. J. Appl. Probab. 2(2), 429–441 (1965)
Jacob, J., Roet-Green, R.: Ride solo or pool: designing price-service menus for a ride-sharing platform. Eur. J. Oper. Res. 295(3), 1008–1024 (2021)
Karlin, S., Taylor, H.M.: A Second Course in Stochastic Processes. Academic Press, New York (1981)
Kim, J., Ward, A.R.: Dynamic scheduling of a \(GI/GI/1+GI\) queue with multiple customer classes. Queueing Syst. 75(2–4), 339–384 (2013)
Kogan, Y., Lipster, R.: Limit non-stationary behavior of large closed queueing networks with bottlenecks. Queueing Syst. 14(1–2), 33–55 (1993)
Kogan, Y., Liptser, R., Smorodinskii, A.V.: Gaussian diffusion approximation of closed Markov models of computer networks. Probl. Inform. Transm. 22(1), 38–51 (1986)
Korolko, N., Woodard, D., Yan, C., Zhu, H.: Dynamic pricing and matching in ride-hailing platforms. Nav. Res. Logist. 67(8), 705–724 (2020)
Krichagina, A.A., Puhalskii, E.V.: A heavy-traffic analysis of a closed queueing system with a \(GI/\infty \) service center. Queueing Syst. 25(1–4), 235–280 (1997)
Kumar, S.: Two-server closed networks in heavy traffic: diffusion limits and asymptotic optimality. Ann. Appl. Probab. 10(3), 930–961 (2000)
Kumar, R., Lewis, M.E., Topaloglu, H.: Dynamic service rate control for a single-server queue with Markov-modulated arrivals. Nav. Res. Logist. 60(8), 661–677 (2013)
Lu, S.H., Kumar, P.R.: Distributed scheduling based on due dates and buffer priorities. IEEE Trans. Autom. Control 36, 1406–1416 (1991)
Lu, A., Frazier, P., Kislev, O.: Surge pricing moves Uber’s driver partners. In: Proceedings of the 2018 ACM Conference on Economics and Computation (2018)
Mandl, P.: Analytic Treatment of One-Dimensional Markov Processes. Springer, New York (1968)
Momcilovic, P., Mandelbaum, A., Carmeli, N., Armony, M., Yom-Tov, G.: Resource-driven activity-networks (RANs): a modelling framework for complex operations. Working Paper (2023)
New York City Taxi and Limousine Commission: 2014 Taxicab Fact Book. URL https://www.nyc.gov/assets/tlc/downloads/pdf/2014_tlc_factbook.pdf (2014)
Özkan, E.: Joint pricing and matching in ride-sharing systems. Eur. J. Oper. Res. 287(3), 1149–1160 (2020)
Özkan, E., Ward, A.R.: Dynamic matching for real-time ridesharing. Stoch. Syst. 10(1), 29–70 (2020)
Polyanin, A.D., Zaitsev, V.F.: Handbook of Exact Solutions for Ordinary Differential Equations, 2nd edn. CRC Press, Boca Raton (2003)
Rubino, M., Ata, B.: Dynamic control of a make-to-order, parallel-server system with cancellations. Oper. Res. 57(1), 94–108 (2009)
Rybko, A.N., Stolyar, A.L.: Ergodicity of stochastic processes that describe functioning of open queueing networks. Probl. Inform. Transm. 28, 3–26 (1992). ((in Russian))
Smorodinskii, A.V.: Asymptotic distribution of the queue length of one service system (in Russian). Avtom. Telemekhanika 2, 92–99 (1986)
Stidham, S., Weber, R.R.: Monotonic and insensitive optimal policies for control of queues with undiscounted costs. Oper. Res. 37(4), 611–625 (1989)
Stolyar, A.L.: MaxwWeight scheduling in a generalized switch: state space collapse and workload minimization in heavy traffic. Ann. Appl. Probab. 14(1), 1–53 (2004)
Varma, S.M., Bumpensanti, P., Maguluri, S.T., Wang, H.: Dynamic pricing and matching for two-sided queues. Oper. Res. 71(1), 83–100 (2022)
Wang, X., Agatz, N., Erera, A.: Stable matching for dynamic ride-sharing systems. Transp. Sci. 52(4), 850–867 (2017)
Williams, R.J.: Diffusion approximations for open multiclass queueing networks: sufficient conditions involving state space collapse. Queueing Syst. 30(1–2), 27–88 (1998)
Yang, P., Iyer, K., Frazier, P.: Mean field equilibria for resource competition in spatial settings. Stoch. Syst. 8(4), 307–334 (2018)
Zhang, R., Pavone, M.: Control of robotic mobility-on-demand systems: a queueing-theoretical perspective. Int. J. Robot. Res. 35(1–3), 186–203 (2016)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendices
Appendices
Derivations
1.1 Formal derivation of the Brownian control problem
This section provides a formal derivation of the approximating Brownian control problem introduced in Sect. 4. We do not provide a rigorous weak convergence limit theorem. However, the arguments given in support of the approximation can be viewed as a broad outline for such a proof; see Harrison [49, 52, 53] for similar derivations.
We consider a sequence of systems indexed by the system parameter n under the heavy traffic assumption. Then we center the various processes by their mean, scale them appropriately by the system parameter n, and finally pass to the limit as \(n\rightarrow \infty \) formally. To that end, we first define the following (diffusion) scaled processes:
where \(\lfloor x\rfloor \) is the greatest integer less than or equal to x. We also define the following (fluid) scaled processes:
By Donsker’s theorem, the functional central limit theorem for renewal processes, and independence of the stochastic primitives, the processes \({\hat{\Psi }}_i^n\) and \({\hat{N}}_j^n\) converge weakly to independent standard Brownian motions, see Billingsley [28].
As observed in Kogan and Lipster [66], under the heavy traffic assumption, we expect that the number of jobs in the infinite-server node will be n to a first-order approximation. That is, we expect that \({\bar{Q}}^n_0(t)\approx 1\) for \(t\ge 0\) as n gets large. Similarly, we expect the queue lengths at buffers \(1,\dots , I\) to be of order \(\sqrt{n}\). As such, we expect the prices, or equivalently, the demand rates, to deviate from their nominal values only in the second order. That is, we expect \(\lambda _i^n-\lambda ^*_i n = O\left( \sqrt{n}\right) \). Because the demand rates determine the service rates (see Eq. (9)), we expect that \({\bar{\mu }}_j^n(t)\approx \mu _j^*\) for \(t\ge 0\) as n gets large.
By combining Eqs. (145) and (149) with Eqs. (38) and (44), it is straightforward to derive the following scaled system dynamics equations for \(i=1,\dots , I\):
where the second equality holds by Assumption 3 and where the process \(B_i^n\) is given by
Assuming that \(Z_i^n(0)\approx Z_i(0)\) for large n, it is also straightforward to argue that \(B_i^n\) can be approximated by a Brownian motion \(B_i\) with starting state \(Z_i(0)\) that has drift parameter \(\gamma _i={\hat{\eta }}q_i\) and variance parameter
Furthermore, the covariance between the limiting Brownian motion processes is given by
Therefore, replacing \(Z^n\), \(Y^n\), and \(\kappa ^n\), by their formal limits Z, Y, and \(\kappa \), we arrive at the following system dynamics equations in the approximating Brownian control problem for \(i=1,\dots , I\):
Equations (19) and (39) of the system state also imply that \(Z_0^n(t) = -\sum _{i=1}^{I}Z_i^n(t)\) and that \(Z_i^n(t)\ge 0\) for \(i=1,\dots , I\) and \(t\ge 0\). Thus, in the approximating BCP, the following relationships hold for \(t\ge 0\):
Similarly, it is clear that Eqs. (9) and (43) and (44) give rise to Eq. (52) in the BCP; Eqs. (17) and (41) give rise to Eq. (54); and Eq. (42) gives rise to Eq. (51).
To complete the formal derivation of the Brownian control problem, we argue that \({\hat{V}}^n\approx \xi \) for large n, where \({\hat{V}}^n\) and \(\xi \) are given by Eqs. (46) and (47), respectively. First, observe that by Taylor’s theorem we have
where \(R_{\lambda ^*, 3}\left( \frac{1}{\sqrt{n}}\zeta ^n(s)\right) =O(n^{-3/2})\) is a third-order remainder term.Footnote 8 Moreover, note that the term \(\nabla \pi \left( \lambda ^*\right) ^{\prime }\zeta ^n(s)/\sqrt{n}\) vanishes because \(\lambda ^*\) is a maximizer of \(\pi \left( \lambda \right) \) and is in the interior of the feasible region \({\mathcal {L}}\) (see Assumption 2), implying that \(\nabla \pi \left( \lambda ^*\right) =0\). Therefore, we have that
where \(H=-\frac{1}{2}\nabla ^2\pi \left( \lambda ^*\right) \). Using this and Eqs. (35) and (43), it follows that
Finally, using Eqs. (39), (41) and (46), and (150), it is straightforward to derive the following:
Therefore, replacing \({\hat{V}}^n\), \(Z^n\), \(\zeta ^n\), and \(U^n\) by their formal limits \(\xi \), Z, \(\zeta \), and U, we arrive at the following cost process of the approximating Brownian control problem:
Note that it is a diagonal matrix, i.e., \(H=\textrm{diag}(\alpha _1,\ldots ,\alpha _I)\) where
Using this we further simplify the limiting cost process \(\xi (t)\) as follows:
1.2 Derivation of Eq. (143)
Recall that the proposed chosen demand rates are
where \(q(t) = \frac{1}{2\alpha _i}v\left( \frac{W^n(t)}{\sqrt{n}}\right) \). Therefore, the proposed pricing policy for region i is given as follows:
where the third equality follows from the fact that \(\left( \Lambda _i^n\right) ^{-1}(nx) = \Lambda _i^{-1}(x)\) for \(x\in {\mathcal {L}}\). Then note that by Taylor’s theorem we have
which implies that
As an aside, observe that by rearranging terms we have
This implies that our proposed dynamic pricing policy coincides with the static prices to a first-order approximation, but deviates from the static prices on the second order, i.e., order \(1/\sqrt{n}\).
Miscellaneous proofs
Proof of Lemma 1
This proof follows in an almost identical fashion to Lemma 2 in Ata et al. [9], but we include it for completeness. It consists of four steps. We let \(e^n\) denote the nth unit basis vector in a Euclidean space of appropriate dimension. That is, the nth component of \(e^n\) is one, whereas its other components are zero. Moreover, recall from the discuss following Assumption 3 that for a vector \(y\in {\mathbb {R}}^J\), we write \(y = \left( y_B, y_N\right) \) where \(y_B\in {\mathbb {R}}^b\) and \(y_N\in {\mathbb {R}}^{J-b}\).
Step 1: Consider the set of basic activity rates that do not cause any server idleness, i.e., \(\left\{ y\in {\mathbb {R}}^J: By_B=0,\,y_N=0\right\} \). First, we show that this set is the span of \(\bar{\bar{C}}\), defined next:
where \({\bar{C}}=\left\{ \left( j,j^{\prime }\right) : j,\,j^{\prime }\in \left\{ 1,\dots , b\right\} \text { such that }s(j) = s(j^{\prime })\right\} \). That is, \({\bar{C}}\) is the set of all pairs of basic activities undertaken by the same server. Note that the difference \(e^j - e^{j^{\prime }}\) in Eq. (151) captures the trade-off server s(j) makes by increasing the rate at which activity j is undertaken (from its nominal value \(x_j^*\)) at the expense of decreasing the rate of activity \(j^{\prime }\). By making such adjustments to the nominal basic activity rates \(x_B^*\), the system manager can redistribute the workload between buffers b(j) and \(b(j^{\prime })\) without incurring any idleness. As such, we intuitively expect that taking linear combinations of such activity rates in \(\bar{\bar{C}}\) should yield the set of activity rates that do not result in any idleness, i.e., the set \(\left\{ y\in {\mathbb {R}}^J: By_B=0,\,y_N=0\right\} \). In summary, in Step 1 we prove that
To prove this, we show inclusions of both sets. First, let \(y\in \Bigg \{y\in {\mathbb {R}}^J: By_B= 0,y_N =0\Bigg \}\). To prove that \(y\in \text {span}\left( \bar{\bar{C}}\right) \), we show that there exist constants \(a_{jj^{\prime }}\), \((j,j^{\prime })\in {\bar{C}}\), such that \(y = \sum _{(j,j^{\prime })\in {\bar{C}}}a_{jj^{\prime }}\left( e^{j}- e^{j^{\prime }}\right) .\) To find these constants, it will be convenient to define the sets
where \({\mathcal {A}}_i\) is the set of activities undertaken by server i, see Eq. (3). To be more specific, \(\bar{{\mathcal {A}}}_i\) consists of all basic activities undertaken by server i. After possibly relabeling, suppose that the basic activities are ordered so that
where \(0=b_0<b_1<b_2<\cdots < b_{I}=b.\) We define constants \(a_{jj^{\prime }}\) for \((j,j^{\prime })\in {\bar{C}}\) as follows:
Therefore, we have that
the first two equalities following from the definition of the \(a_{jj^{\prime }}\),
the fourth equality from algebraic rearrangements, and the fifth equality from canceling terms. To derive the sixth equality note that y satisfies \(By_B=0\), which implies
Equivalently, we have that
Substituting this for the last term of the fifth equality yields the sixth equality. Finally, the eighth equality from the facts that \(y_N=0\) and that the sets \(\bar{{\mathcal {A}}}_i\), \(i=1,\dots , I\), partition the basic activities. Since \(y = \sum _{j=1}^{J}y_j e^j\), we conclude that \(y\in \text {span}\left( \bar{\bar{C}}\right) \).
Conversely, let \(y\in \text {span}\left( \bar{\bar{C}}\right) \). Then there are constants \(a_{jj^{\prime }}\), \((j,j^{\prime })\in {\bar{C}}\), such that
Since \({\bar{C}}\) consists only of pairs of basic activities, it follows that \(y_N = 0\). Furthermore, for \((j,j^{\prime })\in {\bar{C}}\) and \(i\in \left\{ 1,\dots , I\right\} \), we have
the second equality holding by Eq. (1) and the fourth equality holding since \(s(j) = s(j^{\prime })\). Therefore, \(A\left( e^j - e^{j^{\prime }}\right) =0\) for all \((j,j^{\prime })\in {\bar{C}}\), implying that \(Ay = 0\) by linearity. So, \(y\in \left\{ y\in {\mathbb {R}}^J: Ay= 0,\,y_N =0\right\} \).
Step 2: In this step, we show that \({\mathcal {N}} = \text {span}\left( {\tilde{C}}\right) \), where \({\tilde{C}} = \left\{ Ry: y\in \bar{\bar{C}}\right\} .\) To see this, recall that \({\mathcal {N}} = \left\{ Hy_B: By_B=0,\, y_B\in {\mathbb {R}}^b\right\} = \left\{ Ry: Ay=0,\, y_N=0\right\} .\) Thus, it follows from Step 1 and the definition of \({\tilde{C}}\) that \({\mathcal {N}} = \text {span}\left( {\tilde{C}}\right) \).
Step 3: In this step, we show that \({\tilde{C}} = \Bigg \{\mu _j^*\left( e^{b(j)} - e^{b(j^{\prime })}\right) : \left( j,j^{\prime }\right) \in {\bar{C}},\, e^{b(i)},\,e^{b(j^{\prime })}\in {\mathbb {R}}^I\Bigg \}\). To see this, note that for \((j,j^{\prime })\in {\bar{C}}\) and \(i\in \left\{ 1,\dots , I\right\} \), we have that
the second equality following from Eqs. (2) and (107) and the fourth equality following from the fact that \(s(j) = s(j^{\prime })\) (since \((j,j^{\prime })\in {\bar{C}}\)) and Eq. (24). That is,
Then using the definition of \(\bar{\bar{C}}\), we write
where the last equality follows from Eq. (152). Hence, the result holds. In particular, by the definition of buffer communication, note that
Step 4: We consider the matrix M defined in Lemma 1 (see Eq. (59)) and show that its rows form a basis for \({\mathcal {M}}\). To that end, let \(M^l\), \(l=1,\dots , L\), be the rows of the matrix M given in Eq. (59). Since the buffer pools partition the servers, the rows of M are linearly independent. Thus, to complete the proof, it suffices to show that \({\mathcal {M}}=\text {span}\left( M^1,\dots , M^L\right) \). Recalling that \({\mathcal {M}}= {\mathcal {N}}^{\perp }\) and \({\mathcal {N}} = \text {span}\left( {\tilde{C}}\right) \), it follows that \(a\in {\mathcal {M}}\) if and only if \(a\cdot z = 0\) for all \(z\in {\tilde{C}}\). Moreover, since \(\mu _j^*>0\) for all \(j\in \left\{ 1,\dots , b\right\} \), it follows from Step 3 that
Therefore, \(a\in {\mathcal {M}}\) if and only if \(a_{i} = a_{i^{\prime }}\) for all buffers i and \(i^{\prime }\) that communicate directly.
To prove that \({\mathcal {M}}=\text {span}\left( M^1,\dots , M^L\right) \) we show inclusions of both sets. On the one hand, let \(a\in {\mathcal {M}}\). Then \(a_i = a_{i^{\prime }}\) for all buffers i and \(i^{\prime }\) that communicate directly. By definition of buffer communication, it immediately follows that \(a_i = a_{i^{\prime }}\) for all buffers i and \(i^{\prime }\) that communicate. That is, \(a_i = a_{i^{\prime }}\) for all buffers i and \(i^{\prime }\) that are in the same buffer pool. Thus, \(a\in \text {span}\left( M^1,\dots , M^L\right) \), implying that \({\mathcal {M}}\subseteq \text {span}\left( M^1,\dots , M^L\right) \). On the other hand, to show that \(\text {span}\left( M^1,\dots , M^L\right) \subseteq {\mathcal {M}}\), it suffices to show that \(M^l\in {\mathcal {M}}\) for each \(l=1,\dots , L\). To that end, it is enough to show that \(M^l_{i} = M^l_{i^{\prime }}\) for all buffers i and \(i^{\prime }\) that communicate directly. However, this trivially holds by Eq. (59), since buffers i and \(i^{\prime }\) that communicate directly are in the same buffer pool. Thus, \(\text {span}\left( M^1,\dots , M^L\right) \subseteq {\mathcal {M}}.\) \(\square \)
Proof of Lemma 2
It is enough to show that \((MR)_{lj}=(GA)_{lj}\) for all \(l=1,\dots , L\) and \(j=1,\dots , J\), where G is given by Eq. (60). Indeed, by Eqs. (122), (116), and (59),
On the other hand, by Eqs. (120) and (60),
Note that by Eq. (24) we have \(\mu _j^*=\lambda ^*_{s(j)}\) and by Eq. (58) we have that \(b(j)\in {\mathcal {P}}_l\) if and only if \(s(j)\in {\mathcal {S}}_l\). Thus, the desired result immediately follows by Eqs. (153) and (154). \(\square \)
Proof of Lemma 3
When \(L=1\), all buffers are in a single buffer pool. Thus, it follows immediately from Eq. (59) that \(M= e^{\prime }\). Furthermore, by definition of buffer communication and Eq. (58), there is a single server pool. It then follows from Eq. (60) that \(G=\left( \lambda ^*\right) ^{\prime }\).
To prove the first relationship in Eq. (69), note that
where the second equality follows from \(M=e^{\prime }\) and where the fourth equality follows from the fact that q is a probability vector. To prove the second relationship in Eq. (69), first note that \(MC=e^{\prime }\in {\mathbb {R}}^J\). This follows from \(M=e^{\prime }\in {\mathbb {R}}^I\), the definition of C in Eq. (142), and the fact that C has one nonzero element per column. Therefore,
the fourth equality following from the heavy traffic assumption, see Eq. (29). \(\square \)
Proof of Lemma 4
This is a straightforward convex optimization problem. Forming the Lagrangian
where \(\nu \) is the Lagrange multiplier, the necessary first-order conditions then give
Substituting this into the constant \(e'\zeta =x\) yields \(\nu =2x/{\hat{\alpha }}\) and
The optimality of this solution follows from the convexity of the objective. Substituting (155) in the objective function yields \(c(x)=x^2/{\hat{\alpha }}\) as desired. \(\square \)
Proof of Proposition 1
Let \((Y,\zeta )\) be an admissible control for (48) and (54) with the corresponding state process Z and idleness process U. Letting \(W(t)=MZ(t)\) for \(t\ge 0\), (48) implies that (65) holds, and (64) holds by definition. Similarly, (66) and (67) follow from (53) and (54) whereas (68) follows from (52). Thus, \((Z, U, \zeta )\) of the BCP formulation (48) and (54) is an admissible policy for the RBCP (63) and (68). Because the two formulations have the same process \(Z, U, \zeta \), they have the same cost.
The converse follows exactly as in (the second part of) the proof of Theorem 1 in Harrison and Van Mieghem [56] (see pages 753–754) with the only substantive difference being (aside from the obvious notational differences) the process X on their Eq. (36) on page 755 is replaced with
in our setting. Then following the same steps in their proof shows that the analogy of the process Y (in our setting) defined as in their Eq. (35) and \(\zeta \) is admissible for our BCP (48) and (54). Moreover, because \((Y, \zeta )\) results in the same queue length process Z. Its cost is the same as that of the policy \((Z, U, \zeta )\) for RBCP (63) and (68). \(\square \)
Proof of Proposition 2
Given an admissible policy \(\theta \) for EWF and the corresponding process W, L, we set \(Z_{i^*}\equiv W\) and \(Z_i\equiv 0\) for \(i\not = i^*\) and \(U_{k^*} \equiv L\) and \(U_k\equiv 0\) for \(k\not = k^*\). Moveover, we set \(\zeta _i(s)=\theta (s)/(\alpha _i {\hat{\alpha }}_i)\) for \(i=1,\ldots , I\), which results in \(\sum _{i=1}^I \alpha _i \zeta _i^2 (s) = c(\theta (s))\) by Lemma 4. Then it follows from (77) and (78) that \((Z, U, \zeta )\) has the same cost in RBCP as \(\theta \) does in EWF.
To prove the converse, let \(Z, U, \zeta \) be an admissible policy for RBCP, and let
It is easy to verify that \(\theta (\cdot )\) is admissible for EWF. Moreover, \(c(\theta (s))\le \sum _{i=1}^I \alpha _i \zeta _i^2 (s)\) by Lemma 4 and that \(h W(s) \le \sum _{i=1}^I (h_i-h_0) Z_i(s)\) and \(r L(s)\le c' U(s)\) for \(s\ge 0\). Thus, the cost of \(\theta \) for the EWF is less than or equal to that of the policy \((Z, U, \zeta )\) for the RBCP. \(\square \)
Proof of Proposition 3
Consider the auxiliary stationary reflected diffusion on \([0,\infty )\), denoted by \(\left\{ {\tilde{W}}(t),\,t\ge 0\right\} \), associated with the drift rate function \(-\left( \eta y -a + \theta ^*(y)\right) \) and variance parameter \(\sigma ^2\). As noted on pages 470–471 of Browne and Whitt [34]—also see Mandl [74] and Karlin and Taylor [64]—its probability density function, denoted by \(\varphi \), is given as follows:
provided all integrals are finite, which we verify next. To this end, let \(k=\inf \left\{ y\ge 0: v(y)\ge 0\right\} \) where \((v,\beta ^*)\) solve the Bellman equation (89) and (90), and note from Eq. (90) that \(-r\le v(y)\le 0\) for \(y\le k\) and \(0\le v(y) \le h/\eta \) for \(y\ge k\). In order to verify the integrals above are finite, using Eq. (91) note that
from which we also deduce that the integral in the denominator of the right hand side of Eq. (123) is finite. Moreover, it follows from Eq. (157) that the stationary diffusion \({\tilde{W}}\) has finite moments. In particular,
Next, we define another auxiliary stationary diffusion, denoted by \({\tilde{W}}^*\), as follows:
Noting \(W^*(0)<{\tilde{W}}^*(0)\) almost surely, we define the stopping time \(\tau \) as follows:
and introduce the following process:
By the strong Markov property of diffusions, \({\hat{W}}^*\) has the same distribution as \(W^*\). Moreover,
Therefore, we conclude that
where the second equality follows from the definition of \({\tilde{W}}^*\), the third equality from the stationarity of \({\tilde{W}}\), and the last equality from Eq. (158). Thus, we conclude from \(W^*(t)\ge 0\) for \(t\ge 0\) and Eq. (159) that
as desired. \(\square \)
The next lemma aids in the proof of Lemma 6. To state the result, it will be convenient to rewrite Eqs. (103) and (104) as follows:
where \(q_0(x)=\frac{2}{\sigma ^2}\left( \beta - hx\right) \), \(q_1(x)=\frac{2}{\sigma ^2}(\eta x-a)\), and \( q_2=\frac{{\hat{\sigma }}}{2\sigma ^2}>0\) for \(x\ge 0\).
Lemma 23
For each \(v\in C^1[0,\infty )\) satisfying Eqs. (160) and (161), \(y(x) = \exp \left\{ -q_2\int _{0}^{x}v(t)\,dt\right\} \) satisfies
Conversely, for each \(y\in C^2[0,\infty )\) satisfying Eqs. (162) and (163), \(v=-y^{\prime }/(q_2y)\) satisfies Eqs. (160)–(161).
Proof of Lemma 23
Let \(v\in C^1[0,\infty )\) satisfy Eqs. (160) and (161) and let \(y(x) = \exp \left\{ -q_2\int _{0}^{x}v(t)\,dt\right\} \). Then it follows that
Moreover, \(y(0) = \exp \left\{ -q_2\cdot 0\right\} = 1\) and \(y^{\prime }(0) = -q_2\exp \left\{ -q_2\cdot 0\right\} v(0) = rq_2\).
On the other hand, let \(y\in C^2[0,\infty )\) satisfy Eqs. (162) and (163) and let \(v=-y^{\prime }/(q_2y)\). Then it follows that
Moreover, \(v(0) = -y^{\prime }(0)/\left( q_2y(0)\right) = -\left( rq_2\right) /\left( q_2\cdot 1\right) =-r\). This completes the proof.\(\square \)
Proof of Lemma 6
It is known that Eqs. (162) and (163) can be transformed into a degenerate hypergeometric equation known as a Kummer’s equation; see Polyanin and Zaitsev [79]. Such equations are known to have confluent hypergeometric function solutions; see Bateman and Erdélyi [22] and Abramowitz and Stegun [1]. It then follows from Lemma 23 that Eqs. (160) and (161) have a solution v. To complete the proof, we must show that the solution v to Eqs. (160) and (161) is unique. To this end, define the function f by
To prove uniqueness, it is enough to show that f is locally Lipschitz in v, i.e., that f is Lipschitz in v when restricted to the compact domain \([0,N]\times [-M, M]\) where \(N,M>0\). More specifically, local Lipschitzness will demonstrate uniqueness on each compact interval, which can then be easily extended to the positive real line. To this end, for \(x\in [0,N]\) and \(v_1,v_2\in [-M,M]\) we have that
Thus, f is locally Lipschitz in v. This completes the proof.\(\square \)
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Alwan, A.A., Ata, B. & Zhou, Y. A queueing model of dynamic pricing and dispatch control for ride-hailing systems incorporating travel times. Queueing Syst 106, 1–66 (2024). https://doi.org/10.1007/s11134-023-09901-y
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11134-023-09901-y