Условия предпочтения кольцевых маршрутов маятниковым

Зачастую, решая задачу выбора оптимального кольцевого маршрута, мы не всегда задумываемся над вопросом: почему доставка груза в каждую из, например, шести точек обязательно должна осуществляться с помощью единого кольцевого маршрута? Не исключено, что для некоторых точек выгоднее кольцевой маршрут, а для оставшихся — маятниковый. Таким образом, необходимо решить две задачи: задачу разбиения множества грузополучателей на подмножества и задачу разработки правил предпочтения кольцевых маршрутов маятниковым для одних и тех же точек. Начнем со второй задачи, имея в виду то очевидное обстоятельство, что многозвенных кольцевых маршрутов не бывает, так как необходимость возить груз, только частично избавляясь от него в каждой точке маршрута, резко увеличивает грузооборот. В маятниковом маршруте выгружается весь перевозимый груз. Доставку грузов многозвенными кольцевыми маршрутами трудно увязывать с режимами работы потребителей продукции, что увеличивает время простоя транспортного средства. Последнее обстоятельство ставит под угрозу доставку грузов во все пункты потребления в течение рабочего времени.

Начнем с простейших задач. Имеются две точки доставки груза. В первую точку необходимо доставить a₁ тонн груза, во вторую, — a₂. Расстояние между точками равно s₁, длина пути от грузоотправителя до первой точки равна l₁, до второй, — l₂. Очевидно, что грузооборот двух маятниковых маршрутов равен:

a₁ · l₁ + a₂ · l₂

Грузооборот кольцевого маршрута определяется по формуле:

(a₁ + a₂) · l₁ + a₂ · s₁

Пусть кольцевой маршрут предпочтительнее двух маятниковых:

(a₁ + a₂) · l₁ + a₂ · s₁ ≤ a₁ · l₁ + a₂ · l₂

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

l₂ ≥ l₁ + s₁ (1)

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

Пример 1: a₁=0,45 т., a₂=0,6 т., l₁=8 км., l₂=21 км., s₁=4 км.

Условие (1) выполняется (21>8+4), кольцевой маршрут выгоднее. Это можно проверить. Грузооборот маятниковых маршрутов равен 0,45·8+0,6·21=16,2 т·км. Грузооборот кольцевого маршрута равен: (0,45+0,6)·8+0,6·4=8,4+2,4=10,8 т·км. Если бы величина l₂ была не более 11 км., то выгоднее были бы маятниковые маршруты.

Пусть имеются три точки для доставки груза. Дополним исходные данные следующими величинами: в третью точку необходимо доставить груз весом a₃, расстояние между второй и третьей точками равно s₂, длина пути от грузоотправителя до третьей точки равна l₃. Условие предпочтения кольцевого маршрута перед тремя маятниковыми запишется в виде:

l₁ · (a₁ + a₂ + a₃) + s₁ · (a₂ + a₃) + s₂ · a₃ ≤ a₁ · l₁ + a₂ · l₂ + a₃ · l₃

После несложных преобразований получим:

a₂(l₂ − l₁ − s₁) + a₃(l₃ − l₁ − s₁ − s₂) ≥ 0

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

l₂ ≥ l₁ + s₁
l₃ ≥ l₁ + s₁ + s₂ (2)

Пример 2: a₁=3 т., a₂=2 т., a₃=1,5 т., l₁=13 км., l₂=21 км., l₃=25 км., s₁=5 км., s₂=4 км.

Условие (2) выполняется: (21>13+5) и (25>13+5+4). Грузооборот кольцевого маршрута равен 108 т·км., трех маятниковых, — 118,5 т·км. Читатель имеет возможность в этом убедиться, обратившись к исходной записи условия предпочтительности.

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

(3)

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

№ п/п	0	1	2	3	4	5
0	х	17,5	26	12,5	13	19
1	17,5	х	15	16	22	25
2	26	15	х	16	22,5	21,5
3	12,5	16	16	х	7	9
4	13	22	22,5	7	х	6
5	19	25	21,5	9	6	х
Груз, т.		0,3	0,2	0,4	0,5	0,25

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

Удалим из связывающей сети максимальный элемент. Таких элементов два — числа 16. После их удаления точки 1 и 2 уже ничего не связывает с остальными точками множества. Независимо от того, удалим ли мы число 9 или оставим, множество из пяти точек естественно разбивается на два подмножества точек: (1,2) и (3,4,5). Вот для этих подмножеств и проверим соответствующие условия предпочтения кольцевых маршрутов маятниковым.

Сначала отметим, что оптимальный кольцевой маршрут по минимуму грузооборота для всех пяти точек, найденный методом «ветвей и границ», определяется следующей последовательностью обхода точек: 0–4–5–3–1–2–0. Суммарный грузооборот равен 47,45 т·км.

Исходные данные для подмножества точек (1,2) следующие: a₁=0,3 т., a₂=0,2 т., l₁=17,5 км., l₂=26 км., s₁=15 км.

Условие (2) не выполняется, маятниковые маршруты выгоднее. Грузооборот маятниковых маршрутов равен: 17,5·0,3+26·0,2 = 5,25+5,2 =10,45 т·км. Минимальный грузооборот кольцевого маршрута равен: 17,5·0,5+15·0,2=8,75+3=11,75 т·км.

Исходные данные для подмножества точек (3,4,5) следующие: a₁=0,4 т., a₂=0,5 т., a₃=0,25 т., l₁=12,5 км., l₂=13 км., l₃=19 км., s₁=7 км., s₂=6 км.

Условие (3) не выполняется, маятниковые маршруты выгоднее. Грузооборот маятниковых маршрутов равен: 12,5·0,4+13·0,5+19·0,25 = 5+6,5+4,75=16,25 т·км. Минимальный грузооборот кольцевого маршрута равен: 12,5·1,15+7·0,75+6·0,25=14,375+5,25+1,5=21,125 т·км.

Суммарный грузооборот по пяти маятниковым маршрутам равен 10,45+16,25=26,7 т·км. Грузооборот по оптимальному кольцевому маршруту для этих же пяти точек, как указывалось выше, равен 47,45 т·км.

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

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

Литература

1. Форд Л., Фалкерсон Д. Потоки в сетях. — М.: Изд-во «МИР», 1966.