A Hybrid Exact-Heuristic Solver for the Integrated Passenger and Parcel Transportation Problem
Organizations: University of Engineering and Technology, Vietnam National University, Hanoi (UET-VNU)
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.
Figures & tables
| Time limit / watchdog / polish | 270 s / 290 s / s |
|---|---|
| Enumeration budgets | 10%, 16%, 12% of 270 s |
| Route cap; state limits | 260,000; 6M (30M if restricted) |
| Pool reduction (limit, ) | 40,000 routes; |
| ALNS | |
| Temperature | mean revenue |
| Weights; restart to best | every 60 its., ; 4000 its. |
| Run time | # | Benefit | Share | Max s | Max MB |
|---|---|---|---|---|---|
| s | 22 | 61,588 | 12.6% | 4.0 | 184.5 |
| 5–61 s | 6 | 96,773 | 19.9% | 60.9 | 250.8 |
| s (limit) | 10 | 328,876 | 67.5% | 276.9 | 278.6 |
| Total | 38 | 487,237 | 100% | 276.9 | 278.6 |
Vehicle Routing
Vehicle routing studies how to assign and sequence trips for fleets while meeting capacity, time, energy, and service constraints.
See all 146 papers