晨光
暗夜
晨光
极光
Bilingual Paper Reading · 中英对照精读

电动汽车充电调度与柔性服务运营：联合优化充电与服务排程

准大一 · 电气工程 × 运筹优化 × 新能源交通 —— 电动汽车充电调度精读材料
原文：arXiv:2201.03972 2022年1月11日发布 arXiv 预印本（eess.SY） 充电调度 × 分支定价 × 柔性服务运营 附英文摘要朗读音频

一、论文档案

英文标题Electric vehicle charge scheduling with flexible service operations
中文标题电动汽车充电调度与柔性服务运营（允许服务任务灵活提前/推迟出发的充电调度）
作者帕特里克·肖恩·克莱因, 马克西米利安·希弗（机构未在素材中标注）
发布时间2022年1月11日（v1）｜分类：eess.SY（系统工程与控制）
原文链接arxiv.org/abs/2201.03972
一句话概括充电桩不够用？那就让服务任务「稍微早走或晚走几分钟」——把充电与服务排程一起优化，充电基础设施最多可减少 57%，运营成本最多可省 5%。
💡 为什么选这篇给你：① 电动卡车、物流车队是「电气 + 运筹」的交叉热点，问题来自真实运营，看得见摸得着；② 方法上是教科书级的分支定价（Branch & Price）精确算法，适合建立对「精确优化算法骨架」的正确认识；③ 结论全是硬数字——57%、5%、1 小时内算出 5 天/68 辆车的最优解，可复现、可验证。

二、核心术语表（先扫一遍再读正文）

英文术语中文大白话解释
electric commercial vehicle (ECV)电动商用车辆物流、货运场景的电动卡车/货车，是本文研究的主角。
charge scheduling充电调度决定车队里每辆车「何时、在哪个桩、充多少电」的计划问题。
service operation服务运营（出车任务）车辆执行的运输/服务任务，比如一条送货线路。
central depot中央车场车辆不运营时集中停放、充电的基地，充电桩一般装在这里。
charger contention充电桩争用桩比车少，多辆车抢桩排队，需要错峰安排充电。
Time-of-Use (TOU) energy tariff分时电价不同时段电价不同，峰时价格最高可达谷时的 3 倍。
state of charge (SoC)荷电状态电池当前剩余电量，常用百分比表示。
battery degradation电池退化（老化）充放电过程对电池寿命的损耗，激进充电会加速老化。
non-linear charging非线性充电充电速率与电量的关系不是直线；用线性近似会高估或低估充电速率。
flexible service operations柔性服务运营允许服务任务在有限范围内提前或推迟出发，给充电腾出窗口。
Branch & Price (B&P)分支定价把列生成（Column Generation）嵌进分支定界框架的精确求解方法，适合大规模整数规划。
pricing problem定价子问题列生成中寻找「能改进当前解的列」的子问题；本文它是带资源约束的最短路问题。
labeling algorithm标号算法求解资源约束最短路问题的动态规划方法，本文用它精确求解定价子问题。
primal heuristic原始启发式快速构造可行解的技巧，用来加速分支定界收敛。
planning horizon规划周期调度覆盖的时间长度；本文能在 1 小时内最优求解 5 天 / 68 辆车的实例。

三、摘要中英对照（精读核心）

🎧 音频在文末，可先听一遍原文再读；每个英文句都配了逐句翻译。

摘要 Abstract

EN · 原文
Operators who deploy large fleets of electric vehicles often face a challenging charge scheduling problem.
CN · 翻译
部署大型电动车队的运营商，常常要面对一个棘手的充电调度问题。
EN · 原文
Specifically, time-ineffective recharging operations limit the profitability of charging during service operations such that operators recharge vehicles off-duty at a central depot.
CN · 翻译
具体来说，在服务任务间隙充电浪费时间、不划算，因此运营商选择让车辆休班时在中央车场集中充电。
EN · 原文
Here, high investment cost and grid capacity limit available charging infrastructure such that operators need to schedule charging operations to keep the fleet operational.
CN · 翻译
而高昂的投资成本和电网容量限制了充电基础设施的数量，运营商必须合理安排充电计划才能保证车队正常运转。
EN · 原文
In this context, flexible service operations, i.e. allowing to delay or expedite vehicle departures, can potentially increase charger utilization.
CN · 翻译
在这种背景下，柔性服务运营——即允许车辆推迟或提前出发——有可能提高充电桩利用率。
EN · 原文
Beyond this, jointly scheduling charging and service operations promises operational cost savings through better utilization of Time-of-Use energy tariffs and carefully crafted charging schedules designed to minimize battery wear.
CN · 翻译
更进一步，联合调度充电与服务运营有望通过更好地利用分时电价、并精心设计最小化电池损耗的充电计划，来节省运营成本。
EN · 原文
Against this background, we study the resulting joint charging and service operations scheduling problem accounting for battery degradation, non-linear charging, and Time-of-Use energy tariffs.
CN · 翻译
基于此，我们研究由此产生的充电与服务运营联合调度问题，并综合考虑电池退化、非线性充电和分时电价。
EN · 原文
We propose an exact Branch & Price algorithm, leveraging a custom branching rule and a primal heuristic to remain efficient during the Branch & Bound phase.
CN · 翻译
我们提出一种精确的分支定价（Branch & Price）算法，借助自定义分支规则和原始启发式，在分支定界阶段保持高效。
EN · 原文
Moreover, we develop an exact labeling algorithm for our pricing problem, constituting a resource-constrained shortest path problem that considers variable energy prices and non-linear charging operations.
CN · 翻译
此外，我们为定价子问题开发了精确标号算法——该问题是一个资源约束最短路问题，要考虑变化的电价与非线性充电过程。
EN · 原文
We benchmark our algorithm in a comprehensive numerical study and show that it can solve problem instances of realistic size with computational times below one hour, thus enabling its application in practice.
CN · 翻译
我们在大规模数值实验中基准测试该算法，证明它能在一小时内求解实际规模的问题实例，从而具备实际应用价值。
EN · 原文
Additionally, we analyze the benefit of jointly scheduling charging and service operations.
CN · 翻译
此外，我们分析了联合调度充电与服务运营带来的收益。
EN · 原文
We find that our integrated approach lowers the amount of charging infrastructure required by up to 57% besides enabling operational cost savings of up to 5%.
CN · 翻译
我们发现，这一集成方法最多可将所需充电基础设施减少 57%，同时最多可节省 5% 的运营成本。

关键词 Keywords：Charge Scheduling 充电调度 ｜ Flexible Service Operations 柔性服务运营 ｜ Branch & Price 分支定价 ｜ Battery Degradation 电池退化 ｜ Time-of-Use Tariffs 分时电价

四、引言精选（为什么这个问题重要）

① 大背景：交通电动化是大势所趋

EN · 原文
Increasing societal and political environmental awareness resulting from climate change and local and global emission problems call for a paradigm change towards sustainable transportation systems. Herein, electric commercial vehicles (ECVs) are seen as a promising alternative to internal combustion engine vehicles (ICEVs), allowing up to 20% reduction in life-cycle greenhouse gas emissions when considering the current European energy mix (cf. EEA, 2018). Moreover, ECVs may provide an economic advantage due to lower operational costs (Taefi, 2016; Schiffer et al., 2021).
CN · 翻译
气候变化以及本地和全球排放问题带来的社会与政治环保意识提升，呼唤交通系统向可持续交通转型。其中，电动商用车辆（ECV）被视为内燃机车辆（ICEV）的有力替代方案——按当前欧洲能源结构计算，其全生命周期温室气体排放可减少高达 20%；而且由于运营成本更低，ECV 还可能带来经济优势。

② 两个硬约束：充电桩有限 + 分时电价

EN · 原文
A central challenge in all of these applications is the efficient scheduling of charging operations, which are often conducted during off-service periods using private charging infrastructure installed at a central depot to avoid inefficient use of drivers' time. Here, grid constraints and high investment costs limit the availability of dedicated charging infrastructure, such that there are generally fewer (fast) chargers than vehicles. Accordingly, operators must synchronize the fleet's charging operations to avoid charger capacity bottlenecks. Moreover, time-of-use (TOU) energy tariffs, which charge different prices depending on the time of consumption, further complicate this scheduling problem: with on-peak prices up to three times as high as off-peak prices (OpenEI, 2022), it becomes economically worthwhile to consider energy prices when planning charging operations.
CN · 翻译
这些应用中的核心挑战是高效安排充电作业——充电通常安排在非服务时段，利用中央车场自建的充电设施，以免浪费司机时间。然而电网约束和高投资成本限制了专用充电设施的数量，充电桩（尤其是快充桩）一般比车少。因此运营商必须同步协调整个车队的充电作业，避免充电桩容量瓶颈。此外，分时电价（TOU）按用电时间收取不同价格，让调度问题更加复杂：峰时价格最高可达谷时的 3 倍，规划充电时考虑电价就变得非常划算。

③ 第三个维度：电池老化不能忽视

EN · 原文
Generally, charger capacity and TOU pricing favor schedules where a vehicle's state of charge (SoC) peaks at certain times, e.g., when a fast charger becomes available or energy is cheap (cf. Pelletier et al., 2018). However, these schedules impose considerable stress on an ECV's battery, such that the long-term effects of battery degradation may mitigate short-term energy cost savings (see Appendix C). Operators who want to utilize this trade-off between charger utilization, off-peak energy prices, and battery degradation must consider an accurate (non-linear) charging model as simple (e.g., linear) approximations may over- or underestimate charging rates, which potentially distorts the cost savings attainable through the trade-off mentioned above (cf. Montoya et al., 2017; Pelletier et al., 2018).
CN · 翻译
一般来说，充电桩容量和分时电价都倾向于让车辆荷电状态（SoC）在某些时刻达到峰值——比如快充桩空出来时或电价便宜时。然而，这类计划会给电池带来相当大的压力，电池退化的长期影响可能会抵消短期的电费节省。想利用「充电桩利用率—谷时电价—电池退化」三者权衡的运营商，必须采用精确的（非线性）充电模型——简单的（如线性）近似会高估或低估充电速率，从而扭曲上述权衡能带来的成本节省。

④ 机会：服务任务其实「有点弹性」

EN · 原文
These predetermined service schedules often have some (unavoidable) slack due to, e.g., driver service regulations and restrictive time windows (cf. Kok et al., 2011), such that individual service operations are flexible, i.e., can be shifted in time to a limited extent without violating upstream scheduling constraints. Operators may benefit from this flexibility and delay or expedite a service operation to allow charging at a slower charger, e.g., to make a faster charger available to another vehicle of the fleet, to charge during cheap off-peak periods, or to balance charging operations across the planning horizon to avoid charging patterns with high impact on battery health.
CN · 翻译
这些预先确定的服务排程往往有（不可避免的）松弛空间——比如司机工时法规和严格的时间窗限制，使得单个服务任务具备柔性：可以在不违反上游排班约束的前提下在时间上有限移动。运营商可以利用这种弹性，推迟或提前某个服务任务，以便让车辆用较慢的桩充电——例如把快充桩让给车队里另一辆车、把充电挪到便宜的谷时，或在规划周期内均衡充电负荷，避免对电池健康影响大的充电模式。

⑤ 问题全貌：五个要素缺一不可

EN · 原文
Concluding, operators who deploy (large) fleets of ECVs face an inherently complex planning problem comprising decisions on charging and service operation schedules, which may significantly impact the viability and practicability of an ECV fleet. Here, they need to account for i) capacity restrictions of available charging infrastructure, ii) battery degradation effects, iii) TOU energy tariffs, iv) non-linear battery behavior, and v) flexible service operations.
CN · 翻译
总而言之，部署（大型）电动商用车队的运营商面临一个本质上很复杂的规划问题：要同时决定充电计划与服务任务排程，这会显著影响车队的经济可行性与实用性。他们必须同时考虑：i) 可用充电设施的容量限制；ii) 电池退化效应；iii) 分时电价；iv) 非线性电池行为；v) 柔性服务运营。
💡 这是全文最有味道的一句：“These predetermined service schedules often have some (unavoidable) slack…”——现实中处处有「看起来不能动、其实能挪一点」的松弛。把这种松弛变成决策变量，正是联合调度的创新起点：省下的是整个充电桩的投资。

五、论文贡献（3 个要点）

EN · 原文
1. An exact Branch & Price algorithm. We propose an exact Branch & Price algorithm, leveraging a custom branching rule and a primal heuristic to remain efficient during the Branch & Bound phase.
CN · 翻译
1. 精确的分支定价算法。提出精确的分支定价（Branch & Price）算法，用自定义分支规则与原始启发式保证分支定界阶段的高效性。
EN · 原文
2. An exact labeling algorithm for the pricing problem. Moreover, we develop an exact labeling algorithm for our pricing problem, constituting a resource-constrained shortest path problem that considers variable energy prices and non-linear charging operations.
CN · 翻译
2. 定价子问题的精确标号算法。为定价子问题开发精确标号算法——一个考虑可变电价与非线性充电的资源约束最短路问题。
EN · 原文
3. Joint scheduling with quantified benefits. We find that our integrated approach lowers the amount of charging infrastructure required by up to 57% besides enabling operational cost savings of up to 5%.
CN · 翻译
3. 联合调度及其量化收益。集成方法最多减少 57% 的充电基础设施，并最多节省 5% 的运营成本——把「柔性」的价值量化了出来。

六、结论中英对照

EN · 原文
We presented a novel charge- and service operation scheduling problem where a fleet of electric vehicles fulfills a set of service operations under the assumption of limited charging station capacity, variable energy prices, battery degradation, and non-linear charging behavior. We developed an exact algorithm based on B&P to solve the proposed problem. A novel labeling algorithm with efficient dominance criteria, a primal heuristic, and a problem-specific branching rule establish the efficiency of our algorithm, which we demonstrated in numerical experiments.
CN · 翻译
我们提出一个新颖的充电与服务运营联合调度问题：电动车队在充电站容量有限、电价变化、电池退化、非线性充电的假设下完成一组服务任务。我们开发了基于分支定价（B&P）的精确算法来求解该问题——带有高效支配准则的新颖标号算法、原始启发式和面向问题的分支规则，共同保证了算法效率，并在数值实验中得到了验证。
EN · 原文
This numerical study asserts the competitiveness of our algorithm through a benchmark against an equivalent mixed-integer formulation, showing that our algorithm significantly outperforms commercial solvers. This study further shows the algorithm's scalability to instances of larger size, optimally solving instances with planning horizons of 5 days or 68 vehicles within the hour, allowing for day-ahead planning in practice.
CN · 翻译
数值实验通过与等价混合整数规划模型对比，证明了算法的竞争力：我们的算法显著优于商业求解器，并且可扩展到更大规模——能在1 小时内最优求解规划周期 5 天或 68 辆车的实例，从而支撑实际的日前规划。
EN · 原文
We further derived several managerial insights concerning the impact of service flexibility. Specifically, we find that integrated scheduling of charge and service operations allows to better utilize the trade-off between battery degradation costs and energy price, such that cost savings of up to 5% can be realized. Moreover, service flexibility reduces charger contention, allowing to reduce the number of chargers installed by up to 57%. Finally, we analyze the impact of different TOU plans on the benefit of flexible service operations. Here, we find that integrated charge and service operation scheduling performs best in scenarios with highly variable energy rates.
CN · 翻译
我们还得到了关于服务柔性价值的管理启示：联合调度充电与服务运营能更好地利用「电池退化成本与电价」之间的权衡，实现最多 5% 的成本节省；服务柔性降低了充电桩争用，可将安装的充电桩数量最多减少 57%。最后我们分析了不同分时电价方案对柔性收益的影响，发现联合调度在电价波动剧烈的场景下表现最好。

七、编者解读：这篇论文到底讲了什么（大白话版）

  1. 问题：物流公司买了一堆电动卡车，晚上回基地充电。但充电桩又贵又少、电费峰谷差价能到 3 倍、电池还怕「暴力充电」——充电计划到底怎么排才最省钱、最不伤电池、又保证第二天车都开得出去？
  2. 做法：以前的做法是「先定好每辆车几点出发，再倒推什么时候充电」（两阶段解耦）。这篇论文把两者捆在一起优化：允许服务任务提前或推迟一点点出发，用「分支定价」精确算法一次性算出最优的充电+出发计划，还专门设计了一个标号算法来处理「边充电边考虑电价和电池状态」的子问题。
  3. 结果：算得快——1 小时内能最优解出 5 天、68 辆车的真实规模实例（商业求解器做不到）；省得多——充电桩最多少装 57%，运营成本最多省 5%。
  4. 最值钱的观点：「服务时间表不是铁板一块」。现实中时间窗、司机工时本来就留有余量，把这些「柔性」利用起来，价值比想象中大得多——省掉一半以上的充电桩投资。另外，非线性充电模型必须用，线性近似会算错账。
  5. 工程意义：对电网来说，车队集中充电是典型的大负荷；调度好充电时间（挪到谷时、避开峰值）既帮运营商省钱，也帮电网削峰填谷——这正是「车网互动」和需求侧管理要解决的问题。
🎯 对保研的启示：这篇论文是「把现实松弛变成建模机会」的绝佳范例——先发现「任务其实可以挪一点」，再把它形式化成约束和决策变量，最后用经典算法框架（分支定价）落地。复试时能讲清楚「问题从哪来、模型怎么建、算法为什么快」，就是完整的科研叙事。

八、给准大一的阅读路线图 & 延伸方向

📖 怎么读这篇论文（三遍法）

  1. 第一遍（10 分钟）：只读摘要和术语表，回答三个问题——问题是什么（充电调度+柔性服务）？方法是什么（分支定价）？结果是什么（57%、5%）？
  2. 第二遍（20 分钟）：读引言 + 结论，重点体会「五个要素缺一不可」（充电容量、电池退化、分时电价、非线性充电、柔性服务），以及「服务弹性从哪来」。
  3. 第三遍（30 分钟）：读方法文字部分（B&P 框架、定价子问题、标号算法、支配准则），跳过所有公式和编号，只看文字描述；遇到不懂的术语回查术语表。

🚀 这个方向你能延伸做什么

九、英文摘要朗读（练听力用）

先盲听一遍→再看对照稿→再听一遍。目标是听出每个数字（up to 57%、up to 5%、below one hour）和术语（Branch & Price、Time-of-Use tariffs、battery degradation、flexible service operations）。