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

Теория массового обслуживания является одним из разделов теории вероятностей. В последние годы она получила развитие и выделилась в самостоятельный раздел математики. Основоположником теории массового обслуживания является датский ученый А.К. Эрланг. Его первая работа по этому вопросу была опубликована в 1909 году.

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

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

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

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

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

Требование – это запрос на выполнение работы (погрузки-выгрузки, заправки топливом, ремонта, посадки в транспорт для поездки и другие).

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

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

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

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

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

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

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

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

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

< 1, (3)

где λ – средняя интенсивность входящего потока требований; ν – интенсивность обслуживания одним аппаратом в единицу времени; s –число обслуживающих аппаратов; p – коэффициент использования обслуживающей системы.

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

В соответствии с поведением требований системы подразделяются на три группы:

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

2. Система с ожиданиями, например, автомобиль ожидает погрузки;

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

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

Задача № 1

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

Составим данный исходный план в табл. 7.

Таблица 6
Матрица условий
Пункт назначения	Вспомогательные	Пункт назначения	Наличие груза, т.
Строка Столбец	B1	B2	B3	B4	B5	B6
А1
А2
А3
А4
Потребность в грузе, т.

Таблица 7

Данный исходный план

Пункт назначения

Вспомогательные

Пункт назначения

Наличие груза, т.

Строка Столбец

B1

B2

B3

B4

B5

B6

V1= 6

V2= 1

V3= -1

V4= 3

V5= 0

V6= 4

А1

U1= 0

А2

U2= 6

А3

U3= 3

А4

U4= 5

Потребность в грузе, т.

Транспортные расходы составят:

z = 5 ∙ 4 + 2 ∙ 12 + 5 ∙ 7 + 3 ∙ 6 + 4 ∙ 9 + 6 ∙ 6 + 5 ∙ 7 + 9 ∙ 4 + 11 ∙ 5 = 295

Решим задачу методом потенциалов. Т.к. m+n-1= 6 + 4 – 1 = 9 и имеем 9 загруженных клеток, план ацикличный. Пусть U_i и V_j - потенциалы i-го склада и j-го магазина соответственно.

Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения U_i+V_j=C_i,j, просматривая все занятые клетки. Получим:

U₁=0

V₆ =C_1,6 – U₁= 4

U₃ = C_3,6 – V₆ = 3

V₁ = C_3,1 – U₃ = 6

U₂ = C_2,1 – V₁ = 6

V₂ = C_2,2 – U₂ = 1

V₄ = C_3,4 - U₃ = 3

V₅ = C_2,5 – U₂ = 0

U₄ = C_4,5 – V₅ = 5

V₃ = C_4,3 – U₄ = -1

Для свободных клеток определим значения оценок (разностей между прямыми и косвенными тарифами).

S_1,1 = С_1,1 - (U₁ + V₁) = -1

S_1,2 = С_1,2 - (U₁ + V₂) = 7

S_1,3 = С_1,3 - (U₁ + V₃) = 12

S_1,4 = С_1,4 - (U₁ + V₄) = 3

S_1,5 = С_1,5 - (U₁ + V₅) = 9

S_2,3 = С_2,3 - (U₂ + V₃) = 6

S_2,4 = С_2,4 - (U₂ + V₄) = 1

S_2,6 = С_2,6 - (U₂ + V₆) = -2

S_3,2 = С_3,2 - (U₃ + V₂) = 6

S_3,3 = С_3,3 - (U₃ + V₃) = 5

S_3,5 = С_3,5 - (U₃ + V₅) = 7

S_4,1 = С_4,1 - (U₄ + V₁) = -3

S_4,2 = С_4,2 - (U₄ + V₂) = 6

S_4,4 = С_4,4 - (U₄ + V₄) = 5

S_4,6 = С_4,6 - (U₄ + V₆) = 0

Имеем три клетки с отрицательными оценками – (1,1), (2, 6) и (4, 1). Выбираем клетку с наименьшей оценкой (4, 1) и строим для нее цикл табл. 8.

Таблица 8

Допустимый исходный план

Пункт назначения

Вспомогательные

Пункт назначения

Наличие груза, т.

Строка Столбец

B1

B2

B3

B4

B5

B6

V1= 6

V2= 1

V3= -1

V4= 3

V5= 0

V6= 4

А1

U1= 0

А2

U2= 6

-

+

А3

U3= 3

А4

U4= 5

+

-

Потребность в грузе, т.

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

Таблица 9

Допустимый исходный план

Пункт назначения

Вспомогательные

Пункт назначения

Наличие груза, т.

Строка Столбец

B1

B2

B3

B4

B5

B6

V1= 6

V2= 4

V3= 2

V4= 3

V5= 3

V6= 4

А1

U1= 0

А2

U2= 3

А3

U3= 3

А4

U4= 2

Потребность в грузе, т.

Целевая функция (транспортные расходы) z = 289. Значение целевой функции изменилось на 6 единиц по сравнению с предыдущим этапом.

Проверим полученный план на оптимальность. Подсчитаем потенциалы.

U₁=0

V₆ =C_1,6 – U₁= 4

U₃ = C_3,6 – V₆ = 3

V₁ = C_3,1 – U₃ = 6

V₄ = C_3,4 - U₃ = 3

U₄ = C_4,1 – V₁ = 2

V₃ = C_4,3 – U₄ = 2

V₅ = C_4,5 – U₄ = 3

U₂ = C_2,5 – V₅ = 3

V₂ = C_2,2 – U₂ = 4

Для свободных клеток определим значения оценок (разностей между прямыми и косвенными тарифами).

S_1,1 = С_1,1 - (U₁ + V₁) = -1

S_1,2 = С_1,2 - (U₁ + V₂) = 4

S_1,3 = С_1,3 - (U₁ + V₃) = 11

S_1,4 = С_1,4 - (U₁ + V₄) = 3

S_1,5 = С_1,5 - (U₁ + V₅) = 6

S_2,1 = С_2,1 - (U₂ + V₁) = 3

S_2,3 = С_2,3 - (U₂ + V₃) = 6

S_2,4 = С_2,4 - (U₂ + V₄) = 4

S_2,6 = С_2,6 - (U₂ + V₆) = 1

S_3,2 = С_3,2 - (U₃ + V₂) = 3

S_3,3 = С_3,3 - (U₃ + V₃) = 2

S_3,5 = С_3,5 - (U₃ + V₅) = 4

S_4,2 = С_4,2 - (U₄ + V₂) = 6

S_4,4 = С_4,4 - (U₄ + V₄) = 8

S_4,6 = С_4,6 - (U₄ + V₆) = 3

Имеем клетку (1, 1) с отрицательной оценкой, план не оптимален. Строим для этой клетки цикл.

Таблица 10

Допустимый исходный план

Пункт назначения

Вспомогательные

Пункт назначения

Наличие груза, т.

Строка Столбец

B1

B2

B3

B4

B5

B6

V1= 6

V2= 4

V3= 2

V4= 3

V5= 3

V6= 4

А1

U1= 0

+

-

А2

U2= 3

А3

U3= 3

-

+

А4

U4= 2

Потребность в грузе, т.

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

Таблица 11

Допустимый исходный план

Пункт назначения

Вспомогательные

Пункт назначения

Наличие груза, т.

Строка Столбец

B1

B2

B3

B4

B5

B6

V1= 5

V2= 3

V3= 1

V4= 3

V5= 2

V6= 4

А1

U1= 0

А2

U2= 4

А3

U3= 3

А4

U4= 3

Потребность в грузе, т.

Целевая функция (транспортные расходы) z = 285. Значение целевой функции изменилось на 4 единицы по сравнению с предыдущим этапом.

Проверим полученный план на оптимальность. Подсчитаем потенциалы.

U₁=0

V₁ = C_1,1 – U₁ = 5

U₄ = C_4,1 – V₁ = 3

V₃ = C_4,3 – U₄ = 1

V₅ = C_4,5 – U₄ = 2

U₂ = C_2,5 – V₅ = 4

V₂ = C_2,2 – U₂ = 3

V₆ =C_1,6 – U₁ = 4

U₃ = C_3,6 – V₆ = 3

V₄ = C_3,4 - U₃ = 3

Для свободных клеток определим значения оценок (разностей между прямыми и косвенными тарифами).

S_1,2 = С_1,2 - (U₁ + V₂) = 5

S_1,3 = С_1,3 - (U₁ + V₃) = 12

S_1,4 = С_1,4 - (U₁ + V₄) = 3

S_1,5 = С_1,5 - (U₁ + V₅) = 7

S_2,1 = С_2,1 - (U₂ + V₁) = 3

S_2,3 = С_2,3 - (U₂ + V₃) = 6

S_2,4 = С_2,4 - (U₂ + V₄) = 3

S_2,6 = С_2,6 - (U₂ + V₆) = 0

S_3,1 = С_3,1 - (U₃ + V₁) = 1

S_3,2 = С_3,2 - (U₃ + V₂) = 4

S_3,3 = С_3,3 - (U₃ + V₃) = 3

S_3,5 = С_3,5 - (U₃ + V₅) = 5

S_4,2 = С_4,2 - (U₄ + V₂) = 6

S_4,4 = С_4,4 - (U₄ + V₄) = 7

S_4,6 = С_4,6 - (U₄ + V₆) = 2

Так как все оценки S_i,j ≥ 0, то полученный план является оптимальным, минимальные транспортные расходы равны 285.