Analysis of mathematical formulations of capacitated vehicle routing problem and methods for their solution

Задача маршрутизации является одной из важнейших NP-трудных задач комбинаторной оптимизации. Она заключается в нахождении множества оптимальных замкнутых маршрутов с целью развозки товаров клиентам, используя ограниченное количество транспортных средств. В данной работе анализируется особый вид задачи маршрутизации - задача маршрутизации с ограничением по грузоподъемности, в которой у каждого транспортного средства есть лимит на максимальный вес (объем) груза. Целью данной работы является составление классификации различных типов задачи маршрутизации с ограничением по грузоподъемности. В первой части работы дана общая информация о проблеме, указаны рамки, в которых проводилось исследование - не рассматривались динамические и стохастические подвиды задачи маршрутизации. Во второй части представлена впервые предложенная авторами работы математическая постановка трех классических вариантов задачи маршрутизации с ограничением по грузоподъемности. В третьей части работы представлен список подклассов рассматриваемой задачи, включающий описание, математические модели для некоторых задач, а также наиболее перспективные метаэвристики, с помощью которых можно решать поставленную задачу. В четвертой части приведено упоминание об алгоритме LKH-3, способном решать некоторые подклассы задач с меньшим отклонением от оптимального значения по сравнению с другими алгоритмами. В заключении, приведена таблица, объединяющая все методы, описанные ранее, и схема с взаимосвязями задачи маршрутизации с ограничением по грузоподъемности и её подклассами. В будущем авторы работы планируют расширить классификацию, включив в неё подклассы стохастических и динамических вариантов данной проблемы.