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

Авхадиев Рустем Ахмедович

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

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