Международный журнал роевого интеллекта и эволюционных вычислений

Абстрактный

Иммунологический алгоритм для комбинаторной оптимизации: задача распределения топлива как пример исследования

Павоне М*, Костанца Дж и Кутелло В.

Аннотация Задачи маршрутизации являются классическими задачами комбинаторной оптимизации, которые находят широкое применение в многочисленных промышленных и реальных сценариях. Одним из сложных вариантов задачи маршрутизации является задача распределения топлива (FDP), с которой транспортная компания сталкивается в своей повседневной деятельности. Основная деятельность транспортной топливной компании заключается в пополнении запасов всех своих магазинов, т. е. заправочных станций, вдоль географической карты с целью минимизации ее общих затрат. В этой исследовательской работе мы представляем гибридную эвристику, основанную на метафоре иммунной системы для решения FDP, которая в основном требует найти набор маршрутов как можно короче для фиксированного числа транспортных средств компании, чтобы удовлетворить несколько полученных требований клиентов. В частности, представленный иммунологический алгоритм черпает вдохновение из принципа клонального отбора, ключевыми особенностями которого являются клонирование, гипермутация и старение операторов. Такой алгоритм также характеризуется наличием (i) детерминированного подхода, основанного на алгоритме поиска в глубину (DFS), используемого в схеме назначения вершины транспортному средству, и (ii) локального оператора поиска, основанного на исследовании окрестностей. Алгоритм был протестирован на одном реальном экземпляре данных с 82 вершинами и 25 других искусственных экземплярах, взятых из эталонного теста раскраски графа DIMACS. Экспериментальные результаты, представленные в этой работе, не только доказывают надежность и эффективность разработанного алгоритма, но также показывают качество локального поиска и подхода, основанного на алгоритме DFS. Обе методологии помогают алгоритму лучше исследовать сложное пространство поиска.