Multiobjective shortest path problem with interval costs

• Thesis title in Czech: Nejkratší cesta v grafu s více intervalovými kritérii
• Thesis title in English: Multiobjective shortest path problem with interval costs
• Key words: nejkratší cesta s více intervalovými kritérii|maximální regret řešení|eficientní řešení
• English key words: the interval multiobjective shortest path problem|the minimax regret problem|an efficient solution
• Academic year of topic announcement: 2022/2023
• Thesis type: diploma thesis
• Thesis language: angličtina
• Department: Department of Applied Mathematics (32-KAM)
• Supervisor: prof. Mgr. Milan Hladík, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 03.02.2023
• Date of assignment: 03.02.2023
• Confirmed by Study dept. on: 14.02.2023
• Date and time of defence: 12.09.2023 09:00
• Date of electronic submission: 16.07.2023
• Date of submission of printed version: 24.07.2023
• Date of proceeded defence: 12.09.2023
• Opponents: RNDr. Jiří Fink, Ph.D.

Guidelines

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.

References

[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