Оптимизация замкнутых маршрутов на транспортной сети
Предложен точный алгоритм ветвей и границ для решения замкнутой общей задачи коммивояжера. Среди решений с одинаковой стоимостью выбирается то, что содержит в себе наименьшее количество ребер....
Збережено в:
| Дата: | 2010 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем штучного інтелекту МОН України та НАН України
2010
|
| Назва видання: | Штучний інтелект |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/56121 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Оптимизация замкнутых маршрутов на транспортной сети / А.В. Панишев, А.Ю. Левченко, О.Б. Маций // Штучний інтелект. — 2010. — № 1. — С. 43-49. — Бібліогр.: 7 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-56121 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-561212015-08-05T21:03:27Z Оптимизация замкнутых маршрутов на транспортной сети Панишев, А.В. Левченко, А.Ю. Маций, О.Б. Системы и методы искусственного интеллекта Предложен точный алгоритм ветвей и границ для решения замкнутой общей задачи коммивояжера. Среди решений с одинаковой стоимостью выбирается то, что содержит в себе наименьшее количество ребер. Запропоновано точний алгоритм гілок та меж для розв’язку замкненої загальної задачі комівояжера. Серед розв’язків з однаковою вартістю обирається той, що містить найменшу кількість ребер. The article offers exact branch and bounds algorithm of closed common Commercial Traveler Task solution. This algorithm selects the solution, which contains minimal number of edges between equal cost solutions. 2010 Article Оптимизация замкнутых маршрутов на транспортной сети / А.В. Панишев, А.Ю. Левченко, О.Б. Маций // Штучний інтелект. — 2010. — № 1. — С. 43-49. — Бібліогр.: 7 назв. — рос. 1561-5359 http://dspace.nbuv.gov.ua/handle/123456789/56121 681.3 ru Штучний інтелект Інститут проблем штучного інтелекту МОН України та НАН України |
| 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 |
2010 |
| topic_facet |
Системы и методы искусственного интеллекта |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/56121 |
| citation_txt |
Оптимизация замкнутых маршрутов на транспортной сети / А.В. Панишев, А.Ю. Левченко, О.Б. Маций // Штучний інтелект. — 2010. — № 1. — С. 43-49. — Бібліогр.: 7 назв. — рос. |
| series |
Штучний інтелект |
| work_keys_str_mv |
AT paniševav optimizaciâzamknutyhmaršrutovnatransportnojseti AT levčenkoaû optimizaciâzamknutyhmaršrutovnatransportnojseti AT macijob optimizaciâzamknutyhmaršrutovnatransportnojseti |
| first_indexed |
2025-07-05T07:22:09Z |
| last_indexed |
2025-07-05T07:22:09Z |
| _version_ |
1836790715217084416 |
| fulltext |
«Штучний інтелект» 1’2010 43
1П
УДК 681.3
А.В. Панишев1, А.Ю. Левченко1, О.Б. Маций2
1 Житомирский государственный технологический университет, Украина
2 Харьковский национальный автомобильно-дорожный университет, Украина
dear_anton@yahoo.com, irinagar@rambler.ru
Оптимизация замкнутых маршрутов
на транспортной сети
Предложен точный алгоритм ветвей и границ для решения замкнутой общей задачи коммивояжера.
Среди решений с одинаковой стоимостью выбирается то, что содержит в себе наименьшее количество
ребер.
Постановка задачи
В статье рассматривается задача нахождения замкнутого маршрута минимальной
стоимости, который проходит по всем пунктам транспортной сети.
Транспортная сеть представлена связным взвешенным графом ( ),H V U= , где
V – множество вершин, U – множество ребер. Пункту i сети соответствует верши-
на i V∈ графа H , V n= , а отрезку дорожного полотна, связывающего два соседних
пункта i и j , отвечает ребро { },i j U∈ . Каждому ребру { },i j приписан вес 0ijd R+∈ ,
равный стоимости проезда или расстоянию между пунктами i и j ; 0R+ – множество
действительных неотрицательных чисел. Предполагается, что ij jid d= .
Требуется построить замкнутый маршрут, проходящий по всем вершинам графа
H и имеющий минимальную сумму весов ребер (минимальную стоимость).
Сформулированная задача получила название общей задачи коммивояжера (ОЗК) [1],
а ее решение – маршрутом коммивояжера.
Маршрутом в графе H называется чередующаяся последовательность вершин
и ребер, а цепью – маршрут, все ребра которого различны. Простая цепь – это марш-
рут, состоящий из различных вершин. Замкнутый маршрут называется циклом, а цикл,
в котором все вершины различны, – простым. Простой цикл, проходящий по всем
вершинам графа H точно один раз, называется гамильтоновым циклом, или обходом.
ОЗК, в которой требуется найти обход с минимальной суммой весов ребер, известна
как гамильтонова задача коммивояжера (ГЗК) [1], [2]. Не всякий граф содержит га-
мильтонов цикл, то есть не каждый граф гамильтонов. Следовательно, ГЗК в отличие
от ОЗК не всегда имеет решение.
Исследованию ОЗК посвящено ограниченное число работ, в которых в основном
обсуждаются подходы к построению алгоритмов ее решения. Вместе с тем проблема
нахождения оптимальных гамильтоновых циклов в полном графе всесторонне изучена.
В данной статье развиваются результаты из [1], [2], ориентированные на сведение ОЗК
к известной метрической задаче коммивояжера (ЗК).
Панишев А.В., Левченко А.Ю., Маций О.Б.
«Искусственный интеллект» 1’2010 44
1П
Обоснование и описание алгоритма
Известно, что ГЗК NP – трудна [3]. Этот же статус имеет ее частный случай, ко-
торый состоит в определении гамильтоновости графа. Поэтому найти решение ГЗК
или установить, что ее граф негамильтонов, можно только методами с экспоненциальной
трудоемкостью вычислений. Так как множество циклов, проходящих по всем верши-
нам связного графа, не пусто, то, очевидно, ОЗК поддается приближенному решению
за полиномиальное время. Ниже изложен точный алгоритм решения ОЗК, построен-
ный на ее сведении к метрической ЗК, которая состоит в нахождении гамильтонова
цикла минимальной стоимости в полном графе ( ),H V Eα = с весами ребер { },i j , рав-
ными кратчайшим расстояниям между вершинами i и j графа ( ),H V U= , , 1,i j n= .
Каждому ребру { },i j U∈ графа ( ),H V U= поставим в соответствие множество
ijA простых цепей, в которых вершины i и j являются концевыми. Множество ijA
содержит единственную цепь, состоящую из ребра { },i j , если в графе H нет других
простых цепей, соединяющих вершины i и j . Выберем в ijA цепь ijα , ребра которой
в совокупности имеют наименьший вес ( )ijD α . Назовем ее кратчайшей цепью между
вершинами i и j . В зависимости от значений ijd получим случай а), когда для всех
ребер { },i j U∈ выполняется неравенство
( )ij ijd D α≤ , (1)
и случай б), когда оно нарушается хотя бы для одного ребра. Неравенство (1) харате-
ризует весовые соотношения ребер в графе H подобно неравенству треугольника
ik ij jkd d d≤ + , (2)
которое должно выполняться для всех троек вершин , ,i j k V∈ , i j≠ , j k≠ , полного
взвешенного графа ( ),nH V E= в метрической ЗК [1].
Найдем любым известным методом, например, алгоритмом Флойда – Уоршалла [1],
кратчайшие цепи ijα между всеми вершинами графа H и определим их веса ( )ijD α ,
, 1,i j n= [1].
Матрица ( )ij n
D α
удовлетворяет неравенству (2) и вместе с матрицей ij n
α за-
дает полный граф ( ),H V Eα = , где каждое ребро { },i j отвечает цепи ijα в H весом
( )ijD α (рис. 1).
а) б)
Рисунок 1 – а) Граф H ; б) полный граф Hα
4
1 6
2 3
3
2 5
1
5
4
4
5 1
2
3
3
3 5
5
4
1
6
7
10
2
Оптимизация замкнутых маршрутов на транспортной сети
«Штучний інтелект» 1’2010 45
1П
Пусть граф ( ),H V U= гамильтонов, τ , Τ – оптимальные решения соответст-
венно ГЗК и ОЗК, построенные в H , ( )D τ и ( )C Τ – стоимости построенных реше-
ний. Найдем обход σ минимальной стоимости в полном графе Hα .
Утверждение 1. Если для всех ребер { },i j U∈ гамильтонова графа ( ),H V U= вы-
полняется неравенство (1), то τΤ = , ( ) ( )C D τΤ = .
Доказательство. Решение ГЗК τ содержит n ребер множества U . В случае а)
ребро { },i j полного графа Hα имеет вес ( )ij ijD dα = , если { },i j U∈ , и ( )ij ijD dα ≥
иначе. Отсюда следует, что в Hα точное решение ЗК σ совпадает с τ , а его стоимость
не превышает стоимость произвольного маршрута, который содержит n и больше ре-
бер, включая Τ .
Утверждение 2. Если хотя бы для одного ребра { },i j гамильтонова графа
( ),H V U= неравенство (1) не выполняется, то ( ) ( )C D σΤ ≤ .
Доказательство. В случае б) в полном графе Hα найдется по крайней мере од-
но ребро { },i j , которое в H имеет вес ( )ij ijd D α> . Если гамильтонов цикл σ графа
Hα проходит по ребру { },i j , то его стоимость больше стоимости соответствующего
замкнутого маршрута в H , содержащего вместо ребра { },i j U∈ цепь ijα . Если цикл
σ не включает ребер, которые нарушают неравенство (1), то он совпадает с решени-
ем ГЗК.
Допустим, что граф ( ),H V U= не гамильтонов. Тогда в любом случае а) или б)
стоимость оптимального решения ЗК σ для полного графа ( ),H V Eα = равна стоимос-
ти решения ОЗК Τ для графа H . Поэтому маршрут Τ можно найти в результате по-
строения в графе Hα гамильтонова цикла σ и замены в нем каждого ребра { },i j E∈
на цепь ijα из ребер множества U .
Приведенные рассуждения позволяют описать алгоритм решения ОЗК.
S0. ( ),H V U= – связный взвешенный граф с множеством вершин V , V n= , и
множеством ребер U , ij n
d – матрица весов ребер графа H , где 0ijd R+∈ , если { },i j U∈ ,
и ijd = ∞ иначе, , 1,i j n= , 0R+ – множество действительных неотрицательных чисел.
S1. Построить матрицу ij n
α кратчайших цепей между всеми парами вершин
графа H и матрицу ( )ij n
D α
, в которой элемент ( ),i j равен весу ( )ijD α цепи ijα ;
матрицы ij n
α и ( )ij n
D α
определяют полный взвешенный граф ( ),H V Eα = , где каж-
дое ребро { },i j заменяет цепь ijα в графе H .
S2. В графе Hα найти обход минимальной стоимости σ любым известным ме-
тодом решения метрической ЗК.
S3. Построить оптимальное решение ОЗК Τ в результате замены каждого реб-
ра { },i j гамильтонова цикла σ на цепь ijα графа H .
Панишев А.В., Левченко А.Ю., Маций О.Б.
«Искусственный интеллект» 1’2010 46
1П
Минимизация длины маршрута коммивояжера
Количество ребер в маршруте называется его длиной [4]. В общем случае связ-
ный граф H содержит несколько замкнутых маршрутов коммивояжера минимальной
стоимости, включающих разное число ребер. Представленный алгоритм строит какой-
либо из них. Потребуем, чтобы длина маршрута коммивояжера была наименьшей.
Для выполнения этого требования достаточно применить на шаге S2 классичес-
кий алгоритм решения ЗК (метод Литтла) с дополнениями к правилу выбора вершины
ветвления.
В методе Литтла ветвление выполняется после приведения исходной матрицы
стоимостей и представляет собой пошаговый процесс разбиения множества решений
ЗК на непересекающиеся множества, изображаемые в бинарном дереве перебора в ви-
де вершин [5]. Корню дерева решений соответствует вершина ∅ , которая обознача-
ет множество всех допустимых решений ЗК. Она является начальной вершиной вет-
вления.
Пусть ( )ijD α – значение элемента ( ),i j приведенной матрицы стоимостей, ,i j =
1,n= . Каждый элемент матрицы представлен дугой в ориентированном мультиграфе
Gα , где любые две вершины i и j соединены парой дуг ( ),i j и ( ),j i .
Ветвление начинается с выбора дуги ( ),k l мультиграфа Gα , которая, исходя из
значений элементов приведенной матрицы, оценивается как наиболее подходящая для
включения в искомое решение. Дуга ( ),k l разбивает множество всех решений ∅ на
два подмножества. Решения одного подмножества включают дугу ( ),k l , а решения
другого не содержат ее. Корень дерева ∅ порождает две текущие активные вершины.
Обозначим их соответственно ( )( ),k l o и ( )( ),k l o . Для подмножеств ( )( ),k l o и ( )( ),k l o
вычисляются нижние границы стоимостей решений ЗК ( )( ),k lϕ o и ( )( ),k lϕ o , в каж-
дую из которых входит своя константа приведения [6]. Вершина с наименьшей ниж-
ней границей выбирается в качестве вершины ветвления.
По матрице, соответствующей выбранной вершине, определяется следующая ду-
га ( ),r s , инициирующая ветвление. Если ( )( ) ( )( ), ,k l k lϕ ϕ≤o o , то множество ( )( ),k l o
разбивается на подмножества ( ) ( )( ), , ,k l r s o и ( )( )( ), ,k l r s o , иначе множество ( )( ),k l o
разбивается на подмножества ( ) ( )( ), , ,k l r s o и ( )( )( ), ,k l r s o . Вершина ветвления по-
рождает пару текущих активных вершин, затем формируются соответствующие им
приведенные матрицы, по которым находятся нижние границы для каждого из двух
полученных подмножеств разбиения. Очередная вершина ветвления определяется сре-
ди всех текущих активных вершин, представленных висячими вершинами в дереве
перебора. Путь из корня в висячую вершину содержит часть допустимого решения ЗК,
состоящую из включенных в процессе ветвления дуг. Алгоритм Литтла завершает
работу, когда следующая вершина ветвления включает все дуги обхода в графе Gα .
Оптимизация замкнутых маршрутов на транспортной сети
«Штучний інтелект» 1’2010 47
1П
Если на каком-либо шаге ветвления несколько активных текущих вершин полу-
чают наименьшее значение для своих нижних границ, то метод Литтла не гарантирует
решение ОЗК, минимальной длины. Поэтому, чтобы найти такое решение, в процес-
се построения дерева перебора для каждой его вершины вместе с нижней границей
стоимости определяется параметр, оценивающий длину частичного решения.
В строящемся дереве перебора путь из корня в висячую вершину содержит ду-
ги, включенные и не включенные в частичное решение. Обозначим ( ){ },j j jp qP v v=
множество дуг, включенных в частичное решение в результате построения пути из
корня дерева в висячую вершину j . Каждая дуга ( ),j jp qv v множества jP в мультигра-
фах Gα является дугой ( ),p qv v , которой в графе H соответствует кратчайшая цепь
pqα , соединяющая вершины p и q и содержащая ( ),l p q ребер. Тогда частичное ре-
шение, полученное для вершины j , включает
( )
( ),
j pq
v v Pj j jp q
l l α
∈
= ∑ (3)
ребер графа H . В методе Литтла для каждой вершины j , порожденной на шаге вет-
вления, к нижней границе стоимости jϕ добавим оценку
j j jL l P= − . (4)
Из двух и более активных текущих вершин с наименьшим значением нижних гра-
ниц, в качестве вершины ветвления выбирается та, для которой оценка (4) минимальна.
Пусть в связном графе ( ),H V U= Τ – точное решение ОЗК с наименьшим чис-
лом ребер Τ . Тогда если nΤ = , то из утверждений 1 и 2 следует, что граф H – га-
мильтонов. Если nΤ > , то граф H либо не гамильтонов, либо такой гамильтонов граф,
в котором, по крайней мере, для одного ребра неравенство (1) не выполняется. Дру-
гими словами, алгоритм решения ОЗК Τ минимальной длины является алгоритмом
поиска решения ГЗК для графа H в случае а). Для графа H в случае б) поиск реше-
ния ГЗК выполняется алгоритмом, предложенным в [7].
Пример
Найдем маршрут коммивояжера, содержащий минимальное число ребер для гра-
фа, изображенного на рис. 1 а). После выполнения шагов S0 и S1 алгоритма точного
решения СЗК получим матрицы:
1 2 3 4 5
1 ∞ ∞ 4 ∞ 1
2 ∞ ∞ ∞ 3 2
5ijd =
3 4 ∞ ∞ ∞ 5
4 ∞ 3 ∞ ∞ 6
5 1 2 5 6 ∞
,
1 2 3 4 5
1 ∞ 3 4 6 1
2 3 ∞ 7 3 2( )
5ijD α =
3 4 7 ∞ 10 5
4 6 3 10 ∞ 5
5 1 2 5 5 ∞
,
Панишев А.В., Левченко А.Ю., Маций О.Б.
«Искусственный интеллект» 1’2010 48
1П
1 2 3 4 5
1 0 (1, 5, 2) (1, 3) (1, 5, 2, 4) (1, 5)
2 (2, 5, 1) 0 (2, 5, 3) (2, 4) (2, 5)
5ijα =
3 (3, 1) (3, 5, 2) 0 (3, 5, 2, 4) (3, 5)
4 (4, 2, 5, 1) (4, 2) (4, 2, 5, 3) 0 (4, 2, 5)
5 (5, 1) (5, 2) (5, 3) (5, 2, 4) 0
,
1 2 3 4 5
1 0 2 1 3 1
2 2 0 2 1 1 ( )
5ijl α =
3 1 2 0 3 1
4 3 1 3 0 2
5 1 1 1 2 0
.
На шаге S2 построим обход минимальной стоимости для полного графа Hα , пред-
ставленного на рис. 1 б). Построение выполним модификацией метода Литтла, мини-
мизирующей число ребер в решении ОЗК Τ . На рис. 2 представлено дерево перебора,
по которому находится обход минимальной стоимости в графе Hα и маршрут ком-
мивояжера минимальной длины в графе H .
Рисунок 2 – Дерево поиска модифицированного алгоритма Литтла
( )4,1
21,0
9
( )1,4( )1, 4
20, 0
19
20, 2
34
∞
33
( )2,4 ( )2,4
( )1,3 ( )1,3
( )3,5
( )4, 2 ( )4,2
( )1,3
( )4,1 ( )1,5( )1,5
Ø
18, 0
1
17,0
2
18, 0
4
18, 0 10
19, 0
6
19, 0
11
20, 2
14
∞
13
( )1,5
18, 0
3
20, 0
7 ( )2,5
( )1,3
19, 0
12
( )2,5
20, 0
18
( )3,4( )3, 4
20, 2
28
∞
27
20, 0
17
( )1,5
( )3,1 ( )3,1
19, 0
8
20, 0
16
22, 0
15
( )4,3 ( )4,3
20, 2
26
∞
25
( )2,3
( )3,1 ( )3,1
20, 0
20
22, 0
31
20, 0
32
( )2,3
∞
35
20, 1
36
20, 2
37
( )5, 4
( )1, 2 ( )1,2
20, 1
24
∞
23
22, 1
40
20, 2
41
( )4,5( )4,5
( )2,1( )2,1
20, 1
30
∞
29
∞
42
( )5, 4
20, 2
44
20, 1
43
( )3,5( )3,5
( )3,2
( )3,5
( )3, 2
20, 0
5
20, 1
22
∞
21
20, 2
38
20, 2
39
( )4,5 ( )4,5
15, 0
Оптимизация замкнутых маршрутов на транспортной сети
«Штучний інтелект» 1’2010 49
1П
Каждой вершине дерева приписано значение нижней границы стоимости частич-
ного решения и число, вычисляемое по формулам (3) и (4). Граф H содержит несколь-
ко оптимальных маршрутов коммивояжера равной длины. Например, ОЗК находится
из пути от корня ∅ дерева до вершины 37. Этот путь включает дуги (4, 2), (1,5), (3, 1),
(2,3), (5,4), образуя в полном графе Hα цикл (1, 5, 4, 2, 3, 1) стоимостью 20.
На шаге S3 выполним замену ребер {5, 4} и {2, 3} соответственно на цепи
54α = (5, 2, 4) и 23α = (2, 5, 3). В результате получим решение ОЗК Τ = (1, 5, 2, 4, 2, 5,
3, 1), состоящее из 7 ребер. Другого решения стоимостью 20 и с меньшим числом ре-
бер в графе H нет.
Заключение
В данной статье нашли развитие изложенные в [1], [2] идеи, которые лежат в ос-
нове метода построения замкнутого маршрута минимальной стоимости, проходящего
по всем пунктам транспортной сети. Задача построения такого маршрута называется
общей задачей коммивояжера (ОЗК). Моделью транспортной сети является связный
неполный граф с произвольно заданными неотрицательными весами (стоимостями)
ребер. Показано, что если в графе содержится гамильтонов цикл, т.е. простой цикл, вклю-
чающий каждую вершину точно один раз, то его стоимость не меньше стоимости реше-
ния ОЗК.
Предложен точный алгоритм решения ОЗК, выполняемый в две стадии. На пер-
вой стадии граф транспортной сети преобразуется в полный граф с весами ребер, огра-
ниченными неравенствами треугольника. Каждому ребру { },i j полного графа ставится
в соответствие цепь минимальной стоимости, соединяющая вершины i и j . На второй
стадии применяется классический алгоритм ветвей и границ для решения метрической
симметричной задачи коммивояжера, дополненный способом минимизации числа ребер
в искомом маршруте.
Литература
1. Майника Э. Алгоритмы оптимизации на сетях и графах / Майника Э. – М. : Мир, 1981. – 323 с.
2. Бондаренко М.Ф. Компьютерная дискретная математика / Бондаренко М.Ф., Белоус Н.В., Руткас А.Г. –
Харьков : Компания СМИТ, 2004. – 476 с.
3. Гэри М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. – М. : Мир,
1982. – 416 с.
4. Харари Ф. Теория графов / Харари Ф. – М. : Мир, 1973. – 300 с.
5. Теория расписаний и вычислительные машины / [под ред. Э.Г. Кофмана]. – М. : Наука, 1984. – 336 с.
6. Панишев А.В. Модели и методы оптимизации в проблеме коммивояжера / А.В. Панишев, Д.Д. Пле-
чистый. – Житомир : ЖГТУ, 2006. – 300 с.
7. Garashenko Irina. Method of Finding Hamilton Routes in Transport Network / I. Garashenko, A. Panishev //
Artificial Intelligence and Decision Making. – ITHEA, Sofia, 2008. – № 7. – P. 43-48.
А.В. Панішев, А.Ю. Левченко, О.Б. Маций
Оптимізація замкнених маршрутів на транспортній мережі
Запропоновано точний алгоритм гілок та меж для розв’язку замкненої загальної задачі комівояжера.
Серед розв’язків з однаковою вартістю обирається той, що містить найменшу кількість ребер.
A.V. Panishev, A.Yu. Levchenko, O.B. Matziy
Transport Network’s Closed Walks Optimization
The article offers exact branch and bounds algorithm of closed common Commercial Traveler Task solution.
This algorithm selects the solution, which contains minimal number of edges between equal cost solutions.
Статья поступила в редакцию 25.01.2010.
|