Решение транспортной задачи при помощи генетического алгоритма как часть SOA

Решение транспортной задачи при помощи генетического алгоритма как часть SOA

Приветствую уважаемое Хабрасообщество!

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

Формулировка задачи

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

Например – необходимо спланировать доставку бутылей воды по городу, известны потребности каждого заказчика, грузоподъёмность транспортных средств и расстояния между точками.

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

Генетический алгоритм

Описание

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

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

Представление хромосом

Каждая хромосома есть вариант решения проблемы и представлена в виде массива массивов, где каждый вложенный массив представляет один маршрут (1 ходку автомобиля). Каждый элемент массива — это заказчик, которому необходимо доставить груз:

Все маршруты явно начинаются со склада и неявно им заканчиваются.

Скрещивания

Имеем 2 типа скрещиваний – случайный (Random Crossover) и однородный (Uniform Crossover)
Случайное скрещивание – произвольная часть произвольного маршрута от родителя 1 помещается в наилучшее место вставки для родителя 2. Наилучшее место вставки – то которое дает наименьшую длину.

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

Мутации

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

Локальная оптимизация

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

Фитнесс функция

Приспособленность (качество) каждой хромосомы считается по формуле:
Фитнесс = общее расстояние + штраф за перегруз * перегруз + штраф за недогруз * недогруз

Поддержание уникальности маршрутов

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

Конец вычислений

Алгоритм завершает вычисления по достижению максимального количества эпох или при отсутствии улучшений за определенный % эпох

Результаты работы алгоритма

Ниже приведены результаты работы алгоритма на подмножестве стандартного набора задач. Первая цифра в названии проблемы – число точек, вторая – мин количество машин. B-n31-k5 – 31 точка при 5 машинах.
Результаты работы на 8 ядерном AMD (8350):

Результаты работы на всех тестовых данных находятся на странице проекта.

Архитектура решения

Решение написано на C# и состоит из ряда сервисов, баз данных и очередей:

Стек технологий:
1. .NET 4.5 / C# / WCF / WinService
2. Queue: RabbitMQ
3. DB: MongoDB
4. DI container: Autofac
5. Unit tests: MS Test / Rhino Mocks / Fluent assertions

.NET специфичный опыт которым я считаю нужным поделится:
1. В часто обращаемых участках кода не используйте свойств, а просто публичные переменные
2. Массивы зачастую быстрее списков (List) и словарей (Dictionary) даже при реализации в них операций вставки внутрь и удаления элементов

Следующие шаги

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

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

Гугл содержит массу публикаций о решении задачи средствами генетических (и не только) алгоритмов. Вот названия некоторых из них:
1. Solving the Vehicle Routing Problem with Genetic Algorithms
2. A hybrid algorithm for the Vehicle Routing Problem with Time Windows
3. A Route-directed Hybrid Genetic Approach for the Vehicle Routing Problem with Time Windows