189 lines
7.4 KiB
Python
189 lines
7.4 KiB
Python
#!/usr/bin/env python3
|
|
"""
|
|
Solveur OR-Tools avec Support de Rotation 3D
|
|
Programmation par Contraintes avec 6 orientations possibles par coli
|
|
"""
|
|
|
|
import sys
|
|
from ortools.sat.python import cp_model
|
|
|
|
|
|
def solve_ortools():
|
|
"""Solveur CP-SAT avec support de rotation"""
|
|
# --- LECTURE ---
|
|
input_data = sys.stdin.read().split()
|
|
if not input_data:
|
|
return
|
|
iterator = iter(input_data)
|
|
|
|
try:
|
|
L_truck = int(next(iterator))
|
|
W_truck = int(next(iterator))
|
|
H_truck = int(next(iterator))
|
|
M = int(next(iterator))
|
|
except StopIteration:
|
|
return
|
|
|
|
item_original_dims = []
|
|
item_orders = []
|
|
for i in range(M):
|
|
l = int(next(iterator))
|
|
w = int(next(iterator))
|
|
h = int(next(iterator))
|
|
d = int(next(iterator))
|
|
item_original_dims.append((l, w, h))
|
|
item_orders.append(d)
|
|
|
|
# Générer toutes les rotations possibles pour chaque coli
|
|
# Pour chaque coli, on a 3 rotations uniques principales
|
|
def get_rotations(dims):
|
|
l, w, h = dims
|
|
# 3 rotations principales (les 3 axes X, Y, Z)
|
|
return [
|
|
(l, w, h),
|
|
(l, h, w),
|
|
(w, l, h),
|
|
]
|
|
|
|
all_rotations = [get_rotations(dims) for dims in item_original_dims]
|
|
|
|
max_vehicles = M
|
|
|
|
# --- MODÈLE CP-SAT ---
|
|
model = cp_model.CpModel()
|
|
|
|
# VARIABLES
|
|
|
|
# Pour chaque coli, on doit choisir une rotation ET une position
|
|
# Approach 1 : Créer des variables pour chaque rotation possible
|
|
# is_rotation[i][r] = True si coli i utilise rotation r
|
|
|
|
item_vehicle = []
|
|
item_x = []
|
|
item_y = []
|
|
item_z = []
|
|
item_rotation = [] # Index de rotation utilisée
|
|
|
|
for i in range(M):
|
|
# Véhicule assigné
|
|
v_id = model.NewIntVar(0, max_vehicles - 1, f'v_id_{i}')
|
|
item_vehicle.append(v_id)
|
|
|
|
# Rotation choisie (index dans all_rotations[i])
|
|
rot_idx = model.NewIntVar(0, len(all_rotations[i]) - 1, f'rot_{i}')
|
|
item_rotation.append(rot_idx)
|
|
|
|
# Les dimensions dépendent de la rotation, donc on force manuellement
|
|
# Pour simplifier, on crée des variables pour chaque dimension possible
|
|
# et on force le choix via disjonction
|
|
|
|
max_dim = max(max(d) for d in all_rotations[i])
|
|
|
|
item_x.append(model.NewIntVar(0, L_truck - 1, f'x_{i}'))
|
|
item_y.append(model.NewIntVar(0, W_truck - 1, f'y_{i}'))
|
|
item_z.append(model.NewIntVar(0, H_truck - 1, f'z_{i}'))
|
|
|
|
# Variables : "véhicule utilisé"
|
|
vehicle_used = [model.NewBoolVar(f'v_used_{v}') for v in range(max_vehicles)]
|
|
|
|
# Assignation unique
|
|
for i in range(M):
|
|
is_in_vehicle = [model.NewBoolVar(f'in_v{v}_i{i}') for v in range(max_vehicles)]
|
|
model.Add(sum(is_in_vehicle) == 1)
|
|
for v in range(max_vehicles):
|
|
model.Add(item_vehicle[i] == v).OnlyEnforceIf(is_in_vehicle[i])
|
|
# Activer vehicle_used
|
|
model.Add(vehicle_used[v] == True).OnlyEnforceIf(is_in_vehicle[i])
|
|
|
|
# CONTRAINTES
|
|
|
|
# A. Contraintes géométriques avec rotation
|
|
for i in range(M):
|
|
for rot_idx, (l, w, h) in enumerate(all_rotations[i]):
|
|
is_this_rotation = model.NewBoolVar(f'is_rot_{i}_{rot_idx}')
|
|
|
|
# Lier la variable booléenne à l'index de rotation
|
|
model.Add(item_rotation[i] == rot_idx).OnlyEnforceIf(is_this_rotation)
|
|
model.Add(item_rotation[i] != rot_idx).OnlyEnforceIf(is_this_rotation.Not())
|
|
|
|
# Si cette rotation est choisie, appliquer les bornes
|
|
model.Add(item_x[i] + l <= L_truck).OnlyEnforceIf(is_this_rotation)
|
|
model.Add(item_y[i] + w <= W_truck).OnlyEnforceIf(is_this_rotation)
|
|
model.Add(item_z[i] + h <= H_truck).OnlyEnforceIf(is_this_rotation)
|
|
|
|
# B. Non-chevauchement (simplifié : approximation 2D sur axe X-Y)
|
|
# Note: Full 3D no-overlap est complexe avec rotations en CP-SAT
|
|
for i in range(M):
|
|
for j in range(i + 1, M):
|
|
same_vehicle = model.NewBoolVar(f'same_{i}_{j}')
|
|
model.Add(item_vehicle[i] == item_vehicle[j]).OnlyEnforceIf(same_vehicle)
|
|
|
|
# Pour chaque paire de rotations, créer les contraintes de séparation
|
|
for rot_i in range(len(all_rotations[i])):
|
|
for rot_j in range(len(all_rotations[j])):
|
|
l_i, w_i, h_i = all_rotations[i][rot_i]
|
|
l_j, w_j, h_j = all_rotations[j][rot_j]
|
|
|
|
both_rotations = (model.NewBoolVar(f'both_rot_{i}_{rot_i}_{j}_{rot_j}'))
|
|
model.Add(item_rotation[i] == rot_i).OnlyEnforceIf(both_rotations)
|
|
model.Add(item_rotation[j] == rot_j).OnlyEnforceIf(both_rotations)
|
|
|
|
# Si ces rotations, forcer la séparation
|
|
left = model.NewBoolVar(f'{i}_left_{j}_{rot_i}_{rot_j}')
|
|
right = model.NewBoolVar(f'{i}_right_{j}_{rot_i}_{rot_j}')
|
|
behind = model.NewBoolVar(f'{i}_behind_{j}_{rot_i}_{rot_j}')
|
|
front = model.NewBoolVar(f'{i}_front_{j}_{rot_i}_{rot_j}')
|
|
below = model.NewBoolVar(f'{i}_below_{j}_{rot_i}_{rot_j}')
|
|
above = model.NewBoolVar(f'{i}_above_{j}_{rot_i}_{rot_j}')
|
|
|
|
model.Add(item_x[i] + l_i <= item_x[j]).OnlyEnforceIf([left, both_rotations])
|
|
model.Add(item_x[j] + l_j <= item_x[i]).OnlyEnforceIf([right, both_rotations])
|
|
model.Add(item_y[i] + w_i <= item_y[j]).OnlyEnforceIf([behind, both_rotations])
|
|
model.Add(item_y[j] + w_j <= item_y[i]).OnlyEnforceIf([front, both_rotations])
|
|
model.Add(item_z[i] + h_i <= item_z[j]).OnlyEnforceIf([below, both_rotations])
|
|
model.Add(item_z[j] + h_j <= item_z[i]).OnlyEnforceIf([above, both_rotations])
|
|
|
|
# Si même véhicule, au moins une séparation doit être vraie
|
|
model.AddBoolOr([left, right, behind, front, below, above]).OnlyEnforceIf([same_vehicle, both_rotations])
|
|
|
|
# C. Symmetry Breaking
|
|
for v in range(max_vehicles - 1):
|
|
model.Add(vehicle_used[v] >= vehicle_used[v+1])
|
|
model.Add(item_vehicle[0] == 0)
|
|
|
|
# D. Contrainte LIFO
|
|
for i in range(M):
|
|
for j in range(M):
|
|
if i == j:
|
|
continue
|
|
if item_orders[i] != -1 and item_orders[j] != -1 and item_orders[i] < item_orders[j]:
|
|
same_v = model.NewBoolVar(f'same_lifo_{i}_{j}')
|
|
model.Add(item_vehicle[i] == item_vehicle[j]).OnlyEnforceIf(same_v)
|
|
# i doit être devant j (x_i plus grand)
|
|
model.Add(item_x[i] >= item_x[j]).OnlyEnforceIf(same_v)
|
|
|
|
# OBJECTIF
|
|
model.Minimize(sum(vehicle_used))
|
|
|
|
# --- RÉSOLUTION ---
|
|
solver = cp_model.CpSolver()
|
|
solver.parameters.max_time_in_seconds = 20.0
|
|
status = solver.Solve(model)
|
|
|
|
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
|
|
print("SAT")
|
|
for i in range(M):
|
|
v = solver.Value(item_vehicle[i])
|
|
x = solver.Value(item_x[i])
|
|
y = solver.Value(item_y[i])
|
|
z = solver.Value(item_z[i])
|
|
rot_idx = solver.Value(item_rotation[i])
|
|
l, w, h = all_rotations[i][rot_idx]
|
|
print(f"{v} {x} {y} {z} {x+l} {y+w} {z+h}")
|
|
else:
|
|
print("UNSAT")
|
|
|
|
|
|
if __name__ == "__main__":
|
|
solve_ortools()
|