Тема выпускной квалификационной работы: «Построение гибких маршрутов в динамической транспортной сети с учетом грузоподъемности транспортного средства». Предметом исследования является алгоритм построения маршрута в динамической транспортной сети, а целью – построение гибких маршрутов в динамической транспортной сети для n транспортных средств с ограниченной грузоподъемностью так, чтобы покрыть максимальное количество заявок за заданное время при условии, что заявки появляются случайно при прохождении маршрута. В работе использовались методы математического моделирования, математической статистики, элементы теории графов и объектно-ориентированного программирования. Был разработан алгоритм решения задачи на языке JAVA на базе двухфазного (кластерного) алгоритма. Для кластеризации использовалась модификация алгоритма сбалансированного дихотомического деления вершин, построение маршрутов производилось с применением эвристики ближайшего соседа, а поиск маршрута между двумя вершинами осуществлялся алгоритмом Astar. Решение поставленной задачи позволяет оптимизировать составление маршрутов развозки пассажиров из организации, доставки товаров со склада по торговым точками или обслуживание электрических самокатов. Эксперименты проводились на дорожной сети города Санкт-Петербург.

The subject of the graduate qualification work is «Building flexible routes in a dynamic transport network, taking into account the carrying capacity of the vehicle». The subject of the research is an algorithm for building a route in a dynamic transport network, and the goal is to build flexible routes in a dynamic transport network for n vehicles with limited load capacity so as to cover the maximum number of requests for a given time, provided that requests appear randomly when passing the route. We used methods of mathematical modeling, mathematical statistics, elements of graph theory and object-oriented programming. An algorithm for solving the problem in JAVA was developed based on a two-phase (cluster) algorithm. For clustering, a modification of the balanced dichotomous vertex division algorithm was used, routes were constructed using the nearest neighbor heuristic, and a route search between two vertices was performed using the Astar algorithm. The solution to this problem allows you to optimize the preparation of routes for transporting passengers from the organization, delivering goods from a warehouse to retail outlets, or servicing electric scooters. The experiments were carried out on the road network of the city of Saint Petersburg.