Журнал «Современная Наука»

Russian (CIS)English (United Kingdom)
МОСКВА +7(495)-142-86-81

Формирование оптимального пути для большого количества погрузчиков на производстве

Авхадиев Рустем Ахмедович  (Аспирант, Казанский Национальный Исследовательский Технический Университет им. А.Н. Туполева - КАИ)

На сегодняшний день разработано значительное количество алгоритмов, позволяющих найти кратчайший маршрут в графе. При этом для большинства из них характерным является один недостаток - экспоненциальный рост периода работы при возрастании количества вершин графа и протяженности пути. Для практического применения в производственном планировании требуется такой алгоритм, который в кратчайшие сроки позволит оценить фактическое расстояние, которое необходимо будет преодолеть объекту при перемещении из одной точки в другую. Время расчета должно быть небольшим ввиду огромного количества вариантов, перебираемых системой при построении оптимального плана. Если применять классические алгоритмы, то придется строить граф с огромным количеством вершин, т.к. внутри производственной площадки возможно перемещение в любом направлении (в отличие от графа автомобильных дорог). Соответственно, время вычислений, которое потребуется на формирование маршрутов, будет неприемлемо большим (к моменту построения плана он будет уже неактуален). Поэтому, для решения этой задачи мы не будем использовать графы, а введем понятие препятствий и построим матрицу проходимости (используя пространственное разбиение). Формирование маршруту будем производить в два этапа: сначала последовательное обойдем все препятствия, мешающие достижению цели, а затем оптимизируем построенный маршрут “срезая углы”. В результате, мы получим маршрут, который будет хуже (длиннее) идеальных маршрутов (построенных классическими алгоритмами) на 3 - 16%, но время, затраченное на построение будет меньше в 85 - 920 раз. Конечно, погрешность достаточно высокая и, в большинстве случаев, такой маршрут будет непригоден для реального использования. Но для производственного планирования сами маршруты и не нужны, нужно лишь при подборе и сравнении большого количества вариантов примерно оценить длину маршрута и время, которое потребуется на перемещение. Если сами маршруты все же потребуются, можно применить рассматриваемый алгоритм для выбора точек старта и финиша, а затем уже выбранный маршрут улучшить классическим алгоритмом.

Ключевые слова:производственное планирование, логистика, поиск кратчайшего пути

 

Читать полный текст статьи …



Ссылка для цитирования:
Авхадиев Р. А. Формирование оптимального пути для большого количества погрузчиков на производстве // Современная наука: актуальные проблемы теории и практики. Серия: Естественные и Технические Науки. -2018. -№12. -С. 79-86.
ПРАВОВАЯ ИНФОРМАЦИЯ:
Перепечатка материалов допускается только в некоммерческих целях со ссылкой на оригинал публикации. Охраняется законами РФ. Любые нарушения закона преследуются в судебном порядке.
© ООО "Научные технологии"