[PDF] Application #2 Problème du voyageur de commerce (TSP)

View - Download Application #2 Problème du voyageur de commerce (TSP)

Previous PDF

Next PDF

1/32/3 3/3

Application #2

Probleme du voyageur de commerce (TSP)

MTH6311

S. Le Digabel,

Ecole Polytechnique de Montreal

H2018 (v4)

MTH6311: Heuristiques pour le TSP1/34

1/32/3 3/3

Plan

1. Introduction

2. Formulations MIP

3. Heuristiques pour le TSP

MTH6311: Heuristiques pour le TSP2/34

1/32/3 3/3

1. Introduction

2. Formulations MIP

3. Heuristiques pour le TSP

MTH6311: Heuristiques pour le TSP3/34

1/32/3 3/3

Introduction

I

Le probleme du voyageur de commerce, ou TSP pour

Traveling-Salesman Problem, consiste, pour un graphe donne, de determiner un cycle hamiltonien dont la longueur est minimale. I Pas juste des villes et des distances : le TSP peut se rencontrer dans d'autres contextes, et/ou comme sous-probleme : problemes de logistique, de transport, d'ordonnancement, etc. (voir p roblemedu p ereNo el I Certains problemes rencontres dans l'industrie se modelisent sous la forme d'un TSP, comme l'optimisation de trajectoires de machines outils : comment percer plusieurs points sur une carte electronique le plus vite possible?

MTH6311: Heuristiques pour le TSP4/34

1/32/3 3/3

Introduction (suite)

I Un des accomplissements majeurs du TSP est l'aide donnee au domaineMixed-Integer Programming(MIP). Quasiment tout algorithme pour resoudre un MIP a d'abord ete teste sur le TSP. I La theorie de la complexite a ete etablie par W. Cook en 1971 en se basant sur l'exemple du TSP. I

Le TSP estNP-dicile.

I

Liens :

site du TSP et

TSP interactif

.MTH6311: Heuristiques pour le TSP5/34

1/32/3 3/3

Notations

I

G= (V;E).

I

Chaque sommet represente une ville.jVj=n.

I On considere que le graphe est complet :jEj=n(n1)=2. I Gest non-oriente mais les solutions doivent tenir compte d'une orientation. I cij: co^ut (distance) de l'arc(i;j)2E. On suppose que c ij=cjipour tout(i;j)2E. I On peut supposer aussi que les distances sont positives et respectent l'inegalite triangulaire c ij+cjkcikpour tousi;j;k2V. I

Pour un tourTE, on note le co^ut du tourc(T) =P

e2Tc(e).MTH6311: Heuristiques pour le TSP6/34

1/32/3 3/3

Histoire non-exhaustive du TSP

I

Premieres references en 1832.

I

1859, W.R. Hamilton : enonce avec un voyageur de commerce.

I

1949, J.B. Robinson,\On the Hamiltonian game (a

traveling-salesman problem)". Premiere reference sous sa forme moderne. I Annees 30-50 : popularise dans la communaute mathematique par M. Flood et les chercheurs du RAND. I

1954, RAND : G. Dantzig, R. Fulkerson, et S. Johnson,

\Solution of a large-scale traveling-salesman problem". Solution exacte pour les 49 capitales des etats americains (introduction des coupes et du B&B).

MTH6311: Heuristiques pour le TSP7/34

1/32/3 3/3

Histoire non-exhaustive du TSP (suite)

I

1962, M. Held et R.M. Karp : introduction d'heuristiques

basees sur la programmation dynamique. I

1973 : Heuristique de Lin and Kernighan.

I

1976 : Heuristique de Christodes.

I Annees 80 { aujourd'hui : diverses heuristiques et metaheuristiques.

MTH6311: Heuristiques pour le TSP8/34

1/32/3 3/3

Tailles des instances resolues

Annee Chercheursn1954 Dantzig, Fulkerson, Johnson 49

1971 Held, Karp 64

1975 Camerini, Fratta, Maoli 67

1977 Grotschel 120

1980 Crowder, Padberg 318

1987 Padberg, Rinaldi 532

1987 Grotschel, Holland 666

1987 Padberg, Rinaldi 2,392

1994 Applegate, Bixby, Chvatal, Cook 7,397

1998 Applegate, Bixby, Chvatal, Cook 13,509

2001 Applegate, Bixby, Chvatal, Cook 15,112

2004 Applegate, Bixby, Chvatal, Cook, Helsgaun 24,978

2005 Cook et al. 33,810

2006 Cook et al. 85,900

MTH6311: Heuristiques pour le TSP9/34

1/32/3 3/3

Probleme ouvert : le World TSP

I

Instance den= 1;904;711villes.

I www.tsp.gatech.edu/world/index.html. I

Meilleure borne actuelle (2007) :7;512;218;268.

I Meilleure solution actuelle (2011) :7;515;778;188:gapd'au plus 0.0474%.

MTH6311: Heuristiques pour le TSP10/34

1/32/3 3/3

1. Introduction

2. Formulations MIP

3. Heuristiques pour le TSP

MTH6311: Heuristiques pour le TSP11/34

1/32/3 3/3

Une premiere formulation MIP

On utilise deux variables binairesxijetxjipour chaque ar^ete (i;j)2E. La variablexijvaut1si on emprunte l'ar^ete deiversj,

0sinon.

min xP (i;j)2Ec ij(xij+xji) P i2Vi6=jx ij= 18j2V(entrer une seule fois dans chaque ville) P j2V j6=ix ij= 18i2V(sortir une seule fois de chaque ville) x ijetxji2 f0;1g 8(i;j)2EMTH6311: Heuristiques pour le TSP12/34

1/32/3 3/3

Une premiere formulation MIP

On utilise deux variables binairesxijetxjipour chaque ar^ete (i;j)2E. La variablexijvaut1si on emprunte l'ar^ete deiversj,

0sinon.

minxP (i;j)2Ec ij(xij+xji) P i2Vi6=jx ij= 18j2V(entrer une seule fois dans chaque ville) P j2V j6=ix ij= 18i2V(sortir une seule fois de chaque ville) x v1v2+xv2v3+:::+xvtv1t18S=fv1;v2;:::;vtg V (elimination des sous-tours) x ijetxji2 f0;1g 8(i;j)2EMTH6311: Heuristiques pour le TSP12/34

1/32/3 3/3

Une premiere formulation MIP (suite)

I

Contraintes d'elimination des sous-tours :

I Imposent une tournee reliant tous les sommets deG. I

Pourt= 2, revient axij+xji1.

I

Pourt= 3,xij+xjk+xki2ou bienxik+xkj+xji2

(elimine les deux tours dans un triangle). I Au pire2ncontraintes de bris de sous-tours. A-t-on besoin de toutes ces contraintes? Peut-on les generer iterativement quand un sous-tour appara^t dans une tournee? I Resolution par la technique de separation et evaluation (Branch and Bound) ou techniques plus specialisees.MTH6311: Heuristiques pour le TSP13/34

1/32/3 3/3

Une deuxieme formulation MIP (

ots et etapes) On utilise un indice supplementaires2 f1;2;:::;ng(l'etape) : la variablexij;svaut1si on va deiaja l'etapes,0sinon : min xn P i=1n P j=1 j6=in P s=1c ijxij;s n P i=1x ij;snP i=1xji;s%n+1= 08jets2 f1;2;:::;ng ot entrant = ot sortant) nP j=1n P s=1x ij;s= 18i2 f1;2;:::;ng(passer une fois par chaque ville) x ij;s2 f0;1g 8i;j;s2 f1;2;:::;ng On n'a plus besoin des contraintes d'elimination des sous-tours, mais cette formulation requiertn3variables : 50 villes donnent

125,000 variables!

MTH6311: Heuristiques pour le TSP14/34

1/32/3 3/3

1. Introduction

2. Formulations MIP

3. Heuristiques pour le TSP

MTH6311: Heuristiques pour le TSP15/34

1/32/3 3/3

Introduction

I

On voit ici deux types d'heuristiques :

I Celles qui construisent une tournee en ne partant de rien (from scratch). I Celles, plus ecaces, qui ameliorent une tournee deja existante. I Les heuristiques vues ici sont dediees au TSP et ne sont donc pas des metaheuristiques. Cependant plusieurs notions, comme les voisinages, peuvent ^etre utilisees pour denir des metaheuristiques. I Ensemble d'instances :TSPLIB.MTH6311: Heuristiques pour le TSP16/34

1/32/3 3/3

Voisin le plus proche

Nearest Neighbour (NN)[1]Choisir un sommetv12VPoserk 1[2]Tant quek < nk k+ 1choisirvkdansVn fv1;v2;:::;vk1gqui minimisecvk1;vkRetourner le tour(v1;v2;:::;vn)MTH6311: Heuristiques pour le TSP17/34

1/32/3 3/3

Voisin le plus proche (suite)

I

Facile a implementer. Complexite enO(n2).

I Sur les problemes de laTSPLIB, en moyenne,NNdonne des tours de co^ut 1.26 fois plus eleve que la valeur optimale, note

NN/OPT= 1:26.

I

Pire comportement connu :NN/OPT2logn3loglogn

(environ

3pourn= 100,4pourn= 10;000, etc.)

I Borne garantie sur la solution optimale(Rosenkrantz, Stearns, Lewis, 1977) : Si les distances sont positives et respectent l'inegalite triangulaire, alors

NN=OPT12

dlog2ne+12 (4:5pourn= 100,7:5pourn= 10;000, etc.)MTH6311: Heuristiques pour le TSP18/34

1/32/3 3/3

Methodes d'insertion

On commence avec deux noeuds et on ajoute les autres noeuds un a un. Contrairement aNN, a chaque etape, on a un tour.

Insertion Method (IM)[1]Choisirv1etv22Vet poserT= (v1;v2)(typiquement on maximisecv1v2)Poserk 2[2]Tant quek < nk k+ 1choisirvkdansVnTinserervkdansTRetournerTMTH6311: Heuristiques pour le TSP19/34

1/32/3 3/3

Methodes d'insertion (suite)

Pour un noeudvkhors du tourT:

I La quantitedT(vk) = minv2Tcvk;vrepresente la distance au tour.quotesdbs_dbs8.pdfusesText_14

[PDF] formulation peinture acrylique

[PDF] formulation peinture pdf

[PDF] formulation produit alimentaire

[PDF] formulation produit cosmétique

[PDF] formulation shampoing pdf

[PDF] formulation variationnelle des problèmes elliptiques

[PDF] formulation variationnelle éléments finis

[PDF] formulation variationnelle exemple

[PDF] formulation variationnelle problème de neumann

[PDF] formule a connaitre en gestion finance

[PDF] formule acompte devis

[PDF] formule actuariat vie

[PDF] formule aliment poule pondeuse pdf

[PDF] formule alimentaire poules pondeuses

[PDF] formule amortissement constant excel