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

Тип разработки: 
Программа
Регистрационный номер в ФАП: 
PR15001
Дата регистрации в ФАП: 
2015-03-30
Тематическая направленность: 
Дискретная оптимизация. Исследование операций. Эвристические алгоритмы
Разработчики программы (базы данных): 
Аннотация: 

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

Назначение - нахождение приближенных решений для задачи маршрутизации транспортных средств с разделеннымы поставками (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

Версия регистрируемой программы (базы данных): 
1.0
Использованные при разработке материалы: 
Boudia M, Prins C, Reghioui M. An effective memetic algorithm with population management for the split delivery vehicle routing problem. Proc. HM–2007 — Berlin: Springer-Verl., 2007. — P. 16–30. (Lect. Notes Comp. Sci.; Vol. 4771), Glover F, Laguna M. Tabu Search. — Kluwer Academic Publishers, 1997, Mladenovi´ c N, Hansen P. Variable neighborhood search. Comput. Oper. Res. — 1997. — Vol. 24, N 11. — P. 1097–1100.
Признак доступности программы (базы данных): 
полностью свободный доступ
Требования к аппаратным и программным средствам: 

Java 6.0

Контактная информация: 
avhmel@gmail.com
ВложениеРазмер
khmelev_kochetov_sdvrp.pdf413.99 КБ
sdvrp_solver.zip1.69 МБ
sd10-064.png102.94 КБ