Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Queueing Systems
Erschienen in: Queueing Systems 1-2/2024

04.02.2024

A queueing model of dynamic pricing and dispatch control for ride-hailing systems incorporating travel times

verfasst von: Amir A. Alwan, Baris Ata, Yuwei Zhou

Erschienen in: Queueing Systems | Ausgabe 1-2/2024

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.
Nächster Artikel Some reflected autoregressive processes with dependencies

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
The customer demand rate in region i, \(\lambda _i(t)\), depends only on the price \(p_i(t)\).
 
2
One can assume \(c_i \ge p_i^* = \Lambda _i^{-1}(\lambda _i^*)\) naturally, where \(\lambda ^*\) is defined in Eq. (23) below.
 
3
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.
 
4
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 \).
 
5
The first equality in (35) is proved by applying (34) and noting that \(\left( \Lambda ^n\right) ^{-1}(nx) = \Lambda ^{-1}(x)\) for \(x\in {\mathcal {L}}\). The second equality in (35) then follows by (7).
 
6
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.
 
7
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).
 
8
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}$$
 
Literatur
1.
Abramowitz, M., Stegun, I.A.: Handbook Mathematical Functions with Formulas, Graphs, and Mathematical Tables. Dover Publications, New York (2003)
2.
Adusumilli, K.M., Hasenbein, J.J.: Dynamic admission and service rate control of a queue. Queueing Syst. 66(2), 131–154 (2010)MathSciNetCrossRef
3.
Afèche, P., Liu, Z., Maglaras, C.: Ride-hailing networks with strategic drivers: the impact of platform control capabilities on performance. Working Paper (2018)
4.
Afèche, P., Liu, Z., Maglaras, C.: Surge pricing an dynamic matching for hotspot demand shock in ride-hailing networks. Working Paper (2022)
5.
Ata, B.: Dynamic power control in a wireless static channel subject to a quality-of-service constraint. Oper. Res. 53(5), 842–851 (2005)MathSciNetCrossRef
6.
7.
Ata, B., Barjesteh, N.: Dynamic pricing of a multiclass make-to-stock queue. Working Paper (2020)
8.
Ata, B., Barjesteh, N., Kumar, S.: Enhancing equitable access to taxis in NYC through search friction reduction and spatial pricing. Working Paper (2019)
9.
Ata, B., Barjesteh, N., Kumar, S.: Dynamic matching and centralized relocation in ridesharing platforms. Working Paper (2020)
10.
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)MathSciNetCrossRef
11.
Ata, B., Harrison, J.M., Shepp, L.A.: Drift rate control of a Brownian processing system. Ann. Appl. Probab. 15(2), 1145–1160 (2005)MathSciNetCrossRef
12.
Ata, B., Field, J., Lee, D., Tongarlak, M.H.: A dynamic model for managing volunteer engagement. Working Paper (2021)
13.
Ata, B., Lin, W.: Heavy traffic analysis of maximum pressure policies for stochastic processing networks with multiple bottlenecks. Queueing Syst. 59, 191–235 (2008)MathSciNetCrossRef
14.
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)CrossRef
15.
Ata, B., Olsen, T.L.: Congestion-based leadtime quotation and pricing for revenue maximization with heterogeneous customers. Queueing Syst. 73(1), 35–78 (2013)MathSciNetCrossRef
16.
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)CrossRef
17.
Ata, B., Tongarlak, M.H.: On scheduling a multiclass queue with abandonments under general delay costs. Queueing Syst. 74(1), 65–104 (2013)MathSciNetCrossRef
18.
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)MathSciNetCrossRef
19.
Banerjee, S., Freund, D., Lykouris, T.: Pricing and optimization in shared vehicle systems: an approximation framework. Oper. Res. 70(3), 1783–1805 (2021)MathSciNetCrossRef
20.
Banerjee, S., Kanoria, Y., Qian, P.: Dynamic assignment control of a closed queueing network under complete resource pooling. Working Paper (2020)
21.
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)
22.
Bateman, H., Erdélyi, A.: Higher Transcendental Functions. McGraw-Hill, New York (1953)
23.
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)MathSciNetCrossRef
24.
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)MathSciNetCrossRef
25.
Bertsimas, D., Jaillet, P., Martin, S.: Online vehicle routing: the edge of optimization in large-scale applications. Oper. Res. 67(1), 143–162 (2019)MathSciNetCrossRef
26.
Besbes, O., Castro, F., Lobel, I.: Surge pricing and its spatial supply response. Manag. Sci. 67(3), 1350–1367 (2021)CrossRef
27.
28.
Billingsley, P.: Convergence of Probability Measures, 2nd edn. Wiley, New York (1999)CrossRef
29.
Bimpikis, K., Candogan, O., Saban, D.: Spatial pricing in ride-sharing networks. Oper. Res. 67(3), 744–769 (2019)MathSciNetCrossRef
30.
Bramson, M.: Stability of Queueing Networks. Springer, Berlin (2008)
31.
Bramson, M., Dai, J.G.: Heavy traffic limits for some queueing networks. Ann. Appl. Probab. 11(1), 49–90 (2001)MathSciNetCrossRef
32.
Bramson, M., Dai, Williams, R.J.: Two workload properties for Brownian networks. Queueing Syst. 45(3), 191–221 (2003)MathSciNetCrossRef
33.
Braverman, A., Dai, J.G., Liu, X., Ying, L.: Empty-car routing in ridesharing systems. Oper. Res. 67(5), 1437–1452 (2019)MathSciNetCrossRef
34.
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)
35.
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)CrossRef
36.
Castillo, J.C., Knoepfle, D., Weyl, G.: Matching in ride hailing: wild goose chases and how to solve them. Working Paper (2021)
37.
Çelik, S., Maglaras, C.: Dynamic pricing and lead-time quotation for a multiclass make-to-order queue. Manag. Sci. 54(6), 1132–1146 (2008)CrossRef
38.
Chen, Q., Lei, Y., Jasin, S.: Real-time spatial-intertemporal dynamic pricing for balancing supply and demand in a network. Working Paper (2020)
39.
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)
40.
Dai, J.G., Lin, W.: Maximum pressure policies in stochastic processing networks. Oper. Res. 53(2), 197–218 (2005)MathSciNetCrossRef
41.
Dai, J.G., Lin, W.: Asymptotic optimality of maximum pressure policies in stochastic processing networks. Ann. Appl. Probab. 18(6), 2239–2299 (2008)MathSciNetCrossRef
42.
Ethier, S., Kurtz, T.: Markov Processes: Characterization and Convergences. Wiley, New York (2005)
43.
Garg, N., Nazerzadeh, H.: Driver surge pricing. Manag. Sci. 68(5), 3219–3235 (2021)CrossRef
44.
George, J.M., Harrison, J.M.: Dynamic control of a queue with adjustable service rate. Oper. Res. 49(5), 720–731 (2001)MathSciNetCrossRef
45.
Gokpinar, B., Selcuk, C.: The selection of prices and commissions in a spatial model of ride-hailing. Working Paper (2019)
46.
Ghosh, A.P., Weerasinghe, A.P.: Optimal buffer size for a stochastic processing network in heavy traffic. Queueing Syst. 55(3), 147–159 (2007)MathSciNetCrossRef
47.
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)MathSciNetCrossRef
48.
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)
49.
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)
50.
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)
51.
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)MathSciNetCrossRef
52.
Harrison, J.M.: Brownian models of open processing networks: canonical representation of workload. Ann. Appl. Probab. 10(1), 75–103 (2000)MathSciNetCrossRef
53.
54.
Harrison, J.M.: Brownian Models of Performance and Control. Cambridge University Press, Cambridge (2013)CrossRef
55.
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)MathSciNetCrossRef
56.
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)MathSciNetCrossRef
57.
Harrison, J.M., López, M.J.: Heavy traffic resource pooling in parallel-server systems. Queueing Syst. 33(4), 339–368 (1999)MathSciNetCrossRef
58.
He, L., Hu, Z., Zhang, M.: Robust repositioning for vehicle sharing. Manuf. Serv. Oper. Manag. 22(2), 241–256 (2020)CrossRef
59.
Hosseini, M., Milner, J., Romero, G.: Dynamic relocations in car-sharing networks. Working Paper (2021)
60.
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)CrossRef
61.
Hu, M., Zhou, Y.: Dynamic type matching. Manag. Serv. Oper. Manag. 24(1), 125–142 (2021)CrossRef
62.
Iglehart, D.: Limiting diffusion approximations for the many server queue and the repairman problem. J. Appl. Probab. 2(2), 429–441 (1965)MathSciNetCrossRef
63.
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)MathSciNetCrossRef
64.
Karlin, S., Taylor, H.M.: A Second Course in Stochastic Processes. Academic Press, New York (1981)
65.
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)MathSciNetCrossRef
66.
Kogan, Y., Lipster, R.: Limit non-stationary behavior of large closed queueing networks with bottlenecks. Queueing Syst. 14(1–2), 33–55 (1993)CrossRef
67.
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)
68.
Korolko, N., Woodard, D., Yan, C., Zhu, H.: Dynamic pricing and matching in ride-hailing platforms. Nav. Res. Logist. 67(8), 705–724 (2020)MathSciNetCrossRef
69.
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)MathSciNetCrossRef
70.
Kumar, S.: Two-server closed networks in heavy traffic: diffusion limits and asymptotic optimality. Ann. Appl. Probab. 10(3), 930–961 (2000)ADSMathSciNetCrossRef
71.
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)MathSciNetCrossRef
72.
Lu, S.H., Kumar, P.R.: Distributed scheduling based on due dates and buffer priorities. IEEE Trans. Autom. Control 36, 1406–1416 (1991)CrossRef
73.
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)
74.
Mandl, P.: Analytic Treatment of One-Dimensional Markov Processes. Springer, New York (1968)
75.
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)
76.
77.
Özkan, E.: Joint pricing and matching in ride-sharing systems. Eur. J. Oper. Res. 287(3), 1149–1160 (2020)MathSciNetCrossRef
78.
79.
Polyanin, A.D., Zaitsev, V.F.: Handbook of Exact Solutions for Ordinary Differential Equations, 2nd edn. CRC Press, Boca Raton (2003)
80.
Rubino, M., Ata, B.: Dynamic control of a make-to-order, parallel-server system with cancellations. Oper. Res. 57(1), 94–108 (2009)MathSciNetCrossRef
81.
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))
82.
Smorodinskii, A.V.: Asymptotic distribution of the queue length of one service system (in Russian). Avtom. Telemekhanika 2, 92–99 (1986)MathSciNet
83.
Stidham, S., Weber, R.R.: Monotonic and insensitive optimal policies for control of queues with undiscounted costs. Oper. Res. 37(4), 611–625 (1989)MathSciNetCrossRef
84.
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)MathSciNetCrossRef
85.
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)
86.
Wang, X., Agatz, N., Erera, A.: Stable matching for dynamic ride-sharing systems. Transp. Sci. 52(4), 850–867 (2017)CrossRef
87.
Williams, R.J.: Diffusion approximations for open multiclass queueing networks: sufficient conditions involving state space collapse. Queueing Syst. 30(1–2), 27–88 (1998)MathSciNetCrossRef
88.
Yang, P., Iyer, K., Frazier, P.: Mean field equilibria for resource competition in spatial settings. Stoch. Syst. 8(4), 307–334 (2018)MathSciNetCrossRef
89.
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)CrossRef
Metadaten
Titel
A queueing model of dynamic pricing and dispatch control for ride-hailing systems incorporating travel times
verfasst von
Amir A. Alwan
Baris Ata
Yuwei Zhou
Publikationsdatum
04.02.2024
Verlag
Springer US
Erschienen in
Queueing Systems / Ausgabe 1-2/2024
Print ISSN: 0257-0130
Elektronische ISSN: 1572-9443
DOI
https://doi.org/10.1007/s11134-023-09901-y

Premium Partner

    Bildnachweise