链上镖师 / Chain Biaoshi
TRE 2026.9|非线性充电下电动卡车机器人协同配送问题
电动卡车携带机器人协同配送时，电池非线性充电特性如何影响路线规划？本文提出分段线性近似MILP模型与ALNS算法，系统回答了充电策略选择的关键问题。
- 核心创新：
首次为卡车-机器人协同配送引入独立电池的非线性充电模型，区分四种充电模式 - 方法亮点：
时间依赖有效不等式将CPLEX求解速度提升数千倍；ALNS同步决策算法大幅超越序贯策略 - 关键发现：
部分充电始终优于完全充电；电池容量与充电站数量是配送效率的主要瓶颈
电动卡车机器人协同配送的兴起与瓶颈
城市物流的低碳化与智能化正在并行推进。电动卡车凭借城区零排放和通行限制少的优势，逐步成为物流配送的重要工具；与此同时，机器人在末端配送中的应用也在快速增长。然而单独看两者都面临短板：电动卡车无法进入窄巷或园区等受限环境，而机器人受限于速度、续航和载重能力，难以独立承担中长途配送任务。
Yu等人在本文中提出一种电动卡车机器人协同配送模式：卡车充当移动平台运载和补给机器人，两者既可串行作业也可并行执行任务，从而扬长避短，提高整个配送系统的灵活性。这一模式比卡车-无人机配送更具落地潜力，因为地面机器人不依赖低空空域，可以更顺畅地融入现有路侧和末端配送环境。
研究聚焦于单车单机器人场景下的非线性充电函数影响，专注考察充电机制本身的核心效应，为未来多车多机器人扩展提供方法论基础。
非线性充电给车机协同带来的新难题
电池充电过程并非匀速：通常在低电量段充电快、高电量段充电慢，表现为典型的非线性函数。当卡车和机器人各自拥有独立电池时，两套非线性充电曲线交织在一起，使得系统级的能量管理变得远比单一车辆路径问题复杂。
已有研究大多假设线性充电行为，或在卡车-机器人协同建模中简化为共享电池。这些简化虽然在数学上易处理，但忽视了电池物理特性的本质。Yu等人的模型设定卡车和机器人拥有独立的电池系统，并允许在充电站进行异步、分位置的充电，更接近真实运行条件。
卡车-机器人协同配送示例：卡车沿一级路线行驶，机器人在二级路线独立服务客户。卡车在汇合节点释放或回收机器人。取自 Fig.1。
模型考虑了两种充电模式：完全充电模式下车辆每次到站必须充满；部分充电模式下可以灵活选择充电量。研究中以部分充电为主要考察对象——因为完全充电本质上是部分充电的特例——并以目标函数最小化最大完工时间（makespan）为优化目标。模型还要求卡车和机器人在同一节点汇合时必须时间同步。
数学模型：分段线性化与有效不等式
为处理非线性充电函数，研究采用分段线性（PWL）近似方法。将充电曲线剖分为L个线性段，每段由斜率、截距和电量断点刻画。通过引入辅助二元变量标识当前电量落在哪个分段，将非线性充电转化为一组混合整数线性约束，从而保持MILP结构，可用商业求解器直接求解。
非线性充电曲线的分段线性近似：以多段直线逼近真实的凸充电函数。卡车和机器人各自拥有独立的充电曲线。取自 Fig.2。
模型的核心决策变量包括三组路由变量——分别标识卡车单独行驶、机器人单独行驶、以及卡车携带机器人行驶的弧段——以及到达时间、剩余电量、充电时长等连续变量。目标函数为极小化卡车返回终点的时刻。约束体系覆盖弧流守恒、时间推进、能量流动、分段线性充电映射和子路径消除等多个维度。
模型的关键突破在于引入时间依赖有效不等式（Time-Dependent Valid Inequalities, TVIs）。两条TVIs分别为卡车和机器人提供了最小完工时间的下界约束，大幅强化了线性松弛，在后续数值实验中展现出惊人的加速效果。
算法设计：从序贯决策到同步决策
针对问题规模增大时MILP模型难以求解的现实，研究设计了两种互补的算法范式。
序列优先-充电后决（Sequence First, Charging Second, STC）：先利用启发式算法生成忽略能量约束的卡车-机器人协同路线，再在固定路线上插入充电站并确定最优充电量。
STC框架中的路线生成采用ALNS（自适应大邻域搜索）算法，包含四类破坏算子（随机/贪婪删除常规客户、随机/贪婪删除汇合节点）和六类修复算子（含regret-k插入策略），通过自适应权重机制动态选择算子组合。作为基准对比，还设计了一种基于节省值的路线构造方法（Savings-STC）。
1TSP初始路线 → 三段式转化为TSPR路线（分割-变换-合并）
2ALNS迭代破坏与修复（8类算子池，含汇合节点专用算子）
3固定路线插入充电站（先优化卡车充电，再用贪婪规则插入机器人充电）
4进一步优化：贪婪插入常规充电节点与联合充电节点
GenerateTruck-RobotRoute算法示例：TSP路线经分割、变换、合并三步转化为卡车-机器人协同路线。取自 Fig.3。
充电阶段遵循一个被形式化证明的够用即充原则：在固定路线和凸充电函数条件下，每站只充刚好够到达下一充电站（或终点）的电量即可使总充电时间最小。该命题的凸性证明为后续启发式充电策略提供了理论保证。
同步排序与充电（Simultaneous Sequencing and Charging, SAC）：在同一ALNS框架中联合决策路线排序与充电安排，打破序贯分解带来的解空间限制。SAC在原有算子池基础上新增六种充电节点相关的破坏与修复算子，并引入可行性校验与能量修复机制、节点局部搜索和结构局部搜索两道后处理。
计算实验：STC对SAC、MILP对ALNS的全面对比
实验设计了四类共80个算例：微型（7客户、3充电站）、小型（15客户、7充电站）、中型（30客户、15充电站）、大型（60客户、30充电站）。行驶距离采用曼哈顿度量，客户随机分布在网格交叉点上。使用CPLEX 12.8求解MILP（时限7200秒），ALNS每次运行200000次迭代、重复10次以保证统计可靠性。
不同实例规模的卡车与机器人参数设置。微型和小型算例刻意降低电池容量以保证充电决策成为必要条件。取自 Fig.6。
01充电方法对比：在STC框架中，精确充电方法frvcpy与传统启发式方法相比，胜率更高（55023:19789）但耗时约为46倍。由于SAC中充电操作频率极高，启发式方法更具可扩展性，后续实验统一采用。
02排序方法对比：Savings-STC仅0.28秒即可生成可行解，但ALNS-STC在约241秒内将目标值平均提升46.25%，这一计算时间在中小型应用中完全可接受。
03STC对SAC：SAC在所有迭代阶段均一致优于STC，收敛更快且终值更低。在初始1000次迭代中SAC就表现出显著的加速改进能力。
STC与SAC的目标值演化对比：(a)完整200000次迭代；(b)前1000次迭代放大。SAC始终收敛到更优目标值且收敛速度更快。取自 Fig.8。
TVIs的消融实验揭示了其决定性作用。在微型算例上，无TVIs的模型仅能求解2个实例至最优，平均gap高达63.60%；加入TVIs后全部20个实例在平均2.12秒内获得最优解——加速比超过3000倍。在小型算例上，无TVIs时9个实例根本无法找到可行解，平均gap几乎100%；加入TVIs后所有实例均获得可行解，平均gap降至27.48%。
TVIs加速效果（微型算例）
6915s → 2.12s
20个微型实例全部求至最优，加速比约3260倍
ALNS vs CPLEX
1.603 vs 1.650
ALNS平均382.6秒，CPLEX在7200秒内无法求至最优，gap约2.8%
充电策略的灵敏度分析：四种模式大比较
研究在微型实例上将四种充电模式——线性完全充电（LFC）、非线性完全充电（NFC）、线性部分充电（LPC）、非线性部分充电（NPC）——与电池容量、充电速率、充电站数量三个扰动因素进行了系统的参数敏感性分析。所有分析基于CPLEX最优解以确保公平。
实验采用的非线性充电函数及分段配置。取自 Fig.7。
结果表明两个核心规律。第一，部分充电模式全面优于完全充电：在非线性函数下NPC（1.086）优于NFC（1.228），在线性函数下LPC（1.092）优于LFC（1.162）。部分充电允许车辆只充到刚好够用的电量，避免了高SOC区间充电效率下降带来的时间浪费。
第二，线性充电近似可能产生误导。在线性假设下完全充电看起来更优（LFC 1.162 vs NFC 1.228），但一旦改用部分充电模式，非线性模型的优势就会显现（NPC 1.086 vs LPC 1.092）。这意味着真实运营中若以线性模型规划路线，可能导致实际执行时电量不足而不可行。
实例T-10在四种充电模式（LFC、LPC、NFC、NPC）下的最优路线结构与充电站决策对比。取自 Fig.C.1。
电池容量是最敏感的参数：容量减半时目标值恶化超过50%，而容量翻倍仅带来5%-12%的改善。这表明小电池迫使车辆频繁中断路径充电，严重限制路径选择的自由度。充电速率的敏感性远小于容量——速率减半或翻倍引起的变化均不到10%。充电站数量的影响也很显著：减至三分之二时目标值上升超过10%，减至三分之一时上升超过20%。
电池容量减半的影响
≥53.9%
四种模式下目标值恶化幅度均超过50%（NPC模式下为53.9%）
充电站减至1/3的影响
≥23.6%
充电站从基准减至三分之一时，四种模式下目标值恶化均超过23%
结论与管理启示
Yu等人首次为电动卡车-机器人协同配送系统引入了区分车辆类型的独立非线性充电模型，通过分段线性近似将非线性充电嵌入MILP框架，设计了时间依赖有效不等式和ALNS算法来解决模型的计算挑战。
✓MILP模型配合TVIs可在微型实例上以秒级速度获得最优解，为小规模精确规划提供了可行工具
✓ALNS同步决策算法（SAC）在大规模实例上持续优于序贯策略（STC），适合中大型实际部署场景
✓部分充电策略在非线性充电函数下始终优于完全充电，应作为实际运营的默认充电策略
✓线性充电近似的规划方案在真实非线性充电条件下可能不可行——规划时必须以真实充电曲线为输入
✓车队运营商应优先投资更大容量的电池和更密集的充电基础设施，充电速率的边际收益相对有限
研究的一个局限是假设卡车与机器人在汇合点必须同步到达。未来工作可放宽此约束，允许两者自主决定是否在充电站汇合或独立充电后在其他节点会合，这将进一步提升模型的现实适用性。多车多机器人、动态需求、随机环境也是有价值的扩展方向。
论文：Electric truck-based robot delivery problem with nonlinear charging
作者：Shaohua Yu，Tengkuo Zhu，Jakob Puchinger
期刊：Transportation Research Part E: Logistics and Transportation Review，2026
链接：https://doi.org/10.1016/j.tre.2026.104958
链上镖师、先卜交通、先卜运筹通用论文ID
保存此推文 ID，可在粉丝群内获取相关材料，未来更多功能敬请期待
先卜科技团队：常文婕、张巧巧、王一航、夏子帆、张晓乐、祁园园、张仁义
