基于排队网络的共享单车坏车运维决策优化

Operational maintenance for broken bicycles in a dock-less bike sharing system:From a closed queueing network perspective

共享单车系统中车辆的损坏会严重影响顾客使用体验。为此,运营方需要投入运维资源(如维修工、运载车等)对坏车进行回收、修复和重新投放。由于运维资源有限,如何优化资源的配置是当前共享单车管理实践中待解决的重要问题。本文结合实际运维特点,构建了一个封闭排队网络模型,并在运维资源有限的条件下,以最小化顾客损失比例为目标提出决策问题。本文基于前述排队网络模型,提出基于连续时间马尔可夫过程的状态稳态概率和基于离散事件系统仿真,两种求解系统性能指标的方法。针对决策问题解空间有限且离散的特点,本文结合前述仿真方法,采用基于排序择优(ranking and selection)的仿真优化算法来求解。实验算例结果显示离散事件系统仿真可有效估计出系统性能指标;提升维修工和运载车的工作速率或增加数量可改善系统性能表现,但改善效果边际递减。此外,本文采用的排序择优算法可有效求解决策问题,为共享单车的运营管理决策提供参考。

Regular operations and maintenances of a bike-sharing system require extremely high fixed asset investments and operational costs,which have become a heavy burden for a bike-sharing company.Excessive bicycles also bring huge challenges to urban governance.The bike-sharing company needs many maintenance workers,trucks,and operators for daily operations and maintenances.As in the serial processes of collecting,repairing,and redistributing the bicycles,these operations affect each other.Thus,designing an appropriate resource allocation can help the company provide a good service to customers while minimizing costs.This paper first constructs a closed queuing network model of a dockless bike-sharing system and uses the discrete event simulation model to characterize system performances.Based on that,the optimal decision problem is solved by minimizing the customer loss rate with limited total resource allocation for operations and maintenances.In the first part,a closed queuing network model for the dockless bike-sharing system is built,which is a continuous-time Markov chain(CTMC)based on reasonable abstractions of actual daily operations.Necessary assumptions in the system are specified to build the model,and variables and system parameters are described based on which the closed queueing network model is defined.Especially,processes in the system are all Markovian,and the carriers collect the broken bicycles and redistribute the repaired bicycles in a batch manner.Finally,a decision problem is defined with the purpose of minimizing the expected loss rate of customers and with a limitation on the total operation resources to be allocated between the repairing and transporting processes.In the second part,a system performance solution method is presented based on the steady-state equations of the CTMC.Three system performance indicators are introduced:(1)the expected customer loss rate,(2)the expected portion of usable bicycles,and(3)the expected idling rate of the repairing workers.The number of states in the system increases exponentially as the number of areas and bicycles in the system increases,making the former equation method difficult to apply.However,the discrete event system simulation method does not need to evaluate all limiting states to obtain the system performance estimator.Therefore,this work adopts a discrete event system simulation method to obtain system performance estimators.As the simulation proceeds,the indicators will converge to their theoretical expectations according to the law of large numbers.For the decision problem,the solution space is found to be finite and discrete,which is suitable for a kind of simulation optimization method,called ranking-and-selection(R&S).The parameters and steps of a fully sequential R&S procedure,called the KN procedure of Kim and Nelson,are further introduced to solve the decision problem.The third part describes the calculation of the system performance by the rate-balance equation in the CTMC model and the discrete event simulation method in detail.Simulation experiments are run to cross-validate the proposed two methods.Analysis results of the variation of parameters of the system reveal that the increase of the operation ability can reduce the customer loss rate,increase the portion of usable bicycles in the system,and increase the idling rate of repairing workers.However,the effect is marginally decreasing.For a small-scale decision problem,the system performance of each solution is separately calculated by the rate-balance equation and the KN procedure to find the optimal solution.The results are then compared in different settings to demonstrate the effectiveness of the simulation optimization procedure.In summary,this paper builds a closed queuing network model of a dockless bike-sharing system considering the repairing process and proposes a decision problem that optimizes the allocation of limited operation resources between repairing and transporting processes.Two methods are then proposed to derive the system performance.The simulation method has the advantages of better tolerance of computational complexity as the scale of the model increases and applicability when the distribution of the operation process is unknown.At the same time,this work introduces the KN procedure to solve the operation resource allocation decision problem.In the numerical experiments,the introduced methods are first cross-validated,and the relationship between the system parameters and performance is then analyzed.Finally,the correctness of the KN procedure is demonstrated,and more experiments are conducted to exhibit the effectiveness of the method.This method is argued to be better than comparing solutions using the average of the simulation samples.This work provides a good reference for the operation practice of bike-sharing management.