An incentive algorithm for a closed stochastic network: data and mean-field analysis. (English) Zbl 1540.60203
Summary: The paper deals with a load-balancing algorithm for a closed stochastic network with two zones with different demands. The algorithm is motivated by an incentive algorithm for redistribution of cars in a large-scale car-sharing system. The service area is divided into two zones. When cars stay too long in the low-demand zone, users are encouraged to pick them up and return them in the high-demand zone. The zones are divided in cells called stations. The cars are the network customers. The mean-field limit solution of an ordinary differential equation (ODE) gives the large-scale distribution of the station state in both clusters for this incentive policy in a discrete Markovian framework. An equilibrium point of this ODE is characterized via the invariant measure of a random walk in the quarter-plane. The proportion of empty and saturated stations measures how the system is balanced. Numerical experiments illustrate the impact of the incentive policy. Our study shows that the incentive policy helps when the high-demand zone observes a lack of cars but a saturation must be prevented especially when the high-demand zone is small.
MSC:
| 60K25 | Queueing theory (aspects of probability theory) |
| 90B22 | Queues and service in operations research |
Keywords:
large scale analysis; mean-field; car-sharing; incentive algorithm; stochastic network; cluster; load balancing; closed Jackson networks; product-form distributionReferences:
| [1] | Fricker, C., Gast, N., Mohamed, H.: Mean field analysis for inhomogeneous bike sharing systems. In: Discrete Mathematics & Theoretical Computer Science Proceedings, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA’12) (2012) · Zbl 1296.90019 |
| [2] | Gast, N., Expected values estimated via mean-field approximation are 1/n-accurate, Proc. ACM Meas. Anal. Comput. Syst., 1, 1, 1-26, 2017 · doi:10.1145/3084454 |
| [3] | Gast, N.; Van Houdt, B., A refined mean field approximation, Proc. ACM Meas. Anal. Comput. Syst., 1, 2, 1-28, 2017 · doi:10.1145/3154491 |
| [4] | Gast, N.; Bruno, G., A mean field model of work stealing in large-scale systems, ACM SIGMETRICS Perform. Eval. Rev., 38, 1, 13-24, 2010 · doi:10.1145/1811099.1811042 |
| [5] | Mukhopadhyay, A., Mazumdar, R.R., Roy, R.: Binary opinion dynamics with biased agents and agents with different degrees of stubbornness. In: 2016 28th International Teletraffic Congress (ITC 28), vol. 1, pp. 261-269. IEEE (2016) |
| [6] | Gordon, WJ; Newell, GF, Closed queueing systems with exponential servers, Oper. Res., 15, 2, 254-265, 1967 · Zbl 0168.16603 · doi:10.1287/opre.15.2.254 |
| [7] | Jackson, JR, Jobshop-like queueing systems, Manag. Sci., 10, 1, 131-142, 1963 · doi:10.1287/mnsc.10.1.131 |
| [8] | Economou, A.; Fakinos, D., Product form stationary distributions for queueing networks with blocking and rerouting, Queueing Syst. Theory Appl., 30, 251-260, 1998 · Zbl 0919.90064 · doi:10.1023/A:1019117121530 |
| [9] | Fricker, C.; Tibi, D., Equivalence of ensembles for large vehicle-sharing models, Ann. Appl. Probab., 27, 2, 883-916, 2017 · Zbl 1370.60166 · doi:10.1214/16-AAP1219 |
| [10] | Fayolle, G.; Lasgouttes, J-M, Asymptotics and scalings for large product-form networks via the central limit theorem, Markov Process. Relat. Fields, 2, 317-348, 1996 · Zbl 0902.60080 |
| [11] | George, DK; Xia, CH, Asymptotic analysis of closed queueing networks and its implications to achievable service levels, SIGMETRICS Perform. Eval. Rev., 38, 3-5, 2010 · doi:10.1145/1870178.1870180 |
| [12] | Wielinski, G.; Trépanier, M.; Morency, C., Exploring service usage and activity space evolution in a free-floating carsharing service, Transp. Res. Rec., 2673, 8, 36-49, 2019 · doi:10.1177/0361198118825465 |
| [13] | Fricker, C., Mohamed, H., Popescu, T., Trépanier, M.: Stochastic modelling of free-floating car-sharing systems. CIRRELT (2021) |
| [14] | Powers, D.M.W.: Applications and explanations of Zipf’s law. In: New Methods in Language Processing and Computational Natural Language Learning (1998). https://aclanthology.org/W98-1218 |
| [15] | Ethier, S.N., Kurtz, T.G.: Markov Processes: Characterization and Convergence. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. Wiley, New York (1986) · Zbl 0592.60049 |
| [16] | Kelly, FP, Loss networks, Ann. Appl. Probab., 1, 3, 319-378, 1991 · Zbl 0743.60099 · doi:10.1214/aoap/1177005872 |
| [17] | Robert, P., Stochastic Networks and Queues. Applications of Mathematics: Stochastic Modelling and Applied Probability, 2003, Berlin: Springer, Berlin · Zbl 1038.60091 · doi:10.1007/978-3-662-13052-0 |
| [18] | Fayolle, G.; Iasnogorodski, R.; Malyshev, V., Random Walks in the Quarter Plane: Algebraic Methods, Boundary Value Problems, Applications to Queueing Systems and Analytic Combinatorics, 2003, Berlin: Springer, Berlin |
| [19] | Fricker, C.; Gast, N., Incentives and redistribution in homogeneous bike-sharing systems with stations of finite capacity, Euro J. Transp. Logist., 5, 3, 261-291, 2016 · doi:10.1007/s13676-014-0053-5 |
| [20] | Baccelli, F., Foss, S., Shneer, V.: Migration-contagion processes. arXiv preprint arXiv:2208.03512 (2022) · Zbl 07807057 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
