Прислать материал
Разработка модели транспортной сети для поиска кратчайшего пути.
Логистика на предприятии с каждым годом становится все актуальнее. Грамотно построенная логистика решает важные проблемы на производственных предприятиях, позволяя уменьшить убытки компании и увеличить товарный оборот.
Важность использования логистического подхода к организации грузоперевозок заключается в том, что в условиях рыночной экономики компании могут добиться высокой прибыли и эффективной работы только при условии качественного управления и высокоорганизованного подхода. Разрабатываемые способы логистического подхода должны быть направлены на повышение эффективности работы предприятия.
Целью данной работы является создание модели транспортной сети, а также выбор алгоритма поиска кратчайшего пути удовлетворяющего следующим критериям:
- Минимальное время работы алгоритма
- Удобство реализации
- Минимальное количество требуемой памяти
В данной работе рассматриваются следующие алгоритмы поиска кратчайшего пути:
- Алгоритм Дейкстры
- Алгоритм Флойда-Уоршелла
- Алгоритм Беллмана-Форда
- Алгоритм A*
А так же способы хранения данных:
- Матрица смежности
- Описание Бержа
- Список дуг
- Список смежности
Под «оптимальностью пути» понимается минимальное время и затраты на преодоление пути. Для решения проблемы с многокритериальным выбором выполнен переход к однокритериальной задаче с использованием метода свёртки критериев. Поиск оптимального пути происходит по коэффициенту K.
\({K = \text{Price}*d_1+\text{Time}*d_2}\quad{K\to min}\)
где K-свертка критериев а d1,d2-частные критерии.Price,Time- сумма потраченная на транспортировку , и время транспортировки соответственно.
Опираясь на анализ данных алгоритмов по быстродействию и количеству требуемой памяти, основой для выполнения поставленной задачи был выбран алгоритм Дейкстры. Данный алгоритм позволяет за минимальное время найти кратчайший путь между двумя вершинами, он прост и удобен в реализации.
Результатом работы является приложение, реализующее составление оптимального маршрута движения автотранспортных средств в зависимости от времени доставки товара и затрат на транспортировку.
В результате исследования были сделаны следующие выводы:
- Самым быстрым алгоритмом нахождения кратчайшего пути выбран алгоритм Дейкстры.
- Самым емким способом хранения данных в памяти выбран список смежности.
Работа выполняется под руководством: к.т.н., доц Андреевой О. В.