多补给模式下电动汽车的选址-路径问题：分支-定价-切割算法

《Sustainable Energy Technologies and Assessments》：Location-routing problem for electric vehicles under multi-replenishment modes: A branch-price-and-cut algorithm

　　

• •
  提出了一种针对EVLRP-MR的多因素综合MILP模型。
• •
  重构后得到一种处理时空-能量耦合的BPC算法。
• •
  BPC算法在计算效率和内存方面优于求解器。
• •
  自定义的有效不等式平均缩短19.09%的计算时间。
• •
  敏感性分析揭示了设施成本与运营效率之间的耦合关系。

引言

在绿色物流配送系统中，基础设施规划和车辆路径规划正经历着根本性的范式转变。电动汽车（EV）以其低碳排放为特征，在减轻环境影响和提升城市宜居性方面具有巨大潜力[1]。然而，向电动物流车队的转型受到固有挑战的阻碍，尤其是续航里程有限和充电时间过长。为规避与续航相关的运营瓶颈，电动汽车通常配备高容量电池。然而，这种做法在日间运营中无意间延长了充电时间，并大幅增加了服务运营商的资本支出[2]。另一种策略是车队运营商购置额外的备用车辆以弥补续航限制；然而，这同样通过增加车辆购置成本而带来严重的经济负担[3]。

电动配送车队通常依赖固定充电基础设施，这使得它们本质上不如燃油车辆灵活。近年来，快速充电和电池更换技术已成为缓解这些运营约束的高效解决方案[4]。这些新兴补给技术的应用使得电动物流车辆能够以更小的电池容量运行，从而促进更轻量化和紧凑的车辆设计[5]。这种适配不仅显著提升了城市配送环境中的路径灵活性，还降低了车队运营商的运维成本。然而，补给模式的最优选择高度依赖于具体的运营里程特征。对于相对较短的配送路线，运营商主要优先考虑电池更换，其次是无线充电；相反，对于较长距离的运营，快速充电则是更优策略[6]。

利用快速充电和电池更换技术不仅可以最小化所需车队规模，还能大幅扩展电动配送车辆的可运营范围。然而，不恰当的补给策略加上低效的路径规划会严重增加系统的运营成本。传统上，选址决策和车辆调度被视为两个独立的分层决策过程。然而，基础研究早已证明，解耦这些问题通常会产生次优解[7]、[8]。相反，这些组件的集成优化引入了复杂的时空-能量耦合，不可避免地使得联合决策过程高度复杂且计算要求极高。

尽管现有文献对电动汽车路径规划和单一补给技术进行了广泛研究，但先前的研究主要集中在单一补给模式上，且往往将设施选址与路径决策解耦。随着绿色物流配送的电气化，基础设施规划和配送路径的联合优化已成为关键问题。然而，同时纳入异构补给模式引入了关键的时间-成本权衡。具体而言，快速充电具有成本效益但耗时更长，而电池更换速度快但设施成本高。这种权衡显著加剧了时空-能量耦合，导致路径问题中的状态空间呈指数级扩张，使得传统精确算法效率极低甚至难以处理。为弥补先前相关研究的不足并克服这一计算瓶颈，本文做出以下贡献：

• (1)
  本研究针对多补给模式下的电动汽车定位-路径问题（EVLRP-MR）建立了一个全面的混合整数线性规划（MILP）模型。该模型准确捕捉了异构补给模式在时间和财务维度上的不同影响，为时空-能量耦合系统提供了严格的数学基础。
• (2)
  为解决多补给模式引起的状态空间爆炸问题，本研究提出了一种定制化的分支定价切割（BPC）算法。我们设计了一种具有多维状态扩展和严格占优准则的专门标签算法，能够在异构设施选择下高效定价出非改进路径，保证全局最优性。
• (3)
  本研究提出了从物理覆盖必要条件数学推导出的有效不等式。这些算法增强大幅缩小了可行域并加速收敛，有效解决了精确算法带来的棘手计算挑战。

此外，数值实验验证了所提方法的实际适用性，为物流运营商在车队选择和设施部署方面的战略性时间-成本权衡提供了定量见解。

本研究的结构安排如下：“文献综述”部分系统回顾了现有相关研究。“MILP建模”部分定义了EVLRP-MR问题，介绍了符号表示，并给出了数学公式。“分支定价切割算法”部分详细介绍了所提算法的框架。“数值实验”部分讨论了数值实验结果，并对关键运行参数进行了敏感性分析。最后，“结论”部分总结了整体工作并提出了未来探索的潜在研究前景。

章节摘要

文献综述

电动物流车队固有的续航限制不仅严重削弱了城市配送网络的运营效率，还增加了运营成本并导致能源资源的低效利用。因此，设施和车辆路径的集成优化构成了一个高度复杂的组合优化问题。这种集成需要对多个相互关联的要素进行全面评估，包括选址和

MILP建模

在建立模型之前，必须明确定义问题和关键参数，以增强清晰度并确保更广泛受众的可理解性。

电动汽车：配备有限容量电池的商用电动汽车，用于执行客户配送服务，具有特定的载重能力和行驶里程限制。

配送中心节点：电动汽车集中停放、维护和保养的仓库。在每日运营开始之前，

分支定价切割算法

为精确求解EVLRP-MR的MILP模型，本研究设计了一种基于列生成框架和有效不等式的精确分支定价切割（BPC）算法（如图2所示）。在主问题（MP）层级，该算法通过松弛整数约束构建线性规划模型，专注于设施选址决策和路线选择的协同优化。在定价子问题（SP）层级，算法探索可行的车辆路线

数值实验

本研究使用Gurobi 13求解器与分支定价（BAP）算法和分支定价切割（BPC）算法对不同规模的问题进行求解性能比较。所有代码均用Python 3.14编写，所有程序均在配备Apple M4处理器和16 GB RAM的MacOS上运行。所有计算均在单线程上执行。求解器和所有算法均设置了7200秒的统一计算时间限制，并且

结论

EVLRP-MR是一个复杂的组合优化问题，其中设施选址、车辆路径规划和补给调度紧密交织在一起。为求解EVLRP-MR，本研究建立了一个全面的MILP模型，并设计了一种定制化的分支定价切割（BPC）算法。所提出的BPC框架通过专门的标签算法将复杂的时空-能量耦合嵌入定价子问题中。此外，通过引入数学上严格的有效

CRediT作者贡献声明

陈陶乐：写作 – 审阅与编辑，写作 – 初稿，可视化，软件，方法论，资金获取，概念化。方莉：写作 – 审阅与编辑，方法论，概念化。唐进军：写作 – 审阅与编辑，监督，项目管理，方法论，资金获取，概念化。胡立鹏：写作 – 审阅与编辑，方法论，概念化。孙超：写作 – 审阅与编辑，监督，方法论，概念化。

利益冲突声明

作者声明，他们没有任何已知的竞争性经济利益或个人关系，可能影响本文报告的工作。

致谢

本研究部分受国家自然科学基金（编号52172310）、湖南省重点研发计划（编号2023GK2014）、湖南省芙蓉学者奖励计划（编号202405）以及湖南省自然科学基金（编号2026JJ90251）资助。

陈陶乐|方莉|唐进军|胡立鹏|孙超