Traveling salesman problem (asymétrique et groupé)

[TheReveller]

Bonjour,

J'aimerais optimiser un cas spécifique du TSP et j'aimerais savoir si par hasard quelqu'un aurait des détails (articles, pages web) que je pourrais consulter à ce sujet.

Mon problème consiste à visiter plusieurs "lieux" une seule fois selon une boucle optimale. Cependant, on peut aller à ces "lieux" selon plusieurs "dispositions" différentes possibles. De plus, la matrice n'est pas symétrique. Aller du "lieu" 1 selon la "disposition" 1 vers le "lieu" 2 selon la "disposition" 2 ne prend pas nécessairement le même temps que le chemin inverse.

J'ai donc des "lieux" 1 à n qui comportent des "dispositions" 1 à m et je veux optimiser l'ordre pour visiter les n "lieux" et connaître quelle "disposition" a été utilisée pour chaque "lieu" afin de rendre la visite des n "lieux" optimale.

Je compte utiliser une matrice et des algorithmes génétiques.

Exemple de solution avec les "lieux" A, B, C, D, E et les "dispositions" 1, 2, 3, 4, 5, 6, 7 :

A1 à D3, D3 à B1, B1 à E1, E1 à C7, C7 à A1

Exemple de solution erronée avec les "lieux" A, B, C, D, E et les "dispositions" 1, 2, 3, 4, 5, 6, 7 :

C1 à D2, D3 à B1, B1 à E6, E2 à A1, A1 à C3

Merci.

[C.Ret]

Bonjour,

Si je comprends bien "disposition" signifie surtout "sens de circulation", le coût du déplacment e A vers B n'est pas le même que de B vers A.

Utiliser une matrice pour représenter les "coûts" de déplacement est une bonne idée.

Celle consistant à utiliser un algorithme génétique ne l'ai peut-être pas autant, tout du moins selon moi, je préfère une approche heuristique. Mais c'est une question de goût. Je fais beaucoup de génétique dans les labos de biologie, beaucoup moins dans dans les salles d'informatique.

Par contre, je n'ai rien compris aux "dispositions" des points donné en exemple:
Pourquoi ne pas représenter l'exemple sous la forme d'une matrice (d'un tableau quoi):

Code: Tout sélectionner

  A B C D E 
A - ? 1 3 ?
B ? - ? 1 1
C 7 ? - ? 7
D 3 3 ? - ?
E ? 1 1 ? -


Clairement, il manque les coûts pour un grand nombre de combinaisons ?

A moins que les coûts ("dispositions") ne soient liés à chaque point de passage. Dans ce cas, je suis désolé, mias je ne comprend pas en quoi cela va influencer sur l'optimisation puis que l'on devra passer par tous les point ??? :hum: :hum:

[Dlzlogic]

Bonjour,
En lisant la question, j'ai tout de suite pesé au problème bien connu de trajet, il est connu aussi sous le nom de "voyageur de commerce".
C'est un problème très intéressant, et à mon avis le seule méthode possible est l'utilisation des graphes.
Dans votre exemple, il y a 5 points, dans la pratique, il y en aura probablement plusieurs centaine, ce qui fait que l'utilisation d'un tableau carré me semble à exclure.
Mais il est fort possible que j'ai mal compris la question, l'élément "disposition" n'entre pas dans ce contexte.

[fatal_error]

bjr,

alors déjà la matrice aue représente Cret est censée etre une matrice de couts, or les 1 3 et 7 sont pas des couts mais des dispositions.

Si on devait la représenter ca serait plus un truc genre
A1 A2 A3...B1 B2
A1 xx xx xx...10 10
A2 xxxxxxxx 12 14
A3 etc
qui dit: d'un noeud A peut importe la disposition, on va vers un autre noeud (xx signifie interdit)

l'idée consiste à poser xx == l'infini, comme ca t'es sur que le chemin optimal, ca passera pas par une relation qui vaut xx.

"voyageur de commerce"

c'est le TSP en anglais.

ce qui fait que l'utilisation d'un tableau carré me semble à exclure.

nan ca va. L'exploration complète est délicate (en PLNE, 16 ca va après bof), mais ya des furieux qui ont fait d'excellents résultats jusqu'à 2000 villes en une ptite minute à peu près (du moins sur ma bécane)

[Dlzlogic]

Bon, j'ai pas tout compris ce que tu m'as dit, mais en ce qui concerne la recherche du meilleur trajet d'un point à un autre, j'ai un module qui résout le problème. Par "meilleur" il faut tenir compte de ce qui a été précisé, plus court, plus rapide, plus joli, moins contrôlé etc.
J'ai essayé de répondre à notre ami, pour l'aider, il n'est pas sûr que les remarques linguistes soient très constructives.
Concernant la capacité des machines, je suis de la vieille école, alors plutôt que d'utiliser un tableau carré presque vide, à mon avis, il vaut mieux utiliser une structure chainée.
Je suppose qu'on en reparlera demain. :dodo:

[C.Ret]

Effectivement, je n'ai pas compris ce que vous appelez une "disposition".

C'est en fait l'indice d'une disposition, un indicateur qui donne indique comment le noeud est "disposé" ?

J'ai du mal à comprendre de quoi il s'agit.

Effectivement, cela ne corrspond pas à ma matrice des coûts qui d'ailleurs peut aussi servir à indiquer les liaisons impossibles. Par exemple en les indiquant aussi par xx ou par
Mais, il m'est aussi arrivé de coder des laisons impossibles par des 0 comme dans les matrices d'incidence.
On peux aussi coder le TSP à partir de matrice d'adjacence ...
En fait tout est une question de codage et de disposition.

Ah ! Zut ! J'utilise le mot "disposition" dans un sens différent de celui que vous lui donné.


@DlzLogic c'est la seconde fois aujourd'hui que nos interventions concernent un problème de vocabulaire et de champ lexical.
C'est un peu chronique sur ce forum, les terme et dénomination sont raremetn clairement défnie par leurs utilisateurs.
Difficile de communiquer si les interlocuteurs ne font pas l'effort de se rendre compréhensibles...

[fatal_error]

J'ai du mal à comprendre de quoi il s'agit.

pour ma part, je l'ai compris comme une autoroute.
Tu as un noeud A.
Pour te rendre à B, tu as 7 autoroutes possibles.
Ai->Bj
une fois arrivé à Bj, tu choisis un nouvel autoroute qui détermine le trajet Bi->Ck

ca ressemble à des réseaux de neurones ou un chemin ville-ville fait la liaison entre deux layers.

[fatal_error]

j'aimerais egalement ajouter de quoi dependent les dispositions.
de la ville courante?
du chemin fait jusqu a cette ville?

[Dlzlogic]

Bonjour,
Je pense que TheReveller devrait nous préciser le contexte de sa question.
Le problème du voyageur de commerce peut se poser de deux façon différentes.
1- le plus simple : il est chez-lui, regarde son agenda et se rend chez son premier client. Ensuite, il regarde de nouveau son agenda ou reçoit un coup de téléphone et se rend chez le client suivant.
2- le plus élaboré : avant de partir, il indique à sa machine la liste des clients qu'il doit rencontrer, et celle-ci lui indique les parcours à suivre entre chaque client et naturellement l'ordre des visites.

Je ne suis pas sûr que l'étape 2 ait été vraiment réalisée dans la pratique.
Je pense qu'il faudrait organiser les choses de la façon suivante :
Chaque ville est caractérisée par son nom, sa position géographique (X,Y) et la liste des villes où l'on accède directement sans passer par une autre ville. Cette liste a en général une longueur de 3 ou 4 et ne devrait pas dépasser 6. Il est logique d'avoir, en parallèle à cette liste de ville (leur nom) un liste décrivant l'état de la route.
Chaque ville est un noeud, l'information sur l'arc est contenue dans la liste de descriptions. Ceci constitue une structure parfaitement définie. Informatiquement, en C, ce sera un pointeur.

[TheReveller]

Bonjour,

J'ai vu qu'il y avait beaucoup de réponses. Je n'ai malheureusement pas eu le temps de tout lire, mais j'ai cru comprendre l'ambiguïté. Je m'en doutais.

Voici un petit schéma (désolé, je n'ai pas de logiciel autre que PowerPoint) :



Dans ce schéma, il y a les lieux L1 à L3 qui comportent chacun les dispositions D1 à D3. Chacune des disposition comporte des liens possibles avec toutes les dispositions des autres lieux et chaque lien a en fait deux possibilités de temps selon le sens de visite.

Autrement dit, le lien qui unit L1D1 à L2D3 a un temps différent dépendament si le parcours est L1D1 vers L2D3 ou L2D3 vers L1D1.

En vert, un exemple de solution. Je viens de penser que je n'ai pas fait de flèches, mais supposons que la solution est L1D2 vers L3D2 vers L2D1 (vers L1D2) [Ce qui est différent de L1D2 vers L2D1 vers L3D2 (vers L1D2)]

N'hésitez pas à me le dire encore si ce n'est pas clair.

Merci.

[C.Ret]

Merci, c'est bien plus clair comme cela.

Donc, ce que l'on cherche à optimiser, c'est le temps mis pour faire le tour complet des lieux. Entre chaque lieu, il faut donc que le système choisisse quelle disposition il va utiliser car évidement elle en sont pas équivalente en temps. De même, l'ordre de viste des lieu a de l'importance, car le temps dépend du sens.

Quelque question cependant :
Q1: Le tour ne doit passer qu'une seule fois par chaque lieu, un nombre imorant de disposition ne seront pas donc pas utilisées?

Q2: Pourquoi tenir compte des dispositions et rendre le problème plus complexe, est-ce que le tour n'utilisant que les dispositions les plus rapides n'est pas sytématiquement la meilleure solution ?

En ramène le problème à un TSP classique assymétrique où l'on ne renseinge en chaque lieu que les dispositions (une entrante et une sortante) les plus efficace (les plus rapides)

Voilà, voilà... pour le moment les interrogations sur ce problème.

[TheReveller]

Dans l'exemple, j'ai mis 3 lieux et 3 dispositions, mais l'optimisation à faire peu comporter des centaines de lieux ayant chacune 16 dispositions possibles par exemple.

Pour la question 1 :

On visite tous les lieux et ce qu'une seule fois, donc pour chaque lieu il faut choisir la disposition optimale pour s'y rendre.

Pour la question 2 :

Je ne suis pas certain de bien comprendre, mais il se peut par exemple que L1D2 vers L3D2 prenne plus de temps que L1D2 vers L3D1, mais qu'à partir de L3D1, se rendre à un prochain lieu soit très coûteux en temps à cause de la disposition choisie. Il faut donc faire un agencement optimal.

[C.Ret]

Je ne suis pas certain de bien comprendre, mais il se peut par exemple que L1D2 vers L3D2 prenne plus de temps que L1D2 vers L3D1, mais qu'à partir de L3D1, se rendre à un prochain lieu soit très coûteux en temps à cause de la disposition choisie. Il faut donc faire un agencement optimal.

Autant pour moi, je ne n'avais pas compris que l'on entrait et sortait de chaque lieu par la même disposition.
J'était partie sur l'idée, fausse dans votre cas, qu'une fois arrivé au lieux L, je pouvais repartir vers le lieu suivant par le dispositf de mon choix.

Donc, effectivement, si l'on ne peut pas changer de disposition, il faut effectivement donner les temps (dans les deux sens) pour chaque disposition et chaque lieu.


Le fait qu'il y ai des centaines de lieux qui ont jusqu'à 16 dispositions, cela multiplie considérablement la taille de la matrice représentant le système. Il va falloir utiliser un algorithme capable de trouver un chemin efficace sur plusieurs milliers de nodes.
A priori, pas évident !

[TheReveller]

En fait, je sais déjà que je vais utiliser les algorithmes génétiques, mais je cherchais à savoir si quelqu'un connaissait déjà ce cas spécifique du TSP et aurait de l'information quant à l'approche utilisée ou une façon de représenter le problème ou la matrice de distances et comment imposer les contraintes.

Voici un exemple typique du TSP classique optimisé grâce aux algorithmes génétiques : http://www.mathworks.com/matlabcentral/fileexchange/13680

Je n'ai pas validé la technique employée pour l'application des algorithmes génétiques, mais le principe y est.

Merci.

[fatal_error]

je t'ai déjà représenté la matrice de distance.

Les points concernés sont la fitness (généralement la distance du chemin)
La sélection (généralement les plus courts):
- eventuellement considérer ceux qui n'ont pas des chemins qui se croisent (ex pour 4 villes consécutives, ca dessine un quadrilatère croisé (c'est pas bon (2-opt)). Mais de toute façon comme ils sont pas bons ils seront éliminés tot ou tard.

le cross over:
- on peut pour deux chemins v1 et v2: prendre la première partie de v1 et concaténer avec la seconde de v2 (pour la ville qui manquent)
jme rappele pas des autres mais celui la est merdique.

la mutation:
- permuter deux villes n'importe comment (pas tres convainquant)

[C.Ret]

Je suis du même avis que fatal_error surtout en ce qui concerne l'organisation des donnée dans une matrice des coûts (ici donc des temps) en utilisant une valeur spéciale \infty ou autre pour marquer les liaison indisponible.


Pour fixer les idée, voici à quoi ressemblerait la matrice (évidemment la matrice réelle aura quelque centaine de lieu qui peuvent avoir jusqu'à 16 "disposition"

Code: Tout sélectionner

µs  A A A A A  B B B B  C C C C C C   D D D D     
    1 2 3 4 5  1 2 3 4  1 2 3 4 5 6   1 2 3 4

A1  \ \ \ \ \  2 1 0 #  2 4 5 7 1 3   7 6 3 #
A2  \ \ \ \ \  3 4 5 #  3 2 3 4 5 3   2 3 1 #
A3  \ \ \ \ \  # 6 2 #  8 4 0 1 2 #   # # # #
A4  \ \ \ \ \  # 4 5 2  6 3 4 9 3 3   # 3 2 5
A5  \ \ \ \ \  # 5 2 3  2 3 4 2 9 3   # 2 8 3

B1  2 3 # # #  \ \ \ \  2 1 0 3 2 2   7 6 3 #
B2  2 3 9 2 3  \ \ \ \  3 4 5 3 3 3   2 3 1 #
B3  3 2 2 3 3  \ \ \ \  3 6 2 3 2 8   2 3 4 #
B4  # # # 1 0  \ \ \ \  6 3 4 9 3 3   2 3 2 #

C1  ...
C2  ...
C3  ...

   \  = coût null
   #  = marqueur liaison impossible


C'est bien la structue proposée ci-dessus par fatal_error !



Je reste malgré tout peu convaincu qu'un algorithme génétique soit le plus approprié dans ce cas.

Si je me souviens bien, le principe de la méthode "génétique" est de faire un peu comme fait mère nature avec notre génôme. A partir de deux gènes (ici des tours valides est suffisament acceptables), un enfant est créé en prenant deux parties complèmentaires des gènes (tours) parents auquel on mute une petite fraction aléatoirement.

Si on se contente d'un seul gène (une suel tours que l'on cherche à optimiser) , se que certaines auteurs appèlent encore "algorithme génétique" est un fait surtout une méthode de "recuit simulé" où l'on modifie aléatoirement une partie plus ou moins importante du "tour" en fonction d'une température que l'on contrôle dynamiquement et que l'on fait refroidr afin de donner une chance au "tour" de se "détendre" après une "quazi-fusion" et espérer ainsi avoir un résultat proche de l'optimum.

Ces deux méthodes ne me semblent pas adaptées au cas présent, car elles supposent toute les deux une intervention aléatoire (soit les variations aléatoire dépendant de la température de recuit, soit la position aléatoire des cross-over des mutations du gène de chaque enfant).

Or, le souci principal que je vois à notre cas avec des "dispositions" fixe est qu'il faudra modifier ces deux algorithmes afin que les "modifications" aléatoires ne n'utilise pas des "dispositions" d'un même point. Ce qui va en quelqeu sorte complexifier l'algorithme de base et risque fort de mettre à mal la convergence de ces méthodes qui ne fonctionnent pas si les "mutation" ou le "recuit" n'est pas aléatoire.

Donc, quitte à modifier l'algorithme d'un TSP standard, je préfère les méthode heuristique et surtout les méthode 2-Opt, 3-Opt ou a-Opt qui sont basée sur les interversions de node et la création de dynamique de partitions des "tours" en sélectionnat à chaque étape les bons points de passages.
Ici, ces points de pasage sont précisément les "dispositions" des lieu successifs. Il sera donc plus facile de ne pas sélectionner des "dispositions" invalides.

En effet, contrairement à un TSP standard, ici, il faut passer par chaque lieu une seule fois et un grand nombre de lignes ou de colonnes de la matrice décrivant le système sont "invalde" à chaque pas itération de la recherhce (quelqeu soit la méthode de recherche employée).
Utiliser une méthode de recherche en relation avec le codage des donnée et la structure va donc naturellement aider à faire moins de calcul "inutile". Par exemple, en évitant d'utiliser la valeur "infinie" qui, même si la solution est valide, va nécessairemtn occasionner un nombre non négligeable de calculs. Calculs qui, surtout sur les méthodes génétique, recuit ou réseaux de neuronne, risque fort d'être important avant de rejeter la tentative.
Alors qu'un simple test, ou une prospection algorithmique adaptée de la structure sera certainement plus efficace et rapide (limité un un test par exemple).

D'où mes craintes et ma préfèrance pour des méthodes heuristique, maté-heuristique ou a-Opt. En tout cas une méthode basée sur le choix contrôlé des poitns de passage (et donc ici des dispositions).

Mais bon, il y a longtemps que je n'ai plus eut à traiter ce type de problème, et les progrés et la puissance de calcul des systèmes actuels justifie peut être aujourd'hui une approche moins rationelle et moins économe ?

[TheReveller]

En fait, c'est le début de mon projet et je dois réactiver un peu mon cerveau puisque j'étais en stage et je ne pensais plus à l'école, et là c'est mon dernier trimestre !

Bref, je réfléchis à voix haute en ce moment.

Première chose, je crois que mon superviseur aimerait bien que l'optimisation s'effectue à l'aide d'un algorithme génétique, mais si vous avez d'autres propositions qui me conviendraient, je pourrais en discuter. Il y aurait aussi par exemple l'Ant Colony Optimization (ACO).

Deuxième chose, peut-être que je me complexifie la vie en ce moment en plus d'avoir un peu de mal à expliquer le principe à optimiser sans trop entrer dans les détails.

Je crois en fait que tout ce que j'aurais à faire serait de générer une permutation des lieux et associer à chaque lieu une disposition aléatoire et alors toutes les contraintes dont je parlais sont nécessairement respectées...

Par exemple, avec 5 lieux et 6 dispositions, je génère aléatoirement l'ordre de visite comme étant la permutation L4-L2-L5-L1-L3, ensuite je génère aléatoirement des dispositions pour chaque lieu, par exemple : L4D1-L2D3-L5D3-L1D6-L3D4. Et voilà, c'est tout bête, je viens de générer la solution potentielle L4D1 vers L2D3, L2D3 vers L5D3, L5D3 vers L1D6, L1D6 vers L3D4 (et L3D4 vers L4D1). Maintenant, je l'évalue selon la matrice des distances. Selon l'approche des algorithmes génétiques, j'aurais généré aléatoirement une population de solutions de ce genre, ensuite j'évalue les solutions pour trouver les meilleures et il ne reste qu'à appliquer des opérations de croisement et de mutation sur les meilleures candidats. Bon, dans mon cas, je me dis qu'une mutation importante à effectuer serait de changer uniquement la disposition d'un (ou plusieurs) lieux. Ensuite, il reste à voir comment appliquer les croisements et les mutations de base.

Je sais que ça parrait moins évidant la justification de l'algorithme génétique pour ce cas (contrairement au ACO qui est très facile à visualiser), mais pourtant l'algorithme génétique proposé sur le site de MATLAB par Joseph Kirk m'a apparu très efficace. Comme je dis, je n'ai pas encore analysé son approche, mais d'un premier coup d'oeil, il ne semble pas faire de croisements, mais plutôt différentes mutations.

Voici son code, si jamais vous connaissez un peu MATLAB, sinon c'est tout de même assez simple à comprendre.

Par Joseph Kirk http://www.mathworks.com/matlabcentral/fileexchange/13680 :

Code: Tout sélectionner

%TSP_GA Traveling Salesman Problem (TSP) Genetic Algorithm (GA)
%   Finds a (near) optimal solution to the TSP by setting up a GA to search
%   for the shortest route (least distance for the salesman to travel to
%   each city exactly once and return to the starting city)
%
% Summary:
%     1. A single salesman travels to each of the cities and completes the
%        route by returning to the city he started from
%     2. Each city is visited by the salesman exactly once
%
% Input:
%     XY (float) is an Nx2 matrix of city locations, where N is the number of cities
%     DMAT (float) is an NxN matrix of point to point distances/costs
%     POPSIZE (scalar integer) is the size of the population (should be divisible by 4)
%     NUMITER (scalar integer) is the number of desired iterations for the algorithm to run
%     SHOWPROG (scalar logical) shows the GA progress if true
%     SHOWRESULT (scalar logical) shows the GA results if true
%
% Output:
%     OPTROUTE (integer array) is the best route found by the algorithm
%     MINDIST (scalar float) is the cost of the best route
%
% Example:
%     n = 50;
%     xy = 10*rand(n,2);
%     popSize = 60;
%     numIter = 1e4;
%     showProg = 1;
%     showResult = 1;
%     a = meshgrid(1:n);
%     dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),n,n);
%     [optRoute,minDist] = tsp_ga(xy,dmat,popSize,numIter,showProg,showResult);
%
% Example:
%     n = 100;
%     phi = (sqrt(5)-1)/2;
%     theta = 2*pi*phi*(0:n-1);
%     rho = (1:n).^phi;
%     [x,y] = pol2cart(theta(:),rho(:));
%     xy = 10*([x y]-min([x;y]))/(max([x;y])-min([x;y]));
%     popSize = 60;
%     numIter = 2e4;
%     a = meshgrid(1:n);
%     dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),n,n);
%     [optRoute,minDist] = tsp_ga(xy,dmat,popSize,numIter,1,1);
%
% Example:
%     n = 50;
%     xyz = 10*rand(n,3);
%     popSize = 60;
%     numIter = 1e4;
%     showProg = 1;
%     showResult = 1;
%     a = meshgrid(1:n);
%     dmat = reshape(sqrt(sum((xyz(a,:)-xyz(a',:)).^2,2)),n,n);
%     [optRoute,minDist] = tsp_ga(xyz,dmat,popSize,numIter,showProg,showResult);
%
% See also: mtsp_ga, tsp_nn, tspo_ga, tspof_ga, tspofs_ga, distmat
%
% Author: Joseph Kirk
% Email: jdkirk630@gmail.com
% Release: 2.3
% Release Date: 11/07/11
function varargout = tsp_ga(xy,dmat,popSize,numIter,showProg,showResult)

% Process Inputs and Initialize Defaults
nargs = 6;
for k = nargin:nargs-1
    switch k
        case 0
            xy = 10*rand(50,2);
        case 1
            N = size(xy,1);
            a = meshgrid(1:N);
            dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),N,N);
        case 2
            popSize = 100;
        case 3
            numIter = 1e4;
        case 4
            showProg = 1;
        case 5
            showResult = 1;
        otherwise
    end
end

% Verify Inputs
[N,dims] = size(xy);
[nr,nc] = size(dmat);
if N ~= nr || N ~= nc
    error('Invalid XY or DMAT inputs!')
end
n = N;

% Sanity Checks
popSize = 4*ceil(popSize/4);
numIter = max(1,round(real(numIter(1))));
showProg = logical(showProg(1));
showResult = logical(showResult(1));

% Initialize the Population
pop = zeros(popSize,n);
pop(1,:) = (1:n);
for k = 2:popSize
    pop(k,:) = randperm(n);
end

% Run the GA
globalMin = Inf;
totalDist = zeros(1,popSize);
distHistory = zeros(1,numIter);
tmpPop = zeros(4,n);
newPop = zeros(popSize,n);
if showProg
    pfig = figure('Name','TSP_GA | Current Best Solution','Numbertitle','off');
end
for iter = 1:numIter
    % Evaluate Each Population Member (Calculate Total Distance)
    for p = 1:popSize
        d = dmat(pop(p,n),pop(p,1)); % Closed Path
        for k = 2:n
            d = d + dmat(pop(p,k-1),pop(p,k));
        end
        totalDist(p) = d;
    end

    % Find the Best Route in the Population
    [minDist,index] = min(totalDist);
    distHistory(iter) = minDist;
    if minDist  2, plot3(xy(rte,1),xy(rte,2),xy(rte,3),'r.-');
            else plot(xy(rte,1),xy(rte,2),'r.-'); end
            title(sprintf('Total Distance = %1.4f, Iteration = %d',minDist,iter));
        end
    end

    % Genetic Algorithm Operators
    randomOrder = randperm(popSize);
    for p = 4:4:popSize
        rtes = pop(randomOrder(p-3:p),:);
        dists = totalDist(randomOrder(p-3:p));
        [ignore,idx] = min(dists); %#ok
        bestOf4Route = rtes(idx,:);
        routeInsertionPoints = sort(ceil(n*rand(1,2)));
        I = routeInsertionPoints(1);
        J = routeInsertionPoints(2);
        for k = 1:4 % Mutate the Best to get Three New Routes
            tmpPop(k,:) = bestOf4Route;
            switch k
                case 2 % Flip
                    tmpPop(k,I:J) = tmpPop(k,J:-1:I);
                case 3 % Swap
                    tmpPop(k,[I J]) = tmpPop(k,[J I]);
                case 4 % Slide
                    tmpPop(k,I:J) = tmpPop(k,[I+1:J I]);
                otherwise % Do Nothing
            end
        end
        newPop(p-3:p,:) = tmpPop;
    end
    pop = newPop;
end

if showResult
    % Plots the GA Results
    figure('Name','TSP_GA | Results','Numbertitle','off');
    subplot(2,2,1);
    pclr = ~get(0,'DefaultAxesColor');
    if dims > 2, plot3(xy(:,1),xy(:,2),xy(:,3),'.','Color',pclr);
    else plot(xy(:,1),xy(:,2),'.','Color',pclr); end
    title('City Locations');
    subplot(2,2,2);
    imagesc(dmat(optRoute,optRoute));
    title('Distance Matrix');
    subplot(2,2,3);
    rte = optRoute([1:n 1]);
    if dims > 2, plot3(xy(rte,1),xy(rte,2),xy(rte,3),'r.-');
    else plot(xy(rte,1),xy(rte,2),'r.-'); end
    title(sprintf('Total Distance = %1.4f',minDist));
    subplot(2,2,4);
    plot(distHistory,'b','LineWidth',2);
    title('Best Solution History');
    set(gca,'XLim',[0 numIter+1],'YLim',[0 1.1*max([1 distHistory])]);
end

% Return Outputs
if nargout
    varargout{1} = optRoute;
    varargout{2} = minDist;
end


[Dlzlogic]

Un point que je n'avais pas compris, c'est que vous vouliez passer par tous les points.
Donc, les trajets possibles ne sont a priori pas connus (oui - non ?)
Si c'est oui, alors une technique qui pourrait être utile, c'est la triangulation de Delaunay. C'est un peu long pour le premier calcul, mais ensuite, à l'utilisation, c'est très efficace. Avec derrière une organisation de graphe.
Il est bien évident que personnellement, j'exclue la solution de tableau énorme pratiquement vide.

[Dlzlogic]

Bonjour,
J'ai toujours un peu de mal à "visualiser" en quoi consiste la "disposition".
Tout d'abord, cette disposition est rattachée à un élément de L, indépendamment de tous les autres lieux, ou au contraire est rattaché à la liaison entre deux lieux Li et Lj .
Je cherche une comparaison à cela.
Soit un certain nombre de villes, on veut se rendre de l'une à l'autre. Il y a deux cas possibles :
Soit chaque ville dispose d'une gare, exemple garage à vélos, location de voiture, gare Sncf, aéroport etc. plusieurs gares pouvant coexister.
Soit la route entre une ville et une autre est un chemin de terre : seuls des vélos peuvent passer, soit une route départementale, vélos et voitures peuvent passer, soit un autoroute, vélo interdit etc.

Autre question que je me pose : quelle est l'unité de travail
Soit la ville L avec ses différentes dispositions, en ce cas, comment identifier les liaisons avec les autres villes ?
Soit la ville L avec les différentes liaisons possibles avec les villes voisines, en ce cas, que représentent les dispositions ?

[TheReveller]

Mon exemple est peut-être complètement absurde et tiré par les cheveux, mais bon.

Disons qu'il y a une pomme devant moi (L1), une pomme à ma gauche (L2), une pomme à ma droite (L3) et une pomme derrière moi (L4). Moi, je suis présentement debout face à une pomme, au centre des quatre pommes. Je veux aller prendre ces quatre pommes (lieux) aussi rapidement que possible avec ma main droite. J'ai plusieurs façons (dispositions) pour prendre les pommes : je peux être face à la pomme et la prendre (D1); je peux être à droite de la pomme, tourner légèrement le tronc vers la gauche et aller prendre la pomme à ma gauche (D2); je peux être à gauche de la pomme et prendre la pomme à ma droite (D3); la pomme peut être derrière moi, alors je tourne le tronc de 90 degrés et je prends la pomme (D4).

Comme je procède pour que ce soit optimal ?

L1D1-L2D2-L3D3-L4D4 ? (Autrement dit, mes pieds n'ont pas à bouger)
L1D1-L2D1-L3D1-L4D1 ? (Autrement dit, mes pieds ont à bouger pour me mettre face à la pomme à chaque fois)
L1D1-L3D3-L4D4-L2D1 ? (Autrement, je ne bouge pas pour aller chercher les pommes devant moi, à ma droite et derrière moi, puis je me mets face à celle à ma gauche pour la prendre)
L1D1-L3D3-L4D1-L2D3 ? (Autrement dit, je prends celle devant moi et celle à ma droite, puis je me mets face à celle qui était derrière moi pour la prendre et je prends celle qui était initialement à ma gauche qui est maintenant à ma droite)

On voit alors que le choix de la disposition est important. Si je veux prendre la pomme à ma droite en me mettant face à cette pomme (L3D1), alors la pomme qui était à ma gauche devient plus difficile à atteindre puisqu'elle est maintenant derrière moi. Notez que je pourrais prendre la pomme à ma droite avec la disposition D4, cela impliquerait de tourner mes pieds de sorte à ce que cette pomme soit derrière moi. La pomme initialement à ma gauche serait par la suite devant moi, donc je n'aurais pas à bouger les pieds pour la prendre en D1.

etc...