WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |   ...   | 13 |

13 При определении кратчайшего гамильтонова пути также может быть H применен метод расширения цикла, при этом начальный путь k,l также H может быть записан как k jl.

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

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

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

3. Решение, содержащее в себе повторяющиеся элементы, может быть использовано для получения решения задачи о двух и более (в зависимости от числа повторяющихся элементов) коммивояжерах.

Так, например, из решения (3.12) имеем L1 4,6,3,4 = 8, L1 3,4,5,2,3 =18, L 1,4,6,3,4,5,2,3,1 = 31 (3.13) L 4,5,2,3,1,4 = 23, L2 3,1,4,6,3 =13.

И в первом и во втором случае оба коммивояжера вместе могут выходить только из пунктов A3 или A4, что, однако, не исключает возможность выхода каждого коммивояжера из любого пункта, входящего в его маршрут. Из (3.13) следует, что суммарная длина пути обоих коммивояжеров остается такой же, что и при одном, однако в первом варианте оба будут на месте через 23 ед. времени, а во втором – через 18 ед., если полагать, что скорости их перемещения постоянны и одинаковы.

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

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

4. В полученном решении в качестве исходного пункта может быть взята любая вершина ( k = 1; n ). Для этого достаточно номера, стоящие в цикле перед выбранным исходным номером k, перенести в конец кортежа и в конце приписать номер k. Например, для k = 6 из (3.18) получим L 6,3,4,5,2,3,1,4,6 = 31.

Для классической задачи коммивояжера решение инвариантно к исходному пункту цикла.

4. ОБОБЩЕННАЯ ЗАДАЧА КОММИВОЯЖЕРА 4.1. Постановка обобщенной задачи коммивояжера Содержательная постановка обобщенной задачи практически остаётся такой же, как и у классической задачи коммивояжера, с тем лишь добавлением, что коммивояжер, превратившись фактически в поставщика, должен выбрать такой маршрут для развозки грузов a ( j =1;n), при j котором энергозатраты будут минимальными.

Задача, как и ранее, будет состоять в определении гамильтонова цикла k, соответствующего минимальным энергозатратам. Дополнительной исходной информацией, по сравнению с предыдущей задачей, будет являться вес груза a, который должен быть доставлен в пункт Aj j ( j = 1;n).

Поскольку в исходный пункт Ak груз ak доставлять не требуется, то под величиной ak будем понимать вес самого транспортного средства, которое по циклу пройдет весь маршрут длиной Lkk = Lk = L(k ), энергозатраты на что составят ak Lk ед. (т·км, кг·м). Первый номер присвоим исходному пункту ( k = 1), в который возвратится транспортное средство с пассивным грузом a1 =1.

Формальная постановка обобщенной задачи коммивояжера как задача минимизации энергозатрат Э(1) путём выбора гамильтонова цикла 1 из всего их множества {1} (4.2) при ограничениях на частные маршруты 1 j доставки грузов как частей цикла 1 (4.3) формализуются следующим образом:

n Э( ) = L(1 j ) min (4.1) a 1 j j=1 {1}, (4.2) 1 j 1, j = 1;n. (4.3) Длина каждого частного маршрута определится как сумма длин дуг, входящих в маршрут:

L(1 j ) = L1 j = (4.4) c, j = 1,n.

i, j (i, j)1 j Поскольку в процессе решения гамильтонов цикл сформируется только к концу процесса расширения цикла, то в ходе решения некоторые обозначения в (4.1) – (4.4) потребуется дополнить индексом t, обозначающим номер шага (итерации) процесса МРЦ.

Когда для j 1 имеем a = 0, a1 = 1, задача вырождается в j обычную задачу коммивояжера.

4.2. Алгоритм решения обобщённой задачи коммивояжера методом расширения цикла при полной матрице расстояний ( = 1) и пример расчёта Схема решения остаётся такой же, что и в методе расширения цикла, при этом изменится только порядок определения приращения величины энергозатрат на текущем (t -м) шаге процесса.

Получим формулу для вычисления приращения энергозатрат на t -м шаге процесса при включении индекса в r -й интервал (jr-1 jr ) цикла.

Энергозатраты при этом повысятся из-за увеличения общего перевозимого груза на величину a и вследствие изменения длины цикла на величину L = c + c, jr - c. (4.5) jr-1, jr-1, jr jr-1,, jr Прирост энергозатрат по первой причине определится по формуле t tr,1( ) = a L1, = a (4.6) c, i, j t (i, j)1, t где L1, – длина пути от исходного пункта A1 до включенного в цикл пункта A.

Изменение энергозатрат по второй причине будет обусловлено тем, что весь оставшийся, неразвезённый груз (к пунктам на оставшейся части t t (,1) текущего цикла 1 ) придётся везти дальше, чем прежде, на L L L величину (при > 0 ), или ближе (при < 0 ). С учётом (4.5) и jr-1,, jr (4.6) изменение энергозатрат по второй причине вычисляется по формуле L tr,2( )= = (c + c, jr - c ).

. (4.7) a a j j jr-1,, jr jr-1, jr-1, jr t t j,1 j, Общее изменение энергозатрат как сумма приращений (4.6) и (4.7) на t -м шаге вычисляется по формуле, Gt, r, (4.8) tr( )= a + c - c c + a c jr -1 -ij j t t,, jr jr, jr (i, j)1, j, t где j,1 означает, что суммирование грузов производится по тем t t пунктам, которые на t -м шаге находятся по маршруту,1 1.

Выбор номера интервала rt и номера, включаемого в этот t интервал, производится из условия минимума прироста энергозатрат:

min min{tr ( )}= trt ( ) rt,, rt rt r=1;t+Gt где, как и ранее, Gt – множество номеров пунктов, ещё не вошедших в текущий цикл.

Полученные соотношения позволяют сформулировать алгоритм решения обобщенной задачи коммивояжера, блок-схема которого представлена на рис. 4. Работу алгоритма проиллюстрируем на числовом примере, представленном в табл. 18 ( =1) при а = (1,2,4,3,1).

Так как, в отличие от классической задачи коммивояжера, обобщенная задача коммивояжера неинвариантна к начальному пункту цикла, то выбирается конкретный исходный пункт (пусть k = 1).

Промежуточным пунктом Am в исходном цикле 1 может быть выбран любой из оставшихся пунктов (пусть m = 3 ). Согласно 30 для исходного цикла 1 = (1,3,1) имеем G1 = {1,2,3,4,5} \ {1,3} = {2,4,5}, 1 = 1,3,, 1 Э1 = Э(1 ) = a3c1,3 + a1(c1,3 + c3,1) = 4 17 + 1 (17 + 15) =100.

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

Например, при включении номера = 2 G2 во второй интервал ( r = 2) текущего (t = 2) цикла 1 ( ) полное приращение энергозатрат 2 (2) согласно 50 (рис. 4) равно:

tr ( ) = 2 (2) = 1,4,2,3,1 = a2 (c1,4 + c4,2 ) + (a3 + a1)(c2,3 + c3,1 - c2,1) = 2(3 + 8) + (4 + 1)(8 + 12 - 3) = 22 + 85 =107.

Согласно пункту 60 минимальный прирост энергозатрат на шаге t = 2 соответствует включению в интервал r2 = 1 номера пункта A( = 1 = 2 ) 1.

rПримечание. В табл. 19 включаемые в текущий цикл номера пунктов и минимальные приросты энергозатрат выделены жирным шрифтом.

Из табл. 19 видна динамика решения обобщенной задачи коммивояжера методом расширения цикла.

На первом шаге согласно пункту 60 процесса (t =1) в текущий цикл был включен элемент 1 = 4 (интервал r = 4 ), при этом энергозатраты не только не увеличились, но даже уменьшились ( Э1(4) = -46 < 0 ).

Физически это обусловлено тем, что включение элемента 1 = 4 в интервал r =1 сократило длину пути перевозки грузов к пунктам A3(a3 = 4) и A1(a1 =1) на 11 ед. [см. формулу (4.5)]:

Отрицательный прирост энергозатрат может быть получен в том случае, если включение в цикл номера приводит к уменьшению длины пути к последующим пунктам, что имеет rt место, например, на шаге t = 1 (табл. 19).

1,4.3 = с1,4 + с4,3 + с1,3 = 3 + 3 -17 = -11, что уменьшило энергозатраты на ( 4 +1) 11 = 55 ед. [см. формулу (4.7)].

На втором шаге (табл. 19; t = 2 ) минимум прироста энергозатрат был получен при включении элемента 1 = 2 в первый интервал текущего цикла 1,4,3,1.

На третьем шаге в текущий цикл 1,2,4,3,1 включен последний, ещё не вошедший в цикл элемент = 5, при этом энергозатраты возросли на 55 ед. и было получено следующее решение 1 и соответствующие ему энергозатраты:

1рц = 1,2,4,3,5,1, Э(1рц ) = Э 1,2,4,3,5,1 =127, (4.9) где рц – метод расширения цикла.

Таблица 18. c = || сij ||, =j 1 2 3 4 i 1 1 17 3 2 14 12 4 3 15 4 19 4 5 8 3 5 20 2 18 ( a ) = ( 1, 2, 4, 3, 1) j Таблица t = 1, G1 = {2,4,5} t = 2, G2 = {2;5} t = 3, G3 = {5} 1 Э1 = Э 1,3,1 = 100 Э12 = Э 1,4,3,1 = 54 Э1 = Э 1,2,4,3,1 = 1 1 1 2 Эч ( ) r Эч ( ) r Эч ( ) r 1 ( ) 1 ( ) 1 ( ) 1,5,2,4,3,1 1,2,3,1 2 – 20=-18 1 1,2,4,3,1 2+16=18 1 6+70=1,2,5,4,3,1 1,4,3,1 9 – 55=-46 1 1,5,4,3,1 6+80=86 2 11+104=1 1,5,3,1 6+35=41 2 1,4,2,3,1 22+85=107 3 1,2,4,5,3,16+130=1,2,4,3,5,2 1,3,2,1 42+3=45 2 1,4,5,3,1 14+130=144 4 29+26=2 1,3,4,1 108+9=117 3 1,4,3,2,1 20+3=Эрц = Э 1,2,4,3,5,1 =2 1,3,5,1 38+26=64 3 1,4,3,5,1 27+26=Начало 1° Ввод: c = cij, a = (a ), m, n j 2° t = 3° t Начальные значения: 1 = 1, m,1, Gt = {1;n}\ {1;m}, t Эt = Э(1 )= a c1 + a1 (c1 + c1) 4° Нумерация интервалов:

r 1 6 8 6t+474 }} r:

t 1 = 1, j1, j2,..., jr-1, jr,..., jt, jt+ r = 1,t +1, Gt :

5° t r()= a cij + j a c + c - c jr-1,, jr jr-1, jr tt (i, j)1 j 6° Определение rt :

,rt min {tr ( )} = min {tr ( )}= t ( ) rt, min r rt rt rt r=1;t+1 r=1;t+Gt 7° t Номер j = включается в интервал rt цикла r. Пересчет:

rt t t 1+1 = 1 U{rt}, Gt+1 = Gt \{rt}, Эt+1 = Эt + t ( ), t = t +rt rt 8° - Gt = + 0 t 9° Вывод: 1 = 1 = 1, j,...,m,...,1, Э(1 )= Эt Конец Рис. 4. Блок-схема алгоритма решения обобщенной задачи коммивояжера Найденное методом расширения цикла решение на 12,4 % имеет большие энергозатраты, чем оптимальное решение 1, полученное полным перебором всех N вариантов (N = (n -1)!= 4!= 24) :

0 1 = 1,4,3,2,5,1, Э(1 ) = Э 1,4,3,2,5,1 =113. (4.10) Как и при решении классической задачи коммивояжера, решение, найденное методом расширения цикла, следует попытаться улучшить на основе проверки первого необходимого условия оптимальности.

Действительно, анализ структуры решений (4.9), (4.10) показал, что выделенные в них жирным шрифтом элементы [см. формулу (4.11)] не являются минимальными ни в строках, ни в столбцах матрицы c (табл. 18):

L(1 ) = 1,2 + c2,4 + c4,3 + c3,5 + c5,1 = 1+ 4 + 3 + 21 + 20 = 49, (4.11) L(1 ) = c1,4 + c4,3 + c3,2 + c2,5 + 5,1 = 3 + 3 + 4 + 10 + 20 = 40.

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

3 5 =, = + = + = = L( ) L 3 2,5 c3 2 c 4 10 14 вместо с3,5 ( ),,, 2,5 1 = = + + = + + = = L( ) L 5,2,4,1 c c c4,1 2 4 5 11 (вместо с5,2 20), (4.12), 5 2 2,, 2,5 = = = L( ) L 2,5 c2,5 10.

Таким образом, с учётом (4.11), (4.12) уменьшение общей длины каждого из маршрутов в (4.11) будет соответственно равно:

L(1рц ) = (21-14) + (20 -11) = 7 + 9 = 16, (4.13) L(1 ) = (10 -10) + (20 -11) = 0 + 9 = 9.

Новые маршруты 1рц, 1 будут получены из (4.10) и (4.9) при замене в них участков 3;5, 5;1 соответственно на 3,2,5 и 5,2,4,1 :

1рц = 1,2,4,3,2,5,2,4,1, L 1рц = 49 -16 = 33, (4.14) 0 1 = 1,4,3,2,5,2,4,1, L 1 = 40 - 9 = 31.

Примечание. Жирным шрифтом выделены номера «транзитных» пунктов, которые коммивояжер проходит транзитом, т.к. предназначенный для них груз уже оставлен в них при первом проходе.

При прочих неизменных условиях уменьшение энергозатрат, обусловленное уменьшением расстояния перевозки грузов a5 = 1 и a1 = на 7 ед. (см. (4.13) для 1рц ) и груза a1 = 1 – на 9 ед., согласно (4.7) равно:

2 рц = 1 = + 3,5 + 5,1 = + + = Э Э ( ) ( a 5 a1) a1 (1 1) 7 1 9 23.

Аналогично Э2 (1 ) = a1 5,1 = 19 = 9. (4.15) С учётом (4.10), (4.9) и (4.15) уменьшенные значения энергозатрат равны 1:

Э 1рц = Э(1рц)- Э2 (1рц ) = 127 - 23 = 104, (4.16) 0 0 Э 1 = Э(1 )- Э2 (1 ) = 113 - 9 = 104.

Из (4.16) следует, что существуют, по крайней мере, два равнозначных по энергозатратам маршрута (4.14), однако различных по длине цикла.

Решение задачи коммивояжера может существенно отличаться от решения обобщенной задачи коммивояжера. Это обусловлено вектором грузов a = (a )n. Например, при рассмотренном векторе a длина пути j кратчайшего замкнутого маршрута и соответствующие ему энергозатраты соответственно равны:

0 L(1 ) = L 1,5,2,4,3,2,4,1 = 28, Э(1 ) = 146, что на 40 % больше минимальных энергозатрат (4.16).

Энергозатраты для (4.14) могут быть вычислены непосредственно по формуле (4.10).

4.3. Модифицированный метод расширения цикла и решение обобщенной задачи коммивояжера Модификация метода расширения цикла, как и ранее, будет состоять в том, что для включения номера Gt в некоторый r -й интервал, при соединении с границами этого интервала будут использоваться соответствующие кратчайшие маршруты, получаемые на основе алгоритма эстафетного метода или заготовленные заранее. Особенность модифицированного метода расширения цикла состоит в том, что на каждом t -м шаге процесса в текущий цикл может быть включено более одного номера пунктов Aj из множества Gt, а следовательно, формулу приращения (4.8) при вычислении суммарного приращения придется применять подряд несколько раз, каждый раз используя при этом весь текущий цикл (все его элементы). Поэтому на каждом шаге будет удобней применять не формулу приращений (4.8), а для каждого пробного варианта вычислять и сравнивать полные энергозатраты, найденные согласно (4.1).

При сравнении пробных вариантов текущего цикла на каждом шаге процесса критерия минимума приращения энергозатрат уже будет недостаточно, так как он не учитывает количество элементов nr ( ) из множества Gt, которое войдет в r -й интервал вместе с включаемым элементом Gt 1. В качестве критерия, учитывающего указанный фактор, может быть использован показатель удельных энергозатрат t r ( ), то есть приращение средних затрат, приходящихся на один r включенный в данный интервал jr-1 j «нетранзитный» номер j :

t t tr ( ) Эr ( ) - Эr-t r ( ) = =, Gt, r, (4.17) t t nr ( ) nr ( ) t t где Эr-1, Эr ( ) – энергозатраты соответственно до и после включения t t элемента Gt в интервал ( jr -1 jr ) текущего цикла 1 ; nr ( ) – общее количество «нетранзитных» элементов j Gt, включаемое при t этом в цикл 1.

Критерий (4.17) для выбора элемента, включаемого в rt -й rt t интервал текущего цикла 1, соответствует задаче минимизации общих энергозатрат Э(1 ), которая эквивалентна задаче минимизации t В не включаются «транзитные» элементы, т.е. номера тех пунктов, в которые груз n ( ) r уже доставлен при первом проходе.

удельных энергозатрат Э(1 ) n при n = const. Вычислительную схему проиллюстрируем на примере графа, заданного в табл. 18, что даёт возможность сравнить решение с решением, полученным ранее методом расширения цикла (4.16). Для удобства расчетов на основании табл. вычислено и записано семейство кратчайших маршрутов (табл. 20), полученное эстафетным методом. Вычисления модифицированным методом и основные результаты представлены в табл. 21.

На первом шаге (t =1) в качестве начального используется нулевой н цикл 1 = 1;1, в единственный интервал которого поочередно вставляются элементы G1 = {2,3,4,5}, соединённые с границами интервала через кратчайшие маршруты, взятые из табл. 20. Например, t пробный цикл 1 (r, ) = 1 (1;3), записанный в графе 4 второй строки, получен путём включения в интервал r =1 элемента = 3 с помощью двух кратчайших маршрутов, взятых из табл. 20:

Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |   ...   | 13 |






















© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.