Определение второго загруженного элемента.

Объем перевозок	Пункты разгрузки	Столбец разностей
Пункт погрузки	b₁	b₂	b₃	b₅	b₆	b₇	b₈
Q, т	0,25	0,3	0,45	0,5	0,6	1,0	1,1
a₁	l, км
a₂	l, км
Строка разностей

Таблица 30

Решение транспортной задачи

Пункт погрузки	Пункты разгрузки	Итого:
b₁	b₂	b₃	b₄	b₅	b₆	b₇	b₈
a₁	0,25	0,3		1,5					2,05
a₂			0,45		0,5	0,6	1,0	1,1	3,65

Набор пунктов в маршрут выполним методом Свира, используя схему дислокации пунктов относительно друг друга, представленную на рисунке 10. Грузоподъемность транспортных средств предполагается равной 2,2 тонны.

Рис. 10. Дислокация грузообразующих и грузопоглощающих пунктов.

Согласно методу Свира воображаемый луч, исходящий из пункта погрузки, например, а₁, вращаясь против (или по) часовой стрелки "стирает" изображения пунктов разгрузки. Маршрут считается сформированным, если включение следующего пункта приведет к превышению объема перевозки над грузоподъемностью транспортного средства. Первым пунктов маршрута будет b₂ с объемом перевозки 0,3 тонны, следующий пункт – b₄, суммарный объем составит 1,8 тонны. Включение пункта b₁ в маршрут так же возможно, так как не произойдет превышение грузоподъемности подвижного состава.

Метод Свира для пункта а₂ позволяет получить два маршрута. Первый включает два пункта b₆ и b₇ с суммарным объемом перевозки 1,6 тонны, а второй – три b₃, b₅ и b₈, объем – 2,05 тонны.

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

Таблица 31.

Таблица кратчайших расстояний между пунктами маршрутов

а₁

а₂

b₁

b₆

b₃

b₂

b₇

b₅

b₄

b₈

Применение метода рассмотрим на маршруте, включающем пункты a₁, b₁, b₂ и b₄.

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

Приведенная матрица показана в табл. 32, б. Справа и внизу матрицы показаны константы приведения – минимальные элементы, которые вычитались вначале из строк, а затем из столбцов матрицы.

Таблица 32

Определение нижней границы множества "все решения"

а)

а₁

b₁

b₂

b₄

б)

а₁

b₁

b₂

b₄

а₁

∞

а₁

∞

b₁

∞

b₁

∞

b₂

∞

b₂

∞

b₄

∞

b₄

∞

Сумма констант, равная 28, является нижней границей протяженности для всех маршрутов, то есть для множества "все решения".

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

Для этого определяются оценки всех элементов приведенной матрицы как сумму наименьших величин протяженности соответствующей строки и столбца. Например, для нулевого элемента a₁b₁ оценка составит 1 + 15. Оценка показывает на потери от невключения данного элемента в маршрут. Проставим ее в правом верхнем углу (табл. 33).

Таблица 33

Определение оценок для нулевых элементов матрицы.

	а₁	b₁	b₂	b₄
а₁	∞	0 ¹⁶
b₁	0 ¹⁶	∞
b₂			∞	0 ⁹
b₄			0 ⁹	∞

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

3. Для ветвления множества его необходимо разделить на два вида: маршруты первого подмножества будут включать пару a₁b₁, а маршруты второго ее не включают.

Нижняя граница второго подмножества равна сумме значений нижней границы разделяемого множества и величины оценки пары a₁b₁, то есть 28 + 16 = 44. Строку a₁ и столбец b₁ исключают из рассмотрения, то сеть удаляют из матрицы. Выбор в дальнейшем пары b₁a₁ привел бы к нарушению условия о заезде в каждый пункт только по одному разу. Поэтому пара b₁a₁ блокируется, проставляя в соответствующую клетку матрицы знак блокировки ( ) вместо прежнего значения.

4. Преобразованная и приведенная матрица приведена в таблице 34. В процессе вычисления констант появились константы, равные 9 и 7 соответственно. Следовательно, протяженность подмножества, включающего пару a₁b₁, увеличивается на 16 (28 + 16 = 44).

Таблица 34

Матрица с исключенными строкой a₁ и столбцом b₁

	а₁	b₂	b₄
b₁	∞		0 ¹
b₂		∞	0 ¹
b₄	0 ¹	0 ¹	∞

Как видно из таблицы 34, все пары имеют одинаковые оценки, равные 1. Выбираем, например, пару b₁b₄. Протяженность множества, не включающего пару b₁b₄, увеличивается на 1 (44 + 1 = 45). Исключаем соответствующие столбец и строку из дельнейшего рассмотрения. Столбец b₁ из матрицы удален, поэтому знак блокировки не ставиться (табл. 35). В процессе вычисления появилась константа 1, поэтому увеличиваем нижнюю границу на 1 (44 + 1 = 45).

Таблица 35

Матрица с исключенными строкой b₁ и столбцом b₄

	а₁	b₂
b₂	0 ^∞	∞
b₄	0 ⁰	0 ^∞

Полученную матрицу 2 х 2 легко решить. недостающими парами пунктов в маршруте будут: b₄b₂ и b₂a₁.

Таким образом, получен маршрут a₁b₁ - b₁b₄ - b₄b₂ - b₂a₁, протяженностью 45 км.

Решение можно представить в виде схемы, называемой "деревом решений" (рис.11).

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

Аналогичным образом определяем порядок объезда пунктов на двух других маршрутах: a₂b₆ – b₆b₇ – b₇a₂, длиной 25 км; a₂b₃ – b₃b₅ – b₅b₈ – b₈a₂, длиной 33 км (рис. 12).

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

Рис 11. Дерево решений для метода "ветвей и границ".

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

Среднее значение времени движения определяется как отношение расстояния перевозки (10 км) к среднему значению скорости движения t_дв = 0,32 (10 / 31 = 0,32). Среднее квадратическое отклонение времени движения (σ_дв) определяется, исходя из утверждения, что значения коэффициентов корреляции ν для скорости и времени движения равны. Коэффициент корреляции для технической скорости равен 2,5. Поэтому, σ_дв определяется как произведение среднего значения времени движения и коэффициента корреляции скорости (σ_дв = 0,34 · 2,5 = 0,8 ч).

Рис 12. Маршруты движения транспортных средств

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

При α_p = 1,0 прибытие подвижного состава в установленное пределами время может ожидаться в 68,3% случае; при α_p = 2,0 – в 95,4%, а уже при α_p = 3,0 практически не должно быть случаев выхода затрат времени за установленные пределы.

Таблица 36

Значение квантиля нормального распределения, соответствующее вероятности P

Значение коэффициента α_p	0,5	1,0	1,5	2,0	2,5	3,0
Вероятность нахождения затрат времени в пределах расчетных, %	38,3	68,3	86,6	95,4	98,8	99,7

Допустимое отклонение затрат времени для определения взаимоотношений с клиентурой предлагается рассчитывать по коэффициенту α_p = 2,5 – 3,0, что гарантирует большую надежность выполнения обязательств. При составлении расписания работы водителя для стимулирования четкой работы можно принять α_p = 1,0 – 2,0.

Верхняя граница времени доставки груза потребителю b₁ при α_p = 1,5 равна:

нижняя граница:

Таким образом, время доставки груза первому потребителю на маршруте составит (10 – 19) ± (1 – 02) ч. Для второго пункта b₄ среднее время доставки определяется как сумма времени доставки в первый пункт маршрута, времени движения между первым и вторым потребителем и времени разгрузки у второго потребителя; среднее квадратическое отклонение рассчитывается как квадратный корень из сумм дисперсий указанных величин.

Аналогичным образом рассчитываются интервалы доставки груза остальным потребителям на маршруте и время прибытия в начальный пункт погрузки (табл. 37).

Таблица 37

Временные интервалы прибытия автомобиля в пункты первого маршрута.

Пункт разгрузки	Гарантированное время доставки	Верхняя граница	Нижняя граница
ч – мин	± ч - мин
b₁	10-19	1-02	11-21	9-17
b₄	11-26	1-55	14-21	9-31
b₂	12-04	2-00	14-04	10-04
a₁	12-27	2-13	14-40	10-14

Для двух других маршрутов временные интервалы представлены в таблице 38.

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

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

Таблица 38

Временные интервалы прибытия автомобиля в пункты второго и третьего маршрутов.

Пункт разгрузки	Гарантированное время доставки	Верхняя граница	Нижняя граница
ч – мин	± ч - мин
Второй маршрут
b₆	10-19	1-02	11-21	9-17
b₇	10-55	1-10	12-05	9-45
a₂	11-18	1-31	12-49	9-39
Третий маршрут
b₃	10-27	1-18	11-45	9-09
b₅	11-05	1-26	12-31	9-39
b₈	12-43	1-33	14-16	11-10
a₂	13-04	1-47	14-51	11-17

⇐ Предыдущая 19 20 21 22 23 24 25 262728 Следующая ⇒