Comment appliquer les chaînes augmentantes pour atterrir a lheureReport as inadecuate




Comment appliquer les chaînes augmentantes pour atterrir a lheure - Download this document for free, or read online. Document in PDF available to download.

1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués 2 AMADEUS - Amadeus s.a.s.

Résumé : Lorsqu-un avion approche d-un aéroport , il dispose d-un intervalle de temps slot très limité une vingtaine de minutes pour atterrir. Si l-avion a du retard à cause des conditions météorologiques à cause du retard d-autres avions, ou si lui-même a eu du retard au décollage, il perd son slot et il faut qu-un nouveau slot lui soit attribué par les contrôleurs des opérations de la compagnie aérienne. Cependant, les slots d-atterrissage sont une denrée rare et, pour qu-un avion A puisse atterrir a l-heure, les contrôleurs doivent régulìèrement modifier l-attribution des slots d-autres avions afin d-affecter un slot compatible avec l-heure d-arrivée de l-avion A. Ce problème peut aisément etre modélisé comme un problème de couplage dans un graphe biparti. Malheureusement, dû au système mis en place pour permettre ces échanges, les contrôleurs aériens ne peuvent effectuer leurs modifications qu-en effectuant deux types d-opérations : soit attribuer à l-avion A un slot libre, soit donner à l-avion A le slot d-un avion B et attribuer un slot libre à ce dernier. Le problème devient donc le suivant. Soit G un graphe et M un couplage ensemble d-arêtes deux-à-deux disjointes de G. Comment calculer un couplage maximum pouvant etre obtenu à partir de M en utilisant uniquement des chemins augmentants de longueur au plus k ? Ce problème a déjà été étudié dans le cadre des réseaux sans-fil car il fournit une simple approximation au problème de couplage maximum. Nous prouvons que, pour k = 3, ce problème peut être résolu en temps polynomial, fournissant ainsi un algorithme efficace pour les contrôleurs aériens. Nous prouvons ensuite que, pour tout entier impair k ≥ 5, le problème est NP-complet dans les graphes bipartis planaires de degré au plus 3.





Author: Nicolas Nisse - Alexandre Salch - Valentin Weber -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents