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

Аннотация

Задача маршрутизации – одна из широко известных задач комбинаторной оптимизации. Она состоит в отыскании оптимального множества маршрутов для транспортных средств с целью однократного обслуживания определенного множества клиентов. В данной работе исследуется подвид задачи маршрутизации – задача маршрутизации с ограничением по грузоподъемности, в которой каждое транспортное средство имеет свою грузоподъемность. Задача является NP-трудной, поэтому вместо точных алгоритмов решения исследуются только эвристические алгоритмы, позволяющие получить приближенные решения за полиномиальное время. Задача работы – провести экспериментальное исследование точности решения различных конструктивных эвристик, так как в других источниках не было найдено подобных сравнений.  В большинстве случаев, лидером можно признать эвристику «Clarke and Wright Savings», однако существуют отдельные наборы данных, описанные в тексте, на которых лучше работают другие алгоритмы. Также в статье рассмотрены и другие интересные факты. В целом работа проделана с целью дальнейшего использования полученных знаний в экспериментальном исследовании наиболее известных и современных метаэвристических алгоритмов решения задачи маршрутизации с ограничением по грузоподъемности, для которых будут получены предварительные решения на основе выявленных лучших эвристических методов конструирования маршрута.