跳到正文
arXiv cs.AI· The Dung Bui, Ha Thu Nguyen·· 56 分钟前AI 评分29

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

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

AI 导读

作者介绍了提交给 SOICT 2026 竞赛第二轮的乘客与包裹联合运输问题求解器,这是一个单文件标准库 Python 程序,结合基于最晚到达松弛的常数时间插入检验、贪心插入、局部搜索、模拟退火接受的 ALNS,以及按出租车枚举最优路线再用分支定界求解 set-packing 的精确引擎。

正文 · 原文

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