Register now After registration you will be able to apply for this opportunity online.
This opportunity is not published. No applications will be accepted.
Three-Dimensional Knapsack Problem with Physical Constraints
This project focuses on developing an efficient methodology for a modified 3D knapsack problem with physical constraints (stability, no replacement, irregular container, etc.) and potentially multiple objectives (maximize occupancy, minimize level differences, etc.).
Packing problems have been intensely studied in academia as they have various applications. For instance, the classical 1D knapsack problem has been
fully explored and solved with Dynamic Programming
in polynomial asymptotic time. However, the 3D packing problem remains NP-hard, and gaps still
exist when physical constraints (e.g. stability) and
multiple objectives are involved, which are essential for practical purpose including container loading and scheduling.
Deliverables
- Review of the state-of-art techniques for 3D
knapsack problem
- Efficient methodology/framework documented
by a report with programming scripts
- 3D-printed demonstrators
Desirable qualities
- Programming Experience
- Knowledge in Optimization Techniques
- Knowledge/Interest in Algorithms
Packing problems have been intensely studied in academia as they have various applications. For instance, the classical 1D knapsack problem has been fully explored and solved with Dynamic Programming in polynomial asymptotic time. However, the 3D packing problem remains NP-hard, and gaps still exist when physical constraints (e.g. stability) and multiple objectives are involved, which are essential for practical purpose including container loading and scheduling.
Deliverables - Review of the state-of-art techniques for 3D knapsack problem - Efficient methodology/framework documented by a report with programming scripts - 3D-printed demonstrators
Desirable qualities - Programming Experience - Knowledge in Optimization Techniques - Knowledge/Interest in Algorithms
The approach/framework should be
compatible with many practical applications in various industries after minor modifications accordingly.
The approach/framework should be compatible with many practical applications in various industries after minor modifications accordingly.