面向自组织平衡的共享电动汽车调度优化方法

姚恩建，何媛媛，金方磊，卢天伟，潘 龙

(北京交通大学a.交通运输学院；b.综合交通运输大数据应用技术交通运输行业重点实验室，北京100044)

0 引 言

近年来，随着我国经济的快速发展，城市小汽车保有量不断升高的同时，空气污染、交通拥堵、停车资源紧张等问题日益严重.共享电动汽车成为城市交通问题的新的解决方案.目前，共享电动汽车模式以单程式(one-way)为主，这种模式比较灵活便捷，可满足用户多样化的出行需求.由于用户出行需求的潮汐特征，在运营过程中存在各站点车辆分布不平衡，导致站点车辆供给与需求不匹配，用户体验差，运营结束后人工调度成本过高，制约了该新兴模式的发展.因此，如何通过对共享电动汽车的调度优化解决这些问题成为当前亟待研究的问题.

共享汽车调度优化研究主要包括基于人工调度(Staff-based)和基于用户调度(User-based).既有研究面向共享汽车的人工调度模式进行优化.Nourinejad等[1]构建了基于不同需求场景的动态车辆调度模型，以共享电动汽车运营商利润最大为目标求解站点间的车辆调度计划.Wang等[2]建立了基于线性整数规划模型的共享电动汽车调度优化模型，考虑车辆调度和员工分配，通过仿真求解.李昭涵[3]以调度距离、车辆使用率等4 个指标对车辆调度方案进行优化.然而，人工调度模式存在调度反馈滞后、车辆利用率低、人工成本较高等问题.

基于用户调度(User-based)的研究较少.Clemente 等[4]提出采用价格优惠措施引导用户参与调度的方法，能够降低人工调度的成本，但其策略仅针对用户还车阶段.王宁等[5]提出基于用户激励的共享电动汽车自适应调度，引入价格激励手段，但没有考虑用户在选择共享电动汽车时包括出行费用、取车距离等因素的综合效用.

综上，本文面向基于站点运营的单程式共享电动汽车，研究面向自组织平衡的车辆调度优化方法.在人工调度的基础上，为实现自组织平衡，基于用户的共享电动汽车站点选择行为偏好，制定动态折扣策略以引导用户改变默认的最近取还车站点，在满足用户出行需求的同时由用户完成部分调度任务，从而提高各站点车辆的供需平衡，降低人工调度任务数与调度成本.

1 共享电动汽车用户取车站点选择行为分析

针对通勤场景下的共享电动汽车用户，其在选择取车站点时主要考虑取车步行距离，站点车辆的剩余续航里程，共享电动汽车的出行费用这3个因素，即对于用户来说，站点的差异主要表现在这3个方面.故本文基于MNL(Multinominal Logit)模型构建用户的共享电动汽车站点选择模型，并利用SP 调查数据标定模型参数，确定用户选择不同站点的效用大小.

基于MNL 理论，用户选择某一站点的效用公式为

式中：Vin为用户n选择取车站点方案i的效用；是模型参数向量；是用户n的取车站点选择方案i的影响因素变量；An为用户n的取车站点选择方案集合.

根据设计好的SP 调查问卷，采用随机抽样的方法选取北京城市居民进行调查，共得到有效问卷482份.基于最大似然法，对构建的MNL模型进行标定，模型参数标定结果如表1所示.

表1 取车站点选择MNL 模型参数标定结果Table 1 Results of parameters calibration of MNL model

从表1可以看出：模型的调整优度比ρ2＞0.2，说明模型整体精度较高；各变量t值的绝对值均大于1.96，即有95%以上的置信度认为所有变量均对选择结果产生影响；取车步行距离、出行费用的预测值均为负，说明随着距离、费用的增加，用户愿意选择对应站点的概率会降低；车辆的剩余续航里程的预测值为正，说明随着续航里程的增加，用户愿意选择该车辆所对应站点的概率会增加.结果表明，该模型符合实际情况.根据模型结果，得到用户选择某一取车站点的效用公式为

2 面向自组织平衡的共享电动汽车调度优化方法构建

面向自组织平衡的共享电动汽车调度优化方法为：考虑运营时段，基于动态折扣策略的用户调度到运营结束后的人工调度的整个调度过程，在一定程度上实现各站点供需自组织平衡的同时，减少人工调度任务数，使运营企业调度总成本，即自组织调度(用户调度)成本和人工调度成本之和最小.

2.1 前提假设

结合共享汽车实际运营情况，做出如下前提假设：假设所有站点的初始停车位数固定，且均配有充电桩；车辆返回站点即开始充电，直至充满或被提走；用户单程行驶距离均不大于电动汽车满电量续航里程；各时段的车辆需求数为已知.

2.2 基于动态折扣策略的用户调度阶段

用户调度阶段通过动态折扣策略，以引导用户改变默认的最近取还车站点，将汽车返还到供给不足的站点，缓解站点供需不平衡状况，在一定程度上实现站点供需的自组织平衡，减少人工调度阶段的调度任务数.用户调度阶段具体步骤如下.

Step 1寻找可用车辆及站点.

对于需求i，其选择车辆应满足时间约束和续航里程约束，站点应该满足步行距离、车辆和停车位约束，即

式中：D为按照需求触发时间先后顺序排列的用户需求集合，D={1 ,…,i,…} ；L为车辆取还车站点集合，L={1 ,…,m,…,n,…} ；Vi为需求i的可用车辆集合，Vi={1 ,…,v,…} ；T为运营时段所有需求触发时间按先后顺序排列的时间点集合，T={t1,…,ti,…,tN} ；T0、T2分别为车辆运营开始和结束时间；T1为动态折扣策略开始实施时间，T1∈[T0,T2] ；Fv,i为车辆v对于i的解除占用时间；Rv,i为车辆v对于i的剩余续航里程为0-1变量，若i由站点m到n使用车辆v，则变量为1，否则为0；Vm,ti为站点m在ti时刻的实际车辆数；Nn,ti为站点n在ti时刻的可用停车位数；dm,n为站点m与n的距离；di,m、dn,i分别为i的起点至m的取车步行距离，n至i的终点的还车步行距离；Q0,v为v的最小剩余续航里程；dmax为用户取车与还车能接受的最大步行总距离.

Step 2对可用车辆和站点分类.

根据各站点的车辆供需状态，对可用取还车站点进行分类.为观察各站点的供需是否平衡，引入站点不平衡系数，并将其定义为某一站点在运营任意时刻的实际车辆数与需求数之差，即

式中：Vm,0为站点m运营起始时刻的车辆需求数.

式中：Bm,ti为ti时刻站点m的不平衡系数；为站点m、n在ti时刻的状态.

Step 3求出为用户提供的最佳折扣或者惩罚.

用户取车与还车距离类似，且在取车时会考虑取还车总距离，所以用户的效用值采用前文标定的效用函数确定.出行费用按照“里程+时间”的方式收取.

求出可取的折扣或者惩罚系数集合，使用户可选车辆和站点集合中，有利于达到站点供需平衡方案的效用较大，且系数最优值选取时考虑使运营商的用户调度成本较低，从而得出最佳折扣或惩罚系数.存在以下这7 种情况，其中，Vik为需求i的第k种可用车辆集合，Lik为需求i的第k种可用取还车站点集合，Ai、Bi分别为i的可取折扣系数、可取惩罚系数集合，αmin、βmax分别为折扣系数的最小值、惩罚系数的最大值.

Step 4车辆与站点状态更新阶段.

式中：ti,m为i的起点至站点m的取车步行时间；Qv为车辆v最大续航里程；Hv为单位充电时间车辆v增加的续航里程；Vn,ti为站点n在ti时刻的实际车辆数；Nm,ti为站点m在ti时刻的可用停车位数.

Step 5用户调度成本的计算.

Step 1～Step 4循环至每日运营结束时，全天用户调度成本为

式中：Z1为自组织调度(用户调度)成本.

2.3 人工调度阶段

根据各站点每日运营结束时实际车辆数与第2日运营起始时车辆需求数之差，采用供需平衡的运输问题求解人工调度任务集合D1.以调度总成本最小为目标建立调度模型，并利用禁忌搜索算法来求解.

(1)目标函数.

式中：Z为调度总成本；Z2为人工调度成本；P为调度员集合，P={1 ,…,p,…} ；D1为调度员调度共享电动汽车的调度任务集合，D1={1 ,…,d1,…} ；D2为调度员骑电动单车从某一站点到另一站点取共享电动汽车的取车任务集合，D2={1 ,…,d2,…} ；为0-1变量，当调度员p因调度任务d1由站点m到n，则变量为1，否则为0；为0-1变量，当调度员p因取车任务d2由站点m到n，则变量为1，否则为0；P0、P1分别为调度员的单位距离调度成本、固定成本；Np为调度员数量.

(2)约束条件.

调度员的任务约束，即一个调度任务或取车任务均最多由一个调度员完成，且一个调度员的取车任务数不超过其调度任务数，即

(3)求解算法.

采用禁忌搜索算法对人工调度阶段的优化模型进行求解.采用最小成本插入法构造调度初始解，采用线路间和线路内变换相结合的邻域结构以便尽可能搜索更大空间.

3 算例分析

3.1 算例选取

选取北京市海淀区经度范围116.2°E～116.4°E，纬度范围39.92°N～40.12°N 的长方形地区为研究区域，该区域内站点较为集中.

模拟算例数据集分为：站点数据集，车辆数据集，需求订单数据集.站点数据集包括站点经纬度，各时段的车辆需求数量和供给数量，停车位总数，编号，共设置100 个站点；车辆数据集包括车辆满电量续航里程，所在站点位置，共设置200辆共享电动汽车，假设其均为同一种车型，满电量续航里程为260 km，最小剩余续航里程20 km，充电速率为90 km/h；需求订单数据集包括出发地和目的地经纬度，需求触发时间，设计的需求数量为80个.

参照GoFun共享电动汽车项目和前面的问卷统计结果，算例中其他常量的设置如表2所示.

表2 算例中的常量Table 2 Constants in example

为避免过早进入搜索循环，减小计算量和存储量，提高收敛速度，设置禁忌长度为10，最大迭代次数为2 000次.

3.2 模型求解

考虑无动态折扣，即在运营期间用户自主选车，车辆调度在运营结束后由人工单独完成的情况，并将两种情况进行对比.根据概率和数理统计原理，考虑有效样本量和偶然误差，将从用户调度到人工调度的整个调度程序运行139次，取所得结果期望作为最终取值，结果如表3所示.可以看出：实施动态折扣策略后调度员的调度任务数减少了8.3%，人工调度成本降低了21.1%，说明在运营结束时有更多的站点达到供需平衡；站点平衡度提高，调度总成本降低了4.5%，表明实施相应动态折扣策略具有一定的有效性.

表3 不同策略模型结果对比Table 3 Comparison of results of different strategy models

求解得到用户折扣或惩罚系数，如表4 所示，部分用户改变了取还车站点.

表4 各用户折扣或惩罚系数Table 4 Discount or penalty coefficient for each user

为观察站点采取动态折扣后的平衡性，以任意站点为例，图1 给出站点25 的情况.可以看出，其不平衡系数显著降低，表明通过该策略让用户参与调度，可以有效降低运营期间站点车辆供需的不平衡.

图1 站点25 的平衡度Fig.1 Vehicle balance of station 25

3.3 模型主要参数敏感性分析

为研究不同动态折扣策略对调度成本的影响，对动态折扣最小值进行敏感性分析.改变动态折扣最小值αmin，变化区间为(-14.2%,14.2%)，人工调度成本，用户调度成本，以及调度总成本随αmin的变化趋势如图2所示.

从图2 可以看出，随αmin减小，人工调度成本减少，用户调度成本增加，调度总成本先减少后增加，表明动态折扣策略的引入虽然能降低人工调度成本，但只有设置合适的动态折扣最小值才能使调度总成本达到最低.

图2 动态折扣最小值αmin 对调度成本的影响Fig.2 Impact of αmin on relocation cost

4 结 论

本文在分析用户共享电动汽车站点选择行为的基础上，建立面向自组织平衡的共享电动汽车调度优化方法.主要得到以下结论：采用动态折扣优惠策略后，调度总成本降低4.5%，人工调度成本降低21.1%，人工调度任务数减少8.3%，该调度优化方法合理有效.本文为企业车辆调度优化问题提供了参考，企业可以定制有针对性的动态折扣策略以实现调度总成本的最小化.本例中动态折扣的最小值为0.70，企业可以根据自身情况和相关实践进行调整，权衡人工调度成本和用户调度成本，使调度总成本达到最低.