École Nationale Supérieure de
Techniques Avancées

Résumé

Dans cet article nous étudions un problème bi-objectif : Le premier objectif est de minimiser le coût d’un chemin entre deux noeuds d’un graphe et le second est de maximiser sa distance euclidienne à un ensemble d’obstacles donnés. Nous passons en revue plusieurs méthodes tirées de la littérature qui furent introduites pour des problèmes plus généraux, nous présentons de nouvelles approches pour le problème du plus court chemin évitant des obstacles, et nous montrons qu’elles ont des complexités en temps polynomiales. Tous les codes ont été implémentés en C++ et testés sur deux types de graphes : Des planaires et des complets, pour évaluer leur performance empirique. Deux des méthodes que nous avons élaborées sont sorties du lot lors des ces expériences : SS-ADD2, qui a surpassé les autres méthodes sur les graphes planaires, et BS-LB, qui a surpassé les autres sur les graphes complets.