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

郭忠玉 罗 俊 夏 俊

(1.上海交通大学 安泰经济与管理学院, 上海 200030; 2.上海交通大学 中美物流研究院, 上海 200030)

共享单车因其便捷性在日常通勤中扮演着重要的角色。根据交通运输部2019年公布的数据,截至2019年8月底,我国互联网租赁自行车共有1950万辆,覆盖全国360个城市,注册顾客数超过3亿人次,日均订单数达到4700万单[1]。然而自从共享单车借助移动互联网从传统的有桩模式演进成无桩模式开始,故障单车(后文简称“坏车”)的运维管理始终是运营者面临的管理难题。企鹅智库2018年发布的《共享单车数据报告:解读摩拜ofo们的顾客与未来》中显示,55.2%的ofo顾客认为共享单车未能满足其骑行需求,其中上报车辆故障的比例高达39.3%[2]。

相比传统的固定车桩模式,无桩共享单车模式(后文简称“无桩模式”)极大地提高了顾客的使用便利,但同时也给城市治理带来了挑战。共享单车在投入使用的过程中会产生各种故障或损坏。单车一旦发生故障即无法有效服务顾客,需要经过运维才能再次投入使用。当前坏车的运维主要按照区域进行批量回收、集中维修和批量重新投放的方式来进行。具体地,运维人员驾驶运载工具收集所辖范围内的坏车,将其运送至特定的维修中心,然后装载维修完毕的好车,重新投放至所辖区域。随着城市治理政策的出台和行业竞争格局日趋稳定,当前共享单车的运维越来越受到其运营商的重视。为了提升品牌竞争力和增加收入,运营方开始投入大量的运维资源用于坏车的回收、维修和重新投放。这些资源包括用于回收和投放的运载车辆资源,以及用于维修的服务资源等。从运维效率的角度看,维修资源的配置决策会影响坏车修复的速率,而运载资源的配置决策会影响坏车回收速率和好车投放速率。因此,两种服务资源的配置决策会共同影响单车系统的运维效率。本文旨在针对共享单车系统的运维实践构建封闭排队网络和系统仿真模型,并基于该仿真模型优化运维资源的配置,从而最小化顾客损失比例。

当前共享单车的文献中,考虑坏车运维的研究工作较少。Kaspi等人[3]提出一种基于贝叶斯估计的数学模型来估算有桩模式下单车的故障概率。Kaspi等人[4]指出坏车会严重降低顾客对共享单车系统的满意度,需要提高坏车运维力度。徐国勋等人[5]以运营成本最小化为目标,针对坏车回收问题建立混合整数线性规划模型,并使用禁忌搜索算法对较大规模的问题进行求解。针对无桩模式的共享单车系统,Wang和Szeto[6]在考虑坏车的情形下研究共享单车的调度策略。王涵霄等[7]提出一个比例风险模型来实时监控单车的使用情况,进而制定单车的维修和调度策略。

针对大型复杂的共享单车系统,部分文献通过建立排队网络模型来研究。Li等[8-10]最先使用封闭排队网络来描述和分析有桩模式的共享单车系统。该排队网络中,单车看作“虚拟顾客”,停车区和道路看作“虚拟服务台”。该研究假设道路网络结构是不可约图,顾客到达是马尔可夫到达过程,且单车骑行时间是独立同分布的,并基于以上假设应用流体和扩散极限来分析共享单车系统的性能表现。排队网络也经常被用来研究其他服务系统。Adelman等人[11]使用封闭排队网络来对不同节点之间的集装箱运输过程进行建模。George等人[12]针对汽车租赁系统构建了封闭排队网络模型,用以确定租赁公司的最优车队规模,并评估公司各个租赁站汽车的可用性。

在共享单车相关研究中,部分学者使用系统仿真或仿真优化方法来研究不同区域间单车的调度问题。Wang和Wang[13]运用仿真方法比较了在是否拥有实时或历史运营数据的情形下单车的调度策略。韩琦等[14]运用系统仿真方法分析共享单车系统中车在不同区域之间的转移状态。Caggiani和Ottomanelli[15]基于仿真方法通过优化路线选择来确定最佳调度流程,从而降低共享单车运营商的车辆重置成本,提高顾客满意度。孙怡璇等[16]结合实际调研得到的数据,运用仿真方法求解共享单车的调度问题。Jian等[17]使用一种基于梯度的启发式仿真优化算法来优化纽约城区的自行车和车桩分布。排序择优算法是仿真优化中一类通过比较仿真实验结果,从有限解空间中选择出最优或近似最优解的方法。其中考虑无差别区域(indifference zone,当两个解之间的差异小于该值时,认为二者无差异)[18]的典型的方法包括两阶段[19]、两阶段带筛选[20]和完全序贯(fully sequential)的方法[21],以及在并行计算环境下解决大规模问题的新序贯算法[22]。排序择优算法可以以较少的计算资源,以给定概率选择出最优或接近最优的系统。

近年来共享单车的相关工作主要研究系统的运行状态,例如单车需求量预测、顾客骑行规律,和单车调度等等。这些研究对坏车(处于损坏状态的共享单车,后文同)的回收、维修和好车投放等运维环节涉及较少,尚有一些关键问题未得到解决。例如运维环节会如何影响系统整体表现,如何进行运维资源的优化配置等问题都是共享单车运营商亟待解决的问题。本文通过对共享单车运维系统建立封闭排队网络模型,结合连续时间马尔可夫链和离散事件系统仿真方法,探究了单车运营各环节对系统整体服务表现的影响。进一步,研究总运维资源有限约束下的运维能力分配决策问题,使用排序择优这类仿真优化算法对该问题进行求解。最后在数值实验部分,首先,我们通过小规模问题的实验,将封闭排队网络模型的理论计算结果和离散事件系统仿真结果对比,同时,将理论计算结果与排序择优算法结果进行对比,分别进行交叉验证。最后在较大规模问题上进行了试验,验证了排序择优算法的有效性。

后文章节内容安排如下:第一章构建了共享单车整体系统的封闭排队网络模型,并基于该模型定义本文要求解的决策问题;第二章介绍基于连续时间马尔可夫链(continuoustime markov chain, CTMC)和基于离散事件系统仿真的方法来求解系统性能指标,并描述了用于求解决策问题的排序择优算法;第三章通过数值实验验证前述建模及求解方法的正确性,在设定的算例上进行系统性能指标求解和决策问题的求解,并分析实验结果;第四章对本文的研究工作进行总结。

本节结合当前共享单车的实际运行情况和特点,建立一个封闭排队网络模型,并基于该模型提出决策问题。其中,1.1节介绍了模型所需的假设,以及相关变量和参数。1.2节对模型进行详细描述。1.3节描述了针对维修和运载资源优化配置的决策问题。

1.1 模型假设和符号标记

记A为区域数量,i为区域的脚标;M为单车总数。

1) 共享单车系统划分成A个不同的区域;

2) 区域i的顾客到达服从参数λi的泊松过程,各区域的顾客到达互相独立;

3) 记P为顾客在各个区域间骑行的概率转移矩阵,顾客到达区域i,如果有好车,则以转移概率Pij骑往区域j,否则该顾客立即离开,i记为起始区域,j记为目标区域。若起始与目标区域相同,则表示顾客在区域内骑行;

4) 顾客从区域i至区域j的单车骑行时间服从参数ρij的指数分布,各骑行过程相互独立;

5) 顾客骑行完毕后,以1-β的概率进入目标区域,否则进入损坏状态;

6) 进入损坏状态的单车通过回收、维修、再投放这三个过程,重新服务顾客;

7) 运载车间隔参数为τ的指数分布时间,对运载车的最大载荷C以内尽可能多的坏车进行回收作业;然后间隔相同参数τ的指数分布时间,对载荷C以内尽可能多的维修完毕的好车进行投放作业;

8) 同一辆运载车持续不断地交替进行回收和投放作业;

9) 该特定维修中心有N个维修工,维修工修复一辆单车的服务时间服从独立同分布且参数μ的指数分布。

表1为系统状态变量的各分量描述。记t为系统时间变量。

表1 状态随机变量分量表Table 1 Random variables of system states

1.2 封闭排队网络模型

共享单车系统的运行可以解构为两大部分:(1)正常服务状态的部分;(2)因故障进入运维状态的部分。本文中,我们将损坏单车的回收、维修、投放统称为共享单车的运维。

共享单车日常会根据供需情况对区域间的单车进行平衡调度,比如在需求低谷期将单车从过剩区域转移至不足区域。共享单车调度策略是一个复杂的研究课题,目前已有相关研究工作[5,13,23]。本文聚焦于共享单车系统的运维。由于单车的重新投放过程一定程度上发挥了再平衡的作用,因此我们不具体考虑平衡调度对系统的影响。

图1展示了由两个区域组成的共享单车系统,系统各过程中等待或正在被服务的共享单车构成队列。因为同一队列中的单车没有区别,所以不需要考虑排队的顺序。某区域i的顾客到达服从参数λi的泊松过程,并且各区域间的顾客到达相互独立。顾客到达某区域i时,选择一辆单车,并根据概率转移矩阵P中第i行,确定目标区域j,进入骑行队列。各个骑行过程相互独立,因此相当于进入骑行队列的单车都能够马上得到服务。骑行的时间服从参数为ρij的指数分布。当顾客到达而该区域没有可骑单车时,该顾客立即流失。骑行完毕后,单车以概率1-β排至目标区域j的单车队列,否则以概率β进入一个回收池BrokenPool(简称BP),即单车进入待回收队列。损坏的单车需要经过运载车回收,运维中心的维修工维修和运载车的投放来重新进入各个区域的单车队列,并服务顾客。运载车有回收和投放两种工作状态。处于搬运状态时,其经过服从参数为τ的指数分布时间后,将不多于载荷C的尽可能多的坏车运至维修中心。运送至维修中心的坏车进入等待维修队列。运载车随即进入投放状态。运载车再经过参数为τ的指数分布时间,将不多于C的尽可能多的维修后的好车重新投放至各区域的单车队列。运载车随即进入回收状态。回收和投放二者交替进行。这里以DistributePool(简记为DP),表示已维修待投放的单车队列。维修中心有N个独立、并行的维修工,每个维修工每次维修一辆车,每个维修工的维修时间服从相同参数μ的指数分布。维修完毕的单车进入待投放队列。系统中单车的总量不变,并在各个队列中转移,于是构成一个封闭排队网络。

图1 区域数为2时单车封闭排队系统示意图Figure 1 Diagram of closed queueing network consisting of two areas

本文采用一种固定的投放策略,具体步骤为:(1)对某区域,以其顾客到达率除以各个区域到达率之和,再乘以单车总数并向下取整,得到初始各区域的目标数量;由于取整,可能会出现初始目标数量未达到单车总量,进一步以单车总量减去各区域初始目标数量之和得到剩余数量;按到达率由大至小,给前剩余数量个区域的目标数量加一,以此作为每个区域的目标投放数量。(2)投放时,如果某区域的好车数量已达目标量,则不向该区域投放;否则以当前运载车上的好车数为上限,尽可能多地投放至该目标量。

由于该排队网络中各过程的指数时间性质,系统中相邻事件发生的间隔时间服从指数分布,因此该系统的状态变化构成一个CTMC。由于事件发生时间的随机性,以及单车状态的随机性,系统中任意状态之间可以以一定概率和一定时间进行转移。因此,这是一个遍历(ergodic)的CTMC,系统存在长程稳定状态。由此,我们在给定系统参数设置下,可以通过系统状态概率转移方程,求解系统处于各个状态的概率,从而得到系统性能指标。

1.3 决策模型

坏车运维需要配置合适数量的运维资源,如运载车、维修工等。通常运载车和维修工的单位成本是已知的,运营方有固定的预算来执行运维作业。在总预算限制下,运营方需要优化运载车和维修工的配置数量,从而最小化系统中期望顾客损失比例。模型所需的参数和变量如表2所示。

表2 决策问题相关参数及变量表Table 2 Parameters and variables of the decision problem

数学模型如下所示:

模型目标函数中的顾客损失比例为各个区域因没有可供骑行单车而流失的顾客数量总和,占所有到达系统的顾客数量的比例。

本节描述封闭排队网络模型性能指标的求解方法和决策模型的求解算法。2.1节介绍两种性能指标的求解方法。其中2.1.1节介绍基于CTMC长程稳态概率的系统性能求解方法。2.1.2节介绍基于离散事件系统仿真的求解方法。2.2节介绍用于求解决策模型的排序择优算法。

2.1 系统性能指标求解方法

2.1.1 CTMC状态方程求解方法

对于遍历的CTMC,当系统时间趋向于无穷大时,系统处于各个状态的时间比例收敛于其极限概率[24]。因此,我们可以由系统状态转移的偏微分方程构建对任意系统而言状态转出率与转入率相等的方程组。求解该状态转移方程组可得系统处于各状态的概率,即系统处于每个状态的时间比例。基于该时间比例可计算得到系统性能指标。以上基于CTMC的状态微分方程组求解结果理论上是精确解。

记S为系统所有可能的状态的集合,s为集合中元素。记s为系统状态向量如下:

因为系统中的车的总数固定,所以状态变量符合以下等式:

记πs为系统处于状态s的概率。记INi如下:

对任意系统状态,其转出速率为该状态可以到达的任意下一状态的长程比例乘以相应转移速率之和。即:

由于系统状态的繁杂,为方便实际计算,我们使用以下示性函数表示一个状态是否可能出现在当前系统状态:

稳态情况下,对任意状态其转入速率为任意可以到达该状态的前继状态的长程比例乘以相应转移速率之和。具体为,任意系统状态可由另一个状态经由(一)顾客骑走一辆好车;(二)骑行到达;(三)单车损坏;(四)坏车回收至维修中心;(五)一辆单车维修完毕;(六)投放至各区域;这六种过程的某一种而进入。

其中,过程(五)的计算需要考虑到当前状态中C,BP和RC的值。从前一状态进入当前状态所搬运的数量不超过C和RC之间的较小值。同时,当该搬运数量小于C时,BP必为0,否则由搬运的规则可知,搬运的数量应当更多。于是,我们使用以下示性函数判断一个状态是否可能为通过搬运进入当前状态的系统状态:

此外,过程(六)需要根据1.3节中描述的投放策略得到所有可能的投放前系统状态集合Q。前述六种过程分别对应表达式(7)中的1-6行,从而确定系统任意状态的转入速率之和为:

因为系统必须处在某个状态,因此必须满足:

上述(2)～(8)式构成了系统状态转移概率方程组。由于遍历的CTMC极限稳态概率的唯一性,该方程组具有唯一解[25]。通过求解上述方程组,我们可求解得到系统处于每个状态的长程稳态概率,也即长程比例。根据系统的每个状态的长程稳态概率,可以计算得到一些系统性能指标。本文所选取的三个系统性能指标主要是为了反映共享单车系统的运行性能状况,与实际中单车企业的收入、成本和运行效率紧密相关。其中,期望顾客损失比例表示到达系统而未被服务的顾客数占到达系统顾客总数的比例的期望,与用户使用体验直接相关。高的顾客损失比例对应着差的用户体验,同时也意味着用户的减少,进而带来单车企业收入的损失,是一个同时关系到共享单车供需双方的指标;期望好车比例为系统中好车数占总车数的比例的期望,与共享单车企业的单车成本投入相关联,好车比例越高所需要的维修和替换投入越少;期望维修工空闲比例则为空闲维修工数占总维修工数比例的期望,反映了单车企业进行维修的人力成本投入的利用效率。根据解决问题的需要,我们还可以考虑其他类似的性能指标,例如各区域的平均可使用的单车数。为了简便起见,本文中仅举出三个代表性的指标,并以期望顾客损失比例作为决策目标进行详细论证(类似地,我们都可以用同样的方法得出其他性能指标的结论)。

(1)期望顾客损失比例

当系统中某个区域没有好车时,新到达的顾客会因骑行需求不能立即得到满足而损失。因此,我们用没有好车的区域的顾客到达速率除以总的顾客到达速率,来计算任意状态的顾客损失比例。然后以所有状态比例为权重,计算顾客损失率的期望值:

(2)期望好车比例

系统中好车和坏车的比例可以由任意状态中的好车数量占车辆总数的比例,以系统状态比例为权重加权平均得到:

(3)期望维修工空闲比例

维修中心处可能会有多个维修工。当维修中心处待维修的单车数少于维修工数量时,即出现维修工空闲。因此,维修中心的车数除以维修工数量得到某一状态的空闲比例,再以所有状态比例为权重加权平均,即可计算期望维修工空闲比例。

2.1.2 离散事件系统仿真

对本文所建立的封闭排队网络模型所对应的CTMC而言,其状态数量可通过系统中的区域数量、单车总数以及运载车的数量计算得到,总状态数量为(此处!为阶乘符号)。

由此可知,系统中的状态数量与区域数量、单车总数和运载车数量呈指数关系,也就是说系统对应的系统状态转移概率方程组将随共享单车系统的规模增加而迅速增多。由于时间和计算机内存的限制,2.1.1节介绍的方程求解方法难以解决系统状态数较多的情况。相比之下,基于仿真的方法可以无需遍历所有状态来获得系统性能指标期望值的估计值。因此,我们提出基于离散事件的系统仿真方法来计算系统性能指标。

我们基于前述构建的封闭排队网络模型,使用计算机程序编写离散事件仿真系统,再生成相应分布的随机数来运行离散事件的仿真。在仿真过程中,我们对系统状态进行记录或计数来辅助计算系统性能指标。通过记录系统中发生的事件,可以计算系统性能指标的均值。随着系统仿真的进行,系统逐渐进入稳态,由大数定律,仿真得到的性能指标均值也逐渐收敛到系统性能指标的理论期望值。具体地,顾客损失比例可通过到达顾客总数和未被服务而丢失的顾客总数相除得到;好车比例和维修工空闲比例可通过记录系统状态和状态持续时间来计算。

2.2 决策问题求解-排序择优算法

决策模型(1)的解空间有限、离散。由于系统状态数量较多,系统性能指标难以通过方程直接求解得到;此外,每一组特定参数设置下的仿真结果具有随机性,因而无法进行不同参数设置之间的比较,除非运行大量仿真实验。Kim和Nelson在2001年提出的KN算法(KN procedure)[21],即可在正确率确保选出最优参数设置的同时,通过序列式筛选,节省计算开支,适用于求解本文的决策问题。Hong等人[26]的研究表明,该算法的计算时间复杂度与待比较的方案个数K的关系为O(KlogK)。

具体而言,本文所采用的KN排序择优算法可保证以设定的1-α概率水平从候选系统中挑选出最优的系统。参数δ表示无差别区间长度,当某个待选系统在性能表现与最优的系统差距在δ以内时,认为两个系统的性能表现无差别。表现在结果上是当某些系统的均值与最优系统对应的均值之间的距离小于该值时,多次执行算法,最优解无差别范围内的系统也将被当做最优系统而以一定频率被选出。这种解记作δ-最优解。该方法的优点在于:(一)可以设置无差别区间,从而可以认为决定什么样程度的性能差别是没有影响的;(二)其筛选过程中,可以逐步剔除明显差的方案,从而节省比较所需要的总样本数;(三)该方法虽然基于样本分布为正态的假设,但是对样本分布非正态同样有着良好的适用性,可以应对在实际使用过程中,样本分布未知的情形[21]。算法的输入参数如表3所示。

表3 KN算法参数表Table 3 Parameters of KN procedure

具体到求解本文的运维决策问题中,K表示待比较的运维方案的个数;1-α为人为设定的,实际上的最优运维方案被算法选出的概率大小;δ为人为设定的判断阈值,当两个运维方案的性能指标差异小于该值时,认为两个方案的性能指标没有差异;n0为算法初始比较时,每个运维方案的仿真样本个数;c为算法参数,与实际运维问题无关;k为运维方案的标号。

记Xkp为系统k的第p个观测值。

算法流程如算法1所示。

算法1 KN算法输入:K,α,δ,n0,c输出:最优系统编号1 初始化:2 I={1,2,…,K}3 η=1 2[( )-2/(n0-1)-1 2α K-1]4 h2=2(n0-1)cη 5 S2kl=1 n0-1 n0 l(n0)])2,∀k∈Iandk≠l 6 Nkl=∑p=1(Xkp-Xlp-[X k(n0)-Ximages/BZ_223_1480_1843_1503_1942.pngh2S2k l δ2images/BZ_223_1586_1843_1608_1942.png,∀k∈I and k≠l 7 Nk=max l≠k Nkl,∀k∈I 8 Xk(r)=1 r ∑r p=1Xkp 9 初始判断:10 if n0＞maxkNk then 11 return argmaxkXk(n0)12 else 13 r=n0 14 进入筛选过程15 end if 16 筛选过程:17 while |I|＞1: 18 ∀系统k∈I中产生一个观测值Xk,r+1 19 r=r+1 20 if r==maxkNk+1 then 21 return argmaxkX k(r)22 else 23 Iold=I 24 Xk(r)=1 r ∑r p=1Xkp,∀k∈I 25 Wkl(r)=max 0,δ 2cr h2S2 kl { },∀k∈Iandk≠l ( )δ2-r

26 I={k:k∈Iold and X k(r)≥X l(r)-Wkl(r),∀l∈Iold,l≠k}27 end if 28 end while 30 return I

系统k与l观测值之差的样本方差,Nk为系统k的最大样本量。在将该排序择优算法应用到本文的决策问题时,注意到算法原适用于最大化问题,因此在本研究实际应用该算法时,将目标函数做取反处理。

本节我们验证第2章中封闭排队网络建模和离散事件系统仿真方法的正确性并设置算例测试排序择优算法的效果。3.1节介绍系统性能指标求解的过程,在设定的算例上验证其正确性,并分析结果。3.2节基于小规模问题通过比较方程计算得到的结果、仿真计算得到的期望值和排序择优算法的结果,验证本文所采用算法的正确性。然后在不同算例上运行排序择优算法,验证其优化效果。

3.1 运维模型数值实验

3.1.1 求解方法设置

在如表4所示的默认系统参数设置下,使用方程求解和系统仿真两种方法来计算系统性能指标。

表4 系统仿真默认参数表Table 4 Default parameters of simulation

使用系统状态转移方程求解主要经过三大步骤:(一)根据系统参数设置,生成所有可能的系统状态;(二)使用稀疏矩阵存储方程组;(三)求解方程组。本研究中,我们基于Python调用Scipy包的稀疏矩阵方程求解算法来对方程进行求解。

通过对仿真模型的简单扩展,可以仿真系统中包含多辆运载车同时运行的情况。根据仿真结果,我们对结果进行排序,从而挑选出最优解或近似最优解,也即δ-最优解,继而求解目标决策问题。由于初始系统状态对长程稳定状态下的系统性能指标没有影响,我们统一设置初始状态下系统中所有车均为好车,且均匀分布于各个区域中。仿真运行过程中,观察系统指标变化可判断系统是否进入稳态。取系统进入稳态后的一段时间,计算这段时间某性能指标均值,作为该指标的期望值的估计[25]。为了快速得到CTMC模型方程的解,我们首先考虑一个小规模问题。特别要指出的是,在现实中不同场景下会有不同的顾客骑行转移概率和到达速率。本文中不同的Pij、λi相当于现实中不同的地区或时间等不同的单车系统的运行场景。在实际中可以通过实际运行情况进行统计、估计。在此,为了研究便利,我们采用随机数。3.1节中取

并且,在后文的数值实验中生成不同的随机数,以比较不同的场景,反映计算方法对不同情景的鲁棒性。为了文章简洁,后文不再具体给出取值。仿真结果如图2所示,纵轴为比例值,横轴为离散系统仿真的系统时间,三条曲线分别代表了性能指标仿真进行至当前时间的平均值。如图所示,2.1.1节中介绍的三种性能指标随仿真进程推进,其均值逐渐趋于稳定。如2.1.2节所述,后续将根据稳定值估计系统性能指标。

图2 A=2,M=6时系统性能指标-时间30000图Figure 2 Performance indicators-simulation time graph with A=2, M=6

3.1.2 系统状态参数数值算例

由于输入参数的随机性,离散事件系统仿真结果存在波动。为准确得到结果,我们以20次仿真结果的均值作为一个仿真得到的系统性能指标结果。基于表4中的默认参数设置,我们在不同的系统运维速率下比较方程求解和系统仿真所得的结果。如下图3所示。

图3 A=2,M=6时方程与仿真结果对比图-变动运载速率Figure 3 Comparison of ODE and simulation result varying speed of carrier with A=2, M=6

图4 A=2,M=6时方程与仿真结果对比图-变动维修速率Figure 4 Comparison of ODE and simulation result varying repairing speed with A=2, M=6

通过对比方程求解和仿真结果可以看到,仿真方法可以逼近系统性能指标的CTMC方程计算值。此外,单独提升运维系统中的运载车或维修工的速率,可以降低顾客的损失比例,提升系统中好车的比例,并提高维修工空闲的比例。但从图中也可以看到随着速率的进一步提升,系统性能指标的曲线变得平缓,也即单独提升运维系统中的运载车或维修工的速率,提升改善效果存在边际递减效应。

图5展示了不同运载车数量和维修工数量下顾客损失比例的变化。从图5中可知,增加维修工或运载车的数量均可降低顾客的损失率,改善系统性能表现。但当数量持续增加时,曲线的下降趋势渐趋平缓,说明改善效果边际递减。当二者增加到一定程度后对系统的性能改善效果几乎消失。由此可知,对一个共享单车系统而言,单纯通过增加维修或投放的能力对改善系统的性能表现是存在上限的。因此在相同资源限制条件下,可能存在性能表现相近,而资源投入存在差异的方案。实验结果符合常识推论。

图5 A=2,M=6时变动维修工及运载车数量仿真结果Figure 5 Simulation result with varying number of repairing workers and carriers server with A=2, M=6

3.2 决策模型数值实验

3.2.1 仿真优化算法验证

我们首先在A=2,M=6的情况下使用CTMC方程方法求解CostR=1,CostC=1,CostTotal=5,nC=1的小规模决策问题中的每一个解的期望顾客损失比例。

通过方程计算得到如表5所示结果,显示(N,nc)=(4,1)为最优解。在δ=0.01时,(N,nc)=(2,1)和(N,nc)=(3,1)在最优解的无差别范围之内,为δ-最优解。

为了排序择优算法的适用性,仿真结果应当尽可能符合正态分布。图6为不同决策问题解的200次仿真结果的频数分布分布统计图。4个解对应仿真结果的分布均能通过正态性的KS检验(Kolmogorov-Smirnov test)。按照表3中的参数设置,运行1000次排序择优算法,结果(N,nc)=(4,1) 被选中974次,(N,nc)=(3,1)选中26次。所有结果中,在最优解无差别区域内的解被选中的比例超过了设定的95%。该实验验证了算法的正确性。

图6 小规模决策问题解对应仿真结果频数分布统计图Figure 6 Frequency distribution graph for the simulation result of the solutions of the small-scale decision problem

3.2.2 决策问题数值算例

分别在A=2,M=6,A=10,M=100和A=10,M=1000的情况下,取CostR=1,CostC=1,CostTotal=10;不考虑N=0或nC=0的情况;相应的KN算法的参数K=45。以不同的转移概率和各区域的顾客到达率作为不同场景,在各场景中求解其对应的决策问题。在如表4所给出的参数设置下,对前述场景分别运行重复试验。结合3.1.2的结果,和从表6和表7中看到的50次仿真结果的置信区间,我们可以认为50次仿真结果的均值可以较准确地估计实际值。以每个场景中的每个解的50次仿真结果的均值和标准差作为比较标准,统计算法结果。其中正确选择比例(PCS,probability of correct selection)为KN算法选出最优解或δ-最优解的次数占总实验次数的比例。展示KN算法选出的结果如表6、表7和表8所示。

表6 决策问题数值算例,A=2,M=6,500次重复Table 6 Numerical experiments of decision problem, A=2, M=6, 500 times repetition

表7 决策问题数值算例,A=10,M100,500次重复Table 7 Numerical experiments of decision problem, A=10, M=100, 500 times repetition

表8 决策问题数值算例,A=10,M=1000,10次重复Table 8 Numerical experiments of decision problem, A=10, M=1000, 10 times repetition

三张表中的结果显示,排序择优算法在不同场景下,可以给定概率选出性能指标与最优解在给定的无差别区域内的方案,试验显示较少次数的排序择优算法重复试验,也已可以选出较好的方案。从而保证了问题求解的最优性,并具有一定的鲁棒性。该方法适用于在难取样的复杂系统中挑选可行方案。此外,排序择优算法的运行是通过逐步剔除明显差解。本研究中,运行KN算法需要900次左右仿真得到一个结果。而通常情况下,基于仿真样本均值估计的求解方式往往难以准确估计所需的仿真次数。因此,在算法效率方面,KN算法对于解决本文的管理决策问题具有一定的优势。

本文结合共享单车的实际运维特点,将无桩共享单车的整体运行过程建模成封闭排队网络,并构建对应的CTMC模型。该模型可通过状态转移方程求得系统长程稳态概率和系统性能指标,具有理论上的精确性。在大规模共享单车系统运行环境下,系统中的状态数量呈指数速度增长,导致状态转移方程难以求解。并且该计算方法,依赖于指数分布假设,难以适用于实际问题。本文提出基于离散事件系统仿真的方法来估计系统性能指标。该方法适用于不同的系统假设,例如不同的顾客到达分布假设等,极大增加了研究的可扩展性,为研究共享单车系统运行状态提供参考。通过观察单车系统参数变化对性能指标的影响,我们发现增加系统中运载车的速率和数量,或提升维修环节速度、增加维修工数量可提高系统性能表现,但对系统的改善作用都存在边际递减现象。因此,需要解决将总数有限的运维资源在运载和维修环节之间进行合理分配的决策问题。排序择优算法适用于求解该决策问题,并且可以从理论上保证,在给定的正确概率水平下,从不同性能指标接近的方案中挑选得到可接受的最优方案或接近最优的δ-最优方案。本文通过小规模数值算例对比理论计算和仿真优化算法结果,交叉验证了算法的正确性。并进一步在设置的算例上展示算法运行效果。为共享单车实际运营中进行运维能力的分配决策提供解决方案参考。

猜你喜欢 维修工性能指标单车 共享单车为什么在国外火不起来意林彩版(2022年1期)2022-05-03沥青胶结料基本高温性能指标相关性研究石油沥青(2021年1期)2021-04-13坏掉的8号电话亭奥秘(创新大赛)(2020年3期)2020-11-28飞吧，单车读友·少年文学(清雅版)(2020年1期)2020-05-20北斗卫星空间信号故障与监测性能指标定义空间科学学报(2020年4期)2020-04-22街道维修工(外四首)岷峨诗稿(2019年4期)2019-04-20调查中国工人(2017年10期)2017-11-22对恶意破坏共享单车行为要“零容忍”领导决策信息(2017年9期)2017-05-04共享单车(外四首)岷峨诗稿(2017年4期)2017-04-20自动控制系统的优劣评价分析考试周刊(2017年7期)2017-02-06

推荐访问:单车 排队 决策