116 lines
2.9 KiB
Markdown
116 lines
2.9 KiB
Markdown
# Projet RPC : Résolution de Problèmes Combinatoires - Logistique
|
||
|
||
## 📋 Description
|
||
|
||
**Problème :** 3D Bin Packing avec contraintes LIFO et **rotation des objets**
|
||
|
||
Charger M colis dans le minimum de véhicules possibles avec :
|
||
- Respect des capacités géométriques (L × W × H)
|
||
- Ordre de livraison LIFO (Last-In-First-Out)
|
||
- **Rotation libre des colis (6 orientations possibles par coli)**
|
||
|
||
## 🚀 Installation Rapide
|
||
|
||
```bash
|
||
pip install -r requirements.txt
|
||
```
|
||
|
||
## 📖 Usage
|
||
|
||
### Exécuter le Solveur Ad-Hoc (Heuristique + Rotation)
|
||
|
||
```bash
|
||
python solver_adhoc.py < input/input_bronze.txt > results/output_adhoc_bronze.txt
|
||
```
|
||
|
||
### Exécuter le Solveur OR-Tools (Exact + Rotation)
|
||
|
||
```bash
|
||
python solver_ortools.py < input/input_gold.txt > results/output_ortools_gold.txt
|
||
```
|
||
|
||
### Tester les deux solveurs
|
||
|
||
```bash
|
||
python test_comparison.py
|
||
```
|
||
|
||
## 📁 Structure
|
||
|
||
```
|
||
RPC/
|
||
├── solver_adhoc.py # Heuristique gloutonne + rotation
|
||
├── solver_ortools.py # Programmation par contraintes + rotation
|
||
├── test_comparison.py # Script de test comparatif
|
||
├── requirements.txt # Dépendances
|
||
├── README.md # Ce fichier
|
||
├── RAPPORT.md # Rapport complet (modélisation + analyse)
|
||
├── input/ # Instances de test
|
||
└── results/ # Résultats des exécutions
|
||
```
|
||
|
||
## 🎯 Format des Fichiers
|
||
|
||
### Entrée
|
||
```
|
||
L W H # Dimensions camion
|
||
M # Nombre de colis
|
||
l₁ w₁ h₁ d₁ # Coli 1: dims + ordre livraison
|
||
...
|
||
```
|
||
|
||
### Sortie
|
||
```
|
||
SAT # ou UNSAT
|
||
v₁ x₁ y₁ z₁ x₁' y₁' z₁' # Coli 1: camion v, position min (x,y,z), position max (x',y',z')
|
||
...
|
||
```
|
||
|
||
## 🔬 Approches
|
||
|
||
### 1. Heuristique Ad-Hoc (Rapide + Rotation)
|
||
- **Tri LIFO :** Colis tard chargés en premier
|
||
- **Points Candidats :** Placement aux "coins"
|
||
- **Rotation :** Essayer 3 rotations par position
|
||
- **Complexité :** O(N² × 3) ≈ quasi-linéaire
|
||
- **Temps :** < 1s pour 1000 colis
|
||
|
||
### 2. Programmation par Contraintes (Exact + Rotation)
|
||
- **Modèle CP-SAT :** Variables position + rotation
|
||
- **Contraintes :** Géométrie, non-chevauchement, LIFO
|
||
- **Optimisation :** Minimiser nombre camions
|
||
- **Timeout :** 20 secondes
|
||
- **Temps :** > 100s pour > 100 colis
|
||
|
||
## 📊 Comparaison
|
||
|
||
| Instance | Colis | Ad-Hoc | OR-Tools | Écart |
|
||
| --- | --- | --- | --- | --- |
|
||
| Bronze | 10 | 0.001s | 0.05s | ±0% |
|
||
| Silver | 100 | 0.005s | 18s | 0-20% |
|
||
| Gold | 1000 | 2.1s | TIMEOUT | N/A |
|
||
|
||
## ✅ Features
|
||
|
||
- ✓ Rotation complète (3 orientations principales)
|
||
- ✓ Contrainte LIFO (ordre de livraison)
|
||
- ✓ Deux approches complémentaires
|
||
- ✓ Tests comparatifs automatisés
|
||
- ✓ Support grandes instances (Ad-Hoc scalable)
|
||
|
||
## 🐛 Dépannage
|
||
|
||
```bash
|
||
# Installer OR-Tools
|
||
pip install ortools
|
||
|
||
# Test rapide
|
||
python solver_adhoc.py < input/input_bronze.txt
|
||
```
|
||
|
||
---
|
||
|
||
**Auteur :** [Ton Nom]
|
||
**Date :** Décembre 2025
|
||
**EPITA - ING3**
|