SOICT 2026 竞赛求解器:面向乘客与包裹联合运输问题的精确-启发式混合解法
A Hybrid Exact-Heuristic Solver for the Integrated Passenger and Parcel Transportation Problem
AI 导读
作者介绍了提交给 SOICT 2026 竞赛第二轮的乘客与包裹联合运输问题求解器,这是一个单文件标准库 Python 程序,结合基于最晚到达松弛的常数时间插入检验、贪心插入、局部搜索、模拟退火接受的 ALNS,以及按出租车枚举最优路线再用分支定界求解 set-packing 的精确引擎。
正文 · 原文
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