Optimisation Combinatoire -- Hill-climbing/VND pour SMTWTP

Dans ce TP, nous allons implémenter des descentes simples pour le problème SMTWTP.

Pré-requis

Pour attaquer ce TP, il faut au moins pouvoir lire les instances données dans le TP précédent. Nous aurons aussi besoin des heuristiques gloutonnes implémentées.

Hill-Climbing

Le but de cette partie est de mettre en place plusieurs version d'un algorithme de descente en jouant sur différents 'paramètres' puis d'en étudier les performances.

• Choix de la stratégie de sélection :

  • First improvement

  • Best improvement

• Choix du voisinage :

  • Insertion, i.e., insérer un job de la position i à la position j

  • Swap, i.e., inter-échanger deux jobs aux positions i et j

  • échange, i.e., inter-échanger deux jobs dans des positions successives j et j+1

• Solution initiale :

  • Random

  • heuristique

    • EDD

    • MDD

Travail à effectuer : 

• Mettre en place les différentes versions possibles. Attention : Au totale cela fait 18 versions possibles de votre algorithme de descente ! Biensur, il s'agit de faire en sorte d'avoir un seul programme qui selon les paramètres spécifiés en entrée execute une version bien précise (réutiliser votre code), e.g., java HillClimbingSMTWTP -select [first,best] -voisinage [insert,swap,exchange] -init [rnd,edd,mdd]

• Pour chaque instance, et chaque version de votre algorithme, exécuter k runs différents (typiquement k=30). Enregistrer les deux mesures suivantes :

  • Le temps de calcul nécessaire de chaque run.

  • La déviation par rapport à la meilleur solution connue, i.e., 100 * (coût de la solution trouvée - coût de la meilleur solution connue) / (coût de la meilleur solution connue)

• comparer les différents résultats en moyenne pour chaque instance 

Variable Neighborhood Descent

On considère les trois derniers voisinages dans les deux ordres suivants :

• échange, swap, insertion

• échange, insertion, swap

Travail à effectuer :

• En utilisant ces voisinages, Implémenter un VND pour le SMTWTP. Testez les différentes variantes et observer leur comportement relatif.

• Même chose en imaginant une stratégie de choix aléatoire des voisinage et/ou en jouant sur le nombre d'itération par voisinage.

• Tester vos algorithmes en considérant une solution initiale aléatoire et une solution gloutonne.

• Comparer (déviation et temps de calcul) par rapport aux différentes descentes que vous avez implémentées. Quelles conclusions vous pouvez en tirer ?