Go back
Binpacking
ISEN CIR 3 - 2024
Role
Developer and Analyst
Duration and Result
30 Hours | 18/20
Team
3 people
Links
Github Repository
Live Site (Soon)
Youtube video
Youtube video Sandbox
Overview
The project aimed to solve a complex optimization problem within the scope of operations research. It involved minimizing the number of containers required to transport goods in a freight train. Through algorithmic and heuristic approaches, we developed solutions for optimal loading of goods based on their dimensions (1D, 2D, 3D) while considering sorting constraints (online and offline).
0.1
Home Page
0.2
1D View
Goal
Reducing the number of containers in goods transportation.
The objective was to develop an algorithm capable of minimizing the number of containers needed to transport goods, taking into account dimensional constraints (length, area, volume). This project also allowed for a comparison of exact and heuristic algorithms in terms of accuracy and computation time, in order to choose the most efficient solutions.
Context
A project in operations research at ISEN.
1.0
2D View
Conducted in June 2024, this third-year academic project at ISEN aimed to introduce us to operations research by enabling us to solve real logistical problems using optimization algorithms. It was carried out in groups of three over a duration of 30 hours and included a precision challenge and a speed challenge to encourage innovation in the proposed solutions.
Process and Methodology
Development of algorithms for combinatorial optimization.
The project was carried out in several stages:
Understanding the problem: Modeling the issue based on the dimensions (1D, 2D, 3D) of the goods and the possibility of sorting them before loading (online vs offline).
Algorithm development: An exact algorithm to obtain the optimal solution, based on mixed-integer linear programming (MILP). A faster but less precise heuristic algorithm to generate solutions in a reduced time.
Performance comparison: Utilizing the time library to measure computation times and compare algorithms in terms of efficiency and speed, along with tracking algorithmic complexity.
3D visualization: Development of a web interface, including a 3D visual representation using Three.js to display the results of the algorithms in both offline and online scenarios.
2.0
3D View (Three.js)
Challenges Faced and Solutions
Addressing algorithm complexity in real time.
Managing large dimensions: The 3D processing of goods presented challenges in terms of modeling.
Balancing precision and speed: The exact algorithm demonstrated precise performance but exhibited long computation times for large datasets. We implemented heuristics that, while less precise, provided acceptable results in record time.
Interactive visualization: Integrating results into a 3D web interface required adjustments to ensure that the visualizations were smooth and comprehensible.
Results
High-performing algorithms and an online visualization system.
3.0
Wagon Information
The project resulted in:
Algorithms capable of efficiently minimizing the number of containers, with optimal accuracy.
Heuristic algorithms that significantly reduced computation times while providing near-optimal solutions.
A web application offering 2D and 3D visualizations of solutions, facilitating understanding and analysis of results for different scenarios (online/offline).
Lessons Learned and Skills Gained
Enhancing the ability to solve logistical optimization problems.
Through this project, I developed advanced skills in:
Optimization and operations research, with the implementation of exact and heuristic algorithms to solve combinatorial problems.
Mathematical modeling of container loading constraints in freight transportation.
Interactive web development, using Three.js to visualize algorithm results in a smooth and dynamic 3D manner.
4.0
Sandbox