Задача о доставке грузов

2020-02-06 в 9:52, admin, рубрики: математика, целочисленное программирование

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

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

У каждой отгрузки есть объем и стоимость, а рейс ограничен в объеме. Вы можете подумать об этом как об упрощенной проблеме рюкзака. Итак, есть 1024-1=1023 возможных решений (мы не отправили бы самолет полностью пустым).

Мы могли бы создать электронную таблицу, чтобы перечислить все решение и выбрать самое выгодное из них. Но что, если у вас те же десять отправлений, но два рейса? Это 59 049 решений всего за 10 отправлений.

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

Целочисленное программирование - это подраздел дискретной оптимизации, область исследования операций, связанных с минимизацией некоторой целевой функции, подверженной ограничениям. Мы хотим минимизировать общие затраты при условии своевременной доставки грузов в нужные пункты, укладываясь в ULD (Unit Load Device - средство пакетирования грузов). Мы стремимся к оптимальному решению, но на практике иногда не можем его достичь. В этом случае мы довольны хорошим или близким решением. Здесь ограничимся простой моделью, в которой оптимальное решение достижимо.

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

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

Целевая функция - минимизация общей стоимости, определяемой как общий вес всех грузов, присвоенных ULD, умноженный на коэффициент перегрузки. Например, если у ULD1 100 килограммов перегрузки, а ставка за перегрузку для ULD1 – 4 доллара за килограмм, то общая стоимость ULD 1 составит 400 долларов. Итак, нам нужна некоторая нотация для избыточного веса и для его стоимости.

Пусть $y_j^E$ - вес ULD j выше стандартного и $c_j^E$ - коэффициент стоимости для той же ULD. Нам нужно вычислить $y_j^Ec_j^E$ для всех $j$ . Если $j in {1, 2, 3}$ , то целевая функция будет $y_1^Ec_1^E+y_2^Ec_2^E+y_3^Ec_3^E$ . Это сворачивается до $sum y_j^Ec_j^E$ . Мы хотим минимизировать значение, поэтому наша конечная цель:

$text{min} sum_{j} y^E_j c^E_j$

Значение для $c_j^E$ не является вычисляемым значением. Это параметр, получаемый из электронной таблицы или базы данных. Но $y_j^E$ мы определили как общий вес перегрузки для ULD $j$ , который мы можем вычислить как общий вес всех поставок, назначенных ULD (обозначим его $y_j$ ), за вычетом стандартного веса этого ULD. Стандартный вес специфичен для типа ULD и также является параметром. Пусть $U_j^P$ - это стандартный вес для ULD $j$ в килограммах. Тогда сумма дополнительного веса для ULD $j$ определяется как $y_j^E=y_j-U_j^P$ .
Общий вес ULD, конечно, зависит от того, какие грузы отнесены к ULD, и их веса. Поэтому нам нужно выражение для его вычисления, включающее упомянутые выше детали.

Это просто сумма весов грузов, назначенных ULD. Как указать, что партия товара была назначена конкретному ULD? Для этого нам нужен не параметр, а переменная решения. Переменная решения - это то, что решатель может контролировать при минимизации целевой функции.

Пусть параметр $g_i$ представляет вес брутто груза $i$ в килограммах.
Например, $g_4=500$ означает, что груз 4 весит 500 килограммов.

Пусть $x_{i, j}$ - переменная решения, принимающая значение 1, если отгрузка $i$ назначена ULD $j$ , и $0$ в противном случае. Таким образом, когда мы хотим подсчитать все отгрузки, назначенные ULD 3, мы можем выполнить цикл по всем переменным $x_{i, j}$ , где $j=3$ . Если бы у нас было 4 отгрузки, и отгрузка номер 1 и 3 была назначена ULD 3, это выглядело бы так:

$x_{1,3} + x_{2,3} + x_{3,3} + x_{4,3}=1 + 0 + 1 + 0=2$

Но нам нужен общий вес, а не количество. Для его получения можно просто умножить каждую переменную решения на весовой параметр. Поскольку переменная решения принимает значение 0, если ей не присвоен вес, то этот вес обнуляется и не включается в общий. Допустим, веса для грузов с первого по четвертый - 10, 50, 25 и 5. Тогда общий вес в ULD 3 будет таким:

$g_1x_{1,3} + g_2x_{2,3} + g_3x_{3,3} + g4x_{4,3}=(10)(1) + (50)(0) + (25)(1) + (5)(0)=10 + 25=35$

Давайте выпишем этот расчет общего веса в общем виде. Определим общий вес ULD $j$ как $y_j$ . Тогда $y_1=g_1x_{1,1}+g_2x_{2,1}+ … + g_ix_{i, 1}$ , и $y_2=g_1x_{1,2}+g_2x_{2,2} +…+ g_ix_{i, 2}$ . Мы можем свернуть это, используя нотацию суммирования $y_1=sum g_ix_{i, 1}$ и $y_2=sum g_ix_{i, 2}$ . Поскольку мы хотим, чтобы это было верно для всех возможных $j$ , мы используем знак «для всех»: $forall$ . Это дает нам конечную форму нашего ограничения общего веса:

$y_j=sum_{i in I}g_ix_{i,j} forall j in J$

Дополнительный вес

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

$y_j^E=y_j-U_j^P quad forall j in J$

Например, если $y_1=1500$ и and $U_1^P=1000$ , то дополнительный вес $y_1^E=1500 - 1000=500$ килограммов. Умножим это на коэффициент соимости, чтобы получить результат в долларах. На первый взгляд это может показаться достаточным, но как насчет случая, когда общий вес всего груза для ULD не превышает стандартный вес? В этом случае, если бы мы использовали формулу «как есть», то вес перегрузки был бы отрицательным числом. Например, если стандартный вес составляет 1650 килограммов, а общий присвоенный - 1000 килограммов, то перегрузка = 1000–1650 = -650. Целевая функция умножит это число на коэффициент для перегрузок и мы получим отрицательное число. Как если бы перевозчик платил нам за доставку меньше стоимости стандартного веса.

Вот, чего мы действительно хотим: $text{max}(y_j^E, 0)$ .
Это то же самое, что просто установить 0 для переменной, что так же просто, как создать ограничение $y_j^E>=0$ .

$y_j^E >=y_j - U_j^P quad forall j in J$ , $y_j^E >=0 quad forall j in J $

Итак, мы реализовали функцию max() в математическом программировании: a = max (b, c), то есть a >= b && a >= c. Давайте посмотрим на наши определения.
Целевая функция: $text{min} sum_{j} y^E_j c^E_j$
$c_j^E$ : Коэффициент перегрузки ULD $j$
$y_j^E$ : Перегрузка ULD $j$ ; $inline$y_j^е = y_j - U_j^P$inline$
$U_j^P$ : Стандартный вес ULD $j$
$g_i$ : Вес отгрузки брутто $i$
$x_{i, j}$ : переменная решения; $x_{i, j}=1$ , если отгрузка $i$ назначена ULD $j$ , $0$ в противном случае.
$y_j$ : общий вес всех грузов, назначенных ULD $j$ ; $y_j=sum_{i in I}g_ix_{i,j} quad forall j in J$

Каждый груз должен лететь

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

Это означает, что $x_{i, j}$ может равняться только 1 для одного значения $j$. Например, если мы рассматриваем отгрузку 13, то $x_{13,1}+x_{13,2}+ x_{13,3}+ … + x_{13, J}=1$ . Мы хотим применить это ограничение для каждой отгрузки $i$ (которую мы записываем как $forall iin I$ ), и мы можем свернуть сложение с помощью оператора суммирования ( $sum$ ), поэтому наше окончательное ограничение:

$sum_{j in J} x_{i, j}=1quadforall i in I$

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

Ограничения объема и веса

Давайте определимся $U_j^M$ , как максимальную грузоподъемность в килограммах ULD $j$ и $U_j^В$ как максимальный объем в кубических метрах ULD $j$ . Давайте все же определимся $v_i$ , а объем в кубических метрах груза $i$ . Для ограничения модели максимальной грузоподъемностью и максимальным объемом, у нас есть условия:

$y_j<=U_j^M quad forall j in J$

$sum_{i in I} x_{i,j} v_ i <=U_j^V quad forall j in J$

Ветеран отрасли сразу же поймет, что это не соответствует действительности. Почему? Потому что эти ограничения рассматривают груз так, как будто его можно вылить, как воду, в любой объем. В реальности грузы жесткие или имеют другие ограничения, например, по укладке. 10 кубических метров груза не могут быть упакованы в произвольный объем, равный именно 10 кубическим метрам. Чтобы справиться с этими случаями, нужно решить задачу об упаковке в контейнеры. Мы проверяем, поместятся ли определенные объемы внутри других, но это выходит за рамки данной статьи.

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

Время, когда отгрузка фактически готова к консолидации с другими отгрузками в ULD и загрузке на рейс. Давайте используем $Q_i^-$ , чтобы представить время готовности отгрузки $i$ .
Время, к которому груз должен быть выгружен в пункте назначения, деконсолидирован и доступен для получения, как правило, из грузового терминала. Давайте используем $Q_i^+$ для представления крайнего срока поставки отгрузки $i$ .
Время, к которому весь груз должен быть доставлен в грузовой терминал для погрузки на рейс. Давайте используем $T_j^ -$ для представления времени отсечения груза ULD $j$.
Время прибытия рейса: это время, к которому груз на рейсе становится доступным для получения на складе назначения. Давайте используем $T_j^+$ для представления времени прибытия рейса ULD $j$

Источник и назначение

Введем еще один набор $J_i$ , который мы определим как набор рейсов, чей источник и назначение совпадает с отправлением и получением груза $i$ . Другими словами, если отправление 85 имеет происхождение из Гонконга и пункт назначения в Лондоне, то $J_{85}$ - это набор всех ULD с отправлением из Гонконга и пунктом назначения в Лондоне.
Теперь мы можем использовать $j in J_i$ для получения набора ULD, который совпадает с торговым путем отгрузки $i$ , или мы можем использовать $j notin J_i$ для получения набора ULD, который не совпадает. Чтобы запретить привязку груза к ULD, который не соответствует его источнику и назначению, просто ограничим $x_{i,j}=0$ для всех таких рейсов. Ограничение полностью описывается так:

$sum_{j notin J_i} x_{i,j}=0 quad forall i in I$

Сроки поставки

При работе с временными метками в оптимизации удобно представлять нужные моменты как время Unix. Плюсы подхода:

Хранение дат как чисел.
Не нужно обрабатывать часовые пояса.
Решатель использует прямые сравнения «больше-меньше».

Рейс должен прибыть до срока доставки груза:
$sum_{j in J_i}T_j^+x_{i,j}<=Q_i^+ quad forall i in I quad$
Обратите внимание, что так же, как и для вышеприведенное ограничение по отправлению и назначению, мы указали, что это ограничение действует только для ULD в наборе $J_i$ , где $J_i$ - это набор ULD, которые совпадают с отправлением и получением отгрузки $i$ . Вот и все! Посмотрим на всю модель.

Полная модель

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

Параметры

$I$ : Набор всех отправлений. Одна отправка представлена $i$
$J$ : Набор всех ULD. Индивидуальный ULD представлен в нижнем регистре $j$ .
$J_i$ : Набор всех ULD, которые совпадают с отправителем и получателем груза $i$ .
$g_i$ : Вес брутто отгрузки $i$ в килограммах.
$v_i$ : Объем в кубических метрах отгрузки $i$
$c_j^E$ : Коэффициент перегрузки ULD $j$ в долларах США за килограмм
$U_j^M$ : Максимальная весовая вместимость ULD $j$ в килограммах
$U_j^V$ : Максимальная объемная мощность ULD $j$ в кубических метрах
$U_j^P$ : Стандартный вес ULD $j$ в килограммах

$T_j^-$ : Допустимое время доставки к терминалу ULD $j$ .
$T_j^+$ : Время прибытия ULD $j$ .
$Q_i^-$ : Время готовности к отгрузке $i$ .
$Q_i^+$ : Срок доставки $i$ .

Переменные решения и целевая функция:
$y_j$ : Общий вес по ULD $j$
$y_j^E$ : Перегрузка ULD $j$ в килограммах.
$x_{i,j}$ : 1 если отправка $i$ назначена ULD $j$ , 0 в противном случае.

Целевая функция

$text{Minimize} sum y_j^Ec_j^E$

Ограничения

$y_j$ - общий вес отправлений по ULD $j$: $y_j=sum_{i in I} g_ix_{i,j} quad forall j in J$
Дополнительный вес jE это max(0, yj-UjP):
$y_j^E >=y_j-U_j^P quad forall j in J$
$y_j^E >=0 quad forall j in J $
Каждая поставка должна быть назначена ровно на 1 ULD: $sum_{j in J} x_{i,j}=1 quad forall i in I$ .
ULD $j$ не может превышать максимальный вес: $y_j<=U_j^M quad forall j in J$
ULD $j$ не может превышать максимальную вместимость: $sum_{i in I}x_{i,j}v_i <=U_j^V quad forall j in J$

Дальнейшие шаги

В этой статье описывается математическое программирование, лежащее в основе назначения груза полету. Но просто записать математику недостаточно. Следующий шаг - реализация программы, вероятно, в AML, как Pyomo, или с использованием собственного API решателя, например, Python API Gurobi. После этого разработчик напишет код для передачи параметров всех доступных отправлений и рейсов. Затем экземпляр модели отправляется решателю. Решатель установит значения переменных решения оптимальным образом. Затем разработчик должен что-то сделать со значениями переменных принятия решений.

Автор: Иван Новиков

Источник

Информация

Обсуждаемое

Рекомендуем