koz"Вестник Северо-Казахстанского университета имени Манаша Козыбаева"Bulletin of Manash Kozybayev North Kazakhstan University2958-003X2958-0048М. Қозыбаев атындағы СҚУ10.54596/2958-0048-2026-3-13-25koz-2821Research ArticleЕСТЕСТВЕННЫЕ НАУКИNATURAL SCIENCESРАСПРЕДЕЛИТЕЛЬНО-РОБАСТНАЯ ОПТИМИЗАЦИЯ ГАМИЛЬТОНОВЫХ ЦИКЛОВ НА СТОХАСТИЧЕСКИХ ГРАФАХ С ИСПОЛЬЗОВАНИЕМ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ НА БАЗЕ МЕТРИКИ ВАССЕРШТЕЙНА: ЭМПИРИЧЕСКИЕ ДАННЫЕ ИЗ АЛМАТЫ И АСТАНЫDISTRIBUTIONALLY ROBUST HAMILTONIAN CYCLE OPTIMIZATION ON STOCHASTIC GRAPHS VIA WASSERSTEIN-METRIC GENETIC ALGORITHMS: EMPIRICAL EVIDENCE FROM ALMATY AND ASTANAhttps://orcid.org/0009-0001-5951-9435ДуманА.DumanA.

Астана

Senior Lecturer, Astana IT University, School of Artificial Intelligence and Data Science

Astana

adilet.duman@gmail.comhttps://orcid.org/0000-0002-8449-1251ТолеубекМ. Т.ToleubekM. T.

Астана

Senior Lecturer, School of Artificial Intelligence and Data Science

Astana

moldir.toleubek@astanait.edu.kzhttps://orcid.org/0009-0000-2498-927XЕлемесТ. Ж.YelemesT. Zh.

Астана

Senior Lecturer, School of Artificial Intelligence and Data Science

Astana

tolkynay.yelemes@astanait.edu.kzAstana IT UniversityКазахстанAstana IT UniversityKazakhstan20263009202603 (71)1325Copyright © Думан А., Толеубек М.Т., Елемес Т.Ж., 20262026Думан А., Толеубек М.Т., Елемес Т.Ж.Duman A., Toleubek M.T., Yelemes T.Z.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestnik.ku.edu.kz/jour/article/view/2821

В данной статье представлена основанная на данных концепция распределительно-робастной оптимизации (DRO) для идентификации минимизирующих риски гамильтоновых циклов в нестационарных стохастических сетях, подверженных сильной вероятностной неопределенности. Вместо того чтобы полагаться на статические номинальные значения времени в пути, которые сильно страдают от «проклятия оптимизатора» (optimizer's curse), мы конструируем свободное от распределения множество неопределенности (ambiguity set), определяемое шаром метрики Вассерштейна 1-го типа с центром на эмпирическом распределении исторических задержек на ребрах графа. Полученная минимаксная модель оптимизации минимизирует математическое ожидание затрат на маршрутизацию в худшем случае по всем распределениям вероятностей, совместимым с историческими наблюдениями. Для решения совместной проблемы комбинаторной сложности (NP-полная задача) и нелинейных робастных целевых функций мы синтезируем данную формулировку DRO с механизмом эволюционных вычислений, управляемым точными операторами на множестве перестановок, используя оператор кроссинговера рекомбинации ребер (ER) и эргодический механизм мутации обменом (Swap Mutation). Мы оцениваем нашу модель на двух структурно контрастирующих городских сетях Казахстана: плотной, ограниченной топографией сетке Алматы и протяженной, зависящей от мостов сети Астаны. Наши эмпирические результаты показывают, что предлагаемый фреймворк предотвращает катастрофические задержки маршрутизации вне выборки (out-of-sample) за счет сохранения карт смежности ребер и превосходит классические модели стохастического программирования.

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.

Распределительно-робастная оптимизация (DRO)метрика Вассерштейназадача о гамильтоновом циклеГенетические алгоритмыDistributionally Robust Optimization (DRO)Wasserstein metricHamiltonian Cycle ProblemGenetic AlgorithmsReferencesLaporte, 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-YLaporte, 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-YEsfahani, 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-1Esfahani, 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-1Wang, 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.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.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.2383Gao, 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.2383Gu, 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.2241149Gu, 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.2241149Rahimian, H., & Mehrotra, S. (2019). Distributionally robust optimization: A review. https://doi.org/10.48550/arXiv.1908.05659Rahimian, H., & Mehrotra, S. (2019). Distributionally robust optimization: A review. https://doi.org/10.48550/arXiv.1908.05659Blanchet, 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.0936Blanchet, 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.0936Whitley, 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.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.Bertsimas, D., & Sim, M. (2004). The price of robustness. Operations Research, 52(1), 35–53. https://doi.org/10.1287/opre.1030.0065Bertsimas, D., & Sim, M. (2004). The price of robustness. Operations Research, 52(1), 35–53. https://doi.org/10.1287/opre.1030.0065Villani, C. (2009). Optimal transport: Old and new (Vol. 338). Springer Science & Business Media. https://doi.org/10.1007/978-3-540-71050-9Villani, C. (2009). Optimal transport: Old and new (Vol. 338). Springer Science & Business Media. https://doi.org/10.1007/978-3-540-71050-9Peyré, G., & Cuturi, M. (2019). Computational optimal transport. Foundations and Trends in Machine Learning, 11(5–6), 355–607. https://doi.org/10.1561/2200000073Peyré, G., & Cuturi, M. (2019). Computational optimal transport. Foundations and Trends in Machine Learning, 11(5–6), 355–607. https://doi.org/10.1561/2200000073Wiesemann, W., Kuhn, D., & Rustem, B. (2014). Distributionally robust convex optimization. Operations Research, 62(6), 1358–1376. https://doi.org/10.1287/opre.2014.1314Wiesemann, W., Kuhn, D., & Rustem, B. (2014). Distributionally robust convex optimization. Operations Research, 62(6), 1358–1376. https://doi.org/10.1287/opre.2014.1314Larrañ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:1006529012972Larrañ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:1006529012972Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. Addison-Wesley.Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. Addison-Wesley.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.102805Wang, 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.102805Zhao, 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.102751Zhao, 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.102751Shapiro, A., Dentcheva, D., & Ruszczyński, A. (2021). Lectures on stochastic programming: Modeling and theory (3rd ed.). SIAM. https://doi.org/10.1137/1.9781611976594Shapiro, A., Dentcheva, D., & Ruszczyński, A. (2021). Lectures on stochastic programming: Modeling and theory (3rd ed.). SIAM. https://doi.org/10.1137/1.9781611976594OpenStreetMap Contributors. (2025). Almaty transit network geospatial dataset. Retrieved from https://www.openstreetmap.orgOpenStreetMap Contributors. (2025). Almaty transit network geospatial dataset. Retrieved from https://www.openstreetmap.orgOpen Source Routing Machine (OSRM). (2025). Astana road network travel time latency telemetry. OSRM API Data Engine.Open Source Routing Machine (OSRM). (2025). Astana road network travel time latency telemetry. OSRM API Data Engine.

The authors declare that there are no conflicts of interest present.