MODELING TRANSPORTATIONS BY A SEVERAL TYPES OF TRANSPORT

Full Text

Задача планирования перевозок на транспортной сети несколькими видами транспорта предполагает возможность выбора транспорта для каждого маршрута перевозки товара от конкретного источника к определённому потребителю и его смены в процессе осуществления перевозки, а также учёт связанных с этим издержек, что отличает её от известной в литературе трипланарной транспортной задачи [1]. Такая постановка задачи описывает реальную ситуацию, возникающую на производстве, когда из-за особенностей транспортной инфраструктуры невозможно (или невыгодно) доставить товар потребителю одним видом транспорта. Количество различных вариантов организации перевозок затрудняет получение оптимального плана эмпирическим путём или с помощью экспертных оценок [2]. Это обусловливает необходимость применения математических моделей, методов и вычислительной техники для её решения [3]. Постановка задачи Пусть планируется перевозка гомогенного делимого товара со складов с известными запасами к магазинам с фиксированными спросами посредством нескольких видов транспорта по транспортной сети с промежуточными вершинами, в которых может происходить выбор и сопряжённая с затратами смена вида транспорта, используемого для перевозки. Задача заключается в отыскании такого плана перевозок, который минимизирует суммарные затраты, обеспечивает спрос магазинов и баланс запасов и вывоза для складов. Модель будет выглядеть следующим образом (формулы 1-5): ,(1) (2) , , (3) , (4) , (5) где: I0={ai | i= } - склады, J0={bj | i=} - магазины, ai - запас на i-ом складе, bj - спрос j-ого магазина, K={kl} - вид транспорта, cijk - тариф на перевозку из i в j транспортом k, xijk - объём перевозки из i в j транспортом k, dikр - тариф на перегрузку в узле i с транспорта p на k, yikр - объём перегрузки в узле i с транспорта p на k. I, J - множества всех узлов транспортной сети. Так на графе (рис. 1) из узла i=2 в узел l=2 можно переместиться только первым типом транспорта, а из узла l=4 в узел l=5 - только вторым. Здесь сплошными линиями обозначены коммуникации, на которых доступен первый тип транспорта, пунктирными - коммуникации, на которых доступен второй тип транспорта. Для каждой дуги (h,q) и каждого вида транспорта k задан тариф chqk на перевозку товара по этой дуге транспортом k. Смена транспорта также связана с дополнительными затратами: для каждого узла l и каждой пары (k,p) видов транспорта обозначим эти затраты dlkp. Построение вспомогательного графа Для решения поставленной задачи сведём её к задаче о потоке минимальной стоимости [4] на специальным образом построенном вспомогательном графе. Для каждого из K видов транспорта составим отдельный транспортный граф (рис. 2). Будем говорить, что граф для k-го вида транспорта имеет уровень k. Для наглядности на рис. 2 показаны графы для двух типов транспорта k и p≠k. В общем случае получим K таких графов по количеству видов транспорта. Следует оговорить, что вершины lk и lp, также как и вершины ik и ip, jk и jp, географически являются одними и теми же пунктами, а разные графы отражают только возможность перевозки различными видами транспорта k и p. Построим такие графы для каждого из K видов транспорта. Смена транспорта k на какой-либо другой вид транспорта p≠k сопряжена с затратами dlkp. Для каждой вершин l, где возможна смена транспорта k на p добавим дополнительную дугу, соединяющую эту вершину графа уровня k с аналогичной вершиной графа уровня р. Таким образом, если общее количество промежуточных вершин транспортной сети в исходной задаче составляет=L-m-n, то получим граф с K∙ вершинами, где K - количество различных видов транспорта. Далее присоединим к получившемуся графу n вершин, соответствующих продавцам i, и m вершин, соответствующих покупателям j (рис. 3). Тогда получаем граф, состоящий из (K∙+m+n)= вершин. При этом следует отметить, что на пропускные способности дуг, которые ведут от продавцов к промежуточным вершинам, нужно наложить ограничения вида (6), которые означают, что нельзя вывести больше товара, чем есть у продавца. . (6) Рис. 1. Транспортная сеть с возможностью изменения вида транспорта: l - промежуточные пункты транспортной сети, i - продавцы, j - покупатели (объяснения в тексте) Рис. 2. Графы для двух видов транспорта (объяснения в тексте) Рис. 3. Вспомогательный граф для двух видов транспорта (объяснения в тексте) Аналогичные ограничения накладываются на те дуги, которые соединяют промежуточные пункты с потребителями. Так как задача строится на графе, необходимо ввести условие баланса: для промежуточных вершин сумма всех входящих в них потоков должна быть равна сумме выходящих из них потоков [5]. Но для продавцов и потребителей сохраняется условие полного насыщения спроса и вывоза всего объёма товаров. Таким образом, условия задачи могут быть записаны в виде (7): (7) Ко всем продавцам искусственно присоединяют источник S, причём цены на транспортировку из источника к продавцам будут нулевыми, а пропускные способности дуг равны ai. Аналогично вводится сток Т, который соединён со всеми покупателями, транспортные тарифы здесь опять же равны нулю, а пропускные способности дуг равны bj. Пропускные способности всех остальных дуг равны 0. Веса дуг для графов отдельных уровней равны транспортным тарифам chqk. Остальным дополнительным дугам придаются веса dlkp, равные затратам на смену вида транспорта в узле. Исходная задача эквивалентна задаче о потоке минимальной стоимости заданной величины из фиктивного источника S в фиктивный сток Т на построенном графе. Задача о потоке минимальной стоимости Необходимо найти поток из источника S в сток T, имеющий заданную величину v и обладающий минимальной стоимостью. Тогда ограничения на пропускные способности будут иметь только дуги, которые идут от источника к продавцам и от покупателей к стоку, то есть пропускные способности дуг из источника s к i-ому продавцу равны его запасу ai, а пропускная способность дуги от j-ого потребителя к стоку t равна его спросу bj. Для всех остальных дуг, соединяющих промежуточные вершины между собой и с продавцами, и потребителями, пропускные способности будут бесконечны, как указано в формулах (8-10): , (8) , (9) . (10) Формально задача ставится следующим образом (формула 11): (11) При этом подразумевается, что величина v не превышает величины максимального потока, иначе задача не имеет решения [6]. Будем полагать величину потока равной (формула 12): . (12) Задача планирования перевозок несколькими видами транспорта, приведённая к виду задачи о потоке минимальной стоимости, строится на графе (рис. 4). Эквивалентную задачу о потоке минимальной стоимости заданной величины (MCFP) рекомендуется решать алгоритмом Басакера-Гоуэна либо алгоритмом Клейна. В случае применения алгоритма Басакера-Гоуэна скорость работы алгоритма составит O((L'r+m+n)2|V|v), тогда как при выборе алгоритма Клейна вычислительная сложность составит O((L'r+m+n) |V|2С) [7; 8]. Результаты численных экспериментов Экспериментальное применение модели к практическим нуждам транспортировки товара предприятия оптово-розничной торговли показало снижение денежных издержек (совокупности затрат на бензин и почасовую оплату труда) за приемлемое время в разовых экспериментах (табл. 1). Модель была реализована в среде Turbo Delphi как десктопное приложение. Рис. 4. Задача о потоке минимальной стоимости (объяснения в тексте) Таблица 1 Результаты применения модели перевозок несколькими видами транспорта № п/п Кол-во складов, шт. Кол-во магазинов, шт. Кол-во промежуточных вершин, шт. Кол-во видов транспорта, шт. Объём товара, уп. Процент уменьшения совокупных затрат на перевозку, % Полное время работы программы, сек. n m L' r v t 1 1 3 84 2 960 15,06 113 2 3 25 126 2 1 800 17,32 328 3 5 23 183 3 2 950 14,22 453 Исследована модифицикация модели с наложением дополнительного условия целочисленности на товар. В реальной логистической задаче перевозки товаров с оптовых складов в магазины применение такой модели обеспечило снижение затрат лишь на 0,75-1,02 % по сравнению с уже описанной в литературе моделью и потребовало слишком больших временных и ресурсных затрат рабочих компьютеров, что на настоящий момент затрудняет применение предлагаемой нами модели.

About the authors

Anastasiya Dmitrievna Ivanova

Samara University

Email: hudoj-nik@mail.ru
443086, Russia, Samara, Moskovskoye Shosse, 34

References

Supplementary files