Multiobjective shortest path problem with interval costs
Název práce v češtině: | Nejkratší cesta v grafu s více intervalovými kritérii |
---|---|
Název v anglickém jazyce: | Multiobjective shortest path problem with interval costs |
Klíčová slova: | nejkratší cesta s více intervalovými kritérii|maximální regret řešení|eficientní řešení |
Klíčová slova anglicky: | the interval multiobjective shortest path problem|the minimax regret problem|an efficient solution |
Akademický rok vypsání: | 2022/2023 |
Typ práce: | diplomová práce |
Jazyk práce: | angličtina |
Ústav: | Katedra aplikované matematiky (32-KAM) |
Vedoucí / školitel: | prof. Mgr. Milan Hladík, Ph.D. |
Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
Datum přihlášení: | 03.02.2023 |
Datum zadání: | 03.02.2023 |
Datum potvrzení stud. oddělením: | 14.02.2023 |
Datum a čas obhajoby: | 12.09.2023 09:00 |
Datum odevzdání elektronické podoby: | 16.07.2023 |
Datum odevzdání tištěné podoby: | 24.07.2023 |
Datum proběhlé obhajoby: | 12.09.2023 |
Oponenti: | RNDr. Jiří Fink, Ph.D. |
Zásady pro vypracování |
Hledání nejkratší cesty v grafu je známá úloha. My se ale zaměříme na případ, kdy máme více kritérií, navíc délky hran nejsou přesná čísla, ale známe jen jejich intervalový rozsah.
Cílem práce je navrhnout a prozkoumat robustní řešení takovýchto úloh, například využít konceptu nutně eficientních řešení. Z algoritmického hlediska nás pak zajímá design příslušných metod a analýza jejich složitosti. |
Seznam odborné literatury |
[1] I. Averbakh and V. Lebedev. Interval data minmax regret network optimization problems. Discrete Appl. Math., 138(3):289-301, 2004
[2] M. Hladík. Complexity of necessary efficiency in interval linear programming and multiobjective linear programming. Optim. Lett., 6(5):893-899, 2012 [3] H. Yaman. Essays on some combinatorial optimization problems with interval data. Master’s thesis, Department of Industrial Engineering, Bilkent University, 1999, http://repository.bilkent.edu.tr/handle/11693/18114 |