École Nationale Supérieure de
Techniques Avancées

Abstract

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.