Элементарные решения неэлементарных задач на графах. Берзин Е.А. - 47 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

Составители: 

Рубрика: 

49
∑
∈
⋅=⋅=Δ
t
ji
ji
tt
r
caLa
γ
μ
γγγ
γ
,1
),(
,,1
1,
)( , (4.6)
где
t
L
γ
,1
– длина пути от исходного пункта
1
A
до включенного в цикл
пункта
γ
A
.
Изменение энергозатрат по второй причине будет обусловлено тем,
что весь оставшийся, неразвезённый груз (к пунктам на оставшейся части
(
t
1,
γ
μ
) текущего цикла
t
1
μ
) придётся везти дальше, чем прежде, на
величину
L
jj
rr
,,
1
γ
δ
−
(при 0>
L
δ
), или ближе (при 0
<
L
δ
). С учётом (4.5) и
(4.6) изменение энергозатрат по второй причине вычисляется по формуле
()
(
)
.
,,,,,
2,
11
1,
1
1,
rrrr
t
rr
t
jjjj
j
j
L
jj
j
j
t
r
cccaa
−−−
−+
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
=⋅
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
=Δ
∑∑
∈∈
γγ
μ
γ
μ
γγ
δγ
. (4.7)
Общее изменение энергозатрат как сумма приращений (4.6) и (4.7)
на
t -м шаге вычисляется по формуле
()
, , ,
,,,
),(
11
1,,1
rGcccaca
t
jjjj
j
j
ji
ij
t
r
rrrr
tt
∀∈
⎟
⎠
⎞
⎜
⎝
⎛
−+
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
+⋅=Δ
−−
∑∑
∈∈
γγ
γγ
μμ
γ
γγ
(4.8)
где
t
j
1,
γ
μ
∈ означает, что суммирование грузов производится по тем
пунктам, которые на
t
-м шаге находятся по маршруту .
11,
tt
μμ
γ
⊂
Выбор номера интервала
t
r и номера
t
γ
, включаемого в этот
интервал, производится из условия минимума прироста энергозатрат:
{
}
ttt
t
rtr
t
r
t
r
G
tr
r
γγγ
γ
, )()(minmin
1;1
⇒Δ=Δ
∈
+=
,
где, как и ранее,
t
G – множество номеров пунктов, ещё не вошедших в
текущий цикл.
Полученные соотношения позволяют сформулировать алгоритм
решения обобщенной задачи коммивояжера, блок-схема которого
представлена на рис. 4. Работу алгоритма проиллюстрируем на числовом
примере, представленном в табл. 18
)
1
=
ϕ
при а = (1,2,4,3,1).
Так как, в отличие от классической задачи коммивояжера,
обобщенная задача коммивояжера неинвариантна к начальному пункту

Страницы