Retour
Binpacking
ISEN CIR 3 - 2024
Rôle
Développeur et Analyste
Durée et résultat
30 Heures | 18/20
Équipe
3 personnes
Liens
Github Repository
Live Site (Soon)
Youtube video
Youtube video Sandbox
Aperçu
Le projet visait à résoudre un problème complexe d'optimisation dans le cadre de la recherche opérationnelle. Il consistait à minimiser le nombre de conteneurs nécessaires pour transporter des marchandises dans un train de fret. À travers des approches algorithmiques et heuristiques, nous avons développé des solutions pour le chargement optimal des marchandises en fonction de leurs dimensions (1D, 2D, 3D) et en tenant compte des contraintes de tri (online et offline).
0.1
Page d'accueil
0.2
Vue dimension 1
Objectif
Réduire le nombre de conteneurs dans le transport de marchandises
L’objectif était de développer un algorithme capable de minimiser le nombre de conteneurs nécessaires pour transporter des marchandises, en tenant compte des contraintes de dimensions (longueur, surface, volume). Ce projet a également permis de comparer des algorithmes exacts et heuristiques en termes de précision et de temps de calcul, afin de choisir les solutions les plus efficaces.
Contexte
Un projet en recherche opérationnelle à l'ISEN
1.0
Vue Dimension 2
Réalisé en Juin 2024, ce projet académique de troisième année à l'ISEN avait pour de nous introduire à la recherche opérationnelle, en nous permettant de résoudre des problèmes logistiques réels à l’aide d’algorithmes d’optimisation. Il a été mené en groupes de trois personnes sur une durée de 30 heures et comprenait un challenge de précision et un challenge de rapidité pour encourager l’innovation dans les solutions proposées.
Processus et méthodologie
Développement d'algorithmes pour une optimisation combinatoire
Le projet s'est déroulé en plusieurs étapes :
Compréhension du problème : Modéliser le problème en fonction des dimensions (1D, 2D, 3D) des marchandises et de la possibilité ou non de les trier avant chargement (online vs offline).
Développement des algorithmes : Un algorithme exact pour obtenir la solution optimale, basé sur la programmation linéaire en nombres entiers (MILP). Un algorithme heuristique plus rapide mais moins précis, pour générer des solutions en un temps réduit.
Comparaison des performances : Utilisation de la librairie time pour mesurer les temps de calcul et comparer les algorithmes en termes d’efficacité et de rapidité, avec un suivi de la complexité algorithmique.
Visualisation 3D : Développement d’une interface web, incluant une représentation visuelle en 3D avec Three.js pour afficher les résultats des algorithmes en offline et online.
2.0
Vue 3D (Three.js)
Défis rencontrés et solutions
Résoudre la complexité des algorithmes en temps réel
Gestion des grandes dimensions : Le traitement en 3D des marchandises a posé des défis en termes de modélisation.
Équilibrage entre précision et rapidité : L’algorithme exact a montré des performances précises mais des temps de calcul très longs pour les grands ensembles de données. Nous avons implémenté des heuristiques qui, bien que moins précises, permettaient d’obtenir des résultats acceptables en un temps record.
Visualisation interactive : Intégrer les résultats dans une interface web 3D a requis des ajustements pour garantir que les visualisations soient fluides et compréhensibles.
Résultats
Des algorithmes performants et un système de visualisation en ligne
3.0
Information sur les wagons
Le projet a permis d'obtenir :
Des algorithmes capables de minimiser efficacement le nombre de conteneurs, avec une précision optimale.
Des algorithmes heuristiques permettant de réduire considérablement les temps de calcul tout en fournissant des solutions proches de l’optimum.
Une application web offrant une visualisation en 2D et 3D des solutions, facilitant la compréhension et l’analyse des résultats pour différents scénarios (online/offline).
Retours d'expérience et compétences acquises
Amélioration de la capacité à résoudre des problèmes d'optimisation logistique
Grâce à ce projet, j’ai pu développer des compétences avancées dans :
Optimisation et recherche opérationnelle, avec la mise en place d’algorithmes exacts et heuristiques pour résoudre des problèmes combinatoires.
Modélisation mathématique des contraintes de chargement de conteneurs dans le transport de fret.
Développement web interactif, en utilisant Three.js pour visualiser les résultats des algorithmes en 3D de manière fluide et dynamique.
4.0
Sandbox