Questions et réponses sur le Challenge ROADEF 2009

Question 1 : D'après le sujet du challenge, il est possible de créer de nouveaux vols. Il nous semble que de ce fait, le changement d'appareil entre familles différentes est possible. Par exemple le vol Orly-Nice partant à 11h00 opéré par l'A320#2 est annulé, et le vol Orly-Nice partant à 11h00 opéré par le B747#1 est crée. Pouvez-vous confirmer/infirmer que cela est bien possible ?

Réponse : La réponse à la question est oui. Il est tout à fait possible de créer un vol avec un appareil d'une quelconque famille. Ce qu'il faut bien voir dans ce cas, c'est que ce sera un vol différent, auquel un numéro de vol unique et non encore utilisé devra être affecté. En d'autre termes, il sera impératif de réaccomoder l'ensemble des passagers empruntant le vol initial annulé. Il faudra de plus faire en sorte que la suite de la rotation affectée à l'appareil remplacé reste cohérente. Si on reprend l'exemple donné, et si on suppose un Nice-Orly partant à 14h00 qui fait suite au Orly-Nice de 11h00, il faudra soit l'opérer par un airbus, disponible à Nice, soit l'annuler et créer un nouveau vol Nice-Orly opéré par le B747#1, ou un autre appareil, et dans ce cas, réaccomoder les passagers empruntant le Nice-Orly. Autant dire que la création de nouveaux vols est très fortement impactante et peut nécessiter des opérations d'optimisation supplémentaires et potentiellement coûteuses, d'autant plus que les capacités des appareils sont amenées à différer, auquel cas on peut se retrouver avec un avion presque vide, ou des passagers qui ne peuvent être transportés. Possible donc, mais il s'agit de choisir judicieusement les cas où celà présente un réel intérêt.

Question 2 : Dans la première instance A01, le fichier des distances annonce une distance entre MPL et ORY de 85 minutes. Or, le vol 4406 MPL ORY 8:05 à 9:25 ne met que 80 minutes. Cette incohérence est elle normale  ?

Réponse : Il ne s'agit pas d'une incohérence. Les plans de vols sont inspirés de données réelles, et contiennent donc des vols possédant des durées différentes pour un même itinéraire. Par exemple, un vol peut être plus ou moins long du fait des vitesses différentes des appareils qui l'opèrent. Par contre, au niveau du fichier des distances, nous avons déterminé une distance non variable qui correspond en fait à la distance maximum que l'on peut retrouver dans le plan de vols. En résumé, pour créer un vol, on doit utiliser le temps donné dans le fichier des instances. Pour retarder un vol existant, on doit conserver le temps prévu dans le fichiers des vols.

Question 3 : Dans l'instance A01,Le vol 4600 a un retard de 75 minutes, il arrive donc à CDG à 8:00 (06:45+1:15 = 8:00). Le vol 145 a un retard de 9 minutes, il part donc de CDG à 08:14 (08:05+0:09 = 08:14). Ce qui fait 14 minutes entre l'arrivée de l'un et le départ de l'autre. Or les itinéraires ci-dessus empruntent ces deux vols à la suite et demandent donc un temps de transit de 30 minutes. Selon l'énoncé, on ne peut modifier ni les vols, ni la partie des itinéraires qui se trouvent avant 12:00 (fichier de config). Ma question est donc de savoir s'il s'agit d'une erreur dans l'énoncé ou si on doit supposer que les passagers ont raté leur vol et qu'il faut leur faire prendre un autre vol? Ou y a-t-il une autre explication?

Réponse : Pour les passagers arrivés ou déjà partis en début de période de recouvrement, la partie de leur itinéraire précédant le début de la période (c'est-à-dire portant sur des vols déjà partis, au sens mentionné dans le sujet, i.e "dont l'heure de départ indiquée dans le programme initial de vols est strictement antérieure au début de la période de recouvrement") ne peut être modifiée, dans la mesure du possible. Ainsi, ils empruntent les vols successifs de leur itinéraire, que ceux-ci soient retardés ou pas, tant qu'il n'y a pas de violation de contrainte (temps minimum de correspondance ou vol annulé). Différents cas de figure peuvent se présenter :

  • ils sont en mesure de prendre l'ensemble des vols déjà partis prévus dans leur itinéraire : ils sont soit arrivés (avec retard possible => coûts de retard éventuels), soit en correspondance pendant la période de recouvrement ( => réaccomodation classique sur les vols de la période de recouvrement pour les faire arriver à destination ou annulation de leur voyage);
  • ils ont manqué une correspondance ou un vol intermédiaire de l'itinéraire a été annulé : ils sont en correspondance, éventuellement avant le début de la période ( => réaccomodation classique sur les vols fixes, partis avant le début de la période, et/ou les vols de la période pour les faire arriver à destination ou annulation de leur voyage);
  • le premier vol de leur itinéraire a été annulé : ils sont au début de leur voyage ( => réaccomodation classique sur les vols fixes, partis avant le début de la période, et/ou les vols de la période pour les faire arriver à destination ou annulation de leur voyage).

De façon concrète, si on reprend l'exemple des passagers empruntant le vol 4600 puis 145, ils ont donc pris le premier vol avec le retard constaté et ne peuvent assurer la correspondance. Ils se retrouvent donc "coincés" à CDG à 8h00. Il s'agit alors de tenter de les réaccomoder vers Mulhouse (à partir de 8h30, du fait du temps min de correspondance), soit sur un vol "fixe" qui part avant 12h00, soit sur un des vols de l'après-midi. Quelle que soit la solution choisie, les coûts de retard associés devront être calculés et ajoutés à la fonction objectif, ou les coûts d'annulation si aucun itinéraire alternatif ne peut être trouvé. Dans ce dernier cas, les coûts d'annulation sont ceux de passagers en correspondance (coûts d'annulation élevés). Si on suppose à présent que le premier vol est annulé, les passagers doivent être réaccomodés de Brest à Mulhouse, à partir de 5h25, ou annulés (coûts d'annulation de passagers en itinéraire aller pour les passagers 80, 82, 95, 96 et de passagers en itinéraire retour pour les passagers 84, 86).

Question 4 : Dans le cas, d'un itinéraire aller-retour (A->B->C->B->A), si je comprends bien, si on veut modifier ce genre d'itinéraire, on ne peut pas se contenter de réaffecter les passagers sur d'autres vols, il faut en plus s'assurer qu'ils visitent bien la ville "destination" (celle en plein milieu du trajet) et doit-on en plus "respecter" le plus possible les fenêtres de temps à cet endroit? La réaffectation (du trajet intermédiaire) via d'autres aéroports ne serait donc possible que pour des allers (ou des retours) simples?

Réponse : Non, pour simplifier et malgré le côté "absurde" que cela peut engendrer, Les aller/retour doivent être traités comme des allers simples sans obligation de passer par aucune ville intermédiaire. Il s'agit donc de ramener le passager à son point de départ quel que soit le trajet (par exemple A->D->C->F->A!) ou d'annuler le vol avec une pénalité.

Question 5 : Au niveau des pénalités, les allers-retours doivent-ils être considérés séparément ou s'il s'agit vraiment que d'un aller? Entre autres, peut-on acheminer les passagers au point C (voir exemple précédent) sans avoir l'obligation de les ramener au point A? (sous peine de pénalités, il va sans dire)

Réponse : Ils sont considérés comme des aller. Soit on annule la totalité du voyage, soit on achemine jusqu'au bout (c'est à dire juqu'au point de départ dans ce cas). Au contraire des retours, on n'a pas ici le risque de laisser un passager loin de chez lui (sauf si le passager a déjà débuté son itinéraire, auquel cas de toute façon la pénalité de correspondance est utilisée en lieu de la pénalité d'aller). Pour résumer : passager non encore parti de son point de départ => pénalité d'aller; passager déjà parti => pénalité de correspondance.

Question 6 : Si un avion n'accumule pas le temps de vol maximum durant la période de recouvrement (à cause de vols annulés), doit-on quand même en faire l'entretien à l'endroit et à l'heure prévue?

Réponse : Le potentiel de vol fixe une limite supérieure uniquement, donc on n'est pas obligé d'atteindre ce temps de vol avant une maintenance, i.e. toutes les maintenances doivent impérativement être réalisées en lieu et date prévus, même si l'appareil voit son nombre de vols assurés diminué.

Question 7 : Doit-on prévoir d'autres maintenances pour les avions que celles aux heures mentionnées?

Réponse : Non.

Question 8 : Pourquoi la durée initiale de trajet ne prend-elle pas en compte les durées de connexion, dans le cas des trajets avec plusieurs vols

Réponse : Cette durée ne sert qu'à une chose : au calcul des indemnités réglementaires en cas de retard ou d'annulation. Les indemnisations réglementaires des passagers dépendent de cette durée initialement prévue et du retard constaté. Le retard est lui calculé sur la base du retard a l'arrivée" (5.2) i.e, en comparant les heures d'arrivée à destination finale.

Question 9 : Le retard des vols s'applique-t-il a la fois au depart et a l'arrivee(fichier alt_flights.csv) ou seulement a l'arrivee ?

Réponse : Il s'applique au depart ET a l'arrivee.

Question 10 : Est-il possible d'allonger la duree des vols pour profiter d'une meilleure plage d'atterrissage?

Réponse : Cela n'est pas possible. En revanche, on peut retarder le vol au départ, ce qui impliquera un retard à l'arrivée et l'utilisation éventuelle d'un meilleur créneau d'atterrissage.

Question 11 : Le calcul parallèle est-il autorisé?

Réponse : Non.

Question 12 : Les fenêtres horaires sur lesquelles sont définies les capacités aéroportuaires sont-elles toujours exprimées en heure pleine, c'est-à-dire que le terme MM dans HH:MM est toujours 00 ? La question vaut également pour le fichier des perturbations. De plus, les intervalles horaires de définition des capacités sont-ils toujours donnés triés comme c'est le cas dans l'exemple et dans les fichiers de la base A ?

Réponse : Les fenêtres horaires sont toujours exprimées en heures pleines dans les fichiers que nous avons fournis (base A), mais nous ne pouvons pas certifier que cela sera toujours le cas pour les jeux d'instances B et X, notamment en ce qui concerne les perturbations aéroportuaires. Par contre, nous assurons de toujours fournir les intervalles horaires triés. Dans le cas où une fenêtre n'est pas donnés en heures pleines, la capacité sur la fenêtre est calculée de la façon suivante : durée de la fenêtre (en heure) * capacité horaire. Par exemple, soit la fenêtre [11h45 - 14h30[ associée à la capacité horaire 4. La capacité globale sur la fenêtre est de 4 * 2.75 = 11, répartie de la façon suivante :
[11h45 - 12h00[ : 1 - [12h00 - 13h00[ : 4 - [13h00 - 14h00[ : 4 - [14h00 - 14h30[ : 2

Question 13 : Est il autorisé d'avoir de l'avance à l'arrivée sur un itinéraire réaccomodé ?

Réponse : Oui. Par exemple, un passager qui faisait NCE-ORY (8h-9h25) puis ORY-LIL (10h15-11h05) peut très bien être réaccomodé sur un NCE-LIL (8h30-10h10), ce qui le ferait arriver en avance par rapport à son itinéraire d'origine.

Question 14 : Lors des maintenances, l'appareil en maintenace peut il commencer sa mainteance immédiatement après une arrivée et redécoller immédiatement après sa maintenance ? Ou faut il qu'il vérifie en plus les déais de transit ?

Réponse : Non, il n'y a pas de délai. On considère qu'un avion arrivant à 8h par exemple peut tout à fait débuter sa maintenance à 8h. En fait, les créneaux de maintenance sont suffisamment larges pour prendre en compte ce délai éventuel à l'arrivée de l'appareil (et cela vaut également pour le redécollage immédiat possible suite à une maintenance).

Question 15 : Un passager qui a commencé à être pris en charge avant la période de recouvrement (c.à.d. un passager en correspondance) doit etre acheminé à sa destination en priorité (sous peine de fortes pénalités). Si l'itinéraire était initialement un Aller simple, a droit à un retard maximum de 18h (comme pour un Aller), ou à un retard maximum plus important (comme pour un retour) ?

Réponse: Dans le cas des passagers en correspondance ou sur un itinéraire retour, on n'a pas de contrainte de retard maximum, comme indiqué dans le sujet.

Question 16 : Si un vol a un retard qui fait que l’heure de départ passe au lendemain (par exemple Heure originale de depart : 23h00 (01/01/2008), Retard : 70 minutes) et si nous écrivons la date qui correspond (02/01/2008) dans le fichier sol_rotations.csv, le vérificateur de solutions l’interprète comme un vol déjà parti. C'est la même chose pour les itinéraires (il indique que l'itinéraire part avant l’heure de départ originale). Y a-t-il une erreur du vérificateur ?

Réponse: La date de départ d'un vol donné doit demeurer identique à celle du vol original. Dans le cas où le vol part le lendemain par exemple, c'est le marqueur "+1" après l'heure de départ qui va faire en sorte que la date soit correcte. Pour l'exemple donné ci-dessus, le vol partirait donc le 01/01/2008 à 00h10+1. Il n'y a pas d'erreur dans le vérificateur sur ce point.

Question 17 : Un vol est identifié dans un plan de vols par son numéro et sa date. Or, lors du retard de certains vols, il peut fréquemment arriver que deux vols distincts aient le même identifiant et soient programmés le même jour. Cela ne pose pas de problème dans le fichier « sol_rotations » grâce à l’utilisation du « +1 ». Par contre cela semble pouvoir poser problème dans certains cas au niveau des itinéraires. En effet lorsque nous sauvegardons le fichier sol_itineraries, nous devons préciser la date initiale de chaque vol (de manière à les distinguer), mais le vérificateur de solutions peut alors interpréter cela comme une erreur si cette date initiale est antérieure au départ prévu des passagers concernés. Comment contourner ce problème, sachant que l’utilisation du « +1 » dans ce fichier semble inefficace à l’heure actuelle ?

Réponse: Le +1 dans le fichier sol_rotations n'est pas prévu pour décaler des vols d'une journée à une autre mais pour préciser l'heure d'arrivée de certains vol qui débutent en fin de journée (par exemple 23h00) et se terminent le lendemain (ex 01h00 du matin). En realité, 2 vols avec un même identifiant n'existent jamais le même jour. Dans ce cas la, au lieu de garder les 2 vols avec le meme identifiant, il faut annuler l'un des deux et re-créer un autre avec un identifiant différent et la date correspondante afin d'éviter les conflits. Cela ne change rien en terme de cout de la solution puisqu'il sera question du même vol opéré par le même appareil.