Аннотация:В выпускной квалификационной работе рассмотрена транспортная задача с ограничением на вместимость грузовика, в англоязычной литературе эта задача носит название Capacitated Vehicle Routing Problem (CVRP). Решаемая задача относится к классу NP трудных. Задача эта не является новой и достаточно хорошо изучена, есть алгоритмы, основанные на линейном программировании, динамическом программировании, методов муравьиных колоний и другие эвристические подходы.
Предложен алгоритм, основанный на последовательном объединении двух маршрутов в 1, если данное объединение дает выигрыш. Алгоритм является «жадным» и весьма прост в реализации. Было проведено сравнение результатов работы алгоритмы с известными лучшими результатами (known best results).