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

Présentation du problème :
Démonstration :
Retour à démonstrations ORCHIDS :
Retour à page principale ORCHIDS :

RESOLUTION DU PROBLEME DE TOURNEES SUR ARCS

Grâce au pré-traitement (calculs de plus courts chemins dans un graphe) on connaît :

ainsi que la capacité des camions CAP et le nombre de secteurs NS.

La solution de ce problème peut être décomposée en deux parties
(en supposant qu'un seul camion fera successivement toutes les tournées,
il suffira ensuite de distribuer les camions aux tournées si on a plusieurs camions) :
- dans quel ordre le camion visite les secteurs ?
- quand le camion retourne-t-il au dépôt entre la visite de deux secteurs ?
c'est-à-dire le découpage d'un grand tour
qui visite successivement tous les secteurs dans l'ordre choisi
en sous-tours correspondant chacun à une tournée.

Si vous allez sur le site de démonstration
et que vous choisissez le mode de
démonstration manuelle,
c'est vous qui choisirez dans quel ordre visiter les secteurs
en entrant les numéros de secteurs dans l'ordre où vous voulez les visiter
(une seule fois chaque numéro entre 1 et NS)
et en mettant des "*" lorsque vous souhaitez retourner au dépôt
après la visite d'un secteur.
Le démonstrateur vous représente alors la solution que vous avez choisie
en vous donnant la distance totale parcourue et en vous signalant
toutes les tournées que vous avez proposées et qui ne respectent pas
la capacité maximale du camion.

Si on sait dans quel ordre on visite les secteurs,
alors on peut utiliser une approche de programmation dynamique
pour optimiser la distance parcourue.

Si vous êtes intéressé par la description
de cette approche par programmation dynamique,
cliquer sur le bouton .

Si vous allez sur le site de démonstration
et que vous choisissez le mode de
démonstration semi-automatique,
c'est encore vous qui choisirez dans quel ordre visiter les secteurs
en entrant les numéros de secteurs dans l'ordre où vous voulez les visiter
(une seule fois chaque numéro entre 1 et NS)
mais c'est le démonstrateur qui utilisera la programmation dynamique
pour découper le grand tour en plusieurs tournées de manière à minimiser
la distance totale parcourue tout en respectant la capacité du camion.

Si on ne sait pas dans quel ordre les secteurs doivent être visités,
alors il faut explorer les ordres possibles de visite des secteurs afin
de trouver un des ordres qui donne la plus petite distance parcourue totale.

Malheureusement, il y a NS! ordres possibles (1x2x3x...xNS)
et si NS est grand, il n'est pas possible de visiter tous les ordres possibles
et, pour ce problème, on ne sait pas comment se limiter à des sous-ensembles
plus petits de solutions qui contiendraient les meilleures solutions.
Il faut donc essayer d'explorer le mieux possible une partie des ordres possibles
et retenir la meilleure solution trouvée.

Si vous allez sur le site de démonstration ,
si vous choisissez, parmi les exemples proposés par le menu déroulant,
un exemple comportant au plus 6 secteurs
et si vous choisissez le mode de
démonstration automatique,
alors vous n'avez plus rien à choisir,
le démonstrateur construit les NS! ordres possibles (720 pour NS=6),
pour chaque ordre il appelle la programmation dynamique
pour trouver le découpage optimale en tournée
et il retient les solutions optimales.
Vous constaterez que vous devez attendre un peu avant d'avoir les résultats.
Le démonstrateur vous fournit la liste de tous les ordres optimaux
et vous illustre en détail une des solutions optimales.

Si vous allez sur le site de démonstration ,
si vous choisissez, parmi les exemples proposés par le menu déroulant,
un exemple comportant plus de 7 secteurs
et si vous choisissez le mode de
démonstration automatique,
alors on vous demande de choisir des paramètres
permettant au démonstrateur
de dérouler un algorithme génétique.

Si vous êtes intéressé par la description
de l'approche par algorithme génétique
pour visiter un ensemble d'ordres (appelés aussi
permutations), cliquer sur le bouton .

En ce qui concerne la suite de la démonstration,
le démonstrateur vous demande de fournir pour l'algorithme génétique
la taille de la population et le nombre de génération.
Ensuite il visite les ordres en utilisant de manière aléatoire
chacun des quatre croisements et chacune des quatre mutations
avec une probabilité de croisement et une probabilité de mutation
choisies par le démonstrateur et
pour chaque ordre il appelle la programmation dynamique
pour trouver le découpage optimale en tournée
et il retient la meilleure des solutions trouvées.
Selon les valeurs plus ou moins grandes choisies pour
la taille de la population et le nombre de générations,
v ous constaterez que vous devez attendre plus ou moins longtemps
avant d'avoir les résultats.
Le démonstrateur vous fournit une des meilleures solutions qu'il a trouvé
avec les détails correspondant.

Présentation du problème :
Démonstration :
Retour à démonstrations ORCHIDS :
Retour à page principale ORCHIDS :