《Applied System Innovation》：An Operational Mixed-Integer Programming Model for Autonomous Electric Ride-Hailing Fleets
编辑推荐：
本文研究一个自主电动网约车（autonomous electric ride-hailing）车队的运营者，其必须在每个时段为每辆车决策：原地停留、空驶接客、载客行驶或在充电站充电。所提出的混合整数规划（mixed-integer programming, M
本文研究一个自主电动网约车（autonomous electric ride-hailing）车队的运营者，其必须在每个时段为每辆车决策：原地停留、空驶接客、载客行驶或在充电站充电。所提出的混合整数规划（mixed-integer programming, MIP）模型同时整合了五项运营特征：前往乘客处的空驶（deadhead travel）、接客容忍时间窗（tolerance window）、载客状态（occupancy state）、在容量受限充电站的部分充电（partial charging）以及按分时电价（time-of-use tariff）购电。目标函数综合了行驶成本、未服务请求的惩罚、购电费用以及期末剩余能量的价值。此外，研究证明，若电池在后续每个时段均具有剩余容量（spare capacity），则充电最优当且仅当该期末估值（terminal value）超过电价。在三个价格水平下、对求解至证明最优（proven optimality）的算例所进行的计算实验证实了这一阈值。结果表明，分时电价的价值取决于其低价时段落在何时：在六小时班次内，同一收入中性（revenue-neutral）电价在低价时段与车队充电时段重合时使电费降低，而在不重合时使电费升高，两种情况下服务水平均无变化。此外，期末估值能够在不影响服务的前提下捕获免费充电机会，而最小荷电状态（state-of-charge）下限则是达到更高电池目标的更廉价手段。
论文解读文章
一、研究背景与问题
自主电动网约车服务正从有限试点向持续商业运营过渡。在此类系统中，单一运营者控制每辆车的所有决策，这与由人类司机独立选择工作、空驶和补能时机的传统平台截然不同。在一个班次内，运营者必须决定收集哪些乘客、如何规划车辆前往乘客及请求之间的路线、何时派车前往充电站，以及在场站内购买多少能量。这些决策相互耦合：派去充电的车辆无法提供服务；服务远距离请求消耗能量并约束后续选择；某时段购得的能量无法以相同价格在其他时段获得。现有文献分别处理这些特征：电动车辆路径问题（electric vehicle routing problem）纳入电池限制和充电但假设需求预知；动态车辆路径处理时变请求到达但抽象掉能量；网约车与移动即服务模型刻画匹配与再平衡但通常将充电视为外生或忽略能量价格。尽管Ali等人[4]和Zhang等人[5]近年已开始整合部分特征，但尚无模型同时表示全部五项运营特征，并由此导出对期末剩余能量的价值及其对应的充电条件。本研究的核心动机正在于此：在统一模型中同时呈现这些耦合，并刻画其产生的行为。
二、研究内容与主要结论
研究人员提出了一个混合整数规划模型，在有限时域内为每辆车每个时段决策原地停留、空驶、载客或充电。模型同时表示五项运营特征：前往乘客处的空驶、接客容忍时间窗、载客状态、容量受限充电站的部分充电以及分时电价下的购电。车辆移动采用时间扩展弧（time-expanded arc）表示，携带在途状态并精确强制多时段行程时间。目标函数综合行驶成本、未服务请求惩罚、购电费用并减去期末剩余能量价值。研究建立了核心定理（Theorem 2）：在电池于后续每个时段均具有剩余容量的条件下，充电最优当且仅当期末估值率超过当前电价；Remark 2通过反例表明该容量条件不可省略。计算实验在三个价格水平上证实了充电阈值，量化了车队对分时电价的响应，并刻画了车队规模、乘客容忍度和需求强度的影响。此外，研究将期末估值与实践中使用的最小荷电状态约束进行比较，表明两者应对不同的失效模式。该模型的意义在于：期末估值率并非需要校准的自由参数，而是运营者对储存能量的估值，充电条件即基本的套利条件，这为充电决策提供了直接的经济解释。
三、关键技术方法
研究人员采用了以下主要技术方法：其一，时间扩展网络（time-expanded network）表示，将车辆位置表示为可用性变量与出发变量的双变量族，通过排他约束强制在途车辆在任何区域均不可用，精确处理多时段行程时间；其二，混合整数规划（MIP）建模，目标函数综合行驶成本、未服务惩罚、购电费用与期末能量价值，约束涵盖状态守恒、请求收集与窗口、单载客限制、充电能量与舱位容量、电池平衡等；其三，基于Bin Packing问题的归约证明模型NP-hard；其四，使用OR-Tools的CP-SAT求解器求解至证明最优，连续量以100为比例缩放为整数并截断，以25秒或60秒为时间限制；其五，通过独立枚举程序对单车辆算例进行验证，两者在三十个算例上一致。算例由生成器产生：方形网格区域带空间抖动，行程时间由欧氏距离按30 km/h计算并向上取整至时段，请求按含三个日内峰值的时变泊松过程到达，车辆初始分布于按需求权重加权的区域，三个随机种子42、142和242控制区域布置、车辆初始化和请求生成。
四、研究结果
充电阈值（Section 5.1）：在固定电价下变化期末估值率，所有配置均求解至证明最优。当时无能量购买；在（扫描中首个超过电价的取值）处车队开始充电并购买50单位能量，转变区间包围至扫描分辨率。在另外两个价格水平下重复测试，均呈现电价以下无充电、电价以上有充电的模式。超过阈值后解在广泛范围内对不敏感，服务在处开始下降，机制是车辆时间的竞争。
分时电价响应（Section 5.2）：在六小时班次（24个15分钟时段）下，两个收入中性电价仅低价时段位置不同。当低价时段落在班次末尾（与车队充电集中期重合）时，电费降低超过三分之一，每单位均在低谷购买且服务不变；当低价时段落在班次开始（电池仍接近满电）时，仅5%在低谷购买，电费升高。在固定电价下车队89%的能量在班次后三分之一段购买。
最小荷电状态约束对比（Section 5.3）：在车辆以25%容量起步、高需求下，10%及以下下限松弛；20%下限约束生效，损失1.6个百分点服务且不诱导充电；30%下限成本升至12.2个百分点并出现充电；40%下限无可行调度。期末估值在每个水平均诱导充电而不损失服务，两者共同作用时服务成本仍归因于下限。达到30%终端电池，下限花费12.2个百分点服务，估值花费18.8个百分点；估值以免费获得4.4个百分点终端电池，利用的是空闲车辆时段中的充电。
车队规模、容忍度与需求（Section 5.4）：调整后服务率在六辆车时达到100%的可服务请求，边际贡献递减（第二、三辆车合计46.2个百分点，第四、五辆18.6，第六辆3.9）；空驶占行驶成本比例从4.2%升至29.9%。乘客容忍度从立即匹配提升至四时段等待使调整后服务率从64.2%升至81.5%，前两个时段贡献大部分增益（6.4和6.9个百分点）。需求从低到高使调整后服务率从91.5%降至62.2%，空驶比例从35.0%降至7.7%，充电时段从7.3降至2.7。舱位容量在标准配置下非约束，在诱导竞争的构造算例中单舱位限制充电至5.7时段和85单位能量，双舱位提升至7.3时段和110单位。
可求解性（Section 5.5）：在60秒限制下，模型可求解至证明最优至六个区域、四辆车、十时段时域，更大规模在最优性约1.5%至3%范围内返回可行解。增长由出发变量主导，其数量为。
五、讨论与结论
讨论部分指出，定理2确定车队何时充电但未确定运营者在极高估值下会放弃多少服务；观测到的退化起点与车辆时间论证一致，但建立界限需在车队层面分析服务与充电之间的车辆时段分配。时间相关拥堵可通过按出发时段索引行程时间来表征，保持模型结构不变。真实充电在约80%容量以上显著放缓，分段线性近似是直接扩展方向。需求已知使模型作为离线基准，滚动时域实现是自然扩展，期末估值项适合作为控制时域外的价值函数近似。车队同质且单载客，异质电池容量和拼车是自然扩展方向。
结论部分总结：研究提出了联合路由、分配和能量管理的混合整数规划模型，同时表示五项运营特征。定理2给出充电条件：在电池容量松弛条件下，车队充电当且仅当期末估值率超过当前电价。计算实验在三个价格水平确认阈值。分时电价的价值取决于低价时段位置，六小时班次中与充电集中期重合时电费降低超过三分之一，不重合时升高，两者服务均不变。期末估值与最小荷电状态下限应对不同失效模式：下限通过禁止行程运作，估值通过奖励购买运作；对硬性终端要求下限更廉价，对捕获免费充电估值更廉价。车队规模、容忍度和需求的影响已量化：六辆车达100%调整后服务率，两时段容忍度捕获大部分增益，空驶与需求密度呈反向关系。未来方向包括分解方法或启发式以扩展至城市规模、时间相关拥堵、非线性充电、滚动时域实现及异质车队和拼车扩展。
