💻 computer science

A Graph-based Decomposition Framework for Flow-based Charging Station Location Problems

本文提出了一种基于图的分解框架，该框架通过将网络划分为较小的子问题、分别求解并对聚合结果进行优化，从而提高了在大规模交通网络上解决基于流的充电站选址问题的计算效率和可扩展性。

原作者： Jingyu Xiang, Paula Carroll, Annunziata Esposito Amideo

发布于 2026-08-25

📖 1 分钟阅读☕ 轻松阅读

原作者： Jingyu Xiang, Paula Carroll, Annunziata Esposito Amideo

原始论文采用 CC BY 4.0 许可（https://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

向电动汽车的转型是现代交通领域最重大的变革之一，它有望净化空气并减少日常出行的碳足迹。然而，要使这一转型取得成功，驾驶员需要一个可靠的充电网络。与只需几分钟即可完成且几乎随处可见的加油过程不同，为电动汽车充电需要时间，并且需要特定的地点。如果驾驶员在电池电量不足时找不到充电器，车辆就会变得无法使用，从而产生一种被称为“里程焦虑”的现象。这种焦虑在长途旅行中尤为严重，因为车辆必须穿越广阔的道路，而周围并没有加油站作为安全保障。因此，城市规划者和工程师面临着一个复杂的难题：究竟应该在哪里建设这些站点，才能既高效地服务最多的人群，又不至于在冗余的基础设施上浪费资金？

这不仅仅是一个在地图上挑选位置的问题，而是一个巨大的数学挑战。交通网络是一个由连接数千个城镇和交叉口的道路组成的网络，每天都发生着数百万次的行程。为了找到完美的解决方案，计算机必须分析每一条可能的路线、每种可能的充电技术以及每种可能的充电站位置组合。随着道路网络规模的增长，所需的计算量会呈爆炸式增长，甚至会让最强大的超级计算机也感到难以承受。试图一次性解决整个问题的传统方法往往会陷入困境，无法在合理的时间内找到理想的答案。都柏林大学的研究人员开发了一种处理这一问题的新方法，通过将庞大的网络分解成更小的、易于管理的碎片，使他们能够为此前难以解决的大规模高速公路系统找到高质量的解决方案。

研究人员将重点放在了爱尔兰高速公路网络上，这是一个由代表主要城镇和交叉口的90个关键节点组成的系统。他们的目标是确定新充电站的最佳位置，以平衡两个相互竞争的目标：尽可能降低建设和运营站点的成本，同时最大限度地减少驾驶员在充电或绕道前往充电站时所花费的额外时间。他们使用了一个复杂的模型，该模型考虑了不同类型的充电方式，如慢速插电式充电器、快速充电器和电池更换设施，同时也考虑到了驾驶员可能会为了节省总时间而选择稍长的路线前往充电站这一事实。当他们尝试使用强大的计算机通过标准的直接法来解决这个问题时，系统表现得很吃力。即使在运行了五个小时后，计算机仍无法找到一个既便宜又高效的解决方案，这往往导致所提出的网络成本显著高于必要水平。

为了克服这一障碍，团队引入了一个基于图的分解框架。研究人员并没有将整个高速公路网络作为一个巨大的整体来处理，而是利用数学技术将网络切割成若干个较小的、独立的子网络。想象一下，高速公路系统就像一个巨大的、缠绕在一起的线团；研究人员的方法则是小心翼翼地将其理顺成几个较小的、整齐的线束。他们测试了三种不同的切割线束的方法：一种方法是根据行政边界对城镇进行分组；另一种方法是使用一种高质量的算法来平衡各组之间的交通流量；第三种方法则是根据城镇之间的距离进行聚类。一旦网络被划分开来，研究人员就会独立地解决每个小线束中的充电站问题。然后，他们将这些局部解决方案重新缝合在一起，并增加一些额外的站点以处理在不同线束之间移动的交通流。最后，他们运行了一个优化过程，以移除任何不必要的站点，并确保整个系统作为一个整体能够平稳运行。

这一方法的成果令人瞩目。通过将问题拆解，研究人员发现他们找到的解决方案不仅计算速度更快，而且明显优于直接法所得到的结果。在测试中，该分解框架生成的充电站网络在满足驾驶员时间约束的同时，其建设和运营成本要低得多。例如，在一种直接法运行五小时后仍无法找到理想方案的情景中，分解法在不到一小时的时间内就找到了一个更优的方案。研究表明，网络切割的方式至关重要。那种平衡了各小组间交通流量的方法表现最好，这表明一个好的解决方案取决于理解人们如何在景观中实际移动，而不仅仅是看道路在物理上是如何连接的。

研究人员还发现，仅仅将碎片化做得更细并不总是更好。如果他们将网络切割成过多的微小片段，各部分之间的连接就会变得过于薄弱，最终导致整体方案效果不佳。最有效的方法是进行适度的划分，既保留了自然的交通流，又使单个问题足够小以便快速求解。这一发现为规划者提供了一条清晰的路径：解决这类大规模基础设施难题的关键在于尊重网络的底层结构和人类旅行的模式。通过使用这种分解框架，规划者现在可以应对此前无法触及的大规模充电站问题，确保电动汽车革命得到稳健、高效且规划周密的充电基础设施网络的支持。

技术摘要：一种基于图分解的流量型充电站选址问题框架

问题陈述

充电站选址问题（CSLP）对于支持电动汽车（EV）的广泛普及和实现碳中和目标至关重要。尽管已经开发出了先进的流量型 CSLP 模型，以考虑现实中的约束条件——例如异构充电技术、容量限制、路径偏差以及基础设施成本与用户出行时间之间的多目标权衡——但在大规模交通网络上求解这些模型在计算上仍然难以实现。

现有的 CSLP 分解技术通常通过分离变量、约束或场景来对优化模型进行划分。然而，这些方法往往无法利用底层运输网络的拓扑结构。因此，在文献中存在着关于图分解方法的空白，这类方法需要能够保留网络连通性和空间流量分布，特别是在处理当子问题独立求解时难以维持全局权衡的双目标流量模型时。

方法论

本文提出了一种基于图的分解框架，旨在解决大规模、双目标的流量型 CSLP 模型。该框架通过**具有多种类型充电站的容量限制多路径加注选址模型（CMPRLM-MTCS）**进行说明，这是一个双目标混合整数线性规划（MILP）模型，旨在最小化：

$z_1$ ：新建站点及扩建的总投资与运营成本。
$z_2$ ：电动汽车用户经历的总额外行驶时间（充电时间 + 偏差时间）。

该框架通过四个阶段运行：

1. 网络分解

将原始运输网络 $G=(N, A)$ 使用图划分或聚类技术分解为 $P$ 个不相交的子网络。研究评估了三种具体方法：

KaHIP：一种高质量的图划分工具，旨在最小化边切割的同时平衡节点权重（交通流）。
地理划分：基于行政区域（如爱尔兰省份）进行分解，并使用 KaHIP 进行进一步精细化。
层次聚类：基于簇间距离的凝聚聚类，包含针对加权和未加权 O-D 对的变体。

2. 交通流分解与子问题求解

交通需求被分为三个组成部分：

子网络内流量：位于同一子网络内的 O-D 对。这些作为独立的 CSLP 子问题进行求解。
聚合的子网络间流量：跨越子网络边界的 O-D 对。为了避免重新引入全额计算负担，这些流量被聚合为连接子网络的代表性 O-D 对。代表的选择基于相对于电动汽车驾驶里程的距离度量（均值、中位数、流量加权均值/中位数）。
未覆盖流量：在完成前两个阶段后仍未被覆盖的残余 O-D 对。

框架首先求解子网络内子问题，并将由此产生的站点位置固定为现有设施。然后，它求解一个针对聚合后的子网络间流量的子问题。

3. 恢复与集成

由于独立求解分解后的子问题不能保证原全局问题的可行解（特别是关于全局时间约束 $z_2$ ），因此引入了一个恢复步骤。通过求解原模型的松弛版本（ $M''$ ）来识别任何未覆盖的 O-D 对。随后在目标函数中添加惩罚项，以强制选择额外的站点来覆盖这些残余流量。

4. 最终精炼

对集成解应用后处理精炼算法（算法 1）。此阶段：

将最高效的充电类型分配到选定的位置。
在保持可行性的前提下，迭代地移除冗余站点。
执行充电类型交换（例如，在不同位置之间交换站点类型），以在保持可行性的同时降低总成本。

核心贡献

新颖框架：本文引入了一种分解策略，该策略划分的是网络拓扑而非仅仅是优化变量，从而保留了原始大规模实例中至关重要的空间和拓扑特征。
双目标适配：该框架专门解决了双目标优化在分解过程中的挑战。它采用了一种恢复机制和全局约束保持策略（使用 $\epsilon$ -约束法），以确保局部子问题的解能够集成为高质量的全局解，且不会丢失预期的成本与时间之间的权衡。
聚合策略：提出了使用代表性 O-D 对来聚合子网络间流量的方法，在计算效率与更好地捕捉空间分布特征（相比于单一节点中位数方法）之间取得了平衡。
实证评估：研究使用包括图指标（如边切割、子网络直径）和流量指标（如流量负荷不平衡、子网络间流量比例）在内的指标，对不同的分解配置（变化的分解方法、子网络数量 $P$ 以及权重方案）进行了系统评估。

实验结果

该框架在 90 节点的爱尔兰高速公路网络实例上进行了测试。计算实验将该分解框架与使用 Gurobi 优化器直接求解原始模型（设定 18,000 秒时间限制）的结果进行了对比。

计算效率：与 Guropi 基准相比，分解框架始终能在显著更短的计算时间内（通常低于 4,000 秒）实现更低的成本相关目标值（ $z_1$ ）。
解质量：对于具有挑战性的实例（例如，在 $\alpha=0.9$ 或较大偏差容许度下的紧凑时间约束），Gurobi 往往无法在时间限制内找到高质量的可行解，而是返回高成本或较大的整数间隙。分解框架则能成功找到可行且成本更低的解。
方法比较：基于 KaHIP 的分解通常产生最佳的 CSLP 结果，优于地理划分和层次聚类。这表明，维持平衡的交通负荷和最小化边切割对于 CSLP 性能而言，比纯粹的空间紧凑性更为关键。
$P$ 的影响：增加子网络数量（ $P$ ）并未线性地提高性能。过度细碎的分解（例如 $P=13$ 或 $18 $）会使网络碎片化，增加子网络间的流量比例，并降低解的质量。适度的分解水平（例如$ P=6 $或$ 9$）被证明是最优的。
权重方案：在分解过程中纳入边权重和 O-D 流量权重通常改善了 CSLP 的结果，强调了在划分过程中反映网络结构和交通需求强度的重要性。

重要性与主张

本文声称，所提出的框架为大规模交通网络上的双目标流量型 CSLP 模型提供了一种有效且可扩展的求解策略。其意义在于：

弥合差距：它将网络分解分析与 CSLP 优化联系起来，证明了保留拓扑特征和流量模式对于解质量至关重要。
实际应用性：该框架支持一种渐进式的规划逻辑（局部部署 $\to$ 区域间支持 $\to$ 全系统精炼），这反映了现实世界的基础设施部署策略。
性能表现：它证明了基于网络拓扑的分解在处理复杂的、大规模的电动汽车基础设施规划问题时，在计算时间和解决方案成本方面均能优于直接优化和基于变量的分解方法。

作者总结道，虽然该框架前景广阔，但未来的研究应探索用于选择子网络数量的自适应规则、处理子网络间流量的高级策略，以及将元启发式算法集成到框架各阶段中。