Регистрация / Вход
Прислать материал

Разработка модели транспортной сети для поиска кратчайшего пути.

ФИО
Костенко Роман Юрьевич
Электронная почта
e194d3rasetys@gmail.com
Номинация
Информационные технологии
Институт
Институт информационных технологий и автоматизированных систем управления (ИТАСУ)
Кафедра
Инженерной кибернетики
ФИО научного руководителя
доцент к.т.н., Андреева О. В.
Академическая группа
ММ-13-1
Наименование тезиса
Разработка модели транспортной сети для поиска кратчайшего пути.
Тезис

Логистика на предприятии с каждым годом становится все актуальнее. Грамотно построенная логистика решает важные проблемы на производственных предприятиях, позволяя уменьшить убытки компании и увеличить товарный оборот.

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

Целью данной работы является создание модели транспортной сети, а также   выбор алгоритма поиска кратчайшего пути удовлетворяющего следующим критериям:

  1. Минимальное время работы алгоритма
  2. Удобство реализации
  3. Минимальное количество требуемой памяти

В данной работе рассматриваются следующие алгоритмы поиска кратчайшего пути:

А так же способы хранения данных:

 Под «оптимальностью пути» понимается  минимальное время и затраты на преодоление  пути. Для решения проблемы с многокритериальным выбором выполнен переход к однокритериальной задаче с использованием метода свёртки критериев. Поиск оптимального пути происходит по коэффициенту K.

 \({K = \text{Price}*d_1+\text{Time}*d_2}\quad{K\to min}\)

где K-свертка критериев а d1,d2-частные критерии.Price,Time- сумма потраченная на транспортировку , и время транспортировки соответственно.

Опираясь на анализ данных алгоритмов по быстродействию и количеству требуемой памяти, основой для выполнения поставленной задачи был выбран алгоритм Дейкстры. Данный алгоритм позволяет за минимальное время найти кратчайший путь между двумя вершинами, он прост и удобен в реализации.

Результатом работы является приложение, реализующее составление оптимального маршрута движения автотранспортных средств в зависимости от времени доставки товара и затрат на транспортировку.

В результате исследования были сделаны  следующие выводы:

  •  Самым быстрым алгоритмом нахождения кратчайшего пути выбран алгоритм Дейкстры.
  •  Самым емким способом хранения данных в памяти выбран список смежности.

Работа выполняется под руководством: к.т.н., доц Андреевой О. В.