Способы решения задач маршрутизации

Рассмотрим наиболее часто используемые способы решения задачи VRP. Почти все из них — эвристические и метаэвристические методы. Точные алгоритмы не всегда дают решение за приемлемое время при больших входных данных.

Существует следующая классификация методов:

Точные методы. Осуществляется перебор, пока не будет найдено оптимальное решение.

Метод ветвей с отсечением.

Метод ветвей и границ.

Эвристические алгоритмы. Осуществляется поиск по пространству решений за приемлемое время.

Конструктивные алгоритмы Механизм сбережений.

Метод, основанный на совпадениях.

Эвристики улучшения многих маршрутов.

Двухфазные методы. Состоят из 2 этапов. На первом вершины организуются в группы, на втором по каждой группе строится маршрут.

The Petal Algorithm.

The Sweep Algorithm.

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

Ant Algorithms.

Bee Algorithms.

Simulated Annealing.

Genetic Algorithms.

Tabu Search.

The adaptative memory procedure.

Granular Tabu.

В данной работе уделяется внимание именно метаэвристическим подходам в решении VRP. Рассматриваются алгоритмы роевого интеллекта (Swarm Intelligence): муравьиный, пчелиный, роевой и меметический алгоритмы. В этих алгоритмах каждый агент (муравей, пчела и др.) по отдельности достаточно просто взаимодействует с другими и окружающей средой, однако в целом система таких агентов обладает разумным поведением.

Глава 2.