Optimisation de tournées avec contraintes

Bonjour à tous.

Après avoir fait une recherche sur le forum, je ne trouve pas vraiment de réponses à cette question :

Quel type d'algorithme privilégier pour résoudre un problème d'optimisation de tournées, en sachant que j'aurais plusieurs contraintes :

1) Optimisation du temps du trajet (lié à la distance en grande partie)
2) Contraintes horaires de livraison
3) Contraintes de capacité (chaque véhicule comportent plusieurs compartiments de capacités différentes)

Chaque 'client' :
1) précise quel produit il désire et en quelle quantité
2) peut préciser une plage horaire
3) certains véhicule ne peuvent livrer certains clients (véhicules trop imposant)


Ceci est ma première approche de ce type de problème. Pour le moment j'ai fait des essais d'algo de type génétiques et colonies de fourmis sur une résolution basique de type TSP mais je n'ai aucune idée si ce type d'algo peut être adapté quand il y a des contraintes.

J'aimerais, si certains d'entre vous ont des expériences sur ce genre de problèmes, qu'ils m'indiquent vers quel type d'algo me tourner.

Merci par avance.

Cette question relève pour beaucoup du domaine de la recherche. A ma connaissance, de telles heuristiques se débrouillent plutôt bien (on utilise aussi de la recheche tabou ou du recuit). Lorsqu'il y a beaucoup de contraintes tordues, il faut souvent coupler ces méthodes avec de la programmation par contraintes (voir par exemple le produit ILOG Dispatcher).

Pour résoudre ces problèmes de manière exacte, la génération de colonne.

Voir surtout le site
http://osiris.tuwien.ac.at/~wgarn/VehicleRouting/vehicle_routing.html

Merci pour ces pistes de recherche.