Planning product supplies for the year, taking into account minimizing transportation costs

Толық мәтін

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

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

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

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

На сегодняшний день существует программное обеспечение, использующее методы математического моделирования в управлении поставками, такие, как Forecast NOW, ConsID, GoodsForecast.Replenishment, GoodsForecast.Distribution, TMS Логистика.  Все они направлены на оптимизацию задач бизнеса и минимизацию затрат, но не учитывают специфику задач планирования для госучреждений и госпредприятий – необходимо бесперебойное обеспечение всех потребителей, даже в тех случаях, когда это может быть экономически не оправдано, что не позволяет применить их для решения задачи в заданном контексте.

В литературе рассматриваются транспортные задачи с различными их модификациями: в классической постановке [1, 2, 3]; с дополнительными ограничениями [4, 5]; как многокритериальные оптимизационные задачи [6, 7]. Также рассматриваются задачи маршрутизации транспорта [8, 9, 10, 11], но они не решают задачу планирования на период (например, на год) с учетом доступности/недоступности потребителей в определенные сезоны. Таким образом, в данной статье предлагается алгоритм формирования плана поставки товаров от поставщиков до потребителей (с учетом временной недоступности некоторых из них) в течение года или в более общей постановке – в течение заданного периода таким образом, чтобы потребление было непрерывным.

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

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

$F\left(r\right)=\underset{i=1}{\overset{m}{}}\underset{j=1}{\overset{n}{}}\left(c_{ij}{r}_{ij}\right)\to min$   (1)

при ограничениях

$\left\{\begin{array}{c}\underset{j=1}{\overset{n}{}}\left(g_{ij}{r}_{ij}-z_{ij}\right)=a_i,i=\overline{\mathrm{1,}m}\\ \underset{i=1}{\overset{m}{}}\left(g_{ij}{r}_{ij}-z_{ij}\right)=b_j,j=\overline{\mathrm{1,}n}\\ \underset{j=1}{\overset{n}{}}{r}_{ij}{t}_{ij}\le s, i=\overline{\mathrm{1,}m}\\ g_{ij}{r}_{ij}-z_{ij}>\mathrm{0,} i=\overline{\mathrm{1,}m}, j=\overline{\mathrm{1,}n}\\ r_{ij}\ge \mathrm{0,} i=\overline{\mathrm{1,}m}, j=\overline{\mathrm{1,}n}\\ z_{ij}>\mathrm{0,} i=\overline{\mathrm{1,}m}, j=\overline{\mathrm{1,}n}.\end{array}\right.$   (2)

Здесь считаем, что $c_{ij}-$ транспортные расходы из i-го пункта в j-й пункт; $r_{ij}-$ количество рейсов, произведенных в течение текущего промежутка; $t_{ij}-$ время, за которое выполняется один рейс; $g_{ij}-$ грузоподъемность транспорта;

$z_{ij}=g_{ij}{r}_{ij}-x_{ij}$   93)

где $x_{ij}-$ объем перевозимого груза из i-го пункта в j-й пункт, т.е. это объем груза, которого не хватит до полной загрузки транспорта; $s-$ длина промежутка времени; $b_j-$ объем заявок; $a_{\text{i}}-$ объем запасов; $m-$ число складов; $\text{n}-$ число пунктов потребления.

Математическая модель (1), (2) представляет собой модель транспортной задачи (Т-задачи), зависящей от количества рейсов, с ограничением по времени. Все координаты решения данной задачи должны принадлежать множеству целых неотрицательных чисел. В связи с этим количество вычислений может быть гораздо больше, чем в обычных задачах линейного программирования без условия на целочисленность. Так как количество переменных здесь $2\times m\times n$, то при достаточно больших значениях  время решения задачи может существенно увеличиться.

Для ускорения расчетов сократим количество переменных модели (1), (2). Согласно равенству (3), перейдем от переменных $r_{ij}$ и $z_{ij}$ к $x_{ij}$, тем самым незначительно увеличив погрешность расчета (погрешность данной процедуры составляет $z_{ij}$). После преобразований целевая функция примет вид:

$\underset{i=1}{\overset{m}{}}\underset{j=1}{\overset{n}{}}\frac{c_{ij}}{g_{ij}}{x}_{ij}\to min,$   (4)

а ограничения:

$\left\{\begin{array}{c}\underset{j=1}{\overset{n}{}}{x}_{ij}=a_i, i=\overline{\mathrm{1,}m},\\ \underset{i=1}{\overset{m}{}}{x}_{ij}=b_j, j=\overline{\mathrm{1,}n},\\ \begin{array}{c}\underset{j=1}{\overset{n}{}}\frac{t_{ij}}{g_{ij}}{x}_{ij}\le s, i=\overline{\mathrm{1,}m},\\ x_{ij}>\mathrm{0,} i=\overline{\mathrm{1,}m},j=\overline{\mathrm{1,}n}.\end{array}\end{array}\right.$.  (5)

Заметим, что при округлении на прошлых этапах условие баланса Т-задачи частично не соблюдается. Возникает случай, при котором сумма запасов незначительно превышает сумму запросов, для учета данного случая преобразуем ограничения (4) и получим:

$\left\{\begin{array}{c}\underset{j=1}{\overset{n}{}}{x}_{ij}\le a_i, i=\overline{\mathrm{1,}m},\\ \underset{i=1}{\overset{m}{}}{x}_{ij}=b_j, j=\overline{\mathrm{1,}n},\\ \begin{array}{c}\underset{j=1}{\overset{n}{}}\frac{t_{ij}}{g_{ij}}{x}_{ij}\le s, i=\overline{\mathrm{1,}m},\\ x_{ij}>\mathrm{0,} i=\overline{\mathrm{1,}m},j=\overline{\mathrm{1,}n}.\end{array}\end{array}\right.$   (6)

Задача (4), (6) содержит в два раза меньше переменных, чем первоначальная модель, что поможет ускорить процесс вычисления. Кроме того, если количество перевозимого груза считается в единицах массы, то такая задача является классической задачей линейного программирования, в которой переменные принадлежат множеству действительных чисел, и это еще более ускорит процесс вычисления. Но, так как в настоящей работе мы считаем, что затраты и время перевозки вычисляются по количеству рейсов, то модель (1), (2) дает нам более точное решение, чем модель (4), (6).

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

2. Алгоритм. Как известно, чтобы Т-задача имела решение, необходимо, чтобы выполнялось условие баланса – общий объем заявок должен быть равен суммарному объему товаров на складах. Поэтому для годового плана, а также для всех периодов, необходимо выполнение условие баланса, то есть нужно привести исходные данные по наличию и заявкам к такому виду, чтобы Т-задача решалась корректно в каждом периоде. Простым делением количества запасов и заявок на $l$ периодов здесь невозможно обойтись, так как в определенных периодах некоторые потребители могут быть недоступными, то есть количество промежутков для поставки товаров этим потребителям меньше, чем $l$.

На основе выше сказанного алгоритм состоит из двух этапов: 1) подготовительный; 2) решение Т-задачи с ограничением по времени.

2.1. Первый этап. На первом этапе предлагается равномерно распределить годовые запасы и запросы по периодам с учетом недоступности потребителей в определенные периоды, что с экономической точки зрения наиболее реально.

Пусть необходимо распределить годовой план на $l$ периодов равномерно. Необходимо перераспределить товар, который предназначен для потребления в недоступные периоды, на доступные периоды, то есть нужно сделать так, чтобы суммарный объем запросов за все периоды каждого отдельного потребителя был равен годовому объему запросов этого потребителя; аналогичное условие и для поставщиков. При этом должно быть выполнено условие баланса: годовой запас товара у поставщиков должен быть равен общему годовому объему запросов.

Алгоритм распределения товаров включает в себя несколько шагов:

• равномерно распределяем запросы каждого потребителя по периодам;
• для каждого потребителя, у которых есть недоступные периоды (назовем их «закрытыми»), подсчитываем объем товара, который должны перебросить на каждый доступный период («открытый» период), предшествующий «закрытому», и производим перераспределение объема товара с каждого «закрытого» периода каждого такого потребителя на все предшествующие «открытые»;
• равномерно распределяем запасы по периодам;
• перебрасываем равномерно весь товар с «закрытых» периодов первого потребителя для всех поставщиков, то есть объем перебрасываемого товара в соответствующем «закрытом» периоде нужно разделить на количество поставщиков и количество предшествующих открытых периодов, затем полученный объем добавить к каждому поставщику во всех предшествующих «открытых» периодах.
• далее повторяем 4 этап для каждого следующего потребителя, у которых были «закрытые» периоды.

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

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

Пример. Рассмотрим простейший пример перераспределения товаров между поставщиками и потребителями по периодам.

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

 

Рис. 1. Годовой план перевозки товаров

 

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

• в первом периоде все потребители доступны;
• во втором периоде недоступен пункт ${\text{B}}_4$;
• в третьем периоде недоступны пункты $B_2$ и ${\text{B}}_4$;
• в четвертом периоде все потребители доступны.

Согласно алгоритму сначала распределяем запросы равномерно по всем периодам, рисунок 2(а). Затем перебрасываем товар из ячейки (3,2) во все ячейки столбца ${\text{B}}_2$, соответствующим периодам, предшествующим третьему, в размере $2900/2 периода=1450$. Аналогично поступаем с ${\text{B}}_4$: перебрасываем товар со второго и третьего периодов в первый в размере $2600/2 периода=5200$. Ячейки, расположенные после недоступных периодов, не изменяем.

 

Рис. 2. Перераспределение заявок с учетом «закрытых» периодов у поставщиков ${\mathbf{\text{B}}}_{\mathbf{2}}$ и ${\mathbf{\text{B}}}_{\mathbf{4}}$

 

Далее перераспределяем товар по складам, рисунок 3. На этом шаге также сначала распределяем его равномерно по периодам, рисунок 3(а). Затем перебрасываем в ячейки первого и второго периодов весь товар из клеток третьего периода в размере $1450/3 склада=\mathrm{483,33}$. Аналогично перебрасываем товар из ячеек третьего и четвертого периодов в ячейки первого периода в размере $5200/3 склада=\mathrm{1766,66}$. В результате получили план хранения товаров у поставщиков на складах и подачи заявок на товар в каждом периоде.

 

Рис. 3. Перераспределение запасов с учетом «закрытых» периодов у поставщиков ${\mathbf{\text{B}}}_{\mathbf{2}}$ и ${\mathbf{\text{B}}}_{\mathbf{4}}$

 

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

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

 

Рис. 4. Таблицы значений объемов запасов и заявок в каждом периоде

 

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

На этом первый этап алгоритма заканчивается.

2.2. Второй этап. На втором этапе решается транспортная задача с ограничением по времени в каждом периоде [12]. В данном случае именно период и накладывает ограничение по времени. Как было уже сказано ранее, при использовании модели (1), (2) на этом этапе могут возникнуть проблемы, связанные с большой размерностью задачи. Так, задача 5х12 содержит 120 переменных, это приводит к тому, что время расчетов значительно увеличивается. Особенно это становится заметным, когда достаточно много периодов поставки в году, например, планирование осуществляется по месяцам, неделям.

Если не требуется высокой точности результата, то есть достаточно получить решение хотя бы близкое к оптимальному, то предлагается применить задачу (4), (6), которая решается быстрее, но дает квазиоптимальное решение. Ниже представлен код описания и решения поставленной задачи по второй модели на языке Python.

Листинг 1. Описание и решение модели (4), (6)

# Создаем модель

    model = LpProblem("transport-problem-with-critical-time", LpMinimize)

    # Инициализируем переменные решения:

    X = {} # Будет хранить количества рейсов каждого маршрута

    for a in A:  # Заполняем словари переменными

        for b in B:

            var_name = "x_" + a + "_" + b  # Название переменной

            X[a, b] = pulp.LpVariable(var_name, lowBound=0, cat="Integer") # Инициализация переменной

    # Задаем целевую функцию

    lst_mult = [C[key] / G[key] * var for key, var in X.items()]

    obj_expression = pulp.lpSum(lst_mult)

    model.setObjective(obj_expression)  # Добавили в модель

    for a in A:  # Создаем ограничение для каждого поставщика

        constr_name = f"{a}_constraint"  # Название ограничения

        lst_vars = [X[a, b] for b in B]

        model += pulp.lpSum(lst_vars) <= expenses[a], constr_name # Все запасы должны быть использованы

        constr_name = f"S{a}_constraint"  # Название ограничения

        lst_vars = [X[a, b]  * T[a, b] / G[a, b] for b in B]

        model += pulp.lpSum(lst_vars) <= s, constr_name  # Затраты по времени каждого поставщика должны не превышать s

    for b in B:  # Создаем ограничение для каждого потребителя

        constr_name = f"{b}_constraint"  # Название ограничения

        lst_vars = [X[a, b] for a in A]

        model += pulp.lpSum(lst_vars) == expenses[b], constr_name # Все запросы должны быть удовлетворены

    # Решаем задачу оптимизации с помощью решателя

    if timeCalculation != 0:

        model.solve(PULP_CBC_CMD(msg=1, maxSeconds=math.ceil(timeCalculation/periodCount)))

    else:

        model.solve()

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

Авторлар туралы

Tatyana Malanova

Irkutsk national research state technical university

Хат алмасуға жауапты Автор.
Email: malanova_tanya@mail.ru
ORCID iD: 0000-0002-1586-2530

candidate of technical sciences, associate professor at software engineering center

Ресей, Irkutsk

Sergey Bakhvalov

Irkutsk national research state technical university

Email: bsv@istu.edu
ORCID iD: 0009-0009-8396-1926

candidate of technical sciences, associate professor at software engineering center

Ресей, Irkutsk

Danil Yanhaev

Irkutsk national research state technical university

Email: yanhaev2000@gmail.com

Master's student

Ресей, Irkutsk

Vadim Arshinsky

Irkutsk national research state technical university

Email: arshinskyv@istu.edu
ORCID iD: 0000-0001-7832-1582

candidate of technical sciences, associate professor at software engineering center

Ресей, Irkutsk

Әдебиет тізімі

Қосымша файлдар