АЛГОРИТМ СОРТИРОВКИ ПАРТИЙ ГРУЗА ПО ПРИОРИТЕТАМ НА МОРСКОМ ТЕРМИНАЛЕ ПРИ ОГРАНИЧЕНИИ НА ВРЕМЯ
Авторы:
1.
Мурманский государственный технический университет
(кафедра "Судовождение", Доцент)
Россия
Россия
2.
Мурманский государственный технический университет
(кафедра "Судовождение", Аспирант)
Россия
Россия
3.
Мурманский государственный технический университет
(д-р техн. наук, профессор; профессор кафедры судовождения)
Россия
Россия
Тип:
Статья
Страницы:
с 113
по 119
Статус:
Опубликован
Получено:
20.08.2019
Одобрено:
25.08.2019
Опубликовано:
25.08.2019
Классификаторы:
УДК 65.011
ГРНТИ 45.01 Общие вопросы электротехники
ГРНТИ 55.42 Двигателестроение
ГРНТИ 55.45 Судостроение
ГРНТИ 73.34 Водный транспорт
ГРНТИ 44.31 Теплоэнергетика. Теплотехника
ГРНТИ 45.01 Общие вопросы электротехники
ГРНТИ 55.42 Двигателестроение
ГРНТИ 55.45 Судостроение
ГРНТИ 73.34 Водный транспорт
ГРНТИ 44.31 Теплоэнергетика. Теплотехника
Язык материала:
русский
Ключевые слова:
морской терминал, груз, алгоритм сортировки партий груза, ограничение на время, множество переменных, множество приоритетов сортировки
Аннотация (русский):
Представлен алгоритм сортировки партий груза на морском терминале. Рассматриваются преимущества и недостатки морской транспортной системы; отмечено, что одновременно обработать все партии груза, поступающие в морской терминал, практически невозможно. Подробно описана процедура сортировки партий груза, обладающих различными приоритетами, основанная на идеях метода ветвей и границ. Для оценки верхней границы использован итерационно-градиентный метод. Эффективность рассматриваемого алгоритма сортировки партий груза по приоритетам на морском терминале при ограничении на время характеризуется простотой способа определения верхней границы целевой функции. Обосновывается необходимость предложенного алгоритма в работе российского морского терминала. Если компания способна поставлять свою продукцию потребителям быстро и с более низкими издержками, то она сможет получить определённые преимущества перед конкурентами в размере рыночной доли. В случае даже небольшого сбоя в порядке выполнения морских транспортных операций компании (производители продукции) могут столкнуться с проблемами производства или отгрузки, что приведёт к остановке производства в целом. Эффективная морская транспортная система конкретной судоходной компании - исключительный в своём роде комплекс операций и действий, скопировать который конкурентам крайне трудно. Приведено упрощенное описание сортировки партий груза по приоритетам на морском терминале при ограничении на время в виде последовательности десяти блоков, представляющих алгоритм. Блок первый включает формирование множества переменных, определяющих качество решений, принимаемых персоналом терминала при сортировке партий груза, и др. На последнем этапе будут просмотрены все перспективные ветви и получено оптимальное значение приоритета партии груза, поступившей на морской терминал.
Представлен алгоритм сортировки партий груза на морском терминале. Рассматриваются преимущества и недостатки морской транспортной системы; отмечено, что одновременно обработать все партии груза, поступающие в морской терминал, практически невозможно. Подробно описана процедура сортировки партий груза, обладающих различными приоритетами, основанная на идеях метода ветвей и границ. Для оценки верхней границы использован итерационно-градиентный метод. Эффективность рассматриваемого алгоритма сортировки партий груза по приоритетам на морском терминале при ограничении на время характеризуется простотой способа определения верхней границы целевой функции. Обосновывается необходимость предложенного алгоритма в работе российского морского терминала. Если компания способна поставлять свою продукцию потребителям быстро и с более низкими издержками, то она сможет получить определённые преимущества перед конкурентами в размере рыночной доли. В случае даже небольшого сбоя в порядке выполнения морских транспортных операций компании (производители продукции) могут столкнуться с проблемами производства или отгрузки, что приведёт к остановке производства в целом. Эффективная морская транспортная система конкретной судоходной компании - исключительный в своём роде комплекс операций и действий, скопировать который конкурентам крайне трудно. Приведено упрощенное описание сортировки партий груза по приоритетам на морском терминале при ограничении на время в виде последовательности десяти блоков, представляющих алгоритм. Блок первый включает формирование множества переменных, определяющих качество решений, принимаемых персоналом терминала при сортировке партий груза, и др. На последнем этапе будут просмотрены все перспективные ветви и получено оптимальное значение приоритета партии груза, поступившей на морской терминал.
Ключевые слова:
морской терминал, груз, алгоритм сортировки партий груза, ограничение на время, множество переменных, множество приоритетов сортировки
морской терминал, груз, алгоритм сортировки партий груза, ограничение на время, множество переменных, множество приоритетов сортировки
Введение На российских предприятиях и на предприятиях со смешанным капиталом морские перевозки чаще всего воспринимают утилитарно, как некий комплекс операций, привычных для любой компании (транспортировка, складирование, таможенная очистка и т. д.). Однако теория и практика транспортных операций доказывают, что для подобных операций всегда используется системный подход в управлении, необходимый для повышения рентабельности и показателей безопасности. Эффективная морская транспортная система конкретной судоходной компании - во многом уникальный комплекс операций, скопировать который конкурентам бывает очень сложно и, наверно, не нужно. Такая система одновременно является и самым главным преимуществом компании, и самым уязвимым её местом. С одной стороны, она позволяет компании сосредоточиться на главном: производстве материальных ценностей посредством сокращения затрат и высвобождения средств, которые могут быть направлены на развитие компании, с другой - её деятельность нацелена на сокращение затрат и запасов и осуществляется по принципу «в нужное время, в нужном месте». При малейшем сбое в порядке выполнения морских транспортных операций компании (производители продукции) могут столкнуться либо с проблемой производства, либо с проблемой отгрузки, что в свою очередь может привести к остановке производства в целом. Если же компания-производитель способна поставлять свою продукцию потребителям быстро и с более низкими издержками, то она будет получать определённые преимущества перед конкурентами в размере рыночной доли. Цель работы - предложение алгоритма сортировки партий груза на морском терминале, основанного на идеях метода ветвей и границ. Алгоритм представлен в описательном виде и может быть использован при обработке и сортировке партий грузов с различными приоритетами при ограничении на время. Материалы исследования Рассмотрим процедуру сортировки партий груза, поступающих на морской терминал по направлению «берег - море», основанную на идеях метода ветвей и границ, при этом для оценки верхней границы решения задачи сортировки будем использовать итерационно-градиентный метод [1]. При ограниченном времени сортировки партий груза, поступающих на обработку в морской терминал, обработать все партии груза одновременно практически невозможно [2]. Поэтому если партии груза xij, подлежащие сортировке, обладают различными приоритетами, то для реализации этой операции целесообразно выбирать лишь те партии, для которых выполняется условие при заданном ограничении (1) где λj - приоритет j-й партии груза, поступившей на морской терминал; Tд - допустимое время процедуры сортировки; S - множество переменных, определяющих качество решений, принимаемых персоналом терминала при сортировке партий грузов. Время контроля j-го приоритета партии груза tij (i, j = 0; n, i ≠ j) зависит от того, какой i-й приоритет партии груза проверяется непосредственно перед ним (i = 0 означает, что оператор, ответственный за сортировку партий груза, начинает просмотр элементов партии с исходного состояния). В то же время j = 0 означает, что оператор, ответственный за сортировку партий груза, после идентификации последнего приоритета возвращается к исходной партии груза [3]. Введём обозначения: U - множество приоритетов сортировки партий груза; ES - запрещённое множество приоритетов сортировки, введение которых на множество S приводит к повторной проверке параметров, образованию недопустимых циклов или не приводит к улучшению принимаемого для необходимого результата; GS - свободное множество приоритетов сортировки, из которого производится выбор очередной переменной для включения в множество S; hij = λj / tij - коэффициент эффективности сортировки партии груза по j-му приоритету, если ему предшествовал i-й приоритет. На первом шаге решения S = Ø, Еs= Ø, а множество GS включает партии груза, прибывшие на морской терминал xij (j = 1, 2, ..., n). С помощью выражения (2) определяется переменная x0k, которая включается на множество S. При этом величина λS(x0k) будет являться верхней границей целевой функции при включении на множество S переменной x0k. На втором шаге x0k Î S, x0k Î ES (i = l, 2, ..., n), xkj Î GS (j = 1, ... , n, j ≠ n). Поэтому определив величину можно ввести переменную (партию груза) xkl на множество S. На всех последующих шагах выбор очередной партии груза для включения на множество S производится с помощью выражения, аналогичного (2). Если в процессе решения окажется, что множество GS = Ø, то величину можно принимать уже в качестве первого приближенного решения по сортировке партий груза в зависимости от приоритетов. На следующем шаге из множества S исключается партия груза, вошедшая на последнем шаге (эта партия вводится на множество ES), и поиск продолжается для вариантов, которые удовлетворяют условию Выбор вариантов заканчивается, если для всех вершин дерева имеет место GS = Ø, то есть рассмотрены все перспективные комбинации, и одновременно выполняются два условия: Рассмотрим более подробно процесс определения верхней границы целевой функции. Допустим, что сортируемые партии груза (переменные) x0,1, x1,2, ..., xk - 1,k вошли во множество S(k < n). Тогда переменные хij (i = l, 2, ..., j = 1, 2, ..., k, i ≠ j), хij (i = 1, 2, ..., k - 1, j = k + 1, k + 2, ..., n), xi0 (i = 1, 2, ..., k - 1) образуют множество ES, т. к. их введение на множество S приведёт к повторному процессу сортировки и образованию недопустимых циклов. Кроме того, на множество ES заносятся сортируемые партии груза (переменные) xkj (j = k + 1, k + 2, ..., n), для которых выполняются неравенства (3) (4) Условие (3) означает, что введение переменной хkj на множество S не может привести к улучшению полученного на предыдущих шагах решения, а неравенство (4) следует из ограничения (1). Допустим, что требуется определить верхнюю границу целевой функции (5) при условии выполнение которого определяет принадлежность партии груза к множеству S. Определим и значения Тогда, приняв, что выполняется условие (6) можно найти (7) (8) Так как при то вместо (5) для определения верхней целевой функции может быть использована зависимость вида (9) Следовательно, для определения верхней целевой функции необходимо определить партии груза, для которых выполняются условия (6)-(8), и для этих партий вычислить величину, определяемую выражением (9). Упрощенное описание алгоритма сортировки партий груза по приоритетам на морском терминале при ограничении на время может быть представлено в виде следующей алгоритмической последовательности. Блок 1. Формируются множества S, ЕS, GS и принимается начальное значение λ = 0. Блок 2. С помощью условий (6)-(9) с учётом ЕS определяются значения λS(xij) (xij Î GS) и по формуле (2) выбирается переменная хkl, которая вводится в S. Блок 3. С учётом введения хkl в S пересчитываются GS и ES. Блок 4. Проверяется условие GS = Ø. Если условие не выполняется, то продолжается процесс формирования множества S. При выполнении условия процесс формирования множества S прекращается. Блок 5. Проверяется условие λ < λS. При выполнении неравенства величина λS является новым приближенным решением. Блок 6. Запоминается новое приближенное решение λ и соответствующее ему множество S. Блок 7. Для движения вверх по дереву возможных вариантов из множества S исключается последняя переменная xkl, которая для исключения повторного просмотра ветви вводится в множество ES. Блок 8. Находится множество GS и ES после исключения xkl из множества S. Блок 9. Проверяется условие GS = Ø. Если условие не выполняется, то строится новая ветвь дерева возможных вариантов. Блок 10. Проверяется условие S = Ø. Если условие не выполняется, то продолжается движение вверх по дереву возможных вариантов. Выполнение условия свидетельствует о том, что просмотрены все перспективные ветви и получено оптимальное значение λ и соответствующее ему множество S. Таким образом, эффективность рассмотренного алгоритма сортировки партий груза по приоритетам на морском терминале при ограничении на время определяется простотой способа определения верхней границы целевой функции [4]. Кроме того, если ветви дерева возможных вариантов сортировки партий груза по заданным приоритетам строятся последовательно, то алгоритм достаточно просто реализуется [5]. Заключение При ограниченном времени сортировки партий груза, поступающих на обработку в морской терминал, обработать все партии груза одновременно практически невозможно. Представлен алгоритм и упрощенное описание (в виде последовательности десяти блоков) сортировки партий груза по приоритетам на морском терминале при ограничении на время. Эффективность рассмотренного алгоритма сортировки партий груза по приоритетам на морском терминале при ограничении на время определяется простотой способа определения верхней границы целевой функции.
1. Гермейер Ю. Б. Введение в теорию исследований операций. М.: Наука, 1971. 384 с.
2. Снопков В. И. Технология перевозки грузов морем: учеб. СПб.: Профессионал, 2006. 560 с.
3. Андронов Л. П. Перевозка опасных грузов морем. М.: Транспорт, 1971. 208 с.
4. Карташов С. В., Меньшиков В. И., Пеньковская К. В., Шутов В. В. Операции по перевозке, обработке и размещению груза на судне: учеб. пособие. Мурманск: Изд-во МГТУ, 2017. 114 с.
5. Позняков С. И., Меньшиков В. И. Методы разрешения нештатных ситуаций при управлении судовыми технологическими процессами. Мурманск: Изд-во МГТУ, 2017. 184 с.
