I-PASS: Interpretable Position-Aware Statistical-based Swap Operator

Introduction: The swap operator in Simulated Annealing (SA) typically exchanges nodes randomly without knowledge of the route structure. This randomness wastes computation and slows convergence in Vehicle Routing Problems (VRPs). To incorporate spatial information, we propose an Interpretable Position-Aware Statistical-Based Swap Operator (I-PASS) that makes every swap decision spatially informed.

Method: Instead of random pairwise swaps, I-PASS, as an interpretable mechanism, employs geometric median analysis. For a candidate pair from routes A and B, it measures each node's distance to the coordinate-wise median of the remaining nodes in its current route, compared with the median of the destination route. Processed symmetrically, the swap is accepted only if it decreases individual distances to the medians or reduces the total distance across both routes, thereby optimizing spatial clustering.

Results: Experiments were run across 30 clustered VRP instances (20 customer nodes, 4 vehicles, 600 SA iterations). Results confirm that I-PASS significantly outperforms random-swap SA. The mean total route cost was reduced from 305.96 to 217.80, representing a 28.82% improvement. Additionally, the standard deviation dropped from 62.75 to 42.01, indicating more consistent solutions. Convergence curves show that I-PASS reaches lower cost values faster and maintains this advantage throughout the search.

Conclusion: Embedding spatial reasoning into a swap operator delivers substantial and consistent gains over blind random selection. I-PASS improves solution quality, reduces variance, and naturally clusters nodes into geographically coherent routes without needing a separate clustering step.