Calcul de chemin le plus court

[Batou69]

Bonjour à tous,

J'ai un souci avec la performance d'une requête de calcul de chemin le plus court.

Tout d'abord, je vous expose le contexte : je souhaite modéliser un graphe orienté multiple. Voila pour la théorie.
Dans la pratique, cela peut s'apparenter à un GPS. J'ai une liste de sommets (les villes) et des arêtes (les routes). Mes routes sont unidirectionnelles et ont une longueur. Il existe des boucles. De plus il existe aussi des villes reliées entre elles par deux routes distinctes (mais n'ayant pas la même longueur).

Je connais la ville de départ de toutes mes excursions et je cherche a rallier mon point d'arrivée qui est connu à l'avance. Mais attention, je dois impérativement passer par certaines 'routes' et je ne reviens jamais au point de départ (ce n'est pas un cycle)

Voici un exemple de graphe que je modélise :

(Je n'ai pas pu représenter les routes multiples)

Pour modéliser tout cela, j'ai deux tables fixes : la table des villes et la table des routes. Une route a une ville de départ, une ville d'arrivée et une longueur
J'ai par ailleurs une table dynamique qui contient une ligne par passage dans une route

Ma technique utilisée pour résoudre le problème :
Je calcule l'ensemble des chemins possibles entre la ville de départ et la ville d'arrivée. Avant de partir, je calcule la liste des chemins qui passent par toutes les routes qui m’intéressent et je prend le plus court.
Je me suis aidé de l'excellent papier sur les requêtes récursives http://sqlpro.developpez.com/cours/s...te-recursives/.

Dans ma base j'ai 32 villes et 60 routes.

Le problème est que depuis le point de départ de mon périple vers la dernière ville me donne presque 70 000 possibilités de chemins (en presque 3 minutes).

Or maintenant on me demande d'effectuer le calcul en temps réel (cad en moins d'environ 100ms) et cela pour n'importe quel point.
En gros une fois que j'arrive dans une ville, je dois recalculer le chemin le plus court pour aller vers la dernière ville, tout en passant par les routes obligatoires et en éliminant celles déjà visitées.

La requête récursive me donne une liste de chemins possibles. Chaque chemin comporte un varchar avec les routes empruntées séparées par une virgule. Si je décompose cette liste en lignes pour faciliter la comparaison avec les routes obligatoires, j’obtiens une liste de prés de 2milions de lignes, ce qui est incompatible avec ma performance.

Pouvez vous m'aider sur la méthode employée ? Trouvez vous la technique viable ou bien dois je repenser la structure pour améliorer la performance ?

Si vous le souhaitez je peux donner des définitions de tables et les requêtes utilisées pour générer tout cela.

Merci d'avance !

(Désolé pour la longueur)

[Waldar]

Le problème du voyageur de commerce ! La solution réside plutôt dans les l'optimisation linéaire ou les algorithmes génétiques dont le code est plus efficace je pense dans les langages de programmation classiques.

Probablement faisable en SQL, mais en 100ms j'en doute un peu !
Néanmoins, c'est un bon sujet !

[SQLpro]

Oubliez la programmation génétique et autres folklore du genre... Vous n'irez pas plus vite.

Plusieurs éléments doivent être pris en considération :
1) comment la table est-elle indexée ?
2) au lieu de stocker les noms des villes dans les chemins, préférez stockez les ID des villes
3) toutes ces données étant statiques, il suffit de les calculer une bonne fois pour toute puis mettre un trigger sur INSERT, UPDATE, DELETE pour lancer le calcul en bacth de nuit.

Pour ce faire j'aurais modélisé comme suit :
1) tables des "puits" villes :
T_VILLE_VIL
(VIL_ID, VIL_NOM)
2) table des "arcs" route :
T_ROUTE_RTE
(RTE_ID, VIL_ID_DEPART, VIL_ID_ARRIVE, RTE_DISTANCE_ALLER, RTE_DISTANCE_RETOUR)
3) table des trajets :
T_TRAJET_TRJ
(TRJ_ID, VIL_ID_DEPART, VIL_ID_ARRIVE, TRJ_DISTANCE, TRJ_OK)
4) table du détail des trajets :
T_TRAJET_CHEMIN_CHM
(CHM_ID, TRJ_ID, VIL_ID, CHM_ORDRE, CHM_DISTANCE)

Les deux dernières tables étant calculées via les triggers mais indirectement. En gros le trigger insère des lignes dans la table T_TRAJET_TRJ avec la ville de départ et d'arrivée avec TRJ_OK = 0 pour signaler que ce trajet est à calculer.

A +

[Batou69]

Merci pour vos réponses

Envoyé par SQLpro

Plusieurs éléments doivent être pris en considération :
1) comment la table est-elle indexée ?

Je n'ai pas encore mis d'index sur la table car la volumétrie me parait dèjà et à priori démesurée (voir plus bas)

Envoyé par SQLpro

2) au lieu de stocker les noms des villes dans les chemins, préférez stockez les ID des villes

Pas de problème la dessus, je ne travaille jamais avec des chaines variables ou non. En réalité le problème ne concerne pas du tout des villes, mais comme c'est assez compliqué à expliquer, j'ai préféré faire cette analogie qui me parait plus parlante.
Dans mon cas, les villes sont des points de décision et les routes sont des convoyeurs.

Envoyé par SQLpro

3) toutes ces données étant statiques, il suffit de les calculer une bonne fois pour toute puis mettre un trigger sur INSERT, UPDATE, DELETE pour lancer le calcul en bacth de nuit.

Je suis d'accord avec cela. Mon modèle est même mieux que ça, la liste des villes et des routes est totalement fixe. Mais je travaille sur un progiciel et les villes et les routes font partie de la configuration.

Envoyé par SQLpro

Pour ce faire j'aurais modélisé comme suit :
1) tables des "puits" villes :
T_VILLE_VIL
(VIL_ID, VIL_NOM)

J'ai ca :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
CREATE TABLE [dbo].[POINT_DECISION](
	[NO_POINT_DECISION] [int] IDENTITY(1,1) NOT FOR REPLICATION NOT NULL,
	[DATE_CREATION] [datetime] NOT NULL,
	[LIBELLE] [varchar](50) NULL,
	[DEBUT_CONVOYAGE] [bit] NOT NULL,
	[FIN_CONVOYAGE] [bit] NOT NULL,
	[NO_POINT_DECISION_EQUIVALENT] [int] NULL,
	[NB_PASSAGES_CHEMIN] [int] NOT NULL,
 CONSTRAINT [PK_POINT_DECISION] PRIMARY KEY CLUSTERED 
(
	[NO_POINT_DECISION] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
) ON [PRIMARY]

Envoyé par SQLpro

2) table des "arcs" route :
T_ROUTE_RTE
(RTE_ID, VIL_ID_DEPART, VIL_ID_ARRIVE, RTE_DISTANCE_ALLER, RTE_DISTANCE_RETOUR)

A noter que mes routes sont toutes unidirectionnelles

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
CREATE TABLE [dbo].[CONVOYEUR](
	[NO_CONVOYEUR] [int] NOT NULL,
	[NO_CONFIGURATION] [int] NOT NULL,
	[NO_POINT_DECISION_FROM] [int] NOT NULL,
	[NO_POINT_DECISION_TO] [int] NOT NULL,
	[DATE_CREATION] [datetime] NOT NULL,
	[LIBELLE] [varchar](50) NULL,
	[LONGUEUR] [int] NULL,
	[VITESSE] [int] NULL,
	[CORRECTIF] [int] NULL,
 CONSTRAINT [PK_CONVOYEUR] PRIMARY KEY CLUSTERED 
(
	[NO_CONVOYEUR] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
) ON [PRIMARY]

Envoyé par SQLpro

3) table des trajets :
T_TRAJET_TRJ
(TRJ_ID, VIL_ID_DEPART, VIL_ID_ARRIVE, TRJ_DISTANCE, TRJ_OK)

La je ne suis plus très sûr. Je ne vois pas très bien ce que tu mes dans cette table. As tu toutes les possibilités selon toutes les villes du graphe et vers toutes les autres ? Si oui alors le nombre de possibilité est vraiment énorme !

Pour ma part, j'ai calculé cela :

Code :

1
2
3
4
5
6
7
8
 
CREATE TABLE [dbo].[CHEMIN](
	[NO_CHEMIN] [bigint] NULL,
	[LISTE_POINT_DECISION] [varchar](max) NULL,
	[DISTANCE] [int] NULL,
	[TEMPS_PARCOURS] [float] NULL,
	[LISTE_CONVOYEURS] [varchar](max) NULL
) ON [PRIMARY]

Tous mes chemins partent du (ou des) point(s) de décision qui ont le flag DEBUT_CONVOYAGE et vont vers le(s) point(s) qui ont le flag FIN_CONVOYAGE. Mais je n'ai pas les trajets 'internes' dans cette table (c'est peut etre là que se situe mon problème). Par trajet interne j’entends que cette table ne contient pas de chemin entre deux points qui ne sont pas ni un début ni une fin.
Les données que je possède, me donnent déjà près de 71000 chemins possibles. (pour mémoire, j'ai seulement 32 points de décision et 60 convoyeurs).
MAIS : comme mon graphe n'est pas simple, il est possible qu'un chemin nécessite de passer plusieurs fois par le même point de décision pour atteindre la sortie. J'ai donc ajouté une colonne NB_PASSAGES_CHEMIN pour limiter le nombre de fois de passage et ainsi ne pas exploser la récursivité de mon CTE.

Envoyé par SQLpro

4) table du détail des trajets :
T_TRAJET_CHEMIN_CHM
(CHM_ID, TRJ_ID, VIL_ID, CHM_ORDRE, CHM_DISTANCE)

Cela aussi j'ai fait :

Code :

1
2
3
4
5
6
 
CREATE TABLE [dbo].[CONVOYEUR_CHEMIN](
	[NO_CHEMIN] [bigint] NULL,
	[ORDRE] [int] NOT NULL,
	[NO_CONVOYEURS] int NULL
) ON [PRIMARY]

Mais c'est là que cela me parait coincer : j'ai 2 millions de lignes dans cette table. Et je dois chercher le plus court en faisant le rapprochement avec une autre table contenant la liste des convoyeurs imposés (les endroits par ou je dois impérativement passer).

Envoyé par SQLpro

Les deux dernières tables étant calculées via les triggers mais indirectement. En gros le trigger insère des lignes dans la table T_TRAJET_TRJ avec la ville de départ et d'arrivée avec TRJ_OK = 0 pour signaler que ce trajet est à calculer.

Pas de souci de trigger, comme je le disais plus haut, toutes mes données sont fixes. Seul les points de passage imposés varient.

Mon problème est que trouver le bon chemin ne doit pas prendre de temps car la réponse doit venir en 'temps réel' (cad environ 100ms maxi de temps de réponse) et ce sur n'importe quel point de décision du graphe.
La requête de recherche du chemin doit selon moi faire un produit cartésien sur les CONVOYEUR_CHEMIN et ma table de chemins imposés. Puis trouver le chemin qui correspond en faisant un 'count' du nombre de convoyeurs du chemin et trouver ceux qui on le même nombre que le nombre de mes étapes imposées. (Je sais pas si c'est très clair). Bref cette requête est à ma portée, mais faire cela avec 2M de lignes, c'est vraiment chaud pour un temps de réponse très très court.
Pour l'instant, je n'ai pas évalué le temps que cela prend sur mon serveur de test. Je n'ai pas non plus ajouté le moindre index sur les tables que je vous ai présenté. J'en suis encore à la phase de modélisation et d'écriture des requêtes. Mais si cela n'est pas possible en faisant de cette manière, alors je devrais peut être revoir ma structure de données. Cela ne me pose pas de problème de tout casser pour faire différemment.

Envoyé par SQLpro

A +

Merci de ton aide !

[iberserk]

Je n'ai pas encore mis d'index sur la table car la volumétrie me parait dèjà et à priori démesurée (voir plus bas)

Justement...

[SQLpro]

Envoyé par Batou69

Je n'ai pas encore mis d'index sur la table car la volumétrie me parait dèjà et à priori démesurée

JUSTEMENT ! Les index n'ont d'intérêt que si la volumétrie est importante puisque leur but est de faire passer un traitement qui a cout linéaire à un cout logarithmique...
Déjà, au moins :

Code :

CREATE INDEX X_CON_FROM_TO_LONG ON dbo.CONVOYEUR (NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, LONGUEUR);

La je ne suis plus très sûr. Je ne vois pas très bien ce que tu mes dans cette table. As tu toutes les possibilités selon toutes les villes du graphe et vers toutes les autres ? Si oui alors le nombre de possibilité est vraiment énorme !

Énorme ne veut rien dire en matière de bases de données. On parle volume... Sachant qu'une base de données de quelques Go c'est une petite base. Une base moyenne c'est de 30 à 300 Go, une grosse entre 300 et 1 To, une très grosse au dessus du To, et une fois indexé la plupart du temps la recherche d'une données consiste à lire 3 pages de 8 ko !!!
Faisons un calcul, avec 10 000 villes l'ensemble des trajets fait 10000x10000 = 100 000 000.
Or dans cette table on ne conserve que 4 entiers, soit 32 octets.
32 octets par 100 millions, cela fait 3 Go pour la table. Bref du pipi de chat !

Pour ma part, j'ai calculé cela :

Code :

Ca c'est stupide!!!
1) c'est pas relationnel : viol de la 1FN : les données doivent être atomique
2) ça va effectivement générer des centaines de Go

Commence par revoir cela on discute ensuite.

1) table des trajet
2 table des détails de trajets

A +

[Batou69]

Envoyé par SQLpro

JUSTEMENT ! Les index n'ont d'intérêt que si la volumétrie est importante puisque leur but est de faire passer un traitement qui a cout linéaire à un cout logarithmique...
Déjà, au moins :

Code :

CREATE INDEX X_CON_FROM_TO_LONG ON dbo.CONVOYEUR (NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, LONGUEUR);

Je suis tout à fait d'accord sur l'intérêt des indexes, mais cette table ne fait que 60 lignes, et en plus la requête de calcul des chemin utilise toutes les lignes. Je sors d'un cours d'administration sql et nous avons évoqué l'optimisation. Je connais les avantages des indexes et les utilise dans la plupart des cas, mais pour une table si petite, je n'ai pas compris l’intérêt d'un index sur les convoyeurs. En fait la table tient dans une page.
Ce point n'étant pas mon problème principal, j'ai suivi ce conseil et mis un index.

Envoyé par SQLpro

Ca c'est stupide!!!
1) c'est pas relationnel : viol de la 1FN : les données doivent être atomique
2) ça va effectivement générer des centaines de Go

Commence par revoir cela on discute ensuite.

1) table des trajet
2 table des détails de trajets

Alors je crois que je n'ai pas correctement expliqué ce que je veux faire et comment je le fais, car ma table me parait être la seule solution à mon problème.

La table CHEMIN contient la liste des chemins depuis le point de départ jusqu’à l'arrivée. C'est une table intermédiaire. Je ne m'en sert que pour calculer le détail des chemins.
Pour faire simple, dans la table chemin j'ai (extrait parmi les 71000 lignes) :

Code :

1
2
3
4
5
6
 
NO_CHEMIN	LISTE_POINT_DECISION	DISTANCE	TEMPS_PARCOURS	LISTE
_CONVOYEUR
1	36,24,20,13,1,2,3,4,5,22,12,16,23,27,18,32,33	301189	7,30017835497835	2,8,9,12,17,55,56,57,58,23,24,59,42,44,46,48
2	36,24,20,13,1,2,3,4,5,22,12,16,23,27,18,32,33	292954	7,72035692640693	2,8,9,12,17,55,56,57,58,23,24,41,42,44,46,48
3	36,24,20,13,1,2,3,4,5,22,12,16,23,27,18,32,33	287152	7,51314264069264	2,8,9,12,17,55,56,57,22,23,24,59,42,44,46,48

Tous mes chemins partent du convoyeur numero 2 et se terminent au 48, c'est bien le but recherché.

et dans la table du détail des chemins j'ai :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
NO_DETAIL_CHEMIN	NO_CHEMIN	NO_ORDRE	NO_CONVOYEUR
1	1	1	2
2	1	2	8
3	1	3	9
4	1	4	12
5	1	5	17
6	1	6	55
7	1	7	56
8	1	8	57
9	1	9	58
10	1	10	23
11	1	11	24
12	1	12	59
13	1	13	42
14	1	14	44
15	1	15	46
16	1	16	48

La table chemin n'est là que pour générer le détail des chemins. Le détail des chemins contient presque 2millions de lignes

Bien sûr j'ai fait des indexes sur tout cela :

Code :

1
2
3
4
5
6
7
 
CREATE NONCLUSTERED INDEX [IX_NO_CONVOYEUR] ON [dbo].[DETAIL_CHEMIN] 
(
	[NO_CONVOYEUR] ASC
)
INCLUDE ( [NO_CHEMIN]) WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
GO

Tout cela fonctionne plutôt bien si je cherche tous les chemins d'un convoyeur X vers un convoyeur Y. Mais la difficulté est que je cherche tous les chemins qui vont de X vers Y et qui passent par une liste donnée. Et la pour faire cela, j'ai ça :

Code :

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
 
WITH 
	up_con AS ( 
	-- cette partie est la une partie simplifiée de la selection de la liste des 
	-- convoyeurs imposés. Elle fait appel à d'autre tables que je n'ai pas décrites
	SELECT
		no_convoyeur
	FROM 
		convoyeur con
	WHERE 
		no_convoyeur IN ( 9, 50, 51, 52, 53, 54, 55, 56, 57, 58 )
	-- fin de la partie simplifiée
	)
	, up_nb_con AS (
	SELECT
		count(*) nb_convoyeur
	FROM
		up_con
	)
	, coc_up_con AS (
	SELECT
		no_chemin
		, count(*) nb_convoyeur
	FROM
		convoyeur_chemin coc
	INNER JOIN
		up_con
	ON
		coc.no_convoyeur = up_con.no_convoyeur
	GROUP BY
		no_chemin
	)
SELECT 
	* 
FROM 
	coc_up_con
INNER JOIN
	up_nb_con
ON
	coc_up_con.nb_convoyeur = up_nb_con.nb_convoyeur
INNER JOIN
	chemin che
ON 
	coc_up_con.no_chemin = che.no_chemin

Voilà.
Je veux pas vous noyer avec le code, alors j'ai simplifié la requête de dessus. La partie simplifiée est marquée avec un commentaire. Ce que je constate, c'est que la requete ci dessus -telle quelle- est vraiment rapide. La partie que j'ai simplifié est relativement simple et -si je l'éxécute toute seule-, est aussi très rapide. En revanche, lorsque je met les deux ensemble, cela devient vraiment lent.
Ce n'est pas la première fois que je constate ce genre de phénomène. Vous prenez un requête qui semble optimisée et rapide, vous la collez dans un cte qui lui aussi est rapide tout seul, et le tout devient vraiment lent.

Je peux fournir la partie simplifiée si cela est pertinent.

Pour finir, j'en revient à ce que tu disais :

Envoyé par SQLpro

Ca c'est stupide!!!
1) c'est pas relationnel : viol de la 1FN : les données doivent être atomique
2) ça va effectivement générer des centaines de Go

Commence par revoir cela on discute ensuite.

1) table des trajet
2 table des détails de trajets

Il me semble que c'est ce que j'ai fait. Je comprend que la table que j'ai faite n'est pas relationelle, mais je ne sais pas faire autrement. Comment faire une table des trajets ?

[SQLpro]

C'est justement cette table là qui ne vas pas du tout :

Code :

1
2
3
4
5
NO_CHEMIN	LISTE_POINT_DECISION	DISTANCE	TEMPS_PARCOURS	LISTE
_CONVOYEUR
1	36,24,20,13,1,2,3,4,5,22,12,16,23,27,18,32,33	301189	7,30017835497835	2,8,9,12,17,55,56,57,58,23,24,59,42,44,46,48
2	36,24,20,13,1,2,3,4,5,22,12,16,23,27,18,32,33	292954	7,72035692640693	2,8,9,12,17,55,56,57,58,23,24,41,42,44,46,48
3	36,24,20,13,1,2,3,4,5,22,12,16,23,27,18,32,33	287152	7,51314264069264	2,8,9,12,17,55,56,57,22,23,24,59,42,44,46,48

Elle viole la 1FN puisque dans une colonne vous avez plusieurs valeurs.

Commencer par la décomposer en deux :

Entête avec les données relationnelles, puis détail (peut être deus tables détails d'ailleurs) en reprenant la clef de la première à titre de FK et en décomposant vos LISTE_POINT_DECISION et LISTE
_CONVOYEUR (comme il y en a 2 et que je ne voit pas de lien entre les deux, alors vous aurez 2 tables détail.

A +

[Waldar]

Envoyé par Batou69

Dans ma base j'ai 32 villes et 60 routes.

Ce qui serait super ce serait de fournir les données !
Comme ça on pourrait vraiment s'amuser.

[Batou69]

Envoyé par Waldar

Ce qui serait super ce serait de fournir les données !
Comme ça on pourrait vraiment s'amuser.

Alors là, il n'y a pas, mais vraiment pas, de problème. Quel format ?

[Batou69]

Envoyé par SQLpro

Commencer par la décomposer en deux :

Entête avec les données relationnelles, puis détail (peut être deus tables détails d'ailleurs) en reprenant la clef de la première à titre de FK et en décomposant vos LISTE_POINT_DECISION et LISTE
_CONVOYEUR (comme il y en a 2 et que je ne voit pas de lien entre les deux, alors vous aurez 2 tables détail.

A +

Je suis désolé mais je ne comprend pas ce que vous voulez dire.... Car ma seconde table est -elle- tout ce qu'il y a de relationnel et c'est sur cette deuxieme table que je fais mes recherches, celle que vous citez n'est qu'intermédiaire. Peut etre un exemple de lignes obtenues dans les deux tables m'aiderait à comprendre ??

Merci

[Waldar]

Envoyé par Batou69

Alors là, il n'y a pas, mais vraiment pas, de problème. Quel format ?

Un script SQL classique :

Code :

1
2
CREATE TABLE <...>
INSERT INTO <...> VALUES <...>

[Batou69]

Voila :

J'ai ajoute la table ETAPES qui contient la liste des convoyeurs imposés pour ce cas.

Code :

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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
 
CREATE TABLE [dbo].[POINT_DECISION](
	[NO_POINT_DECISION] [int] NOT NULL,
	[DATE_CREATION] [datetime] NOT NULL,
	[LIBELLE] [varchar](50) NULL,
	[DEBUT_CONVOYAGE] [bit] NOT NULL,
	[FIN_CONVOYAGE] [bit] NOT NULL,
	[NO_POINT_DECISION_EQUIVALENT] [int] NULL,
	[NB_PASSAGES_CHEMIN] [int] NOT NULL,
 CONSTRAINT [PK_POINT_DECISION] PRIMARY KEY CLUSTERED 
(
	[NO_POINT_DECISION] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
) ON [PRIMARY]
 
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES(  1, getdate(), 'Transfert T2', 0,0,NULL,0 )
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES(  2, getdate(), 'Transfert T3', 0,0,NULL,0 )
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES(  3, getdate(), 'Transfert T4', 0,0,NULL,0 )
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES(  4, getdate(), 'Transfert T5', 0,0,NULL,0 )
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES(  5, getdate(), 'Transfert T6', 0,0,NULL,0 )
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES(  6, getdate(), 'Transfert T8', 0,0,NULL,0 )
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES(  7, getdate(), 'Transfert T9', 0,0,NULL,0 )
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES(  8, getdate(), 'Transfert T10', 0,0,NULL,0 )
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES(  9, getdate(), 'Transfert T11', 0,0,NULL,0 )
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 10, getdate(), 'Transfert T12', 0,0,NULL,0 )
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 11, getdate(), 'Transfert T202', 0,0,NULL,0 )
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 12, getdate(), 'Bras déviateur B251', 0,0,NULL,0 )
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 13, getdate(), 'Transfert T203', 0,0,NULL,2 )
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 14, getdate(), 'Transfert T205', 0,0,NULL,0 )
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 15, getdate(), 'Transfert T206', 0,0,NULL,0 )
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 16, getdate(), 'Transfert T207', 0,0,NULL,1 )
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 17, getdate(), 'Transfert T208', 0,0,NULL,0 )
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 18, getdate(), 'Transfert T212', 0,0,NULL,0 )
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 19, getdate(), 'Balance B1 Dyna-Trad', 0,0,NULL,0 )
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 20, getdate(), 'Balance B2 Magauto', 0,0,NULL,0 )
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 21, getdate(), 'Balance B4 Dyna', 0,0,NULL,0 )
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 22, getdate(), 'Balance B5 Trad', 0,0,NULL,0 )
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 23, getdate(), 'Balance B6 finale', 0,0,NULL,0 )
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 24, getdate(), 'PUM Magauto', 0,0,NULL,0 )
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 25, getdate(), 'PUM Dyna-Trad', 0,0,NULL,0 )
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 26, getdate(), 'Secteur Froid T322', 0,0,NULL,0 )
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 27, getdate(), 'Ticket adresse T210', 0,0,NULL,0 )
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 28, getdate(), 'Ticket adresse T211', 0,0,27,0 )
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 29, getdate(), 'Ticket erreur Rappel', 0,0,NULL,0 )
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 30, getdate(), 'Ticket erreur Mag 1', 0,0,NULL,0 )
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 31, getdate(), 'Ticket erreur Mag 2', 0,0,NULL,0 )
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 32, getdate(), 'Pose Facture', 0,0,NULL,0 )
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 33, getdate(), 'Trieur', 0,1,NULL,0 )
INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 36, getdate(), 'Lancement', 1,0,NULL,0 )
 
CREATE TABLE [dbo].[CONVOYEUR](
	[NO_CONVOYEUR] [int] NOT NULL,
	[NO_POINT_DECISION_FROM] [int] NOT NULL,
	[NO_POINT_DECISION_TO] [int] NOT NULL,
	[DATE_CREATION] [datetime] NOT NULL,
	[LIBELLE] [varchar](50) NULL,
	[LONGUEUR] [int] NULL,
	[VITESSE] [int] NULL,
	[CORRECTIF] [int] NULL,
 CONSTRAINT [PK_CONVOYEUR] PRIMARY KEY CLUSTERED 
(
	[NO_CONVOYEUR] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
) ON [PRIMARY]
 
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES(  1,36,25,getdate(),'conv 1',    2820, 40,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES(  2,36,24,getdate(),'conv 2',   12291, 30,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES(  3,25,19,getdate(),'conv 3',    3564, 40,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES(  4,19,11,getdate(),'conv 4',    2926, 28,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES(  5,11, 1,getdate(),'conv 5',    4305, 28,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES(  6,11, 2,getdate(),'conv 6',    9806, 28,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES(  7,11,26,getdate(),'conv 7',   82603, 30,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES(  8,24,20,getdate(),'conv 8',    6547, 28,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES(  9,20,13,getdate(),'conv 9',   38576, 28,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 10,13,30,getdate(),'conv 10',   1823, 30,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 11,13,31,getdate(),'conv 11',   1823, 30,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 12,13, 1,getdate(),'conv 12',  11028, 28,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 13,13,17,getdate(),'conv 13',  75934, 49,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 14,30,13,getdate(),'conv 14',   1823, 30,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 15,31,13,getdate(),'conv 15',   1823, 30,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 16,26,17,getdate(),'conv 16', 140383, 41,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 17, 1, 2,getdate(),'conv 17',   6187, 30,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 18, 1, 6,getdate(),'conv 18',  22824, 30,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 19, 2, 3,getdate(),'conv 19',  12600, 28,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 20, 3, 4,getdate(),'conv 20',  12600, 28,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 21, 4, 5,getdate(),'conv 21',  12684, 28,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 22, 5,22,getdate(),'conv 22',   5963, 28,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 23,22,12,getdate(),'conv 23',   2116, 33,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 24,12,16,getdate(),'conv 24',  19760, 28,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 25,12,17,getdate(),'conv 25',  12918, 30,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 26, 6, 7,getdate(),'conv 26',   9817, 28,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 27, 7, 8,getdate(),'conv 27',  10606, 28,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 28, 8, 9,getdate(),'conv 28',   9798, 28,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 29, 9,10,getdate(),'conv 29',   9838, 28,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 30,10,21,getdate(),'conv 30',   7816, 28,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 31,21,14,getdate(),'conv 31',  18795, 30,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 32,14,15,getdate(),'conv 32',  16873, 30,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 33,14,27,getdate(),'conv 33',  30288, 36,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 34,14,28,getdate(),'conv 34',  30689, 30,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 35,17,15,getdate(),'conv 35',  10953, 30,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 36,17,27,getdate(),'conv 36',  27532, 30,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 37,17,28,getdate(),'conv 37',  27817, 30,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 38,15,16,getdate(),'conv 38',   8595, 28,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 39,15, 2,getdate(),'conv 39',  54870, 60,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 40,16,29,getdate(),'conv 40',   1302, 28,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 41,16,23,getdate(),'conv 41',  11765, 28,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 42,23,27,getdate(),'conv 42',  46830, 30,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 43,23,28,getdate(),'conv 43',  47230, 30,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 44,27,18,getdate(),'conv 44',   3108, 40,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 45,28,18,getdate(),'conv 45',   3108, 40,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 46,18,32,getdate(),'conv 46',   6546, 40, 30 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 47,18,33,getdate(),'conv 47',  54059, 30,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 48,32,33,getdate(),'conv 48',  48200, 30,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 49,29,16,getdate(),'conv 49',  11113, 30,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 50, 6, 7,getdate(),'conv 50',  20000,  1,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 51, 7, 8,getdate(),'conv 51',  20000,  1,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 52, 8, 9,getdate(),'conv 52',  20000,  1,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 53, 9,10,getdate(),'conv 53',  20000,  1,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 54,10,21,getdate(),'conv 54',  20000,  1,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 55, 2, 3,getdate(),'conv 55',  20000,  1,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 56, 3, 4,getdate(),'conv 56',  20000,  1,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 57, 4, 5,getdate(),'conv 57',  20000,  1,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 58, 5,22,getdate(),'conv 58',  20000,  1,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 59,16,23,getdate(),'conv 59',  20000,  1,  0 )
INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 60,26,26,getdate(),'conv 60',  20000,  1,  0 )
 
CREATE TABLE [dbo].[ETAPES](
	[NO_ETAPE] [int] NOT NULL,
	[NO_CONVOYEUR] [int] NOT NULL,
 CONSTRAINT [PK_ETAPES] PRIMARY KEY CLUSTERED 
(
	[NO_ETAPE] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
) ON [PRIMARY]
 
INSERT ETAPES( NO_ETAPE, NO_CONVOYEUR ) VALUES (  1,  9 )
INSERT ETAPES( NO_ETAPE, NO_CONVOYEUR ) VALUES (  2, 50 )
INSERT ETAPES( NO_ETAPE, NO_CONVOYEUR ) VALUES (  3, 51 )
INSERT ETAPES( NO_ETAPE, NO_CONVOYEUR ) VALUES (  4, 52 )
INSERT ETAPES( NO_ETAPE, NO_CONVOYEUR ) VALUES (  5, 53 )
INSERT ETAPES( NO_ETAPE, NO_CONVOYEUR ) VALUES (  6, 54 )
INSERT ETAPES( NO_ETAPE, NO_CONVOYEUR ) VALUES (  7, 55 )
INSERT ETAPES( NO_ETAPE, NO_CONVOYEUR ) VALUES (  8, 56 )
INSERT ETAPES( NO_ETAPE, NO_CONVOYEUR ) VALUES (  9, 57 )
INSERT ETAPES( NO_ETAPE, NO_CONVOYEUR ) VALUES ( 10, 58 )

[Waldar]

J'ai pu jouer avec vos données.

Je suis parti sur une solution calculée à la volée, pas sur la solution de SQLPro qui - puisqu'elle consiste à distribuer le calcul en tâche planifiée la nuit pour ne plus faire qu'une simple lecture en journée - sera beaucoup plus performante dès lors que la volumétrie augmentera.

En fait, la requête dynamique répond mieux que ce que je ne pensais, comme vous je suis parti sur une CTE récursive.
Par contre, je ne retrouve pas vos 70000 ou 2M de lignes dans les étapes intermédiaires (en fait mes étapes intermédiaires sont présentes dans le select, je n'ai rien en plus du script que vous avez fourni).

Je ne suis pas tombé à 100 ms comme vous le souhaitez, mais c'est déjà pas trop mal :
j'ai tronqué les 0 des "lob physical reads" et "lob read-ahead reads" pour conserver la mise en page

SQL Server parse and compile time: 
   CPU time = 47 ms, elapsed time = 82 ms.

(8 ligne(s) affectée(s))
Table 'Worktable'     . Scan count   2, logical reads  3726, physical reads 0, read-ahead reads 0, lob logical reads 1954.
Table 'POINT_DECISION'. Scan count   1, logical reads  1416, physical reads 0, read-ahead reads 0, lob logical reads    0.
Table 'ETAPES'        . Scan count 355, logical reads 42836, physical reads 0, read-ahead reads 0, lob logical reads    0.
Table 'CONVOYEUR'     . Scan count 354, logical reads   708, physical reads 0, read-ahead reads 0, lob logical reads    0.

SQL Server Execution Times:
   CPU time = 266 ms,  elapsed time = 289 ms.

Le meilleur chemin ramené par ma requête sur vos données est celui-ci :

chemin                                                      longueur
----------------------------------------------------------- -----------
36,24,20,13,1,6,7,8,9,10,21,14,15,2,3,4,5,22,12,17,27,18,33 461537

Déjà, est-ce que vous avez trouvé la même chose ?

Si oui, comment procède-t-on : je vous donne ma solution brut de fonderie ou j'essaie de vous y amener à partir de votre solution ?

[iberserk]

289 ms

Ca reste inperceptible pour l'utilisateur...

[Batou69]

Envoyé par Waldar

Le meilleur chemin ramené par ma requête sur vos données est celui-ci :

chemin                                                      longueur
----------------------------------------------------------- -----------
36,24,20,13,1,6,7,8,9,10,21,14,15,2,3,4,5,22,12,17,27,18,33 461537

Déjà, est-ce que vous avez trouvé la même chose ?

OUI !!

mais moi j'ai plutot ca :

SQL Server \endash  Temps d'exécution*:
, Temps UC = 0 ms, temps écoulé = 1 ms.
Temps d'analyse et de compilation de SQL Server : 
, Temps UC = 0 ms, temps écoulé = 1 ms.

(100*ligne(s) affectée(s))
Table 'CHEMIN'. Nombre d'analyses 1, lectures logiques 1301, lectures physiques 0, lectures anticipées 0
Table 'Worktable'. Nombre d'analyses 0, lectures logiques 0, lectures physiques 0, lectures anticipées 0
Table 'DETAIL_CHEMIN'. Nombre d'analyses 10, lectures logiques 1055, lectures physiques 0, lectures anticipées 0
Table 'ETAPES'. Nombre d'analyses 2, lectures logiques 4, lectures physiques 0, lectures anticipées 0

SQL Server \endash  Temps d'exécution*:
, Temps UC = 453*ms, temps écoulé = 450*ms.

Alors je peux vous donner les trois requetes utilisées pour arriver à ce résultat, mais je vous demande de l'indulgence car je ne suis pas non plus le plus grand expert du coin !!

Les trois étapes sont :

• 1 - requête récursive pour calculer l'ensemble des chemins possibles entre la gare de départ et la gare d'arrivée : résultat placé dans la table CHEMIN avec un numéro comme clef (70968 lignes). J'ai suivi l'excellent tutoriel : http://sqlpro.developpez.com/cours/s...te-recursives/
  Cela me donne des chemins avec un varchar contenant les points de décision et les convoyeurs dans l'ordre de parcours pour chaque chemin.
  (Aie c'est la que je sens que je vais faire hurler les puristes)
  A noter que cette table est 'statique', comme mes convoyeurs sont des données fixes, elle est calculée une seule fois

• 2 - Eclatement de la table chemin en une table DETAIL_CHEMIN contenant une ligne par chemin et par convoyeur (1786536 lignes)

• 3 - recherche des chemins qui m'intéressent dans la table précédente en faisant un produit croisé avec la table ETAPES puis en filtrant les chemins qui ont le nombre d'étapes demandées (soit 10 ici)
  A noter que je doute moi même de la fiabilité de l'algo basé sur un comptage sans s'assurer que l'on compte bien les même convoyeurs

Le tout me donne le résultat....

Envoyé par Waldar

Si oui, comment procède-t-on : je vous donne ma solution brut de fonderie ou j'essaie de vous y amener à partir de votre solution ?

En effet je préfèrerais vous présenter ma solution et vous m'expliquiez où sont mes erreurs, cela sera formateur...

[Batou69]

La table CHEMIN et DETAIL_CHEMIN

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
CREATE TABLE [dbo].[CHEMIN](
	[NO_CHEMIN] [bigint] NOT NULL,
	[LISTE_POINT_DECISION] [varchar](max) NULL,
	[DISTANCE] [int] NULL,
	[TEMPS_PARCOURS] [float] NULL,
	[LISTE_CONVOYEURS] [varchar](max) NULL
) ON [PRIMARY]
 
CREATE TABLE [dbo].[DETAIL_CHEMIN](
	[NO_DETAIL_CHEMIN] [bigint] NOT NULL,
	[ORDRE] [int] NOT NULL,
	[NO_CHEMIN] [int] NOT NULL,
	[NO_CONVOYEUR] int NOT NULL
) ON [PRIMARY]

Avec les indexes qui vont bien :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
ALTER TABLE [dbo].[CHEMIN] ADD  CONSTRAINT [PK_CHEMIN] PRIMARY KEY CLUSTERED 
(
	[NO_CHEMIN] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
GO
ALTER TABLE [dbo].[DETAIL_CHEMIN] ADD  CONSTRAINT [PK_DETAIL_CHEMIN] PRIMARY KEY CLUSTERED 
(
	[NO_DETAIL_CHEMIN] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
GO
 
CREATE NONCLUSTERED INDEX [IX_NO_CONVOYEUR] ON [dbo].[DETAIL_CHEMIN] 
(
	[NO_CONVOYEUR] ASC
)
INCLUDE ( [NO_CHEMIN]) WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
GO

(édité à la main donc pas certain qu'ils passent tous)

[Batou69]

LA requête pour construire la table CHEMIN :

Code :

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
 
WITH
	CONVOYEUR_CTE
	AS (
		SELECT DISTINCT 
			PTD.NO_POINT_DECISION NO_POINT_DECISION_TO
			, 0 ETAPES
			, CAST( NO_POINT_DECISION AS VARCHAR(MAX) ) CHEMIN
			, 0 DISTANCE
			, CAST( 0.0 AS float ) TEMPS_PARCOURS
			, CAST( '' AS VARCHAR(MAX) ) CONVOYEURS
		FROM
			dbo.POINT_DECISION PTD
		WHERE
			PTD.DEBUT_CONVOYAGE = 1
		UNION ALL
		SELECT 
			CON.NO_POINT_DECISION_TO
			, CON_CTE.ETAPES + 1
			, CON_CTE.CHEMIN + ',' + CONVERT( VARCHAR(10), CON.NO_POINT_DECISION_TO )
			, CON_CTE.DISTANCE + CON.LONGUEUR
			, CON_CTE.TEMPS_PARCOURS + 
			  CASE 
				WHEN CON.VITESSE = 0  THEN 0 
				ELSE CON.LONGUEUR / ( 1000.0 * CON.VITESSE ) + COALESCE( CON.CORRECTIF, 0 ) / 60.0
			END
			, CASE
				WHEN CON_CTE.CONVOYEURS = '' THEN CAST( CON.NO_CONVOYEUR AS VARCHAR(MAX) )
				ELSE CON_CTE.CONVOYEURS + ',' + CAST( CON.NO_CONVOYEUR AS VARCHAR(MAX) )
			END
		FROM
			dbo.CONVOYEUR CON --arrival
		INNER JOIN
			CONVOYEUR_CTE CON_CTE --departure
		ON
			CON_CTE.NO_POINT_DECISION_TO = CON.NO_POINT_DECISION_FROM
		INNER JOIN
			dbo.POINT_DECISION PTD
		ON
			CON.NO_POINT_DECISION_TO = PTD.NO_POINT_DECISION
		WHERE
			dbo.ufn_CountString( ',' + CON_CTE.CHEMIN + ',', ',' + CONVERT( VARCHAR(10), PTD.NO_POINT_DECISION ) + ',' ) <= PTD.NB_PASSAGES_CHEMIN
	)
INSERT
	CHEMIN(NO_CHEMIN,LISTE_POINT_DECISION, DISTANCE, TEMPS_PARCOURS,LISTE_CONVOYEURS)
SELECT
	row_number() over (ORDER BY CON_CTE.CHEMIN ) NO_CHEMIN
	, CON_CTE.CHEMIN LISTE_POINT_DECISION
	, CON_CTE.DISTANCE
	, CON_CTE.TEMPS_PARCOURS
	, CON_CTE.CONVOYEURS LISTE_CONVOYEURS
FROM
	CONVOYEUR_CTE CON_CTE
 
INNER JOIN
	dbo.POINT_DECISION PTD
ON
	PTD.NO_POINT_DECISION = CON_CTE.NO_POINT_DECISION_TO
	AND PTD.FIN_CONVOYAGE = 1

Où la fonction ufn_CountString compte le nombre d’occurrences d'une chaine dans une autre

Temps d’exécution : (sans l'insert) !!

Temps d'analyse et de compilation de SQL Server : 
, Temps UC = 0*ms, temps écoulé = 1*ms.

SQL Server \endash  Temps d'exécution*:
, Temps UC = 0*ms, temps écoulé = 1*ms.
Temps d'analyse et de compilation de SQL Server : 
, Temps UC = 47*ms, temps écoulé = 54*ms.

(70968*ligne(s) affectée(s))
Table 'Worktable'. Nombre d'analyses 2, lectures logiques 5799963, lectures physiques 0, lectures anticipées 0, lectures logiques de données d'objets volumineux 2193336
Table 'POINT_DECISION'. Nombre d'analyses 1, lectures logiques 878863, lectures physiques 0, lectures anticipées 0, lectures logiques de données d'objets volumineux 0
Table 'CONVOYEUR'. Nombre d'analyses 1, lectures logiques 432555, lectures physiques 0, lectures anticipées 0, lectures logiques de données d'objets volumineux 0

SQL Server \endash  Temps d'exécution*:
, Temps UC = 132046*ms, temps écoulé = 135647*ms.

(SQLPro va pas être content de voir cette table)

[Batou69]

La requete pour construire la table DETAIL_CHEMIN

Code :

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
 
WITH 
	CTE
	AS (
    SELECT 
		NO_CHEMIN
		, 0 POS
		, convert( bigint, 1 ) POS_BEGIN
		, CHARINDEX( ',', LISTE_CONVOYEURS + ',' ) POS_END
		, LISTE_CONVOYEURS
	FROM
		CHEMIN
    UNION ALL
    SELECT 
		NO_CHEMIN
		, POS + 1
		, POS_END + 1
		, CHARINDEX( ',', LISTE_CONVOYEURS + ',', pos_end + 1 ) 
		, LISTE_CONVOYEURS
	FROM 
		CTE
	WHERE 
		CHARINDEX( ',', LISTE_CONVOYEURS + ',', pos_end + 1 ) > 0 )
INSERT
	detail_chemin(no_detail_chemin,position,no_chemin,no_convoyeur)
SELECT 
	row_number() over (ORDER BY NO_CHEMIN ) NO_CHEMIN
	, pos + 1 ORDRE
	, NO_CHEMIN
	, convert( int, SUBSTRING( LISTE_CONVOYEURS, pos_begin , pos_end - pos_begin ) ) NO_CONVOYEUR
FROM
	CTE
ORDER BY no_chemin,pos
OPTION ( MAXRECURSION 0 )

Celle là elle prend environ 15 minutes, je l'ai pas ré exécutée. Elle génère 1,7milllion de lignes.
Mais la encore je ne l’exécute qu'une seule fois..

[Batou69]

Enfin la requête finale qui me donne le chemin le plus court selon les étapes dans la table ETAPES:

Code :

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
 
WITH 
	up_con AS ( 
	SELECT no_convoyeur FROM etapes
	)
	, up_nb_con AS (
	SELECT
		count(*) nb_convoyeur
	FROM
		up_con
	)
	, coc_up_con AS (
	SELECT
		no_chemin
		, count(*) nb_convoyeur
	FROM
		detail_chemin coc
	INNER JOIN
		up_con
	ON
		coc.no_convoyeur = up_con.no_convoyeur
	GROUP BY
		no_chemin
	)
SELECT 
	* 
FROM 
	coc_up_con
INNER JOIN
	up_nb_con
ON
	coc_up_con.nb_convoyeur = up_nb_con.nb_convoyeur
INNER JOIN
	chemin che
ON 
	coc_up_con.no_chemin = che.no_chemin
ORDER BY 
	distance ASC

Ouf !!

L'intérêt c'est que je ne fait que la derniere requête à chaque fois que je dois trouver le meilleur chemin. De plus la table ETAPES dépend de chaque élément sur mon convoyage, je doit donc connaitre le chemin pour d'autres étapes imposées sans tout recalculer....