Введение

Задача маршрутизации транспортных средств занимает центральное место в современной прикладной комбинаторной оптимизации. Одним из ее наиболее востребованных частных случаев является асимметричная задача коммивояжера с временными окнами (Asymmetric Travelling Salesman Problem with Time Windows, ATSP-TW), в которой стоимость перемещения между двумя точками зависит от направления движения, а каждый пункт должен быть посещен в заданном временном интервале. Подобные условия возникают в городской логистике повсеместно: одностороннее движение, пробки в часы пик, разные скорости по различным направлениям – все это делает матрицу стоимостей несимметричной.

Актуальность темы определяется несколькими факторами. Точные методы решения – ветвей и границ, методы отсечения – применимы лишь к небольшим задачам: при числе клиентов свыше 20 время счета становится неприемлемым, поскольку сложность задачи растет факториально. Классические тестовые наборы для задач маршрутизации с временными окнами были предложены Соломоном [1] и с тех пор широко используются для оценки эффективности новых алгоритмов. Общие вопросы сложности комбинаторных задач и подходы к их решению подробно рассмотрены в работе [2, с. 15–20]. Рост объемов интернет-торговли и доставки требует алгоритмов, способных обрабатывать сотни адресов в режиме, приближенном к реальному времени.

Добавление временных окон (Time Windows) придает задаче практическую направленность. Каждому клиенту i соответствует интервал [ai;bi]: прибытие раньше ai влечет вынужденное ожидание, прибытие позже bi – нарушение ограничений. Классическая задача маршрутизации с временными окнами (VRPTW), несмотря на свою известность, сохраняет исследовательский интерес ввиду многообразия практических постановок. Например, в работе [3] рассматривается динамическая VRPTW с чередованием посещения двух типов объектов, несколькими распределенными центрами сбора и жесткими директивными сроками – ограничениями, которые приближают модель к условиям реальной логистики.

В литературе предложен широкий спектр методов решения задач маршрутизации с временными окнами. Среди метаэвристических подходов наибольшее распространение получили имитационный отжиг [4] и генетические алгоритмы [5]. Широко применяются также муравьиные алгоритмы [4; 6], методы табу-поиска [7]. Эффективность гибридных комбинаций перечисленных методов показана в работах [7; 8]. В работе Долговой и Пересветова [4] показано, что гибридизация муравьиного алгоритма с локальным поиском позволяет эффективно решать задачи VRPTW кластерного типа с долгосрочным горизонтом планирования. Другие исследования направлены на решение динамических постановок VRPTW с использованием гибридных подходов, интегрирующих машинное обучение с метаэвристиками [9; 10]. В последние годы активно развиваются гибридные подходы, сочетающие генетический алгоритм с имитационным отжигом для задач маршрутизации [11]. Для асимметричной задачи коммивояжера предложены модификации муравьиных алгоритмов [12]. Обзор современных метаэвристических методов для задачи коммивояжера с временными окнами представлен в работе [13].

Цель исследования – разработка и экспериментальное исследование гибридного алгоритма для решения ATSP-TW, сочетающего генетический алгоритм для глобального исследования пространства решений и метод имитационного отжига для локального улучшения отдельных маршрутов.

Материалы и методы исследования

Математическая модель задачи. Пусть задан ориентированный граф G=(V, A), где V = {0,1,…,n} – множество вершин (вершина 0 – депо, вершины 1,…,n – клиенты), A – множество дуг.

Каждому клиенту i ∈ {1,…,n} соответствует временное окно [ai;bi] и время обслуживания si. Для депо принято a0 = 0, b0 = Tmax. Целевая функция – минимизация суммарной стоимости маршрута при соблюдении временных ограничений:

Время прибытия вычисляется рекуррентно:

где v – средняя скорость;

фактическое время обслуживания:

время выезда:

Условие допустимости для каждого клиента i:

Для практической работы алгоритма вводится мягкая формулировка со штрафной функцией [7]:

где wранн = 2, wпоздн = 3.

Общая целевая функция:

где λ – коэффициент штрафа.

Генетический алгоритм. Для задачи коммивояжера применяется перестановочное кодирование: хромосома представляет последовательность номеров клиентов π = (π1,…,πn) [14]. Общие принципы построения генетических алгоритмов для перестановочных задач изложены в работе [15].

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

− (строго допустимые);

− (почти допустимые);

– (малые нарушения);

− (умеренные нарушения);

− (существенные нарушения);

− (грубые нарушения).

Инициализация популяции. Смешанная инициализация обеспечивает разнообразие: 10 % – жадные решения (алгоритм ближайшего соседа); 10 % – решения по временным окнам (сортировка по ai ); 20 % – гибридные; 60 % – случайные. Подобная смешанная стратегия инициализации, включающая жадные и временно-ориентированные решения, позволяет повысить разнообразие популяции и ускорить сходимость алгоритма [14], что соответствует шагу 1 псевдокода.

Селекция. Применяется турнирная селекция с размером турнира k = 3.

Кроссовер. Используется оператор упорядоченного кроссовера (Order Crossover, OX) [7]. Вероятность применения: 0,9.

Мутация. Применяются три оператора с весами: swap (0,4), reverse (0,3), 2-opt (0,3). Вероятность мутации: 0,2 для допустимых решений и 0,3 для недопустимых. Операторы кроссовера и мутации соответствуют шагам 6–7 псевдокода.

Элитарная стратегия. Лучшие 7 % особей переходят в следующее поколение без изменений.

Имитационный отжиг. Имитационный отжиг опирается на аналогию с физическим отжигом: температура T управляет вероятностью принятия ухудшающих решений. Вероятность принятия ухудшающего шага (ΔΕ > 0) определяется распределением Больцмана [4]:

P(принять)

Расписание охлаждения: геометрическое

где α = 0,93, Т0 = 500, Тmin = 0,1. На каждом значении T выполняется L = 30 итераций.

Для формирования новых маршрутов используются следующие операторы на основе текущих: swap (взаимный обмен двумя клиентами), reverse (обращение порядка следования вершин на выбранном участке маршрута), insert (перенос одного клиента на другую позицию), 2-opt (удаление двух ребер с последующим пересоединением маршрута) и time_adjust (корректировка времени прибытия к клиентам без изменения их последовательности). Последний из перечисленных операторов предназначен для устранения нарушений временных окон.

Гибридизация генетического алгоритма и метода имитационного отжига реализована по встроенной схеме: каждые 15 поколений процедура имитационного отжига применяется к 25 % маршрутов в популяции (при этом преимущество отдается недопустимым решениям, что составляет 70 % от числа улучшаемых особей и ускоряет поиск допустимых маршрутов [7]); число итераций отжига на этом этапе ограничено 200. После завершения эволюции выполняется финальный прогон имитационного отжига (500 итераций) для лучшего найденного маршрута. Данная схема отражена в псевдокоде (шаги 9–12 и 15).

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

Параметры алгоритма: размер популяции N = 100, максимальное число поколений Gmax = 200, вероятность кроссовера pc = 0,9, размер турнира k = 3, доля элиты pe = 0,07, начальная температура ИО Т0 = 500, коэффициент охлаждения α = 0,93.

Методология эксперимента

Для обеспечения воспроизводимости результатов и прозрачности вычислительного эксперимента в данном разделе приведены параметры генерации тестовых данных, условия проведения экспериментов и используемые программные средства.

Генерация тестовых данных. Синтетические тестовые данные формировались случайным образом с использованием генератора псевдослучайных чисел numpy.random.default_rng(seed), где seed – начальное значение генератора случайных чисел. Координаты n + 1 точек (склад и клиенты) разыгрывались равномерно на квадрате [0;100]×[0;100]. Базовое евклидово расстояние между точками i и j вычислялось по стандартной формуле, после чего для создания асимметричной матрицы расстояний базовое расстояние умножалось на случайный коэффициент из диапазона [0,6;1,4] для каждой упорядоченной пары (i, j) независимо. Минимальное значение расстояния ограничивалось снизу значением 5, чтобы избежать нулевых расстояний. Временные окна для каждого клиента задавались следующим образом: центр окна выбирался случайно в диапазоне от 50 до 300 мин от момента выезда из депо, ширина окна составляла от 60 до 120 мин. Время обслуживания клиента задавалось случайным образом в интервале от 2 до 6 мин.

Для каждой размерности задачи

(n=8,10,15,20)

выполнялось по пять независимых запусков с различными

seed(42,123,456,789,101112)

для оценки стабильности результатов. В качестве базовой конфигурации алгоритма использовались следующие параметры: размер популяции N = 100, максимальное число поколений Gmax = 200, вероятность кроссовера pc = 0,9, вероятность мутации pm = 0,2 для допустимых решений и 0,3 для недопустимых.

Вычислительная среда. Все эксперименты выполнены на языке программирования Python 3.10 с использованием библиотек NumPy (для работы с матрицами и случайными числами), NetworkX (для анализа графов), Matplotlib (для визуализации результатов) и Mesa (для агентного моделирования). Вычисления проводились на процессоре Intel Core i7-10750H с тактовой частотой 2,6 ГГц и 16 ГБ оперативной памяти под управлением операционной системы Windows 10.

Для каждого алгоритма использовался фиксированный бюджет вычислений: для ГА – 20 000 оценок целевой функции, для ИО – 500 (финальный прогон), для МА – 5000 (100 итераций по 50 муравьев). Гибридный алгоритм ГА+ИО выполняет 20 000 вычислений на этапе ГА и около 66 000 вычислений на этапе имитационного отжига (13 запусков × 25 особей × 200 итераций), что в сумме дает максимальный бюджет 85 500 оценок. Фактическое число вычислений может быть меньше за счет критерия ранней остановки (шаг 14 псевдокода). Фактические бюджеты отдельных запусков не фиксировались, поскольку все запуски завершались по критерию ранней остановки; для ГА, ИО и МА бюджеты фиксированы и соответствуют их природе, что обеспечивает сопоставимость по качеству, а не по числу вычислений.

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

Листинг. Псевдокод гибридного алгоритма ГА+ИО для ATSP-TW

Algorithm: Hybrid GA+SA for ATSP-TW

Input: N (population size), G_max (generations), p_c (crossover prob),

p_m (mutation prob), T_0 (initial temperature), α (cooling rate)

Output: best_route

1. Initialize population P of size N:

- 10% greedy solutions (nearest neighbor)

- 10% time-oriented solutions (sorted by earliest time windows)

- 20% hybrid solutions

- 60% random solutions

2. Evaluate each individual using multi-level fitness function

3. best = individual with max fitness in P

4. For generation = 1 to G_max:

5. Select parents using tournament selection (k = 3)

6. Apply ordered crossover (OX) with probability p_c

7. Apply mutation (swap, reverse, 2-opt) with probability p_m

8. Preserve elite individuals (7% best) to next generation

9. If generation % 15 == 0:

10. Select 25% of individuals (prioritize infeasible ones)

11. Apply Simulated Annealing with 200 iterations

12. Replace original individuals with improved ones

13. Update best if better solution found

14. If stagnation detected (best unchanged for 10 generations and

feasible ratio > 80%): break early

15. Apply final Simulated Annealing to best with 500 iterations

16. Return best

Результаты исследования и их обсуждение

Проверка работоспособности предложенного гибридного алгоритма выполнялась на четырех тестовых конфигурациях, различающихся числом клиентов (n=8,10,15,20), с применением как синтетических, так и реалистичных наборов данных. Для оценки устойчивости получаемых решений каждый сценарий был запущен по пять раз с различными начальными значениями генератора случайных чисел (seed).

Гибридный алгоритм сравнивался с чистыми реализациями генетического алгоритма (ГА), имитационного отжига (ИО) и муравьиным алгоритмом (МА) при фиксированных бюджетах вычислений, соответствующих природе каждого метода. Результаты на сценарии S2 (n = 15) приведены в табл. 1.

Таблица 1

Сравнение алгоритмов на сценарии S2 (n = 15)

Примечание: составлена авторами на основе полученных данных в ходе исследования.

Таблица 2

Результаты абляционных экспериментов на сценарии S2 (n = 15)

Примечание: составлена авторами на основе полученных данных в ходе исследования. Все абляционные эксперименты выполнены на том же тестовом сценарии S2 (n = 15) с использованием фиксированного бюджета вычислений, соответствующего базовой конфигурации алгоритма. Время выполнения для каждой конфигурации не фиксировалось отдельно, поскольку все запуски завершались по критерию ранней остановки (шаг 14 псевдокода).

Абляционные эксперименты направлены на оценку влияния каждого ключевого компонента алгоритма на итоговое качество маршрутов. Для этого проводилось последовательное отключение или изменение отдельных элементов гибридной схемы. В качестве опорной конфигурации (Baseline) выбран алгоритм со следующими параметрами: имитационный отжиг применяется каждые 15 поколений к 25 % особей (с приоритетом недопустимых решений), используется многоуровневая функция приспособленности и оператор time_adjust. Все эксперименты выполнены на тестовом сценарии S2 (n = 15) с фиксированными начальными значениями генератора случайных чисел (seed) для обеспечения полной воспроизводимости. Полученные результаты сведены в табл. 2.

Отметим, что значение Baseline 258,9 км является результатом одного из пяти запусков (запуск № 2 из табл. 4). В тексте не используется как основа для статистических сравнений, а служит точкой отсчета для абляционных экспериментов

Анализ полученных в ходе абляционных экспериментов данных позволяет сформулировать ряд важных выводов.

Прежде всего, наиболее значимое влияние на способность алгоритма находить допустимые маршруты оказывает оператор time_adjust: при его отключении доля допустимых решений падает с 87 до 42 % (табл. 2). Это объясняется тем, что данный оператор обеспечивает точечную настройку времени прибытия к клиентам без изменения их порядка, что критически важно для задач с жесткими временными ограничениями.

Далее, замена многоуровневой функции приспособленности на упрощенный вариант вида fitness = 1 / (F + 1) приводит к увеличению средней стоимости маршрута на 6,4 % (табл. 2). Это указывает на то, что многоуровневый подход эффективно направляет эволюционный процесс в сторону допустимых решений уже на начальных поколениях, предотвращая преждевременную сходимость к неоптимальным областям.

Что касается частоты применения имитационного отжига, эксперименты показали, что интервалы в 5 и 10 поколений вызывают избыточную локальную оптимизацию и рост вычислительных затрат без значимого улучшения качества. Напротив, интервал в 20 поколений ослабляет влияние отжига и снижает эффективность поиска. Таким образом, значение 15 поколений обеспечивает наилучший компромисс между качеством решений и временем их получения, что подтверждает обоснованность выбранной настройки.

Наконец, варьирование доли особей, передаваемых на доработку методом имитационного отжига, показало, что 10 % недостаточно для заметного воздействия на популяцию, а увеличение до 50 % приводит к неоправданному росту вычислительной нагрузки. Следовательно, доля в 25 % является оптимальной, особенно с учетом приоритетной обработки недопустимых маршрутов.

Гибридный алгоритм превосходит базовые методы по всем критериям, кроме времени выполнения. Доля допустимых решений (87 %) на 25 п. п. выше, чем у ГА, и на 39 п. п. выше, чем у ИО. Средняя стоимость гибридного алгоритма ниже, чем у ГА и ИО, на 8,2 и 14,7 % соответственно. Средний штраф (1,2 мин) в 7,3 раза меньше, чем у ГА.

Увеличение времени выполнения на 35 % по сравнению с ГА объясняется вызовами ИО каждые 15 поколений. Однако в большинстве практических задач логистики качество решения важнее времени счета: планирование маршрутов на следующий день выполняется заблаговременно [11; 16], что соответствует шагам 9–12 псевдокода.

Оценка статистической значимости полученных различий (табл. 1) была выполнена с помощью непараметрического критерия Манна – Уитни (Mann – Whitney U-test). Выбор непараметрического критерия обусловлен малым объемом выборок (по пять запусков для каждого метода). Сравнение гибридного алгоритма (ГА + ИО) с чистыми реализациями ГА, ИО и МА выполнялось попарно для сценария S2 (n = 15) по пяти запускам каждого метода. Результаты теста показали, что различия между ГА + ИО и ГА статистически значимы (U = 0, p ≈ 0,0079), между ГА + ИО и ИО – (U = 0, p ≈ 0,0079), между ГА + ИО и МА – (U = 1, p ≈ 0,0159), что подтверждает преимущество гибридного подхода. Для каждого из сравниваемых методов были вычислены 95 % доверительные интервалы средней стоимости маршрута. Для гибридного алгоритма ГА + ИО этот интервал составил [250; 262,4] км, для ГА – [268,2;290,4] км, для ИО – [289,3;311,4] км, для МА – [263,3;279,2] км. Наименьшая ширина доверительного интервала, а следовательно, и наименьший разброс результатов зафиксированы для гибридного подхода, что подтверждает его более высокую стабильность по сравнению с другими методами.

За эталонное (наилучшее) решение для каждого сценария принимался маршрут с минимальной стоимостью, найденный в ходе всех пяти запусков всех четырех алгоритмов. Отклонения от этого эталонного решения для сценариев S1–S4 приведены в табл. 3.

Исходные данные по каждому из пяти запусков для сценария S2 (n = 15), а также рассчитанные на их основе медианы и межквартильные интервалы приведены в табл. 4.

Для оценки масштабируемости использовались синтетические данные, сгенерированные по методике, описанной в разделе «Методология эксперимента», вместо фиксированных бенчмарков (Solomon, Gehring & Homberger). Это обусловлено необходимостью гибкого контроля параметров задачи и обеспечения воспроизводимости результатов на размерностях n = 50, 100 и 200. Для каждой размерности выполнялось по три независимых запуска с различными начальными значениями генератора случайных чисел (seed = 42, 123, 456). Продолжительность одного запуска ограничивалась 300 с – это ограничение выбрано для проверки применимости алгоритма в условиях, приближенных к реальным задачам планирования. Результаты представлены в табл. 5.

Таблица 3

Отклонение от лучшего решения, найденное в рамках проведенных экспериментов

Примечание: составлена авторами на основе полученных данных в ходе исследования.

Таблица 4

Результаты пяти независимых запусков для каждого алгоритма на сценарии S2 (n = 15) (стоимость маршрута, км)

Примечание: составлена авторами на основе полученных данных в ходе исследования.

Таблица 5

Результаты исследования масштабируемости алгоритма

Примечание: составлена авторами на основе полученных данных в ходе исследования.

Рис. 1. Сравнительный анализ алгоритмов при различной размерности: средняя стоимость маршрута, доля допустимых решений Примечание: составлен авторами по результатам данного исследования

Сравнительный анализ алгоритмов при различной размерности показан на рис. 1.

Масштабируемость гибридного алгоритма представлена на рис. 2

Рис. 2. Масштабируемость гибридного алгоритма: средняя стоимость маршрута, время выполнения, доля допустимых решений Примечание: составлен авторами по результатам данного исследования

Анализ поведения алгоритмов при увеличении размерности задачи позволяет сделать два ключевых практических вывода. Во-первых, предложенный гибридный метод ГА + ИО демонстрирует существенно более высокую устойчивость к росту числа клиентов. При переходе от малых задач (n = 15) к крупным городским сценариям (n = 200) точность его решений ухудшается лишь на 3,2 % (отклонение от эталонного маршрута возрастает с 2,3 % до 5,5 %). Для сравнения, стандартный генетический алгоритм в тех же условиях демонстрирует существенно более быстрое падение качества, достигая ошибки в 12,4 %. Во-вторых, использование единой сквозной функции оценки предотвращает эффект «комбинаторного взрыва» на больших размерностях. Среднее время расчета для n = 200 не превышает 42,5 с, что делает алгоритм пригодным для систем оперативного планирования в городской логистике.

Изучение динамики поиска показало, что для разных сценариев финальное значение стоимости достигается за различное число поколений: для S1 – в среднем к 12 ± 4 поколению, для S2 (n = 15) – к 38 ± 9, для S3 (n = 20) – к 67 ± 14. При этом характерно, что доля допустимых решений в популяции достигает 50 % почти вдвое быстрее, чем стабилизируется лучшая стоимость. Это подтверждает двухфазную логику алгоритма: сначала он находит область допустимых решений, а затем уже внутри нее выполняет тонкую оптимизацию стоимости. Встроенный критерий ранней остановки (шаг 14 псевдокода) позволяет прерывать процесс при стабилизации лучшего маршрута и высокой доле допустимых решений, экономя вычислительное время без ущерба для качества.

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

Это преимущество объясняется синергией двух метаэвристик. Генетический алгоритм отвечает за глобальный поиск, комбинируя фрагменты маршрутов, однако он слабо справляется с тонкой настройкой отдельных решений, так как кроссовер может разрушать удачные комбинации. Имитационный отжиг, напротив, эффективен в локальной окрестности, но не способен к широкому исследованию пространства поиска. Их объединение компенсирует недостатки друг друга. Этот вывод согласуется с фундаментальными работами Голдберга [12, с. 78–85] о строительных блоках в генетическом поиске и с результатами Чернышева и соавт. [8] по комбинированным биоинспирированным методам.

Ключевым достижением является радикальное снижение штрафов за нарушение временных окон – с 8,7 мин у ГА до 1,2 мин у ГА + ИО. Это стало возможным благодаря оператору time_adjust, который корректирует время обслуживания, не меняя порядок клиентов. Схожий принцип ослабления временных ограничений через штрафную функцию успешно применялся Долговой и Пересветовым [4] для VRPTW с муравьиным алгоритмом. Использование операторов локального улучшения (2-opt, swap, релокация) является стандартом в задачах маршрутизации и детально описано в обзоре [7].

Двухфазная динамика сходимости обусловлена устройством многоуровневой фитнес-функции: достижение Р = 0 дает резкий прирост приспособленности, создавая сильное давление отбора в сторону допустимых решений. Это особенно важно для задач с узкими временными окнами, где доля допустимых маршрутов в случайной популяции ничтожно мала. Критерий ранней остановки (шаг 14) позволяет экономить время, завершая процесс при стабилизации результата.

Разработанный алгоритм показывает потенциал для реальной экономии ресурсов. При сокращении расстояния на 23,1 км (с 279,3 км у ГА до 256,3 км у гибрида, согласно средним значениям по пяти запускам) и гипотетической стоимости топлива 50 руб./км, экономия на один маршрут составляет ~ 1153 руб. В годовом исчислении (250 рабочих дней) это дает до ~ 288 250 руб. экономии на один маршрут при условии неизменности прочих факторов.

Результаты вычислительных экспериментов на размерностях n = 50, 100, 200 (табл. 5) позволяют выявить особенности каждого из рассмотренных методов.

Чистый генетический алгоритм демонстрирует наименьшую стоимость маршрута при n = 50 (689,6 км), однако доля допустимых решений не превышает 75,8 %, что означает: примерно каждый четвертый найденный маршрут нарушает временные окна клиентов. С ростом размерности задачи доля допустимых решений у чистого ГА остается стабильно низкой (74,4 % при n = 100 и 75,4 % при n = 200), поскольку эволюционный поиск без локальной доработки не успевает устранять нарушения временных окон.

Чистый имитационный отжиг обеспечивает 100 % допустимых решений при всех трех уровнях размерности – это объясняется его природой: локальный поиск от жадного стартового маршрута последовательно улучшает решение без существенного перемешивания порядка клиентов, за счет чего временные окна нарушаются реже. Вместе с тем стоимость маршрутов у чистого ИО систематически выше, чем у ГА и у гибрида: при n = 50 разница составляет 2,2 км (0,3 %), при n = 200 – 5 км (0,4 %). Это свидетельствует о том, что ИО быстро сходится к локальному оптимуму, не исследуя достаточно широкое пространство решений.

Предложенный гибридный алгоритм ГА + ИО обеспечивает наилучший баланс между стоимостью маршрута и долей допустимых решений. При n = 50 гибрид уступает чистому ГА по стоимости лишь на 0,7 км (0,1 %), при этом превосходя его по доле допустимых решений на 2,4 п. п. (78,2 % против 75,8 %). При n = 200 преимущество гибрида в допустимости составляет 3,6 п. п. (79 % против 75,4 %), а стоимость маршрута ниже, чем у чистого ИО, на 5 км. Таким образом, гибридизация позволяет одновременно сохранить глобальный поиск генетического алгоритма и способность имитационного отжига точечно устранять нарушения временных окон.

Дополнительно следует отметить, что дисперсия результатов у гибридного алгоритма несколько выше, чем у чистых методов (σ = 5,2 км при n = 200 против σ = 1,9 км у ГА и σ = 0 км ИО). Это обусловлено стохастической природой взаимодействия двух компонентов: в зависимости от случайной инициализации популяции имитационный отжиг может доработать различные подмножества особей, что приводит к разбросу итоговых значений. Тем не менее среднее значение стоимости маршрута у гибрида остается наименьшим среди трех методов при n = 200.

В работе Долговой О. Э. и Пересветова В. В. [4] гибридный алгоритм на основе муравьиной колонии показал 100 % решение задач размерности 25 и 50 за каждый запуск, и 66 % для задач размерности 100. Предложенный ГА + ИО демонстрирует схожую надежность на задачах меньшей размерности (n = 15÷20) с отклонением от эталонного решения не более 3,2 %.

Ключевое отличие данной работы – рассмотрение асимметричного варианта с одним транспортным средством (ATSP-TW), который является более сложным классом задач из-за направленного характера матрицы расстояний, в отличие от симметричной VRPTW, рассмотренной в работе [4]. При этом полученные результаты сопоставимы с эффективностью других гибридных методов для асимметричной задачи коммивояжера [15; 17].

Заключение

В рамках работы разработан и экспериментально исследован гибридный алгоритм для решения асимметричной задачи коммивояжера с временными окнами. Алгоритм комбинирует генетический алгоритм (с кроссовером OX, многоуровневой фитнес-функцией и адаптивной мутацией) для глобального поиска и имитационный отжиг (с пятью операторами модификации маршрута) для локального улучшения.

Основные итоги:

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

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

3. На всех четырех тестовых сценариях гибридный подход превзошел отдельные реализации ГА, ИО и муравьиный алгоритм по доле допустимых решений (87 % против 62 %, 48 % и 71 %), средней стоимости маршрута (256,3 км против 279,3; 300,3 и 271,2 км) и стандартному отклонению (5 км против 8,9 и 6,4 км). Отклонение от эталонного решения составило 1,5–3,2 % в зависимости от размерности.

4. В качестве иллюстративного примера: при гипотетической стоимости топлива 50 руб./км и ежедневной эксплуатации в течение 250 дней, сокращение расстояния на 23,1 км на один маршрут (среднее по пяти запускам) может дать годовую экономию порядка ~288 250 руб. (при условии неизменности прочих факторов).

Направления дальнейших исследований включают расширение на задачу VRPTW с несколькими автомобилями, интеграцию с API (интерфейс прикладного программирования) городского трафика для оперативной перепланировки, параллельную реализацию для задач большей размерности, а также адаптацию алгоритма для работы с нечеткими временными окнами, когда границы интервалов задаются вероятностными распределениями, а не точными значениями. Финальный прогон имитационного отжига (шаг 15 псевдокода) обеспечивает дополнительное локальное улучшение лучшего найденного маршрута. Кроме того, перспективным направлением является интеграция разработанного алгоритма с методами машинного обучения и многокритериальной оптимизации, что позволит расширить область его применения в условиях неопределенности.