跳到正文
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)。

正文 · 原文

View PDF HTML (experimental)

Abstract:We describe the solver we submitted to the second round of the SOICT 2026 contest on the Integrated Passenger and Parcel Transportation problem, a selective pickup-and-delivery routing problem with time windows, open routes and heterogeneous taxis. The solver is a single-file, standard-library Python program that combines (i) a constant-time insertion test based on latest-arrival slack, (ii) greedy insertion, local search and an Adaptive Large Neighborhood Search (ALNS) with simulated-annealing acceptance, and (iii) an exact route-selection engine that enumerates, for every taxi, the best feasible route for each request set and then solves the resulting set-packing problem by branch-and-bound strengthened with route-based large neighborhood search, Lagrangian bounds and reduced-cost fixing. The engine is chosen automatically from the instance size, and an independent verifier and a watchdog guarantee that a valid answer is always printed. On the official evaluation (38 scored instances, 5-minute limit) the solver obtained a total benefit of 487,237, finished every run within 277 s and used at most 279 MB; 28 of the 38 instances terminated well before the limit.
Comments: 4 pages, 2 figures, 3 tables. Technical Report for the SOICT 2026 Student Contest
Subjects: Artificial Intelligence (cs.AI)
Cite as: arXiv:2611.22043 [cs.AI]
  (or arXiv:2611.22043v1 [cs.AI] for this version)
  https://doi.org/10.48550/arXiv.2611.22043

arXiv-issued DOI via DataCite (pending registration)

Submission history

From: The Dung Bui [view email]
[v1] Tue, 17 Nov 2026 01:10:18 UTC (10 KB)

来源:arXiv cs.AI · arxiv.org