Rolland, Mr Lionel (2022) The shortest path problem avoiding obstacles PRE - Research Project, ENSTA.

Restricted to Repository staff only



In this work we study a biobjective problem: the first objective is to minimize the path cost between two nodes in a network and the second one is to maximize its euclidian distance to a set of given obstacles. We review several methods from the literature that were introduced for more general problems, present new approaches for the shortest path problem avoiding obstacles, and show that they have polynomial time complexity orders. All the codes were implemented in C++ and tested for two types of graphs: planar and complete graphs, for assessing its empirical performance. Two of the methods that we designed stood out in these experiments: SS-ADD2, which outperformed the remaining methods on planar graphs, and BS-LB, which outperformed the remaining methods on complete graphs.

Item Type:Thesis (PRE - Research Project)
Uncontrolled Keywords:Biobjective optimization Network Shortest path problem
Subjects:Mathematics and Applications
ID Code:9175
Deposited By:Lionel Rolland
Deposited On:05 juin 2023 11:25
Dernière modification:05 juin 2023 11:25

Repository Staff Only: item control page