Везде
Modification of the label method for problems of multicriterial optimization
Table of contents
Annotation Estimate Publication content
References Comments
Share
QR
Metrics
Modification of the label method for problems of multicriterial optimization
Annotation
PII
S042473880008559-3-1
DOI
10.31857/S042473880008559-3
Publication type
Article
Status
Published
Authors
Aleksey Zaslavsky 
Occupation: Senior Research Scholar
Affiliation: Central Economics and Mathematics Institute, Russian Academy of Sciences
Address: Moscow, Russian Federation
Alina Belova
Occupation: undergraduate student
Affiliation: Moscow Power Engineering Institute
Address: Russian Federation
Edition
Volume 56 Issue 1
Pages
95-99
Abstract

The label method (Deikstra method) allows to find the shortest way between two vertices of a graph with given lengths of edges.  A modification of the method is proposed for the case when several characteristics are given for each edge, for example the time and the cost of the way. In multicriterial optimization problems different decision makers can choose different solutions, and as usually the preferences of decision maker are not formalized. So  it is necessary to construct a sufficiently large set of Pareto-optimal ways. Such problems can be solved by interacive procedures formalizing the decision maker’s preferences and forming Pareto-optimal solutions. One approach to constructing of such procedure is proposed in the paper. This approach is based on the search of the way having the minimal value of one of the given criteria and satisfactory values of the remaining chiteria. If the obtained way is not satisfactory for the decision maker he formulates new conditions for the values of the criteria. The effecivity of the proposed procedure will be examined by calculating experiments.

Keywords
graph, label method, multicriterial optimization, Pareto-optimality
Received
05.03.2020
Date of publication
20.03.2020
Number of purchasers
41
Views
1865
Readers community rating
0.0 (0 votes)
Cite   Download pdf
1 Метод пометок (МП) (Ху, 1974, гл.10) позволяет решить следующую задачу. Дан ориентированный граф, каждому ребру которого приписано положительное число (длина ребра). Требуется найти кратчайший путь от вершины S до вершины F. В алгоритме метода вершинам графа последовательно, начиная с вершины S, присваиваются пометки, показывающие длину кратчайшего из построенных на данный момент путей, ведущих из S в данную вершину. Пометки могут быть двух видов: постоянные и временные. Если вершина получает постоянную пометку, значит, построенный путь является кратчайшим среди всех возможных путей в эту вершину. Алгоритм заканчивает работу, когда постоянную пометку получает вершина F.
2 Приведем формальное описание алгоритма.
3 Шаг 0. Присвоим вершине S постоянную пометку, равную нулю, а остальным вершинам временные пометки, равные бесконечности.
4 Шаг 1. Пусть V— последняя вершина, получившая постоянную пометку D. Для каждой вершины i, в которую ведет ребро из V, вычислим величину D+di, где di — длина ребра, между V и i. Если вычисленная величина меньше временной пометки вершины i, заменим на нее эту пометку.
5 Шаг 2. Среди всех временных пометок найдем наименьшую и сделаем ее постоянной. Если соответствующая вершина совпадает с F, построим обратным ходом искомый кратчайший путь (для каждой пометки запоминается, из какой вершины она получена), иначе вернемся к шагу 1.
6 Пусть теперь каждое ребро графа характеризуется не одной, а несколькими величинами, например временем пути и его стоимостью. В этом случае невозможно однозначно указать наилучший путь из S в F, поскольку у разных лиц, принимающих решения (ЛПР), могут быть разные представления о сравнительной важности критериев. На этот момент можно лишь требовать, чтобы найденный путь был оптимальным по Парето, т.е. не существовало пути, лучшего по всем критериям (Подиновский, Ногин, 1982, гл.1). Однако построить все множество оптимальных по Парето путей не представляется возможным, поскольку оно может оказаться очень большим. Поэтому нужно поставить задачу построения достаточно представительного множества Парето-оптимальных путей, из которого ЛПР сможет выбрать устраивающий его путь. Строить такое множество целесообразно с помощью интерактивной процедуры, постепенно уточняя требования ЛПР. Приводимый ниже алгоритм может стать основой для такой процедуры.
7 Опишем предложенный алгоритм.
8 Предположим для простоты, что каждое ребро графа характеризуется двумя величинами — временем t и стоимостью c. Пусть ЛПР задает ограничение для одного из критериев, например для стоимости. Будем искать минимальный по времени путь, стоимость C которого не превосходит заданного ЛПР значения C0.
9 В отличие от классического алгоритма МП вершина графа может получить не одну, а несколько пометок (T1,C1),…,(Tk,Ck), где T1Ck. Кроме того, пометки могут не только добавляться, но и удаляться.
10 Приведем формальное описание алгоритма.
11 Шаг 0. Присвоим вершине S постоянную пометку (0,0), а остальным вершинам временные бесконечные пометки.
12 Шаг 1. Пусть V— последняя вершина, получившая постоянную пометку (T,C). Для каждой вершины i, в которую ведет ребро из V, вычислим величины T’i=T+ti, Ci' =C+ci, где ti, ci — время и стоимость, соответствующие ребру V – i.
13 Шаг 2. Если все >C0, удаляем пометку (T,C) и переходим к шагу 4.
14 Шаг 3. Сравниваем вектор (,) со всеми пометками (Tj,Cj), присвоенными вершине i. Если для некоторых jTjи Cj ≤ , то новая пометка не записывается. В противном случае записываем новую пометку и удаляем все пометки (Tj,Cj) с Tjи Cj.
15 Шаг 4. Если не существует ни одной временной пометки с C ≤ C0, то алгоритм заканчивает работу (т.е. не существует пути, удовлетворяющего заданному ограничению по стоимости). В противном случае находим пометку с наименьшим T и делаем ее постоянной.
16 Шаг 5. Если вершина, получившая постоянную пометку, совпадает с F, строим обратным ходом искомый путь. Иначе возвращаемся к шагу 1.
17 Очевидно, что построенный путь является Парето-оптимальным. Если он не устраивает ЛПР, тот задает новые ограничения и процедура повторяется. Аналогично, при числе критериев, большем двух, ЛПР выбирает основной критерий, который минимизируется при заданных ЛПР ограничениях на значения остальных критериев.
18 Пример. Рассмотрим работу алгоритма на примере графа, приведенного на рис. 1. Ребра ориентированы от вершин с меньшими номерами к большим. Требуется построить путь от вершин 0 к вершине 9, удовлетворяющий условию C ≤ 13. Присвоим вершине 0 постоянную пометку (0,0), а вершинам 1, 2, 3 временные пометки (2,3), (1,5), (4,1) соответственно. Пометку (1, 5) вершины 2 сделаем постоянной (рис. 2).
19
Рис. 1 Рис. 2
20 Присвоим вершинам 4 и 5 временные пометки (1+2, 5+1)=(3,6) и (1+3, 5+1)=(4,6) соответственно.
21 Пометку (2,3) вершины 1 сделаем постоянной (рис. 3). Присвоим вершине 4 пометку (5, 5).
22 Пометку (3, 6) вершины 4 сделаем постоянной (рис. 4). Присвоим вершинам 7 и 8 временные пометки (7, 8) и (8, 8) соответственно.
23
Рис. 3 Рис. 4
24 Пометку (4, 1) вершины 3 сделаем постоянной (рис. 5). Присвоим вершинам 5 и 6 временные пометки (6, 3) и (7, 4) соответственно.
25 Пометку (4, 6) вершины 5 сделаем постоянной (рис. 6). Присвоим временную пометку (5, 11) вершине 8.
26
Рис. 5 Рис. 6
27 Пометку (5, 5) вершины 4 сделаем постоянной (рис. 7). Присвоим вершинам 7 и 8 временные пометки (9, 7) и (10, 7) соответственно.
28 Пометку (5, 11) вершины 8 сделаем постоянной (рис. 8). Удалим пометку (5, 11) вершины 8, поскольку из нее нельзя образовать пометки с C ≤ 13.
29
Рис. 7 Рис. 8
Пометку (6, 3) вершины 5 сделаем постоянной. Присвоим временную пометку (7, 8) вершине 8, удалим пометку (8, 8).
30 Пометку (7, 4) вершины 6 сделаем постоянной (рис. 9). Присвоим временные пометки (9, 6) и (11, 9) вершинам 8 и 9 соответственно. Удалим пометку (10, 7) вершины 8.
31 Сделаем пометку (7, 8) вершины 8 постоянной (рис. 10). Присвоим временную пометку (9, 13) вершине 9.
32
Рис. 9 Рис. 10
33 Сделаем пометку (7, 8) вершины 7 постоянной (рис. 11). Пометка (11, 9) вершине 9 не присваивается, поскольку есть такая же пометка. Сделаем пометку (9, 6) вершины 8 постоянной.
34 Пометка (11, 11) вершине 9 не присваивается, поскольку есть лучшая пометка (9, 9). Сделаем пометку (9, 7) вершины 7 постоянной. Присвоим временную пометку (13, 8) вершине 9.
35 Сделаем постоянной пометку (9, 13) вершины 9 (рис. 12). Поскольку вершина 9 получила постоянную пометку, алгоритм заканчивает работу. Обратным ходом строится искомый путь 0—3—5—8—9 (рис. 13)
36
Рис. 11 Рис. 12
Рис. 13
37 Проверка предложенного алгоритма на небольших примерах позволяет сделать предположение о его работоспособности в задачах многокритериальной оптимизации на графах. Тем не менее эффективность алгоритма может быть подтверждена только масштабной серией вычислительных экспериментов. В настоящее время ведется подготовка к проведению такой серии.
38 Еще одно возможное направление дальнейших исследований связано с заменой метода пометок методом поиска кратчайшего пути в графе, например алгоритма Беллмана–Форда (Bellman, 1958;Moore, 1957), алгоритма Флойда–Уоршелла (Галкина, 2003, гл.4; Cherkassky et al., 1996). В частности, перспективным представляется модифицировать для многокритериальных задач метод двусторонняя очередь, показавший свою эффективность (Левит, Лившиц, 1972, § 17).

References

1. Bellman R. (1958). On a routing problem (íåîïð.) // Quarterly of Applied Mathematics. — 1958. — Ò. 16. — Ñ. 87—90.

2. Cherkassky B.V., Goldberg A.V., Radzik T. (1996), Shortest past algorithms. // Math.Prog. — Springer Science+Business Media 1996. — Vol. 73, Iss. 2. — P. 129–174.

3. Galkina V.A.. (2003). Construction of shortest path in the oriented graph //Discrete Mathematics. Combinatort optimization in the graphs. — Moscow, 2003. — P. 75—94. — 232 p. (In Russian).

4. Hu T.C. (1970). Integer Programming and Network flows. Addison-Wesley Publishing Company. California-London.

5. Levit B.Ju., Livshits V.N. (1972). Non-linear transport problems. Moscow. 144 p. (In Russian).

6. Moore E.F. (1957) The shortest path through a maze// Proceedings of an International Symposium on the Theory of Switching 1957 — Harvard University Press, 1959. — Vol. 2. — P. 285–292. — 345 p. — Annals of the Computation Laboratory of Harvard University. V.30.

7. Podinovskij V.V., Nogin V.D. (1982). Paeto-optimal solutions of multicriterial problems. Moscow, Nauka. (In Russian).

Comments

No posts found

Write a review
Translate