Гибридный локальный поиск для задачи маршрутизации транспортных средств с распределенными поставками

Область применения - логистика, транспортные задачи.

Назначение - нахождение приближенных решений для задачи маршрутизации транспортных средств с разделеннымы поставками (Split Delivery Vehicle Routing Problem)

Постановка задачи. В задаче маршрутизации транспортных средств неограниченный автопарк одинаковых транспортных средств расположен на складе. Каждое транспортное средство имеет фиксированную вместимость. Маршрут транспортного средства должен начинаться и заканчиваться на складе. Есть множество клиентов, рассположенных на плоскости. Каждый клиент имеет заданный запрос на доставку. Задача заключается в поиске набора маршрутов транспортных средств с минимальной суммарной длиной маршрутов при условии, что все клиенты будут обслужены. В задаче маршрутизации транспортных средств с разделенным обслуживанием (SDVRP) каждый клиент может быть посещен несколько раз, и поставки по его запросу могут быть разделены между транспортными средствами.

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

Функциональные возможности - программа позволяет находить приближенные решения с малой погрешностью для задачи маршрутизации транспортных средств с разделенными поставками. При размерности до 288 клиентов алгоритм находит решение с погрешностью не более 3%. Ограничение на размерность задачи отсутствует, но при большей размерности  требуется больше временных ресурсов.

Инструментальные средства создания - Java 6.0, Eclipse IDE.

Исходный код находится в прикрепленном архиве. Для запуска работы необходимо установить Eclipse или любую другую IDE для работы с Java. Главный класс находится в пакете "tests". Один из них для запуска одного из примеров, другой для вычисления всего множества примеров. Также в приложении есть рисунок, в котором приведен результат работы программы для размерности в 64 клиента. Красным выделены клиенты с разделенной поставкой.

Алгоритм опубликован в статье:  Alexey Khmelev, Yury Kochetov. A Hybrid Local Search for the Split Delivery Vehicle Routing Problem. International Journal Of Artificial Intelligence 2015, Vol 13, 1