Research on Mean Field Limit Theory and Queuing Modelfor Large-Scale Bike-Sharing Systems

doi:10.12005/orms.2017.0144

Abstract

Abstract: With rapid growth of population and high urbanization of living space, an environmental pollution has been a main factor affecting the sustainable development of human society, in which the automobile exhaust pollution is a large problem. Based on this, bike-sharing systems have received a higher attention and gained rapid development in many major cities of many countries in the world over the past decade. However, few researches on the large bike-sharing systems have been done, and there is one main reason why such a bike-sharing system is always a very complex system including a complicated heavy traffic in each city, heterogeneous operation environments, different customer preference, revenue management of bike enterprises and so on. In this paper, we study a universal large-scale bike-sharing system, and propose an effective analytic method of stochastic model through combining the mean field limit theory and the queuing models. To this end, we develop some new stochastic analytic techniques, which are organized as follows: Establishing a time-inhomogeneous queuing system by means of the mean field theory, analyzing an empirical measure process through a nonlinear birth-death process, computing the fixed point in terms of a segment-structured birth-death process, and discussing the steady-state probability of the problem stations. Therefore, we provide a promising research direction in the study of stochastic models with respect to the large bike-sharing systems, and also hope this method can be applied to analyzing more general large bike-sharing systems.

Key words: bike-sharing system, queuing system, mean field, nonlinear birth-death process, fixed point, problem station

摘要： 人口的快速增长与空间的高度城市化带来了汽车尾气污染等环境污染问题,这已成为影响社会可持续发展的主要制约因素。基于此,近十年来自行车共享系统在世界多个国家的许多重要城市获得了高度重视并取得了迅速发展。然而,相比于自行车共享系统的快速发展,其相关研究却并未取得较大进展,主要原因在于它是一个大型的复杂系统,涉及密集的城市交通、异构的运营环境、多重的顾客偏好选择以及多渠道的收益管理等多种关联因素。在这种背景下,本文建立了一个通用的大型自行车共享系统,并提出了一种基于平均场极限理论与非时齐排队模型相结合的有效随机模型分析方法,包括利用平均场理论建立了非时齐排队系统、构建了经验测度过程(Empirical measure process)的非线性生灭过程、给出了分段结构下生灭过程的固定点的“几何之和”算法以及提供了问题站点稳态概率的数值计算等等。本文为研究大型自行车共享系统的随机模型提供了一个重要的发展途径,并有望能够用于分析更加一般的大型自行车共享系统。

关键词: 自行车共享系统, 排队系统, 平均场, 非线性生灭过程, 固定点, 问题站点

CLC Number:

U48
O226

LI Quan-lin, FAN Rui-Na, XU Liang. Research on Mean Field Limit Theory and Queuing Modelfor Large-Scale Bike-Sharing Systems[J]. Operations Research and Management Science, 2017, 26(6): 107-116.

李泉林, 樊瑞娜, 许良. 大型自行车共享系统的平均场极限理论与排队模型研究[J]. 运筹与管理, 2017, 26(6): 107-116.

References

[1]DeMaio P. Bike-sharing: history, impacts, models of provision, and future[J]. Journal of Public Transportation, 2009, 12(4): 41-56.
[2]DeMaio P. Smart bikes: public transportation for the 21st century[J]. Transportation Quarterly, 2003, 57(1): 9-11.
[3]DeMaio P, Gifford J. Will smart bikes succeed as public transportation in the United States?[J]. Journal of Public Transportation, 2004, 7(2): 1-15.
[4]Faye V. French network of bike: cities and bikesharing systems in france[R]. leClub des Villes Cyclables, Paris, 2008.
[5]Janett B, Hendrik M. Optimising bike sharing in european cities: a handbook[M]. OBIS Project, 2011.
[6]Lathia N, Ahmed S, Capra L. Measuring the impact of opening the london shared bicycle scheme to casual users[J]. Transportation Research Part C, 2012, 22(1): 88-102.
[7]Morency C, Trépanier M, Godefroy F. Insight into the montreal bikesharing system[C]. In: TRB-Transportation Research Board Annual Meeting,Washington, USA, 2011.
[8]Shu J, Chou M C, Liu Q, Teo C P, Wang I L. Models for effective deployment and redistribution of bicycles within public bicycle-sharing systems[J]. Operations Research, 2013, 61(6): 1346-1359.
[9]George D K, Xia C H. Fleet-sizing and service availability for a vehicle rental system via closed queueing networks[J]. European Journal of Operational Research, 2011, 211(1): 198-207.
[10]Waserhole A, Jost V. Vehicle sharing system pricing regulation: a fluid approximation[R]. HAL Id: hal-00727041, 2013.
[11]Fricker C, Gast N, Mohamed A. Mean field analysis for inhomogeneous bikesharing systems[C]. In: International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, 2012.
[12]Fricker C, Gast N. Incentives and regulations in bike-sharing systems with stations of finite capacity[J]. EURO Journal on Transportation and Logistics, Published online：June 7, 2014.
[13]Leurent F. Modelling a vehicle-sharing station as a dual waiting system: stochastic framework and stationary analysis[R]. HAL Id: hal-00757228, 2012.
[14]Schuijbroek J, Hampshire R, van Hoeve W J. Inventory rebalancing and vehicle routing in bike sharing systems[R]. Technical Report, Schuijbroek, 2013.
[15]Sznitman A. Topics in propagation of chaos[M]. In: Springer-Verlag Lecture Notes in Mathematics 1464, cole d’téde Probabilités de Saint-Flour XI, 1989. 165-251.
[16]Vvedenskaya N D, Dobrushin R L, Karpelevich F I. Queueing system with selection of the shortest of two queues: an asymptotic approach[J]. Problems of Information Transmissions, 1996, 32(1): 15-27.
[17]Mitzenmacher M D. The power of two choices in randomized load balancing[D]. PhD thesis, Department of Computer Science, University of California at Berkeley, USA, 1996.
[18]Turner S R E. The effect of increasing routing choice on resource pooling[J]. Probability in the Engineering and Informational Sciences, 1998, 12(1): 109-124.
[19]Graham C. Chaoticity on path space for a queueing network with selection of the shortest queue among several[J]. Journal of Applied Probabability, 2000, 37(1): 198-201.
[20]Benaim M, Le Boudec J Y. A class of mean-field interaction models for computer and communication systems[J]. Performance Evaluation, 2008, 65(1): 823-838.
[21]Gast N, Gaujal B. A mean field model of work stealing in large-scale systems[J]. ACM SIGMETRICS Performance Evaluation Review, 2010, 38(1): 13-24.
[22]Gast N, Gaujal B. A mean field approach for optimization in discrete time[J]. Discrete Event Dynamic Systems, 2011, 21(1): 63-101.
[23]Bordenave C, McDonald D R, Proutiere A. A particle system in interaction with a rapidly varying environment: mean-field limits and applications[J]. Networks and Heterogeneous Media, 2010, 5(1): 31-62.
[24]Li Q L. Tail probabilities in queueing processes[J]. Asia-Pacific Journal of Operational Research, 2014, 31(2): 1-31.
[25]Li Q L, Dai G, Lui J C S, Wang Y. The mean-field computation in a supermarket model with server multiple vacations[J]. Discrete Event Dynamic Systems, 2014, 24(4): 473-522.
[26]Li Q L, Lui J C S. Block-structured supermarket models[J]. Discrete Event Dynamic Systems, Published online: June 29, 2014. 1-36.
[27]Li Q L, Du Y, Dai G, Wang M. On a doubly dynamically controlled supermarket model with impatient customers[J]. Computers & Operations Research, 2015, 55(1): 76-87.
[28]Neuts M F. Matrix-geometric solutions in stochastic models: an algorithmic approach[M]. Johns Hopkins University Press, Baltimore, 1981.
[29]Li Q L, Zhao Y Q. β-invariant measure for markov chains of GI/M/1 type[J]. Stochastic Models, 2003, 19(2): 201-233.
[30]Li Q L, Cao J. Two types of RG-factorizations of quasi-birth-and-death processes and their applications to stochastic integral functionals[J]. Stochastic Models, 2004, 20(3): 299-340.