带时间窗的电动汽车物流配送车辆路径问题研究

黄敏芳，刘敬，郭琼

（1.华北电力大学 经济与管理学院，北京 102206；2.新能源电力与低碳发展研究北京市重点实验室（华北电力大学），北京 102206）

1 引言

电子商务环境下城区物流配送呈现小批量、多品种、多频次、短周期和送货时间严格等特点。近年来，网上零售企业，如苏宁易购、当当、亚马逊等，其网上交易订单量日益增长，由此引发更加频繁的交通运输活动。据两会报道显示，我国快递量去年一年达到400亿件，占世界超40%的市场份额。国际能源署（IEA）2009年发布的《运输、能源与二氧化碳：迈向可持续发展》[1]的报告显示，全球25%的二氧化碳等温室气体的排放来源于交通运输。如何通过发展“绿色物流”来减少电子商务物流配送对环境的污染，做好物流配送中的“最后一公里”服务，是当前物流业面临的主要难题。北京市《关于对部分机动车采取交通管理措施降低污染物排放的通告》[2]提出对城区内送货车辆环保问题的监控势在必行。电动汽车逐渐成为电子商务环境下频繁的城区物流配送活动的最佳选择。2014年物流与运输车辆高峰论坛[3]首次提出可将电动三轮车用于解决电子商务城区物流配送活动。据国家电网报显示，至2017年10月底，全国充电网络已覆盖26个省、273个城市，充电桩数量达到4.5万个。

车辆路径问题（vehicle routing problem，VRP）是物流运作管理面临的难点问题，该问题可定义为：对一系列发货点/收货点，安排适当的行车路线，使车辆有序通过，在满足一定约束条件（如货物需求量、发货量、交货时间、车容量限制、行驶里程限制等）下，达到一定的目标，如路程最短、费用最小、时间尽量少、使用车辆尽量少等[4]。目前对于VRP的研究方向多集中在单车场[5]、多车场[6]、单车型[5-6]、多车型[7]、带时间窗约束[8-9]、随机需求[10-12]等，研究方法可归结为精确算法[8]、传统启发式算法[5]以及现代启发式算法[6-7,9-11]。如今，随着国家大力倡导节能减排，电动物流车已广泛应用到我国的各大城市，电动汽车在物流中的应用已成为该行业相关学者的研究热点。目前，国内外已有诸多学者将电动汽车应用到物流配送问题上，并展开研究，如：M Schneider等[13]研究了带时间窗和充电站的车辆路径问题，以最小化车辆数和总行驶距离为目标，采用变邻域搜索算法和禁忌搜索算法进行求解，并设计两种算例分别用CPLEX和禁忌搜索算法得出结果。Siddiqi等[14]研究了粒子群算法求解电动汽车在多种约束下的路径优化问题。Baouche[15]建立定位的节能路径优化模型使能源消耗最低。Kobayashi等[16]研究不需要充电、充电一次和充电多次三种情况下电动汽车的路径搜索，将路径分为多条子路径后采用Dijkstra算法精确求解。Wang和Song[17]研究了带时间窗的电动汽车的定位和路径优化问题，通过禁忌搜索算法和大规模邻域搜索算法相结合求解。Keskin和Gatay[18]研究了带时间窗的电动汽车不完全充电情况下的车辆路径问题，采用自适应大规模邻域搜索算法求解。以上文献均为本文研究的展开提供了借鉴。

本文研究的是带软时间窗的电动汽车物流配送车辆路径问题，除了传统VRP带来的求解难度以外，电动汽车的应用会涉及到行驶过程中的充电问题，大大提升了问题的复杂度。目前，在电动汽车车辆路径问题的相关研究上，关于具体的成本核算部分，多数文献采用不计充电成本或按充电次数计费的方式，这种粗略核算的方式会降低结果的精确度。本文选择的是由充电度数决定的充电成本，提高了充电成本核算的精确性，解决了由粗略计算充电成本导致的车辆路线与实际情况偏差较大的缺陷，增强了电动汽车在物流配送问题上的应用灵活性。由于遗传算法具有可并行搜索、编码方式多样等优良特点，可用于解决较复杂的组合优化问题，因此本文采用遗传算法进行求解，并结合问题实际特征改进算法。

2 问题描述及模型构建

2.1 问题描述

本文研究的是配送中心在收到客户货物后，用电动物流车给客户配送。由于电动汽车具有一定的续驶里程限制，在电量耗尽之前需要及时进行能源补给，目前能源补给的方式主要有三种：常规充电、快速充电和更换电池。在电子商务环境下“最后一公里”配送过程中，因客户对时间窗有较严格的限制，所以只能通过快充或更换电池进行能源补给。而更换电池的专业化要求较高，换电车辆需要专业的维修保养，所以本文考虑的是较为便捷的充电模式。一般情况下，在同城区中会配置有多个充电站，为电动汽车的正常行驶提供便利。

本文构建模型的目标是使整个配送过程中总物流成本最小。为简化研究，做出如下假设：

（1）每个客户点只能由一辆车配送，一辆车可以服务多个客户点，电动汽车在配送期间最多可充电一次。不考虑配送车辆的巡回使用；

（2）配送中心数量为单个；

（3）所有车辆从配送中心出发时均为满电状态；

（4）不考虑充电站车辆排队等候，即车辆进入充电站就可直接充电，并且车辆在充电站均是充满电再驶离；

（5）车辆在客户点停留过程中不消耗电能。

为更清楚的描述问题，本文给出如图1所示的车辆线路示例。图1中有1个配送中心（0），2个充电站（B1，B2），8个客户点（1，2，…，8），图1（a）为各个点的位置分布情况，图1（b）为经过计算机求解后的最终行驶路线结果，即为配送中心→1→6→3→B1→7→8→配送中心（路线1），配送中心→2→4→5→配送中心（路线2）。

图1 车辆路线图

2.2 符号定义

本文使用的各参数定义如下：

N=Na⋃Nc⋃B，表示配送中心、客户和充电站的集合，其中，Na表示配送中心的集合，这里为单一配送中心，用o表示，Nc表示客户点的集合，B表示充电站的集合，A={(i,j)|i,j∈N,i≠j}表示路段的集合，客户i的时间窗为(ei,li)，i∈Nc，配送车辆的集合为K，配送车辆用符号k表示，k∈K，单位车辆的启动成本为f（元/辆），电动汽车单位距离的运输成本为y（元/km），单位距离消耗的电量为e（kW·h/km），单位充电成本为c（元/kW·h），其它符号定义如下：

Z：配送总成本；

qi：客户点i的需求量；

Qk：配送车辆k的车载容量，k∈K；

Qik：配送车辆k离开i点时最多可剩余货物量，k∈K，i∈N；

dij：i点到j点的距离（单位：km），i,j∈N；

V：配送车辆匀速行驶速度；

U：配送车辆的最大电池容量；

：车辆k到达i点时的剩余电量；

：车辆k离开i点时的剩余电量；

r：充电率；

Ti：配送车辆到达客户点i的时间；

：配送车辆离开客户点i的时间；

Wi：配送车辆在i点的等待时间；

Si：配送车辆在客户点i的服务时间。

决策变量为：

物流配送电动汽车车辆路径问题需考虑客户订单的时间窗。时间窗分为硬时间窗、软时间窗和混合时间窗。硬时间窗要求车辆必须要在时间窗内到达，早到必须等待，而迟到则拒收。软时间窗是客户对时间窗要求具有较大的弹性，允许配送员（车辆）提前或延后到达客户，在实际生活中更实用、更灵活。软时间窗需要考虑准时到达、提前到达与延迟到达等不同情形下的惩罚成本，因此带软时间窗的求解难度更大。混合时间窗表示若配送员（车辆）在期望时间窗内到达，则客户满意度为100%，若在期望时间窗外，但在允许时间窗内到达，则客户满意度会随着时间差的增大而降低。本文对带软时间窗的物流配送电动汽车充电站定位与车辆路径问题进行剖析，用EPU表示车辆提前到达产生的单位时间机会成本，LPU表示车辆延迟到达产生的单位时间惩罚成本，则客户i的惩罚成本Pi(Ti)可表示为：

2.3 模型构建

基于上述参数定义、决策变量、假设条件和惩罚成本函数，构建了带软时间窗的电动汽车车辆路径问题的非线性规划模型。

模型中式（1）为目标函数，表示配送总成本最小，包括启动车辆成本、运输成本、充电成本以及表示客户满意度的惩罚成本；式（2）表示每个客户点到达和离开的车辆数相等，即流量平衡；式（3）表示配送车辆的起点和终点都是配送中心；式（4）表示车辆装载容量和客户需求量之间的关系，若配送车辆从客户i到客户j进行配送，则车辆离开j点的最多可剩余货物量至多为车辆离开i时的最多可剩余货物量减去j点的需求量，否则该约束松弛；式（5）表示车辆k从配送中心出发时满载；式（6）表示每辆电动汽车服务客户的需求量之和不超过车载容量；式（7）表示配送车辆离开i点时的时间；式（8）表示配送车辆离开i点到达j点的时间；式（9）表示电动汽车若提前到达，则需等待，等待时间为ei-Ti，否则，无需等待，等待时间为0；公式（10）表示配送车辆离开j点时的时间；式（11）和式（12）分别表示配送车辆离开配送中心与充电站时电量均充满；式（13）表示配送车辆在客户点服务期间不消耗电能；式（14）表示电量与行驶里程的关系；式（15）确保电动汽车有足够的电量到达路线上的每一个点；式（16）保证每次配送任务都以配送中心为起点和终点。

3 算法设计

3.1 算法原理

算法求解原理如图2所示。

图2 算法流程图

3.2 算法步骤

算法设计中的核心内容如下：

（1）编码设计。遗传算法的编码方式有二进制编码、格雷码编码以及自然数编码。本文采用应用较为普遍的自然数编码。染色体长度为m+ch+k+2，其中m表示客户点数量，ch表示充电站数量，k表示所需车辆数，数字2代表车辆出发和返回均在配送中心。配送中心编码为0，客户点序列为1，2，…，m，充电站序列用m+1，m+2，…，m+ch表示。如用3辆车为8个客户服务，充电站个数为2，则其某一染色体可以是0，6，5，7，0，8，9，1，0，2，3，10，4，0，表示路线一为车辆1从配送中心出发，依次为客户6，5，7服务后返回配送中心，路线二为车辆2从配送中心出发，在为客户8服务后去充电站9充电，再为客户1服务后返回配送中心，路线三为车辆3从配送中心出发，先为客户2，客户3服务后去充电站10充电，再去服务客户4，最后返回配送中心。

（2）约束处理与适应度函数。对于电动汽车的行驶里程以及载重限制，若直接对染色体操作，则会导致染色体长度不同，进而无法进行之后的交叉、变异等操作，故本文采用惩罚函数的形式对行驶里程和载重进行约束。为寻求最经济的配送方案，本文以物流成本作为优化目标，对于其中的充电成本，目前有按充电次数计费以及不计充电成本两种方式，不计充电成本适用于有自建充电站的物流企业，但对于没有自建充电站的企业来说，按充电次数来计算充电成本是不够准确的，为增加成本核算的精确度，这里选择根据充电度数计算充电成本，引入矩阵Dis来记录所有路线方案中车辆到达某一点i（i∈N）的已行驶路程，一旦判断车辆到达充电站j（j∈B），即可通过矩阵Dis获取该充电站对应的已行驶里程数，记为dj。由假设条件电动车在充电站充满电再驶离，可通过公式dj*e*c计算得出在充电站j花费的充电成本（若c的单位为元/h，则是根据充电时长计算的，这里是根据充电度数）。这种方式增加了电动汽车配送成本核算的灵活性。最后制定出的目标函数如下：

其中，d1(i)代表某条染色体的总运输距离（这里的i是染色体的序号），e2(i)（这里的i是染色体的序号）代表所有车辆在所有充电站前电动汽车行驶的总距离，ddd(i)和qqq(i)设计时均为0或1，满足里程条件或载重条件的为0，否则为1，M是很大的正数，使得不满足约束条件的染色体的目标值很大。由于动态线性标定法可以扩大适应度函数寻优能力[11]，故本文采用此方法进行计算，具体适应度函数如下：

（3）选择。采用轮盘赌的方式，计算初始染色体的适应度。生成一个随机数，根据选择概率判断是否进行选择操作，若满足条件，则选择适应度大的两条染色体作为父代染色体，否则，不进行选择操作。

（4）交叉。为获得较好性能的染色体，提高算法的寻优能力，本文采用交换某段子路径的交叉方式，具体操作如下：

Step1：分别在两个父代染色体上随机选择一段子路径（如子路径A和子路径B）。

父代染色体1：

父代染色体2：

Step2：被选择的子路径前置。将父代染色体1中的子路径A前置，同时，将该染色体中除子路径A外的编码按父代染色体2中的顺序排列，在末尾填0，最后再将剩余的0插入到除子路径外的染色体段中，得到子代染色体1。同理得到子代染色体2。

父代染色体1：

父代染色体2：

（5）变异。选择2-交换变异算子进行染色体变异，即在父代染色体上随机选择2个位置进行交换，再将变异后的染色体重插入子代中去。

4 算例分析

选取一个中等规模算例来验证本文提出模型和求解算法的有效性，算例中共包含42个点，包括1个配送中心，35个客户，6个充电站。各个点的位置坐标、客户需求量、时间窗和客户点停留时间均给定（也可由计算机在一定范围内随机生成）。电动汽车的续航里程为200km，其他参数数值设置见表1。

表1 初始参数值

采用MATLAB语言编写程序，在处理器为Intel(R)Core(TM)i5-3230M，内存为4G的笔记本上运行，交叉和变异概率分别为0.9和0.05，迭代500次，重复求解10次，取最小的运行结果做为最优路线，得到的最小配送成本为3 525.63元。

表2 车辆路线表

图3 车辆路线图

表3 配送成本与车辆数数据表

改变配送车辆数，重新求解，结果见表3，发现随着车辆数的增加，配送成本总体呈上升趋势，这是由于车辆的启动成本在总成本中所占比重大于充电成本、行驶成本和惩罚成本的比重，使得增加车辆的代价较大。然而也出现了增加车辆数成本反而降低的现象，原因是虽然车辆数量的增多增加了启动成本，但其通过提高配送效率所降低的惩罚成本已大于增加的车辆启动成本了。

5 结语

从网上零售商的配送中心角度出发，提出了带软时间窗及充电站定位的电动汽车车辆路径问题，从配送中心角度分析了车辆使用数量与使用成本对总物流配送成本的影响。借助计算机实现了基于遗传算法的求解方法，获得最优配送路线。提出的根据充电度数来计算充电成本的方式，增强了成本核算的精确性，克服了已有研究中不计充电成本或粗算充电成本的不足。此外，在采用遗传算法求解问题时，采用改进交叉算子，使得优秀的子路径能够最大程度上被保留，该方法比采用顺序交叉、循环交叉、位置交叉更适用于多车辆配送的车辆路径问题。

物流配送活动中会产生不确定性情况，如路况、车况等，可结合该类情况提出更实用的问题求解方法；电动汽车到达充电站往往会产生等待时间，可通过对车辆的排队分布进行模拟，获得合理的等待时间，在问题求解中将该时间因素考虑进去。