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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

55
4.3. Модифицированный метод расширения цикла
и решение обобщенной задачи коммивояжера
Модификация метода расширения цикла, как и ранее, будет состоять в
том, что для включения номера
t
G∈
γ
в некоторый
r
-й интервал, при
соединении
γ
с границами этого интервала будут использоваться
соответствующие кратчайшие маршруты
, получаемые на основе
алгоритма эстафетного метода или заготовленные заранее. Особенность
модифицированного метода расширения цикла состоит в том, что на
каждом
t
-м шаге процесса в текущий цикл может быть включено более
одного номера пунктов
j
A из множества
t
G , а следовательно, формулу
приращения (4.8) при вычислении суммарного приращения придется
применять подряд несколько раз, каждый раз используя при этом весь
текущий цикл (все его элементы). Поэтому на каждом шаге будет удобней
применять не формулу приращений (4.8), а для каждого пробного варианта
вычислять и сравнивать полные энергозатраты, найденные согласно (4.1).
При сравнении пробных вариантов
текущего цикла на каждом шаге
процесса критерия минимума приращения энергозатрат уже будет
недостаточно, так как он не учитывает количество элементов
)(
γ
r
n из
множества
t
G , которое войдет в
r
-й интервал вместе с включаемым
элементом
t
G∈
γ
1
. В качестве критерия, учитывающего указанный
фактор, может быть использован показатель
удельных энергозатрат
)(
γε
t
r
, то есть приращение средних затрат, приходящихся на один
включенный в данный интервал
rr
jj ÷
−1
«нетранзитный» номер
j
:
, , ,
)(
)(
)(
)(
)(
1
rG
n
ЭЭ
n
t
t
r
t
r
t
r
t
r
t
r
t
r
∀∈
−
=
Δ
=
−
γ
γ
γ
γ
γ
γε
(4.17)
где
1−t
r
Э , )(
γ
t
r
Э – энергозатраты соответственно до и после включения
элемента
t
G∈
γ
в интервал
)(
1 rr
jj ÷
−
текущего цикла
t
1
μ
; )(
γ
t
r
n –
общее количество «нетранзитных» элементов
t
Gj ∈ , включаемое при
этом в цикл
t
1
μ
.
Критерий (4.17) для выбора элемента
t
r
γ
, включаемого в
t
r
-й
интервал текущего цикла
t
1
μ
, соответствует задаче минимизации общих
энергозатрат
(
0
1
μ
Э , которая эквивалентна задаче минимизации
1
В
)(
γ
t
r
n
не включаются «транзитные» элементы, т.е. номера тех пунктов, в которые груз
уже доставлен при первом проходе.

Страницы