Унифицированная методика оптимизации маршрутов в цепях поставки товаров
Одна из актуальных задач логистики - организация оптимальной транспортировки людей и материальных ценностей. Как правило, для решения самого широкого круга оптимизационных задач в логистике используются модели линейного (ЛП) и целочисленного программирования (ЦП). Задача маршрутизации автотранспортных средств осуществляется простыми и эффективными методами эвристики, позволяющими быстро найти нужное решение. Однако она не гарантирует нахождение оптимального решения. В настоящее время разрабатываются методы, которые объединяют гибкость эвристики и строгость моделей линейного программирования, что позволяет получить оптимальное или, по крайней мере, доказуемо лучшее решение. Один из эффективных методов, позволяющих находить оптимальное решение при маршрутизации перевозок мелкопартионных грузов, предложенный J.F.Shapiro [1], получил название унифицированной методики оптимизации.
На рис. 1 представлена логика унифицированной методики оптимизации для задачи локальных поставок. Сначала используют методы эвристики для создания одного или более возможных решений маршрутизации, т.е. набора допустимых развозочных или сборных маршрутов. В качестве стоимости решения рассматриваются общие транспортные издержки, представляющие собой сумму постоянных (накладных) затрат за определенный период (например, за день) для каждой единицу подвижного состава и переменных затрат на 1 километр пробега. Затем переходят к модели линейного программирования, содержащей допустимые маршруты, созданные с помощью эвристики, и оптимизируют ее. Эта модель ищет пути минимизации общей стоимости маршрутов, требующих посещения клиентов лишь один раз, но и дает нереальные комбинации, такие как «использование 0,4 маршрута j и 0,6 маршрута k». Для исключения дробных частей используется модель целочисленного программирования, оптимизация которой позволяет получить строгое решение задачи маршрутизации автотранспортных средств.
Рис. 1. Унифицированная методика оптимизации для задачи локальных
поставок
Наряду с эвристикой при формировании допустимых маршрутов используются возможности линейного программирования, точнее строится и оптимизируется модель двойственная к основной модели линейного программирования. Первоначально в нее включаются все допустимые маршруты, найденные с помощью эвристики. Оптимизация этой модели заключается в максимизации общего вознаграждения за включение допустимых маршрутов в окончательное решение. Вознаграждение равно разнице валового дохода и затрат маршрута. Валовой доход равен сумме двойственных (теневых) цен для обслуженных клиентов. Если общее вознаграждение конкретного маршрута положительно, то этот маршрут добавляется в модель линейного программирования. С другой стороны, если общее вознаграждение равно нулю, то можно сказать, что нет допустимых маршрутов для добавления в модель линейного программирования.
Аннотация книги профессора Шапиро с примерами моделей SCM-класса представлена на сайте http://www.scm-models.com/, поэтому от изложения теории унифицированной методологии оптимизации перейдем к практике ее применения. Исследуем возможность использования предложенного алгоритма при решении задачи маршрутизации перевозок мелкопартионных грузов в городе.
Для примера возьмем предприятие пищевой промышленности Санкт-Петербурга некую производственно-торговую фирму «Т&Л», производящее продукты быстрого приготовления и мороженное, и его сеть обслуживания, ограниченную центральным районом города. Обслуживание клиентов фирма «Т&Л» осуществляет со склада, расположенного по адресу Кузнецовская ул. 52. Фирма располагает собственным парком подвижного состава, в.ч. автомобилями ГАЗ 33021 с изотермическими кузовами объемом 160 транспортных единиц[1] в достаточном количестве. Использование каждой единицы подвижного состава обходится фирме в 350,0 руб. постоянных расходов в день и 6,0 руб. переменных расходов на 1 км пробега. Клиенты предъявляют определенные требования по времени доставки товара, которые должны быть учтены в расчетах. Кроме того, заказы не могут быть разбиты между двумя или более грузовиками и каждый клиент может быть посещен только один раз. Задача состоит в составлении маршрутов таким образом, чтобы все ограничения были соблюдены при минимальных общих затратах.
Для формирования допустимых маршрутов воспользуемся возможностями программы Деловая карта, разработчиком которой является ООО «Фирма «ИНГИТ». Эта программа, относящаяся к классу географических информационных систем, позволяет решать разнообразные задачи транспортной логистики, в том числе осуществлять маршрутизацию перевозок мелкопартионных грузов. На рис. 2 представлена сформированная таблица заказов, в которую внесены адреса погрузки, выгрузки, ограничения по количеству груза и по времени его доставки потребителям.
Рис. 2. Таблица заказов фирмы «Т&Л»
На основании информации заполненной в таблице заказов осуществляется автоматический расчет маршрутов для имеющегося в распоряжении транспорта. Для сохранения результатов расчета в таблице заказов имеются поля: «Время погрузки», «Время разгрузки», «Номер машины», «Номер точки загрузки» и «Номер точки разгрузки». Программа «Деловая карта» обеспечивает выбор одного из четырех способов предварительного расчета маршрутов. Это алгоритмы, которым в соответствии с их свойствами присвоены следующие названия - «Начинать с отдаленных точек», «Выбирать попутные заказы», «Определять дальние направления» и «Искать самые выгодные совмещения». После предварительной раскладки заказов по машинам и оптимизации порядка их следования осуществляется дополнительная оптимизация путем попыток переноса заказов с одной машины на другую. Воспользуемся возможностями всех четырех алгоритмов оптимизации для формирования набора допустимых маршрутов.
Для получения первого возможного решения задачи маршрутизации установим в качестве способа предварительного расчета маршрутов - «Искать самые выгодные совмещения». Результаты расчета маршрутов представлены на рис. 3 и в табл. 1.
Рис. 3. Первый вариант расчета развозочных маршрутов фирмы «Т&Л»
Таблица 1
Возможное решение задачи маршрутизации № 1
Маршрут
Клиенты
Протяженность, км
Затраты, руб
1
0-4-1-0
19,1
464,6
2
0-9-6-16-19-5-18-0
20,4
472,4
3
0-13-10-2-0
16,7
450,2
4
0-3-15-0
13,4
430,4
5
0-12-17-11-8-14-7-0
23,2
489,2
Сумма
2306,8
Таким образом, первое возможное решение задачи маршрутизации дает нам величину транспортных издержек равную 2306, 8 руб.
Второе возможное решение задачи маршрутизации получим, установив в качестве способа предварительного расчета маршрутов - «Начинать с отдаленных точек». Результаты расчета маршрутов представлены на рис. 4 и в табл. 2.
Рис. 4. Второй вариант расчета развозочных маршрутов фирмы «Т&Л»
Таблица 2
Возможное решение задачи маршрутизации № 2
Маршрут
Клиенты
Протяженность, км
Затраты, руб
6
0-2-1-0
20,0
470,0
7
0-17-19-5-18-0
21,7
480,2
8
0-4-13-10-0
19,1
464,6
9
0-7-9-11-6-16-8-14-0
19,5
467,0
10
0-3-15-12-0
15,9
445,4
Сумма
2327,2
Таким образом, второе возможное решение задачи маршрутизации дает нам величину транспортных издержек равную 2327,2 руб.
Третье возможное решение задачи маршрутизации получим, установив в качестве способа предварительного расчета маршрутов - «Выбирать попутные заказы». Результаты расчета маршрутов представлены на рис. 5 и в табл. 3.
Рис. 5. Третий вариант расчета развозочных маршрутов фирмы «Т&Л»
Таблица 3
Возможное решение задачи маршрутизации № 3
Маршрут
Клиенты
Протяженность, км
Затраты, руб
11
0-3-0
13,0
428,0
12
0-7-2-0
14,7
438,2
13
0-9-13-10-11-6-16-8-14-15-12-0
23,0
488,0
1
0-4-1-0
19,1
464,6
7
0-17-19-5-18-0
21,7
480,2
Сумма
2299,0
Таким образом, в третье возможное решение задачи маршрутизации включены рассчитанные ранее маршруты 1 и 7, величина транспортных расходов в этом случае - 2299,0 руб.
Для получения четвертого возможного решения задачи маршрутизации установим в качестве способа предварительного расчета маршрутов - «Определять дальние направления». Результаты расчета маршрутов представлены на рис. 6 и в табл. 4.
Рис. 6. Четвертый вариант расчета развозочных маршрутов фирмы «Т&Л»
Таблица 4
Возможное решение задачи маршрутизации № 4
Маршрут
Клиенты
Протяженность, км
Затраты, руб
14
0-12-17-16-14-1-0
25,8
504,8
4
0-3-15-0
13,4
430,4
15
0-9-6-19-5-13-18-0
20,6
473,6
16
0-4-8-11-10-0
20,3
471,8
12
0-7-2-0
14,7
438,2
Сумма
2318,8
Таким образом, в четвертое возможное решение задачи маршрутизации включены рассчитанные ранее маршруты 4 и 12, величина транспортных расходов в этом случае - 2318,8 руб. Окончательно мы имеем набор из 16 неповторяющихся маршрутов. Обращает на себя внимание также то, что третье возможное решение задачи маршрутизации дает минимум транспортных затрат, по сравнению с другими вариантами, равный 2299,0 руб.
Попытаемся улучшить найденное решение, используя методику профессора Шапиро. Во-первых, сформируем дополнительные маршруты путем разбиения маршрута 0-9-13-10-11-6-16-8-14-15-12-0 и добавления необслуженных клиентов данного маршрута к другим маршрутам. Получим еще три маршрута:
маршрут 17: 0-9-13-10-11-6-16-8-14-0, протяженностью 20,0 км, затраты на этом маршруте составят 470,0 руб;
маршрут 18: 0-7-2-18-0, протяженностью 15,4 км и затратами - 442,4 руб;
маршрут 19: 0-12-17-19-5-0, протяженностью 22,7 км и затратами - 486,2 руб.
Проверку выполнимости этих и других возможных маршрутов необходимо осуществлять средствами Деловой карты, выбрав в качестве способа предварительной раскладки заказов по маршрутам пункт «Восстановить по номерам точек».
Следующим этапом является построение и оптимизация модели линейного программирования для задачи локальных поставок фирмы «Т&Л» с 19 маршрутами. Эта модель, созданная в Excel, представлена на рис. 7.
Рис. 7. Прямая задача линейного программирования для модели
локальных поставок фирмы «Т&Л» с 19 маршрутами
Здесь целевой функцией являются общие затраты на перевозку, которые должны быть минимизированы. В целевую ячейку, в данном случае B28, занесена формула: B28=СУММПРОИЗВ(B5:T5;B26:T26). Ячейки в строке выбора маршрута соответствуют переменным xj, которые соотносятся с выбранным маршрутом j (xj=1) или неподходящим маршрутом j (xj=0), в случае модели линейного программирования значение удовлетворяет неравенству 0≤xj≤1.
Решение модели линейного программирования, представленное на рис. 7, является случайным целочисленным решением. Полученное решение показывает, что при выборе в качестве варианта маршрутизации маршрутов 1,4,17,18 и 19 значение общих затрат минимально и равно 2293,6 руб. Это лучше третьего возможного варианта маршрутизации всего на 5,4 руб., т.е. приблизительно на 0,2% удалось улучшить первоначальное решение, найденное с помощью эвристики. Проанализируем полученное решение, путем построения и оптимизации двойственной модели линейного программирования для модели локальных поставок фирмы «Т&Л». Методика построения и анализа двойственной модели линейного программирования изложены в специальной литературе по исследованию операций [2,3]. Полученное решение представлено на рис. 8.
Рис. 8. Двойственная задача линейного программирования для модели
локальных поставок фирмы «Т&Л» с 19 маршрутами
Данные, представленные на рис. 8 показывают, что отсутствуют маршруты с положительным значением в строке «Вознаграждение», следовательно, полученное решение является лучшим решением из того набора допустимых маршрутов, который включен в анализ. Строго говоря, оптимальным данное решение не является, поскольку мы не включили в анализ все допустимые маршруты. Для создания допустимых маршрутов необходимо вернуться к этапу применения эвристики и затем повторить все этапы рассмотренного алгоритма.
Проведенный пример использования унифицированной методики оптимизации маршрутов в цепях поставки товаров позволяет сделать следующие выводы. Во-первых, предложенный профессором Шапиро алгоритм оптимизации, действительно позволяет улучшить решение, найденное с помощью эвристики. Во-вторых, это решение может быть улучшено только при включении в модель линейного программирования дополнительных маршрутов, также найденных с помощью эвристики. В-третьих, вариантов выбора дополнительных маршрутов не так много ввиду того, что необходимо учитывать при формировании маршрутов разнообразные ограничения. Поэтому, получаемое «оптимальное» решение не всегда может улучшить значение целевой функции затрат по сравнению с тем значением, которое дает применение эвристики. В-четвертых, построение и использование моделей линейного программирования требует от разработчика основательных знаний в области исследования операций, а также значительных затрат времени. Следовательно, затраты на разработку этих моделей могут быть не сопоставимы с той экономией транспортных издержек, которую дает их использование. Это подтверждает вывод, сделанный в работе [1], в отношении предложенного алгоритма, обратите внимание на рис. 1 оптимальные маршруты могут быть получены непосредственно после решения задачи маршрутизации методами эвристики.
Литература:
1. Shapiro, J.F. Modeling the Supply Chain. - DUXBURY, Thomson Learning, 2001. - 586 p.
2. Волков И.К., Загоруйко Е.А. Исследование операций: Учеб. для вузов / Под ред. В.С. Зарубина, А.П. Крищенко. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2000. - 436 с.
3. Таха, Хэмди, А. Введение в исследование операций, 6-е издание.: Пер с англ. - М.: Издательский дом «Вильямс», 2001. - 912 с.
/Бочкарев А. А. СПбГИЭУ ©/