考虑充电调度的电动无人车配送路径规划问题研究

曹珍　韩曙光

摘 要： 在充電站有充电容量约束的情况下，研究充电调度电动无人车配送路径规划问题。首先以极小化车队中电动无人车的最大行驶距离为目标，构建数学规划模型，为电动无人车车队安排配送路径，使得各车的行驶距离尽可能均衡；其次应用动态规划算法（Dynamic programming algorithm， DP）求解小规模算例，改进遗传-模拟退火算法（Genetic-simulated annealing algorithm， GA-SA）优化较大规模算例的电动无人车路径和充电策略；最后对相关因素进行灵敏度分析，以验证所提出算法的可行性与合理性。结果表明：DP算法解小规模算例表现良好；改进GA-SA算法与单纯遗传算法（Genetic algorithm， GA）相比，求解大规模算例时优化的路径效果更佳，且大大缩短电动无人车车队的最长子路径的长度和总行驶距离。该研究可以为物流公司的电动无人车配送业务发展提供参考，帮助企业提高电动无人车的运输效率和服务水平，降低配送成本。

关键词： 电动无人车；配送路径规划；充电容量约束；充电调度；动态规划；遗传-模拟退火算法

中图分类号： O223.1；O223.4

文献标志码： A

文章编号： 1673-3851 （2023） 11-0784-11

引文格式：曹珍，韩曙光.考虑充电调度的电动无人车配送路径规划问题研究［J］. 浙江理工大学学报（自然科学），2023，49（6）：784-794.

Reference Format： CAO Zhen， HAN Shuguang. Research on the distribution routing problem of electric unmanned vehicle considering charging scheduling［J］. Journal of Zhejiang Sci-Tech University，2023，49（6）：784-794.

Research on the distribution routing problem of electric unmanned vehicle considering charging scheduling

CAO Zhen， HAN Shuguang

Abstract：  Under the restriction that the charging station has charging capacity constraints， we focus on researching the distribution routing problem of electric unmanned vehicles with charge scheduling. A mathematical programming model was firstly established with the objective of minimizing the maximum travel distance of electric unmanned vehicles of the fleet， so as to arrange the distribution path for the unmanned vehicle fleet and balance the travel distance of each vehicle as much as possible. Secondly， dynamic programming （DP） algorithm was applied to solve small-scale examples， and genetic-simulated annealing algorithm （GA-SA） was improved to optimize the route and charging strategy of electric unmanned vehicles for large-scale examples. Finally， related factors were analyzed to verify the feasibility and rationality of the proposed algorithm. The results show that the DP algorithm performs well in solving small-scale examples. Compared with the simple genetic algorithm （GA）， the improved GA-SA can get a more reasonable solution when solving large-scale examples， and greatly shorten the length of the longest sub-path and the total driving distance of the electric unmanned vehicle fleet. This study can provide reference for the development of electric unmanned vehicle distribution business of logistics companies， help enterprises improve the transportation efficiency and service level of electric unmanned vehicles， and reduce distribution costs.

Key words： electric unmanned vehicles; distribution route planning; charging capacity constraints; charging scheduling; dynamic programming; genetic-simulated annealing algorithm

0 引 言

近年来，随着能源价格不断上涨，电动无人车在城市物流配送环节逐渐成为传统内燃机汽车的替代品，但电动无人车在实际配送中面临电池续航能力不强、充电设施不足等问题。因此，研究电动车辆（Electric vehicle，EV）的路径规划和充电策略，对于推广电动无人车进行物流配送具有重要的现实意义。

传统的车辆路径规划问题（Vehicle routing problem，VRP）最早由Dantzig等［1］提出，是组合优化中研究最广泛的问题之一，至今已有大量的相关研究成果。张玉州等［2］考虑救灾物资车辆路径规划问题，极小化救灾车辆的总运输距离，根据任务紧急度设计了任务再分配策略的遗传算法（Genetic algorithm，GA），优化了应急物资的配送路径；Tamke等［3］研究有二维装载容量约束的车辆路径规划问题，设计了分支切割算法求解。随着绿色环保的电动汽车的普及与发展，电动车辆路径规划问题（Electric vehicle routing problem，EVRP）扩展了传统的VRP问题，逐渐成为路径规划的研究热点。葛显龙等［4］结合部分充电策略建立整数规划模型，设计了混合模拟退火算法（Simulated annealing algorithm，SA），优化了电动汽车的物流配送路径；揭婉晨等［5］考虑了客户需求可拆分的情况，通过改进分支定价算法求得EVRP問题的最优解；Wu等［6］采用自适应调整信息素挥发因子和突变算子，提出了一种混合的蚁群算法以求解带时间窗的EVRP问题。以上研究的优化目标多是极小化总行驶距离；然而，在实际生活中，物流公司追求的往往不是寻求整个车队的总行驶距离最短，而是均衡利用车辆，降低电池的退化率。该问题的优化目标可以描述为极小化车队中车辆的最大行驶距离，这类问题称为最小最大车辆路径规划问题（Min-max vehicle routing problem，MMVRP），如在线m-steiner旅行商问题［7］、灾区无人机监控［8］等均属于该类问题。

目前MMVRP问题的相关研究主要集中在近似算法和启发式算法上。当无固定仓库点，起点任意且车辆的数量k也任意时，Yu等［9］给出了一个5-近似算法；随后Yu等［10］证明了MMVRP问题的最坏情况界下界为5/4；Yakc［11］考虑了单配送中心的最小最大车辆路径规划问题，采用蚁群优化以及其他随机方法分配客户给车辆，进一步用3-opt方法局部优化；Sze等［12］研究了有容量约束的MMVRP问题，通过并行贪婪插入方法生成初始解，再利用自适应变量邻域搜索改进；李小川等［13］根据问题特征并结合人工鱼群算法的寻优思想，提出了一种精英反向学习鱼群算法来解决MMVRP问题。近些年智能物流配送逐渐发展，研究最小最大电动车辆路径规划问题（Min-max electrical vehicle routing problem，MMEVRP）具有一定的现实意义；然而以上带充电的路径规划研究往往都忽略了充电站容量问题，一般假设一个充电站可同时容纳无数车辆充电。

近年来已有学者开始研究充电站有容量约束的充电路径规划问题以及相关求解算法。例如：Bruglieri等［14］考虑了充电站内的充电桩数量有限的电动车辆路径问题，基于弧变量建立混合整数规划模型，设计割平面的方法精确求解小规模算例；李默涵等［15］考虑了充电站内车辆排队等待充电的时间对路径成本的影响，采用自适应大规模邻域搜索算法求解路径；Keskin等［16］研究充电站出现排队情况对路径选择的影响，考虑依赖排队时间的分段线性充电，使用自适应大邻域搜索可行空间和确定可行路径。

虽然有关充电站有容量约束的路径规划问题研究已取得了一定的进展，但涉及充电站有容量约束的MMEVRP问题研究相对较少，且现有模型并没有考虑充电等待时间。本文在上述研究基础上，结合物流配送的实际状况，针对充电站有容量限制的情况，以极小化车队中电动无人车的最大行驶距离为目标，结合充电等待时间建立了可多次完全充电的混合整数规划模型，研究电动无人车的路径规划和充电调度。最后应用动态规划算法（Dynamic programming algorithm，DP）和改进遗传-模拟退火算法（Genetic-simulated annealing algorithm，GA-SA）求解该模型，并通过Solomon标准算例验证算法的有效性和策略的可行性。电动无人车路径规划研究可为物流企业运营调度车辆提供决策性参考意见。

1 问题描述与模型构建

1.1 问题描述

假设某物流快递公司配有一个配送中心，另有若干个充电站点，充电站的充电桩数量有限，由若干数量的装载容量和电池容量均相同的电动无人车组成配送车队给客户派送货物。在不超过车辆的装载容量的情况下，电动无人车充满电后出发，完成配送任务后返回配送中心；由于车辆的电池容量有限，在行驶过程中可能需要根据实时电量前往充电站进行充电。例如：受充电站数量限制，电动无人车1和电动无人车2在行驶过程中需要前往同一个充电站补充电量，此时可能存在排队等待充电的情况，对应的电动无人车车队的配送路径示意图如图1所示。本文作如下假设：a）为保证交付效率，每个客户只访问一次；b）电动无人车以恒定速度行驶，且电池电量消耗系数恒定，消耗的电量与行驶距离呈线性关系；c）充电站内的充电桩数量有限，每个充电桩充电功能均正常，且充电速率一样；d）当电动无人车前往充电站充电时，车辆的电池总是充满电离开的；e）电动无人车在客户点停留过程中不消耗电量；f）不考虑客户点与充电站的时间窗限制。

以极小化车队中电动无人车的最大行驶距离为目标，研究充电站有容量限制的电动无人车的路径规划和充电调度问题，合理地安排各无人车的行驶路径和充电计划，以满足客户的配送需求，尽可能减少充电次数和排队充电等待时间，均衡各无人车的工作时长。

1.2 MMEVRP数学模型构建

本文中的符号及其含义见表1。无向图j表示配送网络；V=｛C∪F′∪｛o｝｝表示全部点的集合；E=（i，j）i，j∈V，i≠j表示弧集，每条弧关联一个非负的行驶时间tij和距离dij；车辆集合K是由电池容量和装载容量均相同的同一车型组成，表示至多有k辆无人车可以被分配来执行送货任务。

考虑充电站容量有限的电动无人车车辆路径规划问题数学模型如下：

式（1）表示极小化车队中电动无人车的最大行驶距离；式（3）—（4）表示所有客户点的货物仅由一辆电动无人车配送一次；式（5）—（6）表示电动无人车均从配送中心出发，最终返回配送中心；式（7）表示到达和离开同一点的弧的数量相等，即每个点需保持流量平衡；式（8）表示消除不包含配送中心的子回路；式（9）表示电动无人车的载货能力限制；式（10）表示电动无人车从客户点i行驶到客户点j时，载重量的变化约束；式（11）表示电动无人车的电池电量的变化；式（12）表示到达任意客户点的电量和离开该客户点的电量是一样的，即在客户点处不耗电池电量；式（13）表示电动无人车的电池电量不大于电池容量；式（14）表示电动无人车在充电站的充电量；式（15）—（16）表示每辆电动无人车到达各节点的时间变化约束；式（17）表示电动无人车在充电站处完全充电所需时间；式（18）表示在充电站处电动无人车等待充电的时间；式（19）表示0-1变量约束。

2 模型求解

2.1 动态规划算法

传统的VRP问题是NP难问题，而最小最大电动车辆路径规划问题是VRP问题的扩展，因此MMEVRP问题也是NP难问题。由于该问题的复杂性，大部分研究利用GA算法或蚁群算法等启发式算法求解，这些算法通常可以在较短的时间内得到解，但无法保证解的质量，因此本文先采用可精确求解的DP算法求解此问题。

DP算法常用来解决多阶段决策过程的优化问题，在路径规划方面也有较好的应用成果，利用DP算法求解最优路径可以节省反复搜索可行路径的时间。

由袁森等［17］证明的引理可知，最小最大圈覆盖问题的最优解将客户集C恰好划分成了k个子集，构成集合C=｛S1，S2，…，Sk｝。为解决小规模的MMEVRP问题，首先逆时针依次筛选出一定角度范围内的所有客户点，这些客户点的货物需求之和不能超过无人车的装载容量，所有客户点恰好分成k个客户集合，分别由k辆车派送。

DP算法可快速求解MMEVRP问题小规模实例，但随着问题规模的增大计算时间会呈指数型增长，导致算法性能降低，甚至可能无法求解出问题的最优解，因此精确算法在求解大规模实例时不再适用。此时需要利用寻优性能好的启发式算法对大规模算例进行求解，本文改进GA算法能在可接受时间内得到问题较好的全局最优解。

2.2 改进遗传-模拟退火算法

GA算法是源于生物界的启发式算法，是一种高效的随机全局搜索优化方法，常用来求解各种车辆路径规划问题。为更好地求解电动无人车的配送路径以及选取合适的充电站充电，本文对GA算法进行了两个方面的改进。首先为优化充电站位置的选取与充电策略的选取，设计了一个充电站最优插入策略；其次由于GA算法容易陷入局部最优，引入Metropolis准则，以一定概率接受劣质解，增大算法迭代过程中的搜索空间，提高所提出算法的求解质量。

改进遗传-模拟退火GA-SA算法的主要步骤如下：

a）确定染色体编码规则。在模型求解过程中，要确定电动无人车数量、每辆车需要服务的客户集合以及访问的充电桩，采用自然数编码会比较直观得到每辆无人车的配送顺序，用o表示配送中心，用1，2，…，n表示对应的客户点，n+1，n+2，…，n+p表示配送网络中的充电桩编号，即配送网絡中一共存在p个充电桩（包括虚拟充电桩），最后在起点和终点分别插入配送中心，即构成1条染色体。

b）计算适应度函数。适应度函数用于评价种群中染色体优劣以及趋近于最优解的程度，适应度越大，表明染色体质量越高，被选择的可能性越大，本文的目标函数是使得车辆的最大距离最小，取目标函数f的倒数作为适应度函数fit（i）。

c）选择算子。基于对个体适应度的评估，计算种群的每个个体的fit（i），遗传概率为pi=fit（i）/∑nj=1fit（j），计算个体累计概率为qi=∑nj=1pj，最后采用轮盘比例选择适应度较大的个体进入下一次迭代。

d）设计搜索算子。使用部分匹配交叉和基因倒位插入变异两种策略进行寻优。邻域寻优策略示意图如图2所示。交叉操作分别在两个染色体中随机截取相同大小的基因片段，拼接到另一个染色体前端，再将拼接后的两个染色体中与拼接基因重复的基因删去，部分匹配交叉操作的示意图如图（a）所示；在一个染色体上随机挑选两个基因片段互换位置。这样可以保证种群的多样性，避免交叉操作引起的局部收敛，变异操作的示意图如图（b）所示。

e）运用自适应Metropolis准则。对原始种群进行GA算法的选择、交叉、变异等操作后，形成新一代种群，再运用Metropolis准则增强算法的局部搜索能力，分情况选择个体。若新解w′的目标函数f（w′）小于初始解w的目标函数f（w），即f（w′）

f）选择充电站插入。由于车辆的电池容量有限，配送过程中要考虑电动无人车的电量情况。GA算法构造的未插入充电站的初始路径解中可能存在违背距离约束的配送路径，因此，这些路径还要插入充电站，对应车辆需要去充电站补充电量。由于配送网络中含有的充电站数量相对较少，所以电动无人车在充电站处可能产生等待时间。

为此本文设计了一个充电站最优插入策略，改进GA-SA算法流程如图3所示，具体步骤如下：

步骤1。找出所有未插入充电站的解中违背距离约束的不可行配送路径。

步骤2。在不可行配送路径中，找到电动无人车出发后电量低于电池安全电量阈值α之前能到达的最远客户点，此时安排该车辆前往附近充电站充电，若不能到达则转步骤4，否则转步骤3。

步骤3。对当前在该充电站内的电动无人车按到达充电站（站内有m个充电桩）时间顺序进行编号｛n1，n2，…，ni｝，根据先到先充原则充电，若ni≤m，说明有充电桩空闲，车辆无需等待可马上充电；若ni>m，说明车辆等待充电桩空闲才能充电，接在充满电后离开此充电站的有最小编号的车辆nj（j

步骤4。电量低于电池电量阈值α时不能到达附近充电站视为不可行路径，继续迭代搜索可行路径解。

步骤5。若所有车辆均完成货物配送，则结束本次调度；否则重复以上步骤，直到达到迭代次数条件，结束算法。

3 实验分析

本文使用Matlab 2016a与Python3.7编程语言对算例进行求解，运行环境为64位Windows操作系统，运行内存为4 GiB，处理器为Intel（R） Core（TM） i5-7200U CPU@2.50 GiHz 2.71 GiHz的计算机。选取Solomon标准测试集中部分数据［18］进行实验，数据集根据客户的分布特点分为三类：C类数据集的点是聚类分布的，R类数据集的点是随机分布的，RC类数据集是半聚类半随机分布的。

3.1 算例一分析

首先选取Solomon算例中C101的9个点作为基础测试，编号0表示配送中心，编号5和9表示配送网络中的充电站，站内只有单个充电桩，设配送中心内可使用的相同类型电动无人车最大数量为3，该类型的无人车的装载容量为50 kg，距离约束为65 km，电池耗电系数为1.1 kWh/km，充电系数为100 kWh/h，恒定的行驶速度为60 km/h，利用DP算法可以快速求出具体路径分别是：0-3-1-9-0、0-7-8-5-6-0、0-2-4-0。由于配送网络中有2个充电站，3辆无人车只有2辆车前往充电站充电，此算例没有等待时间，3条子路径长度为77.97、68.53、63.22，因此车队中电动无人车的最大行驶距离是77.9，该值即为目标函数值。各客户点、仓库点横纵坐标X和Y的位置信息，以及算例一电动无人车配送路径如图4所示。

3.2 算例二分析

算例二以“数据类别-客户点数量-充电站数量-每个站内充电桩数量”命名，例如“C101-40-1-2”表示在C101标准实例中选取前40个点进行实验，取1个点为充电站，该充电站中有充电桩接口2个。设C101-40-1-2中配送中心编号为0，充电站编号为29，设配送中心中可使用的电动无人车最大數量为5辆，车辆的装载容量为200 kg，距离约束为80 km，电池耗电系数为1.1 kWh/km，充电速率为100 kWh/h，行驶速度为60 km/h，电池电量阈值α设为20%，同时设定算法的最大迭代次数G=2000次，初始温度为10000 ℃，冷却因子为0.99，交叉概率为pc=0.9，变异概率为pm=0.1，变异次数为10次。目标是使得电动无人车车队的最大行驶距离尽可能地小，合理调度充电车辆，减少充电次数以及排队等待充电时间，提高配送效率。

利用单纯的GA得到的目标函数值为196.16，车辆的总配送距离为925.83，无人车队在充电站处共充电9次，充电时间共为552.63，等待充电时间为44.60，其中车辆1的充电等待时间达28.40，车辆4的充电等待时间为16.20，其他车辆充电没有排队等待时间；而使用本文提出的改进GA-SA求解的最小最大子路径长度为100.51，车队的总配送距离为498.11，电动无人车车辆在充电站共充电5次，总的充电时间为366.59，充电等待时间均为0。优化后的目标函数值，即最小最大子回路长度缩短了48.76%，电动无人车车队的总行驶距离减少了46.20%，而且充电时间与等待时间也显著减少，电动无人车配送工作效率提高明显。

表2为改进GA-SA算法求解MMEVRP算例的求解结果，从表中数据可以看出，各无人车的路径长度相差较小，工作时长较均衡，符合目标要求。改进GA-SA算法生成的电动无人车配送路径如图5所示，GA算法和改进GA-SA算法求解的优化过程收敛曲线对比如图6所示，改进GA-SA算法在迭代1000次左右时逐渐收敛，得到最优目标函数值，虽然比GA算法的收敛速度慢，但是从适应度函数值的变化过程可看出本文改进的算法优化效果更佳，求解质量更优。

3.3 算例三分析

为了进一步验证本文提出的算法求解不同类型和规模算例的性能，结合客户总需求，假设可使用的无人车最大数量增加为8辆，其他参数设置同算例二，对一些算例进行仿真实验，分别用未改进的GA算法和所提出的改进GA-SA算法单独求解10次，记录每次的运行结果、充电次数以及程序运行时间，将10次计算的平均运行时间和最优解对比记录见表3。

从上述求解结果可以看出，本文所提出的改进GA-SA算法在求解不同类型和规模的MMEVRP实例时都给出了更优的配送路径，安排更少的充电次数能够满足电量需求。在配送网络完全相同的情况下，从目标函数列中可以看出对比未改进前结果，改进GA-SA算法缩短电动无人车车队中最长子路径的长度显著，与单纯的GA算法相比，优化率（未改进结果与改进结果的差值与未改进结果的百分比）达30%以上，极大地提高了电动无人车的配送效率。虽然算法的求解时间随着问题规模的增大而增加，但求解结果更优、质量更高。可以预测，在求解更大规模的实际物流配送问题时，该算法也将表现出更快的求解速率和更好的优化性能，能合理有效地给出电动无人车车队的物流配送路径规划和充电调度，给物流公司提供一些指导性意见。

3.4 影响无人车行驶距离的关键因素的灵敏度分析

在MMEVRP问题中，实验的计算结果会受无人车数量和充电站中充电桩数量影响，因此下文将分析这两个因素的改变对计算结果的影响。从C101中选取数据进行测试，客户数为50，充电站数量为2，站内只有单个充电桩。

a）无人车数量。将电动无人车的耗电系数设为1.1 kWh/km，最多可使用的无人车数量分别设为3辆、5辆、7辆。电动无人车的数量与其最大行驶距离和总行驶距离的关系如图7所示，从该图可以看出电动无人车数量对不同算例的子路径中的最大行驶距离和车队的总行驶距离的变化趋势。当电动无人车的耗电系数不变，车辆数量增加时，无人车队中最长配送子路径长度逐渐减小，这符合实际配送情况，所需要服务的相同客户数量时，可使用的车辆数量越多，分配给各无人车的客户数量会相应减少，因此配送路径中的最大行驶距离会变小，但是车队的总行驶距离相应的有所增加。车队中的最大行驶距离和总行驶距离都受数据集中客户点分布影响，由于R101和RC101数据中客户点分布较分散，行驶过程中车辆的充电次数不可避免地增加，此时目标函数和总行驶距离都会比聚类分布的C101大。

b）车辆的耗电系数。将最多可使用的无人车数量设为5辆，车辆的耗电系数分别设为0.8、1.1 kWh/km和1.4 kWh/km，电动无人车耗电系数与无人车的最大行驶距离和总行驶距离的关系如图8所示。从图8可以看出，当电动无人车的耗电系数越来越大时，充电次数会有所增加，所以最大子路径长度也会随之增加，车队行驶的总距离也逐渐增加。这符合实际情况，耗电系数越大，说明电动无人车行驶单位距离电池电量消耗的越多，而符合电量约束的可行路径减少，电量不足时无人车需要多次前往充电站充电，所以会改变无人车的行驶路径，这时各辆无人车的行驶距离以及车队的总距离都会相应地有所增加。同样地，由于数据集中客户点分布情况不同，耗电系数增大时，较为分散的数据集R101和RC101行驶过程中充电次数增加的可能更多，此时子路径的最长距离和车队的总行驶距离都随之增大。

由以上实验可以看出，利用电动无人车在城市中配送货物，可以通过增加电动无人车数量和开发新技术降低耗电系数使得最长子路径距离尽可能地短，均衡各无人车的工作时长。

4 结 语

本文研究了在充电站有充电容量约束的情况下，考虑配送途中的充电次数以及可能存在的充电等待时间的电动无人车的路径规划和充电调度优化问题，建立了MMEVRP的数学规划模型。针对小规模算例，应用DP算法精确求解无人车配送路径；针对中大规模算例，改进GA-SA算法求解，增强算法搜索能力，避免算法陷入局部最优。数值实验以及灵敏度分析结果表明，本文提出的优化算法可以减少充电次数以及充电等待时间，同时缩短车队中最长子路径的长度和车队的总行驶距离，使得车队中车辆的工作时间更加均衡，减少车辆的电池损耗率。本文为物流企业选取电动无人车来进行物流配送提供一定參考，帮助物流企业提高电动无人车的利用率和配送效率，降低物流公司的配送成本。

在实际城市无人物流配送系统中，还需考虑客户点的服务时间窗口等其他限制，因此后续研究可以进一步考虑客户时间窗的路径规划、部分充电的充电调度策略等。

参考文献：

［1］Dantzig G B， Ramser J H. The truck dispatching problem［J］. Management Science，1959，6（1）： 80-91.

［2］张玉州，徐廷政，郑军帅， 等.考虑紧急度的救灾车辆路径问题建模与优化［J］.计算机应用，2019，39（8）：2444-2449.

［3］Tamke F， Buscher U. A branch-and-cut algorithm for the vehicle routing problem with drones［J］. Transportation Research Part B： Methodological， 2021，144：174-203.

［4］葛显龙，李祖伟，葛小波.考虑灵活充电策略的带时间窗物流配送路径优化研究［J］.控制理论与应用，2020，37（6）：1293-1301.

［5］揭婉晨，侍颖，杨珺， 等.需求可拆分电动汽车车辆路径问题及其改进分支定价算法研究［J］.管理学报，2020，17（12）：1873-1880.

［6］Wu H G， Gao Y L， Wang W T， et al. A hybrid ant colony algorithm based on multiple strategies for the vehicle routing problem with time windows［J］. Complex & Intelligent Systems， 2023， 9（3）： 2491-2508.

［7］Zhang Y B， Zhang Z， Liu Z H， et al.An asymptotically tight online algorithm for m-Steiner Traveling Salesman Problem［J］. Information Processing Letters， 2022，174：106177.

［8］Guo Q， Peng J， Xu W Z， et al. Minimizing the longest tour time among a fleet of UAVs for disaster area surveillance［J］. IEEE Transactions on Mobile Computing， 2022， 21（7）： 2451-2465.

［9］Zhang Y B， Zhang Z， Liu Z H，Yu W， Liu Z H.Improved approximation algorithms for some min-max and minimum cycle cover problems［J］. Theoretical Computer Science， 2016，654： 45-58.

［10］Yu W，Liu Z H.Better approximability results for min-max tree/cycle/path cover problems［J］. Journal of Combinatorial Optimization， 2019，37（2）：563-578.

［11］Yakc E.A heuristic approach for solving a rich min-max vehicle routing problem with mixed fleet and mixed demand［J］. Computers & Industrial Engineering， 2017，109：288-294.

［12］Sze J F，Salhi S，Wassan N.The cumulative capacitated vehicle routing problem with min-sum and min-max objectives：An effective hybridisation of adaptive variable neighbourhood search and large neighbourhood search［J］. Transportation Research Part B： Methodological， 2017，101：162-184.

［13］李小川，刘媛华，王影歌.求解最小最大VRP的精英反向学习鱼群算法［J］.传感器与微系统，2020，39（2）：140-143.

［14］Bruglieri M，Mancini S，Pisacane O. The green vehicle routing problem with capacitated alternative fuel stations［J］. Computers & Operations Research， 2019，112： 104759.

［15］李默涵，毛李帆，郑从镇， 等.考虑充电等待成本的电动汽车路径问题［J］.广东电力，2020，33（7）：33-41.

［16］Keskin M，Laporte G，atay B.Electric vehicle routing problem with time-dependent waiting times at recharging stations［J］. Computers & Operations Research， 2019， 107： 77-94.

［17］袁森，陈开奇，李江坤， 等.最小最大圈覆盖问题的精确算法［J］.中国科学：信息科学，2022，52（6）：960-970.

［18］Solomon M M. Algorithms for the vehicle routing and scheduling problems with time window constraints［J］. Operations Research， 1987，35（2）： 254-265.

（責任编辑：康 锋）

收稿日期： 2022-11-29网络出版日期：2023-06-07

基金项目： 国家自然科学基金项目（12071436）

作者简介： 曹 珍（1998- ），女，江西赣州人，硕士研究生，主要从事组合优化方面的研究。

通信作者： 韩曙光，E-mail：zist001@163.com