Исходные данные 

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

                 Таблица 1 

 
 
 
 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

                                          Рисунок 1 Схема размещения пунктов 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Решение  

                 Этап 1 Нахождение кратчайшей сети, связывающей все пункты

  

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

   Назовем все пункты, указанные на рис.1, вершинами  сети, а линию, соединяющую две  соседние вершины, - звеном.

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

На схеме (рис.1)находится  наименьшее звено. В данном случае это звено А-Б = 4 км. Затем рассматриваются все звенья, связанные одной из своих вершин с выбранным звеном, т.е. звенья: А-В = 5км, Б-З = 7 км. Из них выбирается звено с наименьшим  расстоянием (А - В = 5 км). Далее рассматриваются все звенья, связанные с вершинами полученной ломаной линии Б-А-В, из них выбирается наименьшее, и так до тех пор, пока не будут выбраны все вершины сети. При этом нельзя выбирать звено, соединяющее две ранее включенные в сеть вершины. На рис. 2 представлена кратчайшая связывающая сеть.  
 

                                          Этап 2 Набор пунктов  в маршруты  

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

   Необходимо  учитывать, что максимальная вместимость автомобиля равна 2т. (2,5*0,8) Исходя из этого, пункты, указанные на рис. 2, группируются следующим образом. (табл. 2)

   Таблица 2

 

          

         Этап 3. Определение очередности объезда пунктов маршрута

 
 

   Этот  этап расчетов имеет  целью связать  все пункты каждого маршрута, начиная  с пункта А, замкнутой линией, которой  соответствует кратчайший путь объезда  этих пунктов. С этой целью проводятся специальные расчеты, один из методов  которых, называемый «методом треугольников», приводится ниже.

   Для каждого маршрута строят таблицу, называемую симметричной матрицей. Для маршрута 1 она приведена  в  табл. 3. По главной  диагонали в ней размещены  пункты, включаемые в маршрут. Цифры  в клетках показывают кратчайшие  расстояния между ними. Для примера  матрица является  симметричной  C_ij  = Cji , хотя приведенный ниже способ применим для размещения несимметричных матриц.

   Начальный маршрут строим для трех пунктов матрицы А,Г,И, имеющих наибольшие значения величины, показанной в  итоговой строке (77, 73, 70 ), т.е. маршрутГАИГ.

  

Таблица 3  

 

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

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

    

   ∆_kp = C_ki + C_ip –  C_kp , 

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

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

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

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

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

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

   Соответствующие расстояния между пунктами  берутся  в табл. 3  и получаем                                           ∆_ГА = 21 + 4 – 17 = 8.

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

     

 ∆_ИГ = С_ГБ + С_ИБ – С_ИГ ,    т.е. ∆_ИГ = 20 + 21 – 6 = 35. 

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

∆_АИ = С_ИБ + С_АБ – С_АИ , т.е. ∆_АИ = 4+ 20 – 23 = 1. 

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

   Вновь в табл.3 выбираем один из еще не включенных в маршрут пунктов К. Все дальнейшие расчеты проводятся, как это было показано выше:

   ∆_ГА = С_ГК + С_АК –  С_ГА  =   14+17 – 17 = 14

   ∆_АБ = С_АК  + С_БК – С_АБ    =  17 + 13 – 4 = 26

   ∆_БИ = С_БК  + С_ИК – С_БИ   =  13 + 8 – 20 = 1

   ∆_ИГ = С_ИК + С_ГК – С_ИГ =  6 + 14 – 6 = 14 .

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

   Остается  определить, куда следует вставить пункт З. Производим соответствующие расчеты :

   ∆_ГА  = С_ГЗ + С_АЗ  – С_ГА  = 19 + 12 – 17 = 14

   ∆_АБ  = С_АЗ + С_БЗ   – С_АБ  = 12 + 7 – 4 = 15

   ∆_БК  = С_БЗ + С_КЗ  –  С_БК = 7 + 5 – 13 = -1

   ∆_КИ  = С_КЗ + С_ИЗ – С_КИ = 5 + 13 – 8 = 10

   ∆_ИГ  = С_ИЗ + С_ГЗ – С_ИГ = 13 + 19 – 6 = 26. 

   Здесь наименьшее  приращение ∆_БК,  поэтому получаем окончательный порядок объезда пунктов первого маршрута ГАБЗКИГ. Можно утверждать, что полученная последовательность объезда дает наименьший или весьма близкий к наименьшему пути путь объезда пунктов маршрута 1.

   По  маршруту 2 проводятся аналогичные  расчеты, исходные данные для которых  представлены в табл. 4. В результате указанных расчетов порядок объезда  пунктов в этом маршруте будет  ЛЖДАВЕДЛ.

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

 Таблица 4