Travelling Salesman Problem.docx

PROBLEMA DEL AGENTE VIAJERO - TSP (TRAVELLING SALESMAN PROBLEM)

JUAN CARLOS PINTO SALAMANCA 201421354

UNIVERSIDAD PEDAGÓGICA Y TECNOLÓGICA DE COLOMBIA FACULTAD SECCIONAL SOGAMOSO INGENIERÍA INDUSTRIAL MODELOS DETERMINISTICOS 2017

TRAVELLING SALESMAN PROBLEM El problema del agente viajero tiene una variación importante, y esta depende de que las distancias entre un nodo y otro sean simétricas o no, es decir, que la distancia entre A y B sea igual a la distancia entre B y A, puesto que en la práctica es muy poco probable que así sea.

Posibles rutas A-B-D-C-A A-B-C-D-A A-C-B-D-A Rutas simétricas A-D-C-B-A A-C-D-B-A A-D-B-C-A

min ∑ cij x ij xij ,ui i,j ∑ xij = 1 ∀ji ∑xij = 1 ∀i

Sujeto a ∑aij xi = bj j= 1, …., m X >= 0,

i= 1, …., n

PROGRAMACION EN GAMS

SETS I PLANTAS /R1*R5/ J CLIENTES /A, B, C, D, E/ ; *BLOQUE DATOS ENTRADA PARAMETERS

TABLE CT (I, J) COSTO TRANSPORTE A B C D 17 8 24 16 15 7 21 11 19 18 12 19 7 10 15 20 9 14 13 18

R1 R2 R3 R4 R5 ; SCALAR TRM /2995/

E 12 13 17 6 17

; *VARIABLES OBLIGTORIO VARIABLES Z OBJETIVO X(I,J) CANTIDAD A ENVIAR ;

BINARY VARIABLE X; *FREE VARIABLES ; *ECUACIONES

EQUATIONS FO FUNCION OBJETIVO R1 RESTRICCION DE CAPACIDAD R2 RESTRICCION DE DEMANDA ; FO.. Z =E= SUM((I,J),X(I,J)*CT(I,J)); R1(I).. SUM (J,X(I,J))=E=1; R2(J).. SUM (I,X(I,J))=E=1; ; *MODELO MODEL PRUEBA /ALL/ ; *SOLUCION SOLVE PRUEBA MINIMIZING Z USING MIP; *VISUALIZACION / OPCIONAL DISPLAY Z.L,X.L;