From Feasibility to Multi-Criteria Optimization in Service Team Transport Scheduling: A Declarative and Metaheuristic Perspective

Abstract

This paper investigates the scalability of a multi-criteria optimization for the Service Team Transport Scheduling (STTS) problem, minimizing total travel time, maximum vehicle worktime, and total vehicle engagement time. The mathematical model of the problem is provided. A simplified problem representation and two graph-based representations along with problem properties are formulated. Using these properties, we propose two complementary frameworks: a declarative Constraint Optimization Problem (COP) solved via Gurobi, and a metaheuristic Tabu Search (TS) incorporating a Constraint Satisfaction Problem (CSP) and an auxiliary greedy method for obtaining initial feasible solutions. Additionally, the population-based NSGA-II algorithm is implemented as an evolutionary baseline. The solving methods are evaluated under a strict 300-second operational limit using 280 realistic instances. The results reveal clear tractability thresholds. The COP solver obtains high-quality Pareto fronts but experiences a combinatorial collapse beyond 8 customer locations, hitting a 0% success rate for instances with size 15 or more. Conversely, the proposed hybrid CSP-TS framework demonstrate high robustness, maintaining a 90–100% operational success rate up to 50 locations. Specifically, the expansive large-neighborhood TS variant excels at medium scales (14–40 locations), while the compact small-neighborhood TS variant achieves the highest Hypervolume Indicator (HVI) at large scales (45 or more locations). Pure population-based approaches like NSGA-II are consistently outperformed by the specialized local search neighborhood structures. These quantitative findings define scale-aware algorithmic boundaries essential for real-time decision support systems.