DCAST: Decoupled Constraint Activation Signature Tokenization for Multi-Task Neural Multi-Objective Vehicle Routing Problems

Neural multi-objective combinatorial optimization (NMOCO) has attracted increasing attentions in solving multi-objective vehicle routing problems (MOVRPs) by their fast Pareto-front approximation capability. However, existing NMOCO solvers are typically trained for a single MOVRP variant, which severely restricts their applications in real-world industry problems with diverse characteristics. Therefore, this paper concentrates on developing multi-task NMOCO solvers for MOVRPs. First, we reformulate 16 single-objective VRP variants to bi-objective VRPs. Subsequently, we adapt two state-of-the-art single-task NMOCO solvers, WE-CA and POCCO, to the multi-task setting by extending their node representations and incorporating dynamic routing attributes into their context embeddings, yielding W-T and P-T, respectively. We also adapt MVMoE, a representative multi-task single-objective NCO solver, to the multi-task NMOCO settings by embedding the preference vector as a pseudo-node and using it to modulate node representations via FiLM, yielding MOM, and further strengthening of its transferred model with a decoder-side nonlinear expert layer yields the MOM-M. Furthermore, building on MOM-M, we propose the Decoupled Constraint Activation Signature Tokenization (DCAST), which factorizes a five-dimensional binary constraint activation signature into five learnable constraint identity embeddings and two shared learnable activation-state embeddings to construct state-aware constraint tokens that are jointly encoded with node and preference embeddings. Lastly, we extend the above solvers with a size-agnostic training paradigm to further boost their cross-size generalization. Extensive experiments on the reformulated MOVRPs demonstrate the superiority of the multi-task paradigms over their original single-task counterparts in terms of both cross-problem and cross-size versatility, as well as the superiority of the proposed DCAST among multi-task solvers. The source code is available at: https://github.com/DFSDarren/DCAST.