跳到正文
arXiv cs.AI· The Dung Bui, Ha Thu Nguyen·· 4 小时前AI 评分18

面向乘客与包裹联合运输问题的混合精确-启发式求解器

A Hybrid Exact-Heuristic Solver for the Integrated Passenger and Parcel Transportation Problem

AI 导读

针对 SOICT 2026 第二轮乘客与包裹联合运输问题,作者提交了一个单文件、仅用标准库的 Python 求解器,融合基于最晚到达松弛的常数时间插入测试、贪心插入与模拟退火接受准则的 ALNS,以及按实例规模自动启用的精确路径选择引擎(分支定界结合路径大邻域搜索、拉格朗日界与 reduced-cost fixing)。

正文 · AI 翻译

查看 PDF HTML(实验性)

摘要:我们描述了提交至 SOICT 2026 竞赛第二轮关于集成乘客与包裹运输问题的求解器,该问题是一个带时间窗、开放路线和异构出租车的选择性取送货路径问题。该求解器是一个单文件、仅使用标准库的 Python 程序,它结合了 (i) 基于最晚到达松弛量的常数时间插入测试,(ii) 贪心插入、局部搜索以及采用模拟退火接受准则的自适应大邻域搜索(ALNS),以及 (iii) 一个精确路线选择引擎,该引擎为每辆出租车枚举每个请求集合的最佳可行路线,然后通过基于路线的大邻域搜索、拉格朗日界和缩减成本固定强化后的分支定界来求解所得的集合划分问题。引擎根据实例规模自动选择,独立的验证器与看门狗保证始终输出有效答案。在官方评估中(38 个计分实例,5 分钟时限),求解器获得总收益 487,237,每次运行均在 277 秒内完成,最多使用 279 MB 内存;38 个实例中有 28 个在时限之前很早就终止了。
注释: 4 页,2 幅图,3 张表。SOICT 2026 学生竞赛技术报告
主题: 人工智能(cs.AI)
引用为: arXiv:2611.22043 [cs.AI]
  (或 arXiv:2611.22043v1 [cs.AI] 用于此版本)
  https://doi.org/10.48550/arXiv.2611.22043

由 DataCite 颁发的 arXiv DOI(待注册)

提交历史

来自:The Dung Bui [查看电子邮件]
[v1] 2026 年 11 月 17 日星期二 01:10:18 UTC(10 KB)

来源:arXiv cs.AI · arxiv.org