РАСПРЕДЕЛИТЕЛЬНО-РОБАСТНАЯ ОПТИМИЗАЦИЯ ГАМИЛЬТОНОВЫХ ЦИКЛОВ НА СТОХАСТИЧЕСКИХ ГРАФАХ С ИСПОЛЬЗОВАНИЕМ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ НА БАЗЕ МЕТРИКИ ВАССЕРШТЕЙНА: ЭМПИРИЧЕСКИЕ ДАННЫЕ ИЗ АЛМАТЫ И АСТАНЫ

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

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.