|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Алгоритм решения транспортной задачи с ограничениямидипломная работа (Бакалавр)
- Научный руководитель: Сазонов В.В.
- Автор: Крачковский Владимир Васильевич
- Тип: Бакалавр
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Год защиты: 2018
- Аннотация: В выпускной квалификационной работе рассмотрена транспортная задача с ограничением на вместимость грузовика, в англоязычной литературе эта задача носит название Capacitated Vehicle Routing Problem (CVRP). Решаемая задача относится к классу NP трудных. Задача эта не является новой и достаточно хорошо изучена, есть алгоритмы, основанные на линейном программировании, динамическом программировании, методов муравьиных колоний и другие эвристические подходы. Предложен алгоритм, основанный на последовательном объединении двух маршрутов в 1, если данное объединение дает выигрыш. Алгоритм является «жадным» и весьма прост в реализации. Было проведено сравнение результатов работы алгоритмы с известными лучшими результатами (known best results).
- Добавил в систему: Савчук Артем Маркович