ОПТИМИЗАЦИЯ ПЕРЕМЕЩЕНИЙ АВТОМОБИЛЬНОГО ТРАНСПОРТА, УЧАСТВУЮЩЕГО В ПРОИЗВОДСТВЕННОМ ПРОЦЕССЕ КРУПНЫХ МАШИНОСТРОИТЕЛЬНЫХ ПРЕДПРИЯТИЙ

Полный текст

Как известно [1-4], производственный процесс - это регламентированное взаимодействие потоков материалов, энергии и информации в целях производства материальной продукции. Определяющую роль играют потоки основных и вспомогательных материалов, их движение и преобразование; потоки энергии и информации обеспечивают эти процессы, делают их возможными. Все взаимодействия в рамках производственного процесса являются технологическими. Для нормального функционирования производственного процесса нужна развитая система транспортирования и хранения заготовок, полуфабрикатов и готовых изделий. Хотя для транспортировки заготовок, полуфабрикатов и готовых изделий между цехами и складами чаще применяют различного рода конвейеры, на крупных предприятиях цеха и складские помещения часто значительно разнесены в пространстве, и для транспортировки заготовок, полуфабрикатов и готовых изделий на них используют автомобильную технику [3, 4]. Как отмечается [3], любое время функционирования, когда технологический процесс прерывается, является бесполезно затраченным, потерянным для основного функционального назначения. Поэтому время на перемещение заготовок, полуфабрикатов и готовых изделий между цехами и складами на предприятии является бесполезно затраченным и увеличивает себестоимость выпускаемой продукции. Кроме того правильный выбор средств транспортирования, загрузки, накопления и складирования изделий непосредственно влияет на надежность, производительность и эксплуатационные затраты производственных систем. [5]. Но не всегда возможно отказаться от использования автомобильной техники в производственном процессе, в частности для транспортировки заготовок, полуфабрикатов и готовых изделий между цехами и складами. Так, например, у ОАО ХК «Коломенский завод» площадь территории производственной зоны составляет 124 га. Производственный комплекс состоит из металлургического, заготовительного, сварочно-сборочного, механосборочного производств. На территории завода расположено 28 цехов основного производства и 15 цехов вспомогательного производства (некоторые из них размещены на значительных расстояниях один от другого). Автотранспортный цех является вспомогательным цехом машиностроительного предприятия и выполняет следующие вспомогательные функции: • перевозка людей по объектам предприятия и по производственным заданиям, доставка персонала к рабочим местам; • перевозка материалов для нужд различных цехов предприятия по его территории, а также перевозка отработанного материала в цеха переработки и переплавки; • перевозка готовых изделий предприятия к местам назначений (складам, площадкам для хранения и т.п.) и др. [6]. При невозможности отказаться от использования автомобилей в движении материальных потоков во внутрипроизводственных логистических системах, как указывается в [7], необходимо оптимизировать работу технологического транспорта (в данном случае автомобильного). Постановка задачи Оптимизация перемещений автомобильного транспорта при перевозках заготовок, полуфабрикатов и готовых изделий между цехами и складами позволит сократить время технологических процессов изготовления изделий, выпускаемых машиностроительным предприятием, а следовательно, оптимизировать его производственный процесс. Таким образом, поиск оптимального маршрута перемещения автомобильного транспорта по территории предприятия является весьма актуальной задачей. Для решения этой задачи необходимо сократить время на перемещения автомобильного транспорта между цехами, между цехами и складами и т.п. Задача нахождения оптимального маршрута относится к области комбинаторной оптимизации, а также рассматривается в теории исследования операций и известна под общим названием как «задача коммивояжера» [8-15]. В «классической» формулировке задачи коммивояжер пытается определить кратчайший маршрут для одноразового посещения n городов. Как указывается в [9, 11, 15], эта задача является задачей о назначениях с дополнительными ограничениями, которые гарантируют исключение из оптимального решения неполных замкнутых маршрутов. В задаче коммивояжера замкнутый маршрут, проходящий через каждый пункт только один раз, называется циклом; цикл, проходящий через все пункты, называется полным, в противном случае - частичным или подциклом. Постановка задачи следующая [11]. Коммивояжер должен выйти из первого города, посетить по одному разу в неизвестном порядке города 2, 3, 4,... , n и вернуться в первый город. Расстояния между городами известны. Требуется определить порядок обхода городов, чтобы замкнутый путь (тур) коммивояжера был кратчайшим. (1) Если города перенумерованы числами у'еТ = (1, 2, 3,...,n), то тур коммивояжера может быть описан циклической перестановкой t = (Л, Л,.-, Л), причем все jn - разные номера; повторяющийся в начале и в конце j1, показывает, что перестановка зациклена. Расстояния между парами вершин С., образуют матрицу ||С||. Задача состоит в том, чтобы найти такой тур t, чтобы минимизировать функционал: L = L (t) = iyC. -- min. V / ЛЛ+1 k=1 Относительно математической формулировки задачи необходимо знать следующее: (2) j Э T:Cj > 0;C„ : СО j jj (последнее равенство означает запрет на петли в туре), симметричными, т.е. для всех , j: (3) В постановке C j означали расстояния, поэтому они должны быть неотрицательными, т.е. для всех: C = C j j (4) C и удовлетворять неравенству треугольника, т.е. для всех: C + C В математической постановке говорится о произвольной матрице. Сделано это потому, что имеется много прикладных задач, которые описываются основной моделью, но всем условиям (2)-(4) не удовлетворяют. Особенно часто нарушается условие (3) (например, если С.. - не расстояние, а плата за проезд: часто туда билет стоит одну цену, а обратно - другую). Поэтому различают два варианта задачи: симметричную задачу, когда условие (3) выполнено, и несимметричную - в противном случае. Условия (2)-(4) по умолчанию считают выполненными. Второе замечание касается числа всех возможных туров. В несимметричной задаче все туры t = j2,..., jn) и t = jn,.., j2, j1) имеют разную длину и должны учитываться оба. Разных туров тогда будет (n-1)!. Общая постановка задачи и большинство ее частных случаев, относится к классу TVP-сложных задач (от англ. non-deterministic polynomial). Поэтому алгоритмы решения этой задачи делятся на точные и приближенные [8-11, 16, 17]. Все точные алгоритмы фактически представляют собой оптимизированный полный перебор вариантов. В некоторых случаях эти алгоритмы достаточно быстро находят решения, но в общем случае приходится перебирать все n! циклов. Задача коммивояжера относится к числу трансвычислительных: уже при относительно небольшом числе городов (66 и более) она не может быть решена методом перебора вариантов никакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет [8-11, 16, 17]. Все эффективные (сокращающие полный перебор) методы решения задачи коммивояжера - методы эвристические. В большинстве эвристических методов находится не самый эффективный маршрут, а его приближенное решение - базовый маршрут. На следующем этапе это приближенное решение улучшают. Для решения задачи коммивояжера используют различные группы простейших методов: полный и случайный перебор (метод Монте-Карло), жадный, деревянный алгоритмы, метод ближайшего соседа, метод включения ближайшего города, метод самого дешевого включения, метод минимального остовного дерева. К приближенным алгоритмам решения задачи, широко применяющимся в практике решения инженерных задач, относятся: генетический, метод имитации отжига, Прима-Эйлера, «иди в ближний» (модифицированный жадный алгоритм) [11, 16, 17]. Также получили распространение различные модификации более эффективных методов, таких как метод ветвей и границ (метод Литтла), модифицированный метод Литтла, метод генетических алгоритмов, а также алгоритм муравьиных колоний [10, 11, 16-18]. К методам улучшения базового маршрута можно отнести: метод перестановок; метод разворота петель; комбинированный метод [15]. В [11] был проведен сравнительный анализ: простейших методов (жадного, деревянного алгоритмов и метод случайного перебора (метод Монте-Карло)); методов улучшения базисных маршрутов, полученных на основе простейших методов (перестановок, разворота петель, комбинированного); приближенных алгоритмов (генетического, метода имитации отжига, Прима-Эйлера, модифицированного жадного алгоритма); алгоритма на основе метода ветвей и границ (Литтла) и алгоритма муравьиных колоний. Для проведения сравнительного анализа и последующего выбора наиболее эффективного метода для решения задачи коммивояжера в [11] был разработаны алгоритм и программа на языке Паскаль в программной среде Delphi 7. Программа проводит решение задачи коммивояжера на основе следующих методов и алгоритмов: жадного, жадного модифицированного, деревянного, Монте-Карло, муравьиных колоний, Литтла. При этом маршрут может быть рассчитан не менее чем для 100 вершин (точек) маршрута, но при наличии соответствующих вычислительных ресурсов. Реально на практике не требуется осуществлять обход более 40 точек маршрута, поэтому для анализа расчеты проводились именно для 40 точек. Оценка временных параметров работы алгоритмов проводилась на персональном компьютере Intel Core i5-3470 3.2GHz с ОЗУ 4Gb и с операционной системой Windows 8.1 (x64). Результаты моделирования на основе созданной программы приведены на рисунке 1. Лучший результат показал алгоритм Литтла. При малом количестве вершин (до 15) он входит в число лучших, а при дальнейшем увеличении количества вершин выходит на первое место, но требует больше вычислительных ресурсов, чем другие алгоритмы. Алгоритм муравьиных колоний также входит в число лучших алгоритмов. Модификация жадного алгоритма оказалась в среднем на 37 % лучше жадного алгоритма, но при этом выполняется в несколько раз дольше. Алгоритм Монте-Карло показал худшие результаты, поэтому использовать его на практике не рекомендуется. Время, затрачиваемое на выполнение решения по жадному алгоритму, близко к нулю, поэтому и время расчетов по жадному модифицированному алгоритму также очень мало. Время, затрачиваемое на решение задачи коммивояжера на основе алгоритмов: Монте-Карло, деревянного, жадного и жадного модифицированного, примерно одинаково. При этом время на решение задачи с помощью алгоритмов Литтла и муравьиных колоний значительно больше по сравнению со временем расчета уже перечисленных алгоритмов; в частности по алгоритму муравьиных колоний для 40 вершин оно составляет почти 0,023 с. Но по сути дела эти временные показатели также незначительные, т.к. не превышают даже 1 с. Поэтому, если количество вершин (точек) маршрута невелико (менее 15) и вычислительные мощности ограничены и оптимальность решения не очень критична, то рекомендуется использовать модифицированную версию жадного алгоритма. В том случае когда, вычислительные ресурсы не ограничены, количество вершин (точек, которые необходимо пройти при выполнении маршрута) значительно (выше 15), то для решения задачи лучше использовать алгоритм Литтла или алгоритм муравьиных колоний. Кроме того, применение алгоритмов Литтла и муравьиных колоний не требует дальнейшего улучшения полученных с помощью этих алгоритмов маршрутов. Следовательно, для решения задачи оптимизации перемещений автомобильного транспорта при участии его в производственном процессе крупных машиностроительных предприятий необходимо использовать либо алгоритм Литтла, либо алгоритм муравьиных колоний. Кратко опишем их. Алгоритм Литтла [18, 19], основан на методе ветвей и границ и строит дерево решений для перебора вариантов маршрута (циклов обхода) с отсечением. Отсекаются такие частично построенные маршруты, у которых оценка снизу длины маршрута больше или равна длине ранее построенного полного наилучшего маршрута. При построении оценки снизу на каждом этапе работы алгоритма матрица расстояний подвергается такому преобразованию с трудоемкостью порядка O(n2), чтобы в каждой ее строке и каждом столбце появился хотя бы один нуль. Более точную оценку снизу можно получать, решая задачу о назначениях на матрице расстояний за время O(n3), при этом улучшается эффективность отсечений в дереве решений. Одним из методов искусственного интеллекта является алгоритм муравьиных колоний (муравьиный алгоритм) Марко Дориго [10]. Основная идея алгоритма подсмотрена в природе и имитирует движение колонии муравьев. По форме этот алгоритм похож на жадный и в некоторой степени является его обобщением. Если в алгоритме ближайшего соседа выбор дальнейшего пути производится исходя из минимального расстояния до очередной вершины, то здесь выбором управляет случайная функция, направляющая движение от текущего положения с большей вероятностью в вершину j, в которой наибольшее значение некоторой функции (где i - номер вершины, в которой производится выбор, к - номер муравья, движущегося по дугам графа). Во время движения создается список пройденных вершин, что позволяет избежать преждевременного зацикливания. В [10] приj lj ij ,k ведена функция, управляющая переходом из данной вер0ины i в вер0ину j: (5) i i где х j количество феромона (pheromon), оставленного муравьями на дуге [i, j]; r\.. -величина, обратная весу (длине) дуги [i, j]; а, р - эмпирические коэффициенты. Функция P.Jk подсказывает муравью номер вер0ины j, в которую он должен направиться. В знаменателе стоит нормирующий коэффициент - такой, что 0 < P.jk < 1. Индекс m в сумме пробегает по всем непройденным вер0инам, смежным с i. В реальности муравей оставляет след (феромон) во время прохождения пути, и чем чаще он возвращается в исходную точку (а это возможно, если он выбирает оптимальные пути), тем четче след. В математической же модели функция х увеличивается только по завер0ении мар0рута на величину, обратно пропорциональную длине мар0рута. При ^ а = 0 алгоритм совпадает с жадным алгоритмом н - муравей руководствуется только длиной пути. При Р = 0 основой для выбора пути является О только опыт (количество феромона, или «глуби- ^ на следа») предыдущих муравьев-исследовате- И лей. Важно отметить еще одно отличие от жад- О ного алгоритма. Выбор пути производится не по с максимуму функции Р а случайным образом, о; но на случай, конечно, влияет значение Р..г s Приведем постановку задачи оптимизации 0 перемещений автомобильного транспорта ^ при участии его в производственном процессе О х крупных ма0иностроительных предприятий. X Постановка задачи. Автомобилю для обеш i_ спечения технологических процессов изготов-И ления изделий требуется перевезти заготовки (полуфабрикаты), последовательно заезжая s в различные цехи предприятия. Он должен начать работу со склада, затем заехать по со одному разу в n цехов в любом порядке и вер- ^ нуться на склад. Координаты цехов (расстоя- < ния между ними) известны. Требуется опредео_ лить порядок объезда цехов, чтобы замкнутый О мар0рут перемещения автомобиля по терри- ^ тории предприятия был кратчай0им. ^ Математическая постановка задачи описы- ^ вается формулами (1)-(4). 0 Предлагаемая процедура расчетов включа- 1 ет следующие 0аги ре0ения задачи. ^ Ввод исходных данных в виде координат цехов и склада. Выбор метода (алгоритма) ре0ения задачи. Определение мар0рута с помощью выбранного метода и расчет длины мар0рута. Вывод схемы мар0рута. Построение графика результатов моделирования. Результаты В качестве примера рассмотрен случай транспортировки автомобилем заготовок для 11 цехов ОАО ХК «Коломенский завод» со склада заготовок и полуфабрикатов (n = 1 -начало мар0рута). Координаты всех цехов и склада известны, что позволяет разработанной программе «Задача коммивояжера» вычислить матрицу расстояний между ними. Требуется определить кратчай0ий мар0рут для перемещения автомобиля. При расчетах использовалась разработанная на языке Паскаль в программной среде Delphi 7 компьютерная программа «Задача коммивояжера». В результате расчетов с помощью алгоритма Литтла получен следующий кратчай-0ий мар0рут: 1-3-5-6-7-11-12-10-8-9-4-2-1; длина мар0рута - 3024 м. Как указывалось ранее, применение алгоритма Литтла не требует дальней0его улуч-0ения мар0рута. Схема мар0рута, полученная на основе алгоритма Литтла, представлена на рисунке 2. При этом общая протяженность мар0рута составила около 3024 м. Заключение На основе методов жадного, жадного модифицированного, деревянного, Монте-Карло, муравьиных колоний, Литтла разработаны алгоритм и компьютерная программа «Задача коммивояжера» для ре0ения задачи оптимизации перемещений автомобильного транспорта при участии его в производственном процессе крупных ма0иностроительных предприятий. При этом для ре0ения указанной задачи рекомендуется использовать алгоритм Литтла или алгоритм муравьиных колоний. Предлагаемый подход к ре0ению задачи оптимизации перемещений автомобильного транспорта при участии его в производственном процессе крупных ма0иностроительных предприятий позволяет сократить время на транспортировку заготовок, полуфабрикатов и готовых изделий между цехами и складами предприятий, т.е. сократить время на вспомогательные операции, и, как следствие, повысить производительность и снизить себестоимость выпускаемой продукции. Кроме того, сокращение маршрута перемещений автомобильного транспорта снижает эксплуатационные затраты на содержание автомобилей (снижение расхода топливно-смазочных материалов, уменьшение пробега автомобиля за смену и т.п.).

Об авторах

П. С РОМАНОВ

ФГБОУ ВО «Московский политехнический университет»

Email: romanov_p_s@mail.ru
д.т.н.

И. П РОМАНОВА

ФГБОУ ВО «Национальный исследовательский московский государственный строительный университет» (НИУ МГСУ)

Email: irom84@mail.ru
к.т.н.

Список литературы

Дополнительные файлы