毛慧婷，石建迈，周玉珍，陈 超

（国防科技大学 系统工程学院 信息系统工程重点实验室，湖南 长沙 410073）

1 引言

随着温室气体的大量排放以及全球气候变暖等环境问题日益严重，近年来关于如何降低交通运输领域碳排放的研究越来越多。根据欧盟的统计数据，大约20%—25%全球能源消耗和二氧化碳排放量源于交通运输系统，其中陆上交通占75%[1]。目前国内外各大商业公司已经意识到充电汽车在绿色物流领域具有明显优势，开始研究以充电汽车为主导的物流配送系统。

车辆路径问题（vehicle routing problem，VRP）是物流运作管理的经典问题，通过优化配送车辆的行驶路径来提高物流配送的效益，如路程最短、费用最小、时间尽量少、使用车辆尽量少等[2]。应用电动汽车替代传统汽车进行物流配送，在带来环境和成本等方面效益的同时，也为车辆路径规划问题带来了新的挑战，引起了国内外学者的广泛关注。相对于传统路径规划，电动汽车的路径规划问题增加了中途充电站的选择决策，使得解空间的组合更多，求解难度更高。

从当前充电站的主流服务方式来看，一般分为快速充电和更换电池两种模式。在快速充电模式下，一般假设电动汽车在充电站充满电池，其充电时间由到达充电站时的剩余电量决定[3-8]。Schneider等[3]研究了带时间窗口的电动汽车路径规划问题，以最小化车辆数和总行驶距离为目标，提出了一种变邻域搜索与禁忌搜索相结合的混合启发式算法。Hiermann等[5]研究了电动汽车与燃油汽车混合模式下的路径规划问题，并设计了分支定价与混合启发式算法。Montoya等[6]分析了非线性充电速率对电动汽车路径规划的影响，并设计了针对非线性充电情况的搜索算子。Guo等[7]提出应用遗传算法求解带时间窗口的电动汽车路径规划问题。国内学者黄敏芳等[8]提出了带软时间窗及充电站定位的电动汽车车辆路径问题，并设计改进了遗传算法进行求解。在快速充电模式下，电动汽车也可以选择部分充电，而不是一次充满，从而节约时间和费用[9-11]。Keskin等[9]研究了部分充电模式下的路径规划问题，实验结果显示，部分充电策略相比较于完全充电策略可以有效减少配送里程。Ding等[10]通过实验对比，证明了部分充电模式下电动汽车的充电时间、客户点的等待时间以及行驶时长都相对较短。Macrina等[11]研究了混合车队中电动汽车允许部分充电情况下的车辆路径规划问题，并应用大邻域搜索算法进行了求解。Verma[12]提出了快速充电与电池更换两种模式下的电动汽车路径规划，并限定电动汽车采用快速充电时必须充满。

从电动汽车物流系统的运行来看，完全或部分快速充电策略的充电成本较低，但是需要一定的充电时间，可能使得电动汽车由于客户时间窗口不满足而减少客户访问数量；直接更换电池的策略在时间上可以忽略不计，但一般成本较高。当前文献大多研究一种充电策略下的路径规划，很少考虑两种充电策略混合模式下的电动汽车路径优化。当电动汽车在充电站既可以选择快速部分充电，也可以选择更换电池时，电动汽车的充电策略更加灵活柔性，进而降低总体成本。但是这种混合柔性的充电策略使得电动汽车路径规划的建模和求解更加复杂。在传统电动汽车路径规划模型的基础上，本文研究了柔性充电策略下带时间窗的电动汽车路径规划问题，建立了问题的非线性混合整数规划模型。通过结合蚁群算法和局部搜索策略，设计了一种改进型蚁群算法，提高了问题的求解效率。通过三种不同客户分布模式下的路径优化实验，验证了算法的有效性，并分析了柔性充电方式对于降低配送总成本的效果。

2 数学模型构建

2.1 问题描述

本文研究的电动汽车路径规划问题中，每个客户点都有特定的服务时间窗口以及服务时长。配送车队均由同一类型的电动汽车组成，具有固定大小的车载容量以及最大的行驶里程。在行驶过程中，电量随着行驶距离成比例消耗。电动汽车电量不足时，可以访问充电站补充电量。所有充电站均可提供两种充电方式：（1）快速充电，可以根据电动汽车的实际需要进行部分充电或充满；（2）更换电池，直接为电动汽车更换上新的满电电池。考虑到电池替换所花的时间很短，这里我们假设电池更换的时间可忽略不计。

在本文的模型中,目标函数是最小化配送总成本，包括车辆固定成本、行驶成本、等待成本以及充电成本。建模中的其他设定如下：

（1）每个客户点只能由一辆车配送，一辆车可以服务多个客户点；

（2）配送中心数量为单个，所有车辆从配送中心出发并回到配送中心；

（3）所有车辆从配送中心出发时均为满电状态，并且不考虑配送车辆的重复使用；

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

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

2.2 符号定义

在建模过程中，V={1,...,N}表示客户点集合，F表示充电站集合，顶点0和N+1分别为出发点和结束点，两者重合，为配送中心的位置。设集合V'=V⋃F，为了区别不同实例中的仓库，以0或者N+1作 为 该 集 合 的 下 标 ，如⋃{0} 和⋃{N+1}。 A={(i,j)|i,j∈表示路段的集合。每一条路段都有相应的距离值dij以及行驶时间tij，车辆电池的电量消耗率为r。在充电站采用快速充电方式时，电动汽车的充电率为g。若选择更换电池，则每次电池替换的成本为cs。Di表示客户i的需求量，si为客户服务时长，客户点的服务时间窗口为[ei,li]。电动汽车的容量表示为C，电池容量为Q。模型中的连续决策变量包括：τi,ui和vi分别为车辆到达客户点i的服务开始时间，剩余货物容量和剩余电量水平，qi为电动汽车在充电站采用快充模式时的充电量，Yi为车辆离开充电站i时的电量水平，δi为在客户点i∈N处的等待时间。如果路径中含有路段(i,j)，0-1决策变量xij的值取1，否则取0；如果在充电站i∈F选择了电池交换技术0-1决策变量yi的值取1，否则取0；如果在充电站i∈F选择了传统充电方式0-1决策变量zi的值取1，否则取0。

模型中所用到的符号总结如下，见表1。

2.3 数学模型

混合柔性充电策略支持下的电动汽车配送路径优化数学模型如下：

表1 模型中的符号表示

模型中公式（1）为目标函数，最小化总体成本。约束（2）和（3）确保每个客户点都恰好被一辆车访问一次。约束（4）为网络流平衡条件。约束（5）和（6）确保了路径中客户点之间时间窗的连续可行性。约束（7）保证车辆服务开始的时间在时间窗内。约束（5）-（7）同时消除了路径中的子回路。约束（8）和（9）确保满足所有客户点的需求量。约束（10）和（11）限定电池的电量始终非负。约束（12）计算车辆离开充电站时的电量水平。约束（13）限制车辆在充电站至多只能选择一种充电方式。约束（14）确保车辆充完电后的电量不超过最大电池容量。约束（15）-（17）限定所有决策变量的取值范围。

3 求解算法设计

为了解决混合充电模式下的电动汽车路径优化问题，本文设计了一种改进的蚁群算法。蚁群算法是一种源于生物界的新仿生类随机型搜索算法，由意大利学者Dorigo等提出，具有群体合作、正反馈选择、并行计算等特点。作为一种有效的启发式算法，近年来蚁群算法逐渐被用于求解各种车辆路径规划问题[13-17]。

为适应本文中的电动汽车路径优化求解，对蚁群算法进行了两方面的改进。首先考虑到充电站的选择和充电策略的优化，设计了一个最优充电站插入启发式；其次鉴于问题的复杂性，引入局部搜索算法，扩大蚁群算法迭代过程中的搜索空间，增加最优解的搜索概率。改进蚁群算法的主要步骤见算法1。

算法1:改进蚁群算法

Step1 参数初始化；

Step2 邻近点搜索构造初始可行解ψ0；

Step3 设定初始信息素浓度；

Step4 让k只蚂蚁同时从配送中心出发，并行搜索产生k个未插入充电站的解φ；

Step5 调用充电站插入算法，插入充电站；

Step6 调用局部搜索算法，进行局部搜索；

Step7 信息素更新；

Step8 若算法循环到最大次数NCmax后停止，输出最优可行解Ψbest；否则，转到Step4。

3.1 蚁群初始解构造

蚁群是正反馈系统，在觅食过程中，每只蚂蚁会在所经过的路径上留下一种化学物质—信息素，后面的蚂蚁可分辨其强度，从而选择信息素浓度高的路径。随着信息素的挥发，采用正反馈机制，蚂蚁将会选择相对较短且信息素浓度较高的路径。随着路径上的信息素不断进行更新和累积，蚂蚁最终会找到觅食的最短路径。

本文利用邻近点搜索及充电站插入算法来生成初始可行解（ψ0）。所有路径的信息素初始浓度设为该初始解目标函数值的倒数。设蚁群系统的规模为P，蚂蚁在生成解的过程中不断选择下一个客户点进行访问，直至没有满足条件的客户点。然后该蚂蚁返回配送中心重新出发，直到访问完所有客户点。蚂蚁在选择下一个客户点 j是根据一个转移概率公式来决定的，该概率公式同时考虑了信息素浓度以及路径的距离长短。转移概率公式如下：

其中dij为边的长度。

3.2 信息素更新

在搜索过程中信息素的更新至关重要。首先由于自然界中蚂蚁留下的信息素会随着时间的推移而挥发，因此在更新过程中引入了信息素挥发机制。其次本文采取了精英蚂蚁策略，即除了蚂蚁搜索产生的最优解所经过的路径之外，其余精英蚂蚁所产生的较优可接受路径也会被用来更新信息素的浓度。本文中，信息素浓度按如下方式进行更新：

其中，Q是一个常数，Costib为当前最优解，为δth精英蚂蚁的解。

3.3 充电站启发式插入算法

由于电动汽车电池容量有限，其行驶里程往往受到电量水平的限制。蚁群算法所构造的未插入充电站的解（φ0）往往存在违背里程约束的路径。因此，这些路径中需要插入充电站对车辆进行适当充电才能顺利完成该条路径的配送。为此本文设计了一个充电站最优插入启发式算法，主要步骤见算法2。

算法2:充电站启发式插入算法

输入：未插入充电站的解γ0

输出：最优可行解γfea

Step1 找出解γ0中所有违背电动里程约束的不可行路径；

Step2 找到电动汽车出发后能到达的最远客户点；

Step3 对最远点与配送中心或者前一个充电站之间的所有点进行以下循环；

Step4 在当前点后插入距离最近的充电站；

Step5 确定充电水平；

Step6 检查时间窗可行性；

Step7 若该条路径违背时间窗，则移除相应的客户点到移除点集合Vunvisit；

Step8 若算法已遍历所有可插充电站位置，则循环停止，否则转到Step3;

Step9 若集合Vunvisit不为空，则用邻近点搜索并重复以上Step1-9，否则算法停止。

充电站插入算法的基本思路是对于超过车辆最大里程的回路，找到电动汽车出发后能到达的最远客户点，即车辆从配送中心或者充电站出发可到达但无法继续到达下一个客户点。在该客户点后插入距离最近的充电站。若余下的路径仍里程违背，则继续按此方式插入充电站。在搜索过程中，遍历所有可插入充电站的位置。

在插充电站过程中，充电方式的选择将会决定充电之后的电池电量水平。由于路径中充电次数不定，假定当快速充电模式下所需的充电时间超过某一个阈值T0时，将选择电池交换技术作为充电方式。否则，选择快速充电方式按照实际需求对车辆进行部分充电。T0的定义如下：

其中，σ是一个0-1之间的参数，Q g表示将电量为0的电池进行快速充电至充满所需要的时间。

当充电水平确定之后，检查该回路上的客户点时间窗是否仍然满足。若有客户点的时间窗不满足，则将该客户点从该路径中移除并将其添加到集合Vunvisit。在整个充电站插入的过程中，可行解的接受第一准则首先是尽可能保留较多的客户点，其次则是接受较低配送成本的可行解。

3.4 局部搜索算法

为了进一步防止蚁群算法陷入局部优，引入局部搜索算法，扩大蚁群算法每次迭代过程中的搜索空间，提高可行解寻优的质量。本文中，局部搜索算法的核心是移除算子和插入算子。在搜索过程中，考虑到客户点位置每一次的重新调整都很可能会导致充电站最优插入位置的改变，因此局部搜索是在当前解移除充电站之后的路径上进行的。在每一次迭代之后，重新对调整后的路径应用充电站插入算法，生成可行解。

3.4.1 移除算子。本文中使用的移除算子分为两类：路径移除和客户点移除。路径移除是指移除被选中回路上的所有客户点，而客户点移除则是移除一定数量λ的客户点。λ由总的客户点数量决定，在一个特定区间内随机选择。

（1）最短路径删除算子：该算子从当前解中挑选出最短的一条回路，删除该回路上所有客户点并将这些客户点放进移除列表中，该算子的目的是尽可能最大化车载量的利用率。

（2）结束最早路径删除算子：该算子从当前解中选择配送时间结束最早的一条回路，删除该回路上所有客户点并将这些客户点放进移除列表中，该算子的目的是基于现实因素考虑，尽可能达到相应的工作时长。

（3）随机客户点删除算子：该算子从当前解中随机选择λ客户点删除，随机性的删除操作可以使得搜索过程更加多样化，防止陷入局部优。

（4）最差客户点删除：该算子计算出当前解中每个客户点距离前后邻接的客户点距离之和，按此数值进行降序排序，选择前λ个客户点进行删除。

3.4.2 插入算子。插入算子是将移除列表中的客户点重新插回被破坏的当前解中，在插入过程中需要考虑该条回路的车容量及时间窗的可行性，但不需要考虑车辆里程的限制。

（1）贪婪插入：将被移除客户点依次插回到当前解最优的位置，使得每次插入增加的成本最低。

（2）后悔值-2插入：找出所有被移除客户点的最优和次优插入位置，并计算最优插入成本和次优插入成本，取两者的差值，将差值较大的客户点优先插入其最优位置。

在搜索过程中，所有移除和插入算子均有一个相同的权重，按照轮盘赌进行随机选择组合。局部搜索算法的主要步骤见算法3。

算法3:局部搜索算法

输入：未插入充电站的初始解φ0

输出：最优可行解Ψbest

Step1 对各个算子的权重进行初始化；

Step2 将初始解φ0插入充电站产生当前可行解，Ψcurrent，Ψbest←Ψcurrent；

Step3 移除当前可行解中的充电站；

Step4 随机挑选一个移除算子，生成客户点移除列表ς；

Step5 随机选择一个插入算子，将列表ς中的客户点重新插入当前解；

Step6 调用插入算法，插入充电站生成当前可行解Ψcurrent；

Step7 若当前可行解的总成本低于最优解，则Ψbest←Ψcurrent；

Step8 若算法循环到最大次数NCmax后停止，输出最优可行解Ψbest；否则，转到Step3。

4 实验结果及分析

为了对模型和算法进行验证，采用三个典型客户分布的算例进行实验。每个算例中共包含122个点，其中一个配送中心、100个客户点、21个充电站。三个算例中，算例A的客户点呈随机分散分布，如图1所示；算例B中客户点呈簇状聚集分布，如图2所示；算例C中的客户点分布兼具簇状聚集和随机分散的特点，如图3所示。

图1 算例A中点的分布

图2 算例B中点的分布

图3 算例C中点的分布

在实验中电动汽车的相关成本参数见表2。电池更换成本设定为给一个电量为0的电池进行快速充电充满所需成本的1.2倍。

表2 电动汽车成本相关参数值

蚁群算法相关的参数值设定为P=30，α=5，β=5，φ =0.25，Q=100，算法所有代码由Visual C++编程实现。

4.1 局部搜索算法的效果

为了防止蚁群算法陷入局部最优，本文设计了以移除和插入算子为核心的局部搜索算法，与蚁群算法集成，来扩大解空间的搜索效率。传统蚁群算法（ACO）和集成局部搜索的蚁群算法（ACO-LS）求解三个算例的计算结果见表3，负Δ%值意味着最优解质量的提高。实验结果证实，局部搜索可以大大增强算法全局寻优的能力，从而显著地提高最优解的质量。

表3 蚁群算法改进效果对比实验结果

4.2 充电策略对比分析

基于三个实例，进一步对比分析了不同充电策略即允许部分充电的快充策略、更换电池以及两者混合的充电策略对配送成本的影响，实验结果见表4。结果显示，对于三个不同的实例，混合充电策略相比于单一充电策略均能有效降低配送总成本，这是因为多种充电方式能更灵活地安排充电模式，使得车辆成本、等待成本及充电成本都相对较低。虽然单一电池更换策略使得车辆数能最大程度地减少，但是由于换电池的成本显著增加了，所以配送总成本不仅没有降低反而有所上升。而单一部分快充策略虽能最大程度地降低充电成本，但由于其充电时间较长，会出现更多客户点的时间窗不可行，导致需要更多的车辆去服务客户，从而大幅度增加了车辆使用成本，使得总成本上升。

表4 不同充电策略对比

5 总结与展望

为了更好地降低充电时间对客户时间窗的影响，本文提出了混合柔性充电方式支持下带时间窗的电动汽车路径问题。柔性充电策略的引入为充电汽车的应用提供了更加灵活的运作方式，也提供了进一步降低配送时间和成本的可行途径。针对电动汽车的中途充电需求，在传统车辆路径的基础上，本文设计了一种充电站启发插入算法快速计算充电站的插入位置。同时，通过设计局部搜索算法并集成到蚁群算法的迭代过程中，提出了一种改进的蚁群算法。以三个具备典型客户点分布的实例为基础，对比了改进蚁群算法的效果。实验结果显示蚁群算法中嵌入的局部搜索对于提高解的质量有着显著的优势。通过混合充电策略和单一充电策略的对比试验，验证了混合充电策略对于降低配送成本的作用。为物流公司选择充电方式提供了具有参考价值的建议。

在下一步的研究中，电动汽车路径规划问题可以考虑更多的现实约束因素。例如，配送过程中的交通道路拥堵情况往往会影响配送的效率。在大规模配送场景中，多配送中心的电动汽车路径规划问题具有很高的应用潜力，具有较大的研究意义。此外，考虑充电桩的选址与路径问题相结合也是未来研究的方向之一。