Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Маршрутизация перевозок мелкопартийных грузов

Поиск

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

Приведем матрицу расстояний по строкам (таблица 3.1)

Таблица 3.1Приведение матрицы по строкам

Из/В Б М1 М2 М3 М4 М5 М6
Б -              
М1   -            
М2     -          
М3       -        
М4         -      
М5           -    
М6             -  

 

Приведем матрицу расстояний по столбцам (таблица 3.2)

Таблица 3.2Приведение матрицы по столбцам

Из/В Б М1 М2 М3 М4 М5 М6
Б -            
М1   -          
М2     -        
М3       -      
М4         -    
М5           -  
М6             -
             

 

Полностью приведенная матрица приведена в таблице 3.3.

Таблица 3.3Полностью приведенная матрица

Из/В Б М1 М2 М3 М4 М5 М6
Б -            
М1   -          
М2     -        
М3       -      
М4         -    
М5           -  
М6             -

 

 

Определим нижнюю границу множества Гамильтоновых контуров:

= 27700

 

Каждый нуль в приведенной матрице (см. таблицу 1.6) условно заменяем на и находим сумму констант приведения . Значения записываем в соответствующие клетки рядом с нулями (таблица 3.4).

Таблица 3.4Определение сумм констант приведения

Из/В Б М1 М2 М3 М4 М5 М6
Б - 0(3500)          
М1 0(3500) -     0(300)    
М2     - 0(1800)      
М3     0(1800) -      
М4   0(700)     -    
М5           - 0(5100)
М6           0(5100) -

Из таблицы 3.4 видно, что наибольшее значение суммы констант приведения получается на пересечении 6й строки и 7-го столбца и 7й строки и 6го столбца и составляет 5100. Рассмотрим первый вариант.

Априорно исключаем из гамильтонова контура дугу (6,7), заменяя элементы а 7,6 = 0 в матрице расстояний на . В результате исключения данной дуги будет образовано подмножество гамильтоновых контуров { }.

Приводим полученную матрицу расстояний и определяем нижнюю границу подмножества гамильтоновых контуров { }.

Таблица 3.5Исключение 6 строки и 7 столбца

Из/В Б М1 М2 М3 М4 М5
Б          
М1          
М2          
М3          
М4          
М6          

Таблица 3.6Приведение матрицы по строкам

Из/В Б М1 М2 М3 М4 М5
Б            
М1            
М2            
М3            
М4            
М6            

 

Таблица 3.7Приведение матрицы по столбцам

Из/В Б М1 М2 М3 М4 М5
Б          
М1          
М2          
М3          
М4          
М6          
           

 

Тогда а Матрица, полученная после приведения по строкам и столбцам приведена в таблице 3.8.

Каждый нуль в полученной матрице условно заменяем на и находим сумму констант приведения . Значения записываем в соответствующие клетки рядом с нулями (таблица 3.9).

Таблица 3.8Полностью приведенная матрица

Из/В Б М1 М2 М3 М4 М5
Б          
М1          
М2          
М3          
М4          
М6          

 

Таблица 3.9Определение сумм констант приведения

Из/В Б М1 М2 М3 М4 М5
Б 0(3500)        
М1 0(3500)     0(300)  
М2     0(1800)    
М3     0(1800)    
М4   0(0)     0(5000)
М6   0(3500)      

 

Из таблицы 3.9 видно, что наибольшее значение суммы констант приведения получается на пересечении 5 строки и 6 столбца и составляет 5000. Априорно исключаем из гамильтонова контура дугу (5,6) и проводим расчеты аналогичные предыдущим.

Таблица 3.10Исключение 5й строки и 6го столбца

Из/В Б М1 М2 М3 М4
Б        
М1        
М2        
М3        
М6        

Таблица 3.11Приведение матрицы по строкам

Из/В Б М1 М2 М3 М4
Б          
М1          
М2          
М3          
М6          

 

 

Таблица 3.12Приведение матрицы по столбцам

Из/В Б М1 М2 М3 М4
Б        
М1        
М2        
М3        
М6        
         


Тогда а Матрица, полученная после приведения по строкам и столбцам приведена в таблице 3.13.

Каждый нуль в полученной матрице условно заменяем на и находим сумму констант приведения . Значения записываем в соответствующие клетки рядом с нулями (таблица 3.14).

Таблица 3.13Полностью приведенная матрица

Из/В Б М1 М2 М3 М4
Б        
М1        
М2        
М3        
М6        
Из/В Б М1 М2 М3 М4
Б 0(3500)      
М1 0(3500)     0(300)
М2     0(6500)  
М3     0(1800)  
М6        

Таблица 3.14Определение сумм констант приведения

 

Из таблицы 3.14 видно, что наибольшее значение суммы констант приведения получается на пересечении 3 строки и 4 столбца и составляет 6500. Априорно исключаем из гамильтонова контура дугу (3,4), заменяя элемент а 4,3 = 3100 в матрице расстояний на и проводим расчеты аналогичные предыдущим (таблицы 3.15-3.18)

Таблица 3.15Исключение 3 строки и 4 столбца

Из/В Б М1 М2 М4
Б      
М1      
М3      
М6      

Таблица 3.16Приведение матрицы по строкам

Из/В Б М1 М2 М4
Б        
М1        
М3        
М6        


Таблица 3.17Приведение матрицы по столбцам

Из/В Б М1 М2 М4
Б      
М1      
М3      
М6      
       

 

 

Тогда а Матрица, полученная после приведения по строкам и столбцам приведена в таблице 3.18.

Каждый нуль в полученной матрице условно заменяем на и находим сумму констант приведения . Значения записываем в соответствующие клетки рядом с нулями (таблица 3.19).

Таблица 3.18Полностью приведенная матрица

Из/В Б М1 М2 М4
Б      
М1      
М3      
М6      

Таблица 3.19Определение сумм констант приведения

Из/В Б М1 М2 М4
Б 0(3500)    
М1 0(3500) 0(3500) 0(0)
М3     0(4700)
М6      

 

Из таблицы 3.19 видно, что наибольшее значение суммы констант приведения получается на пересечении 3 строки и 3 столбца и составляет 4700.

Априорно исключаем из гамильтонова контура дугу (3,4), заменяя элемент а 4,3 = 3500 в матрице расстояний на и проводим расчеты аналогичные предыдущим (таблицы 3.20-3.23)

Таблица 3.20Исключение 4 строки и 3 столбца

Из/В Б М1 М2
Б    
М1    
М6    

Таблица 3.21Приведение матрицы по строкам

Из/В Б М1 М2
Б      
М1      
М6      

Таблица 3.22Приведение матрицы по столбцам

Из/В Б М1 М2
Б    
М1    
М6    
     

 

Тогда а Матрица, полученная после приведения по строкам и столбцам приведена в таблице 3.23.

Таблица 3.23Полностью приведенная матрица

Из/В Б М1 М2
Б    
М1    
М6    

 

 

Каждый нуль в полученной матрице условно заменяем на и находим сумму констант приведения . Значения записываем в соответствующие клетки рядом с нулями (таблица 3.24).

Таблица 3.24Определение сумм констант приведения

Из/В Б М1 М2
Б 0(3500)  
М1 0(3500) 0(3500)
М6   0(3500)

 

 

Из таблицы 3.24 видно, что мы получили 4 одинаковых максимальных суммы констант приведения (3500). Это означает что алгоритм разветвляется и мы должны рассмотреть все получившиеся варианты поочередно.Рассмотрим вариант (1,2).

Априорно исключаем из гамильтонова контура дугу (1,2), заменяя элемент а 2,1 = 0 в матрице расстояний на и проводим расчеты аналогичные предыдущим (таблицы 3.25-3.28)

Таблица 3.25Исключение первой строки и второго столбца

Из/В Б М2
М1    
М6  

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

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

Минимальное значение имеет НГр=38100.

Соответствующий оптимальный контур включает дуги: (М5,М6), (М4,М5), (М2, М3), (М3, М4), (Б, М1), (М1, М2), (М6, Б).

 

 


 



Поделиться:


Последнее изменение этой страницы: 2016-08-16; просмотров: 187; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.135.195.180 (0.006 с.)