Динамическое планирование маршрутов фидерных контейнерных линий тема диссертации и автореферата по ВАК РФ 05.22.19, кандидат наук Малыхин Александр Сергеевич

• Малыхин Александр Сергеевич
• кандидат наук
• 2022

Оглавление диссертации кандидат наук Малыхин Александр Сергеевич

Введение

1 Анализ развития линейного судоходства и проблема фидерной сети

1.1 Теоретическая основа проблемы планирования морских фидерных перевозок

1.2 Обзор исследований в области маршрутизации и планирования

фидерной сети

Выводы, постановка цели и задач исследования

2 Динамическая модель процесса маршрутизации фидерных контейнерных линий с учетом распределения грузов между тыловыми территориями портов

2.1 Математическая основа задачи планирования рейсов судоходной компании

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

2.3 Содержательное описание процесса распределения грузов и планирования рейсов судоходной линии

2.4 Разработка модели процесса маршрутизации фидерных контейнерных линий с учетом распределения грузов между тыловыми территориями

портов

Выводы

3 Экспериментальная оценка модели и формирование методики её использования в планировании работы судоходной линии

3.1 Установление адекватности модели и экспериментальная оценка модели

3.2 Результаты серии экспериментов для установления эффективности модели

3.3 Методика использования модели в проектировании морских

судоходных линий

Выводы

Заключение

Словарь терминов

Список сокращений и условных обозначений

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

Введение диссертации (часть автореферата) на тему «Динамическое планирование маршрутов фидерных контейнерных линий»

ВВЕДЕНИЕ

Актуальность темы исследования обусловлена существенной ролью линейных судоходных компаний в глобальных транспортно-экономических системах. В современных условиях высокой конкуренции на рынке линейных перевозок, контейнерные линии все чаще предлагают в качестве дополнительного сервиса своим клиентам наземные перевозки, что значительно усложняет планирование работы линии. Современная контейнерная система грузораспределения представлена многоуровневой иерархической структурой, связывающей магистральные (океанские), региональные (фидерные) и местные (каботажные) перевозки. Функционирование каждого эшелона этой системы подчиняется своим специфическим законом, и добавление в эту структуру наземных перевозок вводит еще одну степень свободы в задачу. Рациональная разработка и реализация плана работы контейнерной судоходной линии с учетом необходимости организации наземных перевозок является сложной задачей из-за большого размера пространства поиска решений, трудоёмкости и, как следствие, высокого уровня возможных издержек. В данном исследовании рассматривается та часть этой глобальной системы, которая находится во взаимной зависимости с кластерами портов, т.е. фидерной составляющей глобальных маршрутов линейного контейнерного распределения.

Степень разработанности темы исследования. Вопросы планирования и моделирования работы морских контейнерных линий и изучались в многочисленных работах зарубежных и отечественных исследователей. Среди зарубежных специалистов, внесших существенный вклад в исследование данных проблем, необходимо отметить D. Ronen, B. J. Powell, A. N. Perakis, K. Fagerholt, R. Agarwal, E. Ozlem, M. Sigurt, N. Ulstein, M.W. Andersen, M.G. Karlaftis, Q. Meng, M. Catalani. Обширный статистический и научный материал содержится в специализированных изданиях, публикуемых World Bank, UNCTAD, HPC. В числе отечественных исследователей наиболее значимыми являются работы

Ветренко Л. Д., Дерябина В. В., Кириченко А. В., Кузнецова А. Л., Маликова О.Б., Погодина В. А., Романовского Ф. Д., Степанца А. В., Степанова А. Л., Фролова А.С., Эглита Я. Я. Однако, несмотря на проработку фундаментальных научных проблем в трудах указанных авторов, множество возникших вопросов, касающихся рационализации маршрутов линейных судов, остаются нерешенными.

Целью диссертационного исследования является повышение эффективности принятия решений при разработке рациональных маршрутов фидерных контейнерных линий с учетом консолидации и распределения грузов в портах маршрута.

Научное противоречие заключается в объективной необходимости совершенствовать организацию фидерных контейнерных линий, с учётом зарождения и поглощения грузопотоков в тыловых территориях морских портов, и отсутствии возможности удовлетворения этой потребности.

Научной задачей, лежащей в основе выявленного противоречия, решение которой обуславливает достижение поставленной цели, является разработка теоретически обоснованного метода планирования маршрутов фидерных контейнерных линий, учитывающего распределение контейнерных грузов между тыловыми территориями портов ротации.

Для решения основной научной задачи предлагается решить следующие частные задачи:

— на основе анализа существующих методов маршрутизации контейнерных линий выявить их ограничения и недостатки, определить условия и обновить математический аппарат для создания нового метода;

— разработать модель процесса маршрутизации фидерных контейнерных линий с учетом распределения грузов между тыловыми территориями портов, составляющую основу метода;

— установить адекватность модели научно обоснованными методами, по результатам экспериментов обосновать критерий эффективности - время,

обеспечивающее возможность многовариантного исследования для получения единственного рационального решения;

— предложить методику планирования маршрутов фидерных контейнерных линий.

Научная новизна исследования состоит в разработке эффективного подхода к планированию маршрутов фидерных контейнерных линий, отличающейся от известных методов возможностью учета распределения грузов между тыловыми территориями портов.

Теоретическая значимость исследования заключается в формировании обоснованного способа маршрутизации фидерных контейнерных линий с учетом распределения грузов между тыловыми территориями портов, базирующихся на логических и общенаучных принципах, использующих генетические алгоритмы и учитывающих специфику морского транспорта.

Практическая значимость исследования заключается в реализации результатов исследования в виде программного инструмента поддержки проектных и управленческих решений, а также в разработке рекомендаций по использованию этого инструмента при создании и управлении работой фидерных контейнерных линий.

Объектом исследования является организация работы линейного фидерного флота, что соответствует п. 1 «Технология, организация и управление перевозками и работой флота» паспорта научной специальности 05.22.19 в части формулы специальности.

Предметом исследования является разработка оптимального маршрута фидерной линии, что соответствует п. 8 «Разработка оптимальных путей и маршрутов» паспорта научной специальности 05.22.19 в части области исследований.

Границы исследования представляют собой тыловые территории, обслуживаемые морскими портами.

Методы исследования включают в себя системный анализ, метод генетических алгоритмов, объектно-ориентированное программирование.

Методология исследования основана на системном подходе, математической логике, математической статистике, методиках эвристического программирования.

Положения, выносимые на защиту, включают:

— математическую модель процесса маршрутизации фидерных контейнерных линий, реализованную в среде ООП Visual Studio, на языке программирования C#, разработанную на основе методов эвристического программирования;

— результаты серии экспериментов на модели, включая эксперименты для установления адекватности модели;

— научно-обоснованную методику планирования маршрутов фидерных контейнерных линий.

Степень достоверности результатов обусловлена проведенным анализом имеющихся научно-исследовательских работ по предмету диссертации, доказанным совпадением результатов моделирования с существующими апробированными результатами исследований.

Апробация результатов работы проводилась на международных научных и научно-практических конференциях. Основные результаты исследования отражены в 8 опубликованных научных работах, 4 из которых входят в перечень реферируемых изданий ВАК Минобрнауки России.

1 АНАЛИЗ РАЗВИТИЯ ЛИНЕЙНОГО СУДОХОДСТВА И ПРОБЛЕМА ФИДЕРНОЙ СЕТИ

С древнейших времен морской транспорт вносит существенный вклад в мировую экономику. Переход от гребного флота к парусному, от парусного к самоходному, а также увеличение скорости, маневренности и вместимости судов позволяло людям развивать торговлю. Одним из первых видов судоходства стало трамповое. Его существование было продиктовано требованиями рынка. Активное развитие торговли между регионами и континентами нуждалось в таком виде судоходства. Трамповые суда универсальны. Они способны принимать огромное разнообразие грузов, а также их конструкция позволяет им заходить в большинство портов, а также проводить в них погрузо-разгрузочные работы. Коммерческой особенностью работы такой формы судоходства являлось постоянное перемещение судов в поисках груза для перевозки. Однако увеличивающаяся конкуренция на рынке морского судоходства ставила перед судовладельцами новые задачи - повышение конкурентоспособности и эффективности. Результатом решения таких задач стало появление специализированных судов. Их специализация заключается в особенности их конструкции, которая позволяет им перевозить определенные виды грузов с максимальной эффективностью и утилизацией их грузовых пространств. Таким образом, в мировом судоходстве сформировалось три основных вида судоходства: трамповое, индустриальное и линейное [3].

Таким образом, судоходная отрасль разделилась на два основных сектора: балкерные перевозки (трамповое/индустриальное судоходство), которые предоставляют услуги в основном по транспортировке сырья, такого как сырая нефть, уголь, железная руда и зерно. И линейные перевозки, которые предоставляют услуги по перевозке готовой продукции, а также полуфабрикатов. Появление устойчивых грузопотоков на определённых маршрутах или, так называемых, «трейдах», стало причиной зарождения этой новой формы

судоходства. Специфика линейного судоходства позволила создать и использовать специализированный флот для перевозок. Линейное судоходство заключается в регулярном движении судов между указанными портами в соответствии с расписанием и заранее объявленными ставками. Услуга по перевозке является доступной для всех грузоотправителей и в этом смысле напоминает услугу общественного транспорта. Предоставление такой услуги по перевозке требует обширной инфраструктуры: суда, агентства, оборудование и проч.

До развития контейнерных интермодальных перевозок, перевозка брейк балка была очень трудоемкой задачей. Партия груза разбивалась для формирования множества грузовых мест. Как правило, это принимало форму паллет или кип. Перевозка таких грузов на универсальных судах была неудобной. Погрузочно-разгрузочные работы были медленными и трудоемкими, а грузовое место судов использовалось не полностью. Таким образом, суда находились в портах продолжительное время и принимали к перевозке меньший объем груза, что делало перевозку достаточно дорогой [4].

Стандартизированные контейнеры произвели революцию в международной перевозке грузов. С момента их первого появления в 1950-ом году они стали первопричиной появления множества специализированных автомобильных, баржевых и железнодорожных перевозчиков, а так же огромного флота специализированных контейнерных судов. Человеком, стоящим у истоков контейнеризации является Малком МакЛин. Первый рейс его компании с использованием контейнеров состоялся 26 апреля 1956 года из Порта Елизабет, Нью Джерси в Хьюстон, Техас.

В основе идеи интермодальности МакЛина лежала возможность перевозки груза с использованием одного и того же контейнера с помощью разных видов транспорта при минимальных остановках движения. Интермодальные контейнеры могут эффективно и безопасно перевозиться на грузовых автомобилях, поездах и судах. Все узлы на маршруте контейнеров должны быть интегрированы и адаптированы для работы с ними.

Почти все линейные грузы перевозятся посредствам контейнеров. Перевозка осуществляется в герметичных стальных опломбированных контейнерах из пункта отправления до пункта назначения. Контейнеры имеют стандартные размеры (20', 40' фут). Они могут быть оборудованными специализированными технологиями для осуществления перевозки специального груза. Например, рефрижераторной установкой для перевозки груза, обладающего температурными требованиями, либо контейнер флэт-рэк, предназначенный для перевозки негабаритных грузов. В результате развития технологий, разнообразие типов контейнеров значительно увеличилось. Сегодня возможна даже перевозка химикатов и жидкостей, даже опасных по своим свойствам, в танк-контейнерах. По своей сути, контейнеры служат тарой для перевозимого груза. Стандартной единицей объема контейнерных грузов является TEU (twenty-foot equivalent unit).

Рынок контейнерных перевозок довольно фрагментирован по своей природе, на нем присутствует множество компаний, которые принадлежат разным странам. К ведущим игрокам в этом сегменте контейнерных перевозок относятся Maersk, MSC, CMACGM, COSCO и Hapag-Lloyd. Высокие барьеры для входа в данный вид транспортного бизнеса из-за высокой стоимости транспортных средств влияют на конкуренцию в отрасли. На структуру отрасли также влияет строгое международное государственное регулирование и цикличность спроса. Судоходные компании делают разумные инвестиции в новые активы, чтобы гарантировать своим клиентам надежность и эффективность и получать отдачу от своих инвестиций. Крупнейшие контейнерные линейные перевозчики обладают фактически всем флотом контейнерных судов на рынке, а так же фактически всем парком контейнерного оборудования всех типов.

Крупнейшие контейнерные перевозчики работают в рамках организованных ими альянсов. Например, 2M с двумя участниками - Maersk и MSC. Другой известный и крупный альянс - Ocean Alliance (CMA, COSCO и пр.) и другие. Такие объединения позволяют судоходным линиям поддерживать высокий уровень своей конкурентоспособности за счет использования судов и сервисов своих партнеров по альянсу, а так же за счет поддержания низких цен на

перевозки. Очень большие фиксированные затраты контейнерных судоходных линий является одним из основных аргументов в пользу сотрудничества судоходных линий. Сотрудничество между контейнерными линейными перевозчиками, например, посредством соглашения о совместном использовании судов - УБА, может снизить этот риск и повысить коэффициент использования вместимости контейнерных линейных судов. Размер магистральных линейных судов значительно увеличился. Таким образом, переменные затраты линейных перевозчиков на перевозку контейнеров снизился. Также в рамках альянса одни и те же порты, грузовые терминалы и контейнерные сервисы. Совместное использование судов линиями помогает максимально использовать грузовую вместимость контейнерных линейных судов. Кроме того, сотрудничество помогает перевозчикам улучшать предложения услуг для своих клиентов за счет более обширной глобальной сети доставки. Практика показывает, что расширение покрытия и обеспечение большего количества маршрутов является наиболее важной мотивацией для участия в стратегических альянсах. Более того Крупнейшие альянсы контролируют около 85% всех контейнерных мировых перевозок. Около 15% перевозок остается за остальными небольшими перевозчиками.

COVID-19 серьезно подорвал мировую экономику и очень неблагоприятно отразился на отрасли контейнерных перевозок. Судоходство является основной отраслью почти для всех стран мира и играет неотъемлемую роль в цепочке поставок для большинства отраслей промышленности. Многие страны очень зависимы от судоходной отрасли в плане перевозки продуктов питания, лекарств и других предметов первой необходимости, а так же промышленных товаров, сырья и средств производства. Можно отметить, что судоходная отрасль в значительной степени основана на цикличности, а COVID-19 в свою очередь вызвал огромные нарушения в глобальной цепочке поставок. На первых этапах распространения заболевания так же привели к отмене судоходными контейнерными линиями рейсов своих судов. Пропуски в океанском расписании достигали месяцев. Например, всего за несколько недель перевозчики отменили

более 100 рейсов, что составляет 45% пропускной способности между Европой и Азией. Всеобщие проблемы в логистике привели к задержке в возврате клиентами судоходных линий порожних контейнеров обратно в линию. Что в свою очередь привело к дефициту порожнего контейнерного оборудования у линейных судоходных компаний. Более того, линейное оборудование застревало у клиентов не в тех портах, каких они нужны были в данный момент времени. К примеру, огромное количество оборудования скопилось в портах США, а линиям они нужны были в портах Китая для отправки экспорта. Некоторые линии на некоторых этапах даже были вынуждены организовывать рейсы в Китай из Европы, на которых в Китай перевозилось только порожнее линейное оборудования для немедленной выдачи контейнерного оборудования клиентам под загрузку и обратную отправку контейнеров в Европу и США. Таким образом, спрос на перевозку грузов значительно превысил предложение, и фрахтовые ставки соответственно очень сильно возросли. В результате глобальная индустрия контейнерных перевозок столкнулась с нехваткой контейнеров, что в свою очередь привело к соответствующему росту фрахтовых ставок. По информации UNCAD 2021 [5]. В 2020 году международная морская торговля и глобальные сеть поставок пострадали от последствий пандемии СОУГО-19.В 2020 году объем мирового производства упал на 3,5%, а торговля на 5,4%, а международная морские перевозки сократились на 3,8%, до 10,65 млрд. тонн. Ожидается, что мировая морская торговля восстановится на 4,3 % в 2021 году, и прогнозируется, что рост продолжится в период 2022-2026 годов.

В настоящее время на контейнерные перевозки наблюдается огромный спрос. Фрахтовые ставки линейных судоходных компаний, а также объемы перевозок находятся на высоком уровне. Мировая экономика постепенно оправляется после пандемии COVID-19. Грузоотправители пытаются восстановить свои цепочки поставок. Дефицит поставок и высокие фрахтовые ставки серьезно сказываются на стоимости итоговой продукции для потребителей. Такая динамика будет сохраняться. Более того, высокий уровень фрахтовых ставок обуславливается мировым трендом на снижение выбросов

углекислого газа. В первую очередь это сказывается из-за высоких цен на судовое топливо. Контейнерные судоходные линии так же нацелены на переоборудование своих судов на новые типы двигателей, которые работают на природном газе. Многие новые суда, на которые крупнейшие судоходные линии размещают заказы, уже снабжаются новыми двигателями, либо двигателями, которые при необходимости можно будет несложно конвертировать для использования газа как топлива.

Большая часть брейк балка в мире перевозится в морских контейнерах. Контейнеры перемещаются по сети транспортных узлов. Узлы - это точки на маршруте, где движение контейнера прекращается или контейнеры происходит их обработка или перевалка для дальнейшего движения. Такие точки могут являться пунктами мультимодальной перевозки, где контейнеры меняют вид транспорта с одного транспорта на другой. Во время перемещения контейнеров внутри сети, они могут быть порожними, загружены одной партией груза (полная загрузка контейнера, FCL) или с множеством партий для разных грузополучателей (частичная загрузка контейнера, LCL).

Контейнеры перемещаются из пункта в пункт посредством мультимодальной сети, которая связывает суда, портовые терминалы, грузовые автомобили и поезда. В основе планирования работы такой сети лежит планирование, отслеживание и доставка грузов, а также современные информационные системы, необходимые для обеспечения уверенности и надежности грузоотправителей. На сегодня контейнерные судоходные линии предоставляют высокоточный сервис по предоставлению информации по местоположению контейнера в каждый момент времени. На сайтах линии возможно отслеживание по номеру букинга, контейнера или коносамента. Сайты отражают в основном следующую информацию - нахождение контейнера на терминал, погрузку и выгрузку груза с борта контейнерного линейного судна. Так же на сайтах указываются все планируемые действия с контейнером -указывается планируемая дата выхода из порта погрузки и дата прибытия в порт выгрузки. Если линия ответственна за наземную доставку грузов, то указывается

также информация по неземной перевозке контейнера. В настоящее время даже есть дополнительные услуги линий для рефрижераторных контейнеров, которые не только показывает актуальное местонахождение контейнера в данный момент времени, но и предоставляет подробную информацию о работе рефрижераторной установке и информацию о текущем климате внутри контейнера. Данная информация очень важна для клиентов, так как они могут отслеживать состояние своего груза на всех этапах перевозки.

Порты являются основными пунктами на маршруте, где возможен обмен импортными и экспортными контейнерами между судами и наземным транспортом. На территории портов проводятся операции по погрузке и выгрузке контейнеров с судна, хранение, транспортировка и пр. Время стоянки контейнерного судна в порту зависит от количества кранов, которые назначены на обработку судна и в целом от эффективности работы контейнерного терминала [6]. В интермодальном контейнерном бизнесе порты являются связующими звеньями между морским и наземным транспортом. Эволюция контейнерных перевозок привела к появлению трех основных видов портов: порты-хабы, фидерные порты и магистральные (основные) порты. В портах-хабах происходит накопление грузов и перевалка. Фидерные порты являются портами, с которых посредствам фидерных сетей собирается груз для перевалки его в портах-хабах на основные сервисы линии. Магистральными же являются порты, в которые осуществляются регулярные заходы линейных судов компании.

Оборот ТОП-25 крупнейших контейнерных портов мира в 2020 году составил 395,7 млн. ТЕи (+0,6%). При этом в ТОП-25 вошли 9 портов Китая. На них пришлась ровно половина совокупного оборота всех вошедших в рейтинг портов - 197,5 млн. ТЕи. Из девяти китайских портов оборот снизился лишь в Гонконге - 18 млн. TEU (-1,6%). Восемь других нарастили оборот в среднем на 2,8%.

В целом по итогам 2020 года 11 портов из ТОП-25 сократили объемы перевалки. Лидерами падения стали три азиатских порта - Джакарта (Индонезия), Гаосюн (Тайвань) и Лаем Чабанг (Таиланд). Впервые в рейтинг вошел

марокканский порт Танжер-Мед, в котором в 2019 году заработали два новых терминала в районе Tangier Med 2. Оборот порта вырос в 2020 году на 1 млн TEU, благодаря чему порт занял 24 строчку рейтинга.

После нескольких лет перенакопления судов в контейнерных перевозках, недавние поставки и существующие заказы дают понять, что можно ожидать некоторых улучшений в структуре контейнерного флота. В 2020 году было поставлено 127 новых контейнеровозов, что на 70% меньше пикового показателя 2008 года, когда было поставлено 436 судов. Тенденции к строительству флота без судового грузового оборудования продолжается. Только 4,1% от всего построенного тоннажа имеет такое оборудование и способно заходить в порты, в которых нет соответствующего грузового оборудования. В 2020 году наблюдалось положительная динамика в отношении роста среднего размера судов среди только построенных судов. В процессе мировой контейнеризации, суда специализированные для перевозки контейнерных грузов прошли через следующие этапы эволюции: «Ранние контейнеровозы» способные принимать к перевозке до 1000 TEU, «Панамакс» вместимостью до 4000 TEU, «Пост Панамакс I и II» с вместимостью до 8000 TEU, «Нью Панамакс или Нео Панамакс» с вместимостью до 12500 TEU и «Ультра большой контейнеровоз (ULCV)» с вместимостью до 20000 TEU. Хоть контейнерные суда и достигли таких огромных размеров, на сегодня существуют планы по внедрению судов еще большей вместимости - «Маллака» макс. Вместимость данного класса достигает 30000 TEU. Тем не менее, их постройка зависит от появления достаточных объемов грузов на весьма узком перечне маршрутов, на котором суда таких размеров могли бы быть использованы.

Размеры судов всегда менялись в сторону увеличения. Существует прямая зависимость между количеством перевезенных TEU и стоимостью перевозки. Чем больше контейнеров перевезено, тем меньше стоимость перевозки одного TEU. Стремление к сокращению издержек на перевозку привело к гонке по увеличению размеров судов. Скорость контейнерных судов достигла пика в среднем от 20 до 25 узлов, и маловероятно, что скорость увеличится из-за необходимости

дополнительного потребления топлива. Многие судовладельцы выбирают движение на невысоких скоростях для того, чтобы справиться с высокими ценами на топливо. Создание класса быстроходных судов остается на бумаге, поскольку преимущества в плане скорости, которые они предоставят, не компенсируют значительно более высокие транспортные расходы. По итогу, цепи поставок синхронизированы со скоростями контейнерных перевозок.

Тем не менее, динамика по увеличению размеров не затронула фидерные перевозки, а также мировой спрос на постройку судов данного типа. На системах фидерного типа размещаются суда со средней вместимостью в пределах 2000 TEU. Фидерный контейнерный сервис заключается в движении судов по так называемым фидерным маршрутам, которые используются судоходными компаниями для развозки контейнеров от крупных портов побережья по более мелким портам. При использовании фидерных контейнерных сервисов, крупные контейнерные суда могут сконцентрироваться на морских перевозках и не тратить время на порты небольшого размера. Судоходными контейнерными компаниями на фидерные контейнерные линии возложена серьезная задача по дистрибуции груза внутри бассейна плавания.

Более того в современных условиях высокой конкуренции на рынке контейнерных перевозок, линейными перевозчиками все чаще предлагаются услуги по наземной перевозке грузов. Данное дополнительное перемещение контейнеров силами линиями усложняет и без того сложную настройку работы фидерных сервисов.

Ошибочное проектирование системы «Фидерный контейнерный сервис -Наземная доставка грузов» может привести к серьезным расходам судоходной компании, накапливанию контейнеров с грузом, которые ожидают доставку, из-за чего существенно увеличится транзитное время, проблемы с оборотом контейнерного оборудования из импорта в экспорт и прочее. Огромное количество дополнительных вариантов доставки грузов, которые появляются из-за прибавления наземных перевозок к морским, делают задачу по маршрутизации судов №-сложной, т.к. такую задачу невозможно решить методом полного

Список литературы диссертационного исследования кандидат наук Малыхин Александр Сергеевич, 2022 год

у у -

2 * 2

Пример такого графа приведен на рисунке Рисунок 2.7. В обоих случаях построенный граф переходов судна между морскими портами является связным, поскольку из любой вершины (морского порта) можно попасть в любую другую вершину. На рисунке 2.7, а) построен неориентированный граф на основе четырех морских портов. При оптимизации маршрута на основе такого графа нет разницы между переходом, например, из порта 1 в порт 2 и наоборот. На рисунке 2.7, б) построен ориентированный граф на основе тех же четырех портов. В этом случае между круговым рейсом

«Порт 1» ^ «Порт 2» ^ «Порт 3» ^ «Порт 4» ^ «Порт 1» и круговым рейсом «Порт 1» ^ «Порт 4» ^ «Порт 3» ^ «Порт 2» ^ «Порт 1» может оказаться существенная разница в объеме обслуживаемого грузооборота.

а)

б)

Рисунок 2.7 - Вид графа переходов судна между морскими портами в зависимости от критерия оптимальности маршрута: а) критерий оптимальности - время г ;

б) критерий оптимальности - грузооборот 2

Несмотря на данное различие, с точки зрения вычислительной сложности, эти два варианта задачи являются идентичными.

Для решения задачи оптимизации кругового рейса судна на основе критерия времени кругорейса составляется матрица расстояний между морскими портами. В п. 2.2 при описании алгоритма использовано упрощенное представление матрицы расстояний Ь, для которой расстояния могут быть определены как евклидовы метрики между двумя точками с координатами X и У на двумерном пространстве. Однако в реальности такой метод не является достаточно точным из-за кривизны геоида и особенностей судоходных путей, поэтому рекомендуется обращаться к таблицам расстояний между морскими портами для задания дистанций перехода судов. Примером существенного различия между матрицей расстояний, рассчитанной на основе евклидовых метрик, и фактическими расстояниями между портами может служить расположение портов Европы, показанное на рисунке 2.8.

Рисунок 2.8 - Расстояния между портами

Матрица расстояний имеет вид:

( н / д

£ =

521 н / д

V Sn1 2

2п

н/д

где н / д - обозначение «недействительного» перехода из порта г в порт г. Длины таких переходов обозначаются таким способом, а не приравниваются нулю, во избежание возникновения программных исключений, связанных с делением на нуль при работе модели;

п - количество портов, входящих в ротацию кругорейса судна.

Матрица расстояний в общем случае является симметричной относительно главной диагонали, т.е. для любых портов I и у справедливо о.. = . В случае существенной разницы между переходами ^ и ^ в матрицу

расстояний модели должны быть внесены соответствующие изменения.

Для учета возможных сложных переходов между некоторыми морскими портами вводится матрица коэффициентов сложности переходов:

К =

(н!д кп ••■ к1п к21 н/д ••■ к2п

"' н!

Матрица (К по умолчанию заполняется коэффициентами ку, равными

1 для всех переходов. В случае наличия особенностей перехода между двумя портами, влияющих на скорость передвижения судна, соответствующий коэффициент должен быть снижен в диапазоне от 0 < к < 1. Чем меньше

значение, присваиваемое коэффициенту сложности, тем выше сложность перехода. Альтернативной трактовкой этого коэффициента может быть отношение скорости, с которой приходится перемещаться судну, к его скорости на других переходах, на которых нет дополнительных сложностей.

Скорость судна в модели задается одной величиной и для всех переходов и представляет собой экономическую скорость, т. е. такую скорость, при которой достигается минимальный расход топлива на единицу расстояния (морскую милю).

Время кругорейса судна в общем случае складывается из двух составляющих:

— время переходов между портами, входящими в ротацию кругорейса;

— время стоянки судна в каждом порту. Математически это можно выразить следующим образом:

_ о П

и г=1

где ^ - расстояние перехода между портами г и у, морских миль.

Определяется по матрице 5 расстояний между портами; и - экономическая скорость судна, узлов;

ку. - коэффициент сложности перехода между морскими портами г и у; гпортл - время стоянки судна в порту г, часов.

Однако при решении задачи минимизации времени кругорейса, становится очевидным, что время, проводимое судном в морских портах, не влияет на критерий оптимальности решения, поскольку вне зависимости от

п

маршрута судна, оно совершит судозаходы во все порты. Слагаемое ^ £

порт.г 1 =1

будет присутствовать во всех решениях модели, независимо от рассматриваемого варианта рейса судна. Следовательно, нет необходимости учитывать это время при расчёте критерия оптимальности рейса судна. Критерий оптимальности, основанный на времени кругового рейса судна, может быть определен на основе следующей формулы:

_ с

т = (10)

Критерий оптимальности, основанный на максимальном обслуживаемом грузообороте, рассчитывается на основе матрицы грузооборотов, строящейся аналогичным способом с матрицей расстояний между портами:

(»'* е12 - ал

б=

»/<> - а»

кОа 0.2 - »/д, Однако в данном случае матрица (0) не является симметричной матрицей, поскольку, как отмечалось ранее для портов г и у будет справедливо выражение б * 0-},.

Критерий оптимальности по грузообороту кругорейса судна вычисляется на основе следующей формулы:

я=Е о», (11)

где I и у представляют собой соседние порты в последовательности захода в порты во время кругорейса.

С точки зрения генетического алгоритма критерии Т и q представляют собой целевые функции решений (также именуемые фитнесс-функциями). Во время работы ГА фитнесс-функции рассчитываются на каждом шаге для каждого решения. Таким образом, при размере популяции решений, равном т, генетический алгоритм производит вычисления для каждого из т решений:

_ о

Т=£-», я1

и • к У

У

о _

Т=Е-]Г, я 2 =Е о»

и к -1

у

о _

Тт , Ят =Е 0У

и • к,, -1

У

Задача оптимизации генетического алгоритма в таком случае сводится к поиску таких Т и я из множеств Т и q, для которых справедливы следующие выражения:

Тх = тт(Т), Ях = тах(я), где Т = {Т1,Т2,...,Тт}' д = {д1,д2,...,дт}.

С точки зрения грузопотоков, модель представляет собой систему пунктов зарождения и поглощения грузопотоков, обменивающихся грузами с привлечением морской перевозки. Минимальной неделимой единицей груза в модели принят один морской контейнер. Характеристики контейнера (как транспортные, так и модельные) подробно описаны в параграфе 2.4.

Каждый наземный пункт в модели может являться одновременно источником и потребителем грузопотоков. Таким образом, схему,

приведенную на рисунке 2.6, можно расширить, как это показано на рисунке 2.9.

Рисунок 2.9 - Пример схемы взаимосвязей морских портов и их тыловых

территорий

В модели предполагается, что производители и потребители контейнеропотоков не соединены между собой сухопутными транспортными путями или, если соединены, то наземная перевозка априори менее рациональна, чем морская перевозка контейнера между ними. В модели также предполагается, что контейнеропоток, формируемый в наземном пункте, соединенном с морским портом наземными путями сообщения, не может в качестве пункта назначения иметь наземный пункт, соединенный с этим же морским портом. Например, на рисунке 2.9 для контейнеров, отправляемых из источника грузопотока 1, пунктом назначения не может быть выбран потребитель грузопотока 2, поскольку они соединены наземной сетью путей сообщения с морским портом А. Разделение на побережья, показанное на рисунке 2.9, условное и не делает морскую перевозку грузов, например, из порта Б в порт В нерациональной.

Основные принципы, изложенные в данном параграфе, были положены в основу модели, описанной ниже в параграфе 2.4.

2.4 Разработка модели процесса маршрутизации фидерных контейнерных линий с учетом распределения грузов между тыловыми территориями портов

Модель сети распределения контейнерных грузов представляет собой автономное программное обеспечение, написанное на языке C#. В основе архитектуры программы лежит парадигма объекто-ориентированного программирования. Разработанная программа представляет собой совокупность объектов, которые могут вызывать друг друга для выбора и выполнения операций [1]. Поведение объекта задано описанием класса, к которому принадлежит объект.

В модели при помощи классов описываются следующие объекты и процессы, составляющие основу изучаемой в этом исследовании системы:

1. наземные географические пункты зарождения и поглощения грузопотоков (класс LandPoint);

2. морские порты, как пункты, аккумулирующие и распределяющие потоки груза (класс SeaPort);

3. контейнеры, как грузовые единицы (класс Container).

Помимо представленных выше классов, в моделировании участвуют вспомогательные и системные классы, позволяющие описать более абстрактные понятия, являющиеся частью генетического алгоритма, или необходимые для функционирования модели с точки зрения программного обеспечения. К таким классам относятся:

4. класс, представляющий собой одно возможное решение задачи планирования рейсов судоходной компании (класс Solution);

5. класс, обеспечивающий загрузку и сохранение модельных данных (класс IOWorker);

6. класс, обеспечивающий работу главного окна модели (класс MainWindow);

7. класс, обеспечивающий работу окна настроек модели (класс SettingsWindow);

8. класс, обеспечивающий работу самого приложения в целом (класс App);

9. класс, хранящий в себе глобальные переменные модели (класс Constants).

Структура и функциональное устройство основных классов модели подробно описана ниже. Системные и вспомогательные классы модели описаны со степенью подробности, необходимой для пояснения их работы в рамках данного исследования. Описание технической составляющей работы этих классов выходит за границы данной диссертационной работы.

Для описания наземных пунктов и морских портов созданы три класса объектов: Port, SeaPort и LandPoint. Два класса SeaPort и LandPoint наследуют от класса Port. Диаграмма отношений этих классов представлена на рисунке 2.10. Знаком «-» на диаграмме отмечены поля класса, знаком «+» отмечены методы.

Рисунок 2.10 - Диаграмма отношений классов Port, SeaPort и LandPoint

Класс SeaPort предназначен для описания морского порта. Этот класс наследует от суперкласса Port. Он хранит в себе информацию о наземных пунктах, соединенных с морским портом наземными транспортными путями - железнодорожными или автомобильными магистралями. Информация о наземных пунктах хранится в виде списка объектов класса LandPoint. Реализация этого поля выполнена именно в виде списка, поскольку это обеспечивает возможность динамического (во время выполнения модели) изменения размера списка, добавления или удаления из него элементов -связанных с портом наземных пунктов. В объекте класса SeaPort также хранится информация о контейнерах, аккумулирующихся в порту, благодаря связанным наземным пунктам. Эта информация касается экспортных контейнеров, т.е. только тех грузопотоков, которые зарождаются в связанных с портом наземных пунктах и накапливаются в порту для последующей отправки в другой морской порт. Информация о связанных экспортных контейнерах морского порта описывается полем суперкласса Port, которое представляет собой список ссылок на объекты класса Container. Методы класса SeaPort позволяют инициализировать или очистить этот список. Список объектов класса Container формируется в объекте SeaPort как объединение всех массивов контейнеров, зарождающихся в наземных пунктах. Время перехода судна между двумя портами i и j определяется на основе скорости судна. Скорость судна задаётся глобальным параметром и выражается в узлах. Скорость судна на переходе между портами i и j может быть снижена вследствие сложности маршрута. Сложность маршрута условно задаётся в виде таблицы понижающих коэффициентов к для всех

переходов между морскими портами.

Класс LandPoint наследует от суперкласса Port и предназначен для описания наземного пункта зарождения или поглощения грузопотока контейнеров. Помимо полей и методов, унаследованных от суперкласса, LandPoint содержит поле, хранящее ссылку на связанный морской порт.

Также в классе LandPoint содержится метод, генерирующий массив контейнеров, образующих грузопоток, исходящий из этого наземного пункта.

Класс Port представляет собой суперкласс для классов SeaPort и LandPoint и предназначен для описания абстрактных свойств, присущих любому транспортному узлу. Данный суперкласс хранит в себе поля и методы, наследуемые всеми его подклассами. Поскольку и класс SeaPort, и класс LandPoint имеют ряд одинаковых свойств и функций, в процессе разработки модели было принято решение выделить эти свойства и функции в данный суперкласс. К этим свойствам и функциям относятся координаты и название транспортного узла, его порядковый номер (индекс) в модели, а также массив ссылок на объекты класса Container.

Класс Container предназначен для описания грузовой единицы, принятой в модели - одного морского контейнера. Контейнер в модели рассматривается как физическая единица, а не двадцатифутовый эквивалент (ДФЭ или TEU). Структура класса Container представлена на рисунке 2.11.

Container

- пункт зарождения

- пункт назначения

- типоразмер контейнера (ГОСТ Р 53350-2009)

- индекс

Рисунок 2.11 - Структура класса Container

Как видно из рисунка, объекты класса Container не имеют собственных методов, а, следовательно, не обладают собственным поведением. С точки зрения модели они являются пассивными объектами. Тем не менее, выделение контейнеров в отдельный класс позволяет упростить логическую структуру модели и обеспечивает непротиворечивость основного алгоритма. Кроме того, наличие особых свойств у объектов класса Container позволяет

задавать и собирать дополнительную информацию о них в модели. Примером такой информации может быть типоразмер контейнера, задаваемый в виде переменной строкового типа. Предполагается возможность задания типоразмера для каждого отдельного контейнера, на основе типоразмеров, представленных в ГОСТ Р 53350-2009 [2].

Наиболее распространенными контейнерами в практике международных морских контейнерных перевозок являются 20- и 40-футовые контейнеры типов 1ААА, 1АА, 1А 1СС и 1С. Присвоение типоразмера контейнеру в модели носит информативный характер. Контейнерные грузопотоки, загрузка судов и наземных транспортных средств выражается в модели в физических контейнерах.

Основой работы генетического алгоритма, использующегося в модели, является класс Solution, описывающий вариант решения поставленной задачи, то есть последовательность заходов морского судна в порты. Структура класса Solution представлена на рисунке 2.12.

- последовательность захода в морские порты

- ссылка на матрицу грузооборотов

+ метод расчета фнтнес с-функции по временн рейса + метод расчета фптнес с-функции по грузообороту + метод перестановки двух генов (портов) в решении + метод случайного перемешивания всех генов (портов)

Рисунок 2.12 - Структура класса Solution

Поля метода представлены тремя переменными, предназначенными для хранения:

1. последовательности портов, в которые совершаются судозаходы;

2. ссылки на матрицу расстояний между портами;

3. ссылки на матрицу грузооборотов между портами.

Последовательность портов, в которые совершаются судозаходы представляет собой основу модели и по сути является оптимизируемым решением. Остальные поля и методы этого класса служат оболочкой для данного поля и позволяют организовать корректное взаимодействие с ним. Последовательность представлена одномерным массивом объектов класса SeaPort размерностью n + 1, где n - количество морских портов, заданное в начале прогона модели. Первый элемент массива и последний элемент массива всегда хранят ссылку на один и тот же морской порт, обеспечивая тем самым замкнутый характер кругорейса линейного судна. Поле, хранящее последовательность портов, является частным (приватным) полем класса Solution. В классе реализован функционал, допускающий только чтение этого внешними объектами. Для изменения этого поля предназначается метод инициализации решения.

Ссылки на матрицы расстояний и грузооборотов позволяют обратиться к соответствующей матрице изнутри объекта-решения. Ссылки на матрицу расстояний и грузооборотов инициализируются в конструкторе объекта класса.

Метод инициализации решения предназначен для создания и изменения поля последовательности портов. Этот метод позволяет присвоить каждому элементу массива портов значение в виде ссылки на существующий объект класса SeaPort. Этот метод является публичным и может быть вызван извне класса Solution. Финальным шагом метода является присвоение последнему элементу массива портов значения, хранящегося в первом элементе.

Методы расчета фитнесс-функции по времени и расстоянию позволяют определить значение целевой функции для данного решения. Эти методы являются публичными и вызываются извне класса. Методы используют ссылку на соответствующую матрицу (расстояний или грузопотоков), хранящуюся в поле класса Solution, и поле класса, хранящее

последовательность портов, для вычисления общего времени рейса или суммарного грузооборота, обслуживаемого линией. Методы совершают последовательный обход портов в соответствии с одномерным массивом и суммируют стоимости переходов между портами, выраженные в расстоянии или в грузообороте. В случае оптимизации по времени кругорейса, полученная сумма переводится в часы. В качестве результата метод возвращает значение целевой функции для данного решения.

Метод перестановки двух портов используется для имплементации мутаций решения в генетическом алгоритме. Процесс мутаций запускается и контролируется извне решения, на соответствующем шаге генетического алгоритма. Внутри класса Solution, этот метод является единственным используемым для этого процесса. Метод представляет собой простую перестановку двух элементов массива последовательности портов, принцип работы метода представлен на рисунке 2.13.

Индексы массива 0 1 2 3 4 5 6 7

Решение

Решение

6 1 7 4 3 5 2 6

6 5 7 4 3 1 2 6

Рисунок 2.13 - Перестановка двух портов в решении

На рисунке 2.13 числа внутри квадратов представляют собой индексы морских портов (порт 1, порт 2 и т. д.). В конце выполнения метода последнему элементу решения присваивается значение, равное первому элементу, для замыкания маршрута кругорейса.

Метод случайного перемешивания всех портов решения используется при создании нового объекта класса Solution для генерации случайного решения, не зависящего от предыдущих и последующих шагов генетического алгоритма. Работа метода основывается на алгоритме

тасования Фишера - Йетса [47]. Преимуществами данного алгоритма являются возможность генерации перестановок с одинаковой вероятностью и быстрое время выполнения, пропорциональное числу элементов тасуемого множества [39]. Метод является публичным и вызывается извне. Для замыкания маршрута, в конце выполнения этого метода последнему элементу решения присваивается значение, равное первому элементу.

Базовым классом программы является класс MainWindow. Этот класс включает в себя системные поля и методы, необходимые для работы программы, а также логику основного алгоритма программы - генетического алгоритма оптимизации кругорейса судна. Работа класса MainWindow основывается на шаблоне проектирования архитектуры программы MVC (англ. Model-View-Controller). Этот шаблон проектирования позволяет разделить данные приложения на три составляющих: модель (model), представление (view), контроллер (controller) [36]. Взаимосвязь между составляющими программы, основанной на шаблоне MVC, представлена на рисунке 2.14.

Рисунок 2.14 - Шаблон проектирования MVC

Как видно из рисунка, пользователь ПО взаимодействует только со структурами представления (view) и контроллера (controller). В работе

приложения это проявляется как вывод данных на экран или в файл и ввод данных при помощи элементов управления (кнопки, поля для заполнения числовых значений, бегунки прокрутки) соответственно. Получив информацию от пользователя, контроллер передает её в модель и сообщает о необходимости запуска некоторых функций модели. После выполнения собственного функционала, модель передает результаты элементам представления, которые выводят информацию для пользователя. Пример оконной формы представления / контроллера представлен на рисунке 2.15.

Представление и контроллер базируются на стандартных решениях, применяемых для реализации такого рода систем, и не рассматриваются подробно в рамках данного исследования.

Рисунок 2.15 - Оконная форма представления / контроллера модели

Функционирование модели обеспечивается за счёт двух укрупненных программных блоков: блок программы, предназначенный для подготовки исходных данных и блок программы, обеспечивающий выполнение генетического алгоритма.

Первый блок программы отвечает за корректную подготовку исходных данных и состоит из следующих функций:

1. функция генерации набора морских портов и наземных транспортных пунктов;

2. функция генерации контейнеров в наземных пунктах;

3. функция формирования матриц расстояний и грузооборота;

4. вспомогательные функции, поддерживающие работу основных функций (проверка правильности ввода исходных данных, имплементация алгоритма быстрой сортировки и др.).

Основными функциями второго блока программы, обеспечивающего работу генетического алгоритма, являются:

1. функция инициализации популяции решений;

2. функция размножения популяции решений;

3. функция сортировки популяции решений;

4. функция выполнения генетического алгоритма.

Функция выполнения генетического алгоритма использует все вышеперечисленные функции, а также некоторые вспомогательные функции для выполнения шагов генетического алгоритма. Данная функция реализована на основе встроенных инструментов многопоточности языка C#. Использование этих инструментов позволяет разделить поток выполнения генетического алгоритма (модель) и поток обработки графического интерфейса (представление и контроллер). Таким образом, приложение позволяет пользователю осуществлять управление во время выполнения алгоритма, в случае необходимости аварийной остановки выполнения.

Количество шагов генетического алгоритма задается пользователем до начала выполнения алгоритма. Функция выполнения ГА вызывается при помощи цикла «для» столько раз, какое количество шагов было задано пользователем.

С точки зрения оптимизации интерес представляет только последний шаг модели - результат работы генетического алгоритма. Однако для изучения эволюции системы решений, а также для отладки работы программы, также сохраняется информация о предыдущих шагах ГА. В

целях обеспечения приемлемой скорости работы программы, передача информации о результатах шага выполняется не для всех шагов, а только для каждого Ъ-го шага. Значение k зависит от количества шагов и растёт с увеличением их числа. В модели принято, что k должно составлять 10% от количества шагов ГА, т. е. при количестве шагов, равном 1000, модель выводит информацию о каждом 100-м шаге; при количестве 10000, модель выводит информацию о каждом 1000-м шаге, и т. д. Величина k может быть изменена программно.

Инициализация популяции решений выполняется только один раз, на первом шаге выполнения генетического алгоритма. Эта операция представляет собой случайную генерацию популяции решений заданного пользователем размера. Модель получает информацию о стартовых условиях ГА (размер популяции, процент мутаций, количество шагов, матрицы расстояний и грузооборотов) от контроллера.

Операции расчёта целевых функций решений, сортировки решений внутри популяции по значению целевой функции, отбора лучших решений, скрещивания решений, мутаций и распутывания запутанных последовательностей выполняются на каждом шаге генетического алгоритма.

Выводы

В разделе рассмотрены математические основы задачи оптимизации, положенной в основу данного исследования. Формализация задачи позволяет редуцировать её до классической оптимизационной задачи коммивояжера

Проанализированы существующие современные методологии, применимые для разработки модели распределения контейнерных грузов между морскими портами и их тыловыми территориями. Объектно-

ориентированное программирование выбрано как парадигма программирования, наиболее подходящая для целей и задач исследования.

Приводится содержательное описание предлагаемого алгоритма и модели, проанализированы существующие имплементации генетических алгоритмов для задач, схожих с задачей данного исследования. Предлагается собственная модификация генетического алгоритма на основе алгоритма генетических химер и алгоритма упорядоченного кроссовера.

Разобрана структура разработанной модели и её реализация в виде законченного программного продукта - компьютерного приложения, написанного на языке программирования С#. Кратко описана архитектура программы, взаимосвязь между классами, их поля и методы, а также программный функционал основного алгоритма программы - генетического алгоритма.

3 ЭКСПЕРИМЕНТАЛЬНАЯ ОЦЕНКА МОДЕЛИ И ФОРМИРОВАНИЕ МЕТОДИКИ ЕЁ ИСПОЛЬЗОВАНИЯ В ПЛАНИРОВАНИИ РАБОТЫ СУДОХОДНОЙ ЛИНИИ

3.1 Установление адекватности модели и экспериментальная

оценка модели

Для установления корректности работы модели была проведена серия тестовых экспериментов. В тестовых экспериментах применяется упрощенная матрица расстояний Ь, определяемая на основе евклидовых метрик между портами. В данной серии экспериментов не учитываются взаимосвязи между морскими портами и пунктами зарождения грузопотоков в их тыловых территориях. Это сделано для обеспечения возможности сравнения результатов работы алгоритма с примерами задачи коммивояжера, для которых найдено оптимальное решение. Такие примеры сведены научным сообществом в библиотеку примеров задачи коммивояжера (TSPLIB), впервые упоминаемую в [60]. В настоящее время доступ к файлам библиотеки TSPLIB осуществляется при помощи электронного ресурса [61].

Для проверки корректности работы алгоритма также проведены эксперименты с расстановками портов в виде геометрических фигур, для которых длина оптимального решения легко рассчитывается до начала работы алгоритма, например, круговое расположение портов. Для таких расстановок очевидно, что оптимальное решение будет лежать на контуре, повторяющем периметр изображаемой фигуры.

Круговое расположение портов на самом деле подразумевает расстановку портов в виде правильного и-угольника, вокруг которого описана окружность радиусом Я. Координаты порта I задаются уравнениями:

х = соб

У, = яп

--г I- Я + х0,

V п )

--г I-Я+Уо,

V п )

где хиу, - координаты порта ¡;

х0, уо - координаты центра окружности, описанной вокруг расположения портов;

п - количество портов.

На рисунке 3.1 представлено круговое расположение 20, 50, 100 портов. Значение Я = 200. Значения х0, у0 = 0.

а) б) в)

¿00 150 100 50

• • •

• •

• •

л

-200 -100 _чл 100 200

• -100 -150 _*>оо •

• •

• • •

¿00* 150

• • • •

• • 100 50 • •

• • • •

л 1

-Ш -100 100 2в0 --•-

• • -100 • •

• • -150 * -^(Ю* • •

• * • •

1 ^п

/ • и и 100 50 \ •

• • • • • • • •

» п 4 1

-2 }0 -100 А ^А 100 2£Ю __Я_

• * • \ -100 * * • /

-150

Рисунок 3.1 - Круговое расположение портов: а) 20 портов; б) 50 портов; в) 100 портов

Длина оптимального решения Еор1 для такого расположения портов определяется по формуле периметра правильного п-угольника, вокруг которого описана окружность:

^ = Р = п - 2 - Я - 81П

V п )

Проведенная серия экспериментов показала результаты, представленные в таблице 3.1.

Таблица 3.1 - Результаты серии экспериментов с круговым расположением портов

Кол-во портов, n Длина оптимального решения, Fopt Длина наилучшего найденного решения, F Длина наилучшего решения при инициализации популяции решений (на шаге 0) Шагов алгоритма затрачено до нахождения наилучшего решения F Отклонение наилучшего решения Fот оптимального решения Fopt: ( F Л д= F 1 F V opt У

20 1251,48 1251,48 4958,00 1 0,0%

50 1255,81 1255,81 11166,57 1 0,0%

100 1256,43 1256,43 22328,17 1 0,0%

Из таблицы 3.1 видно, что алгоритм проявляет крайне высокий уровень эффективности для портов, расположенных в виде правильного и-угольника.

Также в процессе тестирования алгоритма было проверена эффективность и целесообразность использования полного функционала алгоритма при различных вариантах постановки исходной задачи. Применение операции распутывания невозможно для постановки задачи, базирующейся на ориентированном графе переходов между портами (при котором цена перехода из порта а в порт Ь не равна цене перехода из порта Ь в порт а). Пример поведения алгоритма с включенной операцией распутывания и с выключенной операцией распутывания при работе с ориентированным графом представлен на рисунках 3.2 и 3.3 соответственно. Как видно из рисунка, характер кривой, получаемой по целевым функциям (ЦФ) наилучших решений при включённом операторе распутывания подобен кривой по ЦФ худших решений на каждом шаге. ЦФ наилучших решений при выключенном операторе распутывания, напротив однозначно стремится к оптимальному решению. При заданном количестве портов в тестовом решении (10 портов и 20 портов) оптимальное решение найдено алгоритмом достаточно быстро. Из проведённого теста следует, что алгоритм с включенной операцией распутывания не может осуществлять функцию

оптимизации решения из-за некорректной работы оператора распутывания на ориентированных графах. В связи с этим рекомендуется выключать функцию распутывания в случае работы с постановкой задачи с ориентированным графом.

п

ги

а

и

Он

а

п>

а

я

я

И ©

|=Г

V

а к

<и

г

к

СП

60000 50000 40000 30000 20000 10000

> к А 1 У 1 \к Л) л А 1 1

У ¥ щ ш V щ

\ 1 1 * V

10000 20000 30000 40000 50000 60000 70000 80000 90000 100000

Шаг алгоритма

■ С распутыванием

Без распутывания

Рисунок 3.2 - Пример поведения алгоритма при работе с ориентированным графом переходов между портами. Количество портов = 10

к

1)

В

и Он

а

к &

80000 70000 60000 50000 40000 30000 20000 10000 0

lSiv Л/ У \м \ ЛГ-\ Г\ . / V* и^А/ 1 к \ »А и Л1V л/

1 V '.V Ч" » 1 «Лт" 11 ' А ! * ! V ' ' 1 / Л л 1 и <\ 1 1 ( Г. -'1' 4,1 / : ч » • и ■ ' 1 > л г 1 1 1 \; \, Л ' А г 1 ууу V7 1 У л • 1* \

\! V I,1 \! , / л л ) >! »• " |/ N А" Л 1> V 4 1 > '.¡Л V V V' \ 1 '¿/ Ч 1 А А/ и' А

г\А /\Л \ уу* V1 -I 1 ' у" №

20000 40000 60000 Шаг алгоритма

80000

-Минимум, с распутыванием -Минимум, без распутывания

100000

Максимум, с распутыванием Максимум, без распутывания

Рисунок 3.3 - Пример поведения алгоритма при работе с ориентированным графом переходов между портами. Количество портов = 20

Также была проведена проверка работоспособности модели в усложненных условиях, со случайным расположением точек (портов). Для такой проверки были использованы библиотеки TSPLIB. На рисунке 3.4 приведены примеры расположения портов на основе файлов этой библиотеки. Файлы библиотеки TSPLIB обычно содержат указание на количество точек, входящих в состав задачи (например, bays 29 - означает, что задача включает в себя 29 точек).

Результаты серии экспериментов, проведенной на примерах библиотеки TSPLIB, представлены в таблице 3.2.

Таблица 3.2 - Результаты серии экспериментов с примерами TSPLIB

Пример TSPLIB Кол-во портов, n Длина оптимального решения, Fopt Длина наилучшего найденного решения, F Длина наилучшего решения при инициализации популяции решений (на шаге 0) Шагов алгоритма затрачено до нахождения наилучшего решения F Отклонение наилучшего решения F от оптимального решения Fopt: Г F 1 д= F 1 F V opt У

bays29 29 9074 9108 23485 700 0,4%

att48 48 32524 34439 133404 4000 5,9%

eil 101 101 642 653 3109 20000 1,7%

а)

О 500 1000 1500 2000 0 500 1000 1500 2000

bays29: Исходный набор портов bays29: Оптимальное решение bays29: Наилучшее найденное решение

б)

att48: Исходный набор портов att48: Оптимальное решение att48: Наилучшее найденное решение

Рисунок 3.4 - Расположение портов, оптимальные и лучшие найденные решения

на основе примеров из библиотек TSPLIB: а) bays29, б) att48, вМП01

3.2 Результаты серии экспериментов для установления

эффективности модели

Для определения эффективности использования модели при разработке судоходной линии была проведена серия экспериментов с участием специалистов соответствующей области. Специалисты, участвующие в эксперименте, были разделены на 2 группы, для обеих групп было сформировано одинаковое задание, заключавшееся в необходимости найти оптимальный маршрут следования судна судоходной линии. Критерием оптимальности назначен грузооборот судоходной линии, который необходимо максимизировать.

Группе 1 было предложено найти оптимальное решение с использованием средств, обычно применяющихся в их деятельности для планирования. Выбор средств планирования был оставлен за участниками эксперимента.

Группе 2 было предложено найти оптимальное решение с использованием ПО, разработанного в данном исследовании.

Примеры иллюстраций взаимосвязей портов и наземных пунктов представлены на рисунке 3.5.

а)

б)

в)

г)

Рисунок 3.5 - Пример исходных данных тестовой задачи, представленной для изучения эффективности использования модели:

а) - пример из 3 портов и 6 наземных пунктов;

б) - пример из 6 портов и 12 наземных пунктов;

в) - пример из 10 портов и 20 наземных пунктов;

г) - пример из 20 портов и 40 наземных пунктов.

В качестве исходных данных также выдавались данные о количестве контейнеров, перевозимых из пункта в пункт, на основе которых необходимо было определить маршрут следования судна из порта в порт для обслуживания максимального грузооборота. Пример исходных данных для случая из 3 портов и 6 наземных пунктов приведен в таблице 3.3.

Таблица 3.3 - Пример исходных данных для случая 3 портов

Наземные пункты Кол-во контейнеров к перевозке в пункт Всего конт. к отправке в пункте

Имя Соединен с портом А Б В Г Д Е

А 1 0 0 740 320 595 835 2490

Б 1 0 0 837 378 482 811 2508

В 2 695 212 0 0 673 675 2255

Г 2 864 413 0 0 432 999 2708

Д 3 317 573 953 590 0 0 2433

Е 3 651 722 568 139 0 0 2080

Всего конт. к приему в пункте 2527 1920 3098 1427 2182 3320

Численность каждой группы составляла по 5 человек. Эксперимент проводился удалённо. Задание передавалось на электронном носителе. С участников эксперимента была собрана информация о принятом им решении (порядок обхода портов и результирующий грузооборот) и о времени, затраченном на поиск решения.

Таблица 3.4 - Эффективность принятия решений с использованием и без использования модели

Кол-во портов, входящих в ротацию Кол-во наземных пунктов Группа 1 Группа 2

время, затраченное на поиск решения, мин принятое решение время, затраченное на поиск решения, мин принятое решение

Средние показатели по группе

3 6 10,6 7317 8,0 7317

Кол-во портов, входящих в ротацию Кол-во наземных пунктов Группа 1 Группа 2

время, затраченное на поиск решения, мин принятое решение время, затраченное на поиск решения, мин принятое решение

Средние показатели по группе

6 12 17,6 7502 9,4 7547

10 20 29,4 8170 11,6 8262

20 40 61,4 8149 14,0 8344

Максимальное найденное решение и соответствующее ему время поиска

3 6 8,0 7317 6,0 7317

6 12 15,0 7547 6,0 7547

10 20 27,0 8262 8,0 8262

20 40 51,0 8320 11,0 8344

Результаты эксперимента для установления эффективности использования модели в графической форме представлены на рисунке 3.6.

Результаты показали, что участники группы 1 и группы 2 получили схожие результаты. С ростом сложности поставленной задачи (увеличение числа портов и наземных пунктов) существенно увеличивается время, затрачиваемое на поиск оптимального решения:

— при 3 портах в задаче: группа 1 потратила в среднем на 33% больше времени на поиск наилучшего решения. Наилучшие решения, найденные двумя группами, совпадают;

— при 6 портах в задаче: группа 1 потратила в среднем на 87% больше времени на поиск наилучшего решения. Среднее значение решений, найденных группой 1, отличается от среднего значения решений группы 2 на -0,6%. Наилучшее найденное решение в обеих группах одинаковое;

— при 10 портах: группа 1 потратила в среднем на 153% больше времени на поиск наилучшего решения. Среднее значение решений, найденных группой 1, отличается от среднего значения решений группы 2 на -1,1%. Наилучшее найденное решение в обеих группах одинаковое;

— при 20 портах: группа 1 потратила в среднем на 339% больше времени на поиск наилучшего решения. Среднее значение решений, найденных группой 1, отличается от среднего значения решений группы 2 на -2,4%. Наилучшее найденное решение группой 1 меньше на 0,3% наилучшего решения группы 2. Таким образом, вариант исходных данных с 20 исходными портами единственный, при котором группа 1 не смогла найти оптимальное решение.

Проведенная серия экспериментов с участием экспертов в области планирования деятельности судоходной линии подтверждают оправданность выбранного критерия эффективности - времени поиска рационального маршрута движения судов. С ростом объема исходных данных (сложности сети распределения грузов), при незначительной разнице в найденных наилучших решениях (от 0% до 2,4% разницы), время, затраченное на поиск решений в группе, использовавшей предлагаемую модель, существенно ниже (от 33% до 339%). Таким образом, можно утверждать, что применение модели существенно снижает время, затрачиваемое на поиск оптимального решения поставленной в данном исследовании задачи.

а)

б)

60,0 50,0 40,0 30,0 20,0 10,0

2 а

(Г1 & В та И л в в

%

а и Я о в I а а

о п

и,и

а Я 3 4 5 6 7 ! 9 10 11 12 13 14 15 16 17 1 8 19 20

Кол-во портов в исх. данных

— Группа 1 —•—Группа 2

о 1=1

а я

а

<ь>

о л

и о

а 10 а о

8400 8200 8000 7800 7600 7400 7200

--—♦

/ /

/ /

У /

3 4 5 6

7 8 9 10 11 12 13 14 15 16 17 18 19 20 Кол-во портов в исх. данных

-Группа 1

Группа 2

Рисунок 3.6 - Результаты эксперимента для выявления эффективности использования модели: а) - средние значения; б) - наилучшее найденное решение и соответствующее время поиска

3.3 Методика использования модели в проектировании морских

судоходных линий

Сферой применения, разработанной динамической модели сети распределения контейнерных грузов, является проектирование фидерных контейнерных сервисов. В данном разделе формируется методика использования модели для оптимизации маршрутов линейных судов при распределении грузов в тыловых территориях портов. На рисунке 3.7 представлена блок-схема методики использования модели. В рекомендации входит выполнение нескольких прогонов модели с разными комбинациями (I) исходных данных:

— вариант I = 1: процент мутаций = 10%, с добавлением специального решения на основе матрицы ближайших соседей NN

— вариант I = 2: процент мутаций = 10%, без добавления специального решения на основе матрицы ближайших соседей NN

— вариант I = 3: процент мутаций = 5%, с добавлением специального решения на основе матрицы ближайших соседей ЫЫ;

— вариант I = 4: процент мутаций = 5%, без добавления специального решения на основе матрицы ближайших соседей ЫЫ.

Кроме приведенных рекомендуемых вариантов настройки параметров (I) допустимо использовать любые пользовательские варианты настройки параметров. В случае ориентированного графа задачи, что характерно для задачи максимизации обслуживаемого грузопотока, необходимо отключить функцию распутывания, поскольку работа этой функции негативно сказывается на поиске наилучшего решения, как показано в п. 3.1.

Начало

V

/ Цикл/ \ от 1 до 4

Г

Ввод исходных данных

Граф чадачи • .. <--^ориентированньш2^>

Прогон модели

Сохранение результатов (из. г. п-файла)

Рисунок 3.7 - Укрупненная блок-схема методики использования разработанной имитационной модели

Для обработки полученных результатов по прогонам модели могут использовать программные продукты обработки научных данных, пакеты программ численного анализа и научной графики.

Разработанная методика оптимизации маршрутов контейнерных судов, при учете распределения контейнеров в тыловых территориях портов на основе генетического алгоритма, является практическим инструментом для

да

Отключение функции распутывания

планирования работы сложных систем фидерных перевозок, выполняющих важную работу по доставке экспортных грузов в порты-хабы контейнерных линий, а также работу по доставке импортных грузов из портов-хабов до мелких портов в регионе. Данная методика позволяет в первую очередь осуществлять планирование новых фидерных контейнерных сервисов, а также повышать эффективность работы уже существующих и работающих фидерных контейнерных сервисов линейных судоходных компаний.

Годами накапливаемый опыт эксплуатации контейнерных фидерных сервисов позволяет проводить масштабные и доскональные исследования проблемы маршрутизации судов. Фидерные контейнерные сервисы мировых и локальных контейнерных перевозчиков находятся в условиях жесткой конкуренции и не должны отставать от технологического прогресса для сохранения существующих объемов перевозок, а также для увеличения объемов перевозок. Требования современного рынка контейнерных перевозок предполагают поддержание контейнерными линиями конкурентоспособных контейнерных сервисов, которые будут отвечать основным требованиям клиентов, таким как, например, минимальное транзитное время. При этом контейнерные сервисы должны работать так, чтобы вся доступная провозная способность судов была полностью использована.

В России есть потенциал для формирования подобных эффективных контейнерных сервисов на Балтийском море, в Дальневосточном регионе, в особенности на китайском направлении. Помимо инвестиционных планов перевозчиков, необходима серьёзная поддержка со стороны государства в модернизации судов перевозчиков, а также в модернизации наземной инфраструктуры для обеспечения высокого уровня сервиса для отправителей и получателей грузов при доставке грузов морем и по стране наземным транспортом.

Выводы

1. В разделе было проведено установление адекватности модели.

2. Результаты серии тестовых экспериментов на модели подтвердили её адекватность.

3. Практическая значимость разработанной имитационной модели доказана на основе серии экспериментов.

4. Методика структурирована в виде блок-схемы. В разделе описано пошаговое применение элементов методики.