if ORTOOLS_OK:
from ortools.sat.python import cp_model
import matplotlib.pyplot as plt
# ---- Donnees du probleme ----
# 2 drones, 3 livraisons, 4 sites
# Durees de vol entre sites (matrice symetrique, en minutes)
DISTANCES = {
# (from, to): duree
('Depot', 'A'): 5, ('Depot', 'B'): 8, ('Depot', 'C'): 6,
('A', 'B'): 4, ('A', 'C'): 7, ('B', 'C'): 3,
}
def flight_time(frm, to):
"""Retourne la duree de vol entre deux sites (symetrique)."""
if frm == to:
return 0
key = (frm, to) if (frm, to) in DISTANCES else (to, frm)
return DISTANCES[key]
# Livraisons : (ramassage, depot, nom)
DELIVERIES = [
('A', 'B', 'D1'), # Livraison 1 : A -> B (4 min)
('Depot', 'C', 'D2'), # Livraison 2 : Depot -> C (6 min)
('A', 'C', 'D3'), # Livraison 3 : A -> C (7 min)
]
NUM_DRONES = 2
print("Probleme : Livraisons par drones")
print("=" * 50)
print(f"Drones : {NUM_DRONES}")
print(f"Livraisons :")
for pickup, dropoff, name in DELIVERIES:
print(f" {name} : {pickup} -> {dropoff} ({flight_time(pickup, dropoff)} min)")
# ---- Modelisation CP-SAT ----
model = cp_model.CpModel()
horizon = 30 # Borne superieure
# Chaque livraison est une tache : drone va au ramassage puis vole vers le depot
# Pour simplifier : chaque livraison = 1 intervalle (duree = vol ramassage->depot)
# + temps d'acces au point de ramassage depuis la position initiale (Depot)
# Variables : start[i], end[i] pour chaque livraison i, + affectation de drone
# Modelisation propre : intervalles optionnels par drone (un seul drone par livraison,
# NoOverlap sur les intervalles d'un meme drone). C'est l'idiome OR-Tools CP-SAT
# recommande pour l'ordonnancement parallel multi-ressource.
starts = []
ends = []
durations = []
presence = [] # presence[i][d] = 1 si la livraison i est assignee au drone d
optional_by_drone = {d: [] for d in range(NUM_DRONES)}
for i, (pickup, dropoff, name) in enumerate(DELIVERIES):
# Duree totale = vol Depot->ramassage + vol ramassage->depot
access_time = flight_time('Depot', pickup)
delivery_time = flight_time(pickup, dropoff)
total_duration = access_time + delivery_time
durations.append(total_duration)
s = model.NewIntVar(0, horizon, f'start_{name}')
e = model.NewIntVar(0, horizon, f'end_{name}')
starts.append(s)
ends.append(e)
# Un intervalle optionnel par drone ; exactement un drone par livraison
pres = [model.NewBoolVar(f'on_drone_{name}_{d}') for d in range(NUM_DRONES)]
model.AddExactlyOne(pres)
presence.append(pres)
for d in range(NUM_DRONES):
opt = model.NewOptionalIntervalVar(s, total_duration, e, pres[d], f'opt_{name}_{d}')
optional_by_drone[d].append(opt)
# Contrainte : pas de chevauchement sur un meme drone (NoOverlap par drone)
for d in range(NUM_DRONES):
model.AddNoOverlap(optional_by_drone[d])
# Objectif : minimiser le makespan
makespan = model.NewIntVar(0, horizon, 'makespan')
model.AddMaxEquality(makespan, ends)
model.Minimize(makespan)
# Resolution
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
print(f"\n=== Solution {'optimale' if status == cp_model.OPTIMAL else 'faisable'} ===")
print(f"Makespan : {solver.Value(makespan)} min")
print(f"\n{'Livraison':<12} {'Drone':<8} {'Debut':<8} {'Fin':<8} {'Duree':<8}")
print("-" * 44)
for i, (pickup, dropoff, name) in enumerate(DELIVERIES):
s_val = solver.Value(starts[i])
e_val = solver.Value(ends[i])
d_val = next(d for d in range(NUM_DRONES) if solver.Value(presence[i][d]))
print(f"{name:<12} {'D'+str(d_val):<8} {s_val:<8} {e_val:<8} {durations[i]:<8}")
# Visualisation Gantt temporel
fig, ax = plt.subplots(figsize=(10, 4))
drone_colors = ['#3498db', '#e74c3c']
for i, (pickup, dropoff, name) in enumerate(DELIVERIES):
d_val = next(d for d in range(NUM_DRONES) if solver.Value(presence[i][d]))
s_val = solver.Value(starts[i])
ax.barh(f'Drone {d_val}', durations[i], left=s_val,
color=drone_colors[d_val], edgecolor='black', alpha=0.8)
ax.text(s_val + durations[i]/2, f'Drone {d_val}',
f'{name}\n{pickup}->{dropoff}\n({durations[i]}min)',
ha='center', va='center', fontsize=8, color='white', weight='bold')
ax.axvline(x=solver.Value(makespan), color='green', linestyle='--',
linewidth=2, label=f'Makespan = {solver.Value(makespan)} min')
ax.set_xlabel('Temps (minutes)')
ax.set_title('Plan temporel : Livraisons par drones')
ax.legend(loc='upper right')
ax.set_xlim(0, solver.Value(makespan) + 2)
plt.tight_layout()
plt.show()
# Analyse du parallelisme
seq_time = sum(durations)
par_time = solver.Value(makespan)
print(f"\nAnalyse du parallelisme :")
print(f" Temps sequentiel : {seq_time} min")
print(f" Temps parallele : {par_time} min")
print(f" Gain : {seq_time/par_time:.2f}x")
else:
print("Aucune solution trouvee")
