К вопросу о нахождении значения маршрутной задачи с ограничениями
Розглянуто задачу послідовного обходу мегаполісів з обмеженнями різних типів. Вважається, що функції вартості, а також «поточні» обмеження можуть залежати від списку завдань (можлива залежність від списку виконаних або, навпаки, ще не виконаних завдань). Запропоновано підхід до визначення глобальног...
Збережено в:
| Дата: | 2016 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2016
|
| Назва видання: | Проблемы управления и информатики |
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/208063 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | К вопросу о нахождении значения маршрутной задачи с ограничениями / А.Г. Ченцов, А.А. Ченцов // Проблемы управления и информатики. — 2016. — № 1. — С. 41-54. — Бібліогр.: 17 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-208063 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-2080632025-10-19T00:17:44Z К вопросу о нахождении значения маршрутной задачи с ограничениями До питання про знаходження значення маршрутної задачі з обмеженнями On the problem of obtaining the value of routing problem with constraints Ченцов, А.Г. Ченцов, А.А. Оптимальное управление и методы оптимизации Розглянуто задачу послідовного обходу мегаполісів з обмеженнями різних типів. Вважається, що функції вартості, а також «поточні» обмеження можуть залежати від списку завдань (можлива залежність від списку виконаних або, навпаки, ще не виконаних завдань). Запропоновано підхід до визначення глобального екстремуму (значення задачі) на основі динамічного програмування в широкому сенсі. Завдяки такому підходу досягається економія пам’яті комп’ютера, що дозволяє визначати экстремум в задачі більшої розмірності та використовувати його для тестування евристичних алгоритмів. Для побудови шарів функції Беллмана використовується скорочена процедура, що дозволяє зменшити складність обчислювань (за умов передування не передбачається побудова всього масиву значень функції Беллмана). The problem of sequential travelling of megapolises with constraints of different types is considered. It is supposed that cost functions and «current» constraints can be dependent on the tasks list (it is possible that dependence on the fulfilled or nonfulfilled tasks arises). Approach to determination of global extremum (the problem value) on the basis of widely interpreted dynamic programming is proposed. Under given approach, economy of computer memory is reached; this permits to determine extremum in problem with larger dimensionality and use it for testing of heuristic algorithms. Under construction of layers of Bellman function, truncated procedure which enables one to decrease computing complexity is used (under preceding conditions, construction of all array of the Bellman function values is not provided). 2016 Article К вопросу о нахождении значения маршрутной задачи с ограничениями / А.Г. Ченцов, А.А. Ченцов // Проблемы управления и информатики. — 2016. — № 1. — С. 41-54. — Бібліогр.: 17 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/208063 519.6 10.1615/JAutomatInfScien.v48.i2.30 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Оптимальное управление и методы оптимизации Оптимальное управление и методы оптимизации |
| spellingShingle |
Оптимальное управление и методы оптимизации Оптимальное управление и методы оптимизации Ченцов, А.Г. Ченцов, А.А. К вопросу о нахождении значения маршрутной задачи с ограничениями Проблемы управления и информатики |
| description |
Розглянуто задачу послідовного обходу мегаполісів з обмеженнями різних типів. Вважається, що функції вартості, а також «поточні» обмеження можуть залежати від списку завдань (можлива залежність від списку виконаних або, навпаки, ще не виконаних завдань). Запропоновано підхід до визначення глобального екстремуму (значення задачі) на основі динамічного програмування в широкому сенсі. Завдяки такому підходу досягається економія пам’яті комп’ютера, що дозволяє визначати экстремум в задачі більшої розмірності та використовувати його для тестування евристичних алгоритмів. Для побудови шарів функції Беллмана використовується скорочена процедура, що дозволяє зменшити складність обчислювань (за умов передування не передбачається побудова всього масиву значень функції Беллмана). |
| format |
Article |
| author |
Ченцов, А.Г. Ченцов, А.А. |
| author_facet |
Ченцов, А.Г. Ченцов, А.А. |
| author_sort |
Ченцов, А.Г. |
| title |
К вопросу о нахождении значения маршрутной задачи с ограничениями |
| title_short |
К вопросу о нахождении значения маршрутной задачи с ограничениями |
| title_full |
К вопросу о нахождении значения маршрутной задачи с ограничениями |
| title_fullStr |
К вопросу о нахождении значения маршрутной задачи с ограничениями |
| title_full_unstemmed |
К вопросу о нахождении значения маршрутной задачи с ограничениями |
| title_sort |
к вопросу о нахождении значения маршрутной задачи с ограничениями |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2016 |
| topic_facet |
Оптимальное управление и методы оптимизации |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/208063 |
| citation_txt |
К вопросу о нахождении значения маршрутной задачи с ограничениями / А.Г. Ченцов, А.А. Ченцов // Проблемы управления и информатики. — 2016. — № 1. — С. 41-54. — Бібліогр.: 17 назв. — рос. |
| series |
Проблемы управления и информатики |
| work_keys_str_mv |
AT čencovag kvoprosuonahoždeniiznačeniâmaršrutnojzadačisograničeniâmi AT čencovaa kvoprosuonahoždeniiznačeniâmaršrutnojzadačisograničeniâmi AT čencovag dopitannâproznahodžennâznačennâmaršrutnoízadačízobmežennâmi AT čencovaa dopitannâproznahodžennâznačennâmaršrutnoízadačízobmežennâmi AT čencovag ontheproblemofobtainingthevalueofroutingproblemwithconstraints AT čencovaa ontheproblemofobtainingthevalueofroutingproblemwithconstraints |
| first_indexed |
2025-10-19T01:10:54Z |
| last_indexed |
2025-10-20T01:14:21Z |
| _version_ |
1846461450499915776 |
| fulltext |
© А.Г. ЧЕНЦОВ, А.А. ЧЕНЦОВ, 2016
Международный научно-технический журнал
«Проблемы управления и информатики», 2016, № 1 41
УДК 519.6
А.Г. Ченцов, А.А. Ченцов
К ВОПРОСУ О НАХОЖДЕНИИ
ЗНАЧЕНИЯ МАРШРУТНОЙ ЗАДАЧИ
С ОГРАНИЧЕНИЯМИ
Прототипом задач маршрутизации перемещений с ограничениями, возникающих
в различных областях практической деятельности, является известная труднорешаемая
задача коммивояжера (ЗК). В связи с решением ЗК и задач такого типа отметим метод
ветвей и границ, а также динамическое программирование (ДП), однако из-за
трудностей вычислительного характера (ЗК — одна из классических NP-полных
задач) активно используются эвристические алгоритмы, особенно в тех вариантах
ЗК, которые не являются «метрическими» (когда матрица затрат не определяется
функцией расстояния). В частности, широко применяются варианты «жадного»
алгоритма, реализующие в нужной форме идею оптимизации текущих затрат.
Задачи маршрутизации, возникающие в приложениях, обычно сопровождаются
большим числом разнообразных ограничений, что приводит к применению эвристи-
ческих алгоритмов с безусловным соблюдением упомянутых ограничений. Среди
последних особо отметим так называемые условия предшествования (условия типа
«одно после другого»), которые удается [1, § 4.9] использовать для снижения
сложности вычислений при решении задачи по методу ДП. С другой стороны, данные
условия часто встречаются в прикладных задачах, таких, в частности, как задачи,
ориентированные на снижение облучения персонала АЭС (атомная энергетика), и
задачи, связанные с управлением при листовой резке на станках с числовым
программным управлением (ЧПУ) (см. [2, 3]). Так, например, в последнем случае для
деталей с несколькими внутренними контурами вначале требуется выполнить резку
именно внутренних контуров, а не внешних. На этапе раскроя возможно также
размещение одних деталей внутри других, и в этом случае (схема «матрешки»)
внутренние детали следует вырезать раньше внешнего контура объемлющей детали.
Упомянутые обстоятельства определяют особую роль условий предшествования:
связанные с ними ограничения, с одной стороны, достаточно широко распростра-
нены, а с другой, могут быть использованы в своеобразном «положительном» направ-
лении (в смысле снижения сложности вычислений). Другие ограничения, связанные с
потребностями прикладных задач, являются на сегодняшний день серьезными ослож-
няющими факторами, что делает эвристические алгоритмы еще более значимыми,
хотя качество последних не всегда удовлетворительно.
В связи с этим представляет особый интерес разработка методов, позво-
ляющих оценивать качество эвристик, что, собственно, и нашло свое отражение в
многочисленных исследованиях по построению приближенных алгоритмов [4].
Еще одна возможность связана с попыткой найти значение маршрутной задачи,
т.е. оптимальный результат, с которым можно сравнивать результаты, доставляе-
мые эвристиками, и таким образом оценить качество последних. Именно такая
цель ставится в настоящей работе; для ее достижения предполагается задейство-
вать (в условиях ограничений различных типов) аппарат широко понимаемого ДП.
Заметим, что основное затруднение, касающееся непосредственного применения
ДП для поиска оптимальных решений задач маршрутизации, связано с дефицитом
Работа выполнена при финансовой поддержке РФФИ (грант 15-01-07909).
60
1956 2016
42 ISSN 0572-2691
памяти ЭВМ: требуется хранить массив значений функции Беллмана (в [1, § 4.9]
показано, что упомянутый массив может насчитываться не полностью, если
рассматривается задача с условиями предшествования; однако и в данной, «усе-
ченной», версии требования к памяти вычислителя остаются жесткими). В настоя-
щей работе показано, что если ограничиться поиском значения (экстремума)
задачи, то нагрузку на память вычислителя можно существенно ослабить, введя
«послойную» процедуру с обновлениями: слой функции Беллмана, не актуальный с
точки зрения поиска значения задачи, удаляется и размещается новый слой
функции. Целью данного исследования является нахождение значения (экстре-
мума) по методу ДП для, возможно, большей размерности исходной задачи
(заметим, что если строить оптимальное решение посредством ДП, то вышеупомя-
нутое удаление слоев функции Беллмана недопустимо). Это значение предпо-
лагается использовать для оценивания качества эвристик.
В связи с применением ДП для решения ЗК отметим работы [5, 6]. Метод ветвей
и границ [7] получил широкое распространение в задачах дискретной оптимизации
и, в частности, при решении ЗК. Отметим обстоятельные обзоры имеющихся методов
решения ЗК и задач такого типа в [4, 8–10]. В то же время имеется ряд работ
инженерной направленности (см., в частности, [2, 3]), в которых развиваются
подходы и эвристические методы решения прикладных задач со специфическими
ограничениями различных типов. Рассматривая последнее направление, в настоящей
работе опишем общий вариант ДП: речь идет о задаче последовательного обхода
мегаполисов при условиях предшествования, причем и функции стоимости, и сами
«текущие» ограничения зависят от списка заданий. В настоящей работе данный
список отвечает заданиям, которые еще не выполнены на данный момент времени.
Однако к этой постановке легко сводится случай, когда (при формировании функций
стоимости и развивающихся в процессе реализации конкретных «маршрутных»
решений динамических ограничений) существенна аналогичная зависимость
от списка уже выполненных заданий (работ).
1. Некоторые обозначения общего характера
Если S — множество, то )(P S и )('P S обозначим соответственно семейства
всех и всех непустых подмножеств множества ;S )(Fin S — семейство всех
конечных множеств из )('P S (элементы )(Fin S — непустые конечные подмно-
жества S и только они). Произвольным объектам x и y сопоставляем единственное
множество ,};{ yx содержащее ,x y и не содержащее никаких других элементов
};{( yx — неупорядоченная пара объектов ,x ).y Объекту z сопоставляем синглетон
};{=}{ zzz
(здесь и ниже
= — равенство по определению), содержащий .z Как
обычно в теории множеств [11, с. 67], любым двум объектам p и q сопоставляем
упорядоченную пару (УП) }};{};{{=),( qppqp
с первым элементом p и вторым .q
Если z — какая-либо УП, то )(pr1 z и )(pr2 z обозначим соответственно первый
и второй элементы ,z однозначно определяемые условием ))(pr),(pr(= 21 zzz ; при
,BAz где A и B — множества, имеем Az )(pr1 и .)(pr2 Bz Триплет
),,( cba произвольных объектов ,a b и c определяется [12, с. 17] в виде спе-
циальной УП: .)),,((=),,( cbacba
В связи с этим для любых непустых множеств ,A
B и ,C используя определение [12, с. 17], имеем ;)(= CBACBA
если при
этом ,: DCBAg где D — непустое множество, то при BAx и Cy
определено значение ,),( Dyxg отвечающее аргументу )),(pr),(pr(),( 21 yxxyx
и обозначаемое также ),(pr( 1 xg .)),(pr2 yx
Международный научно-технический журнал
«Проблемы управления и информатики», 2016, № 1 43
В дальнейшем R — вещественная прямая, )('P...}2;{1;= RN
и
{0}=0N
;)('P...}2;1;{0;= RN полагаем
.)}(&)({=, 000 NNN
qpqiipiqp
Ясно, что =01, (пустое множество) и .mmkkm NN }{=1, Каж-
дому непустому конечному множеству K сопоставляем его мощность (количест-
во элементов) ;NK полагаем .0=
Если K — непустое конечное мно-
жество, то ][(bi) K обозначим (непустое) множество всех биекций множества
K1, на .K
В дальнейшем ][R T обозначим множество всех функций, действующих
из непустого множества T в полуось ;}0{=[[0,
R в качестве T
используем далее конечное множество.
2. Постановка маршрутной задачи
Фиксируем непустое множество ,X точку ,0 Xx (натуральное) число
,2, NN N и множества
),(Fin...,),(Fin1 XMXM N (1)
называемые далее мегаполисами. В отношении (1) полагаем, что
}).{\1,1,=(&)1,( 0 pNqNpMMNjMx qpj
Кроме того, полагаем заданными отношения
),(PM̂...,),(PM̂ 111 NNN MMMM (2)
элементы которых (а это — УП) определяют возможные варианты выполнения
(внутренних) работ при посещении мегаполисов (1). Рассмотрим процессы вида
),(...)( )(
)(
2)(
)(
1(1)
(1)
2(1)
(1)
1
0
N
N
N
N
MxMxMxMxx (3)
где — перестановка множества ,1, N .M̂),(...,,M̂),( )(
)(
2
)(
1(1)
(1)
2
(1)
1 N
NN
xxxx
При естественных переобозначениях (3) сводится к виду
,M̂...M̂ )(
)(
(1)
(1)0
N
Nzzz
(4)
где (здесь и ниже) .),(= 000 xxz
Будем считать, что и выбор , и выбор
)((1) ...,, Nzz стеснены дополнительными ограничениями, для описания которых
введем некоторые новые обозначения. Если ,1, Nj то полагаем
}M̂:)(pr{=},M̂:)(pr{=M 21 jjjj zzzz
M
(у каждого мегаполиса выделены множества всех возможных пунктов прибытия и
отправления соответственно (3)). Тогда
).X̂(Fin}{=),(Fin}{=X̂
1=
0
1=
0
i
N
i
i
N
i
xXMx MX (5)
44 ISSN 0572-2691
С учетом (5) фиксируем мультифункции
),(PN̂:...,),(PN̂: 11 NN MAMA XX (6)
где .)1,(P=N̂ N
Если ,1, Nj Xx и ,N̂K то ),( KxAj определяет мно-
жество всех точек ,jM в которые возможно перемещение из x при условии,
что K определяет список еще невыполненных заданий. Всюду в дальнейшем
предполагается, что
KjKxKxA jj N̂M),( X (7)
(условие (7) позволяет стыковать внешние перемещения и внутренние работы).
Пусть ]1,[(bi)= N
P (множество всех перестановок индексного множества ).1, N
Напомним, что в (3), (4) .P Полагаем, однако, что выбор может быть
стеснен условиями предшествования. В связи с этим условимся, что при P
обратная по отношению к перестановка обозначается :1 P1
и
.1,=))((=))(( 11 Nkkkk
Фиксируем множество ;)1,1,(P NN K элементы ,K являющиеся УП, именуем
адресными парами. Если ,Kz то )(pr1 z имеет смысл отправителя, а )(pr2 z —
получателя адресной пары .z Полагаем далее, что
.)(pr)(pr:)(P 0201000 KKKK zzzz
Тогда [1, ч. 2] имеем следующее свойство:
NtNtz 1,1,{= 21
KPA
=)}<()))(=)(pr(&))(=)(pr(( 212211 tttztz
),('P}))(pr(<))(pr(|{= 2
1
1
1
PKP zzz (8)
т.е. K-допустимые по предшествованию маршруты (перестановки индексов) сущест-
вуют. Как видно из (3), (4), маршрут (перестановка индексов) еще не определяет
течение процесса, поэтому введем понятие траектории, согласованной с тем или
иным маршрутом. Сначала условимся, что Z — def -множество всех кортежей
.X̂0,:)(
0,
X
Nz
Nii
Теперь, ориентируясь на вариант (4), при P введем в рассмотрение
(непустое) множество
&)1,M̂(&)=(){(=Z )(
0
00,
Nzzzz
Nii
Z
).(P)}1,}),:)({),(pr()(pr(& 12)(1 Z NsNsjjzAz sss (9)
Тогда, в частности, в виде }Z)())(,{(=
0,0,
NiiNii zz ZAD имеем непустое
конечное множество допустимых решений (ДР) исследуемой ниже экстремальной
задачи. Для ее точной формулировки введем функции стоимости, фиксируя
][R],N̂X̂[R...,],N̂X̂[R],N̂X̂[R 1 XXXXc fcc N (10)
Международный научно-технический журнал
«Проблемы управления и информатики», 2016, № 1 45
(реально функции стоимости задаются на подмножествах ,N̂X̂X N̂X̂ X и ,X
но продолжим их произвольным образом на упомянутые три множества, что не
составляет труда, но несколько упрощает обозначения). Заметим, что при ,A
Z)(
0,Niiz и Ns 1, определены значения
[,[0,}),:)({),(pr),(pr( 112 Nsttzz ssc
,[[0,)}),:)({,()( Nsttzc ss
имеем также .[[0,))(pr( 2 Nzf С учетом этого введем аддитивный критерий,
полагая, что
])}),:)({,()}),:)({),(pr),(pr([=])[( )(112
1=
0,
NsttzcNsttzzz ssss
N
s
Nii cC
.Z)())(pr(
0,2
NiiN zzf A (11)
Итак, посредством (11) оценивается каждое ДР из .D Задаче
,))(,(,min])[(
0,0,
DC
NiiNii zz (12)
сопоставляется значение [[0, V (экстремум критерия):
].)[(min
Z
min=
0,
)(
0,
Nii
z
zV
Nii
C
A
(13)
В настоящей работе ставим своей целью определение V (13). Представляется, что
данная цель достижима при меньших ресурсах памяти в сравнении с полным
решением задачи (12) по методу ДП; найденное значение V предполагается исполь-
зовать для оценивания качества эвристических решений данной (весьма сложной)
маршрутной задачи. Схему построений, направленную на определение ,V изложим
ниже в виде соответствующего алгоритма на функциональном уровне.
3. Некоторые построения общего характера
В настоящем разделе кратко коснемся вопроса о представлении функции Беллма-
на, используя вариант расширения задачи (12), соответствующий идейно [13–15].
Введем сначала при N̂K множество KZ всех кортежей
.Kz
Kii X
X̂0,:)(
||0,
Тогда полагаем при ,Xx N̂K и ,][(bi) K что
&)1,M̂(&)),(=(){(=),,(Z )(0||0,
KtzxxzzKx ttKKii
Z
)}.1,}),:)({),(pr()(pr(& 12)(1 KsKsjjzAz sss (14)
Учитывая определение ,P получаем из (9), (14), что ),1,,(Z=Z 0 Nx при .P
Для построения нужного расширения исходной задачи потребуется редукция
ограничений [1, ч. 2]. С этой целью введем отображение ,I действующее в N̂ по
правилу
]},[:)(pr{\=)( 2 KzzKK
I
46 ISSN 0572-2691
где )})(pr(&))(pr({=][ 21 KzKzzK
K при .N̂K В этих терминах
вводится [1, ч. 2] другой тип допустимости маршрутов: допустимость по
вычеркиванию. Итак, при N̂K получаем, что [1, предложения 2.2.2, 2.2.3]
]),[(bi)(P}1,}),:)(({)(][(bi){=][bi)( KKkKkttkKK
II (15)
т.е. (15) есть множество (непустое) допустимых по вычеркиванию частичных марш-
рутов посещения мегаполисов ., KkMk Напомним, что [1, ч. 2]
&))1,((1)({=]1,[bi)(= NN IPIA
).(P)}2,})11,:)({\1,()((& PI NkkttNk (16)
Из (14), (15) получаем, что при Xx и N̂K
)][(bi)(Fin)},,(Z)(][bi)())(,{(=)(
||0,||0, KKiiKKiiK KKxzKzx ZZID
есть непустое множество ДР частичной задачи, отвечающей позиции .),( Kx Для
формулировки последней введем соответствующий аддитивный критерий: при
,Xx ,N̂K ][bi)( K I и ),,(Z)(
||0,
Kxz
Kii полагаем, что
}),:)({),(pr),(pr([=))((ˆ
112
||
1=
||0,
KsttzzKz ss
K
s
Kii cC
)).(pr(})],:)({,( ||2)( Kss zfKsttzc (17)
С учетом (17) сопоставляем каждой позиции ,),( Kx ,Xx ,N̂K следующую
частичную задачу:
),())(,(,min))((ˆ
||0,||0,
xzKz KKiiKii DC
(18)
ограничения которой совместны, а значение (экстремум)
[.[0,))((ˆmin
),,(Z
min=),(
||0,
)(][bi)(
||0,
Kz
Kx
Kxv
Kii
zK
Kii
C
I
(19)
Из (19), в частности, получаем (см. (16) и ранее упомянутые свойства пучков
траекторий), что
),1,,(= 0 NxvV (20)
а сама основная задача (12) может быть погружена в семейство частичных задач (18).
Наконец, полагаем, что
.)(=),( X xxfxv (21)
Таким образом, посредством (19), (21) на множестве )1,(P NX определена
функция Беллмана ,v [[0,)1,(P: Nv X , для которой имеет место важное
равенство (20). Итак, в виде семейства задач (18), дополненного соглашением (21),
получаем расширение исходной задачи (12). С учетом (7) получаем, что
. N̂)},()(prM̂{=),(Â 1 KjKxKxAzzKx jjj
X (22)
По аналогии с [13–15] устанавливается следующая теорема.
Международный научно-технический журнал
«Проблемы управления и информатики», 2016, № 1 47
Теорема. Если Xx и ,N̂K то
})].{\),(pr(),()),(pr,([min
),(
min=),( 21
Â)(
jKzvKzcKzx
Kx
Kxv j
jzKj
c
I
Из (20) и теоремы вытекает, в частности, что
})].{\1,),(pr()1,,()1,),(pr,([min
)1,,(
min= 21
0
0Â)1,(
jNzvNzcNzx
Nx
V j
jzNj
c
I
(23)
Теорема определяет уравнение Беллмана, а формула (23) характеризует глобальный
экстремум основной задачи.
4. Рекуррентная процедура построения слоев функции Беллмана
Ниже используется экономичная версия метода ДП, восходящая к [1, § 4.9]
(более поздние варианты см. в [13–15]). Речь идет о том, чтобы отказаться
(при наличии условий предшествования) от построения всего массива значений
функции .v В связи с этим полагаем, что
.)})(pr())(pr(N̂{=G 21 KzKzzK
K (24)
Множества, элементы семейства G, именуем существенными списками заданий.
Упомянутые списки ранжируем по мощности; полагаем, что }=G{=G KsKs
.1, Ns При этом, конечно, семейства ,1,,G Nss образуют разбиение .G
Ясно, что }1,{=G NN (синглетон, содержащий множество ).1, N С другой
стороны, }:)(pr{= 11 KK
zz определяет :G1
}.\1,:}{{=G 11 KNtt (25)
Заметим также, что [13, (6.2)] имеет место свойство
.2,)}(,G:}{\{=G 1 NsKtKtK ss I (26)
При этом [1, предложение 4.2.9] .1,G Nss В результате получим
(см. (25), (26)) рекуррентную процедуру 11 G...GG NN с известными
крайними семействами NG и .G1 При этом [13, с. 69] ,\1, 1 KN тогда
)(P=
~
1\1,
XMM
K
i
Ni
и, как следствие, определено (непустое) множество
)).1,(P(P}
~
:),{(=0 NxxD
XM (27)
Кроме того, как и в [13–15], полагаем )}1,,{(= 0 NxDN
(синглетон, содержащий
УП ).)1,,( 0 Nx Если 11, Ns и ,GsK то последовательно конструируем
множества
),\1,(P}G}{\1,{=)(J 1 KNKtKNtK ss
),(P
)(
=][ˆ
J
XMM
j
sj
s
K
K
).G(P]}[ˆ:),{(=][D̂ sss KxKxK
XM
48 ISSN 0572-2691
Cледуя [13–15], в этих обозначениях получаем, что
.11,)G(P][D̂=
G
NsKD ss
sK
s X (28)
Итак, введены слои NDDD ...,,, 10 пространства позиций, являющиеся каждый
непустым множеством. При этом [13, с. 69]
.)(G1,}){\,( 1 kss yKkKNsDkKy MI (29)
Из (29) следует, в частности, понятное свойство:
).,(Â)(),(1,}){\),(pr( 12 KxzKjDKxNsDjKz jss I (30)
С учетом (27), (28) вводим такие определения: если ,0, Ns то полагаем, что
][R ss Dv — такое отображение, что
;),(),(=),( ss DKxKxvKxv
(31)
иными словами, sv определяем как сужение функции v на множество sD . Таким
образом, введены функции
[;[0,:...,[,[0,:[,[0,: 1100 NN DvDvDv (32)
при этом функция Nv в (32) определяется единственным значением (20):
).1,,(= 0 NxvV N (33)
Функция 0v определяется в силу (21), (27) очень просто:
.
~
)(=),(0 M xxfxv (34)
С учетом (30) имеем, что при ,1, Ns ,),( sDKx )(Kj I и ),(Â Kxz j опреде-
лено значение [[0,}){\),(pr( 21 jKzvs . Легко видеть (с учетом теоремы), что
справедливо следующее предложение.
Предложение. Если ,1, Ns то функция 1sv преобразуется в sv по следу-
ющему правилу:
.),(
})]{\),(pr(),()),(pr,([min
),(
min=),( 211
Â)(
s
sj
jzKj
s
DKx
jKzvKzcKzx
Kx
Kxv
c
I
(35)
Таким образом, получаем рекуррентную процедуру
Nvvv ...10 (36)
построения всех функций (32), именуемых далее слоями функции Беллмана:
функция 0v в (36) известна (см. (34)), а преобразование 1sv в ,sv где ,1, Ns
осуществляется по правилу (35). Тогда, в частности, согласно (33) определено
значение ,V т.е. глобальный экстремум основной задачи.
Отметим теперь, что в силу (33), (35)
.})]{\1,),(pr()1,,()1,),(pr,([min
)1,,(
min= 211
0
0Â)1,(
jNzvNzcNzx
Nx
V Nj
jzNj
c
I
(37)
Из (37) видно, что для определения V требуются не все функции (32), а только
функция .1Nv Аналогичным образом из (35) имеем следующее свойство: при
Ns 1, для построения sv достаточно функции .1sv Это существенно с точки
зрения ресурсов памяти используемой ЭВМ. В связи с этим рассмотрим про-
цедуру (36) с целью определения V (13).
Международный научно-технический журнал
«Проблемы управления и информатики», 2016, № 1 49
Начальный (подготовительный) этап состоит в построении функции 0v на
основе формулы (34). Тем самым каждой позиции 0),( DKx сопоставляется
значение [[0,),(0 Kxv .
Последующие этапы процедуры реализуются однотипно: при ,1, Ns
располагая функцией ,1sv значения которой находятся в памяти компьютера,
осуществляется насчитывание массива значений функции sv посредством (35),
после чего новый массив значений, т.е. ,)),(:),(( ss DKxKxv заносится в память
компьютера вместо уже использованного массива значений :),(( 1 Kxvs
;)),(: 1 sDKx последний уничтожается.
Данная операция, включающая полную замену содержимого памяти, пов-
торяется N раз. Результатом ее применения является значение V (33). Точнее,
нахождение V осуществляется на основании .1Nv Для этого, располагая мас-
сивом значений ,)),(:),(( 11 NN DKxKxv искомое значение V рассчитываем
по формуле (37).
Замечание. Упомянутая процедура с постоянным обновлением памяти не
позволяет, в отличие от [1, 13–15], построить ДР, реализующее значение ,V
поскольку [13–15] для этого требуются все функции (32). Однако именно за счет
данного обновления удается увеличить значение ,N для которого V (33) может
быть найдено с помощью процедуры на основе ДП.
5. Оценивание эвристического алгоритма
Располагая значением ,V можем оценить качество эвристических алгоритмов,
применяемых для построения ДР. Данные алгоритмы, не гарантируя близости
к V по результату, позволяют быстро находить соответствующее ДР. Рассмотрим
простейший вариант такого рода — модификацию «жадного» алгоритма [16].
Введем следующее правило. Итак, если Xx и ,N̂K то выбираем )(KIj
и ),(Â Kxjz так, что
)];,()),(pr,([min
),(
min=),()),(pr,( 1
Â)(
1 KzcKzx
Kx
KcKx j
jzKj
czzc
I
j (38)
при этом в качестве x может использоваться либо ,0x либо ,)(pr2 z где lz M̂
и .\1, KNl
Алгоритм действует следующим образом. Находясь в начальной позиции
,)1,,( 0 Nx определяем Xz X̂(0) посредством 0z (см. разд. 1), т.е. полагаем
.= 0(0) z
z Далее используем (38) при )(pr= (0)
2 zx и ;1,= NK находим в этих
условиях j и ,z после чего полагаем jj =1 и .=(1)
zz
Пусть Ns 1, и уже построены ,1, Nt j ,1, st и ,X̂)(
Xz t .0, st
При этом ,= 0(0) zz УП ),( (1)
1 zj определена выше, а при st 2, УП ),( )(t
t zj
определяется посредством (38) в следующей конкретизации:
.=,=},11,:{\1,=),(pr= )(1)(
2 zzjjjz
t
tl
t tlNKx
Если ,= Ns то процедура завершена. Если же ,< Ns то для построения
1sj и 1)( s
z используем (38) при )(pr= )(
2
sx z и ,}1,:{\1,= slNK l j полагая
в данной конкретизации, что jj =1s и .=1)(
zz
s
Из упомянутой выше схемы видно, что Nt 1,j при .1, Nt Кроме того, из
определения множеств (22) имеем, что .0,X̂)( Ntt Xz При этом
).2,})11,:{\1,((&))1,(( 1 NsslNN ls jIjIj (39)
50 ISSN 0572-2691
Из (39) следует, в частности, что N1,1j и }11,:{\1, slN ls jj .,2 Ns
Тогда, как легко видеть,
Pj
Nss 1,
)( (40)
(если lk jj = при ,lk то среди k и l выбираем наименьшее p и наиболь-
шее q ; тогда ,< qp а потому
}11,:{\1, qlN lq jj
и, как следствие, ).qp jj Из (16), (39) и (40) получаем, что
.)(
1,
Aj
Nss (41)
Далее в силу (22) и правила выбора на основе (38) имеем, что
.1,M̂)( Njj
j z (42)
Наконец, из (22) имеем по правилу (38), что
.1,}),:{),(pr()(pr 1)(
2
)(
1 NsNstA t
s
s
s
jzz j (43)
В самом деле, ),1,(1 NIj а }1,:{=1, NsN s j и, стало быть,
}).1,:({1 Nss jIj (44)
Поэтому (см. (38) при )(pr= (0)
2 zx и )1,= NK имеем, что
}),1,:{),(pr(Â (0)
21
(1) Ntt jzz j (45)
а в этом случае из (22) следует, что
}).1,:{),(pr()(pr (0)
21
(1)
1 NtA t jzz j (46)
Пусть .2, Ns Тогда 11,1 Ns и ,))(pr),(pr(= 1)(
2
1)(
1
1)( sss
zzz где со-
гласно правилу выбора в (38)
}).11,:{\1,),(pr(Â 1)(
2
)( stN t
s
s
s
jzz j (47)
С учетом (22) имеем из (47), что
}).11,:{\1,),(pr()(pr 1)(
2
)(
1 stNA t
s
s
s
jzz j (48)
Выбор s был произвольным, и в силу (40) получили, что
.2,}),:{),(pr()(pr 1)(
2
)(
1 NsNstA t
s
s
s
jzz j (49)
Из (45), (49) вытекает, что
.1,}),:{),(pr()(pr 1)(
2
)(
1 NsNstA t
s
s
s
jzz j (50)
Теперь из (9), (43) и (50) имеем по выбору ,(0)
z что
.Z)(
1,
)(0,
)(
NssNs
s
jz (51)
В свою очередь, из (41), (51) вытекает, в частности, что
.))(,)((
,0
)(
1,
Dzj
Ns
s
Nss (52)
Итак, согласно (52) «жадный» алгоритм, определяемый правилом (38), порождает
ДР основной задачи и можно оценить его близость по результату к .V
Международный научно-технический журнал
«Проблемы управления и информатики», 2016, № 1 51
6. Вычислительный эксперимент
Рассматриваемые в настоящей статье алгоритмы решения маршрутной задачи
обхода мегаполисов (точный алгоритм на основе ДП и «жадный» алгоритм)
реализованы в виде программ для ПЭВМ. В качестве мегаполисов в модельном
примере использованы равномерные «сетки» на плоскости, получаемые при
размещении 12 точек на окружностях на равных угловых расстояниях друг от друга,
включая точку, имеющую нулевую угловую координату. Таким образом, каждый
мегаполис iM (1) однозначно представляется парой ,),( ii RO где iO — точка,
являющаяся центром окружности, а iR — радиус окружности; .1, Ni Пусть
начальная точка 0x совпадает с началом координат, т.е. ,0)(0,=0x а терминальное
состояние процесса перемещений (3) связано с возвратом в точку .0x
Пусть функции затрат c и f в (10) пропорциональны евклидову расстоянию,
а именно: f определяется евклидовым расстоянием, а функция c — утроенное
евклидово расстояние между соответствующими точками. Значения функций
nN AAcc ...,,,...,, 11 определяются в виде экстремумов «внутренних» незамкнутых
задач коммивояжера, связанных с посещением всех городов мегаполиса при
условии, что матрица затрат всякий раз определяется посредством евклидовых
расстояний; аргументами упомянутых функций являются при этом точка
прибытия в мегаполис и точка отправления из мегаполиса. Предполагается, что в
данном варианте ,c NN AAcc ...,,,...,, 11 зависимость от списка заданий отсутствует.
Программа написана на языке программирования С++ (использован
64-разрядный компилятор), работает под управлением 64-разрядной операционной
системы семейства Windows, начиная с Windows 7, в многопотоковом режиме
(вычислительная часть выполняется в отдельном от интерфейса пользователя потоке);
при решении задачи на плоскости имеется возможность представления траектории
движения по мегаполисам в графическом виде, увеличения отдельных участков
графика и сохранения изображения в файл графического формата bmp. Исходные
данные и результаты работы программы сохраняются в текстовом файле специального
формата. Вычислительный эксперимент проводился на компьютере с центральным
процессором Intel Core i7 объемом ОЗУ 64 Гбайт с установленной операционной
системой Windows 764 (64 разряда) и максимальной Sp1.
Из-за ограничения объема статьи в явном виде перечислим точки мегапо-
лисов и адресные пары, составляющие условия предшествования, а также элемен-
ты маршрутов и узлы трассы, ограничившись только графическим изображением
траекторий движения.
Пусть 34=N и заданы 39 адресных пар (условия предшествования). В резуль-
тате применения точного алгоритма на основе ДП в его полной версии [17]
(нахождение глобального экстремума (13) и его доставляющего ДР) получим
следующие результаты: величина совокупных затрат 78,4305=V ; время счета
9 ч. 19 мин. 43 с. График маршрута и трассы приведен на рис. 1.
В случае применения точного алгоритма на основе ДП в усеченной версии
(без построения маршрута и трассы) получаем сокращение времени счета в
1,7 раза (время поиска глобального экстремума составило 5 ч. 33 мин. 45 с.).
Рассмотрим теперь результаты работы (для упомянутого выше модельного
примера) «жадного» алгоритма, о котором шла речь в предыдущем разделе:
величина совокупных затрат ;12,6088 время счета 1 с. График маршрута и трассы
приведен на рис. 2.
Как видно из приведенной информации, проигрыш «жадного» алгоритма
по отношению к точному методу составил примерно 30 % при несоизмеримом
выигрыше во времени счета.
Рассмотрим теперь пример использования усеченной версии точного метода для
решения задачи обхода 37=N мегаполисов при условии, что заданы 66 адресных пар
52 ISSN 0572-2691
(элементы множества ),K ограничивающих порядок посещения. Пусть функции ,ic
,371,i аналогичны рассмотренным в предыдущем примере, а функция c — суть
евклидово расстояние между соответствующими плоскими векторами. В итоге
получим величину совокупных затрат (глобальный экстремум) 03,3237=V . В случае
применения «жадного» алгоритма затраты на перемещения по мегаполисам равны
.34,4053 Графическое изображение траектории движения, полученной в результате
работы «жадного» алгоритма, приведено на рис. 3.
– 100
– 100 – 80 – 60 – 40 – 20 0 20 40 60 80
– 90
– 80
– 70
– 60
0
10
20
30
40
– 50
– 40
– 30
– 20
– 10
50
60
70
Рис. 1
– 100
– 100 – 80 – 60 – 40 – 20 0 20 40 60 80
– 90
– 80
– 70
– 60
0
10
20
30
40
– 50
– 40
– 30
– 20
– 10
50
60
70
Рис. 2
Международный научно-технический журнал
«Проблемы управления и информатики», 2016, № 1 53
– 100
– 100 – 80 – 60 – 40 – 20 0 20 40 60 80
– 90
– 80
– 70
– 60
0
10
20
30
40
– 50
– 40
– 30
– 20
– 10
50
60
70
Рис. 3
В данном примере проигрыш «жадного» алгоритма по отношению к глобаль-
ному экстремуму составил примерно 20 %.
Итак, применение усеченной (без построения маршрута и трассы) версии
точного метода на основе ДП позволяет экономить память и существенно
сократить время счета (по сравнению с полной версией); полученный в итоге
глобальный экстремум весьма полезен в качестве оценки результатов работы
эвристических алгоритмов, которые, несмотря на проигрыш по результату,
имеют несравненные преимущества в виде очень малого времени счета и низкие
требования к вычислительным ресурсам компьютера (производительность
процессора и объем оперативной памяти); в ряде прикладных задач отступление
от оптимальности вполне допустимо в угоду скорости счета.
О.Г. Ченцов, О.О. Ченцов
ДО ПИТАННЯ ПРО ЗНАХОЖДЕННЯ ЗНАЧЕННЯ
МАРШРУТНОЇ ЗАДАЧІ З ОБМЕЖЕННЯМИ
Розглянуто задачу послідовного обходу мегаполісів з обмеженнями різних
типів. Вважається, що функції вартості, а також «поточні» обмеження можуть
залежати від списку завдань (можлива залежність від списку виконаних або,
навпаки, ще не виконаних завдань). Запропоновано підхід до визначення гло-
бального екстремуму (значення задачі) на основі динамічного програмування
в широкому сенсі. Завдяки такому підходу досягається економія пам’яті ком-
п’ютера, що дозволяє визначати экстремум в задачі більшої розмірності та
використовувати його для тестування евристичних алгоритмів. Для побудови
шарів функції Беллмана використовується скорочена процедура, що дозволяє
зменшити складність обчислювань (за умов передування не передбачається
побудова всього масиву значень функції Беллмана).
54 ISSN 0572-2691
A.G. Chentsov, A.A. Chentsov
ON THE PROBLEM OF OBTAINING THE VALUE
OF ROUTING PROBLEM WITH CONSTRAINTS
The problem of sequential travelling of megapolises with constraints of different
types is considered. It is supposed that cost functions and «current» constraints can
be dependent on the tasks list (it is possible that dependence on the fulfilled or
nonfulfilled tasks arises). Approach to determination of global extremum (the
problem value) on the basis of widely interpreted dynamic programming is
proposed. Under given approach, economy of computer memory is reached; this
permits to determine extremum in problem with larger dimensionality and use it for
testing of heuristic algorithms. Under construction of layers of Bellman function,
truncated procedure which enables one to decrease computing complexity is used
(under preceding conditions, construction of all array of the Bellman function
values is not provided).
1. Ченцов А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы
теории. — Москва; Ижевск : РХД, 2008. — 238 с.
2. Петунин А.А. О некоторых стратегиях формирования маршрута инструмента при
разработке управляющих программ для машин термической резки материала // Вестник
УГАТУ. Серия: Управление, вычислительная техника и информатика. — 2009. — 13,
№ 2(35). — С. 280–286.
3. Фроловский В.Д. Автоматизация проектирования управляющих программ тепловой резки
металла на оборудовании с ЧПУ // Информационные технологии в проектировании и
производстве. — 2005. — № 4. — С. 63–66.
4. Gutin G., Punnen A.P. The Traveling salesman problem and its variations — Boston; London;
Dordrecht : Kluwer Academic Publishers Group, 2002. — 830 p.
5. Беллман Р. Применение динамического программирования к задаче о коммивояжере //
Кибернетический сборник. — М. : Мир, 1964. — 9. — С. 219–228.
6. Хелд М., Карп Р.М. Применение динамического программирования к задачам
упорядочения // Там же. — М. : Мир, 1964. — 9. — С. 202–218.
7. Литл Дж., Мурти К., Суини Д., Кэрел К. Алгоритм для решения задачи о коммивояжере //
Экономика и математические методы. — 1965. — 1 (вып. 1). — С. 94–107.
8. Меламед И.И., Сергеев С.И., Сигал И.Х. Задача коммивояжера. Вопросы теории //
Автоматика и телемеханика. — 1989. — № 9. — С. 3–34.
9. Меламед И.И., Сергеев С.И., Сигал И.Х. Задача коммивояжера. Точные алгоритмы // Там
же. — 1989. — № 10. — С. 3–29.
10. Меламед И.И., Сергеев С.И., Сигал И.Х. Задача коммивояжера. Приближенные алгоритмы //
Там же. — 1989. — № 11. — С. 3–26.
11. Куратовский К., Мостовский А. Теория множеств. — М. : Мир, 1970. — 416 c.
12. Дьедонне Ж. Основы современного анализа. — М. : Мир, 1964. — 430 с.
13. Ченцов А.Г. К вопросу о маршрутизации комплексов работ // Вестник Удмуртск. ун-та.
Математика. Механика. Комп. науки. — 2013. — № 1. — С. 59–82.
14. Ченцов А.А., Ченцов А.Г., Ченцов П.А. Элементы динамического программирования в
экстремальных задачах маршрутизации // Проблемы управления. — 2013. — № 5. — С.12–21.
15. Ченцов А.Г. Задача последовательного обхода мегаполисов с условиями предшествования //
Автоматика и телемеханика. — 2014. — № 4. — С. 170–190.
16. Ченцов А.А., Ченцов А.Г., Ченцов П.А. Метод итераций в задаче маршрутизации с
внутренними потерями // Труды Института математики и механики УрО РАН. — 2009. —
15, № 4. — С. 268–287.
17. Ченцов А.Г., Ченцов А.А. Задача маршрутизации с ограничениями, зависящими от списка
заданий // Доклады Академии наук. — 2015. — 465, № 2. — C. 154–158.
Получено 02.12.2015
|