Глоссарий ИИ
Полный словарь искусственного интеллекта
Проблема маршрутизации транспортных средств (VRP)
Обобщение задачи коммивояжера, которое заключается в разработке набора оптимальных маршрутов для парка транспортных средств для обслуживания набора клиентов, часто с учетом ограничений по вместимости и времени.
Эвристика ближайшего соседа
Жадный алгоритм, который строит решение задачи коммивояжера, начиная с одного города и систематически посещая ближайший непосещенный город, пока все города не будут посещены.
Алгоритм Кларка и Райта
Эвристика построения для VRP, которая итеративно объединяет начальные маршруты для минимизации общего расстояния, основываясь на экономии расстояния, достигаемой при объединении двух маршрутов.
Имитация отжига (Simulated Annealing)
Метаэвристика, вдохновленная процессом охлаждения металлов, которая с убывающей вероятностью принимает менее хорошие решения, чтобы избежать локальных минимумов и сойтись к квазиоптимальному решению.
Оптимизация муравьиной колонией (ACO)
Метаэвристика, вдохновленная поведением муравьев, которые используют феромоны для отметки путей, позволяя алгоритму постепенно обнаруживать кратчайшие маршруты в графе.
Метод ветвей и границ с отсечениями (Branch and Cut)
Точный метод комбинаторной оптимизации, который объединяет неявное перечисление (метод ветвей и границ) с техниками отсечения (плоскости) для сжатия линейной релаксации задачи и ускорения решения.
Временное окно (Time Window)
Ограничение в VRP, которое определяет интервал времени, в течение которого должен быть обслужен клиент, добавляя временную сложность к оптимизации логистических маршрутов.
VRP с временными окнами (VRPTW)
Вариант VRP, где у каждого клиента есть временное окно обслуживания, что делает задачу гораздо более сложной, так как необходимо оптимизировать как расстояние, так и соблюдение временных ограничений.
Метод вставки
Семейство эвристик для VRP, которое строит решение путем постепенного добавления клиентов в существующие маршруты с минимизацией увеличения общей стоимости, часто используя критерии, такие как предельная стоимость вставки.
Линейная релаксация
Техника, используемая в точных методах, где ограничения целочисленности задачи комбинаторной оптимизации ослабляются для получения нижней границы оптимального значения целевой функции.
2-opt
Оператор локального поиска для TSP, который улучшает решение путем замены двух ребер для разрыва и повторного подключения тура, устраняя пересечения и уменьшая общую длину пути.
Or-opt
Улучшение 2-opt, которое перемещает цепочку из одного, двух или трех клиентов в другую позицию в туре, предлагая большую гибкость для улучшения решений маршрутизации.
Периодическая задача маршрутизации транспортных средств (PVRP)
Расширение VRP, где планирование осуществляется на многодневном временном горизонте, некоторые клиенты требуют посещений с определенными частотами (например: раз в неделю).
Матрица затрат
Фундаментальная структура данных, которая хранит затраты (расстояние, время и т.д.) между каждой парой точек в задаче маршрутизации, служащая основой для вычислений оптимизации.