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