Некоторые точные и эвристические алгоритмы для задач маршрутизации с одним транспортным средством, вывозом и доставкой грузов

Аннотация

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