Traveling salesman problem (asymétrique et groupé)

[Dlzlogic]

Bonsoir,
Votre exemple est parfait, et il met en évidence exactement ce que je cherchais.
1- Vous partez de VOTRE position, or vous n'êtes pas un élément de l'ensemble.
2- La disposition est en relation avec a) VOTRE position b) l'une des pommes
3- la disposition dépend de 5 éléments (VOTRE position et les 4 pommes)

Donc la première chose à faire est de définir les éléments, appelons-les les villes et les liaisons entre les villes, appelons-les les voies.
Un chemin est un ensemble de voies empruntées successivement.
Tout doit pouvoir se ramener numériquement à une somme de distances parcourue. pour parler en termes plus mathématique à une valeur numérique comparable à une autre valeur numérique.
Cette valeur peut être une distance, un coût, un temps, un nombre représentant une "quantité d'agrément touristique" ou "un pourcentage de sécurité" ou "un coefficient de discrétion (cas d'une évasion)". Dans tous les cas, cette valeur doit avoir une référence et une unité connue et constante.
Donc, je pense qu'avant de réfléchir au moyen de le calculer, il faut fixer, et ça doit être définitif
1- les unités de localisation
2- à partir d'un localisation, le moyen de connaitre les localisations voisines immédiates
3- les différents type de choix de voie possible.

Je tiens à préciser que les termes "ville" et "voie" ne sont là que pour utiliser un vocabulaire sans ambiguité. De la même façon que la "valeur" de comparaison est comparable à une distance, mais ce n'est que pour employer des termes simples.
Je veux simplement dire qu'il y a des "ponts" des "arcs" entre ces points et que les arcs ont des caractéristiques. Les points eux-même peuvent très bien ne pas correspondre à des lieux, les arcs peuvent très bien ne pas correspondre à des liaisons.

[TheReveller]

Je tiens à préciser que je vais générer tous les temps des déplacements possibles.

J'aurai, par exemple, pour 300 lieux ayant chacun 16 dispositions, généré les (300^2 - 300) * 16^2 = 22 963 200 différents déplacements possibles ainsi que leur coût en temps.

Il me restera tout simplement à optimiser la boucle de parcours à choisir (l'ordre pour la visite des lieux en tenant compte des dispositions).

[Dlzlogic]

Je tiens à préciser que je vais générer tous les temps des déplacements possibles.

J'aurai, par exemple, pour 300 lieux ayant chacun 16 dispositions, généré les (300^2 - 300) * 16^2 = 22 963 200 différents déplacements possibles ainsi que leur coût en temps.

Il me restera tout simplement à optimiser la boucle de parcours à choisir (l'ordre pour la visite des lieux en tenant compte des dispositions).

Oui, tout à fait d'accord, mais chacun leur tour.
Le bon choix au point Pi est indépendant du bon choix au point Pk.
Je vous conseille vraiment de bien définir votre problème avant de chercher la solution et à fortiori de la fixer.
Par exemple faites un schéma avec une dizaine de lieux, vous verrez qu'on peut les étudier de façon relativement indépendante.
22 millions de déplacements, c'est ingérable, surtout avec un programme interprété.

[Aquemy]

Bonsoir,

Je n'ai pas eu le courage de lire l'ensemble du sujet donc je vais peut-être radoter.
Aujourd'hui les méthodes en vogues pour la résolution de TSP a grande échelle et sous contraintes, ce sont les méta-heuristiques et plus généralement les algorithmes génétiques.

Vous trouverez beaucoup de documentation sur le sujet un peu partout sur internet dans la littérature.

Je ne peux que conseiller l'utilisation du framework ParadisEO pour le calcul sur des volumes de données conséquents. Voici par ailleurs un article sur une manière de résoudre le TSP en utilisant ParadisEO : http://paradiseo.gforge.inria.fr/index.php?n=Problems.TSP

En espérant que cela vous aide.