Такие контейнеровозы называют «post-Panamax», потому что они слишком велики, чтобы поместиться в Панамском канале

Посмотрите вокруг. Есть высокая вероятность того, что какие-то из окружающих вас предметов прибыли к вам по морю. 90% товаров в мире перемещается по океану, зачастую на ужасно огромных грузовых судах: длина четыреста метров, масса 250 тысяч тонн, вмещают в себя 12 тысяч контейнеров суммарной стоимостью в миллиард долларов. В отличие от самолётов, поездов и грузовых автомобилей, грузовые суда работают практически непрерывно, двигаясь по цикличным маршрутам в океанах.

Но какими же будут наилучшие, наиболее оптимальные маршруты таких судов? Для специалиста по computer science это задача из теории графов; для бизнес-аналитика — это задача цепочки поставок. Если её решить плохо, то контейнеры будут простаивать в портах, суда впустую тратить время в открытом море, неспособные причалить, а в конечном итоге подорожают товары из-за того, что поток физических ценностей замедлится и станет менее предсказуемым. Каждой занимающейся контейнерными перевозками компании приходится справляться с этими задачами, но обычно они решаются по отдельности. При их комбинировании сложность умножается; насколько нам известно, эту задачу так пока и не удалось решить для самых крупных контейнерных операций (500 судов и 1500 портов).

Команда Operations Research с гордостью представляет Shipping Network Design API, реализующий новое решение этой задачи. Наша методика лучше масштабируется, позволяя находить решения задач цепочек поставок общемирового уровня, будучи при этом быстрее, чем все остальные известные решения. Она способна удвоить прибыль компании-перевозчика, доставлять на 13% больше контейнеров, задействуя при этом на 15% меньше судов. В этой статье мы расскажем, как нам это удалось.

▍ Введение

Задача Liner Shipping Network Design and Scheduling Problem (LSNDSP, задача проектирования сети и графика линейного судоходства) состоит из трёх компонентов. Проектирование сети (Network Design) определяет порядок, в котором суда посещают порты, график сети (Network Scheduling) определяет время их прибытия и отбытия, а маршрутизация контейнеров (Container Routing) выбирает путь, проходимый контейнером от начальной до конечной точки. Каждой компании-перевозчику необходимо решать все три этих задачи, но обычно они решаются последовательно. Решать их одновременно сложнее, но это может с большей вероятностью позволить обнаруживать более качественные решения.

Решения задачи проектирования сети создают линии обслуживания, по которым движется небольшое множество судов: допустим, перемещаясь из Восточной Азии через Суэцкий канал и в Южную Европу. Эти линии обслуживания публикуются вместе с датами, чтобы перевозчики знали, когда и где их контейнеры должны находиться в порту.

Часть проекта сети для гипотетической океанической компании-перевозчика, демонстрирующая, как суда могут циклически перемещаться между девятью портами

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

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

Пришвартованный в порту контейнеровоз с загружающими и разгружающими контейнеры кранами

При масштабном решении этих трёх задач (network design, network scheduling и container routing) образуется огромное пространство поиска.

▍ Методики решения

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

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

Мы определили два базовых подхода к решению задачи:

1. Двойная генерация столбцов
   
   Мы рассматривали проектирование сети и маршрутизацию контейнеров как две связанные задачи, каждая из которых состоит из задачи первичного выбора (выбора наилучшего варианта) и вспомогательной задачи генерации (выявления разумных вариантов). Мы применили к каждой паре задач алгоритм кратчайшего пути для генерации разумных вариантов, а затем линейную программу (с использованием нашего солвера линейного программирования Glop) для выбора наилучших вариантов для каждого. Мы применили методику генерации столбцов к обеим одновременно, использовав промежуточные результаты каждой задачи для воздействия на прогресс другой. Такая методика двойной генерации столбцов позволила нам найти доказуемо оптимальные решения, но она хорошо масштабировалась только до задач среднего уровня.
   
   
2. CP-SAT
   
   Затем мы попробовали реализацию на основе программирования с учётом ограничений, воспользовавшись нашим солвером CP-SAT. Эта методика тоже хорошо сработала на сетях среднего размера, но не масштабировалась до решения задачи перевозок общемирового уровня.

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

1. Поиск в большом окружении
   
   Перед использованием одного из описанных выше методов мы фиксировали части решения (например, «это судно посещает Лос-Анджелес каждый второй вторник»). Это повышает масштабируемость благодаря уменьшению пространства поиска.
   
   
2. Поиск в переменном окружении
   
   Мы исследовали соседние решения и в сети, и в графике. Процесс исследования был распараллелен и распределён по множеству машин, чтобы можно было оценивать множество окружений одновременно. Кроме того, благодаря ограничению пространства поиска это повышает масштабируемость, одновременно позволяя нам применять знания из математических методов исследования операций и отрасли перевозок.

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

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

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

▍ Результаты

Для количественной оценки показателей наших решений мы воспользовались LINERLIB — отраслевым бенчмарком для задач проектирования сетей перевозок, в том числе и ситуаций с перевозкой контейнеров: флотов судов, портов и спроса на контейнеры. Мы протестировали наше решение в трёх сценариях: WorldSmall, EuropeAsia и в огромном WorldLarge. В последнем использовалось 500 судов, 200 портов и почти 140 тысяч контейнеров.

Ниже представлено сравнение пяти сценариев LINERLIB.


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

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

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

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

По сравнению с исходным результатом, наша методика оказалась способной спроектировать маршруты большего количества контейнеров с задействованием меньшего количества судов. Для каждого из сценариев LINERLIB наши решения повысили общую эффективность, увеличив пропускную способность (на 35% меньше контейнеров для WorldSmall, на 14% для EuropeAsia, на 35% для Pacific, на 32% для Mediterranean), при этом задействуя меньше судов (соответственно, на 7, 15, 4 и 23%). Согласно экономическим допущениям LINERLIB, наши решения также существенно повысили прогнозируемые прибыли.

▍ Заключение

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

Shipping Network Design API стал одним из множества наших Operations Research API, которые мы будем дополнять в будущем, исследуя возможности оптимизации других отраслей.

Telegram-канал со скидками, розыгрышами призов и новостями IT ?