Развитие метода ветвей и границ в задаче поиска оптимального кольцевого маршрута
Побудовано математичну модель прикладної задачі оптимізації замкнених маршрутів — кільцевої задачі про сільського листоношу. Запропоновано двоетапний метод типу гілок та меж, який знаходить розв’язок або встановлює факт нерозв’язності задачі. Перший етап методу включає перевірку достатніх умов нероз...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2013 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/86276 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Развитие метода ветвей и границ в задаче поиска оптимального кольцевого маршрута / А.О. Овезгельдыев, А.В. Морозов // Кибернетика и системный анализ. — 2013. — Т. 49, № 5. — С. 112-123. — Бібліогр.: 4 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-86276 |
|---|---|
| record_format |
dspace |
| spelling |
Овезгельдыев, А.О. Морозов, А.В. 2015-09-11T20:10:42Z 2015-09-11T20:10:42Z 2013 Развитие метода ветвей и границ в задаче поиска оптимального кольцевого маршрута / А.О. Овезгельдыев, А.В. Морозов // Кибернетика и системный анализ. — 2013. — Т. 49, № 5. — С. 112-123. — Бібліогр.: 4 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/86276 519.161 Побудовано математичну модель прикладної задачі оптимізації замкнених маршрутів — кільцевої задачі про сільського листоношу. Запропоновано двоетапний метод типу гілок та меж, який знаходить розв’язок або встановлює факт нерозв’язності задачі. Перший етап методу включає перевірку достатніх умов нерозв’язності і процедуру вершинно-реберного перетворення. Це дає можливість скоротити час пошуку розв’язку на другому етапі методу за допомогою запропонованої модифікації методу Літтла. У ній вперше застосовано спосіб розбиття множини розв’язків на підмножини, що не перетинаються, за допомогою трьох правил розгалуження і обчисленням відповідних нижніх оцінок вартості оптимального розв’язку. Запропонований метод коректно виконує пошук оптимального розв’язку гамільтонової задачі про сільського листоношу, загальної і гамільтонової задачі комівояжера. A mathematical model of the applied problem of optimization of closed routes, i.e., the rural postman problem, is constructed. A two-stage method of the type of the branch-and-bound one is proposed that finds a solution or establishes the fact of the unsolvability of the problem. The first stage of the method includes the test of sufficient unsolvability conditions and a vertex-edge transformation procedure. This makes it possible to decrease the time of searching for a solution at the second stage of the method with the help of a proposed modification of the Little method. This procedure uses (for the first time) a partition of a solution set into disjoint subsets with the help of three rules of branching and computation of corresponding lower assessed values of an optimal solution. The proposed method correctly searches for an optimal solution of the Hamiltonian rural postman problem and general and Hamiltonian traveling salesman problems. Авторы выражают благодарность профессору Анатолию Васильевичу Панишеву за ценные замечания и помощь в работе. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Развитие метода ветвей и границ в задаче поиска оптимального кольцевого маршрута Розвиток методу гілок та меж у задачі пошуку оптимального кільцевого маршруту Developing the branch-and-bound method in the problem of searching for an optimal circular route (the Cyclic Rural Postman Problem) Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Развитие метода ветвей и границ в задаче поиска оптимального кольцевого маршрута |
| spellingShingle |
Развитие метода ветвей и границ в задаче поиска оптимального кольцевого маршрута Овезгельдыев, А.О. Морозов, А.В. Системный анализ |
| title_short |
Развитие метода ветвей и границ в задаче поиска оптимального кольцевого маршрута |
| title_full |
Развитие метода ветвей и границ в задаче поиска оптимального кольцевого маршрута |
| title_fullStr |
Развитие метода ветвей и границ в задаче поиска оптимального кольцевого маршрута |
| title_full_unstemmed |
Развитие метода ветвей и границ в задаче поиска оптимального кольцевого маршрута |
| title_sort |
развитие метода ветвей и границ в задаче поиска оптимального кольцевого маршрута |
| author |
Овезгельдыев, А.О. Морозов, А.В. |
| author_facet |
Овезгельдыев, А.О. Морозов, А.В. |
| topic |
Системный анализ |
| topic_facet |
Системный анализ |
| publishDate |
2013 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Розвиток методу гілок та меж у задачі пошуку оптимального кільцевого маршруту Developing the branch-and-bound method in the problem of searching for an optimal circular route (the Cyclic Rural Postman Problem) |
| description |
Побудовано математичну модель прикладної задачі оптимізації замкнених маршрутів — кільцевої задачі про сільського листоношу. Запропоновано двоетапний метод типу гілок та меж, який знаходить розв’язок або встановлює факт нерозв’язності задачі. Перший етап методу включає перевірку достатніх умов нерозв’язності і процедуру вершинно-реберного перетворення. Це дає можливість скоротити час пошуку розв’язку на другому етапі методу за допомогою запропонованої модифікації методу Літтла. У ній вперше застосовано спосіб розбиття множини розв’язків на підмножини, що не перетинаються, за допомогою трьох правил розгалуження і обчисленням відповідних нижніх оцінок вартості оптимального розв’язку. Запропонований метод коректно виконує пошук оптимального розв’язку гамільтонової задачі про сільського листоношу, загальної і гамільтонової задачі комівояжера.
A mathematical model of the applied problem of optimization of closed routes, i.e., the rural postman problem, is constructed. A two-stage method of the type of the branch-and-bound one is proposed that finds a solution or establishes the fact of the unsolvability of the problem. The first stage of the method includes the test of sufficient unsolvability conditions and a vertex-edge transformation procedure. This makes it possible to decrease the time of searching for a solution at the second stage of the method with the help of a proposed modification of the Little method. This procedure uses (for the first time) a partition of a solution set into disjoint subsets with the help of three rules of branching and computation of corresponding lower assessed values of an optimal solution. The proposed method correctly searches for an optimal solution of the Hamiltonian rural postman problem and general and Hamiltonian traveling salesman problems.
|
| issn |
0023-1274 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/86276 |
| citation_txt |
Развитие метода ветвей и границ в задаче поиска оптимального кольцевого маршрута / А.О. Овезгельдыев, А.В. Морозов // Кибернетика и системный анализ. — 2013. — Т. 49, № 5. — С. 112-123. — Бібліогр.: 4 назв. — рос. |
| work_keys_str_mv |
AT ovezgelʹdyevao razvitiemetodavetveiigranicvzadačepoiskaoptimalʹnogokolʹcevogomaršruta AT morozovav razvitiemetodavetveiigranicvzadačepoiskaoptimalʹnogokolʹcevogomaršruta AT ovezgelʹdyevao rozvitokmetodugíloktamežuzadačípošukuoptimalʹnogokílʹcevogomaršrutu AT morozovav rozvitokmetodugíloktamežuzadačípošukuoptimalʹnogokílʹcevogomaršrutu AT ovezgelʹdyevao developingthebranchandboundmethodintheproblemofsearchingforanoptimalcircularroutethecyclicruralpostmanproblem AT morozovav developingthebranchandboundmethodintheproblemofsearchingforanoptimalcircularroutethecyclicruralpostmanproblem |
| first_indexed |
2025-12-02T07:26:53Z |
| last_indexed |
2025-12-02T07:26:53Z |
| _version_ |
1850861826418409472 |