• Author / Uploaded
• Gonzalo Campos Arancibia

• Categories
• Transporte
• Algoritmos
• Informática y tecnología de la información
• Matemáticas
• Física

Citation preview

´ noma de Nuevo Leo ´n Universidad Auto ´ nica y Ele ´ctrica Facultad de Ingenier´ıa Meca ´ n de Estudios de Posgrado Divisio

COTAS LAGRANGIANAS PARA EL PROBLEMA DE RUTEO DE VEH´ICULOS EN RED TIPO ESTRELLA por

Lic. Luis Alfonso Infante Rivera ´ n al grado de en opcio

Maestr´ıa en Ciencias en Ingenier´ıa de Sistemas

´ s de los Garza, Nuevo Leo ´n San Nicola

diciembre 2012

´ noma de Nuevo Leo ´n Universidad Auto ´ nica y Ele ´ctrica Facultad de Ingenier´ıa Meca ´ n de Estudios de Posgrado Divisio

COTAS LAGRANGIANAS PARA EL PROBLEMA DE RUTEO DE VEH´ICULOS EN RED TIPO ESTRELLA por

Lic. Luis Alfonso Infante Rivera ´ n al grado de en opcio

Maestr´ıa en Ciencias en Ingenier´ıa de Sistemas

´ s de los Garza, Nuevo Leo ´n San Nicola

diciembre 2012

Universidad Aut´ onoma de Nuevo Le´ on Facultad de Ingenier´ıa Mec´ anica y El´ ectrica Divisi´ on de Estudios de Posgrado

Los miembros del Comit´e de Tesis recomendamos que la Tesis ((COTAS LAGRANGIANAS PARA EL PROBLEMA DE RUTEO DE VEH´ICULOS EN RED TIPO ESTRELLA)), realizada por el alumno Lic. Luis Alfonso Infante Rivera, con n´ umero de matr´ıcula 0849084, sea aceptada para su defensa como opci´on al grado de Maestr´ıa en Ciencias en Ingenier´ıa de Sistemas.

El Comit´e de Tesis

Dr. Igor S. Litvinchev Asesor

´ Dr. Oscar Leonel Chac´on Mondrag´on

Dr. Jos´e Antonio Marmolejo Saucedo

Revisor

Revisor Vo. Bo.

Dr. Mois´es Hinojosa Rivera Divisi´on de Estudios de Posgrado

San Nicol´as de los Garza, Nuevo Le´on, diciembre 2012

A mi madre por su apoyo incondicional

´Indice general Agradecimientos

XIII

Resumen

XIV

1. Introducci´ on

1

1.1. Estructura de la tesis . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2. Problema de ruteo de veh´ıculos (VRP) . . . . . . . . . . . . . . . . .

2

1.2.1. Problema de ruteo de veh´ıculos cl´asico y otros . . . . . . . . .

2

1.2.2. Problema de ruteo de veh´ıculos tipo estrella (VRP-Starcase) .

5

1.3. Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.4. Justificaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.5. Hip´otesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.6. Metodolog´ıa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

2. Revisi´ on de la literatura

9

2.1. Nomenclatura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

2.2. Relajaciones a problemas de optimizaci´on . . . . . . . . . . . . . . . . 11 2.2.1. Relajaci´on lineal . . . . . . . . . . . . . . . . . . . . . . . . . 12 v

´Indice general

vi

2.2.2. Relajaci´on subrogada . . . . . . . . . . . . . . . . . . . . . . . 12 2.3. Relajaci´on Lagrangiana . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3.1. La funci´on lagrangiana . . . . . . . . . . . . . . . . . . . . . . 15 2.4. Propiedades de la Relajaci´on Lagrangiana . . . . . . . . . . . . . . . 15 2.4.1. soluci´on factible lagrangeana . . . . . . . . . . . . . . . . . . . 15 2.4.2. Propiedad de Integralidad . . . . . . . . . . . . . . . . . . . . 16 2.4.3. descomposici´on en subproblemas . . . . . . . . . . . . . . . . 17 2.5. Descomposici´on lagrangiana . . . . . . . . . . . . . . . . . . . . . . . 17 2.6. Relajaci´on Lagrangiana modificada . . . . . . . . . . . . . . . . . . . 19 2.7. m´etodos para resolver la Relajaci´on Lagrangiana . . . . . . . . . . . . 21

3. Estado del arte

28

3.1. Introducci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.2. Problema de VRP con ventanas de tiempo suaves . . . . . . . . . . . 28 3.3. Problema de VRP con entregas divididas . . . . . . . . . . . . . . . . 29 3.4. Problema de ruteo en minas . . . . . . . . . . . . . . . . . . . . . . . 29 3.5. Problema de ruteo de contenedores . . . . . . . . . . . . . . . . . . . 30 3.6. Abastecimiento de comida en aviones . . . . . . . . . . . . . . . . . . 31 3.7. Problema de ruteo de veh´ıculos de emergencias medicas . . . . . . . . 33 3.8. Maquinas paralelas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4. Formulaci´ on matem´ atica

35

4.1. Introducci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

´Indice general

vii

4.2. Modelo matem´atico . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.2.1. funci´on Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.2.2. Restricciones . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

5. Construcci´ on de cotas

45

5.1. Introducci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5.2. relajaci´on 1er grupo de restricciones . . . . . . . . . . . . . . . . . . . 45 5.3. relajaci´on 2do grupo de restricciones . . . . . . . . . . . . . . . . . . 46 5.4. relajaci´on 3er grupo de restricciones . . . . . . . . . . . . . . . . . . . 47 5.5. relajaci´on 4to grupo de restricciones . . . . . . . . . . . . . . . . . . . 48 5.6. relajaci´on 5to y 6to grupo de restricciones . . . . . . . . . . . . . . . 48 5.7. M´etodo del subgradiente - detallado . . . . . . . . . . . . . . . . . . . 49 5.8. Sobre el GAP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

6. Implementaci´ on computacional

57

6.1. Introducci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 6.2. GAMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 6.3. Ilog Cplex Optimization Studio . . . . . . . . . . . . . . . . . . . . . 57 6.4. Librer´ıa Cplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 6.5. Lenguaje C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 6.6. archivos de datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 6.7. archivos de salida . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 6.8. Algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

´Indice general

viii

6.9. Simulaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

7. Experimentaci´ on computacional

68

7.1. Introducci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 7.2. Creaci´on de instancias . . . . . . . . . . . . . . . . . . . . . . . . . . 68 7.3. Experimentaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 7.3.1. Par´ametros del subgradiente . . . . . . . . . . . . . . . . . . . 70 7.3.2. C´alculo del GAP . . . . . . . . . . . . . . . . . . . . . . . . . 71 7.4. Resumen resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 7.5. Sobre la cota lagrangiana . . . . . . . . . . . . . . . . . . . . . . . . . 74 7.5.1. Resumen de resultados . . . . . . . . . . . . . . . . . . . . . . 75

8. Conclusiones

78

8.1. Trabajo futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

9. TABLAS

80

9.1. Soluciones Cplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 9.2. Par´ametros del subgradiente . . . . . . . . . . . . . . . . . . . . . . . 83 9.3. Soluciones - Relajaci´on en grupo G0

. . . . . . . . . . . . . . . . . . 85

9.4. Soluciones - Relajaci´on en grupo G1 subgradiente normal . . . . . . . 87 9.5. Soluciones - Relajaci´on en grupo G1 subgradiente modificado . . . . . 89

´Indice de figuras 1.1. Problema de ruteo de veh´ıculos como un grafo completo

. . . . . . .

4

1.2. Problema de ruteo de veh´ıculos tipo Star-case, grafo incompleto . . .

6

2.1. Interpretaci´on geom´etrica de la Relajaci´on Lagrangiana . . . . . . . . 16 2.2. Interpretaci´on geom´etrica de la descomposici´on lagrangiana . . . . . . 18 2.3. Ilustraci´on del m´etodo del gradiente . . . . . . . . . . . . . . . . . . . 22 3.1. Ruteo en minas, evitar conflictos entre veh´ıculos . . . . . . . . . . . . 31 3.2. Problema de ruteo de contenedores . . . . . . . . . . . . . . . . . . . 32 4.1. Descripci´on de funci´on objetivo . . . . . . . . . . . . . . . . . . . . . 38 4.2. Descripci´on de restricci´on 1 . . . . . . . . . . . . . . . . . . . . . . . 39 4.3. Descripci´on de restricci´on 2 . . . . . . . . . . . . . . . . . . . . . . . 40 4.4. Descripci´on de restricci´on 3 . . . . . . . . . . . . . . . . . . . . . . . 41 4.5. Descripci´on de restricci´on 4 . . . . . . . . . . . . . . . . . . . . . . . 42 4.6. Descripci´on de restricci´on 5 . . . . . . . . . . . . . . . . . . . . . . . 43 4.7. Descripci´on de restricci´on 6 . . . . . . . . . . . . . . . . . . . . . . . 44

ix

´Indice de figuras

x

5.1. GAP entre soluci´on factible y la o´ptima global . . . . . . . . . . . . . 53 5.2. Descripci´on del GAP relativo a una soluci´on lineal . . . . . . . . . . . 54 5.3. Descripci´on del GAP relativo a una soluci´on lagrangiana . . . . . . . 55

´Indice de tablas 7.1. Tipos de instancias . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 7.2. GAPs de soluciones Cplex para 8 horas y 1 hora . . . . . . . . . . . . 70 7.3. GAPs Tipo A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 7.4. GAPs Tipo B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 7.5. GAPs Tipo C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 7.6. GAPs Tipo D parte 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 7.7. GAPs Tipo D parte 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 7.8. Resumen de resultados - Relajaciones tipo A . . . . . . . . . . . . . . 75 7.9. Resumen de resultados - Relajaciones tipo B . . . . . . . . . . . . . . 75 7.10. Resumen de resultados - Relajaciones tipo C . . . . . . . . . . . . . . 76 7.11. Resumen de resultados - Relajaciones tipo D . . . . . . . . . . . . . . 76 7.12. Resumen final de resultados . . . . . . . . . . . . . . . . . . . . . . . 77 9.1. Tabla Soluciones Cplex

. . . . . . . . . . . . . . . . . . . . . . . . . 81

9.2. Tabla Soluciones Cplex - continuaci´on . . . . . . . . . . . . . . . . . . 82 9.3. Par´ametros subgradiente G1 . . . . . . . . . . . . . . . . . . . . . . . 83

xi

´Indice de tablas

xii

9.4. Par´ametros subgradiente G0 . . . . . . . . . . . . . . . . . . . . . . . 84 9.5. Relajaciones G0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 9.6. Relajaciones G0 continuaci´on . . . . . . . . . . . . . . . . . . . . . . 86 9.7. Relajaciones G1 - subgradiente normal . . . . . . . . . . . . . . . . . 87 9.8. Relajaciones G1 - subgradiente normal . . . . . . . . . . . . . . . . . 88 9.9. Relajaciones G1 - subgradiente modificado . . . . . . . . . . . . . . . 89 9.10. Relajaciones G1 - subgradiente modificado . . . . . . . . . . . . . . . 90

Agradecimientos Al consejo Nacional de Ciencia y Tecnolog´ıa (CONACYT) por el apoyo econ´omico que me brind´o durante mis estudios A mi asesor Dr. Igor S. Litvinchev por brindarme la oportunidad de trabajar ´ en este proyecto, al Dr. Oscar Leonel Chac´on Mondrag´on que con sus comentarios ayudo a terminar este trabajo y al Dr. Jos´e Antonio Marmolejo Saucedo por tomarse su tiempo para ser revisor de esta tesis

xiii

Resumen Lic. Luis Alfonso Infante Rivera. Candidato para el grado de Maestro en Ciencias en Ingenier´ıa en Sistemas

Universidad Aut´onoma de Nuevo Le´on. Facultad de Ingenier´ıa Mec´anica y El´ectrica. T´ıtulo del estudio:

COTAS LAGRANGIANAS PARA EL PROBLEMA DE RUTEO DE VEH´ICULOS EN RED TIPO ESTRELLA

N´ umero de p´aginas: 96.

´todo de estudio: El objetivo de esta investigaci´on es la obObjetivos y me tenci´on de cotas duales para el problema de ruteo de veh´ıculos en red tipo estrella con el fin de estimar con mayor precisi´on el error relativo de una soluci´on factible(obtenidas por solver comercial o heur´ıstico) de este tipo de problemas. Las cotas utilizadas fueran las obtenidas mediante la Relajaci´on Lagrangiana del problema, utilizando para obtener la soluci´on a las relajaciones (dual lagrangiano) el m´etodo del subgradiente.

xiv

Resumen

xv

Contribuciones y conlusiones: Las contribuciones de esta investigaci´on es el c´alculo de cotas lagrangianas mas precisas del problema de ruteo de veh´ıculos en red tipo estrella, estas cotas m´as precisas indican que las soluciones factibles son m´as cercanas a la soluci´on optima global de lo calculado con las cotas duales calculadas por el solver comercial(Cplex). Otra contribuci´on es la implementaci´on computacional para el c´alculo de las cotas lagrangianas. Firma del asesor: Dr. Igor S. Litvinchev

Cap´ıtulo 1

´n Introduccio 1.1 Estructura de la tesis En el primer cap´ıtulo se presenta el objetivo de la tesis, las hip´otesis implicadas, la justificaci´on de la tesis y la metodolog´ıa empleada para el desarrollo de la misma, adem´as de una breve introducci´on al problema de ruteo en general y al caso estudiado de esta tesis. En el segundo cap´ıtulo est´a dedicado a la explicaci´on de conceptos como relajaci´on y en especifico la relajaci´on lagrangiana, su utilidad y metodolog´ıa para resolver los problemas que implica (la resoluci´on del dual lagrangiano) En el tercer cap´ıtulo se discutir´a sobre el estado actual del arte sobre los problemas de ruteo o los que est´an relacionados con nuestro modelo de investigaci´on En el cuarto cap´ıtulo se explica el modelo matem´atico del problema de ruteo de veh´ıculo tipo estrella. En el quinto cap´ıtulo se explica detalladamente la manera en que se construyeron los modelos relajados para el c´alculo de cotas lagrangianas, normales y modificadas, adem´as de la estimaci´on del error relativo GAP que obtendremos con esta cota. Para el sexto cap´ıtulo se hablar´a sobre la implementaci´on computacional realizada para llevar a cabo las relajaciones. 1

´n Cap´ıtulo 1. Introduccio

2

En el s´eptimo cap´ıtulo se incluyen los experimentos computacionales y algunas estimaciones con los resultados de estos. En el octavo cap´ıtulo se presentan las conclusiones obtenidas de esta investigaci´on y algunas sugerencias para trabajo futuro. El noveno cap´ıtulo presenta m´as detalladamente los datos de las instancias y los par´ametros utilizados en las relajaciones.

1.2 Problema de ruteo de veh´ıculos (VRP) El antecedente hist´orico del problema de ruteo de veh´ıculos data de finales de la d´ecada de los 50’s del siglo XX; Dantzing y Ramser en 1959 [14]establecieron una formulaci´on matem´atica como una generalizaci´on del Problema del Agente Viajero (TSP) presentado por Flood[23], y un algoritmo de resoluci´on para dar una soluci´on cercana a la optima para el problema de suministro de gasolina en las estaciones de servicio, en el a˜ no 1964 Clarke y Wrigth propusieron una heur´ıstica voraz, (conocida como el algoritmo de los ahorros [12]); desde entonces cientos de algoritmos, modelos han sido propuestos para solucionar este problema y sus diferentes versiones por este tipo de problemas envuelve a los investigadores hasta el d´ıa de hoy [50]. En el problema de ruteo de veh´ıculos se establece que desde un dep´osito (o centro de suministros) parten veh´ıculos cargados con mercanc´ıas para ser llevadas a diversos clientes y as´ı satisfacer la demanda de los mismo. El problema es desarrollar las rutas o´ptimas que tengan que hacer los veh´ıculos para satisfacer la demanda de los clientes

´ sico y otros 1.2.1 Problema de ruteo de veh´ıculos cla En muchas organizaciones el manejo de la distribuci´on de las actividades constituye un problema de decisi´on mayor; la utilizaci´on eficiente de una flotilla de veh´ıculo, del ruteo de estos, es la parte m´as importante en los problemas de ruteo. Preguntas

´n Cap´ıtulo 1. Introduccio

3

como cuantos y de que capacidad de veh´ıculos se necesitan para obtener por ejemplo un costo m´ınimo, es lo que necesita responderse. El problema de ruteo de veh´ıculos cl´asico, presentado en la secci´on anterior, tiene como restricciones cl´asicas, la satisfacci´on de la demanda de los clientes, los veh´ıculos pueden visitar varios clientes en un solo viaje. El problema de ruteo de veh´ıculos puede ser reducido a hallar el modo en que la distancia recorrida por los veh´ıculos sea la menor posible y usar el menor n´ umero de estos. En la interpretaci´on cl´asica del VRP se permite conexiones entre clientes, proporcionando un grafo completo, al problema de una red incompleta o cuando no hay conexiones entre todos los nodos o clientes se le ha puesto poca atenci´on. Ver figura 1.1.

Figura 1.1: Problema de ruteo de veh´ıculos como un grafo completo Sin embargo en la vida real el problema de ruteo de veh´ıculos cl´asico es mucho m´as complejo, en la pr´actica se agregan quitan o modifican restricciones complicando o simplificando su resoluci´on. Una de estas variantes es el CVRP (Capacitated Vehicle Routing Problem) en

´n Cap´ıtulo 1. Introduccio

4

este problema los veh´ıculos tienen una capacidad m´axima de mercanc´ıa, esta variante es la m´as conocida y estudiada, la formulaci´on matem´atica de Dantzing y Ramer es para un problema de CVRP [14]. Otra variante es el VRPTW (Vehicle Routing Problem with Time Windows), la cual impone una restricci´on de tiempo en la llegada de veh´ıculos a los clientes, lo que hace que el problema de VRPTW tambi´en tenga un problema de Scheduling (o secuenciaci´on) por lo que tambi´en es conocido como VRPSTW. El primer caso de estudio fue presentado en 1967 por Pullen y Webb [42] y una variante adicional es la combinaci´on de ambos la cual es llamada CVRPTW (Capacitated Vehicle Routing Problem with Time Windows)[52]. El VRP es un problema tipo NP-Completo(Lenstra y Rinnooy Kan,1981 [37]), y solo puede ser resuelto en un tiempo razonable en instancias peque˜ nas, las heur´ısticas no garantizan una soluci´on exacta aunque dan buenos resultados en la pr´actica, En los ultimos 20 a˜ nos se han desarrollado de forma prometedora muchas metaheur´ısticas para la soluci´on del problema. En el libro de Golden del 2008 [7], sobre los u ´ltimos avances y t´ecnicas para la resoluci´on del problema de VRP, se pueden encontrar algunas de ´estas. El uso de m´etodos aproximados para la resoluci´on de este tipo de problemas plantea la necesidad de tener un medio para evaluar las soluciones dadas; las cotas inferiores y superiores son u ´tiles para la determinaci´on de que tan buena es una soluci´on y sustentan la base de este trabajo de investigaci´on.

1.2.2 Problema de ruteo de veh´ıculos tipo estrella (VRP-Starcase) Para este trabajo de investigaci´on nos hemos enfocado en una variante del problema de ruteo de veh´ıculos llamado VRP-Starcase o problema de ruteo de veh´ıculos en red tipo estrella. En esta variante existe el problema de la capacidad de los veh´ıculos y el problema de la ventana de tiempo de entrega a los clientes, siendo la ventana de tiempo suave por lo que los veh´ıculos pueden llegar fuera de la ventana de tiempo pero incurriendo en multa si esto ocurre.

´n Cap´ıtulo 1. Introduccio

5

Una caracter´ıstica importante en esta variante es que el veh´ıculo puede hacer varios viajes para satisfacer la demanda del cliente y que el veh´ıculo solo puede visitar a un cliente en cada uno de sus viajes. La funci´on de costo implica optimizar el costo de los viajes, el costo por las multas y el costo por adquirir los veh´ıculos que se vayan realmente a utilizar. Este modelo se da en la pr´actica por diversas situaciones; por ejemplo, algunas de ´estas son: La red de transporte tiene una configuraci´on tipo estrella, esta situaci´on ocurre en redes bajo tierra, por ejemplo (minas, tren subterr´aneo, etc.), donde efectivamente no existe una conexi´on f´ısica entre clientes, todas las conexiones pasan a trav´es del centro. La red de transporte puede ser un grafo completo, pero por reglas de la empresa no se permite utilizar la conexi´on entre los clientes, aunque esta exista; por ejemplo en el suministro de gasolina de PEMEX (Empresa de petr´oleo de M´exico), la demanda de gasolina de una estaci´on es varias veces m´as grande que la capacidad del veh´ıculo y por razones de seguridad se exige retornar al centro inmediatamente despu´es de visitar una estaci´on de gasolina. En general estas reglas pueden ser por razones de seguridad (por el material peligroso que se transporta) o tambi´en por el valor de la mercanc´ıa. Otra causa probable para que se d´e una red tipo estrella es que la demanda de los clientes sea tan grande, mucho m´as grande que la capacidad de los veh´ıculos, que haga imposible satisfacer la demanda en una sola entrega; as´ı que, aunque la red tenga un grafo completo, las conexiones cliente a cliente no se utilizan, ya que el veh´ıculo queda vaci´o despu´es de entregar a un cliente obligando a regresar al dep´osito para recarga. Una representaci´on gr´afica del problema VRP Star-case se presenta en la figura 1.2.

´n Cap´ıtulo 1. Introduccio

6

Figura 1.2: Problema de ruteo de veh´ıculos tipo Star-case, grafo incompleto

1.3 Objetivo El objetivo de esta investigaci´on es encontrar mejores cotas (mediante el c´alculo de las cotas lagrangeanas del problema) que las ofrecidas por software comercial, para el problema de ruteo de veh´ıculos en red tipo estrella, desarrollando una herramienta de c´alculo de estas cotas, para este tipo de problema.

´n 1.4 Justificacio La soluci´on de este modelo no es sencilla, consumiendo mucho tiempo en un solver comercial pudiendo llevar d´ıas llegar a la soluci´on optima global. Las soluciones factibles intermedias , obtenidas en un tiempo razonable de ejecuci´on son evaluadas por el solver (cplex) como lejanas a la soluci´on optima global[38]. La justificaci´on de este trabajo, est´a en poder ofrecer una mejor estimaci´on de que tan cerca est´a una soluci´on factible de la soluci´on optima global, dada por el solver (o un heur´ıstico).

´n Cap´ıtulo 1. Introduccio

7

´ tesis 1.5 Hipo Para el c´alculo de las cotas lagrangeanas este trabajo se basa en diversos estudios que se han hecho sobre la relajaci´on lagrangiana: la teor´ıa dada por Guignard [29] y la teor´ıa aplicada a problemas de programaci´on lineal como por ejemplo los trabajos sobre relajaciones lagrangianas en problemas de asignaci´on de Saucedo [39]. La teor´ıa nos marca que podemos obtener una cota mejor que la cota calculada por el solver cplex. La teor´ıa en que se sustenta esta hip´otesis es detallada en el segundo cap´ıtulo.

1.6 Metodolog´ıa La metodolog´ıa que se propone es construir instancias del modelo conforme al perfil de caracter´ısticas de casos reales, calcular la mejor soluci´on que se pueda obtener dentro de un l´ımite de tiempo y finalmente calcular su cota lagrangiana (de ser posible) para cada restricci´on del modelo con el m´etodo del subgradiente.

Cap´ıtulo 2

´ n de la literatura Revisio En este cap´ıtulo se detallar´a la teor´ıa en que se basa nuestra tesis para el c´alculo de cotas de nuestro problema, explicando brevemente que se entiende cuando hablamos de relajaciones y que relajaciones existen (ademas de la lagrangiana). Se da adem´as una explicaci´on de los m´etodos utilizados para resolver el problema del dual lagrangiano (o c´alculo de cota lagrangiana)

2.1 Nomenclatura Relajaci´on Subrogada: P Problema de optimizaci´on, sin relajar SPu Problema de optimizaci´on relajado SP (u) Valor optimo del problema relajado, para multiplicadores u SD Definici´on del problema del dual subrogado Relajaci´on Lagrangiana: x Vector de variables del problema f Vector de costos en funci´on objetivo λ Vector de multiplicadores LRλ Problema de optimizaci´on relajado para dado λ LR Representaci´on del problema dual lagrangiano v(LRλ ) Valor optimo del problema LRλ Descomposici´on Lagrangiana:

8

´ n de la literatura Cap´ıtulo 2. Revisio P 0 Problema de optimizaci´on modificado x Vector de variables originales del problema y Vector de variables copia (x = y) del problema LDλ Problema relajado LD1λ Subproblema relajado para x LD2λ Subproblema relajado para y Relajacion modificada: LMu,η Problema de optimizaci´on relajado u Vector de multiplicadores η Multiplicador (escalar) M´etodo del Subgradiente: k ´Indice de iteraci´on del subgradiente xk Soluci´on encontrada para el vector de variables en la iteraci´on k λk Vector de multiplicadores en la iteraci´on k Lk Soluci´on del modelo relajado en la iteraci´on k Ls Soluci´on factible del problema original γ k Valor del vector de subgradientes en la iteraci´on k θk Valor del par´ametro θ del subgradiente la iteraci´on k tk Tama˜ no del paso en la iteraci´on k M´etodo de Benders: k ´Indice de iteraci´on del m´etodo de benders LRλk Problema de optimizaci´on relajado, en iteraci´on k M P k Modelo dual del problema, en iteraci´on k zp Soluci´on al problema relajado zd Soluci´on al problema dual

9

´ n de la literatura Cap´ıtulo 2. Revisio

10

´n 2.2 Relajaciones a problemas de optimizacio En un problema de programaci´on lineal entera o mixta, la obtenci´on de la soluci´on se comporta de la siguiente manera, al crecer el tama˜ no del problema , aumenta adem´as el tiempo de c´alculo para obtener su soluci´on ´optima, pero el tiempo de c´alculo para este tipo de problemas, no crece de manera aritm´etica como se pudiera pensar, crece de una manera exponencial, haciendo dif´ıcil llegar a una soluci´on o´ptima en un tiempo conveniente, a´ un en problemas no muy grandes. Los problemas no solo se complica por su tama˜ no, sino que su misma estructura interna y la caracter´ıstica discreta de las variables(enteras o binarias) puede hacerlo complejo. Para la soluci´on de problemas lineales complejos como los anteriores, muchas veces no es posible ofrecer una soluci´on ´optima global, de hecho el hallar buenas soluciones puede ser tardado con los m´etodos matem´aticos convencionales (simplex, m´etodo de puntos interiores etc.). Las heur´ısticas o metaheur´ısticas dan buenas soluciones , sin embargo nunca se asegura que sean las o´ptimas globales, se habla de buenas soluciones, de ´optimos locales, adem´as las heur´ısticas y metaheur´ısticas pueden ser muy especificas para cada tipo de problema[46]. Otro enfoque para dar soluci´on a un problema, es relajarlo; cuando se habla de una relajaci´on , se habla de modificar el modelo matem´atico del problema, simplificarlo, hacerlo menos restrictivo, ya sea quitando restricciones, volviendo continuas las variables enteras, agrupando restricciones en una sola. Las relajaciones nos ofrecen soluciones modificadas al problema, soluciones que nos pueden servir de cotas para los m´etodos exactos o como punto de partida para encontrar buenas soluciones factibles combin´andolas con alg´ un m´etodo heur´ıstico. Por si mismas las relajaciones pueden dar soluci´on a problemas en algunos casos.

´ n de la literatura Cap´ıtulo 2. Revisio

11

´ n lineal 2.2.1 Relajacio Cuando se habla de la relajaci´on lineal de un problema, se habla de convertir las variables enteras de nuestro problema en variables continuas[51]; mediante esa simplificaci´on el tiempo de c´alculo de un problema se reduce considerablemente. Un problema puede resolverse con la utilizaci´on del m´etodo simplex. Sin embargo, la Relajaci´on Lineal ofrece una cota muy pobre para los problemas y a pesar de no ofrecer una buena cota o de no aproximar a una buena soluci´on en la mayor´ıa de los casos, se puede utilizar ya sea como referencia a otras cotas o como parte de un m´etodo m´as grande por ejemplo en el desarrollo del algoritmo de branch and bound o tambi´en en el algoritmo de soluci´on de una relajaci´on lagrangiana.

´ n subrogada 2.2.2 Relajacio Este tipo de Relajaci´on consiste en agrupar varias restricciones en una sola, Glover (1975) [28] desarroll´o una teor´ıa sobre estas mismas ya que no exist´ıa un cuerpo te´orico completo como lo era para la Relajaci´on Lagrangiana. En este tipo de Relajaci´on se trata de hallar como agrupar de la manera mas conveniente las restricciones, como seleccionar el mejor agrupamiento , ya sea para hallar la soluci´on al problema o para encontrar buenas cotas. Si tenemos un modelo matem´atico definido como

(P )

min {f x|Ax ≤ 0, x ∈ X} x

(2.1)

Donde f x es la funci´on objetivo y Ax ≤ 0 define un conjunto de restricciones, entonces podemos definir una restricci´on subrogada como la combinaci´on lineal de todo el conjunto de restricciones, asociamos cada restricci´on del conjunto con un multiplicador ui para cada restricci´on del conjunto, as´ı que nuestro modelo subrogado seria (SPu )

min {f x|uAx ≤ 0, x ∈ X} x

(2.2)

´ n de la literatura Cap´ıtulo 2. Revisio

12

Para poder mantener la desigualdad uAx ≤ 0 en la restricci´on, se forza a que todos los multiplicadores sean u ≥ 0. Este modelo relajado ofrecer´a una soluci´on menor a la ´optima del modelo primal. De esta forma la soluci´on del problema dual es hallar el conjunto ´optimo de multiplicadores u que de la soluci´on m´axima del modelo subrogado. (SD)

max {SP (u)} u≤0

(2.3)

Relajaciones subrogadas han sido aplicadas en los trabajos de Chen et al [10], Dinkel y Kochenberger[17]. Se han hecho tambi´en combinaciones del planteamiento de la Relajaci´on Subrogada con el de la Relajaci´on Lagrangiana(Espejo y Galvao[21] y Caprara et al[9]).

´ n Lagrangiana 2.3 Relajacio La Relajaci´on lagrangiana en la teor´ıa cl´asica dada por Guignard[29], Fisher[22], se habla de retirar restricciones del modelo original (el solo prescindir de restricciones ya nos habla de la existencia de un tipo de Relajaci´on). Si adem´as estas restricciones las usamos en la funci´on objetivo como penalizaci´on, esta introducci´on de penalizaci´on convierte al problema en una Relajaci´on Lagrangiana. La funci´on objetivo penalizada no solo va a depender de las variables del problema, sino de los llamados multiplicadores lagrangianos. El valor optimizado de esta funci´on depender´a del valor de estos multiplicadores. Una explicaci´on m´as formal se da a continuaci´on. Primeramente definimos nuestro problema al que llamaremos P y sera nuestra definici´on original o primal del problema, la cual tendr´a dos tipos de restricciones, la soluci´on ´optima de este problema la llamaremos z* o tambi´en v(P) como se muestra a continuaci´on. (P )

min {f x|Ax ≤ b, Cx ≤ d, x ∈ X} x

(2.4)

Las variables x de nuestro problema son restringidas a pertenecer al conjunto X el cual estar´a restringido a variables enteras o binarias. Para pasar nuestro modelo a

´ n de la literatura Cap´ıtulo 2. Revisio

13

un modelo de forma lagrangeana, bastar´a con pasar un conjunto de las restricciones a la funci´on objetivo, multiplicando ´estas con un vector de multiplicadores λ. La definici´on de nuestro problema quedara de la siguiente manera. (LRλ )

min {f x + λ(Ax ≤ b)|Cx ≤ d, x ∈ X} x

(2.5)

La elecci´on del conjunto de restricciones se relajar´a deber´a ser el conjunto de restricciones dif´ıciles, que al no ser considerado como tal simplificara mucho nuestro problema; en este caso suponemos que Ax ≤ b es el conjunto de restricciones dif´ıciles. Debido a la naturaleza de las restricciones que son del tipo ”(Ax − b) ≤ 0 ”, los multiplicadores λ tendr´an que ser positivos λ ≥ 0, siendo el problema modificado ya sin el operador de desigualdad, queda expresada como sigue. (LRλ )

min {f x + λ(Ax − b)|Cx ≤ d, x ∈ X} x

(2.6)

LRλ es el modelo matem´atico del problema relajado. La expresi´on de la funci´on objetivo en este problema LRλ queda dependiente del valor de los multiplicadores λ. La evaluaci´on de esta funci´on para dado λ dar´a un valor al que llamaremos Lz que podr´ıa ser igual o menor a la soluci´on ´optima del problema original, esto es Lz ≤ z∗. El c´alculo de la cota lagrangiana se reduce a la soluci´on del llamado problema dual lagrangiano, que en el caso de minimizaci´on no es mas que la b´ usqueda del m´aximo valor de la funci´on objetivo penalizada a minimizar, buscando entre todos los multiplicadores posibles; a este problema de b´ usqueda se le llama dual lagrangiano y queda expresado de la siguiente forma: (LR)

max v(LRλ ) λ≥0

(2.7)

donde v(LRλ ) representa una soluci´on al modelo relajado para dado un multiplicador λ. Al valor resultante de la soluci´on del dual lagrangiano le llamaremos Lz∗ y deber´a ser igual o mayor a cualquier valor Lz, pero menor o igual al valor ´optimo z∗ del problema primal, esto es Lz ≤ Lz∗ ≤ z∗. La soluci´on del dual lagrangiano es la que nos da la cota lagrangiana que es el problema de esta tesis. Para encontrar esta soluci´on al dual lagrangiano, lo que no es un problema trivial y para resolverlo

´ n de la literatura Cap´ıtulo 2. Revisio

14

se utilizan diversos m´etodos. Otra forma de expresar el problema del dual lagrangiano es describirlo de una manera equivalente con este modelo primal min {f x|Ax ≤ b, x ∈ Co{x ∈ X|Cx ≤ d}} x

(2.8)

Esta forma de expresar el dual lagrangiano, nos dice que la soluci´on estar´a en la intersecci´on de la envolvente convexa de las restricciones no relajadas y de la envolvente de las restricciones relajadas (ver figura 2.1).

Figura 2.1: Interpretaci´on geom´etrica de la Relajaci´on Lagrangiana

´ n lagrangiana 2.3.1 La funcio En la secci´on anterior se menciono el hecho de que en la Relajaci´on Lagrangiana un modelo relajado queda en funci´on de sus multiplicadores, esto nos dice que para dado un conjunto de multiplicadores existe una soluci´on optima del modelo relajado. La soluci´on Lz queda entonces en funci´on de los multiplicadores Lz(λ) = v(LRλ ) y la

´ n de la literatura Cap´ıtulo 2. Revisio

15

soluci´on del dual lagrangiano seria Lz∗ = max v(LRλ ). El objetivo de esta funci´on, λ≥0

es encontrar en el caso de minimizaci´on, el m´aximo de los m´ınimos calculados del modelo relajado. en una representaci´on gr´afica de las soluciones del modelo relajado( λ vs Lz ) ser´ıa el punto m´aximo del gr´afico (caso minimizaci´on).

´ n Lagrangiana 2.4 Propiedades de la Relajacio ´ n factible lagrangeana 2.4.1 solucio Una de las propiedades interesantes del problema dual lagrangiano son que si la soluci´on de esta es factible y adem´as el termino de holgura complementaria es λ(Ax − b) = 0, esta soluci´on lagrangiana ser´a la soluci´on o´ptima del problema original, esto es Lz∗ = z∗,.

2.4.2 Propiedad de Integralidad Otra caracter´ıstica de un Relajaci´on Lagrangiana, es que si en un modelo relajado se tiene la propiedad de Integralidad entonces el modelo relajado contiene la envolvente convexa en su espacio de soluci´on (Co{x ∈ X|Cx ≤ d} = Co{x ∈ X|Cx ≤ d}) por lo que la soluci´on al dual lagrangiano ser´a exactamente igual a la relajaci´on lineal del problema sin relajar.

´ n en subproblemas 2.4.3 descomposicio Esta propiedad refiere a la propiedad que puede tener un modelo de separarse en subproblemas al ser relajado, la separaci´on del problema en subproblemas permite resolver el problema de manera separada e incluso paralela. Estos subproblemas no necesariamente pueden ser f´acilmente resueltos, solo si tienen la condici´on de integralidad, pero podr´an tener una situaci´on m´as favorable que el problema original

´ n de la literatura Cap´ıtulo 2. Revisio

16

´ n lagrangiana 2.5 Descomposicio La descomposici´on lagrangiana refiere a una manera de construir una Relajaci´on Lagrangiana; la descomposici´on lagrangiana tiene la capacidad de dividir un problema en dos subproblemas, mediante una reformulaci´on al modelo original. Se crea una nueva variable artificial llamada ”variable layering.o ”variable spliting”,siendo esta nueva variable, una variable espejo (esto es una variable con el mismo valor que otra) de otra original del modelo , esta t´ecnica de crear estructuras de problemas aprovechables a trav´es de una variable artificial se estudia por Glover y Klingman (1988) [18]. No debemos confundir esto con la descomposici´on en subproblemas que se da al simplemente relajar una restricci´on del modelo dada anteriormente, ya que en la descomposici´on lagrangiana se obliga a la separaci´on del problema en por lo menos dos subproblemas, la descomposici´on en subproblemas dada anteriormente, no hace uso de una variable artificial . Una descomposici´on lagrangiana puede tambi´en aprovechar la propiedad de descomposici´on en subproblemas si es posible. A continuaci´on se presenta una interpretaci´on geom´etrica de la descomposici´on lagrangiana. La descomposici´on lagrangiana puede ser mejor que relajar cada restricci´on individualmente, adem´as a diferencia de la Relajaci´on Lagrangiana normal esta Relajaci´on usa las envolventes convexas de cada conjunto de restricciones y no de solo uno solo (ver figura 2.2).

Tenemos un problema P definido con el siguiente modelo matem´atico (P )

min {f x|Ax ≤ b, Cx ≤ d, x ∈ X} x

(2.9)

El problema anterior tiene dos grupos de restricciones; este modelo mediante la creaci´on de las variables artificiales y, que asignamos en un grupo de restricciones nuevo con las variables x originales del modelo, y de ese modo se logra construir un nuevo modelo equivalente. (P )

min {f x|Ax ≤ b, Cy ≤ d, x = y, x ∈ X, y ∈ X} x,y

(2.10)

´ n de la literatura Cap´ıtulo 2. Revisio

17

Figura 2.2: Interpretaci´on geom´etrica de la descomposici´on lagrangiana Este nuevo modelo posibilita la divisi´on del problema en dos subproblemas al relajarse la restricci´on de igualdad x = y (LD)

min {f x + λ(y − x)|Ax ≤ b, Cy ≤ d, x ∈ X, y ∈ X} x,y

(2.11)

Agrupando los t´erminos el problema queda como : (LDλ )

min {(f − λ)x|Ax ≤ b, x ∈ X} + min {λy|Cy ≤ d, y ∈ X} x

y

(2.12)

lo que nos deja ver dos modelos que se pueden resolver individualmente LDλ = LD1λ + LD1λ (LD1λ ) (LD2λ )

min {(f − λ)x|Ax ≤ b, x ∈ X}

(2.13)

min {λy|Cy ≤ d, y ∈ X}

(2.14)

x

y

La cota calculada de este modelo modificado puede ser mejor que relajar individualmente cada grupo de restricciones del modelo original, (ver figura 2.2)

´ n de la literatura Cap´ıtulo 2. Revisio

18

´ n Lagrangiana modificada 2.6 Relajacio Como extensi´on a la teor´ıa cl´asica de la Relajaci´on Lagrangiana tenemos la Relajaci´on Lagrangiana modificada. Esta extensi´on trata de aprovechar las caracter´ısticas que podr´ıa tener un modelo al ser dividido en dos problemas diferentes, se podr´ıa tener una soluci´on f´acil o de poder ser divididos en peque˜ nos problemas. La Relajaci´on Lagrangiana modificada utiliza variables artificiales; sin embargo a diferencia de la descomposici´on lagrangiana que introduce solamente un grupo de restricciones al modelo, la Relajaci´on Lagrangiana modificada introduce varios grupos que intentan tener el mismo efecto. La descomposici´on lagrangiana puede involucrar m´as c´alculos debido a que puede contener un numero de multiplicadores tan alto como el de las variables involucradas ya que las variables artificiales son copias de la original. La Relajaci´on Lagrangiana modificada utiliza un conjunto menor de restricciones y por lo tanto un n´ umero menor de multiplicadores. Una explicaci´on formal es la siguiente, dado el modelo matem´atico primal que se expresa como

(P )

z∗ = max {cx|Dx ≤ b, Ax ≤ d, x ∈ U } x

(2.15)

introducimos la variable artificial y, y volvemos a escribir el modelo de la siguiente forma (P 0 )

zM = max {cx|Dx ≤ Dy, cx = cy, x ∈ X, y ∈ W } x

(2.16)

este modelo no es completamente id´entico al original pero los valores para (x, y) = (x∗, x∗) son factibles en este modelo , donde x∗ son los valores en x para la soluci´on o´ptima global. Hay que hacer notar que z∗ ≤ zM , y si sabemos adem´as que el conjunto X = {x ∈ U |Ax ≤ b}, y que el conjunto W implica la restricci´on Dy ≤ d, esto hace que la soluci´on o´ptima del modelo modificado sea factible en el modelo original. Por lo que sabemos una soluci´on factible en ambos modelos podr´ıa ser menor o igual al ´optimo as´ı que z∗ ≤ zM , pero como sabemos que no puede ser

´ n de la literatura Cap´ıtulo 2. Revisio

19

menor entonces z∗ = zM . Al hacer la Relajaci´on de este modelo, llevando los grupos de restricci´on de enlace de variables a relajar nos queda un modelo que se puede ver como dos subproblemas; esto queda como (LMu,η )

zM (u, η) = max {(1 − v)cx − uDx} + max {η ∗ cy − uDy} x∈X

y∈W

(2.17)

la cota zM (u, v) contiene apenas m+1 multiplicadores (un vector u y un escalar η) mientras que la descomposici´on lagrangiana utiliza una mayor cantidad de multiplicadores. Otra forma de ver la cota modificada es como la minimizaci´on de los t´erminos complementarios de una relajaci´on ,como esto (LMu )

max {cx + u(d − Dx)} − min {u(d − Dy)} x∈X

y∈W

(2.18)

as´ı que podemos observar a la cota modificada como un ajuste a la relajaci´on al restarle una minimizaci´on de los t´erminos complementarios

´todos para resolver la Relajacio ´n 2.7 me Lagrangiana ´todo del subgradiente me Los m´etodos de gradientes son utilizados para obtener el m´aximo valor en una funci´on c´oncava, tambi´en llamados m´etodos de ascensos m´as pronunciados, buscan una soluci´on o´ptima a un problema partiendo desde un punto inicial x0 pasando por una secuencia de {x0 , x1 , ..., xn } ,hasta eventualmente converger a una soluci´on. Cada nuevo punto en xi es calculado con una funci´on de ascenso; Guta[31] desarrolla detalladamente el tema de los m´etodos del subgradiente en relajaciones lagrangianas. xn+1 = xn + tn ∇f (xn )

(2.19)

donde tn es la longitud del paso de b´ usqueda y ∇f (xn ) es el vector gradiente de la funci´on f en xn ; esto es, el nuevo x est´a encaminado en la direcci´on de b´ usqueda dada por el gradiente(ver figura 2.3).

´ n de la literatura Cap´ıtulo 2. Revisio

20

Figura 2.3: Ilustraci´on del m´etodo del gradiente En nuestro caso, la funci´on no es diferenciable ya que es una funci´on discreta y no es continua. El m´etodo del subgradiente es una adaptaci´on del m´etodo de los gradientes, los gradientes son remplazados por subgradientes. los m´etodos basados en los subgradientes no aseguran una soluci´on exacta al problema, sin embargo son r´apidos y f´aciles de implementar. Para aplicar el m´etodo del subgradiente debemos tener la funci´on objetivo relajada. Lk = min {f xk + λk (Axk − b)} xk

(2.20)

donde λ es el vector de multiplicadores lagrangianos para el grupo de restricciones relajadas, x representa las variables soluci´on y el ´ındice k el numero de iteraci´on del subgradiente , para obtener e identificar el subgradiente se deriva la funci´on objetivo con respecto a λ, as´ı que nuestro gradiente ser´ıa: γ k = Axk − b

(2.21)

Se comienza calculando un valor de la funci´on lagrangiana dado un vector λ arbitrario (a´ unque en la pr´actica se utilizan los valores duales de una Relajaci´on

´ n de la literatura Cap´ıtulo 2. Revisio

21

lineal por ofrecer una mejor aproximaci´on inicial, o simplemente un vector inicial donde todos los multiplicadores sean cero). Una vez calculada esa soluci´on de la funci´on lagrangiana, se procede a calcular los subgradientes γ dada la f´ormula 2.21, Podemos notar que la evaluaci´on de subgradientes es parecido a la evaluaci´on de las restricciones relajadas Con el valor obtenido de la funci´on lagrangiana y el c´alculo de los subgradientes procedemos a calcular el tama˜ no del paso tk con la siguiente formula: tk =

θk ∗ (Ls − Lk (λk )) kγk k2

(2.22)

donde Ls es el valor de una soluci´on factible del modelo original, obtenido ya sea por un m´etodo heur´ıstico o por el valor aproximado dado por un software comercial, Lk es la soluci´on obtenida del modelo relajado en la iteraci´on k y θk es un par´ametro de ajuste del m´etodo del subgradiente (com´ unmente inicia en 2 ). Si despu´es de k iteraciones consecutivas con un valor fijo de θ el valor de la soluci´on no mejora entonces se procede a modificar ese valor θ utilizando 2θ . Para la siguiente iteraci´on del subgradiente; el tama˜ no de paso multiplicado por el subgradiente gamma correspondiente nos da la magnitud de cuanto deber´an modificarse los multiplicadores para la siguiente iteraci´on, la siguiente f´ormula calcula el valor de los nuevos multiplicadores. λk+1 = λk + tk ∗ γ k

(2.23)

Este m´etodo es el llamado subgradiente puro, pero existen otras variantes de este m´etodo que intentan hacer que el subgradiente converga mas r´apido, tales como el m´etodo de deflecci´on del subgradiente, el m´etodo del subgradiente condicional utilizados para disminuir el zig-zag en la resoluci´on del subgradiente puro.

´todo de benders o de generacio ´ n de restricciones me Este m´etodo tambi´en llamado generador de restricciones, es tambi´en un m´etodo iterativo, en donde el modelo original es relajado para hacer m´as f´acil su soluci´on[5],

´ n de la literatura Cap´ıtulo 2. Revisio

22

se construye adem´as un problema dual que tendr´ıa como variables los multiplicadores, las restricciones de este modelo dual se ir´ıan adicionando una a una en cada iteraci´on con una funci´on generadora de restricciones.El algoritmo inicia con una soluci´on o´ptima del modelo relajado (podemos utilizar como multiplicadores iniciales λ1 un valor aleatorio o simplemente cero).

(LRλ1 )

zp = min {f x + λ(Ax − b)|Cx ≤ d, x ∈ X} x

(2.24)

Obtenemos un valor o´ptimo de soluci´on inicial zp con x1 y comenzamos la construcci´on del modelo dual. Funci´on objetivo del modelo dual zd = max θ λ

(2.25)

Agregamos una restricci´on con la funci´on generadora de restricciones

θ = f x1 + λ(Ax1 − b)

(2.26)

Obtendremos una soluci´on al sistema, con un valor o´ptimo de soluci´on zd y multiplicadores igual a λ2 . Con este nuevo valor de multiplicadores, regresamos al problema relajado original y resolvemos, d´andonos una soluci´on ´optima con valor zp y x2 , con lo que podemos agregar otra restricci´on al modelo dual con el nuevo valor repiti´endose el proceso entre modelo original y dual La funci´on generadora de restricciones para la iteraci´on k seria expresada como

θ = f xk + λ(Axk − b)

(2.27)

el modelo dual queda expresado de la siguiente forma

MP k

zp = max {θ|θ ≤ f xh + λ(Axh − b), h = 1, 2...k} λ

(2.28)

Y el modelo relajado original podemos expresarlo en una iteraci´on k como LRλk

zp = min {f x + λ(Ax ≤ b)|Cx ≤ d, x ∈ X} x

(2.29)

´ n de la literatura Cap´ıtulo 2. Revisio

23

El algoritmo de este m´etodo terminar´ıa cuando los ´optimos de la soluci´on del modelo relajado y del dual sean iguales; esto es zp = zd quedando la soluci´on del dual lagrangiano en el valor final de convergencia. El m´etodo de benders es un algoritmo exacto para encontrar el dual lagrangiano, pero es m´as costoso computacionalmente.

´ n de columnas Generacio An´alogo al m´etodo de generaci´on de restricciones se tiene el m´etodo de generaci´on de columnas (este m´etodo puede ser visto como una aplicaci´on del m´etodo de Dantzing Wolfe [16][15][6], el cual consiste en reformular el problema de tal modo que las columnas del modelo correspondan a soluci´ones factibles de un subconjunto de restricciones del problema, en este se elige un peque˜ no conjunto de columnas y durante las iteraci´ones se van sumando columnas, el modelo para generaci´on de columnas resulta podemos obtenerlo del modelo dual max {min {f x + λ(Ax − b)|Cx ≤ d, x ∈ X}} λ≥0

(2.30)

x

que expresado como una envolvente convexa queda min {f x|Ax ≤ b, x ∈ conv{x ∈ X|Cx ≤ d}}

(2.31)

x

Para utilizar el m´etodo de generaci´on de columnas debemos identificar las restricciones de acoplamiento Ax ≤ b ,las cuales se combinar´an con una soluci´on P Axk y una nueva variable µk , tal que µk (Axk ) ≤ b , partiendo del hecho de que k∈K P se trata de una combinaci´on convexa µk = 1 , el modelo completo queda como: k∈K

min { x

X k∈K

µk (f xk )|

X

k∈K

µk (Axk ) ≤ b,

X

µk = 1, µ ≥ 0}

(2.32)

k∈K

Una elecci´on adecuada para xk esta en elegir entre cualquiera de todos los puntos de la envolvente convexa o solo de sus puntos extremos x ∈ Co{x ∈ X|Cx ≤ d} P P , para obtener los valores de la variable original se tiene x = µk xk con µk = 1 k∈K

k∈K

´ n de la literatura Cap´ıtulo 2. Revisio

24

and µk ≥ 0. La separaci´on de un problema en un problema maestro y un subproblema es equivalente a la separaci´on de restricciones guardadas y las restricciones dualizadas. Las columnas generadas son soluciones de subproblemas enteros que tienen las mismas restricciones de los subproblemas lagrangianos; al igual que benders, es un m´etodo exacto para el c´alculo del dual lagrangiano.

´todos Combinados me Una descripci´on detallada de estos m´etodos puede encontrarse Hiriart-Urruty y Lemarechal[36],[35],[32] , kiwiel [34] y frangioni [24] introdujeron una extensi´on a los m´etodos de subgradientes, llamados m´etodos combinados en los cuales la informaci´on pasada es recolectada para proveer una mejor aproximaci´on a la funci´on lagrangiana.

´todos h´ıbridos de dos fases me En este m´etodo presentado en 1994 por Guignard y Zhu [30] se hace uso de dos m´etodos: el del subgradiente y el de generaci´on de restricciones. En una primera fase se hace uso del subgradiente para ajustar los multiplicadores y al mismo tiempo las restricciones correspondientes a las soluciones conocidas de los subproblemas lagrangianos son adheridas al problema maestro LP; esto es, hacer uso del m´etodo de generaci´on de restricciones en la segunda fase. Tambi´en se puede usar generaci´on de columnas en la segunda fase [25] el cual es descrito por Guignard y Freville.

El algoritmo de Volumen VA Este algoritmo propuesto por Barahona y Anbil(2000) [3] es una extensi´on mas al m´etodo del subgradiente, pero tambi´en puede ser visto como una forma aproximada de la descomposici´on de Dantzing-Wolfe. Dado un problema de programaci´on entera (IP) con dos restricciones (r1 y r2)

´ n de la literatura Cap´ıtulo 2. Revisio

25

(IP ) min cx (r1)

Ax ≥ b

st :

Dx ≥ d

(r2)

x ∈ Zn+ minimizando la f´ormulaci´on (IP ) min cx −

Ax ≥ b

st :

x ∈ X = {x ∈ Zn+ , Dx ≥ d} su Relajaci´on Lagrangiana con respecto a r1 puede quedar expresado con zona convexa de X z∗ min cx st :

Ax ≥ b

x ∈ conv(X) La Relajaci´on Lagrangiana de este modelo puede reformularse, haciendo de x una combinaci´on convexa de xi , haciendo esto podemos hacer una reformulaci´on similar al esquema de Dantzing-Wolfe para agregaci´on de columnas φ∗ min cx st :

Ax ≥ b x ∈ conv(X) = {x : x =

P i P µx , µ = 1, µ ≥ 0} i

i

El cual puede ser rescrito como: P i φ∗ min (cx )µi i P st : (Axi − b)µi ≥ 0 i P µi = 1 i

µi ≥ 0 Este problema puede ser reformulado con el dual: φ∗ max z st :

z + u(Axi − b) ≤ cxi

u ∈ Rn+ , z ∈ R o tambi´en :

´ n de la literatura Cap´ıtulo 2. Revisio

26

φ∗ max z st :

z ≤ ub + (c − uA)xi

u ∈ Rn+ , z ∈ R La formulaci´on con par´ametro u es equivalente al lagrangiano dual z = φ(u), por ultimo podemos expresar el problema solo minimizando la parte de holgura (c − uA)xi , de tal forma φ(u) = ub + min{(c − uA)xi : xi ∈ X, ∀i}

(2.33)

El c´alculo de los pesos µ se realiza con la estimaci´on de ciertos vol´ umenes asociados a las caras activas en una soluci´on o´ptima dual.

Cap´ıtulo 3

Estado del arte ´n 3.1 Introduccio En este apartado se har´a un recorrido de los problemas actuales e hist´oricos del problema ruteo de veh´ıculos, y de otros problemas en la investigaci´on de operaciones, describiendo su relaci´on con nuestro modelo

3.2 Problema de VRP con ventanas de tiempo suaves En este problema existen un numero de veh´ıculos localizados en un dep´osito, los cuales tienen que satisfacer la demanda de bienes de un conjunto de clientes ubicados en distintas localizaciones geogr´aficas. Los veh´ıculos tienen una capacidad limitada y existe un intervalo (o ventana de tiempo) en el que los clientes deben ser satisfechos, adem´as se debe retornar al dep´osito. A este modelo se le llama VRPTW pero existen otros casos donde se permite llegar fuera de la ventana de tiempo pero causando una penalidad, Valverde et al (2007)[8] realizan una investigaci´on del uso de programaci´on por metas para modelar el problema, donde el modelo intenta reflejar las penalidades por las violaciones a la ventana de tiempo, a trav´es de variables de desviaci´on. Este modelo permite evaluar las consecuencias por poner diferentes penalidades por las violaciones a las ventanas de tiempo, dependientes

27

Cap´ıtulo 3. Estado del arte

28

de los clientes. Tambi´en se han propuesto heur´ısticas como Eglese et al (2008) [26], los cuales propusieron una b´ usqueda tab´ u con memoria adaptativa para resolver el problema. Ellos tambi´en mencionan que este tipo de problemas puede contener al de ventanas de tiempo duras e incluso llegar a resolverlo con los adecuados coeficientes de penalizaci´on.

3.3 Problema de VRP con entregas divididas Este tipo de ruteo tambi´en llamado SDVRP fue introducido en la literatura por Dror y Trudeau (1989) [20] quienes definieron algunas propiedades estructurales y propusieron una b´ usqueda local, Dror et al [19] formularon un modelo de programaci´on entera, aplicaciones reales del problema han sido abordadas por Sierksma y Tijseen [47] que consideraron el problema de determinar la agenda de vuelos de helic´opteros para el intercambio de personal en plataformas. Otro problema es presentado por Archetti et al [2] que consideraron un problema de recolecci´on de residuos donde los veh´ıculos ten´ıa muy poca capacidad y los clientes una gran demanda; ellos tambi´en consideraron restricciones como ventanas de tiempo, priorizaci´on en los clientes y diferentes tipos de veh´ıculos y residuos, ellos propusieron un heur´ıstica de b´ usqueda tabu ara resolver el problema.

3.4 Problema de ruteo en minas Entre los problemas de optimizaci´on de la industria minera, se encuentra el problema del transporte del mineral en minas subterr´aneas, el del manejo de la flotilla de veh´ıculos de acarreo, en la pr´actica el supervisor asigna los operadores para los veh´ıculos tomando en cuenta el estado de los recursos pero son los operadores de los veh´ıculos los que toman las decisiones de ruteo de acuerdo a su experiencia Cordova et al 2004 [13]. Esta problem´atica ha sido tratada por Gamache et al(2005)[27], que intentan resolver el problema de ruteo implementando el algoritmo del camino

Cap´ıtulo 3. Estado del arte

29

m´as corto pero con estrategia de veh´ıculo por veh´ıculo y de manera m´as integral en el 2006 Beaulieu y Gamache [4] estudian el problema de gesti´on de veh´ıculos y desarrollan un algoritmo de enumeraci´on basado en programaci´on din´amica para el enrutamiento y programaci´on de veh´ıculos que se mueven solo en dos sentidos (bidireccionales) en una red de transporte con un solo carril; en esta nueva propuesta o extensi´on se intenta aprovechar el modo bidireccional de desplazamiento de los veh´ıculos en los segmentos del ruteo resultando una m´as eficiente formulaci´on. El veh´ıculo comienza su recorrido desde un punto inicial hasta su destino y se trata de encontrar la mejor ruta y programaci´on posible para cada veh´ıculo de tal manera que haga su recorrido en el menor tiempo posible, tratando tambi´en de evitar conflictos entre las rutas de los veh´ıculos como se ve en la figura 3.1, el algoritmo toma tambi´en en cuenta el movimiento bidireccional del veh´ıculo (hacia adelante y hacia atr´as) pero asegurando que el destino (punto de servicio) es alcanzado por un movimiento hacia adelante; en este tipo de ambientes(minas subterr´aneas) las rutas son muy limitadas y adem´as solo permiten un veh´ıculo a la vez, com´ unmente se elige una u ´nica ruta , este problema ha sido clasificado por Peters et al [41] como uno de los m´as dif´ıciles en los sistemas de veh´ıculos guiados (AGV).

Figura 3.1: Ruteo en minas, evitar conflictos entre veh´ıculos

Cap´ıtulo 3. Estado del arte

30

3.5 Problema de ruteo de contenedores Este problema concierne a la entrega y recolecci´on de bienes. En este problema de transportaci´on el veh´ıculo lleva un contenedor a un cliente donde este es vaciado o llenado; el veh´ıculo parte de una terminal a un cliente con un contenedor donde este es vaciado o llenado y regresa a la terminal con el contenedor, Lo anterior estable que el contenedor puede estar vacio e ir con el cliente de recolecci´on que lo llenara; o ir con el de entrega que vaciar´a para regresar con el contenedor vacio en lo que se llama triangulaci´on de ordenes (de importaci´on y exportaci´on). Esta segunda alternativa es la m´as econ´omica, Imai et al (2007)[33] utilizan un m´etodo heur´ıstico basado en relajaciones lagrangianas para resolver el problema, siendo el m´etodo eficiente en instancias grandes , Reinhardt et al(2012)[43] dise˜ na un modelo matem´atico para resolver un problema de este tipo, en el cual se reciben ´ordenes con ventanas de tiempo establecidas por los clientes y los contenedores de los veh´ıculos deben ser del mismo tama˜ no para poder hacer una triangulaci´on. No siempre ser´a posible la triangulaci´on, por lo que se requiere buscar la mejor combinaci´on de viajes triangulados y simples. Podemos ver c´omo ser´ıan los tipos de viajes posibles en la figura 3.2. 3.2. Este modelo ejemplifica el caso de tener solo una terminal en donde salen los veh´ıculos con sus contenedores, que pueden ser de distintos tama˜ nos.

3.6 Abastecimiento de comida en aviones Un problema de este tipo se estudi´o por Sze (2012) et al[48]. Este problema trata del transporte de alimentos desde un centro (la cocina central) hacia las aeronaves. Se establecen restricciones para que los veh´ıculos de suministro en cuanto a su capacidad para abastecer una limitada cantidad de aeronaves; otra restricci´on es el tiempo en que la comida tarde en salir y ser entregada a las aeronaves, estableci´endose un periodo de tiempo predeterminado desde la salida del centro de preparaci´on la comida. Adicionalmente, los equipos de carga (personas) tienen un

Cap´ıtulo 3. Estado del arte

31

Figura 3.2: Problema de ruteo de contenedores per´ıodo de descanso. El objetivo fundamental del problema es satisfacer a todos los clientes (aeronaves) pero debido a las peque˜ nas ventanas de tiempo y a los distintos tipos de aeronaves, posiblemente m´as de un equipo se requiera para satisfacer la demanda del cliente (aeronave). Otras restricciones son la capacidad del veh´ıculo de carga. Todos los viajes deben ser agendados y tener su tiempo l´ımite, siendo obligado que los clientes sean visitados una vez en la ventana de tiempo dispuesta para ellos. Tiempos de carga y descarga de paquetes de comida son incluidos en los tiempos de viaje por conveniencia. Para este problema, por ser de gran tama˜ no y complejidad, se propuso una heur´ıstica de inserci´on de viajes r´apida y que diera buenas soluciones

Cap´ıtulo 3. Estado del arte

32

3.7 Problema de ruteo de veh´ıculos de emergencias medicas El problema de ruteo de veh´ıculos de emergencias es un problema de ruteo din´amico, donde los veh´ıculos tienen ventanas de tiempo de servicio. El viaje de los veh´ıculos es hacia un solo cliente para proporcionar el servicio necesario (consulta, traslado, etc.) y se debe volver al punto de origen. Existen prioridades de servicio y adem´as es problema de naturaleza din´amica, va cambiando con el tiempo, conforme se van recibiendo llamadas de los clientes y conforme se les va dando el servicio, Rengifo et al(2012)[44] proponen un modelo matem´atico para este tipo de problema de ruteo para una empresa que provee este servicio de veh´ıculos de emergencia en Medell´ın Colombia. En este modelo se manejan distintos tiempos de servicio, dependiendo de la naturaleza de la llamada hecha por el cliente. Se tiene el ´area total de servicio dividida en zonas con un n´ umero de posibles clientes y puntos donde pudieran ubicarse los veh´ıculos. En este problema real existen dificultades para poder dar el servicio en los tiempos reglamentados (para mantener la calidad del servicio) por varias razones: parque vehicular limitado , dificultad para evaluar el impacto de una decisi´on de asignaci´on de veh´ıculos en las futuras asignaciones. En este problema real se intenta optimizar la operaci´on de la flotilla de veh´ıculos con que se dispone antes de acudir a una alta inversi´on por la compra de veh´ıculos nuevos.

3.8 Maquinas paralelas En este problema se tiene un conjunto de maquinas y un conjunto de trabajos a resolver , Zhilong y Powell (1996) [11] propusieron un m´etodo exacto de soluci´on , basado en la descomposici´on de Dantzing Wolfe para un caso de m´aquinas paralelas que inclu´ıa la secuenciaci´on de los trabajos y cuyo objetivo era minimizar el tiempo de la programaci´on de trabajos.

Cap´ıtulo 3. Estado del arte

33

Takashi et al(2007)[49] proponen una relajaci´on lagrangiana para una variante de este tipo de problemas, en la cual se incluyen estaciones de trabajo donde se ubican las m´aquinas y los trabajos se procesan a trav´es de estas estaciones pasando por un buffer intermedio entre estas para ser enteramente realizados. Se trabaja tambi´en con un modelo con ventanas de tiempo y capacidad limitada de buffer; el objetivo es minimizar el peso de las violaciones a las ventanas de tiempo. Ellos encontraron que trabajaba bien La relajaci´on lagrangiana a las restricciones de capacidad y si el n´ umero de estaciones aumentaba pod´ıa usarse conjuntamente la restricciones de precedencia (las que definen en qu´e momento comienza un nuevo trabajo). Una forma aproximada de ver el problema de VRP-Starcase es hacer una analog´ıa con el de m´aquinas paralelas , donde los veh´ıculos podr´ıan hacer la funci´on de maquinas trabajando de manera paralela para hacer un trabajo.

Cap´ıtulo 4

´ n matema ´ tica Formulacio ´n 4.1 Introduccio El problema VRP-Starcase, es un problema de ruteo de veh´ıculos en el cual los veh´ıculos solo pueden visitar un cliente y regresar al dep´osito para recarga. Los veh´ıculos pueden hacer solo un cierto n´ umero de viajes para satisfacer la demanda del cliente y tambi´en se tienen penalizaciones con el cliente por llegar antes o despu´es de lo esperado (ventana de tiempo suave). El objetivo es minimizar los costos por viajes realizados, veh´ıculos utilizados y costos por multas; la soluci´on dar´a como resultados: la flotilla de veh´ıculos m´as adecuada , las rutas de los veh´ıculos, y la secuenciaci´on de los viajes a realizar por los veh´ıculos. El modelo planteado para resolver este problema es un modelo de programaci´on lineal entera mixta. Podemos observar en este modelo matem´atico que no existen restricciones de subtour como en modelos cl´asicos ya que al no existir rutas entre clientes, los subtour son inexistentes.

´ tico 4.2 Modelo matema Los par´ametros del modelo son costos por viajes, utilizaci´on de veh´ıculos, tiempos de viaje, horarios de entrega , demandas de clientes, multas, entre otros, que se listan en esta secci´on 34

´ n matema ´ tica Cap´ıtulo 4. Formulacio

35

Indices de arreglos i.−

N´ umero de cliente (0 para dep´osito)

j.−

N´ umero de viaje, relacionado directamente con el veh´ıculo, existiendo una cantidad de via

k.−

N´ umero de veh´ıculo, no confundir con tipo de veh´ıculo

Par´ametros de veh´ıculos Jk Conjunto de viajes de veh´ıculo k. JMk

M´aximo n´ umero de viajes de veh´ıculo k.

Cik

Costo de viaje redondo desde el dep´osito hacia el cliente i del veh´ıculo k.

qk

Capacidad del veh´ıculo k.

tik

Tiempo de viaje (ida) desde el dep´osito hacia el cliente i por el veh´ıculo k.

fk

Costo de adquisici´on o utilizaci´on de veh´ıculo k.

Par´ametros de clientes di .− Demanda del cliente i

Par´ametros de ventanas de tiempo Ei

Tiempo inicial para comienzo de entrega de mercanc´ıa a cliente i.

Li

Tiempo final para entrega de mercanc´ıa a cliente i.

eik

Multa por entrega de mercanc´ıa de veh´ıculo k antes de tiempo inicial de cliente i.

lik

Multa por entrega de mercanc´ıa de veh´ıculo k despu´es de tiempo final de cliente i.

M

Constante que representa un valor muy grande.

las variables a utilizar son:

´ n matema ´ tica Cap´ıtulo 4. Formulacio xijk

36

Variable de decisi´on, indica si un cliente i es visitado por un veh´ıculo k, en el viaje j de ese mismo veh´ıculo (Xijk = 1 si es visitado).

yk

Variable de decisi´on, indica si un veh´ıculo es utilizado (y = 1 si es visitado).

sjk

Tiempo inicial de viaje j del veh´ıculo k.

− wik

Tiempo de entrega de mercanc´ıa de veh´ıculo k antes de tiempo inicial de cliente i.

+ wik

Tiempo por entrega de mercanc´ıa de veh´ıculo k despu´es de tiempo final de cliente i.

La naturaleza de estas variables es: − + x, y ∈ {0, 1} y sjk , wik , wik ≥0

Como tenemos variables binarias y continuas, tenemos un modelo de programaci´on lineal entera-mixto Se presenta el modelo matem´atico para el problema: (0)

P P fk y k +

min :

k

(1) x0jk +

P

+ cik xijk + eik wijk + lik wijk




i,j∈Jk ,k

xijk = 1

∀j ∈ Jk , k

i≥1

(2)

P

qk xijk ≥ di

∀i 6= 0

j∈Jk ,k

(3) JMk −

P

x0,j,k ≤ yk JMk

∀k

j∈Jk

(4) sj+1,k ≥ sjk +

P 2tik xijk

∀j ∈ Jk , k

i,k (5) wijk ≥ Ei xijk − (sjk + tik xijk )

∀ i 6= 0, j ∈ Jk , k

+ (6) wijk ≥ sjk + tik xijk − Li − M (1 − xijk )

∀ i 6= 0, j ∈ Jk , k

A continuaci´on se da una explicaci´on de c´omo funcionan y para qu´e sirven cada una de las restricciones y la funci´on objetivo.

´ n matema ´ tica Cap´ıtulo 4. Formulacio

37

´ n Objetivo 4.2.1 funcio La funci´on objetivo consta de tres partes, la primera calcula los costos de adquisici´on o utilizaci´on de los veh´ıculos realmente utilizados, la segunda parte calcula el costo de los viajes realizados y la ultima los costos debidos a las multas por salirse de la ventana de tiempo. Los costos de utilizaci´on son superiores a los de transportaci´on; en el caso de ventanas de tiempo duras, el costo de penalizaci´on es muy alto. El objetivo es minimizar los costos. Esto se puede ver en la siguiente figura 4.1.

Figura 4.1: Descripci´on de funci´on objetivo

4.2.2 Restricciones El primer grupo de restricciones (llamaremos .asignaci´on de viajes”) obliga a que en un viaje se visite exactamente un cliente o se quede en el dep´osito; b´asicamente es sumar todos los clientes visitados por el veh´ıculo k en el viaje j. La explicaci´on se puede ver en la figura 4.2

La figura izquierda (visitando a un cliente), muestra que si se visita en el viaje j de un veh´ıculo k a un cliente, se hace imposible visitar a otro para mantener la igualdad. La ilustraci´on derecha (qued´andose en el dep´osito), indica que se permaneci´o en el dep´osito (o cliente 0), no se puede visitar a otro cliente para mantener la igualdad de la restricci´on.

´ n matema ´ tica Cap´ıtulo 4. Formulacio

38

Figura 4.2: Descripci´on de restricci´on 1 El segundo grupo de restricciones (llamaremos ”de capacidad”) asegura la satisfacci´on de la demanda de los clientes; suma todas las entregas hechas al cliente realizadas por todos los veh´ıculos en sus viajes. Una explicaci´on puede verse en la figura 4.3.

Figura 4.3: Descripci´on de restricci´on 2 La ilustraci´on muestra los viajes realizados a un cliente (que no sea el dep´osito)donde las entregas deber´an sumar al menos la demanda del cliente El tercer grupo de restricciones est´a relacionado con la utilizaci´on de veh´ıculos, establece cuales fueron los que realmente se utilizan, marcando como y=1 los veh´ıculos que realmente son usados; est´a relacionada con la primer parte de la funci´on objetivo que calcula los costos por adquisici´on de veh´ıculos. Puede verse en la figura 4.4 La ilustraci´on muestra los dos casos posibles, el caso en que se visita al menos

´ n matema ´ tica Cap´ıtulo 4. Formulacio

39

Figura 4.4: Descripci´on de restricci´on 3 un cliente, que obliga a marcar el veh´ıculo como utilizado yk = 1 y el caso en que todos los viajes fueron al dep´osito. Se marca el veh´ıculo como no utilizado yk = 0. El cuarto grupo de restricciones establece la secuenciaci´on de los viajes, obligando que un viaje de un veh´ıculo solo pueda comenzar despu´es de haberse terminado el anterior viaje del mismo veh´ıculo, un viaje es de ida y vuelta por lo que el tiempo deber´a ser multiplicado por dos para el c´alculo del viaje redondo (ver figura 4.5).

Figura 4.5: Descripci´on de restricci´on 4 El quinto y sexto grupo de restricciones son los que establecen los tiempos de violaci´on, si es que los hubo. Estos dos grupos son muy similares al de secuenciaci´on,

´ n matema ´ tica Cap´ıtulo 4. Formulacio

40

pero estos solo calculan al momento en que se llega al cliente. El quinto grupo calcula el tiempo de violaci´on si se lleg´o antes de lo permitido con el cliente, siendo 0 si se llego despu´es de la hora inicial permitida por el cliente (ver figura 4.6).

Figura 4.6: Descripci´on de restricci´on 5 El sexto grupo revisa si se lleg´o despu´es de la hora final permitida, se hace uso de una constante M (con un valor muy grande)para calcular como cero los tiempos de violaci´on en viajes que no se realizaron(ver figura 4.7).

´ n matema ´ tica Cap´ıtulo 4. Formulacio

Figura 4.7: Descripci´on de restricci´on 6

41

Cap´ıtulo 5

´ n de cotas Construccio ´n 5.1 Introduccio En este cap´ıtulo desarrollamos los modelos relajados del modelo VRP-Starcase. se relajaran en este modelo todas las restricciones una por una y se pondr´an en un formato est´andar para facilitar las labores de programaci´on; sobre estas relajaciones se aplicara el subgradiente el cual se explicar´a en detalle.

´ n 1er grupo de restricciones 5.2 relajacio Separamos del modelo el grupo de restricciones que nos interesa, en este caso el primer grupo que es el de restricci´on de asignaci´on de viajes: P (1) x0jk + xijk = 1 ∀j ∈ Jk , k i≥1

Ponemos a este grupo de restricciones en un formato est´andar para llevar a la funci´on objetivo 1 − x0jk −

X

xijk = 0

∀j ∈ Jk , k

(5.1)

i≥1

Este grupo de restricciones requiere una matriz de multiplicadores λjk correspondientes a cada pareja viaje-veh´ıculo (jk) existente, para poder ser llevada como penalizaci´on a la funci´on objetivo. La naturaleza de los multiplicadores es cualquier numero racional , sin importar el signo, debido a que es una restricci´on de igualdad λjk ∈ R

42

´ n de cotas Cap´ıtulo 5. Construccio

(LRλjk )

min { x

X

fk y k +

k

X

43

+ + lik wijk cik xijk + eik wijk




i,j∈Jk ,k

+λjk (1 − x0jk −

X

xijk )}

(5.2)

i≥1

La expresi´on anterior representa la funci´on objetivo del modelo relajado, el modelo relajado puede entonces decirse que queda como funci´on de los multiplicadores(funci´on lagrangiana). Para obtener la cota debemos obtener el valor m´aximo de esta funci´on.

Lz∗ = max v(LRλ )

(5.3)

λ

´ n 2do grupo de restricciones 5.3 relajacio El segundo grupo de restricciones a relajar es el de la satisfacci´on de la demanda de los clientes P (2) qk xijk ≥ di

∀i 6= 0

j∈Jk ,k

Este grupo de restricciones solo requiere un vector de multiplicadores λi correspondientes a cada uno de los clientes i en el sistema (excepto el ´ındice 0 que es el del dep´osito) (LRλjk )

min { x

X

fk y k +

k

X

+ cik xijk + eik wijk + lik wijk




i,j∈Jk ,k

+λi (1 − x0jk −

X

xijk )}

(5.4)

i≥1

Ponemos a este grupo de restricciones en un formato est´andar (para facilitar la construcci´on de cotas), para llevarlo a la funci´on objetivo, se cambia el sentido de la desigualdad para considerarla siempre negativa. di −

X

qk xijk ≤ 0

∀j, k

(5.5)

j∈Jk ,k

Continuamos con colocar esta expresi´on en la funci´on objetivo con sus multiplicadores correspondiente, los multiplicadores solo podr´an ser positivos λi ≥ 0 debido

´ n de cotas Cap´ıtulo 5. Construccio

44

a la desigualdad ≤, con esto se mantiene que el valor dado de la funci´on lagrangiana sea menor al o´ptimo global. (LRλjk )

X X min { fk yk + x

k

X
+ + lik wijk + λi (di − cik xijk + eik wijk qk xijk )} j∈Jk ,k

i,j∈Jk ,k

Este valor como ya se ha mencionado es menor o igual a la soluci´on ´optima global. Para obtener la soluci´on al dual lagrangiano se obtiene el m´aximo de la funci´on lagrangiana, pero en este caso debe cuidarse el sentido de los multiplicadores. Lz∗ = max v(LRλ )

(5.6)

λ≥0

´ n 3er grupo de restricciones 5.4 relajacio El tercer grupo de restricciones es el de asignaci´on o utilizaci´on de veh´ıculos P x0,j,k ≤ yk JMk ∀k (3) JMk − j∈Jk

Ponemos a este grupo de restricciones en un formato est´andar para llevar a la funci´on objetivo, en este grupo no se cambio el sentido de la desigualdad al ponerla en el formato est´andar. JMk −

X

x0,j,k − yk JMk ≤ 0

∀k

(5.7)

j∈Jk

Continuamos con colocar esta expresi´on en la funci´on objetivo con sus multiplicadores correspondientes, solo se requerir´a un vector de multiplicadores λk uno por cada veh´ıculo , los multiplicadores solo podr´an ser positivos λk ≥ 0 debido a la desigualdad ≤. (LRλjk )

min { x

X

fk y k +

k

+λk (JMk −

X

+ cik xijk + eik wijk + lik wijk




i,j∈Jk ,k

X j∈Jk

x0,j,k − yk JMk −

X j∈Jk ,k

qk xijk )}

(5.8)

´ n de cotas Cap´ıtulo 5. Construccio

45

´ n 4to grupo de restricciones 5.5 relajacio El cuarto grupo de restricciones es el de secuenciaci´on de viajes P (4) sj+1,k ≥ sjk + 2tik xijk ∀j ∈ Jk , k i,k

Pasamos a poner este grupo en el formato est´andar, este grupo necesitara tambi´en una matriz de multiplicadores λjk un multiplicador por cada pareja jk. sjk − sj+1,k +

X

2tik xijk ≤ 0

∀j ∈ Jk , k

(5.9)

i,k

Los multiplicadores ser´an reales mayores que cero debido al sentido ≤ de la desigualdad, La funci´on objetivo ya con el grupo de restricciones incorporado es: (LRλjk )

min { x

X

fk y k +

k

X

+ cik xijk + eik wijk + lik wijk




i,j∈Jk ,k

+λjk (sjk − sj+1,k +

X

2tik xijk )}

(5.10)

i,k

´ n 5to y 6to grupo de restricciones 5.6 relajacio Estos grupos establecen los tiempos de violaci´on de la instancia, son realmente dos conjuntos pero por cuestiones de concepto se relajan de manera conjunta. (5) wijk ≥ Ei xijk − (sjk + tik xijk )

∀i 6= 0, j ∈ Jk , k

+ (6) wijk ≥ sjk + tik xijk − Li − M (1 − xijk )

∀i 6= 0, j ∈ Jk , k

Estos conjuntos van a requerir dos matrices de multiplicadores una por cada grupo uijk para (5) y vijk para (6), se pasan a poner en formato est´andar. Ei xijk − wijk − (sjk + tik xijk ) ≤ 0

∀i 6= 0, j ∈ Jk , k

+ sjk − wijk + tik xijk − Li − M (1 − xijk ) ≤ 0 ∀i 6= 0, j ∈ Jk , k La funci´on objetivo con los dos conjuntos de restricciones integradas en la tiene

como resultado: (LRλjk )

X X min { fk yk + x

k

i,j∈Jk ,k

+ cik xijk + eik wijk + lik wijk




´ n de cotas Cap´ıtulo 5. Construccio

46

+uijk (Ei xijk − wijk − (sjk + tik xijk )) + +vijk (sjk − wijk + tik xijk − Li − M (1 − xijk ))}

´todo del subgradiente - detallado 5.7 Me El m´etodo del subgradiente desarrollado para calcular el dual lagrangiano es el m´etodo del subgradiente normal(Kipp[40]) pero con una estrategia en el avance similar a la planteada por Caprara et al [9]. Se presenta a continuaci´on el proceso completo de soluci´on de una instancia de un modelo relajado en el que se incluye la parte del subgradiente. PARTE 1.- Antes de entrar a la construcci´on del modelo relajado. Se calcula una soluci´on factible del modelo original y se calcula un valor inicial para los multiplicadores de acuerdo a los valores de las variables duales en una relajaci´on lineal. 1.- Calculo de una soluci´on factible para el modelo original. En este caso se uso el mismo solver (cplex) para hallar esta soluci´on pero modificando los par´ametros para obtener una respuesta r´apida del solver (el solver se detiene apenas alcanza un GAP dado, opcionalmente se puede utilizar una heur´ıstica para el c´alculo de esta soluci´on factible. 2.- C´alculo de una relajaci´on lineal en el modelo original. Para obtener sus duales (valores relacionados con las restricciones) y usarlos como multiplicadores in´ıciales se realiza una Relajaci´on Lineal. 2.1.-Relajaci´on Lineal 2.1.1.-Se relaja modelo original. 2.1.2.-Variables enteras o binarias, pasan a ser continuas. 2.1.3.-Se resuelve modelo relajado. 2.1.4.-Se asigna a los multiplicadores λ los valores duales de soluci´on de modelo relajado. Los multiplicadores lagrangianos λ pudieran tambi´en ser estimados simplemente con un valor aleatorio o puestos todos en cero, aunque la pr´actica ha mostrado

´ n de cotas Cap´ıtulo 5. Construccio

47

que una buena estimaci´on son los valores duales de soluci´on. PARTE 2.- Construcci´on del Modelo relajado. Aqu´ı se agregan solo las restricciones no relajadas al modelo y se construye adem´as la funci´on objetivo. 1.- Construcci´on de restricciones del modelo relajado Ax ≤ b Grupo de restricciones que queda fuera del modelo Dx ≤ d Grupo de restricciones que se agrega al modelo 2.- Construcci´on de funci´on objetivo (modelo original) z = Cx En este momento el modelo relajado aun no agrega la penalizaci´on y queda de esta forma P : minz = Cx Sujeto a: Dx ≤ d x∈X PARTE 3.- Construcci´on y soluci´on del modelo lagrangiano 1.- Agregaci´on a la funci´on objetivo de la penalizaci´on del modelo. Los multiplicadores lambda calculados hasta el momento, se agregan a la funci´on objetivo para completar el modelo relajado. z = z + λ(Ax − b) objetivo = minimizar{z} Agregar objetivo al modelo El modelo LRλ relajado esta completo y listo para ser resuelto: LRλ : minz = c ∗ x + λ(Ax − b) Sujeto a: Dx ≤ d x∈X 2.- Se calcula la soluci´on del modelo LRλ . Esta soluci´on ser´a nuestra cota actual Lk del problema. PARTE 4.- Subgradiente, c´alculo de los nuevos multiplicadores con el m´etodo del subgradiente.

´ n de cotas Cap´ıtulo 5. Construccio

48

1.-Verificaci´on de la soluci´on actual. Al comparar la soluci´on actual Lk con la mejor soluci´on hasta el momento Lm se verifica si hubo mejora de soluci´on. En caso de mejora pasar al paso 2; en caso de no haber mejora saltar al paso 3. Comparar Lm < Lk 2.- En caso de mejora (Lm < Lk ). Se cambia la cota Lm por la nueva cota mejor Lk. Se almacena el valor de los multiplicadores (con el objetivo de guardar informaci´on de la iteraci´on donde hubo mejora para regresar a ese punto). Lm = Lk λmejor = λk γmejor = Ax − b γk = γmejor Si se utiliza el subgradiente modificado se incrementa el valor de θ, y se da un valor inicial para el n´ umero de faltas para probar solo unas cuantas veces esta nueva θ θ = θ ∗ 1.5 f altas = f altasmax/1.5 3.-En este paso se penaliza el subgradiente y se incrementan las faltas f altas = f altas + 1 Si la falta fue por tiempo se incrementa en 1 las faltas por tiempo f altastiempo = f altastiempo + 1 Si no se ha pasado m´aximo de faltas por tiempo Si se ha pasado el m´aximo de faltas θ =θ∗2 λactual = λmejor γk = γmejor No ha pasado el l´ımite de faltas γk = Ax − b Se ha pasado del l´ımite de faltas por tiempo Ir a paso 7 (Fin del algoritmo) 4.-En este paso se calcula el nuevo multiplicador λ 4.1.- C´alculo de kγk k2

´ n de cotas Cap´ıtulo 5. Construccio kγk2 =

P

49

γk2

4.2.- C´alculo del tama˜ no del paso tk tk =

θ∗(Ls−Lk (λk )) kγk k2

4.3.- C´alculo de los nuevos multiplicadores λk+1 = λk + tk γk Pero si multiplicadores pertenecen a una restricci´on del tipo ≤ : λk+1 = min(λk + tk γk ,0) 5.- Revisar el criterio de parada (iteraciones, l´ımite de tiempo, convergencia , etc.) 6.- Retornar a la PARTE 3 - paso 2, Si no se cumpli´o el criterio de parada, esto implica recalcular la funci´on objetivo con los nuevos multiplicadores. 7.- Fin del algoritmo, retorna la mejor cota calculada hasta el momento con sus multiplicadores respectivos. Esta es una descripci´on comentada del proceso de c´alculo del dual lagrangiano a trav´es del subgradiente; en el cap´ıtulo 6 se muestran los seudoc´odigos de este proceso.

5.8 Sobre el GAP Para medir el error relativo de una soluci´on factible obtenida ya sea por un m´etodo aproximado (heur´ısticos, metaheur´ısticos , etc.) con el valor real del o´ptimo global de un problema, se mide obteniendo la relaci´on entre la soluci´on obtenida y la real, esta relaci´on en un problema de minimizaci´on se expresa como:

%GAP = 100 ∗

Zf − Zo Zf

(5.11)

Donde: Zf .- Es una soluci´on factible del problema. Zo .- Es la soluci´on o´ptima al problema. %GAP .- Es el error relativo en porcentaje de nuestra soluci´on Este GAP es el mejor que se puede estimar, ya que expresa de manera precisa el error de nuestra soluci´on con la verdadera soluci´on. La explicaci´on de la relaci´on

´ n de cotas Cap´ıtulo 5. Construccio

50

de este GAP con el error absoluto de nuestra soluci´on factible se puede ver en la figura 5.1

Figura 5.1: GAP entre soluci´on factible y la o´ptima global Los problemas a los que nos enfrentamos en programaci´on lineal, no siempre podr´an estar en relaci´on con el valor ´optimo del problema, ya que de hecho es lo que se intenta buscar. No se sabe de antemano cual es la soluci´on o´ptima global, a menos que sea un problema de soluci´on trivial. Un problema de programaci´on entera , binaria o mixta necesitara necesitar´a otra forma de estimar el error; por ejemplo, en un problema de programaci´on lineal entera, usando el m´etodo de branch and bound, se estima una soluci´on factible al problema y esa soluci´on entera estar´a relacionada con una soluci´on de una Relajaci´on Lineal, la relaci´on entre esa soluci´on entera y su soluci´on lineal pudiera ser una estimaci´on del error. Si el error no est´a en lo tolerado se har´ıa un nuevo corte obteniendo una nueva soluci´on factible y nueva soluci´on lineal. Si quisi´eramos obtener la soluci´on o´ptima global tendr´ıamos que reducir ese error hasta cero; la expresi´on siguiente calcula en por ciento ese error estimado.

%GAP = 100 ∗

Zf − Zl Zf

(5.12)

Donde: Zl .- Es la soluci´on lineal del problema. Este GAP expresa un error relativo de nuestra soluci´on, no tiene la precision del GAP estimado con una soluci´on ´optima global, es m´as parecido a un intervalo de

´ n de cotas Cap´ıtulo 5. Construccio

51

confianza, la explicaci´on de la relaci´on de este GAP con el error absoluto de nuestra soluci´on factible se puede ver en la figura 5.2

Figura 5.2: Descripci´on del GAP relativo a una soluci´on lineal La figura 5.2 muestra la relaci´on que hay de nuestra soluci´on factible con la soluci´on ´optima global, La soluci´on ´optima global est´a en un rango entre dos fronteras o cotas, una cota relajada del problema (la soluci´on lineal) y la otra cota es la soluci´on factible que obtuvimos. Entre m´as peque˜ no sea este rango m´as cerca esta nuestra soluci´on de ser la soluci´on o´ptima global, se puede decir que expresa que tan cerca esta nuestra soluci´on de ser la verdadera, no que tan cerca esta de la soluci´on real. Para nuestra investigaci´on usamos el mismo principio anterior: estimamos el error de nuestra soluci´on relativo a una soluci´on relajada, pero no utilizamos la relajaci´on lineal, usamos la relajaci´on lagrangiana, la expresi´on del GAP siguiente es una expresi´on general para cualquier tipo de relajaci´on (lineal, subrogada, lagrangiana, etc.): %GAP = 100 ∗

Zf − Zr Zf

(5.13)

Donde: Zr .- Es la soluci´on relajada del problema La figura 5.3 muestra el GAP deseado utilizando una relajaci´on lagrangiana para estimar nuestra cota, se puede observar donde podr´ıa quedar la cota lineal con

´ n de cotas Cap´ıtulo 5. Construccio

52

respecto a nuestra cota lagrangiana y como la zona encerrada entre cotas pudiera ser menor.

Figura 5.3: Descripci´on del GAP relativo a una soluci´on lagrangiana i´on se seguir´ıa

Por ultimo, para el caso de maximizaci´on, las formulas serian:

Para el caso o´ptimo: %GAP = 100 ∗

Zo − Zf Zo

(5.14)

Zr − Zf Zr

(5.15)

Cuando se tiene una cota relajada: %GAP = 100 ∗

Cap´ıtulo 6

´ n computacional Implementacio ´n 6.1 Introduccio En esta secci´on hablaremos de como se implementaron computacionalmente las relajaciones al modelo y las herramientas utilizadas para esto

6.2 GAMS GAMS es un lenguaje de modelado algebraico, para construir modelos matem´aticos de programaci´on lineal y no lineal, es capaz de utilizar diferentes solvers para la resoluci´on de problemas y modificar los par´ametros de estos, su ventaja sobre un lenguaje de programaci´on general es su facilidad de uso. No se requiere construir las matrices del modelo, solo construir las expresiones algebraicas que definen esas matrices facilitando mucho el modelado[45]. En esta investigaci´on fue utilizado solo para verificar resultados de los modelos construidos con el lenguaje C++ y resueltos por el solver Cplex.

6.3 Ilog Cplex Optimization Studio Ilog Cplex Optimization Studio es un conjunto de herramientas de software para resolver problemas de optimizaci´on. Una de las principales herramientas es un solver llamado Cplex. Este programa contiene una implementaci´on del m´etodo sim53

´ n computacional Cap´ıtulo 6. Implementacio

54

plex hecha en lenguaje C, aunque hoy soporta otros m´etodos de optimizaci´on. El solver Cplex es un solver de alto rendimiento para problemas de Programaci´on Lineal (LP), Programaci´on Entera Mixta (MIP) y problemas de Programaci´on Cuadr´atica (QP/QCP/MIQCP/MIQP) El solver Cplex ofrece varios algoritmos para resolver problemas de Programaci´on Lineal, pudiendo elegir entre el algoritmo simplex primal, el algoritmo de puntos interiores entre otros. El solver Cplex adem´as tiene un presolver que ayuda a reducir el tama˜ no de los problemas a ser resueltos Para la soluci´on de problemas de Programaci´on Entera Mixta, se provee de una implementaci´on del algoritmo de branch and bound, el cual utiliza modernas t´ecnicas como planos de corte y heur´ısticas para encontrar soluciones enteras. Ilog Cplex Optimization Studio ofrece adicionalmente herramientas para el modelado de programas, tales como un lenguaje propio de optimizaci´on llamado .Optimization Programming Language”(OPL) y librer´ıas de componentes, que ofrecen interfaces para usar el solver en distintos lenguajes de programaci´on.

6.4 Librer´ıa Cplex La librer´ıa proporcionada para Cplex[1] provee lo necesario para usar todas las caracter´ısticas del solver en distintos lenguajes de programaci´on la cual nos permite usar el solver e interactuar con los par´ametros de este, algo muy dif´ıcil con la consola de comandos . Se uso esta librer´ıa para resolver instancias y sus relajaciones, adem´as de calcular duales, valor final de las restricciones ya que posee un evaluador de expresiones algebraicas (´ util para el c´alculo de subgradientes). La librer´ıa implementa caracter´ısticas de modelado algebraico, muy parecido a GAMS, esto quiere decir que se pueden construir expresiones algebraicas para definir el modelo. La librer´ıa de Cplex para C++ contiene un conjunto de clases con las que definimos, variables, restricciones, modelos etc.. A continuaci´on se listar´an las m´as importantes: IloNumArray. Esta clase define arreglos de datos num´ericos. En C++ es un arreglo de valores tipo float o double, su uso es opcional ya que pueden utilizarse

´ n computacional Cap´ıtulo 6. Implementacio

55

los tipos de datos proporcionados por C++ IloIntVar, IloNumVar, IloBoolVar. Con estas clases definimos las variables enteras, continuas y binarias , asociadas a estas est´an las clases IloIntVarArray, IloNumVarArray, IloBoolVarArry que definen arreglos de variables, enteras, continuas y binarias respectivamente. IloArray. Es una plantilla que permite hacer arreglos de clases, es b´asicamente utilizada para hacer arreglos de arreglos variables (o matrices) IloExpr. En esta clase se guardan las expresiones algebraicas, con las que construiremos despu´es las restricciones, tambi´en tiene una clase asociada llamada IloExprArray para definir arreglos. IloRange. Esta clase se utiliza para definir las restricciones del modelo, es u ´til para consultar los valores de las variables duales del problema. Tiene una clase asociada llamada IloRangeArray para definir arreglos de esta. IloObjetive. Esta clase define la funci´on objetivo del modelo. IloModel. Esta clase define todo nuestro modelo, es donde se agregan las restricciones y el objetivo. IloCplex. Esta clase es la que realiza el trabajo de soluci´on del modelo, a trav´es de esta se define el tipo de solver a utilizar, el tiempo m´aximo que se dejar´a correr la instancia del modelo y tambi´en guarda otras funciones como exportar el modelo a un archivo o importarlo entre otras. IloEnv. Esta clase es la que guarda toda la informaci´on del modelado y la que maneja la memoria que se vaya utilizando. Cuando se construye un modelo, todas las clases instanciadas deber´an hacer referencia a ´esta.

´ n computacional Cap´ıtulo 6. Implementacio

56

6.5 Lenguaje C++ Aunque la librer´ıa de Cplex nos provee de muchas herramientas no es capaz por s´ı sola de generar instancias especificas, generar reportes de resultados amigables etc. para eso utilizamos C++. A continuaci´on se listaran las funciones programadas en C++ Creaci´on de instancias simuladas. Se genera un archivo de datos con las matrices necesarias para procesar la instancia. Generaci´on de reportes de instancias, de datos de entrada , de salida (soluciones modelo originales y modelos relajados) Construcci´on de modelos originales y relajados usando la librer´ıa de cplex. Implementaci´on del subgradiente usando librer´ıas de Cplex para el c´alculo de expresiones del modelo. El compilador utilizado fue el compilador de C++ para visual studio (Microsoft Visual C++ 9.0 Compiler ), junto con el editor QTCreator

6.6 archivos de datos Un archivo de datos es generado cuando se simulan instancias, el cual contiene el nombre del archivo, tipo de modelo, cuantas matrices tiene el archivo, y todas las matrices de la instancia, iniciando con su descripci´on (nombre de matriz y dimensiones). Este archivo es b´asicamente un archivo de matrices, es un archivo de texto que puede editarse en un bloc de notas.

´ n computacional Cap´ıtulo 6. Implementacio

57

6.7 archivos de salida No existe un solo archivo de salida, existen archivos de salida para la soluci´on de instancias sin relajaci´on y otros para instancias relajadas. Para los modelos sin relajaci´on tenemos: ´ Archivo de reporte de soluci´on. Este es una interpretaci´on de la soluci´on dada por el software, contiene las agendas de los veh´ıculos, de clientes, cuantos veh´ıculos fueron utilizados, etc. Archivo de reporte de soluci´on en formato matricial. Contiene los valores de las variables. Para los modelos relajados Archivo de multiplicadores , generados durante el proceso del subgradiente Archivo de reporte de soluci´on de la relajaci´on, que contiene el valor final de la relajaci´on (la cota lagrangiana), las caracter´ısticas de cada iteraci´on del subgradiente y los par´ametros utilizados para el subgradiente.

6.8 Algoritmos La parte m´as importante de la implementaci´on computacional son cinco funciones: (1) la que implementa la resoluci´on de modelos, considerando como criterio de parada el GAP,(2) una funci´on que implementa la relajaci´on lineal obteniendo los duales del grupo de restricciones relajado,(3) una funci´on que construye los modelos, considerando que grupos de restricciones se relajan y cuales,(4) una funci´on para construir la funci´on objetivo y (5) la funci´on propia del subgradiente, combinaciones de ´estas forman las dem´as funciones de la implementaci´on

´ n computacional Cap´ıtulo 6. Implementacio

58

Los seudoc´odigos dados a continuaci´on puedan dar una idea b´asica de la implementaci´on, la implementaci´on en C++ contiene m´as procesos intermedios no primordiales para el funcionamiento del programa pero u ´tiles para el control de errores y crear los reportes El siguiente seudoc´odigo es una funci´on para obtener una soluci´on factible del modelo sin relajar //OBTENER SOLUCION FACTIBLE //GAP

− e s e l c r i t e r i o de parada d e l s o l v e r ( 0 s o l u c i o n g l o b a l optima

) // g r

− v e c t o r g r u p o s de r e s t r i c c i o n e s a r e l a j a r ( 0 s i n r e l a j a c i o n )

// modelo − modelo a r e s o l v e r S o l u c i o n f a c t i b l e (GAP) begin gr