Multi-Relation Knowledge Graph-Guided Transformer with Objective-Aware Route Selection for Vehicle Routing Problems with Time Windows

Vehicle routing problems with time windows require route construction methods that can reason jointly about spatial distance, vehicle capacity, service time, and customer time windows. Recent neural combinatorial optimization studies show that Transformer and graph-based models can learn routing policies, but many models still rely mainly on node features and do not expose which routing relations are responsible for feasibility and route quality. This study proposes a multi-relation knowledge graph guided Transformer framework for the vehicle routing problem with time windows. For each instance, a pairwise knowledge graph is built from spatial, temporal, capacity, slack, and depot identity relations. These relation vectors are projected into head-specific attention biases inside a pointer-style Transformer, while a feasibility mask enforces capacity and time window constraints during decoding. The framework is trained by imitation from OR-Tools teacher routes and evaluated on the 56 Solomon benchmark instances and on synthetic Solomon-style extensions. The original Transformer baseline decoded feasible routes for 54 of 56 Solomon instances, whereas the full knowledge graph guided model decoded feasible routes for all 56 instances. Additional controlled AM style, POMO style multistart, and edge-aware Transformer baselines improve route quality gaps on feasible instances but still leave one Solomon instance infeasible, highlighting the proposed framework's feasibility-oriented role. On three 120 instance synthetic runs, objective-aware route selection over relation-specialized models reached a mean feasible rate of 0.997 and reduced the mean distance gap by 125.418 Solomon coordinate distance units compared with the relation-free Transformer baseline. The contribution is therefore a diagnostic and extensible framework that integrates explicit routing knowledge into neural attention, evaluates relation ablations, and combines specialized route candidates according to the target operational objective.

@article{Kosolsombat2026,
  title     = {Multi-Relation Knowledge Graph-Guided Transformer with Objective-Aware Route Selection for Vehicle Routing Problems with Time Windows},
  journal   = {International Journal of Advanced Computer Science and Applications},
  volume    = {17},
  number    = {6},
  year      = {2026},
  publisher = {The Science and Information Organization},
  author    = {Somkiat Kosolsombat and Chiabwoot Ratanavilisagul},
  doi       = {10.14569/IJACSA.2026.0170665},
  url       = {https://doi.org/10.14569/IJACSA.2026.0170665}
}