1. Calcul de
tournées de véhicules.
Le problème de routage de véhicules consiste
à calculer les meilleurs parcours pour une flotte de véhicules
devant livrer un ensemble de destinations à partir d'un entrepot.
Chaque véhicule a une capacité limitée.
L'idée ici est d'élaborer des parcours (en forme de fleur
dont les pétales partent de l'entrepot) valides étant donnée
une carte avec les différentes destinations, et des quantités
à livrer. Vous adapterez la méthode de croisement 2-opt ou
mieux l'algorithme de Lin et Kernighan à ce problème (ces
méthodes sont appliquées en général à
un problème assez proche, le problème du voyageur de commerce).
Il faut mettre au point ces méthodes pour les rendre efficaces,
rechercher des améliorations et les tester sur des exemples. Développement
en C, éventuellement visualisation graphique.
2. Stratégies
de remplissage de porte container.
Un porte container fait escale dans différents
ports pour décharger et charger des containers. Les containers sont
rangés par piles. Ainsi lors de la tournée il est parfois
nécessaire de déplacer des containers (sans les débarquer)
car ils se trouvaient au-dessus d'un container à décharger.
L'objectif est de charger le bateau de façon à minimiser
le nombre de ces déplacements inutiles et couteux.
Ce problème est très difficile. L'impossibilite
de calculer complètement le meilleur remplissage conduit à
utiliser des stratégies basées sur l'expérience et
le bon sens. Le but de ce TER est de définir des objectifs pour
le remplissage et de développer différentes méthodes
(complètes et incomplètes) pour atteindre ces objectifs.
Un atelier d'expérimentation servira à mettre au point les
différentes stratégies, afin de les valider et de caractériser
les configurations dans lesquelles certaines sont meilleures que les autres.
Eventuellement mise en place d'un réseau neuronal afin d'aider au
choix de la bonne stratégie en fonction de caractéristiques
du problème.
Développement en C.