ALGORITHM OF SORTING CONSIGNMENTS IN ORDER OF PRIORITY AT SEA TERMINAL UNDER TIME LIMIT
Authors:
1.
Murmansk State Technical University
(Department "Navigation", Assistant Professor)
Russian Federation
Russian Federation
2.
Murmansk State Technical University
(Department "Navigation", Postgraduate Student)
Russian Federation
Russian Federation
3.
Murmansk State Technical University
(Doctor of Technical Sciences, Professor; Professor of the Department of Navigation)
Russian Federation
Russian Federation
Type:
Article
Pages:
from 113
to 119
Status:
Published
Received:
20.08.2019
Accepted:
25.08.2019
Published:
25.08.2019
Subject area:
UDK 65.011
GRNTI 45.01 Общие вопросы электротехники
GRNTI 55.42 Двигателестроение
GRNTI 55.45 Судостроение
GRNTI 73.34 Водный транспорт
GRNTI 44.31 Теплоэнергетика. Теплотехника
GRNTI 45.01 Общие вопросы электротехники
GRNTI 55.42 Двигателестроение
GRNTI 55.45 Судостроение
GRNTI 73.34 Водный транспорт
GRNTI 44.31 Теплоэнергетика. Теплотехника
Language:
Russian
Keywords:
sea terminal, cargo, algorithm of sorting consignments, time limit, set of variables, set of sorting priorities
Abstract (English):
The paper presents the algorithm for sorting consignments at the sea terminal. The advantages and disadvantages of the maritime transport system are considered. It has been stated that it is impossible to simultaneously handle all consignments entering the marine terminal. The procedure of sorting consignments in order of priority based on the principles of branch and bound method is specified. An iterative gradient method was used to estimate the upper bound. The effectiveness of the considered algorithm for sorting consignments in order of priority at the sea terminal under a time limit is defined by simplicity of determining the upper limit of a target function. The importance of the proposed algorithm in operation of the Russian sea terminal is justified. If a company is able to deliver its products to consumers quickly and at lower costs, then it will gain certain advantages over its competitors in the amount of market share. In the event of a malfunction in the marine transportation operations, the companies (product manufacturers) may face production or shipment problems, which will lead to business interruption. Efficient maritime transport system of a particular shipping company is an exceptional complex of operations and actions, which can’t be copied by the competitors. A simplified description of sorting consignments in order of priority at the sea terminal under the time limit is presented in the sequence of ten modules representing the algorithm. The first module includes creating a set of variables that determine the quality of decisions made by terminal personnel when sorting consignments, etc. At the last stage, all promising branches will be considered and the optimum priority of the consignment entered at the marine terminal will be obtained.
The paper presents the algorithm for sorting consignments at the sea terminal. The advantages and disadvantages of the maritime transport system are considered. It has been stated that it is impossible to simultaneously handle all consignments entering the marine terminal. The procedure of sorting consignments in order of priority based on the principles of branch and bound method is specified. An iterative gradient method was used to estimate the upper bound. The effectiveness of the considered algorithm for sorting consignments in order of priority at the sea terminal under a time limit is defined by simplicity of determining the upper limit of a target function. The importance of the proposed algorithm in operation of the Russian sea terminal is justified. If a company is able to deliver its products to consumers quickly and at lower costs, then it will gain certain advantages over its competitors in the amount of market share. In the event of a malfunction in the marine transportation operations, the companies (product manufacturers) may face production or shipment problems, which will lead to business interruption. Efficient maritime transport system of a particular shipping company is an exceptional complex of operations and actions, which can’t be copied by the competitors. A simplified description of sorting consignments in order of priority at the sea terminal under the time limit is presented in the sequence of ten modules representing the algorithm. The first module includes creating a set of variables that determine the quality of decisions made by terminal personnel when sorting consignments, etc. At the last stage, all promising branches will be considered and the optimum priority of the consignment entered at the marine terminal will be obtained.
Keywords:
sea terminal, cargo, algorithm of sorting consignments, time limit, set of variables, set of sorting priorities
sea terminal, cargo, algorithm of sorting consignments, time limit, set of variables, set of sorting priorities
Введение На российских предприятиях и на предприятиях со смешанным капиталом морские перевозки чаще всего воспринимают утилитарно, как некий комплекс операций, привычных для любой компании (транспортировка, складирование, таможенная очистка и т. д.). Однако теория и практика транспортных операций доказывают, что для подобных операций всегда используется системный подход в управлении, необходимый для повышения рентабельности и показателей безопасности. Эффективная морская транспортная система конкретной судоходной компании - во многом уникальный комплекс операций, скопировать который конкурентам бывает очень сложно и, наверно, не нужно. Такая система одновременно является и самым главным преимуществом компании, и самым уязвимым её местом. С одной стороны, она позволяет компании сосредоточиться на главном: производстве материальных ценностей посредством сокращения затрат и высвобождения средств, которые могут быть направлены на развитие компании, с другой - её деятельность нацелена на сокращение затрат и запасов и осуществляется по принципу «в нужное время, в нужном месте». При малейшем сбое в порядке выполнения морских транспортных операций компании (производители продукции) могут столкнуться либо с проблемой производства, либо с проблемой отгрузки, что в свою очередь может привести к остановке производства в целом. Если же компания-производитель способна поставлять свою продукцию потребителям быстро и с более низкими издержками, то она будет получать определённые преимущества перед конкурентами в размере рыночной доли. Цель работы - предложение алгоритма сортировки партий груза на морском терминале, основанного на идеях метода ветвей и границ. Алгоритм представлен в описательном виде и может быть использован при обработке и сортировке партий грузов с различными приоритетами при ограничении на время. Материалы исследования Рассмотрим процедуру сортировки партий груза, поступающих на морской терминал по направлению «берег - море», основанную на идеях метода ветвей и границ, при этом для оценки верхней границы решения задачи сортировки будем использовать итерационно-градиентный метод [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. Germeyer Yu. B. Vvedenie v teoriyu issledovaniy operaciy. M.: Nauka, 1971. 384 s.
2. Snopkov V. I. Tehnologiya perevozki gruzov morem: ucheb. SPb.: Professional, 2006. 560 s.
3. Andronov L. P. Perevozka opasnyh gruzov morem. M.: Transport, 1971. 208 s.
4. Kartashov S. V., Men'shikov V. I., Pen'kovskaya K. V., Shutov V. V. Operacii po perevozke, obrabotke i razmescheniyu gruza na sudne: ucheb. posobie. Murmansk: Izd-vo MGTU, 2017. 114 s.
5. Poznyakov S. I., Men'shikov V. I. Metody razresheniya neshtatnyh situaciy pri upravlenii sudovymi tehnologicheskimi processami. Murmansk: Izd-vo MGTU, 2017. 184 s.
