arXiv:2604.13013cs.AImath.OC2026-04

提出双层算法解决电动车路径规划问题,效率更高且能突破现有最优解。

Bilevel Late Acceptance Hill Climbing for the Electric Capacitated Vehicle Routing Problem

  • 分阶段处理路径与充电决策,上层用代理目标加速搜索。
  • 在小规模实例接近最优,大规模实例创9项新纪录,平均提升1.07%。
  • 无需参数调整,轻量高效,适合有层级结构的大型优化问题。

本文针对电动容量车辆路径问题(E-CVRP),提出一种双层优化框架,根据搜索阶段分别或联合处理路径与充电决策。通过分析二者交互关系,在上层引入代理目标以引导搜索并加速收敛。提出双层晚期接受爬山算法(b-LAHC),包含贪婪下降、邻域探索和最终精炼三个阶段。b-LAHC采用固定参数,无需复杂自适应机制,兼具轻量性与高效性。在IEEE WCCI-2020基准测试中,其性能优于或媲美八种前沿算法。在固定评估预算下,小规模实例逼近最优解,大规模基准创下9/10项新纪录,平均改进1.07%。观察到代理目标与完整成本间存在强相关性(非普遍),验证了代理目标的有效性,同时强调必须联合求解两层,从而证实所提双层框架对具有层次结构的大规模路径优化问题的适用性与潜力。

原文摘要 · Abstract (English)

This paper tackles the Electric Capacitated Vehicle Routing Problem (E-CVRP) through a bilevel optimization framework that handles routing and charging decisions separately or jointly depending on the search stage. By analyzing their interaction, we introduce a surrogate objective at the upper level to guide the search and accelerate convergence. A bilevel Late Acceptance Hill Climbing algorithm (b-LAHC) is introduced that operates through three phases: greedy descent, neighborhood exploration, and final solution refinement. b-LAHC operates with fixed parameters, eliminating the need for complex adaptation while remaining lightweight and effective. Extensive experiments on the IEEE WCCI-2020 benchmark show that b-LAHC achieves superior or competitive performance against eight state-of-the-art algorithms. Under a fixed evaluation budget, it attains near-optimal solutions on small-scale instances and sets 9/10 new best-known results on large-scale benchmarks, improving existing records by an average of 1.07%. Moreover, the strong correlation (though not universal) observed between the surrogate objective and the complete cost justifies the use of the surrogate objective while still necessitating a joint solution of both levels, thereby validating the effectiveness of the proposed bilevel framework and highlighting its potential for efficiently solving large-scale routing problems with a hierarchical structure.

路径优化双层优化电动车启发式算法

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。