摘要 随着车联网、云计算、大数据的应用普及,代表着“互联网+出行”的共享电动汽车租赁业务因灵活便捷、绿色环保拥有广阔的发展空间。可租赁状态的共享汽车与租车客户在时空分布上的不匹配,是共享汽车运营商提高收益面临的焦点问题。基于网络流模型,计及电动汽车充电对车辆可提供租赁服务状态的影响,同时实现时间和空间维度的共享汽车租赁业务供需匹配分析;并结合租赁业务特点,提出租赁站点车流量守恒约束、共享车辆状态转移守恒约束。以调度周期内运营商净收益最大为优化目标,考虑路网、车、租赁需求及充电网络约束,建立共享电动汽车优化调度混合整数线性规划模型,同时优化决策车辆调配方案和充电计划。算例表明,优化调度策略可提高共享电动汽车运营商收益与用户满意度。
关键词:共享电动汽车 网络流 车辆调配 充电计划 混合整数线性规划
随着移动互联网技术的广泛应用和新能源汽车的推广,近几年我国多地相继出台新能源汽车分时租赁相关政策,鼓励新能源汽车租赁行业的发展。共享汽车通过车辆使用权的租赁,提高了汽车使用效率,缓解交通拥堵,保护环境,节约资源。当前电动共享汽车租赁业务作为一种更加环保的商业模式,面临新的发展机遇。
处于可租赁状态的共享汽车与租车客户在时空分布上的不匹配,是共享汽车运营商日常运营中面临的核心焦点问题。针对共享电动汽车,由于电池续航里程较传统燃油车一箱油可行使里程小,租车客户存在里程焦虑问题;且每日运营中需要预留小时级的充电补给时间,挤占共享汽车可提供服务的时间。这些极大程度地影响了共享汽车运营商的收益与租车客户的满意度。因此,伴随电动共享汽车的发展,共享汽车的优化调配问题研究面临更加严峻的新挑战。
传统燃油共享汽车的优化调配问题已有一定的研究成果积累。根据调配主体的不同,有基于顾客的调配和基于调配员的调配两种模式[1]:基于顾客的调配方式[2-3],受租车顾客行为的不确定性影响大;基于调配员的调配方式[4-6],需要额外付出调配员的人力成本,但因调配员的行为可控而具有更好的优化效果。共享汽车的优化调配模型通常以运营商利润最大、运行成本最小或客户满意度最高为目标,采用混合整数规划[4-5]、两阶段随机规划[6]以及启发式算法优化求解。然而以电动汽车作为共享汽车时,共享汽车运营商在决策车辆优化调配方案时还需联合决策车辆的充电计划。
针对电动汽车的充电计划,许多文献从不同角度开展了电动汽车的充电优化研究,包括电动私家车[7-8]、出租车[9]、公交车[10-11]。但是针对新兴发展的电动共享汽车的优化调度研究尚处于起步阶段。文献[12-14]通过采用换电技术,减少电动共享汽车里程焦虑和充电时间消耗对车辆优化调配的影响。随着快速充电技术的日趋成熟,少量文献基于充电模式开展共享汽车优化调度研究[15-17]。文献[15-16]考虑租车的需求时间窗、电池容量等因素,提出了带有时间窗的共享车辆调配模型。文献[17]在共享汽车调配的时空网络优化模型中考虑了电池的充电限制,并采用拉格朗日松弛法进行求解。
共享电动汽车作为一种新兴商业模式,开展面向共享电动汽车的优化调度,研究有利于升级智慧出行,促进电力交通互联网深度融合。共享汽车运营商优化调度的目的是实现净收益最大化,即以最小的成本投入来最大化地满足租车用户需求。因此,本文基于图论网络流模型中最小费用最大流模型,结合共享电动汽车运营商服务租车订单的商业运营特点,建立共享电动汽车调度优化模型,决策共享电动汽车的调配方案与充电策略。模型在共享车辆行驶轨迹时空网络流分析中嵌入车辆承接共享订单可用性的状态判断,在时空双维度上兼容考虑车载电池荷电状态变化对车辆承接共享订单能力的影响,可实现共享电动汽车租赁业务时空维度的供需匹配分析。
调度优化问题是共享汽车运营商提高收益的核心问题。电动共享汽车租赁业务涉及共享汽车、路网(含租赁站点分布)、租车需求顾客三方资源的耦合。其中,路网是中间层,连接着作为供给方的共享车资源和作为需求方的顾客资源。为促进共享车辆与租车顾客间的供需匹配,共享汽车运营商通过决策车辆调配方案改善共享车辆的时空分布特性;与此同时,针对电动共享汽车,运营商还需要计及电动共享汽车调配或提供租赁服务引起的车载电池荷电状态变化,配套决策充电计划(包括充电站点和时段的选择),在时空维度上反映电动汽车充电计划对其可用状态的影响。为了进行上述时空双维度的决策分析,本文采用网络流模型,结合车辆调配方案和充电计划,描述共享汽车分布及状态与租车顾客分布间的匹配关系,以日为周期,建立优化调度模型,模型框架示意图如图1所示。
模型的目标函数为调度周期内共享电动汽车运营商的净收益最大。运营商的净收益为提供的共享汽车服务收入扣减车辆调配成本与充电成本。
模型的约束条件有路网约束、车辆约束、充电网络约束及需求总量约束四个层面。其中,路网约束包括:①车流量守恒约束,即对于路网中每个租赁站点来说上一时段驶入叠加在站车辆总数与下一时段驶离叠加在站车辆总数守恒;②车辆状态转移守恒约束,即对于每个站点来说,只有上一时段停留或驶入的车辆下一时段才能继续停留或驶离本站。车辆约束包括:①车辆状态约束,即对于每辆车而言,每个时段处于以下四种状态之一:停留于租赁站等待状态、停留于租赁站充电状态、满足用户需求的租赁状态与被运营商调配状态;②车载电池约束,包括电池容量约束与充电限制。
图1 模型框架示意图
Fig.1 Model framework
本文在建模过程中作如下简化假设:
1)电动汽车为统一型号,车载电池寿命周期内总吞吐量一定,调度周期开始时均为满电状态,调度周期内,当车辆电池荷电状态满足约束时,单车无租赁次数的限制,不考虑合乘情况。
2)共享电动汽车利用租赁站内配置的快充桩充电,快充桩型号统一。
3)共享汽车运营商在不同时段提供的租赁服务没有价格差异,且租赁服务价格能够弥补车载电池寿命损耗成本,运营商日调度模型的优化目标聚焦在满足订单需求的净收益最大化,忽略电池寿命周期的影响。
4)共享服务订单的起点和终点均是租赁站点,基于租赁站点简化路网结构,所有行程均在调度周期内完成,暂不考虑路况拥堵的不确定性影响。
式中,为服务周期,将一个调度周期等分为段,每个时段开始为时间节点,;为共享电动汽车,;为租赁站,;为路网中各租赁站间路径,;为时段车辆是否为用户租赁行驶于路径上,是0-1变量,表示时段车辆为用户租赁行驶于路径上;为车辆单次满足路径租赁需求的收益;为时段车辆是否被调配于路径上的0-1变量,表示时段车辆被调配于路径上;为车辆经路径被调配的成本;为时段车辆是否在租赁站充电的0-1变量,表示时段车辆在租赁站充电;为时段车辆在租赁站的充电功率;为时段充电电价。
对于任意车辆,每个时段只能处于在租赁站空闲或充电、行驶于路径上满足需求或被调配的四种状态之一,则有
式中,为时段车辆是否在租赁站空闲,为0-1变量,表示时段车辆在租赁站j空闲。
对于任意租赁站,时段驶入的车辆数(调配驶入+提供服务驶入)加上在站车辆数(在站充电+在站空闲)的总和与时段驶离的车辆数(调配驶离+提供服务驶离)加上在站车辆数的总和相互守恒,即
式中,为路径的到达点;为路径的始发点;表示所有始发点为租赁站的路径集合;表示所有到达点为租赁站的路径集合。
对于任意车辆,只有时段停留在租赁站或驶入租赁站的车辆,在时段才能继续停留在站或驶离站,即
1)电池蓄电量
式中,为时段车辆电池蓄电量;为充电时间;为车辆行驶路径损耗电量。
2)蓄电池容量约束
式中,为蓄电池额定容量;、分别为蓄电池荷电状态允许的最小值和最大值,分别取0.1与0.9。
3)充电功率约束
式中,为充电功率最大值。
对于任意租赁站,时段充电功率不能过大,否则导致电网出现重载甚至过载,即
式中,为时段租赁站允许最大充电功率。
式中,为时段在路径上被满足的租赁需求数;为时段路径上租赁需求总数。
上述模型基本为线性,对其非线性部分进行线性化处理,将模型转变为混合整数线性规划模型,便于采用商业化的线性规划软件求解。
模型中,式(1)、式(5)、式(9)中项为两个变量相乘的非线性形式,为0-1变量,为连续变量,引入两个中间变量、将原模型线性化,线性化步骤如下:
将式(1)、式(5)、式(9)中项替换为,并加入等式约束式
加入不等式约束式
式中,、分别为的上、下限,分别表示充电功率最小值与最大值,取0与额定充电功率。
经过上述变化后原模型转化为线性模型,但增加了两个变量和三个约束条件式。
本文以我国某城市出租出行需求为参考,基于热点出行路线分布情况,以某共享汽车运营商在城市中运营5个汽车租赁站为场景,租赁站分布如图2所示,其中3号站位于主城区,其余4个站点分散位于城郊不同方向;各租赁站间直线距离见表1。算例场景中,运营商投资配置15辆电动汽车作为共享汽车,车载电池额定容量为57kW×h,续航里程为200km;租赁站点配置功率为40kW快充桩,接入剩余供电能力有裕度的10kV线路;运营商提供租赁服务收费为1元/km,共享车辆的调配成本取0.8元/km;运营商支付给电网的充电电价为1元/(kW×h)。
表1 各租赁站间距离
Tab.1 Distance between rental stations (单位:km)
站点12345 12345015142016150122020141201215202012018162015180
图2 租赁站点地理位置分布
Fig.2 Location of rental stations
本文在Matlab中调用Gurobi求解器,运用混合整数线性规划方法实现上述算例的模型求解,求解时长为105s。
考虑夜间出行较少,算例中优化调度的时间段取6:00~22:00,以1h为时间间隔,共16个时段,即,。典型日电动共享汽车租车需求分布如图3所示。
图3 典型日客户需求曲线
Fig.3 Typical daily user demand curve
4.2.1 优化调配决策结果分析
利用本文模型,决策该共享汽车运营商车辆调配优化方案见表2。
表2 优化调配方案
Tab.2 Optimal deployment strategy
时段序号时间区间调配车辆数路径O-D 16:00~7:0021-53-1 27:00~8:0013-1 38:00~9:0043-13-41-5 49:00~10:0023-13-4 510:00~11:0013-4 611:00~12:000— 712:00~13:0023-23-4 813:00~14:000—
(续)
时段序号时间区间调配车辆数路径O-D 914:00~15:0011-5 1015:00~16:0011-2 1116:00~17:0014-3 1217:00~18:0022-34-3 1318:00~19:0021-35-3 1419:00~20:0021-3 1520:00~21:000— 1621:00~22:0031-31-4
从5个租赁站分别选取初始停靠在该站的1辆车作为分析对象,共5辆车,开展优化调度模型的合理性分析,具体包括:
1)模型能够分析共享电动汽车在运营商车辆调配方案下时空状态的转移特性,如图4所示。
图4 典型车辆调度周期内时空状态转移特性
Fig.4 Typical vehicle space-time transition characteristics in the scheduling period
图4中,纵轴表示五个租赁站点,横轴表示调度周期内16个时段;每个圆圈表示一种时空状态,包含时标和租赁站点地标两维信息;五种颜色的路径线分别代表五辆共享电动汽车的出行轨迹,轨迹中的实线段表示车辆在租赁、空闲、充电情况下的时空状态转移,其中同一站点间水平实线表示停留此站闲置或充电状态,虚线表示调配情况下车辆的时空状态转移。
共享汽车运营商满足客户租赁需求的能力,与其配备共享电动汽车数量呈正相关,然而增加车辆规模也会增加运营商的投资和运维成本,实际运营中为了降低投入成本与车辆闲置率,需结合租赁站点位置分布(见图2)与客户需求特性(见图3),规划投资适宜的共享车辆数目。本例中,运营商拟以15辆电动汽车为空间分散度较大的5个租赁站点的需求提供服务。
图4展示了五辆车在整个调度周期内满足客户租赁需求、调配、在租赁站点闲置或充电四种情况下的时空状态转移特性。从图3典型日客户需求曲线可以看出,上午6:00~9:00,下午16:00~19:00为需求高峰时段。从表2优化调配方案结果与图4车辆时空状态转移结果可分析得到,在需求高峰时段租赁需求量增大时,运营商提前调配其他租赁站点可用车至需求高峰站点以满足需求高峰时段的租赁服务。如图4中6:00~7:00运营商将1号汽车(黑色箭头)从1号租赁站调配至5号租赁站以满足8:00~9:00 5号租赁站的租赁需求,7:00~8:00运营商将2号汽车(红色箭头)从3号租赁站调配至1号租赁站以满足下一时段1号租赁站的租赁需求。而在租赁需求较少、供过于求的时段,如中午时段与调度周期末,共享电动汽车在租赁站点充电或闲置,等待满足后面时段的租赁需求,以提高运营收益。如图4中9:00~13:00,21:00~22:00,红色、黑色、黄色箭头代表的三辆汽车均在站内停留等待,为后续时段的租赁需求调整状态。
2)本文模型能够结合共享电动汽车的时空状态转移描述车载电池荷电状态变化,如图5所示。
图5 车载电池荷电状态变化特性
Fig.5 Variation characteristics of state-of-charge of on-board batteries of vehicles
图5中,纵坐标表示电池剩余电量,横坐标表示时间。选取1号样本车辆(对应黑色)分析其时空状态转移与车载电池荷电状态变化。结合图4信息,为满足5号租赁站点在时段3的高峰需求,1号车辆在第1时段被提前调配至5号租赁站点;此时,车载电池电量减少;第4时段停留在3号租赁站点充电,充电计划如图5所示,在9:00~10:00车载电池电量增大;第5:00~6:00段停留在3号租赁站点闲置,车载电池电量不变;为满足第9、11、13时段的高峰需求,分别在第7、10、12时段调配至需求站点,最后停留在1号站点充至满电状态,为下一时段优化运行做好准备。1号样本车辆在调度周期内共充电两次,第一次为浅度充电以满足后续时段的租赁需求,第二次为调度周期末深度充电,为下一个调度周期做好准备。
3)模型能够分析租赁业务供给和需求时空匹配特性,如图6所示。
图6 需求高峰时段车辆的空间变化特性
Fig.6 Characteristics of vehicle spatial variation during peak demand
算例分别选取两个租赁需求在空间上有较强规律性的时段分析供需时空匹配特性。图6中,实线表示客户租赁状态下车辆空间变化,虚线表示调配状态下车辆空间变化。图6a为上午8:00~9:00(早出行需求高峰),客户租赁需求较大,共享电动汽车多服务于从城郊驶向城市中心方向的租赁订单需求,运营商为提高后续时段的供需匹配能力,在该时段同时将城中心站闲置车辆向城郊站调配,这与表2所示该时段调配结果相匹配,调配方向多为从城市中心的3号租赁站呈辐射式向城郊1、2、4、5号租赁站调配;图6b为17:00~18:00(晚出行需求高峰),由城中心驶向城郊的租赁需求较大,共享电动汽车多服务于客户驶离城市中心方向的租赁需求,决策出运营商的车辆调配方案是将空闲在2号和4号城郊站的车辆向城中心站调配,以满足更多客户的租赁需求,这与表2在该时段调配结果相匹配,调配方向多为从城郊1、2、4、5号租赁站向城市中心的3号租赁站调配,以满足客户租赁需求,提高车辆使用效率。
综上可见,本文基于网络流分析理论建立的电动共享汽车优化调度模型,能够表征共享汽车时空状态转移和车载电池荷电状态变化,模型决策出的车辆调配计划和充电计划有利于促进共享汽车租赁业务供需时空匹配,提高共享汽车运营商的收益。
4.2.2 优化调度结果效果对比分析
表3和图7对比了运营商在有无实施车辆优化调配的两种场景下,一个调度周期内租赁服务收入、成本支出、车辆闲置率以及满足的需求量等指标的变化情况。
表3 优化调度结果对比
Tab.3 Comparison of optimized scheduling results
指标未调配优化调配变化量 满足用户需求收入/元调配成本/元充电成本/元净收益/元车辆闲置率(%)满足用户需求量/单1 0510117.718933.28270.83701 711321.6148.9661240.43435.83105+660+321.6+31.248+307.152-35.00+35
图7 满足用户需求量对比
Fig.7 Comparison to meet user demand
由表3可见,未开展车辆优化调配场景下,共享电动汽车只在满足用户需求、闲置、充电三种状态之间转换,供需匹配能力受限,车辆闲置严重。考虑优化调配方案的场景下,虽需要新投入调配成本与增加充电成本,但最终的净收益增加,相比未开展车辆优化调配场景提高32.91%。且运营商通过车辆优化调配使得车辆闲置率由70.83%降为35.83%,满足的用户需求量由70单提高至105单,图7中大部分时段的服务能力均有提高。
与传统燃油共享汽车优化调配问题相比,共享电动汽车的优化调度还涉及配套充电计划的优化决策。本文基于网络流分析,建立的共享电动汽车优化调度混合整数线性规划模型,实现了车辆调配与充电计划的联合优化。算例分析表明:
1)本文结合共享电动汽车租赁业务特点,在传统网络流分析模型中,添加共享电动汽车的车辆状态约束、状态转移守恒约束以及租赁站车流量守恒约束,嵌入车辆承接共享订单可用性的状态判断,可实现共享电动汽车租赁业务时空维度的供需匹配分析。
2)共享电动汽车优化调度的收益水平与车辆数量和车载电池容量关联,算例中运营商收益提高了32.91%,需求满足量提高了50%。
共享电动汽车作为电动汽车推广发展的新兴商业模式,发展空间广阔。本文模型尚未考虑道路拥堵的不确定性影响,以及调配策略对车载电池寿命损耗的影响,后续有待开展更精准的建模研究,进一步提高共享电动汽车运营商的收益与租赁服务能力,提高用户满意度,促进绿色智慧电力交通互联网的建设。
参考文献
[1] Weik I S, Bogenberger K. Relocation strategies and algorithms for free-floating car sharing systems[J]. IEEE Intelligent Transportation Systems, 2013, 5(4): 100-111.
[2] Jorge D, Molnar G, Correia G H D A. Trip pricing of one-way station-based carsharing networks with zone and time of day price variations[J]. Transportation Research Part B: Methodological, 2015, 81(2): 461-482.
[3] Clemente M, Fanti M P, Mangini A M, et al. The vehicle relocation problem in car sharing systems: modeling and simulation in a petri net framework[C]// International Conference on Applications and Theory of Petri Nets and Concurrency, Springer, Berlin, Heidelberg, 2013: 250-269.
[4] Boyacı B, Zografos K G, Geroliminis N. An optimization framework for the development of efficient one-way car-sharing systems[J]. European Journal of Operational Research, 2015, 240(3): 718-733.
[5] Carlier A, Munier-Kordon A, Klaudel W. Mathematical model for the study of relocation strategies in one-way carsharing systems[J]. Transportation Research Procedia, 2015, 10: 374-383.
[6] Lu Mengshi, Chen Zhihao, Shen Siqian. Optimizing the profitability and quality of service in carshare systems under demand uncertainty[J]. Manufacturing& Service Operations Management, 2018, 20(2): 162-180.
[7] 麻秀范, 王超, 洪潇, 等. 基于实时电价的电动汽车充放电优化策略和经济调度模型[J]. 电工技术学报, 2016, 31(增刊1): 190-202.
Ma Xiufan, Wang Chao, Hong Xiao, et al. Optimal scheduling of charging and discharging of electric vehicle based on real time price and economic dispatch model[J]. Transactions of China Electrotechnical Society, 2016, 31(S1): 190-202.
[8] 刘星平, 李世军, 于浩明, 等. 住宅小区内电动汽车有序充电优化模式[J]. 电工技术学报, 2015, 30(20): 238-245.
Liu Xingping, Li Shijun, Yu Haoming, et al. Coordinated charging optimization mode of electric vehicles in the residential area[J]. Transactions of China Electrotechnical Society, 2015, 30(20): 238- 245.
[9] 牛利勇, 张帝, 王晓峰, 等. 基于自适应变异粒子群算法的电动出租车充电引导[J]. 电网技术, 2015, 39(1): 64-69.
Niu Liyong, Zhang Di, Wang Xiaofeng, et al. An adaptive particle mutation swarm optimization based electric taxi charging guidance[J]. Power System Technology, 2015, 39(1): 64-69.
[10] 李斌, 刘畅, 陈慧妙, 等. 基于混合整数规划的电动公交车快速充电站有序充电策略[J]. 电网技术, 2016, 40(9): 2623-2630.
Li Bin, Liu Chang, Chen Huimiao, et al. Coordinated charging of plug-in electric buses in fast charging stations based on mixed-integer programming[J]. Power System Technology, 2016, 40(9): 2623-2630.
[11] 杨少兵, 吴命利, 姜久春, 等. 快换式电动公交充电站经济运行优化策略[J]. 电网技术, 2014, 38(2): 335-340.
Yang Shaobing, Wu Mingli, Jiang Jiuchun, et al. Optimal strategy for economic operation of electric bus battery swapping station[J]. Power System Technology, 2014, 38(2): 335-340.
[12] 刘灵恺, 雷霞, 李竹, 等. 电动汽车换电站可用电池组数动态调度策略[J]. 电工技术学报, 2017, 32(22): 242-250.
Liu Lingkai, Lei Xia, Li Zhu, et al. Dynamic scheduling strategy for available battery number of electric vehicle in battery-swap station[J]. Transactions of China Electrotechnical Society, 2017, 32(22): 242-250.
[13] Yang Jun, Sun H. Battery swap station location-routing problem with capacitated electric vehicles[J]. Computers & Operations Research, 2015, 55: 217- 232.
[14] Hof J, Schneider M, Goeke D. Solving the battery swap station location-routing problem with capacitated electric vehicles using an AVNS algorithm for vehicle-routing problems with intermediate stops[J]. Transportation Research Part B: Methodological, 2017, 97: 102-112.
[15] Hiermann G, Puchinger J, Ropke S, et al. The electric fleet size and mix vehicle routing problem with time windows and recharging stations[J]. European Journal of Operational Research, 2016, 253(3): 995-1018.
[16] Paz J, Granada-Echeverri M, Escobar J. The multi-depot electric vehicle location routing problem with time windows[J]. International Journal of Industrial Engineering Computations, 2018, 9(1): 123-136.
[17] Zhao Meng, Li Xiaopeng, Yin Jiateng, et al. An integrated framework for electric vehicle rebalancing and staff relocation in one-way carsharing systems: model formulation and Lagrangian relaxation-based solution approach[J]. Transportation Research Part B Methodological, 2018, 117: 542-572.
Optimal Scheduling of Sharing Electric Vehicles Based on Network Flow
Abstract With the popularization of Internet of vehicles, cloud computing, and big data applications, the sharing electric vehicle rental business, which represents “Internet + travel”, has a broad development space due to its flexibility, convenience, and environmental protection. The time-space distribution of the car-sharing and car-sharing customers does not match, which is the key problem faced by the car-sharing operators to improve their revenue. Based on the network flow model, taking into account the impact of electric vehicle charging on the status of vehicles that can provide rental services, and at the same time realizing the analysis of the supply and demand of the rental business in the time and space dimensions; and combining the characteristics of the rental business, it proposes the conservation of traffic flow at the rental site and the sharing vehicle status transfer conservation constraints. Taking the operator's maximum net income as the optimization goal in the dispatch cycle, considering the road network, car, rental demand and charging network constraints, a mixed integer linear model of sharing electric vehicle optimal dispatch is established to optimize the decision of vehicle deployment plan and charging plan. The calculation example shows that the optimized scheduling strategy can improve the revenue and user satisfaction of shared electric vehicle operators.
keywords:Sharing electric vehicles, network flow, vehicle routing problem, charging plan, mixed integer linear programming
DOI:10.19595/j.cnki.1000-6753.tces.L90513
中图分类号:TM74
国家自然科学基金资助项目(51907063)。
收稿日期 2020-07-11
改稿日期 2020-11-02
程 瑜女,1978年生,博士,副教授,研究方向为电力系统经济分析、电力市场、电力系统规划。E-mail: judychengyu@163.com(通信作者)
邰宇峰男,1996年生,工程师,研究方向为电力系统经济分析、高电压与绝缘技术。E-mail:taiyufeng0909@163.com
(编辑 郭丽军)