公交时刻表优化:一种基于自适应大邻域搜索的混合启发式方法及新型算子权重倒数平方规则

《European Journal of Operational Research》:Optimisation of Bus Timetables: An Adaptive Large Neighbourhood Search-based Matheuristic with a Novel Operator Weight

【字体: 大 中 小 】 时间:2026年02月02日 来源:European Journal of Operational Research 7.0

编辑推荐:

  本研究针对带时间依赖行程时间与需求数据的非周期公交时刻表问题,开发了一种基于自适应大邻域搜索(ALNS)的混合启发式(matheuristic)。研究人员提出两类修复算子:一类为混合整数线性规划(MILP)算子,在被破坏算子定义的决策变量子集上求解受限问题;另

  
本研究针对带时间依赖行程时间与需求数据的非周期公交时刻表问题,开发了一种基于自适应大邻域搜索(ALNS)的混合启发式(matheuristic)。研究人员提出两类修复算子:一类为混合整数线性规划(MILP)算子,在被破坏算子定义的决策变量子集上求解受限问题;另一类为启发式算子,对公交车发车时间进行平移。两类算子的混合使用带来了不同执行时间算子间计算时间分配的挑战。研究人员注意到现有算子选择机制可能向慢速算子分配过多时间,故建立一种称为倒数平方规则(inverse-square rule)的新公式。在哥本哈根路网部分实例上的计算结果表明:(1) 采用所提倒数平方规则的ALNS框架在所有算例上均优于精确解法;(2) 同时使用快速启发式修复算子与慢速MILP修复算子显著优于单独使用任一算子;(3) 平均而言,倒数平方规则表现优于其他反比例幂公式。
研究背景方面,构建同步良好的公共交通时刻表对提升乘客体验与吸引客流至关重要,但既有研究多聚焦单一体验成分(如换乘时间或首站等待时间),且多数忽略车辆行程时间的时间依赖性。Lee等人(2022)提出的非周期公交时刻表模型虽同时纳入时间依赖行程时间与首候车、车内、换乘及期望到达时间等多重成本,却受限于一小时优化时域而难以覆盖更长运营时段。为此,研究人员将自适应大邻域搜索(ALNS)这一已在车辆路径、调度与铁路时刻表等领域验证有效的元启发式引入该问题,并进一步将其扩展为混合启发式(matheuristic)——在算子集中同时放入纯启发式修复算子与调用混合整数线性规划(MILP)求解器的修复算子。由于两类算子单次迭代耗时差异巨大,传统ALNS权重更新忽视耗时或简单按“每秒改进量”惩罚慢速算子,会导致慢速算子占用过多时间预算。研究人员指出该直觉陷阱:选中某算子本身决定了该轮时间消耗,故以“改进量/秒”反推权重会使最慢算子被过度选中。针对此,研究人员给出三项核心贡献:开发求解Lee等人(2022)模型的ALNS并在哥本哈根部分路网实证中超越精确法;设计启发式与MILP两类修复算子并证明混合使用优于单独使用;提出倒数平方规则(inverse-square rule)更新算子选择权重,证明该机制使运行时间按“改进量/计算时间”之比成比例分配,且平均优于其他反比例幂公式。论文发表于《European Journal of Operational Research》。
关键技术方法上,研究人员依托Lee等人(2022)的非周期公交时刻表MILP模型(目标为最小化乘客加权出行成本,含首候车时间yg、车内时间vg、换乘时间pg、早到惩罚eg与晚到惩罚lg,决策变量为各车次在各站到达arsk、出发drsk与停站时间ursk),构建ALNS框架:破坏算子移除部分车次发车时间,修复算子分两类——MILP修复算子在破坏决定的变量子空间上求解受限MILP,启发式修复算子依据需求与间隔平移车次时间。算子权重更新采用所提倒数平方规则,以改进量除以计算时间平方进行奖励,替代文献中“改进量/秒”或“1/计算时间”类公式。实验数据取自哥本哈根公交网络部分线路及Movia提供的确定性时间依赖行程时间与分组乘客需求。
研究结果部分,引言(1. Introduction)指出强调单站换乘可能损害首候车与车内体验,且既有时间依赖模型多只考虑单一成本;研究人员因此动机将ALNS用于Lee等人(2022)模型以覆盖更长时段。文献综述(2. Literature review)分四节回顾公交时刻表(含周期/非周期、同步与集成优化)、ALNS在公共交通时刻表(既往均用于铁路)、修复算子分类(插入/平移/改属性)、ALNS算子选择(多数忽略耗时,少数按1/耗时惩罚但落入直觉陷阱)。模型(3. Model)重述Lee等人(2022)问题:路网R与S,车次k∈Kr,决策变量arsk、drsk、ursk,乘客组g∈G按固定路径Sg与Rg出行,转移机会集Ψ,时变行程时间trs(i)τ,目标式(1)为min∑g∈G qg(cYyg+cVvg+cPpg+cEeg+cLlg)。ALNS算法(4. ALNS algorithm)详述破坏—修复循环、两类修复算子构造、及倒数平方规则权重更新证明(运行时间分配正比于改进量/计算时间)。数值研究(5. Numerical studies)在哥本哈根部分路网多算例显示:ALNS加倒数平方规则全面优于精确法;启发式+MILP混合修复优于任一单独;倒数平方规则平均优于逆一次方、逆三次方等公式。结论(6. Conclusion)总结三贡献,指出未来可纳入容量约束、周期时刻表与实时扰动。
讨论与结论翻译:研究人员表明,所提ALNS混合启发式在非周期、时间依赖公交时刻表问题上可解更长时域且解质优于精确法;启发式与MILP修复算子互补——前者探索快、后者局部精修——混合使用带来一致增益;倒数平方规则通过理论证明与计算验证,纠正了既有“按每秒改进分配权重”导致的慢算子时间侵占偏差,使时间预算按改进效率成比例分布,平均表现超越其他反比例幂形式。该工作首次将ALNS用于公交(而非铁路)时刻表,并给出带求解器的混合启发式在ALNS中权重更新的严谨时间感知方案,对元启发式算子管理具有方法学外溢价值。
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号