DISTRIBUTIONALLY ROBUST HAMILTONIAN CYCLE OPTIMIZATION ON STOCHASTIC GRAPHS VIA WASSERSTEIN-METRIC GENETIC ALGORITHMS: EMPIRICAL EVIDENCE FROM ALMATY AND ASTANA

This paper introduces a data-driven Distributionally Robust Optimization (DRO) framework to identify risk-averse Hamiltonian cycles in non-stationary stochastic networks subject to severe probabilistic uncertainty. Rather than relying on static nominal travel times, which suffer heavily from the optimizer's curse, we construct a distribution- free ambiguity set defined by a Type-1 Wasserstein metric ball centered on an empirical distribution of historical link latencies. The resulting minimax optimization model minimizes the worst-case expected routing cost over all probability distributions compatible with historical observations. To resolve the joint challenge of combinatorial hardness (NP-complete) and non-linear robust objectives, we synthesize this DRO formulation with an evolutionary computing engine governed by precise permutation set operators, deploying an Edge Recombination Crossover (ER) operator and an ergodic Swap Mutation mechanism. We evaluate our model on two structurally contrasting urban networks in Kazakhstan: the dense, topography-constrained grid of Almaty, and the expansive, bridge-dependent network of Astana. Our empirical findings demonstrate that the proposed framework prevents catastrophic out-of-sample routing delays by preserving edge adjacency maps and outperforming classical stochastic programming models.

1. Laporte, G. (1992). The traveling salesman problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(2), 231–247. https://doi.org/10.1016/0377-2217(92)90138-Y

2. Esfahani, P. M., & Kuhn, D. (2018). Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations. Mathematical Programming, 171(1), 115–166. https://doi.org/10.1007/s10107-017-1172-1

3. Wang, J., Wang, X., Yang, S., Yang, H., Zhang, X., & Gao, Z. (2021). Predicting the matching probability and the expected ride/shared distance for each dynamic ridepooling order: A mathematical modeling approach. Transportation Research Part B: Methodological, 154, 125-146.

4. Gao, R., Chen, X., & Kleywegt, A. J. (2024). Wasserstein distributionally robust optimization and variation regularization. Operations Research, 72(3), 1177–1191. https://doi.org/10.1287/opre.2022.2383

5. Gu, Y., & Wang, Y. (2024). Distributionally robust joint chance-constrained programming with Wasserstein metric. Optimization Methods and Software, 39(1), 134–168. https://doi.org/10.1080/10556788.2023.2241149

6. Rahimian, H., & Mehrotra, S. (2019). Distributionally robust optimization: A review. https://doi.org/10.48550/arXiv.1908.05659

7. Blanchet, J., & Murthy, K. (2019). Quantifying distributional model risk via optimal transport. Mathematics of Operations Research, 44(2), 565–600. https://doi.org/10.1287/moor.2018.0936

8. Whitley, D., Starkweather, T., & Fuquay, D. (1989). Scheduling problems and traveling salesmen: The genetic edge recombination operator. In Proceedings of the 3rd International Conference on Genetic Algorithms (pp. 133–140). Morgan Kaufmann Publishers.

9. Bertsimas, D., & Sim, M. (2004). The price of robustness. Operations Research, 52(1), 35–53. https://doi.org/10.1287/opre.1030.0065

10. Villani, C. (2009). Optimal transport: Old and new (Vol. 338). Springer Science & Business Media. https://doi.org/10.1007/978-3-540-71050-9

11. Peyré, G., & Cuturi, M. (2019). Computational optimal transport. Foundations and Trends in Machine Learning, 11(5–6), 355–607. https://doi.org/10.1561/2200000073

12. Wiesemann, W., Kuhn, D., & Rustem, B. (2014). Distributionally robust convex optimization. Operations Research, 62(6), 1358–1376. https://doi.org/10.1287/opre.2014.1314

13. Larrañaga, P., Kuijpers, C. M. H., Murga, R. H., Inza, I., & Dizdarevic, S. (1999). Genetic algorithms for the travelling salesman problem: A review of representations and operators. Artificial Intelligence Review, 13(2), 129–170. https://doi.org/10.1023/A:1006529012972

14. Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. Addison-Wesley.

15. Wang, Y., Zhang, L., & Li, J. (2023). Humanitarian transportation network design via two-stage distributionally robust optimization. Transportation Research Part B: Methodological, 176, 102805. https://doi.org/10.1016/j.trb.2023.102805

16. Zhao, H., Chen, L., & Xu, W. (2022). Data-driven Wasserstein distributionally robust mitigation and recovery against random supply chain disruption. Transportation Research Part E: Logistics and Transportation Review, 163, 102751. https://doi.org/10.1016/j.tre.2022.102751

17. Shapiro, A., Dentcheva, D., & Ruszczyński, A. (2021). Lectures on stochastic programming: Modeling and theory (3rd ed.). SIAM. https://doi.org/10.1137/1.9781611976594

18. OpenStreetMap Contributors. (2025). Almaty transit network geospatial dataset. Retrieved from https://www.openstreetmap.org

19. Open Source Routing Machine (OSRM). (2025). Astana road network travel time latency telemetry. OSRM API Data Engine.