Voyageur de commerce avec horaires d'ouverture

**phryte** · 28/02/2016, 15h55

Bonjour,

Pour les problèmes d’explosion combinatoire, on utilise souvent la méthode de Monte Carlo.
Dans le cas de la distribution du courrier il faut définir au moins les données suivantes:
- Les villes à visiter avec leurs situations géographique y compris la ville de départ
- L’heure de départ
- Le temps passé dans chaque ville
- Les heures d’ouverture et de fermeture des lieux de livraison
- La vitesse moyenne du véhicule sur chaque tronçon
- ………
Les calculs à effectuer sont :
- Tirer un parcours au hasard et calculer le temps passé
- Tirer un autre parcours au hasard et calculer le temps passé
- Si le dernier temps passé est inférieur au temps précédent il est la référence
- Et on recommence …. des milliers de fois
Le résultats ne garantit pas le parcours optimal, mais il s’en approche à chaque bon tirage.
Voici un exemple en première approche sous MATLAB pour 10 villes. (Programme non optimisé.)
Il est possible bien sûr de programmer cette application sous tout autre langage.

Code matlab :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
clear
npts=10;%Nombre de villes
distancemin=1000;
vitmoy=30;%Vitesse moyenne en Km/h
nbsol=0;
X=[];Y=[];
taille=4;%Dimension de la répartition des villes
w=taille+1+i*(taille+1);
k=0;
while k<npts,
    a=rand*taille+0.5+i*(rand*taille+0.5);
    X=[X; real(a)];
    Y=[Y; imag(a)];
    k=k+1;
end;
%xy=[X Y];
pos=[X Y];
 
distmatrix=zeros(npts);
for n1=1:npts,
    for n2=1:n1,
        x1=pos(n1,1);
        y1=pos(n1,2);
        x2=pos(n2,1);
        y2=pos(n2,2);
        distmatrix(n1,n2)=sqrt((x1-x2)^2+(y1-y2)^2);
        distmatrix(n2,n1)=distmatrix(n1,n2);
    end;
end;
 
distance=sum(sum(distmatrix));
h=plot(0,0,'Color','red');
set(h,'LineWidth',2)
set(h,'MarkerSize',15)
set(h,'color',[0 1 0]);
axis([0. taille+1 0. taille+1])
grid
 
hh=plot(0,0,'yo','LineWidth',2,'MarkerSize',15);
grid
set(gcf,'Color','w');
NE=100000;%Nombre d'itération
HD=10;%Heure de départ
hou=[8 10];%Horaires d'ouverture
hfe=[19 20];%Horaires de fermeture
tdis=linspace(0,0.15,npts);%Temps de distribution
title('DISTRIBUTION DU COURRIER')
 
%Répartitioçn des horaires ouverture et fermeture
for nh=1:npts
    H(1,nh)= hou(fix(rand*2)+1);
    H(2,nh)= hfe(fix(rand*2)+1);
end
 
for ne=1:NE
    drawnow;
    Trajet=randperm(npts);
    total=sum(distmatrix([(Trajet-1)*npts+Trajet([end 1:(end-1)])]));
    distance=total+sqrt( pos(Trajet(1),1)^2+ pos(Trajet(1),2)^2);+sqrt( pos(Trajet(10),1)^2+ pos(Trajet(10),2)^2);
    HA(1)=HD+sqrt(pos(Trajet(1),1)^2+pos(Trajet(1),2)^2)/vitmoy;%Heure d'arrivée à la première ville
    %Calcul des heures d'arrivée dans chaque ville
    for ct=2:npts
        HA(ct)=HA(ct-1)+sqrt((pos(ct,1)-pos(ct-1))^2+(pos(ct,2)-pos(ct-1))^2)/vitmoy+tdis(ct);
    end
 
    HA(11)=HA(9)+sqrt(pos(10,1)^2+pos(10,2)^2)/vitmoy+tdis(10);%Matrice des heures d'arrivées
 
    if HA(1)>=H(1,1) %Test horaire d'ouverture
 
        %Horaire d'ouverture OK
        if distance<distancemin
            distancemin=distance;
            Trajetmin=Trajet;
            TrajetRetenu=Trajet;
            HAR=HA;%Heure d'arrivée retenu
            DistRetenue=distancemin;%Distance retenue
            nbsol=nbsol+1;
            ii=1:npts;
            x=pos(ii,1);y=pos(ii,2);
            cla
            plot(x,y,'ko','LineWidth',2,'MarkerSize',12)
            hold on
            plot(0,0,'bo','LineWidth',2,'MarkerSize',12)
            h=plot(pos(Trajet(ii),1),pos(Trajet(ii),2),'Color','red');
            line([0 pos(Trajet(1),1)],[0 pos(Trajet(1),2)],'color','b')
            quiver(0,0,pos(Trajet(1),1),pos(Trajet(1),2),'b')
            line([0 pos(Trajet(10),1)],[0 pos(Trajet(10),2)],'color','b')
            quiver(pos(Trajet(10),1),pos(Trajet(10),2),-pos(Trajet(10),1),-pos(Trajet(10),2),'b')
            set(h,'LineWidth',2)
            set(h,'MarkerSize',15)
            axis([0. taille+1 0. taille+1])
            grid
            hold off
            %Affichage du nom des villes (ici un numéro)
            for ii=1:npts;
                x=pos(ii,1);y=pos(ii,2);
                f=text(x+0.1,y,int2str(ii));
                set(f,'color',[0 0 1]);
            end
            text(0.2,taille+0.8,['Trajet minimum : ',num2str(DistRetenue) ' Km']);
            text(0.2,taille+0.6,['Temps tournée : ',num2str(HA(11)-HD) ' H']);
            text(0.2,taille+0.4,['Heure de départ : ',num2str(HD) ' H'])
            text(3,taille+0.8,['Nombre de villes : ',num2str(npts)]);
            text(3,taille+0.6,['Vitesse moyenne : ',num2str(vitmoy) '  Km/H']);
            text(3,taille+0.4,['Heure d''arrivée : ',num2str(HAR(11)) ' H'])
            text(-0.1,-0.3,'DEPART')
            g=text(2.5,0.2,['Trajet =',num2str(Trajet)]);%    Nb solutions retenues = ',num2str(nbsol)]);
            set(g,'color','k');
            set(g,'FontSize',8);
            gg=text(0,0.2,['Nb solutions retenues = ',num2str(nbsol)]);
            set(gg,'color','k');
        end
    end
end
title(['DISTRIBUTION DU COURRIER   Nombre d''essais :',num2str(NE)])
tableau(1:10,1)=TrajetRetenu';
tableau(1:11,2)=HAR';
disp(' ')
disp(['Heure de départ : ' num2str(HD) ' H'])
disp(['Heure de retour : ' num2str(HA(11)) ' H'])
disp(' ')
disp('    Villes   Heure arrivée')
disp(tableau)

Sortie Command Window :
Heure de départ : 10 H
Heure de retour : 11.6541 H
Villes Heure arrivée
4.0000 10.0708
7.0000 10.1711
1.0000 10.3067
3.0000 10.4687
5.0000 10.6609
8.0000 10.8503
10.0000 10.9789
2.0000 11.1519
9.0000 11.3594
6.0000 11.5948
0 11.6350
Graphe :
Nom : Distribution.png
Affichages : 234
Taille : 23,2 Ko

Nom : Distribution.png
Affichages : 234
Taille : 23,2 Ko

**grint54** · 28/02/2016, 18h24

Merci à phryte pour ses schémas. Voilà à quoi peut ressembler un parcours journalier. Quand au code, je ne saurais pas m'en servir à moins que l'on me dise si par exemple, il serait fonctionnel en remplaçant certains code qui sont en couleur par de vrais noms.

La méthode Monte-Carlo, j'essaierai de m'en souvenir.

Voyageur de commerce avec horaires d'ouverture

Algorithmes et structures de données

Discussions similaires

Partager

Partager