基于GPS轨迹挖掘的电动出租车充电站规划

苏 粟，李玉璟，贾泽瑞，杨 锦，夏明超，陈奇芳

（1. 北京交通大学 电气工程学院，北京 100044；2. 国网山西省电力公司晋城供电公司，山西 晋城 048000）

0 引言

为了缓解能源和环境问题的严峻程度，发展电动汽车已成为全球共识。出租车作为城市交通网络中的重要交通工具，其单辆日行驶里程通常超过300 km，据计算，在汽车使用阶段的单位行驶里程下，电动出租车的碳排放量相较于燃油出租车约减少70%［1］。因此，出租车行业实现全面电动化是大势所趋，其给社会环境带来的效益也是显而易见的。考虑到不同类型电动汽车的充电行为具有较大的差异性：电动私家车大多用于用户通勤、娱乐等，空闲时间相对较长，其相应的充电地点大多集中在办公停车场、居民小区等；电动公交车的运营时间和运营路线较固定，其大多在专用场站进行快速充电；电动出租车的日行驶里程较长，且充电地点较为灵活，制定切实可行的充电设施部署方案是出租车行业实现电动化的重要前提和基础［2］。

充电站CS（Charging Station）的选址定容优化问题受到多种因素的制约，同时受城市土地建设、交通流量、城市人口分布等多方面的影响。文献［3］建立了以电网运行损失最小和充电站运行效益最优为目标的双层规划模型，但未考虑用户侧利益；文献［4］考虑服务能力最大化进行充电站网络规划；文献［5］以充电站年总成本最小为优化目标，虽然考虑了充电站的建设覆盖率，但未考虑用户侧利益。在此基础上，文献［6］将用户选择充电时的距离偏好和等待时间偏好考虑在内，提高了用户充电的便利性；文献［7］引入用户广义充电成本的概念，用于描述通勤者到充电站充电所消耗的时间成本，但是未将用户到达充电站后的时间成本计算在内；文献［8-10］利用排队论建立了用户充电排队等待时间成本模型，对充电站容量进行优化；文献［11］将未来电动汽车数量的增长考虑在内，以充电站成本和用户经济损失最小为目标对充电站进行选址定容；文献［12］综合考虑电动出租车的出行需求、用户充电行为的耗时成本和充电站的建设成本，建立了电动出租车充电站的规划模型。上述研究均从充电站和用户二者的利益均衡角度出发，对充电站的选址定容进行优化，但是未对城市内电动汽车充电需求的时空分布状态进行详细建模，一般将其假设为已知或通过给定的起屹点OD（Origin Destination）需求简单得出。没有准确可靠的充电需求时空分布，就不能精确定位电动汽车到达每个充电点的行驶时间和排队时间，从而难以确保充电站选址定容结果的准确性。文献［13］基于电动出租车的全球定位系统GPS（Global Position System）数据建立充电站充电需求的时空分布预测模型，但未将GPS 数据应用到充电站的规划领域；文献［14］提出了一种新的基于高密度城市地理信息系统GIS（Geographic Information System）的充电基础设施规划模型；文献［15］基于北京市出租车的历史轨迹，研究了公共充电站的位置选择问题；文献［16］基于2000 年加州家庭旅游调查数据集和ArcGIS 平台确定的已知地理位置之间的最短路径，确定覆盖率最大的充电位置集合；文献［17］基于罗马市区内传统私家车旅行的实际数据，采用集群分析方法确定候选充电站的位置；文献［18］对城市交通进行网格化处理，根据电动汽车用户的旅行记录确定停车次数在空间上的分布情况，以此优化充电站的位置。但上述研究只对充电站的选址进行了规划，未进一步对站内充电机的数量进行优化。

针对城市出租车实现全面电动化面临的充电设施规划问题，本文将实时交通模拟、充电行为模拟和数学优化模型相结合，提出了基于出租车GPS 轨迹数据挖掘的充电站规划方法，通过确定充电站的位置及站内充电机的数量配置，保证城市电动出租车系统的正常高效运行。首先，采用数据挖掘技术获取城市交通网络和车辆的运行数据，基于出租车GPS 行驶轨迹数据生成区域内居民打车需求信息；然后，设计电动出租车的充电仿真算法，根据行驶轨迹模拟实际场景中电动出租车的接单行为及充电行为，建立电动出租车的充电需求时空分布模型；最后，基于充电需求时空分布预测结果，综合考虑充电站建设运行成本和电动出租车时间成本，提出电动出租车充电站的综合规划方法。

1 城市出行数据的挖掘与融合

本文以滴滴出行公布的西安市部分区域2016年10 月至11 月订单轨迹数据（数据源自“盖亚数据开放计划［19］”）为基础，选取西安市的核心区域为研究对象，区域的经度范围为108°54′2″E～108°59′53″E，纬度范围为34°12′29″N～34°16′41″N，示意图如附录A 图A1所示，地图信息从高德地图获取。数据集描述、数据清洗及处理、地图匹配、功能区识别等数据处理过程见附录B。基于滴滴出行的数据集，通过数据挖掘与融合进行建模分析，获取出租车路网通行数据集、OD 出行集、车辆行驶轨迹集等一系列衍生数据。

1）路网通行数据集。

利用高德地图经纬度拾取器获取道路重要节点的经度、纬度信息，结合Open Street Map 开源网站获取所选区域路网的矢量图，采用图论分析方法描述交通路网的拓扑结构，如式（1）所示。

式中：GG为整个交通路网的拓扑结构图，由节点集合N、道路集合E、道路长度集合D、车辆通行速度集合V四部分组成；n为节点数量；m为道路数量；dl、vl分别为道路l的长度、车辆通行速度。通过计算每个GPS 轨迹点的瞬时通行速度，得到不同时刻道路中车辆的通行速度信息。

2）OD出行集。

将出租车轨迹数据按照时间序列进行排列，提取每个订单的上车点和下车点，得到OD 数据g={LO，TO，LD，TD}，其中LO、LD分别为起点、终点位置，TO、TD分别为出发、到达时间。遍历所有订单，得到OD出行集GOD={ }g1，g2，…，gM，其中gj(j=1，2，…，M)为第j个订单OD 数据，M为该天的有效出行订单数量。

融合OD 出行集和附录C 图C1 所示功能区识别结果，得到城市居民打车出行的时空分布特征，如附录C图C2所示。

3）车辆行驶轨迹集。

基于地图匹配结果进行车辆轨迹识别，每个订单的起点位置与终点位置之间行驶轨迹的交通节点集合可表示为：

2 电动出租车充电需求时空分布预测模型

2.1 运营特性

1）运营时间。出租车公司实行两班制运营，受行业或管理因素的影响，部分出租车采取一班制运营。换班时段一般为07:00—08:00、15:00—16:00，具体的换班时刻由2 名司机协商决定，且电动出租车凌晨是否运营取决于司机自身。

2）载客行驶特性。电动出租车司机根据自身经验选择最短／最快路线或根据打车软件的既定路线行驶，将乘客载至目的地，且在载客过程中不能进行电能补给。

3）空载行驶特性。在空载行驶阶段，电动出租车司机根据自身经验或相关软件向订单密集区域行驶，期望在最短时间内找到有打车需求的乘客［20］。

2.2 充电特性

本文选取电动出租车车型为比亚迪E5，电池容量为60.48 kW·h。电动出租车在不同等级道路上行驶的单位里程耗电量可表示为：

2.3 充电需求判断

电动出租车会在以下3种场景产生充电需求。

1）剩余电量达到阈值场景：本文设定电动出租车产生充电需求时的电池荷电状态SOC（State Of Charge）阈值为30%，电动出租车司机在结束本次行程的最后1 min 内可以使用打车软件接收下一个订单。若电池SOC 小于30%且巡游1 min 后仍无乘客订单，则产生充电需求；若电池SOC 小于20%，则立即产生充电需求。

2）换班场景：电动出租车的换班时段由西安市出租汽车管理处获得，两班制运营的换班时段为07:00—08:00、15:00—16:00。当电动出租车处于换班时段内且订单完成时产生换班信号，其在换班时段前及换班时段内是否需要充电由电池剩余电量决定。若在换班过程中需要充电，则换班过程的持续时长为该电动出租车的充电时长；若在换班过程中无需充电，则经换班后可继续接单。第h辆电动出租车的充电需求判断如式（4）所示。

3）三餐场景：电动出租车会在司机吃饭的时段内短暂停止运营，部分司机会选择在午餐／晚餐时段进行短时间充电。设定在12:00—13:00 时段内，若司机寻客5 min 仍无订单，则产生午餐需求，且在下午不换班的一班制运营模式下，一般有20%的司机会选择将电动出租车停至充电站，边充电边进餐，但若临近换班时段，司机的运营意愿较高，则该比例会降低至10%。在18:00—20:00 时段内，若司机寻客5 min 仍无订单，则产生晚餐需求，下午没有进行换班的司机中有20%会选择将电动出租车停至充电站，边充电边进餐，其他司机会因为下午刚换班而没有晚餐需求或者会选择快速解决晚餐。

在司机吃饭过程产生充电需求的充电时长与午餐和晚餐的时长相同，分别服从正态分布N（22.8，2）和N（23.7，2）［21］，单位为min。

2.4 充电需求预测

将OD 出行集作为城市居民的打车需求，设计电动出租车的充电仿真算法，模拟电动出租车的运营场景，建立电动出租车充电需求时空分布预测模型，流程图如附录D图D1所示，具体步骤如下。

1）通过对订单数据集进行挖掘与融合，获取研究区域范围、路网通行数据集、OD出行集、车辆行驶轨迹集等一系列衍生数据。

2）初始化电动出租车的参数，包括电动出租车总数量NEV、采取一班制和两班制运营模式的电动出租车数量、开始工作时刻、结束工作时刻、换班时刻以及初始电量。

3）按开始工作时刻对电动出租车进行编号。

式中：to为订单需求产生的时刻。式（7）表示该订单需求产生的时刻要早于当前时刻，且订单需求的起点位置与电动出租车之间的距离在1 km以内。

6）司机接单，更新订单需求，即在订单需求库中删除该需求。

9）判断h是否等于电动出租车总数量NEV，若等于，则结束流程；否则，令h=h+1，转至步骤4）。

基于上述流程建立电动出租车的充电需求时空分布模型，为充电站的规划建模提供必要的输入数据。对于人口相对稳定、道路基础设施发达的城市而言，其居民出行模式、交通系统趋于一致并保持稳定。在可预测的未来情况下，可根据电动汽车市场的渗透率，利用现有的出租车轨迹来估计充电时空分布的演化状况，对充电站网络进行改造或扩建。

3 电动出租车充电站规划模型

本文提出一种将实时交通模拟、电动出租车接单行为模拟、行驶轨迹模拟、充电行为模拟和数学优化模型相结合用于解决城市大规模充电站网络规划问题的方法。基于电动出租车的充电需求时空分布模型，将OD 出行集和交通网络属性作为输入，模拟电动出租车的接单行为和路径选择行为，获取充电需求的时间和空间分布状况。在此基础上，综合考虑充电站的建设运行成本、电动出租车的到站时间成本和充电等待时间成本，确定充电站规划的最佳位置和充电机的最优数量。

3.1 充电站的建设运行成本

考虑时间范围Γ={0，1，…，T}内的电动出租车行驶轨迹数据集，根据第2 节确定充电需求时空分布。考虑到合适的充电地点应该有足够的停车位和良好的可达性，候选充电地点可以是出租车站、加油站和停车场，并可获取其位置信息。

若候选站点i∈I（I为所选的充电站点集合）被选为建设充电站，则应考虑充电站的建设运行成本，主要包括前期建设时的土建、电网设施、充电机、相关保护设备等的建设成本和投入运营后的设备日常维护成本、人力费用等。充电站的建设成本Cstation可表示为：

式中：r0为贴现率；ms为充电站的折旧年限；ξ为充电机配套设施费用的等效系数。

3.2 电动出租车的时间成本

电动出租车的时间成本包括到站时间成本和充电等待时间成本。假设当产生充电需求时，电动出租车司机拟选择最短耗时路径到达充电站，计算所有电动出租车从充电需求产生地点到达候选充电站点的时间成本，如式（13）所示。

当电动出租车到达目的地时，若充电站内仍有空闲充电机，则可以安排立即充电；若充电机均被占用（即发生充电拥堵），则需要排队等待。本文对实际70 座充电站1 个月的真实运营数据进行分析，得到充电站内电动汽车到达时间间隔服从负指数分布，并对充电站内15 369 条快充订单的充电时长进行概率拟合，如图1 所示。图中曲线为使用期望最大化EM（Expectation-Maximum）算法得到的拟合曲线，其充电时长期望为0.736 h，方差为0.122 5，拟合公式如式（17）所示。

图1 充电时长概率分布Fig.1 Probability distribution of charging time

式中：tc为充电时长，其服从多高斯分布。

由真实充电站的运营数据获得电动出租车司机到达时间间隔服从负指数分布，充电时长服从多高斯分布，符合M／G／k 排队模型。M／G／k 排队模型中的服务时长服从一般分布G，一般分布G的期望为ET，方差为VT，则M／G／k 排队模型的平均等待时长WGq的近似计算公式为：

在规划模型中，通过改变充电站内充电机的数量ki，可根据式（18）计算得到该充电站不同容量配置下电动出租车的平均等待时长。由第2 节的电动出租车充电需求时空分布预测模型可得到一天内各时段在各交通节点处的充电需求数量，通过规划模型可得到到达每座充电站的充电需求数量。一天内电动出租车的充电等待时间成本Cwaiting可表示为：

式中：Tyear为规划天数。

3.3 综合优化目标函数

充电站规划的目的是确定充电站的建设位置和充电机的配置数量。当充电机数量足够大时，虽然站内不会出现排队等待现象，但充电站的建设运行成本会急剧增加；当充电机数量不大时，电动出租车的排队等待时间会延长，导致充电站的服务水平降低，不利于充电站的长期运营。为此，需要通过权衡电动出租车的时间成本与充电站的建设运行成本两方面，建立充电站的规划模型。目标函数为：

式中：α∈[0，1]为权重系数。

4 算例分析

4.1 场景描述

本文利用西安市部分区域2016 年10 月至11 月共61 d 的订单轨迹数据，对每天的电动出租车轨迹数据进行处理，轨迹数据处理流程图如附录D 图D2所示。考虑城市充电站的规划建设应以最大限度地满足电动出租车司机的运营利益为目标，同时兼顾建设运行成本，本文选择在充电高峰时段进行规划，此时的充电订单较多，充电需求较平时段高；同时，在规划过程中考虑电动出租车的充电等待时间，其平均等待时长不超过10 min。基于2.4 节模拟得到每天的充电需求时空分布情况，选取其中单天充电需求数量最多且在充电高峰时段内充电需求数量最多的1 d，作为该区域内充电站规划的参考日，生成区域充电需求的空间分布。通过高德地图经纬度拾取器获取道路重要节点的经度、纬度信息，结合Open Street Map 开源网站获取所选区域的路网矢量图。研究区域道路拓扑结构如附录D 图D3所示，共包含373个交通节点以及638条道路，其中一级道路、二级道路分别为255、383 条。电动出租车充电站规划模型的相关参数参考文献［22-23］，具体取值如附录D表D1所示。

4.2 充电需求预测结果

利用11 月21 日至27 日的GPS 轨迹数据，得到该一周内的充电需求分布，如附录D 图D4所示。可以看出，一周内非工作日与工作日的充电需求分布比较相似，非工作日的充电需求量较工作日的充电需求量有所降低。为了直观地表达充电需求在空间上的分布，将充电需求点聚集至与其距离最近的交通节点，11月25日充电需求预测结果的空间分布情况如附录D 图D5所示，图中红色柱体为交通节点及在节点附近产生充电需求的频次，平面为研究区域的路网拓扑结构。

结合附录A 图A1 和附录D 图D5 可知，研究区域大多位于市区，人流量较大，打车点和下车点都相对密集，造成部分边缘区域的充电需求较多。1 d内的总充电需求数量为2 234，预测所得充电需求中有71.75%发生在一级道路上，而在本文研究的路网拓扑中，一级道路仅占道路总数的39.9%，因此可推断道路等级越高，电动出租车在该路段产生充电需求的概率越大。文献［24］对波士顿地区进行研究，验证了主要道路上电动汽车充电需求更多的结论。

以半径为1 000 m 的圆形区域为例，通过计算充电需求数量与交通节点数量的皮尔逊相关系数，得到二者在一定区域内具有较强的正相关性，交通节点数量每增加5 个，有充电需求的电动出租车数量约增加119 辆，即在路网越密集的区域，电动出租车产生充电需求的概率越大。

由上述分析可知，充电需求与空间域的道路等级、交通路网密度的相关性较强，即在产生充电需求概率较高的区域内，交通特征比区域功能特征更明显。在充电站选址规划中，从投资商的利益角度出发，交通功能比土地使用功能更重要［25］。

4.3 充电站规划结果分析

为了得到最优的充电站规划配置方案，以1 d中充电订单最多的时段为充电站规划基础，利用改进的自适应惯性权值粒子群优化算法对规划模型进行求解。模型求解过程见附录E，求解流程图见附录E图E1。当充电站数量为3～17座时，由式（25）可得总成本的变化情况如图2所示。

图2 总成本随充电站数量的变化情况Fig.2 Change of total cost vs. number of charging stations

由图2 可以看出：当充电站数量少于8 座时，电动出租车的时间成本占据较大的比重，由于充电站数量过少，电动出租车的到站时间成本增加，导致总成本较高；当充电站数量为8 座时，总成本最小；随着充电站数量继续增多，虽然在一定程度上减少了电动出租车的到站时间成本和充电等待时间成本，使其时间成本降低，但是充电站的建设运行成本大幅增加，导致总成本增大。综上可知，充电站的最优规划数量为8座。

8 座充电站（CS1—CS8）的最优规划结果如附录F 图F1 和表1 所示。由表1 可知，8 座充电站的充电机配置数量均在允许安装充电机的最小、最大数量范围内，电动出租车的平均等待时长均小于10 min。以充电需求数量较多或排队等待时间较长的CS1、CS2、CS4为例，对站内的充电情况进行动态仿真。在14:00—15:00 时段，CS1、CS2、CS4内有充电需求的电动出租车数量分别为75、74、33 辆，充电机的最优配置数量分别为42、41、19 台，电动出租车的到达时刻、离开时刻、充电等待时长、停留时长如附录F 图F2 所示。由图可知，3 座充电站的平均等待时长均在10 min以内，且在14:00时刻，CS1内的空闲充电机数量明显少于CS2内的空闲充电机数量，当CS1服务的电动出租车数量超过10 辆时出现排队现象，此时的停留时长为排队等待时长与充电时长之和。

表1 充电站的最优规划结果Table 1 Optimal planning results of charging stations

4.4 灵敏度分析

本节分析候选站点建设充电站的建设成本系数cstation、电动出租车时间成本折算系数ctime、权重系数α、电动出租车电池容量等参数对规划结果的影响。

cstation变化对规划结果的影响如图3 所示。由图3（a）可以看出，随着cstation增大，总成本以稳定的斜率增大，到站时间成本和充电等待时间成本间断性增大。由图3（b）可以看出，随着cstation增大，充电站数量不断减少，为了最大限度地满足电动出租车的充电需求，虽然每座充电站内的充电机数量有所增大，但充电机的总数量受充电站数量的影响而减少。该区域内充电站的分布密度随充电站数量的减少而降低，电动出租车的到站时间成本增大，且由于充电机总数量减少，单座充电站内的充电需求数量增多，电动出租车的平均等待时长有所增大。

图3 cstation变化对规划结果的影响Fig.3 Influence of cstation change on planning results

ctime变化对规划结果的影响如图4 所示。由图4（a）可以看出，随着ctime取值的增大，总成本、电动出租车的到站时间成本和充电等待时间成本呈近线性增长趋势，须通过增加充电站数量来提高区域内的充电站分布密度，进而减少电动出租车的到站时间成本，通过增加充电机的数量来避免充电等待时间成本的过度增加。结合图3 和图4（b）可知，充电站数量对充电机总数量的影响较大，充电机总数量随着充电站数量的变化而同时变化。

图4 ctime变化对规划结果的影响Fig.4 Influence of ctime change on planning results

权重系数α变化对规划结果的影响如图5所示。由图可知：随着权重系数α逐渐增大，充电站数量和充电机总数量均显著减少，因此导致电动出租车的到站时间成本和充电等待时间成本增大；随着权重系数α逐渐增大，电动出租车的利益在规划目标中的比重逐渐下降，且电动出租车的时间成本相比充电站的建设运行成本在数值上较小，因此总成本呈现缓慢减小的趋势。

图5 α变化对规划结果的影响Fig.5 Influence of α change on planning results

上述均在电池容量为60.8 kW·h 的情况下进行分析。为了进一步探究电池容量对充电站规划的影响，将电动出租车的电池容量设置为30 kW·h，所得充电需求预测结果和充电站的规划结果分别如附录F 图F3 和图F4 所示。由图可看出：当电池容量减小时，单天的充电需求数量增加为4026，相较于附录D图D5，充电需求数量增多，但其空间分布情况并没有显著差异；此时充电站的最优规划数量为16座。

5 结论

本文提出了一种基于GPS轨迹挖掘的电动出租车充电站规划方法，基于出租车GPS 轨迹数据和实时交通态势，通过交通模拟以及电动出租车接单模拟、轨迹行驶模拟、充电行为模拟，对电动出租车的充电需求时空分布进行预测。在考虑充电排队行为下，提出了一种电动出租车充电站规划模型，用于配置充电站的位置和充电机的数量。所得主要结论如下。

1）通过对出租车轨迹数据进行挖掘与分析，得到路网通行数据集、OD 出行集和车辆行驶轨迹集，并基于此得到以电动出租车作为出行方式的居民出行时空分布特征数据，按照真实的行驶轨迹进行仿真模拟，提高了充电需求预测的准确性，从而可进一步得到充电需求点与OD之间的紧密联系。

2）利用充电站的真实运营数据进行仿真，分析充电站的排队行为，并建立充电站的规划模型。该模型综合考虑充电站的建设运行成本、电动出租车的到站时间成本和充电等待时间成本，用于确定充电站的最佳布局，包括充电站的最优数量和位置、充电站内充电机的最优配置数量、平均等待时长、每座充电站覆盖的交通网节点及其充电站规划成本等。

3）通过灵敏度分析说明某些参数对充电站规划结果的影响。充电机数量受充电站数量的变化影响较大，电动出租车时间成本折算系数变化对总成本的影响相对较明显，因此在时间成本折算系数取值较大的情况下，适当增加充电站的分布密度可以有效降低总成本，对决策者具有参考价值。

本文只对区域级的充电站规划进行了验证，但所提方法同样适用于城市级电动出租车的充电站规划建设。另外，由于地理位置、土地利用和经济发展水平的影响，不同地点的地价也会存在差异，造成不同地点的充电站建设成本也有所不同；由于缺乏土地利用信息，在规划模型中没有考虑到每个候选站点排队空间的限制。在后续研究中将针对上述2 点问题进行进一步改进。

附录见本刊网络版（http：//www.epae.cn）。