Применение алгоритма стаи рыб для задачи маршрутизации транспорта с ограничением грузоподъемности

Для удобства вспомним общую постановку задачи маршрутизации транспорта.

• 1. — множество всех вершин. — «депо».
• 2. — множество n целевых вершин для посещения.
• 3. — матрица стоимостей переезда между вершинами; — стоимость переезда между вершинами и .
• 4. — величина грузоподъёмности для транспортных средств.
• 5. Множество чисел, где — строго положительная потребность в товаре для вершины .
• 6. Необходимо построить маршруты для каждого транспортного средства минимальной общей суммарной стоимости, которые начинаются и заканчиваются в депо, и каждая вершина из должна быть включена в маршрут одного и только одного транспортного средства. Сумма потребности в товаре всех вершин-клиентов каждого маршрута не должна превышать величину .

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

Процесс итеративный, где одна итерация — это один полный набор маршрутов. Количество итераций задается значением IterCount и равно:

IterCount =.

В основе идеи алгоритма лежит то, что рыбки движутся к еде, максимизируя целевую функцию. В то время, как целевая функция (суммарное расстояние) задачи стремится к минимуму. Значит, для данной задачи «еда» — это функция, обратная расстоянию.

Рыбки строят маршруты по очереди. Пока одна не закончит плавание, другая не начинает. В основе идеи реализации алгоритма лежит матрица Е, элементы которой представляют собой привлекательность ребра и корректируется после каждой итерации. Это есть аналогия социального поведения рыбки: рыбки стремятся к соседям, показавшим наилучшие результаты. Алгоритм стаи рыб для задачи маршрутизации транспорта выглядит следующим образом:

1. Для каждого ребра инициализируется матрица .

• 2. В течение IterCount количества итераций происходит:
• 2.1. Сбрасываются параметры рыбки, посещенные точки, первая рыбка помещается в .
• 2.2. Матрица не меняется.
• 2.3. Пока все клиенты не будут посещены повторяется:
• 2.3.1. Происходит поиск доступных клиентов: которых еще не посещали и которые подходят по ограничению грузоподъемности.
• 2.3.2. Если у рыбки хватает места:
• 2.3.2.1. Выбираются «лучших клиентов».

2.3.2.2. Из них с учетом вероятностей случайно выбирается следующий клиент, где вероятность (при движении из):

• 2.3.2.3. Рыбка плывет к клиенту.
• 2.3.2.4. Клиент помечается как уже посещенный.
• 2.3.2.5. Совершенная дорога записывается в массив .
• 2.3.2.6. У рыбки обновляется оставшийся свободный вес.
• 2.3.3. Если у рыбки не хватает места:
• 2.3.3.1. Рыбка плывет в депо.
• 2.3.3.2. Совершенная дорога записывается в массив .
• 2.3.3.3. Заполненный массив сохраняется в список всех дорог на этой итерации.
• 2.3.3.4. Выбирается следующая рыбка и помещается в депо.
• 2.4. Когда все клиенты посещены последняя рыбка едет в депо от последнего клиента.
• 2.5. Совершенная дорога записывается в массив .
• 2.6. Заполненный массив сохраняется в список всех дорог на этой итерации.
• 2.7. Происходит обновление матрицы :

.

где — потребность груза на вершинах этого маршрута:

3. Оптимальный маршрут составлен, ответ выводится на экран Блок-схема алгоритма представлена на рис. 6.

Рис. 6.