针对电气化矿山中多车队电池更换的协同调度：一种基于仿真的优化方法

《eTransportation》：Cooperative Scheduling for Multi-Fleet Battery Swapping in Electrified Mines: A Simulation-Based Optimization Approach

针对开放-pit 矿山电动卡车与电池配送车队的协同调度难题，本研究提出基于离散事件仿真的优化框架，设计 NSPLNS 算法解决高维优化问题，并通过内蒙古案例验证其有效性和经济性。

　　

邹洪辉|赵凯琦|刘艳丽|张荣辉|马小蕾

北京航空航天大学交通科学与工程学院，中国北京100191

摘要

全球碳排放政策的实施加速了露天矿山的电气化转型。为了满足采矿卡车车队的持续运营需求，电池更换（BS）模式作为一种高效的解决方案应运而生。本研究探讨了在配备分布式电池更换站和集中式充电设施的露天采矿系统中，多车队之间的协同调度问题，这些车队包括电动采矿卡车和电池配送车辆。我们提出了一种基于离散事件模拟（DES）的优化框架，该框架利用电池更换需求和电池供应的可控性来协调供需双方的运作，从而挖掘潜在效率并制定出采矿卡车运营、电池更换活动和电池物流的最佳调度方案。该DES模型用于模拟不同车队、各种资源及设施之间的相互作用，以及运营、电池更换和电池领取过程中由排队引起的连锁延迟。此外，DES模型还作为一种修复工具，用于快速纠正不可行的解决方案。为了解决基于仿真的优化中固有的维度灾难问题，我们提出了非支配排序种群基大邻域搜索（NSPLNS）算法，该算法结合了种群基多目标搜索和个体导向优化的优点。我们设计了一系列定制的运算符以提高解决方案的质量，并在算法中明确纳入了并行仿真以提升算法效率。通过中国内蒙古的一个实际案例研究来评估所提出的框架和算法。数值实验分析了算法性能、定制运算符的影响，并进行了敏感性分析。数值结果表明，所提出的模型和算法通过最大化利润提升了运营经济效益，并通过最小化排队时间和电池更换时间提高了电池更换效率。本研究的源代码可公开获取于：https://github.com/HonghuiZou/NSPLNS。

引言

在过去十年中，由于普遍认为电气化可以减少温室气体排放并改善城市空气质量[1]，全球电动汽车车队迅速增长。电动汽车市场的扩张催生了电池更换（BS）模式，该模式降低了车辆拥有和维护成本，缓解了驾驶员的续航焦虑[2]。迄今为止，关于BS系统的研究主要集中在轻型车辆上，只有少数研究关注电动卡车[3]、[4]，而在工业场景下的研究仍然很少。幸运的是，中国的减排政策正在加速露天采矿的电气化进程，促使采矿企业用电动卡车替代传统的柴油动力运输卡车。这一转变为工业重型车辆的BS模式提供了新的研究和应用场景。

露天采矿全天候连续运行，包括五个阶段：钻孔、爆破、装载、运输和破碎。本研究调查了一个煤矿案例，其中配备528千瓦时电池的电动采矿卡车通常只能运行4小时，即使使用快速充电也需要至少1小时才能充满电。这一限制导致多次错过运营机会，每次错过机会大约会造成20万元人民币（约2.8万美元）的收入损失。为了提高经济效益和生产力，采矿企业采用了BS模式[5]、[6]。采矿卡车车队的高强度充电需求（每块电池需要0.5兆瓦的充电功率）给电网带来了压力。因此，使用了一个集中式充电站来充分利用矿内的有限电网资源，并配备电池配送车辆，这些车辆将电池从充电站运输到分布式的更换站。由于装载和运输占露天采矿运营成本的51%[7]，优化车队管理至关重要。露天采矿的电气化为车队管理带来了显著复杂性，因为调度不仅要考虑采矿卡车的运营和电池更换，还要考虑电池配送车队的调度。采矿企业迫切需要解决这些技术挑战。然而，大多数现有的关于露天采矿车队管理的研究都集中在燃油动力采矿卡车上[8]，而关于BS模式的研究主要集中在城市场景中。只有Xiao等人[16]研究了在没有集中式充电的采矿环境下单个车队的调度问题。为了填补这一研究空白，我们创新性地探索了一种优化方法，该方法结合了离散事件模拟（DES）来协同调度采矿卡车车队和电池配送车队，同时考虑了分布式电池更换和集中式充电系统。本研究的主要挑战可以概括为三个方面：

首先，露天矿山的BS和充电系统与城市环境中的系统有根本不同。在城市环境中，出行需求是随机的，受个人出行行为和交通条件的影响。因此，现有的城市BS系统研究主要集中在供应侧管理上，以在不确定性下平衡实时需求。相比之下，采矿卡车车队在固定的、预定的路线上运行，导致电池需求可预测且可控。在这种情况下，电池供应由电池配送车辆的调度决定。因此，卡车运营、电池更换过程和集中式充电之间的有效协调变得至关重要。这就需要一个协同优化框架，以同步供需双方，提高运输生产力和能源效率。

其次，露天采矿生产过程不可避免地面临资源短缺和排队问题，这两者都会影响整个系统的效率。具体来说，由于分布式更换站的电池储备量小于分配的采矿卡车车队的规模，在需求集中的高峰时段，电池配送车辆需要在更换站和充电站之间频繁往返运输电池。同时，充电站有限的充电桩数量和漫长的充电时间使得无法在短时间内提供足够的充满电的电池。这导致更换站的电池供应延迟，形成了电池短缺的恶性循环。此外，当大量采矿卡车和电池配送车辆到达时，装载区、更换站和充电站都会出现排队现象。例如，采矿卡车可能需要等待铲车完成装载或其他卡车完成电池更换，而电池配送车辆可能需要等待电池充满电。更严重的是，采矿卡车运营的任何环节的排队都可能导致后续所有步骤和其他卡车运营的连锁延迟。连锁延迟意味着系统某一部分的延迟会引起连锁效应，延迟所有后续步骤并扰乱整个运营过程。

第三，在这样一个高度耦合的系统中，每个调度方案都会触发一系列事件，影响系统状态，如排队延迟或资源可用性，从而影响后续决策。例如，是否有足够的电池可用或到达的卡车能否立即得到服务取决于早期行为的累积效应。因此，优化模型的线性和非线性约束会随着系统状态的变化而动态演变。

传统的优化方法，如混合整数线性规划（MILP），无法有效模拟排队、实时交互和动态约束，缺乏适应这些现实世界因素的灵活性和适应性。虽然实时调度系统可以通过不断重新优化来适应，但它们的短期规划视野往往导致短视的决策。基于DES的优化提供了一个高效的解决方案框架。给定一个车队调度方案，我们可以使用等效于优化模型的DES模型来模拟露天矿车队的完整运营过程，从而全面评估解决方案的性能。相比之下，预先计算的调度方案可以更好地预测复杂采矿环境中的资源交互，并提供更大的鲁棒性。通过集成启发式算法，我们可以在仿真环境中识别出具有最佳目标值的解决方案，这些解决方案被视为实际应用中的最优解。然而，基于个体的搜索算法无法模拟种群，而基于种群的算法由于无法实现局部改进而具有较长的仿真时间和较差的解决方案质量。因此，我们设计了一种高效的混合启发式算法，能够进行并行仿真计算。我们使用实际案例研究验证了模型和算法的性能，并在本文中提供了管理见解。我们的研究贡献如下：

(1)

我们研究了在分布式BS和集中式充电系统下采矿卡车车队和电池配送车队的实际协同调度问题。提出了一种基于DES的优化框架，以全面适应系统特性并模拟多个子系统之间的交互。

(2)

设计了一种混合启发式算法——非支配排序种群基大邻域搜索（NSPLNS），它将非支配排序的全局探索能力与大邻域搜索中的密集局部探索相结合。值得注意的是，算法中明确采用了提高计算效率的并行仿真架构。

(3)

根据问题特性，设计了一系列定制的运算符，通过实验结果定量验证了这些运算符能有效提高解决方案质量。此外，DES模型还被创新性地用作修复运算符，在优化过程中快速纠正不可行的解决方案。

本文其余部分的结构如下。第2节进行文献综述。第3节提出基于DES的协同优化框架。第4节设计了解决方案算法。第5节实现了实际应用，并提供了管理见解。

节选

文献综述

本节从三个角度回顾了相关文献：电池更换和充电系统、采矿车队管理以及基于仿真的优化。综述指出了现有研究的局限性，并阐明了本文所要解决的研究空白。

基于离散事件模拟的协同优化框架

在本节中，我们介绍了所提出的基于DES的协同优化框架。首先描述了实际问题背景，然后介绍了用于捕捉系统交互和不确定性的DES模型，最后制定了多目标协同优化模型。

离散事件模拟模型

DES是一种强大的工具，用于评估不确定参数对系统性能的影响。由于其能够表示事件驱动的动态和资源约束，它已被广泛应用于露天采矿中的传统卡车调度、子车队划分和车队调度研究[59]。然而，据我们所知，DES尚未应用于采矿作业中的BS场景。此外，在大多数关于车队调度的现有研究中

解决算法

在本研究中，我们旨在为多车队制定最优调度计划，这是一个具有高决策维度和复杂计算量的联合优化问题。为了解决这一优化问题中的维度灾难问题，我们采用了启发式算法。

一般来说，启发式算法可以根据用于探索的搜索过程分为基于种群和基于个体的方法

案例研究

我们使用中国内蒙古的一个实际露天采矿案例来评估所提出的框架和算法，并提供了定量比较、消融研究和管理见解。

结论

本研究首次探索了露天矿山中多车队运营的协同调度优化方法，结合了分布式BS和集中式充电系统。目标是为电动采矿卡车车队和电池配送车队制定最优调度方案。为了在优化模型中有效模拟资源交互和动态约束，我们提出了基于DES模型的优化框架。一种混合启发式算法NSPLNS

CRediT作者贡献声明

邹洪辉：撰写——原始草案、可视化、方法论、概念化。张荣辉：撰写——审阅与编辑、调查。刘艳丽：撰写——审阅与编辑、可视化、验证。马小蕾：撰写——审阅与编辑、概念化。赵凯琦：撰写——原始草案、可视化、软件开发、数据整理

未引用的参考文献

[63]。

利益冲突声明

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

致谢

本研究得到了国家自然科学基金（编号：52472318）的支持。