ПРИМЕНЕНИЕ АЛГОРИТМА ХЕЛДА-КАРПА В СИСТЕМЕ ОПТИМИЗАЦИИ МАРШРУТОВ ГОРОДСКОЙ ДОСТАВКИ

​APPLICATION OF THE HELD–KARP ALGORITHM IN AN URBAN DELIVERY ROUTE OPTIMIZATION SYSTEM

Stepanov Ivan Sergeevich

Master's student, Department of Information Technologies and Computing Systems, Moscow State University of Technology "Stankin",

Russia, Moscow

АННОТАЦИЯ

В статье рассматривается применение алгоритма Хелда-Карпа в системе оптимизации маршрутов городской доставки. Описывается представление дорожной сети в виде графовой модели, формирование матрицы кратчайших расстояний и использование динамического программирования для поиска оптимального маршрута. Приводится пример построения маршрута доставки на основе графовой модели дорожной сети.

ABSTRACT

The article discusses the application of the Held–Karp algorithm in an urban delivery route optimization system. The representation of the road network as a graph model, the formation of a shortest-path distance matrix, and the use of dynamic programming for optimal route search are described. An example of delivery route construction based on a graph model of the road network is presented.

Ключевые слова: маршрутизация; задача коммивояжёра; алгоритм Хелда-Карпа; графовые модели; городская логистика; оптимизация маршрутов.

Keywords: routing; traveling salesman problem; Held–Karp algorithm; graph models; urban logistics; route optimization.

В современных системах доставки важной задачей является автоматизированное построение маршрутных листов транспортных средств. Эффективная маршрутизация позволяет сократить время доставки, уменьшить транспортные издержки и повысить качество логистических процессов [1].

Для решения задач маршрутизации широко применяются графовые модели дорожной сети, в которых дорожная инфраструктура представляется в виде графа. Использование графовых структур позволяет учитывать особенности реальной дорожной сети при вычислении маршрутов между точками доставки.

Одним из точных методов решения задачи коммивояжёра является алгоритм Хелда-Карпа, основанный на методе динамического программирования [4]. Алгоритм позволяет находить маршрут минимальной стоимости путём последовательного вычисления оптимальных путей для различных подмножеств вершин.

Целью работы является исследование применения алгоритма Хелда-Карпа в системе автоматизированного формирования маршрутных листов доставки.

В системах маршрутизации дорожная сеть представляется в виде взвешенного графа:

                                          (1)

где V — множество вершин графа, а E — множество рёбер, соединяющих вершины. Вершины графа соответствуют дорожным узлам, таким как перекрёстки или точки изменения направления движения, а рёбра представляют участки дорог между ними. В качестве веса рёбер может использоваться расстояние между вершинами или предполагаемое время движения.

Использование графовой модели позволяет учитывать структуру дорожной сети при вычислении маршрутов доставки. Для поиска маршрутов между точками применяются алгоритмы поиска кратчайшего пути, результаты работы которых используются при формировании матрицы расстояний для алгоритма оптимизации маршрута [6].

Для применения алгоритма Хелда-Карпа выполняется предварительная подготовка входных данных. Пользователь задаёт точки доставки, после чего система выполняет их привязку к графовой модели дорожной сети. Для каждой точки определяется ближайшая вершина графа, используемая при вычислении маршрутов.

На рисунке 1 представлен пример представления дорожной сети в виде графовой модели, где А – точка начала маршрута, B-F – точки, которые необходимо посетить, G – точка окончания маршрута.

Рисунок 1. Представления дорожной сети в виде графа

После определения точек доставки формируется матрица кратчайших расстояний между всеми вершинами маршрута. Для поиска кратчайших путей используется алгоритм Дейкстры, позволяющий находить минимальное расстояние между вершинами взвешенного графа. Пример матрицы кратчайших расстояний представлен в таблице 1.

Таблица 1.

Матрица кратчайших расстояний между точками маршрута

Помимо матрицы кратчайших расстояний, система сохраняет информацию о последовательности вершин, образующих кратчайший путь между точками маршрута. Это позволяет после завершения работы алгоритма Хелда-Карпа восстановить полный маршрут на графовой модели дорожной сети и выполнить его визуализацию на карте.

Для хранения маршрутов используются структуры данных, содержащие последовательности вершин графа для каждой пары точек доставки. Пример некоторых кратчайших маршрутов представлен в таблице 2.

Таблица 2.

Сопоставление маршрута кратчайшему пути

После формирования матрицы расстояний выполняется поиск оптимального порядка посещения точек доставки. Для решения данной задачи применяется алгоритм Хелда-Карпа, предназначенный для точного решения задачи коммивояжёра методом динамического программирования.

Задача коммивояжёра заключается в определении маршрута минимальной стоимости, проходящего через все заданные точки ровно один раз [2]. В контексте системы доставки данная задача позволяет определить оптимальный порядок посещения точек маршрута с минимальной суммарной длиной пути.

Алгоритм Хелда-Карпа основан на последовательном вычислении оптимальных маршрутов для различных подмножеств точек. Для каждого состояния сохраняется минимальная стоимость маршрута, проходящего через определённый набор вершин и заканчивающегося в текущей точке [5].

Рекуррентное соотношение алгоритма имеет следующий вид:

                          (2)

где: S — множество посещённых вершин, j — текущая вершина маршрута, i — предыдущая вершина, d(i,j)— расстояние между вершинами, C(S,j)— минимальная стоимость маршрута.

В программной реализации алгоритма для хранения промежуточных состояний динамического программирования используются таблицы или словари, содержащие комбинации множеств посещённых вершин и текущих точек маршрута.

На рисунке 2 представлена блок-схема последовательности работы алгоритма Хелда-Карпа в системе маршрутизации.

Рисунок 2. Последовательность работы алгоритма Хелда-Карпа

Вычислительная сложность алгоритма составляет: O(n²⋅2ⁿ), где n – количество точек маршрута.

Экспоненциальный рост вычислительной сложности ограничивает применение алгоритма для задач с большим количеством точек доставки. На практике алгоритм Хелда-Карпа целесообразно использовать для маршрутов с относительно небольшим числом точек, где требуется получение точного оптимального решения [3].

Для демонстрации работы алгоритма был рассмотрен пример построения маршрута доставки для набора точек, расположенных в городской дорожной сети. После формирования матрицы расстояний система выполняет поиск оптимального маршрута и определяет порядок посещения точек доставки.

В рассматриваемом примере были использованы точки маршрута: A — склад, начальная точка маршрута, B, C, D, E, F — точки доставки, G — стоянка, конечная точка маршрута.

В результате работы алгоритма был получен следующий оптимальный маршрут: A→E→D→B→C→F→G. Полученный маршрут обеспечивает минимальную суммарную длину пути среди всех возможных вариантов обхода заданных точек.

После завершения вычислений результат передаётся клиентскому приложению для визуализации на интерактивной карте (Рис.3.). Пользователь получает последовательность посещения точек доставки и графическое отображение маршрута.

Рисунок 3.  Пример отображения оптимального маршрута на карте

Использование алгоритма Хелда-Карпа в составе системы маршрутизации позволяет автоматизировать процесс построения маршрутов доставки и получать точные оптимальные решения для задач с небольшим количеством точек маршрута.

В работе рассмотрено применение алгоритма Хелда-Карпа в системе оптимизации маршрутов городской доставки. Использование алгоритма динамического программирования позволяет автоматизировать процесс построения оптимального порядка посещения точек маршрута и находить решения с минимальной суммарной длиной пути.

Применение графовой модели дорожной сети обеспечивает возможность выполнения расчётов с учётом структуры реальной городской инфраструктуры. Использование матрицы кратчайших расстояний между точками доставки позволяет интегрировать алгоритм маршрутизации в программные системы логистики и доставки.

Проведённый пример построения маршрута показал возможность практического применения алгоритма Хелда-Карпа в задачах городской доставки. При этом экспоненциальная вычислительная сложность алгоритма ограничивает его использование задачами с относительно небольшим количеством точек маршрута, где требуется получение точного оптимального решения.

Список литературы:

1. Ерзин А. И. Задачи маршрутизации : учеб. пособие / А. И. Ерзин, Ю. А. Кочетов. – Новосибирск : РИЦ НГУ, 2014. – 95 с. – URL: https://e-lib.nsu.ru/dsweb/Get/Resource-496/page001.pdf/en/info (дата обращения: 20.05.2026).
2. Меламед И. И. Задача коммивояжера. Вопросы теории / И. И. Меламед, С. И. Сергеев, И. Х. Сигал // Автоматика и телемеханика. – 1989. – № 9. – С. 3–33. – URL: https://www.mathnet.ru/at6414 (дата обращения: 20.05.2026).
3. Меламед И. И. Задача коммивояжера. Точные методы / И. И. Меламед, С. И. Сергеев, И. Х. Сигал // Автоматика и телемеханика. – 1989. – № 10. – С. 3–29. – URL: https://www.mathnet.ru/at6433 (дата обращения: 20.05.2026).
4. Хелд М. Применение динамического программирования к задачам упорядочения / М. Хелд, Р. М. Карп // Кибернетический сборник. – М. : Мир, 1964. – Т. 9. – С. 202–218.
5. Канцедал С. А. Динамическое программирование для задачи коммивояжера / С. А. Канцедал, М. В. Костикова // Автоматизированные системы управления и приборы автоматики. – 2014. – № 166. – С. 15–20. – URL: https://cyberleninka.ru/article/n/dinamicheskoe-programmirovanie-dlya-zadachi-kommivoyazhera (дата обращения: 20.05.2026).
6. Вардомацкая Е. Ю. Оптимизация маршрута с использованием теории графов в пакетах прикладных программ / Е. Ю. Вардомацкая, В. Л. Шарстнев, Я. А. Алексеева // Вестник Витебского государственного технологического университета. – 2016. – № 1 (30). – С. 130–139. – URL: https://rep.vstu.by/bitstream/handle/123456789/672/VGTU_30_130-139.pdf (дата обращения: 20.05.2026).