Planning de Rotations ou Maths Concrètes. Partie 3.

Ce sujet demeurait en suspens depuis maintenant 9 mois. Cela fait cependant uniquement quelques semaines que les résultats sont apparus : pas mal de recherches et de nombreux tests (majoritairement infructueux...) donc.

Dans les deux précédents épisodes (voir Juin 2010), je vous avais expliqué le principe du problème, ainsi que défini ce qu’est une combinaison. Aujourd’hui, nous nous penchons sur le dernier volet de la saga, concernant la détermination des combinaisons possibles, ainsi que de la sélection de celles-ci.

J’ai utilisé pour cela Matlab (release 2007b), qui est un logiciel de calcul scientifique et technique. Une version de test est disponible sur le site de Mathworks.

1 – Détermination des combinaisons

Comme vous le savez, le nombre de combinaisons $C^{k}_{n}$ augmente exponentiellement avec le nombre d’éléments n. Il est donc nécessaire de privilégier à la fois la vitesse d’exécution et la mémoire requise pour effectuer le calcul de détermination. Mes recherches sur le sujet m’ont permis de trouver une fonction efficace, appelée nchoose.

Cette fonction utilise le principe du Power Set (ou "Ensemble des parties d'un ensemble" en français). Chaque élément est étudié un à un, puis assemblé à un autre méthodiquement. La représentation du processus ci-dessous s’applique à un ensemble de 3 éléments {x, y, z}. Il s’agit d’une méthode rigoureuse, structurée et donc sûre.

Structure du Power Set de {x, y, z}.
(Crédit Wikimedia, Creative Commons)

La fonction nchoose possède un atout supplémentaire, qui est de tout transformer en format binaire afin d’accroître la vitesse d’exécution, le binaire étant le langage natif du processeur. Les valeurs sont ensuite reconverties en format décimal avant affichage.

La difficulté principale à surmonter fut la gestion des formats d’entrée/sortie, mais je ne m’attarderai pas trop sur le sujet, car spécifique à Matlab. Obtenir une valeur par case semble moins compliqué qu’il ne l’est !

2 – Sélection des combinaisons

Comme je l’ai dit, chaque élément est en réalité une rotation sur une destination, avec une durée déterminée. Le principe est toujours de déterminer quelle meilleure combinaison de rotations nous pouvons obtenir sur une semaine (soit 168 heures), par exemple.

Nous possédons une base de données de rotations, telle que celle ci-dessous. Ces données sont classées suivant différents paramètres. Toutefois, il apparaît que ces paramètres sont également nos critères de choix préférentiels : une ligne "prioritaire" apparaîtra donc au somment de la liste, une fois le classement effectué.

Base de données des rotations disponibles.

Le programme de sélection des combinaisons prend en entrée un simple fichier texte à deux colonnes, avec le numéro de vol et la durée associée. Dans notre cas, et en raison de limitations matérielles, il n’est pas possible d’avoir plus de 22 rotations (tout de même 4 194 303 combinaisons différentes), d’où un numéro de vol de 100 à 121. Une fois copiées/collées puis nettoyées, les données d’entrée sont les suivantes :

Tableauvols.txt =
    100 7.5
    101 11
    102 7
    103 14
    104 12.5
    105 25.5
    106 11.5
    107 6
    108 12
    109 11
    110 12.5
    111 15
    112 9
    113 8.5
    114 9.5
    115 13
    116 12.5
    117 13.5
    118 8
    119 13.5
    120 8.5
    121 25.5

Attention à remplacer les virgules par des points dans les valeurs décimales...
Le programme va alors déterminer les combinaisons possibles en se basant sur le numéro de vol. Une fois cette étape terminée, les numéros de vol vont être remplacés par la durée correspondante (une simple recherche de rang dans le fichier d’entrée, en sautant de la colonne 1 à 2). La durée totale de chaque combinaison est alors calculée. Cette dernière, en fonction de la durée totale recherchée (avec ou sans marge d’erreur), va être retenue ou pas.

Et voilà, le travail est maintenant terminé ! :o)

Le fichier de sortie présente alors les combinaisons de rotations potentielles satisfaisantes, en les classant par durée totale et par priorité de vol. Priorité de vol ? Oui, comme expliqué quelques lignes plus haut, une rotation prioritaire se trouvera au somment de la liste, donc assignée d’un numéro de vol faible. Ainsi, plus les vols de la combinaison sont prioritaires, plus la somme des numéros de vol sera faible (même si pas rigoureusement exact, l’approximation est ici suffisante).

Ainsi, la première colonne du fichier de sortie nous donne la durée totale de la combinaison, et la seconde colonne la somme des numéros de vol. Les colonnes suivantes sont les numéros de vol de la combinaison. Le programme classe tout d’abord les rotations potentielles par durée totale décroissante, puis par somme de numéros de vol décroissante. De cette manière, les meilleurs résultats seront localisés au sommet de la liste.

Rotations potentielles classées.

Pour terminer, voilà le code. Blogger ne possédant pas de coloration syntaxique, le résultat n’est pas très agréable à regarder.

close all;
clear all;
format compact;

load('tableauvols.txt');
flt_nb = tableauvols(:,1);
duree = tableauvols(:,2);

%% DUREE CIBLE (h)
%
%
% Donnees a remplir de maniere a indiquer
% au programme sur quelles criteres de
% selection se baser :
%
%%%%%%%%%%%%%%%%
T = 168;       %
marge = 10; %  %
%%%%%%%%%%%%%%%%
%
%
% MAXIMUM 22 ELEMENTS !!!
%
%
%
disp(['Duree Rotation : ',  num2str(T), ' h']);


%% COMBIEN D'ELEMENTS ?

% length(flt_nb);
disp(['Nb elements : ',  num2str(length(flt_nb))]);

%% COMBIEN DE COMBINAISONS DIFFERENTES ?
 
nbComb=0;
for i=1:1:length(flt_nb);
    nbCombcalc = factorial(length(flt_nb))./(factorial(i).*factorial(length(flt_nb)-i));
    disp(['Nb Combinaison(s) pour ', num2str(i),' element(s) : ', num2str(nbCombcalc)]);
% end
% 
% for i=1:1:length(flt_nb);
%     nbCombcalc = factorial(length(flt_nb))/(factorial(i)*factorial(length(flt_nb)-i));
    nbComb = nbComb + nbCombcalc;
end
disp(['Nb Combinaisons : ',  num2str(nbComb)]);

%% CREATION TABLEAU DE RESULTATS VIDE
resultats = zeros (nbComb, length(flt_nb));

%% IDENTIFICATION DES COMBINAISONS
% http://www.mathworks.com/matlabcentral/fileexchange/20011-nchoose-v2-1-ma
% r-2010
M = nchoose(flt_nb);

% COPIE DES VALEURS DANS TABLEAU RESULTATS
% 1 VALEUR PAR CELLULE
for k=1:1:nbComb;
%     length(M{k,1});
    resultats(k,1:length(M{k,1})) = M{k}; % copie valeurs sur cellules de la ligne
end

%% EQUIVALENCES FLT_nb ET DUREE DE VOL

% CREATION NOUVEAU TABLEAU (matrice remplie de zeros)
results = zeros (nbComb, length(flt_nb)+2);

% EQUIVALENCES nb/temps
% remplissage de la matrice 'results'
for k=1:1:nbComb;
    for l=1:1:length(flt_nb);
        if resultats(k,l) ~= 0; %  NOT zero
           indice = find(resultats(k,l)==tableauvols);
            results(k,l) = duree(indice);
        end
    end
end

% DUREE DE LA ROTATION PROPOSEE

for k=1:1:nbComb;
    results(k,length(flt_nb)+1) = sum(results(k,1:length(flt_nb)));
end

% PRIORITE DES VOLS
% Les vols prioritaires sont en premier ds 'tableauvols',
% dc possedent un No de vol faible : la somme des Nos
% de vol reflete le choix des vols : plus elle est faible, plus
% les vols selectionnes correspondent a la priorite etablie.
for k=1:1:nbComb;
    results(k,length(flt_nb)+2) = sum(resultats(k,1:length(flt_nb)));
end

%% CHOIX DES ROTATIONS

% marge
t = T*(1-marge/100);

indice = find(results(:,length(flt_nb)+1) >= t & results(:,length(flt_nb)+1) <= T);
% ROT_POT = ROTations POTentielles
ROT_POT = [results(indice,length(flt_nb)+1) results(indice,length(flt_nb)+2) resultats(indice,:)];
ROT_POT2 = sortrows(ROT_POT, [-1 2]); % sorting selon duree totale puis priorite des vols. :o)

% Ouverture du fichier resultat ENTIER
open('ROT_POT2')

% Si nombre de resultats important : choix des 50 meilleurs
% ROT_POTf = ROT_POT2(1:50,:);
% open('ROT_POTf')

Le problème est maintenant résolu, et est opérationnel ! Mais ne vous inquiétez pas, j’ai un nouveau sujet de travail pour très bientôt.

Bye for now...