Постановка задачи маршрутизации транспорта и анализ алгоритмов её решения

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