cs.AINov 17, 2026

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

Authors: The Dung Bui, Ha Thu Nguyen

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

Explore similar work

CardsList
  1. Smart routes: a system for development and comparison of algorithms for solving vehicle routing problems with realistic constraints

    Aug 14, 2026Andrew Soroka, German Mikhelson, Alexander Mescheryakov +1Vehicle RoutingMetaheuristic Optimization

  2. Optimizing Nursing Care Taxi Dispatch Leveraging Integer Linear Programming Solvers and Machine Learning

    Jun 29, 2026Riku Nakao, Akihito Hiromori, Hamada Rizk +1Vehicle RoutingNeural Combinatorial Optimization

  3. Size Generalization for Diffusion Routing Solvers

    Oct 12, 2026Barak Itzchak Davidovitch, Eli Meirom, Ethan Fetaya +1Combinatorial OptimizationVehicle Routing