• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

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

ФИО студента: Гревцов Сергей Валерьевич

Руководитель: Бацын Михаил Владимирович

Кампус/факультет: Факультет информатики, математики и компьютерных наук (Нижний Новгород)

Программа: Прикладная математика и информатика (Бакалавриат)

Оценка: 7

Год защиты: 2018

Проблема маршрутизации транспорта (VRP) является классической задачей логистики, главной задачей которой является нахождение минимального по цене набора маршрутов из централизованного склада. Специальный случаем данной задачи является ситуация, когда сеть представлена в виде дерева (TVRP). Подобные древоподобные структуры могут быть найдены в сельской местности, реках, рядом с магистралями и когда цена строительства и обслуживания новых дорог значительно превышает цену доставку по существующим. В начале эвристика создаёт по отдельному маршрута для каждого листа дерева, после чего работает с данными маршрутами, пытаясь дополнить их предшестующими вершинами или соединить с другими подобными маршрутами. Когда все существующие маршруты сталкиваются с ограничением вместимости и не могут быть дополнены никакими новыми вершинами, но ещё не все вершины в дереве обслужены, для каждой необслуженной вершины создаются новые маршруты. После чего проводится работа с этими новыми маршрутами, пытаясь объединить их между собой и уже существовашими. Для нахождения путей по дереву используется поиск в ширину. Алгоритм работает с маршрутами параллельно для того чтобы сделать маршруты более сбалансированными между собой. Здесь показано две стратегии работы с маршрутами, обе параррельные. Для работы каждый раз берётся тот маршрут, чья ещё не проверенная для добавления вершина является наиболее удалённой от склада, по сравнению с другими маршрутами. Первый подход работает с маршрутом пока он не будет изменён (добавлена новая вершина / соединён с другим маршрутом) или заполнен (нет возможных изменений). Второй подход работает с маршрутом пока не будет изменён он или хотя бы его добавочная информация (например была проверена, но не добавлена вершина, или была неудавшаяся попытка слияния). Эвристический алгоритм был реализован на сетях, сгенерированных с элементом случайности.

Текст работы (работа добавлена 28 мая 2018 г.)

Выпускные квалификационные работы (ВКР) в НИУ ВШЭ выполняют все студенты в соответствии с университетским Положением и Правилами, определенными каждой образовательной программой.

Аннотации всех ВКР в обязательном порядке публикуются в свободном доступе на корпоративном портале НИУ ВШЭ.

Полный текст ВКР размещается в свободном доступе на портале НИУ ВШЭ только при наличии согласия студента – автора (правообладателя) работы либо, в случае выполнения работы коллективом студентов, при наличии согласия всех соавторов (правообладателей) работы. ВКР после размещения на портале НИУ ВШЭ приобретает статус электронной публикации.

ВКР являются объектами авторских прав, на их использование распространяются ограничения, предусмотренные законодательством Российской Федерации об интеллектуальной собственности.

В случае использования ВКР, в том числе путем цитирования, указание имени автора и источника заимствования обязательно.

Реестр дипломов НИУ ВШЭ