Premier problème : optimisation de collecte le long de voies

Explications méthodes de résolution :
Démonstration :
Retour à démonstrations ORCHIDS :
Retour à page principale ORCHIDS :

PRESENTATION DE PROBLEME DE TOURNEES SUR ARCS

On considère un réseau comportant un dépôt et des arcs comme modélisé sur la figure suivante.

Il s'agit de récolter de la matière dispersée le long des arcs dont on connaît la quantité sur chaque arc.
Lorsque l'on passe sur un arc, on récolte tout ou rien (arc emprunté comme passage pour une autre tournée).
Les camions qui collectent la matière ont une capacité identique connue et ne peuvent récolter plus que leur capacité (notée CAP).
Ils partent du dépôt vide et reviennent au dépôt avec la quantité collectée lors d'une tournée.
On doit organiser les tournées de manière à minimiser la distance totale parcourue tout en respectant la capacité des camions.

Pour simplifier le problème en ce qui concerne les voies à double sens, on suppose qu'ils peuvent être empruntés dans les deux sens lorsqu'ils sont traversés sans collecte, mais que l'on a décidé dans quel sens la collecte est effectué sur ces arcs.
On a donc une liste de secteurs orientés à visiter que l'on numérote 1, 2, ... , NS.

PRETRAITEMENT :

Sans établir les tournées, on commence par utiliser des programmes de calcul de plus courts chemins dans un graphe (problèmes faciles à résoudre) pour obtenir les informations suivantes illustrées dans la figure qui suit.

Ce sont les données d'entrées des démonstrations qui vous sont proposées.

Pour avoir des explications sur la manière de résoudre ce problème ou pour avoir une démonstration, cliquer sur l'un des boutons suivants :

Explications méthodes de résolution :
Démonstration :
Retour à démonstrations ORCHIDS :
Retour à page principale ORCHIDS :