ВАССЕРШТЕИН МЕТРИКАЛЫҚ ГЕНЕТИКАЛЫҚ АЛГОРИТМДЕР АРҚЫЛЫ СТОХАСТИКАЛЫҚ ГРАФТАРДАҒЫ ГАМИЛЬТОН ЦИКЛДЕРІН ТАРАЛУ БОЙЫНША ОРНЫҚТЫ ОҢТАЙЛАНДЫРУ: АЛМАТЫ ЖӘНЕ АСТАНА ҚАЛАЛАРЫНЫҢ ЭМПИРИКАЛЫҚ ДӘЛЕЛДЕМЕЛЕРІ

Бұл мақалада ықтималдық белгісіздігі жоғары деңгейдегі стационарлы емес стохастикалық желілерде тәуекелге бейім емес Г амильтон циклдерін анықтауға арналған деректерге негізделген «Таралу бойынша орнықты оңтайландыру» (DRO) фреймворкі ұсынылады. «Оңтайландырушы қарғысынан» (optimizer's curse) қатты зардап шегетін статикалық номиналды жол жүру уақыттарына сенудің орнына, біз байланыс арналарының (сілтемелердің) тарихи кідірістерінің эмпирикалық таралуына негізделген және бірінші типті Вассерштейн метрикалық шарымен анықталған, таралудан тәуелсіз белгісіздіктер жиынтығын (ambiguity set) құрамыз. Алынған минимакс оңтайландыру моделі тарихи бақылаулармен үйлесімді барлық ықтималдық үлестірімдері бойынша ең нашар жағдайдағы күтілетін маршруттау шығындарын азайтады. Комбинаторлық күрделілік (NP-толық) пен сызықтық емес робастық мақсаттардың бірлескен мәселесін шешу үшін біз бұл DRO тұжырымдамасын нақты ауыстырулар жиынтығы операторларымен басқарылатын эволюциялық есептеу жүйесімен синтездеп, қабырғаларды рекомбинациялау кроссинговері (ER) операторы мен эргодикалық ауыстыру мутациясы (Swap Mutation) механизмін қолданамыз. Біз өз моделімізді Қазақстандағы құрылымдық жағынан бір-біріне қарама-қарсы екі қалалық желіде бағалаймыз: Алматының тығыз, топографиямен шектелген торы және Астананың кең, көпірлерге тәуелді желісі. Біздің эмпирикалық нәтижелеріміз ұсынылған фреймворктің қабырғалардың іргелестік карталарын сақтау және классикалық стохастикалық бағдарламалау модельдерінен асып түсу арқылы таңдамадан тыс (out-ofsample) маршруттаудағы апатты кідірістердің алдын алатынын көрсетеді.

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.