Разнорабочие Геленджик
Маршрутизация методом сумм
Решение задачи маршрутизации с большим, чем 4, количеством пунктов рассмотрим с использо-
ванием метода сумм. Рассмотрим решение задачи на следующем примере.
Этап 1. Исходная информация.
Имеется заявка на перевозку груза с условиями: необходимо доста-
вить груз шести потребителям; потребность в грузе qж = 600 кг; qз = 200 кг;
qи = 400 кг; qк = 500 кг; qл = 400 кг; qм = 400 кг. Критерий решения задачи
аналогично п. 5.2.1, этап 1.
Известны адреса клиентов, поставщика и их взаимное расположение; грузы транспортно однород-
ны; затраты времени на погрузку - выгрузку 1 т груза пв = 0,1 т/ч; среднее время на нахождение в пунк-
те маршрута tз
= =0,1 ч; условия эксплуатации – город, Vт = 25 км/ч. Взаимное расположение поставщи-
ка и потребителей представлено на рис. 53.
Этап 2. Нахождение кратчайшей связывающей сети.
Пусть все пункты, указанные на рис. 53, называются вершинами сети, а линия, соединяющая две
соседние вершины, звеном. Незамкнутая сеть, связывающая две и более вершины с минимальной сум-
марной длиной всех соединяющих их звеньев, называется кратчайшей связывающей сетью. Данная сеть
находится следующим образом. На транспортной сети (см. рис. 53) находят наименьшее звено. В данном
случае звено КЛ = 2 км. Затем рассматривают все звенья, связанные с одной из своих вершин с выбран-
ным звеном, т.е. звенья КМ = 5; КИ = 2; КЗ = 6; КЖ = 7; ЛЖ = 6; ЛИ = 3; ЛЗ = 7. Из них выби-
рают звено с наименьшим расстоянием: КИ = 2. Далее рассматриваются звенья, связанные с вершинами
полученной линии ИКЛ, и из них выбирается наименьшее. При этом нельзя выбирать звено, соеди-
няющее две ранее включенные в сеть вершины. Таким звеном является ИЛ; несмотря на то, что оно
наименьшее из всех, связанных с выбранной сетью ИКЛ одной из вершин, его нельзя включить в
кратчайшую связывающую сеть. Другими звеньями, связанными своими вершинами с уже выбранной
сетью, являются звенья МК, ЗК, ИЗ, ИЖ, ИА, ИМ, ЛЖ, ЛЗ, звено ИЗ имеет наименьшее рас-
стояние, равное 4, и в этом случае получим сеть ЗИКЛ.
Далее опять рассматривают все звенья, связанные с вершинами полученной сети ЗИКЛ. Звенья
ИЖ и КМ имеют одинаковую длину, равную 5, берем любое, например КМ. Получаем сеть ЗИКМ
(КЛ). Далее опять рассматривают все звенья, связанные с вершинами полученной сети, и из них выби-
рают наименьшее, и так далее до тех пор, пока не будет выбрана сеть. На рис. 53 представлена кратчай-
шая связывающая сеть рассматриваемого примера, где также проставлена потребность пунктов в грузе
(+).
179
А 6
Ж
6 8
6 11 5
И
4 7 6
З 3
7
6 6 2 Л
6
2
5
М К
Рис. 53. Схема транспортной сети, взаимное расположение
пунктов, длины звеньев: 8 длина звена З-Ж, км
А
Ж +600
И+400
З+200
Л +400
М +400
К +500
Рис. 54. Кратчайшая связывающая сеть и потребность пунктов в грузе (+)
По условию рассматриваемого примера плановый объем перевозок не
превышает возможностей одного автомобиля за ездку, поэтому этап груп-
пировки пунктов в маршрут не рассматривался.
Этап 3. Определение очередности объезда пунктов маршрута.
На этом этапе все пункты маршрута, начиная с А, связываются такой замкнутой линией, которая
соответствует кратчайшему пути объезда этих пунктов. Первоначально, при использовании метода
сумм, строится таблица, называемая симметричной матрицей. Для маршрута АЖЗИКЛМ она приведена в
табл. 19.
По главной диагонали в ней расположены пункты, включаемые в маршрут. Цифры в табл. 19 по-
казывают расстояния между этими пунктами. Дополнительно в этой матрице имеется итоговая строка
строка сумм. В ней проставляют сумму расстояния по каждому столбцу. Затем строят начальный мар-
шрут из трех пунктов, имеющих максимальную сумму по
Таблица 19
Симметричная матрица для маршрута АЖЗИКЛМ
А 6 6 5 7 8 11
6 Ж 8 5 7 6 11
6 8 З 4 6 7 6
180
5 5 4 И 2 3 6
7 7 6 2 К 2 5
8 6 7 3 2 Л 7
11 11 6 6 5 7 М
43 43 37 21 27 33 46
своему столбцу. В табл. 19 максимальные суммы имеют столбцы А, Ж, М. Принимаем маршрут АЖМА.
В него включают следующий пункт с максимальной суммой, т.е. пункт З. Чтобы определить, между ка-
кими пунктами его следует вставить, надо поочередно включать этот пункт между каждой соседней па-
рой АЖ, ЖМ, МА. При этом для каждой пары этих пунктов находят величину прироста пробега автомо-
биля на маршруте при включении в начальный маршрут вновь выбранного пункта. Величину этого при-
роста кр находят по формуле
кр = L 13 + L23 – L12 , (5.8)
где L расстояние; 1 первый соседний пункт; 2 второй соседний пункт; 3 включаемый пункт.
В рассматриваемом примере в начальном маршруте (1 = А, 2 = Ж, 3 = =З) для первых двух сосед-
них пунктов АЖ: АЖ =L АЗ + LЗЖ LАЖ. Соответствующие расстояния между пунктами берем из табл.
19; АЖ = 6+86=8; ЖМ = 8+611=3; МА = 6+611=1. Из всех полученных выбирают минимальное
значение и между соответствующими пунктами вставляют данный пункт. В данном случае минималь-
ный МА, поэтому получаем маршрут АЖМЗА. Вновь в табл. 19 находят не принимавшийся в расчет
пункт с максимальной суммой по столбцу: это пункт Л. Все дальнейшие расчеты производятся так же,
как было указано выше: АЖ = 8+66 = 8; ЖМ = 6+711 = 2; МЗ = 7+76 = 8; ЗА =7+86= =9. Как видно
из расчетов, наименьшее расстояние ЖМ, поэтому пункт Л включается между ЖМ и получается мар-
шрут АЖЛМЗА.
Выполнив аналогичные расчеты для пунктов К и И, получаем маршрут объезда АЖИЛКМЗА, про-
тяженность которого составляет 33 км. Можно утверждать, что полученная последовательность объезда
пунктов маршрута дает меньший или весьма близкий к наименьшему путь движения. На рис. 55 пред-
ставлены схемы движения автомобилей по маршрутам АЖИЛКМЗА и АЗМКЛИЖА.
А
6 Ж
6 5
И
З 3
6 2 Л
М 5 К
А 6
6 Ж
5
И 3
З Л
6 2
5 К
М
Рис. 55. Схемы движения автомобилей по маршрутам
Этап 4. Проверка на минимум транспортной работы.
Критерий решения задачи аналогичный.
Результаты расчета выработки в т∙км представлены в табл. 20.
Таблица 20
181
Результаты расчета
Номер маршрута Порядок объезда Выработка, ткм
1 АЖИЛКМЗА 33,4
2 АЗМКЛИЖА 45,10
Принимаем для дальнейшего проектирования маршрут №1 АЖИЛКМЗА, поскольку ему соот-
ветствует минимальная выработка в тонно-километрах. Расчет результатов функционирования автомо-
биля выполним, используя формулы (4.41) – (4.45). Результаты представлены в табл.21.
Таблица 21
Результаты функционирования автомобиля
Маршрут Q, т Lс, км tрм , ч Р, ткм
АЖИЛКМЗА 2,5 33,0 2,07 33,4
В случае если перевозимый груз относится к грузам первого класса, для перевозки груза на спро-
ектированном маршруте достаточно автомобиля с грузоподъемностью 2,5 т. Если нет автомобиля тре-
буемой грузоподъемности или груз не первого класса, то требуется другой автомобиль, большей грузо-
подъемности.
Контрольные вопросы
1. Что называется звеном транспортной сети?
2. Что называется кратчайшей связывающей сетью?
3. Перечислите этапы нахождения кратчайшей связывающей сети.
4. Назовите условие, которое требуется соблюдать при нахождении кратчайшей
связывающей сети.
5. Перечислите этапы метода сумм.
6. Как производится проверка на минимум транспортной работы?
Разнорабочие Геленджик