一种针对具有模糊需求的电动汽车路径规划问题的两阶段自适应变邻域搜索方法

《Swarm and Evolutionary Computation》：A two-stage adaptive variable neighborhood search approach for electric vehicle routing problem with fuzzy demand

电动汽车模糊需求路径规划问题研究：提出基于可信度的机会约束模型及两阶段自适应变量邻域搜索算法，通过预优化构建基础路线并动态调整搜索方向，结合随机模拟识别路线失败并设计高效重分配策略，实验验证其优于传统方法且决策者保守态度可获最优配送方案。

　　

韩芳|朱玉琴

中国淮南师范学院机械与电气工程学院，淮南232038

摘要

本文研究了在模糊需求条件下的电动汽车路径规划问题（EVRPFD），该问题在现实世界的物流场景中非常普遍。为了解决这个问题，我们基于可信度理论构建了一个机会约束模型，旨在最小化所有车辆的总行驶距离。随后，提出了一种两阶段自适应变邻域搜索（TAVNS）元启发式算法，该算法包括预优化阶段和重新调度阶段。在预优化阶段，设计了一系列搜索机制来构建预优化路径。特别是开发了一种自适应摇动操作符，用于动态指导算法的搜索方向。在重新调度阶段，采用随机模拟方法来识别预优化阶段生成的路径中的故障，并提出了一种重新分配策略来解决这些故障。实验结果表明，所提出的TAVNS显著优于其他算法，并在多个案例中更新了已知的最优解。此外，通过对路径修复策略的可行性分析验证了所提出的重新分配策略能够有效处理路径故障，并且产生的额外成本低于传统修复策略。最后，通过研究不同偏好值下的结果，探讨了决策者态度的变化如何影响交付成本，并得出结论：当决策者采取相对保守的态度时，可以实现最优的交付计划。

引言

几十年来，减少温室气体排放一直是公众关注的焦点。由于化石燃料车辆的广泛使用，交通运输占这些排放量的近四分之一[1]。鉴于日益严重的环境挑战和政府政策，许多物流公司（如京东、TNT和UPS）已经采用电动汽车（EV）来替代其配送系统中的化石燃料车辆[2]。与传统化石燃料车辆相比，电动汽车由于其零排放、低噪音和高能量转换效率的特点，可以有效大幅减少碳排放[3]。然而，电动汽车的续航里程无法与化石燃料车辆相匹配，而且即使在城市核心区域，现有的充电站数量也相对有限。因此，电动汽车必须及时在充电站充电以克服续航里程的限制。这些问题使得电动汽车的路径规划比化石燃料车辆更加困难，从而引发了关于电动汽车运输规划（即电动汽车路径规划问题EVRP）的研究。在过去的几十年中，学者们提出了多种EVRP变体，例如带有时间窗口的EVRP（EVRPTW）[4]、有限容量的EVRP（CEVRP）[5]和异构EVRP（HEVRP）[6]，或者专注于不同的充电策略，包括全额充电[7]、部分充电[8]和电池更换[9]。

目前，大多数关于EVRP的研究都是在确定性环境下进行的，从而忽略了现实世界场景中固有的不确定性因素[10]，如行驶时间、客户需求和服务持续时间。在这些不确定性中，需求不确定性是最常见的场景之一，它广泛应用于各种应用中，包括废物收集[11]、人道主义援助[12]和家庭医疗护理[13]。在这种场景下，客户的需求是事先未知的，只有在车辆到达客户所在地时才能确认。实际上，已经针对传统车辆路径规划问题（VRPs）中的不确定需求进行了大量研究[14]。然而，VRPs的解决方案仅考虑了客户访问顺序的规划，而EVRPs的解决方案不仅关注客户订单，还需要安排充电站（例如选择充电站点和确定充电时间）。因此，针对不确定需求的VRP（VRPUD）的解决方案不适用于解决需求不确定性的EVRP问题。

此外，在许多数据稀缺的场景中，如紧急物流和按需配送，可用于规划的订单信息往往不完整，或者仅基于语言描述而不是精确的历史数据[15]。例如，决策者可能只知道某个区域的“高”需求，或者新客户的订单将在特定范围内“大致”出现。传统的随机模型不适用于此类场景，因为它们需要准确的概率分布[16]。相比之下，采用过于保守的鲁棒优化方法可能会导致能源效率低下和不必要的充电安排，从而削弱电动汽车的经济和环境效益。

为了解决这些限制，本研究采用了一种模糊优化模型，称为具有模糊需求的EVRP（EVRPFD）。该模型将可信度理论与决策者的偏好值相结合，以描述数据稀缺场景中的需求不确定性，从而生成更符合电动汽车实际运营的路径和充电计划。

本文的贡献如下：

• •
  基于模糊需求框架为EVRPFD构建了一个机会约束模型，目标是最小化所有电动汽车的总行驶成本。这建立了一个适用于模糊需求场景的实际电动汽车物流模型。
• •
  为了解决EVRPFD，提出了一种TAVNS算法，该算法包括预优化阶段和重新调度阶段。在预优化阶段，根据设计的搜索机制构建预优化路径。在重新调度阶段，采用随机模拟方法来识别路径故障，并开发了一种重新分配策略来处理这些故障。
• •
  实验结果表明，TAVNS能够生成高质量的解决方案，甚至在多个确定性EVRP案例中更新了已知的最优解。此外，通过与对比算法的比较实验验证了TAVNS在处理EVRPFD方面的性能。
• •
  通过分析不同决策者风险态度下的结果，我们发现当决策者采取相对保守的态度时，可以获得最稳健的EVRPFD解决方案。

本文的其余部分组织如下。第2节回顾了相关文献。第3节给出了EVRPFD的正式描述。接下来，第4节解释了所提出的算法。最后，第5节展示了实验研究，第6节总结了这项工作。

小节片段

不确定场景的建模方法

对于需求不确定性的场景，主要有三类建模框架：随机框架、鲁棒框架和模糊需求框架。

随机需求框架基于概率理论，将需求建模为具有已知概率分布的随机变量。它适用于具有丰富历史数据和稳定统计规律性的场景[16]，[17]。

相比之下，鲁棒需求框架仅假设需求落在某个不确定区间内，而不考虑其他因素

数学模型

在本节中，我们定义了EVRPFD的数学模型，本文中使用的符号在表1中给出。

解决方案方法

在EVRPFD中，每个客户的需求是事先未知的，只有在电动汽车到达后才能确认。为了解决这个问题，我们提出了一种TAVNS算法，该算法分为两个不同的阶段：

• 1.
  预优化阶段（调度前）：根据模糊需求信息和决策者的偏好，构建基线路径方案。
• 2.
  重新调度阶段（执行期间）：电动汽车按照基线路径方案为顾客提供服务，并逐渐获取他们的实际需求。

实验研究

本节验证了所提出算法的性能。首先，我们采用了IEEE WCCI2020进化计算竞赛中关于EVRP的部分基准案例[1]。具体来说，对于每个客户$i$，其原始需求为$p_i$，我们定义$\stackrel{?}{p_i}$为客户$i$的模糊需求，其中$\stackrel{?}{p_i}=(p_i=(1?\gamma )\times p_i,p_i=p_i,p_i=(1+\gamma )\times p_i)$, 其中$\gamma =0。25$。其次，对一些案例进行了参数敏感性实验以确定

结论

本研究探讨了EVRPFD问题，并基于可信度理论开发了一个机会约束模型，目标是最小化所有车辆的总行驶成本。为了解决该模型，我们提出了一种TAVNS算法，该算法包括预优化阶段和重新调度阶段。具体来说，在预优化阶段，设计了一系列改进的操作符，特别是在可信度约束下。值得注意的是，开发了一种自适应摇动操作符来动态调整

CRediT作者贡献声明

韩芳：撰写——审阅与编辑、撰写——原始草稿、软件、方法论、概念化。朱玉琴：撰写——审阅与编辑、撰写——原始草稿、可视化、监督。

利益冲突声明

作者声明他们没有已知的竞争财务利益或个人关系可能会影响本文报告的工作。

致谢

本工作得到了中国安徽省高等学校重点科学基金的支持，项目编号为2022AH051583。