Транспортные модели. 
Логистика городских транспортных систем

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

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

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

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

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

Методика решения данных задач подробно рассматривается в работах по исследованию операций и оптимизационному моделированию^[1].

Примеры типовых моделей задач транспортного типа.

Таблица 8.1

Наименование и цель задачи.	Математическая модель.	Условные обозначения.
Классическая транспортная задача Составить план перевозок товаров от поставщиков к потребителям, обеспечивающий минимальные транспортные затраты и спрос потребителей.		т — количество поставщиков (источников); п — количество потребителей (стоков); Су — стоимость перевозки единицы товара от /-го поставщика к у-му потребителю; 5, — предложение 1-го поставщика; О] — спрос у-го потребителя; Ху — объемы поставок товара от ?-го поставщика ку-му потребителю.

Наименование и цель задачи.	Математическая модел ь.	Условные обозначения.
Транспортная задача с промежуточными пунктами Составить план перевозок товаров от поставщиков к потребителям с учетом промежуточных пунктов (складов), обеспечивающий минимальные транспортные затраты и спрос потребителей.		./ — множество номеров складов, на которые товар может быть доставлен с к- го склада; / — множество номеров складов, с которых товар может быть доставлен на к-и склад; — стоимость перевозки единицы товара от 1-го до у-го пункта; 5, — исходное предложение 1-го поставщика; О) — исходный спрос у-го потребителя; Тк — величина чистого запаса товара, равная объему исходного предложения или исходного спроса; В — величина буферного запаса; д; — объемы поста; ч вок товара от ?-го до у-го пункта.
Задача о назначениях Распределить исполнителей по работам (назначить одного исполнителя на каждую работу) так. чтобы минимизировать суммарные затраты, связанные с выполнением всего комплекса работ.		п — количество видов работ и привлеченных исполнителей; Сц — стоимость выполнения 1-й работыу-м исполнителем; Хц — двоичные (булевы) переменные, которые соответствуют назначению кандидатов на выполнение работ.

Наименование и цель задачи.	М атематическая модел ь.	Условные обозначения.
Задача выбора кратчайшего пути Найти кратчайший путь из заданного г-го узла сети в заданный /-й узел.		п — количество узлов сети; Cjj — расстояние (стоимость, время проезда) от /'-го до j-го узла сети; Xjj — булевы переменные, которые и н тер прет и ру юте я следующ! 1 м образом: переменная х1у- = 1, если дуга (i, j) входит в искомый маршрут минимальной длины, и Xj j = 0, в противном случае.
Задача коммивояжера Построить такой маршрут обхода всехп пунктов (но одному разу каждого), при котором общая длина пути будет минимальной.		п — количество узлов сети; Су — расстояние (стоимость, время проезда) от ?-го до j-го узла сети; Xj j — булевы переменные, которые и нтерпретиру юте я следу Юнн 1 м образом: переменная Хц = 1. если дуга (/,/) входит в искомый простой цикл из п вершин (и, соответственно, п дуг) минимального общего веса (минимальной длины), и Xj j = 0 в противном случае; Uj — переменные — неограниченные действительные числа R (Real).

Наименование и цель задачи.	Математическая модель.	Условные обозначения.
Многопродуктовая транспортная задача Составить план перевозок нескольких неоднородных продуктов от поставщиков к потребителям, обеспечивающий минимальные транспортные затраты и спрос потребителей, при этом суммарный поток всех продуктов по дуге ограничен ее пропускной способностью.		тн — количество поставщиков (источников); п — количество потребителей (стоков); ? — количество продуктов; С{:к — СТОИМОСТЬ перевозки единицы ?-го продукта от ?-го поставщика ку-му потребителю; — предложение !-м поставщиком ?-го продукта; ?>у,* — спрос у-м потребителем ?-го продукта; м, — - — пропускная способность дуги (АД; х^.к ~ объемы поставок ?-го продукта от /-го поставщика ку-му потребителю.

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

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

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

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

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

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

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

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

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

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

Введем дополнительные переменные CjJ = 1,…, п, представляющие собой затраты на транспортировку на /-м маршруте, y_}, j = 1,…, и, принимающие значения у_} =1, если автомобиль / используется, и у_} =0, если автомобиль j не используется, и рассмотрим задачу математического программирования:

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

Целевая функция, описанная формулой (8.10), равна реальным транспортным расходам. Первая группа ограничений в системе (см. формулы (8.11)) гарантирует, что все клиенты будут обслужены. Вторая группа ограничений в системе (8.11) одновременно гарантирует обслуживание только арендованными автомобилями и удовлетворение условий грузоподъемности. Третья группа ограничений в системе (8.11) — ограничения на количество обслуживаемых одним автомобилем клиентов, которые косвенно учитывают ограничения по времени доставки, и, наконец, последние две группы ограничений — эго условия двоичности переменных х_{ —_} и у у Данная задача относится к классу обобщенных задач о назначениях (Generalized Assignment Problem, GAP).

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

• [1] Грешилов А. А. Математические методы принятия решений: учеб, пособие. М.: Изд-воМГТУ им. Н. Э. Баумана, 2006; Котиков С. Н. Математические методы в экономике: учеб, пособие / под. ред. Л. Г. Бурда. М. ;, 2017; Леоиенков А. В. Решениезадач оптимизации в среде MS Excel. СПб.; БХВ-Петербург, 2005; Мур Д., Уэдерфорд Л. Экономическое моделирование в Microsoft Excel: пер. с англ. 6-е изд. М.: ИД «Вильямс», 2004; Смагин Б. И. Экономико-математические методы; учебник. 2-е изд., испр. и доп., 2017.