论文作者：Mouna Kchaou-Boujelben
论文原文：Kchaou-Boujelben, M. (2021). Charging station location problem: A comprehensive review on models and solution approaches. Transportation Research Part C: Emerging Technologies, 132, 103376.
推文作者：林诗然 中国科学院地理科学与资源研究所，中国科学院大学资源与环境学院
我们分上下篇，解读本篇发表在Transportation Research Part C: Emerging Technologies的综述《Charging station location problem: A comprehensive review on models and solution approaches》。其中，上篇重点介绍充电站选址规划问题的数学建模与博弈论方法，下篇重点介绍求解方法与进一步的讨论。
1. 背景
充电基础设施规划对促进电动汽车（EVs）和其他替代燃料汽车的使用具有战略影响。重要的是，决策者需要回答关于充电站的数量和位置的问题，以满足客户的充电需求，并满足现实生活中考虑的某些限制。
因为交通运输活动约占全球二氧化碳总量的四分之一的排放量，各国政府一直在促进使用“绿色”车辆，以减少污染。通过各种激励措施，鼓励司机用完全由电力驱动的电动汽车（EVs）、同时使用电力和内燃机（ICE）的混合动力汽车或氢燃料电池汽车取代传统的汽油汽车。尽管近年来电动汽车用户数量不断增加，但全球电动汽车市场的增长速度依然缓慢。汽车购买价格、有限的驾驶里程和充电器供应不足是更广泛采用电动汽车的主要障碍。
汽车要用充满电的电池行驶，这确实是司机“里程焦虑”的一个来源。他们中的许多人认为，在旅途中需要停下来充电是一个麻烦，他们可能会担心在到达目的地前电量不足。长时间的等待和充电时间也可能会阻止司机购买电动汽车。然而，随着新技术的发展，电动汽车产品在未来应该会得到改善，并生产出更实惠的汽车。最新的电动汽车已经具备了更长的行驶里程，约200英里，是特斯拉S（402英里）提供的最高性能，但由于世界各地缺乏足够的充电基础设施，电动汽车市场的扩张仍然受到阻碍。
最近电动汽车销量的增长鼓励了许多政府，特别是欧洲和亚洲的政府，为基础设施项目收费提供激励措施。根据的数据，尽管2020年新冠肺炎疫情危机导致汽车市场整体下降，但2020年欧洲的插电式汽车销量呈爆炸式增长。插电式汽车目前占汽车市场的13%，其中全电动汽车占6.5%。在美国，2021年电动汽车销量预计将比2020年增长约70%，占市场份额的3.55%，而2015年仅占市场份额的0.65%。因此，全球公共电动汽车充电器的数量预计将从2020年的100万增加到2040年的1200万。然而，如表1所示，安装电动汽车充电器，特别是快速充电器，是一个巨大的投资。正如Jochem等人所解释的那样，搬迁充电站也是一个沉重而昂贵的过程。因此，充电服务提供商选择最佳位置以满足尽可能多的充电需求是至关重要的。在这种情况下，如果司机可以在不耗尽的情况下完成行程，充电需求被认为是满足的。相应的问题，称为充电站选址问题（Charging station location problem, CSLP），因此是我们调查的重点。近年来，越来越多的学者研究CSLP问题。该综述统计了近些年来相关学术论文的数量趋势与所发表的刊物。
2. 充电站选址问题建模（原文第2.1节）
本文首先对充电需求和充电站的覆盖能力进行建模，并给出了一些典型的数学模型，主要是基于流的模型（Flow-based models），具体涵盖流量捕获模型、流量加油模型、弧覆盖模型、路径划分模型、电池SOC跟踪模型等。
流量捕获模型（Flow capturing location model, FCLM）：该模型基于Church和Revelle所提出的最大覆盖设施选址模型（Maximal covering location problem, MCLP）设计。其目标是开设有限数量的充电站，以最大化所覆盖的电动汽车流量。FCLM的表述如下：
FCLM的主要不足是，它没有考虑到电动汽车有限的驾驶范围。
流量加油模型（Flow refueling location model, FRLM）：由Kuby和Lim提出的FRLM是第一个考虑到电动汽车（或更普遍的替代燃料汽车）驾驶范围限制的基于流量的选址模型。给定一个固定的行驶范围，使用在预处理步骤中生成的站点的组合来定义行程覆盖。FRLM的表述如下：
FRLM的主要不足是，定义行程覆盖的组合的生成对于现实生活中的实例来说是耗时的，并且它随着节点数量沿路径的增加而呈指数级增长。
弧覆盖模型（Arc covering）：为了克服在FRLM中产生组合的困难，Capar等学者提出了一种基于弧覆盖方法的新问题公式，根据该方法，如果覆盖属于一个行程的每个弧，则考虑覆盖行程。这个新的建模方式的关键创新点是引入可以覆盖相应弧的一组节点。该问题的表述如下：
路径划分模型（Path-segment）：路径划分的核心思想是将每一个行程分解为起讫点之前被连续遍历的一系列路径。下面提出的相应数学模型旨在通过确定应该覆盖哪些行程，并在每次被覆盖的行程上建立一个最优路径，同时在每个建立路径的节点上放置一个站点，从而最大限度地提高所覆盖的电动汽车流量。
进一步地，本综述基于图4说明了MirHassani和Ebrazi的扩展网络（Expanded network，对应综述文献[134]）。扩展网络定义了一组节点和弧。其中，节点是在原行程q上的节点（即图4中的O_q, A, B, C, D, D_q）基础上，引入人工起讫点（即图4中的s和t）。弧（图4中虚线所示）连接了扩展网络上的一些节点，这些节点之间所需的行驶距离不超过电车的最大行驶里程（若考虑往返行程，则距离不应超过电车的最大行驶里程的一半）。
电池SOC跟踪（Battery SOC tracking）：Wang和Lin提出了一种基于集合覆盖的建模方法，在车辆访问的每个节点上跟踪电池的充电状态（SOC），以确保剩余的充电量为正。该问题的表述如下：
3. 博弈论（原文第2.2节）
博弈论的目标是建模的多个决策者根据某些规则进行交互，然后获得基于他们所做的决定的回报。CSLPs的第一组决策者包括CS定位规划者，即政府和私人机构，而第二组决策者包括充电基础设施的用户，即需要充电服务的车辆的司机。私人投资者的目标是满足客户，同时最大化其利润，而政府机构的目标是尽量减少总社会成本，并促进公平地获得充电设施。电动汽车司机需要以最少的时间和成本来完成他们的行程，但也可以考虑其他因素，如充电地点的吸引力。
Bernardo等人和Guo等人考虑了电动汽车汽车市场进入者之间的竞争互动。这两项研究都研究CS投资者利润最大化和电动汽车驾驶员效用最大化的情况下的均衡位置和定价。Bernardo等人考虑的效用函数考虑了从出发地到目的地时最短路径的偏差，以及收费地点设施的定价和存在。除了目的地吸引力和收费成本，Guo等人使用的效用功能还包括旅行时间和收费地点可用的总容量。
对与博弈论相关的CSLP文献的回顾表明，人们对该领域的兴趣越来越浓厚，特别是对双层的基于流的模型的发展，其中在上层考虑CSLP，在底层解决网络流平衡问题。网络规划者的目标（上层）和网络用户的目标（下层）之间的差异促使问题分为两个阶段。双层方法不是假设用户将遵循规划者根据选择的路径和充电计划决定的最佳设置，而是在决策路径和充电计划中纳入驾驶员的自私行为。电动汽车司机通常会选择从起点到目的地的路径，以减少自己的旅行时间或距离。
在CSs中，旅行时间显然包括驾驶时间，但也包括充电时间和等待时间。此外，在实践中，部分道路的行驶时间取决于穿过该部分的车辆流量。文献也通过建模，考虑了旅行时间和车流量之间的关系。
除了旅行时间外，司机还可能会考虑其他因素来选择路径和充电计划。例如，文章建议司机做出决定基于效用函数，包括旅行时间，CSs的可用性，充电成本和位置吸引力，而Wang等使用效用函数等于司机的概率在充电设施有限的容量。在建模结构方面，双层CSLPs的上下层通常通过下层问题中网络流平衡条件的互补约束连接起来，并添加到上层问题中。
此外，值得注意的是，上面引用的双级CSLP模型假设在较低水平的司机选择路径在一组预定的路径，而在其他情况下，较低的水平可能涉及解决EV路由问题，每个司机决定，基于CSs位于网络规划者，允许他完成旅行的最短路径。另一个提出一种不同的建模结构的值得注意的工作由Liu和Wang提出。作者开发了一种三级的方法，除了上层的位置决策和下层的路径选择决策外，用户在传统的插电式技术或无线充电技术中选择他们的车辆的技术类型。
4. 决策变量（原文第2.3节）
CSLP模型主要旨在确定CSs的最佳位置。然而，在基于流的CSLP模型中，为了评估充电需求满足的程度，还需要进行其他与电动汽车的充电计划和行程覆盖相关的决策，而基于节点的模型通常使用客户-站点分配变量来确保需求满足。额外的决策如CS容量（每个打开车站的充电器的数量），技术选择（电池交换或充电，快速或缓慢充电），偏离最短路径和车辆路由决策也很重要，纳入问题建模以捕捉问题主要决策者的相互关系。本推文展开介绍容量决策，对其他几类决策变量感兴趣的读者可阅读原文第2.3节。
基于有能力节点的设施定位问题已经在文献中得到了广泛的研究，但我们更感兴趣的是它对电动汽车环境的适应。例如，Cui等学者通过集成交通网络和电网的混合整数非线性规划（MINLP）研究了车站位置、站容量和电网相关决策之间的相互关系。Bai等人将车站位置和容量决策与技术选择（交换或充电站）结合在一个双目标模型中，研究成本最小化和服务质量最大化之间的权衡，后者被评估为司机完成充电所花费的时间。Xie等人开发了一种两阶段的方法，其中CSs被放置在第一级，每个开放电站的光伏板和存储单元的容量在第二级被确定。一般来说，通过在每个充电站安装更多的充电器来增加充电站容量意味着更多的需求覆盖，但会导致更高的投资成本。此外，高站容量的另一个优点是为电动汽车司机提供更好的服务，并减少他们在车前的等候时间。等待时间的成本由Dong等人和Ghamami等人使用排队论进行评估，并包含在他们的目标函数中。Xie等和Yang等使用概率方法获得服务质量约束：Xie等在他们的模型将随机机会约束实施电动汽车司机的概率找到一个空充电器在短等待时间应该足够高而Yang等认为电动出租车的概率可以至少充电一次一天，以高于一定水平。
然而， CSs容量的增加会给电网造成更大的压力。正如Wang等人所指出，这需要检查需求覆盖或等待时间的增加与对配电网的负面影响之间的权衡。也就是说，投资预算的减少可能会导致一些车站的容量不足，从而迫使司机使用不同的充电计划。
司机也可能被迫选择比最短路更长的路，以便找到空的充电器。Wang等人和Xie等人采用了结合电站容量决策和路径选择决策的集成CSLP模型。其他的集成模型也包含了技术的选择通过确定CSs的位置和大小来分析可能的权衡。例如，Ghamami等人认为电动汽车电池技术是他们模型中的一个决策变量，因为对优质电池技术的更高投资将导致更长的驾驶里程，从而减少充电需求和更短的等待时间。
关于容量约束建模，这里的一个相关问题是，在实践中依赖于“运营”占用率度量的短期充电容量管理如何与长期车站选址决策相结合。如果考虑一般的固定电荷容量定位问题，可以注意到，容量限制只是将分配给设施的总容量与设施在规划期间可以处理的最大容量进行比较。显然，由于设施位置是一个战略问题，规划周期通常是一年或多年，因此，模型中使用的容量限制只是每个位置的需求的总体表示，但不能用于日常容量管理。然而，一旦设施建成，就可以调整客户的分配决策，以便将需求从一个拥挤的位置转移到另一个具有闲置容量的位置。
综上所述，在CS定位问题中，容量约束在规划范围内相当集中，或以一种保证在最坏情况下（峰值需求）中有足够容量的方式表示。他们的作用是帮助确定定位设施的最佳规模，但日常调整容量是必要的，以避免拥堵和长时间的等待时间。对于充电站来说，将需求从一个地方转移到另一个地方并不容易。然而，有了新技术，就可以实时通知司机每个充电设施的实际拥堵情况，并让他们相应地决定最佳的充电方案。甚至有可能帮助他们决定适当的电动汽车路由算法考虑设施拥堵。
5. 不确定性和时间依赖性（原文第2.4节）
电动汽车充电基础设施规划和更普遍的设施位置涉及战略决策，影响跨越很长的时间。设施选址问题的参数，如需求和成本，在规划期间可能变化很大，因此在做出网络设计决策时难以准确预测。因此，许多研究人员对随机设施位置问题进行了研究，他们提出了不同的模型和解决方法来处理不确定性。此外，在长期规划中，决策者必须处理随时间变化的参数，并需要使他们的决策适应这些变化。在这种情况下，一个多阶段模型提供了根据问题参数的演化动态做出决策的可能性。通常，在电动汽车充电基础设施规划的背景下，多阶段建模允许根据充电需求和可用预算在每个时段打开所需数量的CSs，而不是对整个规划范围做出一次性决策。它还允许根据每个时期的网络状况调整更多的操作决策。
参考文献
Kchaou-Boujelben, M. (2021). Charging station location problem: A comprehensive review on models and solution approaches. Transportation Research Part C: Emerging Technologies, 132, 103376.
微信公众号后台回复
加群：加入全球华人OR|AI|DS社区硕博微信学术群
资料：免费获得大量运筹学相关学习资料
人才库：加入运筹精英人才库，获得独家职位推荐
电子书：免费获取平台小编独家创作的优化理论、运筹实践和数据科学电子书，持续更新中ing...
加入我们：加入「运筹OR帷幄」，参与内容创作平台运营
知识星球：加入「运筹OR帷幄」数据算法社区，免费参与每周「领读计划」、「行业inTalk」、「OR会客厅」等直播活动，与数百位签约大V进行在线交流
文章须知
论文作者：Mouna Kchaou-Boujelben
推文作者：林诗然
责任编辑：张云天
微信编辑：疑疑
文章由『运筹OR帷幄』原创发布
如需转载请在公众号后台获取转载须知
关注我们
FOLLOW US
