葛显龙，李祖伟，葛小波

(1.重庆交通大学经济与管理学院，重庆 400074;2.智能物流网络重庆市重点实验室，重庆 400074)

1 引言

电动汽车具有能源清洁、无污染等显著特点，一经问世就被广泛的应用于各个领域，如公共交通、公路运输以及物流配送等等.特别是在城市物流配送“最后一公里”的应用中，发挥着重要的作用.尽管电动汽车具有灵活机动、节能环保等众多优点，但是其受到行驶距离有限、充电时间较长以及配套的充/换电设施不健全等实际问题的制约，因此，在很大程度上限制了电动汽车在各个领域的推广与应用.此外，由于上述这些问题很难在较短时间内得到有效的解决，故只能通过采取一些优化策略或者措施，对整个电动汽车的物流配送方案进行一系列的优化，进而达到提高电动汽车利用效率和降低物流配送成本的目的.

电动汽车作为一种节能、环保的新型配送工具，其在当今的城市物流配送中应用非常广泛，为了能减少电动汽车充电时间较长、行驶距离有限以及配套设施不完善等问题带来的消极影响，国内外很多学者都对电动汽车的物流配送优化问题进行了深入的研究，其大致可以分为以下几个方面:一是电动汽车的路径优化问题.Sevgi和Elise[1]研究了以电动汽车为配送车辆的绿色车辆路径问题，文中考虑了电动汽车与传统燃油汽车的区别.Bruglieri等[2]研究了带有时间窗的电动汽车路径问题，并对该问题建立了相应的混合整数线性规划模型.Schneider和Stenger等[3]在考虑一些常规VRP约束下，增加了车载电池容量约束，建立了电动汽车的车辆路径优化模型，并使用电动汽车数量最小和路径最短为目标，寻求最优的行驶路径.揭婉晨等[4]研究带时间窗的电动汽车车辆路径问题，建立了相应的混合整数规划模型，指出了通过改进分支定价算法以求得其最优解.二是电动汽车的充/换电站的选址问题.Lim和Kuby[5]基于加油站、ATM机等服务设施的选址问题模型，提出了替代能源汽车的能源补充设施选址模型.冯智泉等[6]在基本路网结构中增加了对充电站分布的考虑，应用蚁群算法分别对分段路线和全局充电方案进行优化，最终将两部分结合形成全局的最优行驶路径.Schiffer和Walther[7]研究充电站选址与路径优化同时进行决策的电动汽车物流配送换电站选址与路径优化问题，优化目标为最小化旅行成本、换电站选址成本以及充电成本.三是电动汽车的智能充电策略等.Liu等[8]引入了实时定价(real time pricing，RTP)策略，并根据RTP策略对电动汽车的导航系统进行优化.Amoroso和Cappuccino[9]通过考虑充电效率和充电速率之间可能的现实关系，比较了两个基于智能可变速率的充电策略的性能.杨松平[10]构建了固定电价下的单辆电动汽车和考虑分时充电成本的多辆电动汽车行驶路径优化模型，构建学习型单亲遗传算法对模型进行求解.张剑等[11]从配电网调度的层面提出了以配电网供电能量最小、运行费用最小或利润最大为目标的充电网优化模型，基于迭代修正节点电压的方法分别对其求解，具有一定的实用价值.根据上述分析，国内外学者大多都将研究重点放在电动汽车的车辆路径优化以及充/换电的选址，而针对电动汽车的智能充电策略和时间窗的研究相对较为薄弱[12].智能充电策略作为一种优化的手段，能够提高配送车辆的充电效率以及电池电能的利用率，可以降低电动汽车的配送成本.以往很多学者在对电动汽车进行路径优化或者选址优化时，大多都是将电动汽车的充电行为进行简化处理，如采取换电池操作或者假设车辆离开充电站时为满电量状态等等，这些处理方式或者假设不但不符合实际的配送情况，而且严重降低了整个优化结果的适用性.因此，本文以电动汽车的物流配送为研究对象，对电动汽车的充电过程进行分析，提出了考虑部分充电策略的带时间窗电动汽车物流配送优化问题，并建立了以车辆的固定成本、行驶成本以及充电成本为优化目标的电动汽车物流配送优化，文中还根据所研究问题的特点和构建问题模型的特点，设计了一种改进的混合模拟退火―遗传算法对其进行求解.最后，通过数值分析对所建立的模型和算法进行验证.

2 问题描述

针对一组分布在一定空间区域内需求已知的客户点，且每个服务客户点都具有一定的时间窗限制，某配送企业采用电动车辆对其进行配送服务，但是由于配送车辆受到车载电池容量的限制，导致其续驶里程非常有限，因此，在对客户进行配送的过程中，车辆需要绕道访问邻近充电站点进行电量的补充，才能在满足车辆载重约束的条件下继续访问剩余的客户点.而在以往的电动汽车物流配送优化研究中，人们为了便于研究，往往假设配送车辆在访问充电站后都是以满电状态驶离，这种假设不但不符合实际的配送情况，而且还不利于电能的有效利用，即配送车辆在完成剩余的配送任务时，留有部分多余的电量而未被有效的利用.为了克服上述这些缺陷，提高车载电池能量的利用效率以及最大限度的保证服务客户点对时间的要求，这里采用了一种部分充电策略，即配送车辆在前往充电站进行电量补充时，可以根据车辆本身剩余电量的多少以及剩余服务客户的情况，确定需要补充的电池能量.具体的配送情况，如图1所示.

图1 部分充电策略示意图Fig.1 An illustration of partial charging strategy

3 数学模型

3.1 提出假设

由于考虑部分充电策略的电动汽车物流配送问题较为复杂，因此，在模型构建之前，需要做出如下假设:

1) 每个客户的需求量都不超过车辆的最大装载容量，且客户的需求不可分拆;

2) 配送车辆的各种参数都相同，即车型相同、电池容量以及装载容量都相同;

3) 配送车辆从配送中心驶出时，电池容量都为最大值;

4) 配送车辆的电量消耗与距离成正比;

5) 配送车辆的充电时长与充电量是线性的关系;

6) 每个充电站点能被访问一次或多次;

7) 配送车辆在完成配送任务时都要返回配送中心;

8) 整个配送的过程中，不考虑其他特殊因素的影响，例如车辆故障、交通拥堵等等.

9) 车辆在进行配送服务的过程中速度是恒定且不变的;

10) 假设车辆驶离配送中心的时间为0时刻.

3.2 符号和变量的定义

为便于理解，现将本文中用到的常量和变量汇总如表1.

表1 全文符号说明Table 1 Notation used in this paper

决策变量定义为

3.3 建立数学模型

根据对问题描述的分析以及电动汽车在实际物流配送过程中的应用，以车辆固定成本、行驶距离成本、充电成本以及时间窗惩罚成本为最小化的优化目标函数，建立了考虑部分充电策略的带时间窗电动汽车物流配送优化问题模型.

其中:目标函数(1)表示电动汽车的固定成本、车辆的行驶成本以及充电成本3项成本的最小值.约束(2)表示每个客户被服务且仅被服务一次.约束(3)表示每辆车只安排一条配送路线.约束(4)保证了流量的平衡，即每辆车进入某个节点的次数和离开该节点的次数相等.约束(5)表示车辆的装载容量与所服务需求点之间的关系，如车辆在节点j处剩余的载货量为车辆到达节点i时的装载量减去节点j处的需求量.约束(6)说明车辆k从配送中心O点出发时最大装载容量为C.约束(7)-(8)表示车辆离开配送中心或者到达节点时，车辆在各个节点的电量关系，如约束(8)所示:车辆到达节点j时所剩余的电量等于车辆离开i时所剩余的电量减去其从节点到i节点j所消耗的能量.约束(9)表示车辆到达任意节点时所剩余的电量不能为负.约束(10)说明电动汽车在换电站处补充的电量要小于电池的最大容量.约束(11)表示车辆在访问客户节点的前后，电量保持不变.约束(12)表示如车辆提前到达服务客户点时，则等待时间twi为反之则等待时间twi为0;约束(13)表示车辆离开i节点的时刻等于车辆达到i点的时间加上其在该点的服务时间与等待时间;约束(14)车辆从节点i行驶到节点j所需要的时间;约束(15)表示车辆到达节点j的时间等于其离开上一个节点i的时间加上其从节点i行驶到节点j所需要的时间;约束(16)-(17)是二进制0-1变量.

4 混合模拟退火算法设计

电动车辆路径问题(electric vehicle routing problem，EVRP)作为传统车辆路径问题的一种变种，也是属于典型的NP-hard问题，因此，很难通过精确算法获取其精确解，特别是对于一些规模较大的基准实例.而通过对当前此类文献的整理和研究发现，国内外众多的学者都普遍采用启发式智能算法对该问题进行求解，该种方法不但对求解大规模的基准实例有着显著的优势，而且其求解质量和运行效率都非常的高.而带时间窗约束的电动车辆路径问题(electric vehicle routing problem with time windows，EVRPTW)问题相比较于一般的EVRP问题，其约束条件更多、求解环境更复杂，同时对算法求解的质量和时效性要求更严苛，故本文采用了并行寻优能力较强的模拟退火-遗传混合算法对其进行求解.改进的混合模拟退火算法作为一种智能混合算法，其不但具有模拟退火算法优越的局部寻优能力，而且还兼顾遗传算法并行的全局寻优能力，此外，为了避免算法过早的陷入局部最优解，这里采用了一种双向随机搜索策略，即当算法在经过邻域搜索和遗传操作后，获得的当前解较初始解有所提高时，将接受当前解以替换之前的初始解;反之，将以一定的概率接受相比较于初始解略差的解为当前解，其中Δc为算法经过邻域和遗传操作前后两个解之间的差值，T是降温过程的控制参数，即温度[14-15].

4.1 编码设计

常见的智能算法编码方式有很多，常用的有0-1编码、自然数编码以及浮点数编码等等，而各种编码形式所适用的范围和性能也各不相同.本文根据所研究问题的特殊性，采用染色体编码形式较为简洁的自然数编码，即每条染色体都是由代表配送中心、客户点以及充电站点的自然数构成，此种编码形式具有操作便捷、表达简洁、可扩充性强等显著优点.在某个配送网络中，配送中心可以编码为0;客户点编码为1，2，3，4，…，m;充电站点编码为m+1，m+2，…，m+ch.若使用2辆车对含有9个客户点和2个充电站点进行配送活动的一条完整染色体编码为:0-2-3-10-5-8-0-1-4-6-11-7-9-0，其中0-2-3-10-5-8-0代表第一辆车的配送路径，即车辆从配送中心出发，先后经过客户点2和客户点3，然后进入编号为10的充电站进行充电，充满电后经客户点5和客户点8返回配送中心.

4.2 种群初始化

初始种群的设置对整个混合算法最终的求解效果有着很重要的影响，质量较好的初始解有助于算法在较短的时间内获得质量更高的解，因此，本文在确定染色体编码形式之后，通过引入了扫描算子来生成质量较优的初始种群.具体操作流程如下:

步骤1获取配送中心0、配送客户点1，2，3，4，…，m的位置信息;

步骤2以配送中心0为原点建立极坐标系，使得需要配送的客户点全部位于极坐标系中，然后通过下式

分别求出各客户节点与极坐标系X轴之间的夹角为θi，则其全部夹角所构成的集合为G={θ1，θ2，…，θm};

步骤3将集合G中的元素，按升序或降序的规则进行排序，生成的一条包含所有配送客户点的初始染色体;

步骤4通过unidrnd(N)函数随机获取一个自然数，然后根据自然数在初始染色体中所对应的位置进行截取，将截取后的染色体片段位置调换，生产一条新的染色体;

步骤5根据车辆载重和电池容量约束以及充电站点的插入等方式，对步骤4中获取的染色体进行车辆分配，生成一条符合配送需求的染色体;

步骤6重复操作步骤4-5生成初始种群.

4.3 适应度函数

适应度函数是遗传算法进行迭代寻优的判断依据，染色体的适应度值越大，则表示该染色体所对应解的质量越高，被选择保留下来的概率也就越高，反之亦然，因此，适应度函数设计的优劣直接关系到最终的求解效果.本文根据参考文献以及电动车辆路径优化问题的特点，以优化目标的倒数为适应度函数，即其中Z为所建立模型的优化目标函数值，即车辆固定成本、行驶距离成本、充电成本以及时间窗惩罚成本4者之和的最小化.

4.4 邻域操作

邻域解的构造这里采用在初始解的基础上，通过rr=randi(4)和switch(rr)函数来随机选择不同的邻域算子，本算法中采用的邻域算子共有4种:逆序邻域搜索算子:将编码片段中被选择的两个位置中间的编码信息进行位置的逆序;1-opt交换搜索算子:通过一定的方式在编码片段中选择两个特定编码位置，并将位置靠前的基因编码信息插入到位置靠后的基因编码信息之前;2-opt交换搜索算子:将编码片段中被选择的两个位置中编码信息进行位置的调换;和3-opt交换搜索算子:通过一定的方式在编码片段中选择3个特定编码位置，并将该位置的基因编码信息从前往后依次调换他们的顺序.

4.5 遗传操作

1) 选择操作:父代染色体选择的优劣直接关系到后续子代染色体的质量，为了能获得质量较好的子代染色体，通常要选择质量较为优秀的父代染色体.而判断父代染色体质量优劣的依据是其所对应适应度值的大小，父代染色体的适应度值越大，则其质量就越优，被保存下来的概率也就越大.因此，文中根据初始种群各个父代染色体适应度值的大小，采用保留最优个体和轮盘赌策略进行父代染色体的选择，通常适应度值越大的个体，所对应的选择概率也就越大，被选中的机会也越高.

2) 交叉操作:电动汽车的物流配送染色体编码过程中，由于存在着充电站点的插入，因此，在一条完整的染色体编码机构中，也存在着充电站点的基因编码，而在进行交叉操作时，如果对充电站点进行交叉，可能会破坏原本优良的子串，而造成很多的劣解，故在进行交叉操作时，优先剔除父代中插入的充电站点基因编码，然后再进行交叉操作.交叉操作采用的是局部映射的交叉策略，对随机选择的优良父代染色体进行两两交叉操作.具体操作步骤如下:

步骤1随机选择父代染色体F1和F2，然后在[1，N]中随机生成两个自然数L1和L1，分别交叉父代染色体中定位出r1和r2所对应的位置;

步骤2分别找出父代染色体F1和F2中需要进行交叉操作的优良基因片段T1和T2，即L1和L2之间包含的基因片段，并将选中的优良基因片段T1和T2的位置进行互换;

步骤3分别删除父代染色体中与优良基因片段T1和T2相同的基因编码，保留不同的基因编码;

步骤4根据优良基因片段T1和T2的对应关系，消除冲突补全基因编码信息;

步骤5重复步骤1到步骤4，完成对所有被选择父代染色体的交叉操作.具体过程如图2所示.

图2 交叉操作Fig.2 Crossover operator

3) 变异操作:变异操作的基因编码形式与交叉操作一样，为了避免破坏优良基因片段和产生大量的劣解，变异前将含有充电站点的基因编码信息删除.首先确定通过变异概率确定进行变异操作的父代染色体F，然后在[1，N]之间随机产生两个自然数x1和x2，最后，定位父代染色体中x1和x2所对应的位置，并将该位置的基因编码信息进行调换.具体过程如图3所示.

4) 逆转操作:为了提高算法的局部搜索能力，改善提高解的质量，在选择、交叉和变异之后，还进行了一项进化逆转操作，并且只接受那些经过逆转操作后适应度值有所提高的个体，否则逆转操作无效.首先确定逆转操作的父代染色体F，然后在[1，N]之间随机产生两个自然数r1和r2，最后，定位父代染色体中r1和r2所对应的位置，并将该位置的基因编码信息顺序进行逆转.具体过程如图4所示.

图3 变异操作Fig.3 Mutation operator

图4 逆转操作Fig.4 Inversion operator

4.6 温度控制

本算法的初始温度为T0，算法的终止温度为考虑到模拟退火-遗传混合算法是双层循环结构，因此，在每个固定外层循环的温度下，内循环的次数为Stop N，解无改善的最大循环次数为Stop M.退火的降温函数为TK+1=βTk，其中β温度降低系数，一般可以在[0.8，1.0)区间内随机选择.

4.7 终止条件

终止条件的设置主要分为两种，一种是内循环的终止条件.当固定温度下迭代计数器Search的值大于或者等于内循环的次数Stop N时，在当前固定温度下内循环终止，或者解无改善的计数器Stop达到Stop M，在当前固定温度下内循环终止;另一种是外部循环的终止条件.当外部循环的温度降低到指定的终止温度Tf时，直接跳出外循环操作终止算法.

5 数值分析

5.1 算例介绍

为了验证本文所建模型和算法的有效性，文中算例的数据来源于文献[13].主要包含的内容如下:以纯电动汽车为配送工具，对均匀分布在一定区域内的25个需求量、时间窗已知的客户点提供配送服务，且每个客户点只能被一辆车服务，此外，在客户点所分布的区域内存在2座可供车辆补充电量的充电站.假设每辆车的最大载货量为5 t;车载电池的最大容量为160 AH;每辆电动汽车的最大行驶距离Dis=160 km，而配送车辆的电能消耗与行驶距离成正比，消耗速率为1 ah/km;配送车辆的行驶速度speed为40 km/h.配送车辆的单位固定使用成本为1000元/每辆;车辆的单位行驶成本为10元/km;电池的单位充电速率为时间窗惩罚成本系数epu为10元/h;lup为20元/h.详细信息如表2所示:其中0代表配送中心;1，2，3，…，25表示的是客户点，26，27表示充电站.

本算例的坐标系统(X，Y)采用平面直角坐标系，坐标的单位是公里(km);每个服务点需求量Pi的单位是吨(t);最早服务时间ei，最晚服务时间li是基于仓库0为起始时间的偏移量，单位小时(h)，“100”代表不限制;服务时间tfi的单位是小时(h).

表2 节点的详细信息Table 2 Node details

图5显示的是算例中配送中心、各客户点和充电站的位置分布情况，其中“■”表示配送中心的位置，“▼”表示充电站点的位置，“*”表示客户点的位置.

图5 节点的位置分布Fig.5 Node inputs of locations

5.2 算例结果及分析

为了能更好的验证本文所提出的考虑部分充电策略的有效性和适用性，针对文献[13]中电动汽车物流配送的算例，这里对两种充电策略进行测试，一种是文本所提出的部分充电策略，即配送车辆可以根据自己的配送情况，在充电站部分补充一部分的电量，也就是说车辆驶离充电站时，电池可以不是满电量状态;另一种是满充电策略，即配送车辆在访问充电站后，车辆是以满电状态驶离充电站点，文献[13]所采用的就是这种充电方式.算例测试是以MATLAB编程软件为基础工具，通过设计和编制改进的混合模拟退火遗传算法对该问题进行求解.相应的参数设置如下:初始温度为100，内循环的次数Stop N为20，最优解没有得到改善的最大次数为Stop M为10，初始种群为200，交叉概率为0.95，变异概率为0.05，遗传代沟为0.9.在MATLAB上的运行结果如图6-7所示.

图6 考虑部分充电策略的配送路径Fig.6 Solution with partial charging strategy

图7 考虑满充电策略的配送路径Fig.7 Solution with full charging strategy

由于文献[13]中优化的目标函数只包含配送车辆行驶成本和时间窗惩罚成本，为了能与其进行较好的比较，文中在算法求解的过程中，现将模型中的优化目标函数值与文献[13]中的保持一致.考虑两种不同充电策略的物流配送优化结果详细信息如表3所示.

表3 两种不同充电策略的优化结果Table 3 Optimized results with two different charging strategies

通过表3中数据可以看出，由于受到服务客户点时间窗的约束，两种不同充电策略的物流配送优化线路非常的接近，所需要的车辆数和访问充电站的次数都相同.当采用部分充电策略时，车辆在每个充电站的充电率分别为32.25%，70.17%，相比较于满充电策略，车辆不但节省了一部分的充电时间，而且还能有效的防止车辆剩余电量的浪费.此外，根据总的行驶距离和总的成本费用两项数据指标，部分充电策略要优于满充电策略，总的行驶距离减少了14 km，总成本减少了124元.

5.3 敏感性分析

通过上述实例分析可知，采用部分充电策略可以显著的节省车辆的充电时间，缩短整个电动汽车物流配送的时间，而对于带时间窗的电动汽车物流配送优化问题，由于服务对象对配送时间要求较为严格，如果不能在客户规定的时间窗口内对其提供配送服务，除了会承担一部分的时间惩罚费用外，还会降低客户的满意度.因此，下面就文中所涉及的两种充电策略与车辆的充电时间进行敏感性分析.

假设上述算例分析中的其他信息保持不变，将车辆的充电等待时间tfi进行变动，分别将其设置为0.4，0.8，1.2，1.6，2，电池的单位充电速率为然后分别求出每个值所对应的时间惩罚成本以及总的成本费用.具体情况如表4所示.

表4 不同单位充电成本下的结果对比Table 4 Comparations of different charging costs per unit

通过表4中的数据可知，在两种充电模式下，线路1-2都绕道访问过充电站，因此，当充电等待时间tfi不断增大时，其所对应的时间窗惩罚成本也在不断增大，而线路3由于中途未进行充电活动，所以其时间窗惩罚成本也一直保持不变.此外，在tfi不断增大的过程中，尽管两种充电模式下的时间窗惩罚成本都呈逐渐增大的趋势，但是考虑部分充电策略配送方案的时间窗惩罚成本增大的趋势明显要小于满充电策略，这点可以从表中时间窗惩罚成本之差这一列中看出，且这种优势随着车辆充电等待时间的不断增大，其体现的越明显.

6 结论

以电动汽车物流配送为研究对象，对电动汽车的充电过程进行了仔细的研究，提出了考虑部分充电策略的带时间窗电动汽车物流配送优化问题，并根据研究问题的特性，建立了以车辆固定成本、车辆行驶成本、车辆的充电成本以及时间窗惩罚成本为目标的优化模型，并设计了改进的混合模拟退火-遗传算法对该问题进行求解.通过算例测试与分析可知，电动汽车在进行物流配送活动时，考虑部分充电策略相比于满充电策略而言，不但能节约配送车辆在充电站的充电时间，而且还能在一定程度上，提高车载电池电量的利用效率，使得整个电动汽车的配送成本有着显著的降低;此外，通过对车辆充电等待时间的敏感性可知，当求解带时间窗的电动汽车物流配送优化问题时，在车辆的充电等待时间不断增大的过程中，尽管在两种充电策略下，配送方案的时间窗惩罚成本都呈逐渐增大的趋势，但是考虑部分充电策略配送方案的时间窗惩罚成本增大的趋势明显要小于满充电策略，且这种优势随着车辆充电等待时间的不断增大，其体现的越明显.