Задача 

       Груз  находится в пункте А – 4000 кг. Используется автомобиль грузоподъемностью 2,5 т; груз – П класса (γ = 0,8). Необходимо организовать перевозку между пунктами с минимальным пробегом подвижного состава. 

 

     
 

       Решение: 

       На  заданной схеме находим наименьшее звено. В данном случае это звено Б-3 = 3 км. Затем рассмотрим все звенья, связанные с одной из этих вершин и рассмотрим все звенья связанные с вершинами полученной ломаной Б-Ж-З : Б-А = 5 км, Б-Ж = 7 км, З-Ж = 4 км, З-И = 8 км, Ж-В = 4 км..  
 
 
 
 
 

   

Рисунок 1 – Кратчайшая связывающая сеть

 
 

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

       Максимальная вместимость автомобиля, равная 2,5 т. Исходя из этого, пункты, указанные на рисунке 1, группируем следующим образом и представим в виде таблицы 1.

Таблица 1

 

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

       Для каждого маршрута строим таблицу. Для маршрута 1 она приведена в таблице 2. По главной диагонали в ней размещены пункты, включаемые в маршрут. Цифры в клетках показывают кратчайшие  расстояния между ними. Начальный маршрут строим для трех пунктов матрицы А, В, Ж, имеющих наибольшие значения величины, показанной в  итоговой строке (36, 34, 27), т.е. маршрут АВЖА.

Таблица 2

 

       Для включения последующих пунктов  в маршрут выбираем из оставшихся пунктов в таблице пункт, имеющий наибольшую сумму - это Б (26). Затем необходимо определить между какими пунктами начального маршрута его следует вставить. Для этого  следует   поочередно вставлять пункт Б между каждой соседней парой пунктов АВ, ВЖ, ЖА.

       При этом для каждой пары пунктов необходимо найти величину приращения маршрута  (∆)  по формуле:

   ∆_kp = C_ki + C_ip –  C_kp ,

       где С – расстояние, км;

       i -  индекс включаемого пункта;

       k – индекс первого пункта из пары;

       p – индекс второго пункта из пары.

       При включении пункта Б между первой парой пунктов АВ  определяем размер приращения ∆АВ при условии, что i =Б, k = A, p = В. Тогда 

∆_АВ = С_АБ + С_БВ – С_АВ . 

       Соответствующие расстояния между пунктами  берем из таблицы 2  и получаем ∆_АБ = 5 + 11 – 11 = 5.

       Для пунктов ВЖ приращение маршрута при включении пункта Б равно:

       ∆_ВЖ = С_ВБ + С_БЖ – С_ВЖ ,

       т.е. ∆_ВЖ = 11 + 7 – 4 = 14.

       Для пунктов ЖА соответственно:

       ∆_ЖА = С_ЖБ + С_БА – С_ЖА ,

       т.е. ∆_ЖА = 7 + 5 – 12= 0.

       Из  полученных значений выбираем минимальное  значение, т.е. ∆_ЖА = 0  и между соответствующими пунктами вставляем пункт Б. Получаем маршрут АВЖБА.

       Вновь в таблице 2 выбираем один из еще не включенных в маршрут пунктов З.

       ∆_АВ = С_АЗ + С_ЗВ–  С_АВ  =  8 +8 – 11 = 5

       ∆_ВЖ = С_ВЗ  + С_ЗЖ – С_ВЖ    =  8 + 4 – 4 = 8

       ∆_ЖБ = С_ЖЗ  + С_ЗБ – С_ЖБ   =  4 + 3 – 7 = 0

       ∆_БА = С_БЗ + С_ЗА – С_БА =  3 + 8 – 5 = 6 .

       Так как наименьшей величиной является ∆_ЖБ, пункт З включаем между ЖБ и получаем  маршрут АВЖЗБА.

       Получаем  окончательный порядок объезда пунктов первого маршрута АВЖЗБА, длина которого составит 27 км. Можно утверждать, что полученная последовательность объезда дает наименьший или весьма близкий к наименьшему пути путь объезда пунктов маршрута 1.

       По  маршруту 2 проводятся аналогичные расчеты, исходные данные для которых представлены в таблице 3.

       Начальный маршрут строим для трех пунктов матрицы А, Д, К, имеющих наибольшие значения величины, показанной в  итоговой строке (93, 90, 81), т.е. маршрут АДКА.

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

   Таблица 3

 

       ∆_АД = С_АГ + С_ГД –  С_АД  =  14 +15 – 16 = 13

       ∆_ДК = С_ДГ  + С_ГК – С_ДК    =  15 + 19 – 14 = 20

       ∆_КА = С_КГ + С_ГА – С_КА =  19 + 14 – 27 = 6 . 

       Из  полученных значений выбираем минимальное значение, т.е. ∆_КА = 6  и между соответствующими пунктами вставляем пункт Г. Получаем маршрут АДКГА.

       Вновь в таблицы 3 выбираем один из еще не включенных в маршрут пунктов Е. 

       ∆_АД = С_АЕ+ С_ЕД –  С_АД  =  21 +22 – 16 = 27

       ∆_ДК = С_ДЕ  + С_ЕК – С_ДК    = 22 + 12 – 14 = 20

       ∆_КГ = С_КЕ  + С_ЕГ – С_КГ   =  12 + 7 – 19 = 0

       ∆_ГА = С_ГЕ + С_ЕА – С_ГА =  7 + 21 – 14 = 14 . 

       Из полученных значений выбираем минимальное значение, т.е. ∆_КГ = 0  и между соответствующими пунктами вставляем пункт Е. Получаем маршрут АДКЕГА.

       Вновь в таблицы 3 выбираем один из еще не включенных в маршрут пунктов И.

       ∆_АД = С_АИ + С_ИД –  С_АД  =  15 +23 – 16 = 22

       ∆_ДК = С_ДИ  + С_ИК – С_ДК    =  23 + 9 – 14 = 18

       ∆_КЕ = С_КИ  + С_ИЕ – С_КЕ   =  9 + 5 – 12 = 2

       ∆_ЕГ = С_ЕИ  + С_ИГ – С_ЕГ   =  5 + 12 – 7 = 10

       ∆_ГА = С_ГИ  + С_ИА – С_ГА   =  12 + 15 – 14 = 13

       Из  полученных значений выбираем минимальное  значение, т.е. ∆_КЕ = 2  и между соответствующими пунктами вставляем пункт И. Получаем маршрут АДКИЕГА.

       В результате указанных расчетов порядок объезда пунктов в этом маршруте будет АДКИЕГА и путь движения в данном случае составит 65 км.

       На  рисунке 2 представим схему движения по маршрутам 1 и 2.  

     

   Рисунок 3 – Схема движения по маршрутам № 1 и 2 
 

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

       Маршрут 1 должен по решению иметь следующую  последовательность объезда пунктов  – АВЖЗБА.

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

   Таблица 4