Основной материал исследования.

УДК 519.863: 338.47

Шихеева Е.Д.

ОПТИМИЗАЦИЯ ПЛАНА ПЕРЕВОЗОК ТРАНСПОРТНОЙ ЗАДАЧИ С ИЗМЕНЯЮЩИМИСЯ ВО ВРЕМЕНИ НАЧАЛЬНЫМИ УСЛОВИЯМИ

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

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

Розглянуто побудову оптимального плану перевезень транспортної компанії, за якого прибуток транспортної компанії для розглянутого періоду часу набуває максимуму.

Ключові слова: транспортна задача, інтенсивність надходження прибутку, затрати на перехід між планами.

This article contemplates making a model of optimum plan of carrier company’s transportations, what maximize the profit of this company for concerned period of time.

Key words: transport problem, intensity of profit receipt, move between planes costs.

Постановка проблемы. Кризис мировой экономики приводит к значительному уменьшению объёмов производства и соответствующим образом влияет на процессы товарооборота, которые обеспечиваются процессом перевозки.

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

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

Обзор последних исследований и публикаций. Результаты исследований оптимальной организации перевозок сконцентрированы в работах [1], [2]. Современные направления изучения транспортной задачи поднимают следующие вопросы:

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

а) при минимизации суммарных затрат – это стоимость перевозки, предлагается минимаксный подход, обеспечивающий оптимальное решение в предположении о наихудшем законе распределения недетерминированной стоимости перевозок [3] или рассмотрение этой стоимости как нечетко-случайного числа [4];

б) при минимизации временных затрат – это продолжительности транспортировок [5];

2) многокритериальная оптимизация – рассмотрение классической транспортной задачи как модель класса многокритериальных задач [6];

3) проблема учёта изменения потребностей в грузе на промежутке времени. Данный вопрос рассматривается в [7]. В работе проводится исследование изменения потребностей в грузе в течение суток и на его основе определяется количество перевозок, необходимых в сутки. Предлагается последовательное решение транспортных задач, соответствующих каждой перевозке в отдельности. Если время доставки грузов превышает минимальный интервал, необходимый для возвращения выполняющих перевозку машин в пункт отправления, возникает ситуация, когда за время поставки появляется новая схема транспортной задачи [7]. В этом случае предлагается переходить к решению объединенной задачи, которая предусматривает учёт появившегося в процессе перевозки запроса на груз.

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

Нерешенные аспекты общей проблемы. Целью классической транспортной задачи [1] является построение наиболее экономичного плана перевозок однородного или взаимозаменяемого продукта из пунктов производства в пункты потребления, минимизирующего суммарные транспортные издержки (1) – (4):

(1)

, (2)

, (3)

, , (4)

или время, затраченное на перевозку (5) – (8) в модификации транспортной задачи по критерию времени [2]:

(5)

, (6)

, (7)

, , (8)

с условием баланса:

(9)

В первом случае - себестоимость перевозки единицы груза из пункта отправления в пункт назначения , а - количество груза, перевезенного пункта отправления в пункт назначения . В случае минимизации времени перевозки, - время, необходимое на перевозку груза из в , планирование (5) производится по минимуму времени осуществления наиболее длительной перевозки [2].

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

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

Исходя из этого, недостатками классической транспортной задачи является:

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

;

2) отсутствие учёта возможного изменения доходов в зависимости от плана перевозок;

3) отсутствие финансовых критериев (дохода , расходов ) в задаче на минимум времени:

.

В данной работе предполагается использовать интегральный показатель интенсивности поступления прибыли [8]:

 

 

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

Такое изменение критерия оптимальности в общем случае приводит к несовпадению планов, соответствующих критерию минимума суммарных транспортных издержек , минимума времени и максимума интенсивности поступления прибыли (табл.1, рис.1).

 

Таблица 1. Планы, соответствующие минимуму расходов и максимуму интенсивности прибыли

Минимизация расходов: , где - суммарные расходы на перевозку груза из всех пунктов производства во все пункты потребления; - план перевозки, , где - область допустимых решений. Если - оптимальный план задачи (1)-(4), то:

Максимум интенсивности прибыли: , - доходы от перевозок ; , где - план, максимизирующий . В общем случае (рис.1).

 

На рис.1 изображены зависимости следующих показателей от плана перевозок:

- расходов на выполнение перевозки,

- затрат времени на выполнение перевозки,

- прибыль за выполнение перевозки,

- интенсивность поступления прибыли за выполненные на протяжении периода перевозки:

(10)

Предполагается, что предприятие не работает в убыток: ,

при :

Рис.1. Несовпадение планов перевозок Х*, Х*** и Х**, соответствующих минимуму расходов, минимуму временных затрат и максимуму интенсивности прибыли

 

Так как в первой четверти функция возрастает по , следовательно, выражение (10) равносильно следующему:

Как видно из рис.1, планы перевозок, доставляющие минимумы расходам (Х*) и затратам времени (Х***) не совпадают с планом перевозок Х**, доставляющим максимум интенсивности прибыли, которому на графике соответствует максимальное значение .

4) отсутствие учёта затрат на переход от одного оптимального плана, служащего начальным состоянием системы ( - если перевозки ранее не осуществлялись) к следующему [9]. Эти затраты состоят из затрат на перемещение транспортных средств, выполняющих перевозки от пунктов потребления, в которые доставлялся груз по плану , к пунктам производства, из которых будет вывозиться груз по плану и затрат на хранение грузов, не вывезенных из пунктов производства или не ввезённых в пункты потребления вовремя.

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

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

7) отсутствует возможность оптимизировать маршруты транспортных средств, так как при расчёте оптимального плана не учитывается текущее местонахождение транспортных средств, совершавших рейсы по предыдущему плану перевозок .

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

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

 

Основной материал исследования.

Постановка задачи

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

 

Рис.2 Схема потоков перевозок между пунктами производства и потребления

 

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

 

1. Информация, порождающая внутренние условия

1.1. Производство груза в пунктах , описывается неубывающими функциями , , . Функция показывает суммарное количество груза, произведенного пунктом за период , то есть с момента начала отсчёта расчётного периода по момент включительно. Множество , состоит из моментов времени , в которые суммарное количество продукции , выпущенной пунктом за период , возрастает на величину партии выпущенной в момент :

,

Таким образом,

,

.

 

Рис. 3 График функции на промежутке

 

Мощность множества :

, ,

где - суммарное количество моментов времени , , в которые

,

то есть число раз, когда пункт производства выпускал очередную партию продукции . Очевидно, что для каждого пункта производства:

,

где - множество целых неотрицательных чисел.

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

1.2. Поступление заявок на груз в пунктах , описывается неубывающими функциями , , , аналогичными функциям пунктов производства (рис.3). Функция показывает суммарное количество запросов на груз, появившихся в пункте за период , то есть с момента начала отсчёта расчётного периода по момент включительно. Множество , состоит из моментов времени , в которые сумма всех запросов - , возникших в пункте за период , возрастает на величину запроса , возникшего в момент :

,

Таким образом,

,

.

Рис. 4 График функции на промежутке

 

Мощность множества :

, ,

где - суммарное количество моментов времени , , в которые

,

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

.

Запросы на груз, существующие либо возникшие в начальный момент времени обозначаем через , .

Множества , и , формируют множество :

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

,

,

,

.

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

Функции

, , и , ,

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

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

Каждой машине присвоен номер , , где - общее число транспортных средств компании.

Для , известны:

- тип машины , ;

- максимально возможная загрузка машины -го типа данным грузом - , ;

- эксплуатационная скорость движения для данного типа , .

Номера машин , сгруппированы по типам во множества , (, если машина относится к типу ). Так как мощность множеств равна количеству машин типа , соответствующего этому множеству, то верно равенство:

.

Очевидно также, что для выполняется равенство:

Ø.

Кроме машин, транспортная компания должна либо располагать собственной площадкой, предназначенной для хранения собственных транспортных средств во время, свободное от рейсов, либо арендовать стояночные места. Обозначим данное место стоянки через . Для построения модели работы транспортной компании можно без потери общности считать, что все транспортные средства компании могут храниться на одной площадке либо их арендованные стояночные места расположены на достаточно малом расстоянии друг от друга (иначе, вместо одного пункта вводится пунктов, в каждом из которых может осуществляться стоянка определённых машин транспортной компании с номерами соответственно. Чтобы исключить, при необходимости, возможность стоянки других машин транспортной компании в не предназначенных для них пунктах , следует приравнять среднесуточные затраты на стоянку таких машин в данных пунктах к +М).

 

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

2.1. Расстояния между пунктами производства и потребления - , , , .

2.2. Пропускные способности маршрутов между пунктами производства и потребления - , , .

2.3. Цены на покупку груза транспортной компанией в пунктах производства - , , ; :

, если транспортная компания работает в качестве перекупщика товара и её доход формируется как разность цен продажи и покупки товара в пунктах потребления и производства соответственно;

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

2.4. Цены на продажу груза транспортной компанией в пунктах потребления - , , :

, если транспортная компания работает в качестве перекупщика;

в случае, если транспортная компания и пункт потребления , для которого , работают на одного владельца.

2.5. Стоимость хранения единицы груза в пункте производства - , , ; .

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

2.7. Число заходов машин -го типа в пункт до момента - , , , .

2.8. Число заходов машин -го типа в пункт до момента - , , , .

2.9. Минимальное число заходов машин в пункт , необходимое для того, чтобы была составлена временная технологическая инструкция перегрузки (ВТИП) либо рабочая технологическая карта (РТК) соответственно: , .

2.10. Минимальное число заходов машин в пункт , необходимое для того, чтобы была составлена временная технологическая инструкция перегрузки (ВТИП) либо рабочая технологическая карта (РТК) соответственно: , .

2.11. Минимальная частота заходов машин в пункт , необходимая для того, чтобы была составлена временная технологическая инструкция перегрузки (ВТИП) либо рабочая технологическая карта (РТК) соответственно: , .

2.12. Минимальная частота заходов машин в пункт , необходимая для того, чтобы была составлена временная технологическая инструкция перегрузки (ВТИП) либо рабочая технологическая карта (РТК) соответственно: , .

2.13. Суточные расходы на содержание одной машины типа на ходу и на стоянке соответственно: , , .

 

Составление модели

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

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

1. партия груза, появившаяся в пункте в момент при существующем в этот момент запросе в пункте ;

2. запрос на груз, появившийся в пункте в момент при существующем в этот момент запасе в пункте ;

3. одновременное появление партии груза, произведённой в пункте и запроса на груз, появившегося в пункте в момент .

Совпадение интересов пунктов и происходит в момент и является основанием для перевозки.

Машина, которая по решению транспортной компании, должна совершать перевозку груза из в для удовлетворения интересов этих пунктов, совпавших в момент , перемещается по следующей схеме (рис.5):

Рис.5 Схема перемещения машины , совершающей перевозку из в , соответствующую совпадению интересов пунктов и в грузе в момент .

Заранее решается, что машина будет совершать перевозку по направлению , для удовлетворения совпавших в момент времени интересов. Это решение отражается значением булевой переменной:

, , , , .

- если соответствующая перевозка не осуществляется,

- если соответствующая перевозка осуществляется.

Для упрощения модели считаем, что при осуществлении перевозки , , , , машина , всегда использует максимальную загрузку , соответствующую её типу машин . Следовательно, количество груза, перевозимого машиной в момент равно:

Введем индекс :

(11)

1) если маши