• Author / Uploaded
• Andres Felipe Quijano Echeverry

• Categories
• Transporte
• Red de computadoras
• Toma de decisiones
• Aluminio
• Movimiento (física)

Citation preview

´ ´ UNIVERSIDAD AUTONOMA DE NUEVO LEON Facultad de Ingenier´ıa Mec´ anica y El´ ectrica Divisi´ on de Estudios de Posgrado

´ n de Recursos de Transporte: “Asignacio ´ctico” Un Enfoque Pra Tesis profesional presentada por

Israel Cano Robles

´n en opcio al grado de Maestro en Ciencias en Ingenier´ıa de Sistemas

San Nicol´as de los Garza, N.L.

Oto˜ no de 2005

´ ´ UNIVERSIDAD AUTONOMA DE NUEVO LEON Facultad de Ingenier´ıa Mec´ anica y El´ ectrica Divisi´ on de Estudios de Posgrado

´ n de Recursos de Transporte: “Asignacio ´ctico” Un Enfoque Pra Tesis profesional presentada por Israel Cano Robles ´n en opcio al grado de Maestro en Ciencias en Ingenier´ıa de Sistemas ´ de Tesis Comite Dr. Mauricio Cabrera R´ıos Revisor Dr. Igor S. Litvinchev Asesor y Director MC. Gerardo Naranjo Sotomayor Revisor San Nicol´as de los Garza, N.L.

Noviembre de 2005

Tesis profesional sustentada por Israel Cano Robles en opci´on al grado de Maestro en Ciencias en Ingenier´ıa de Sistemas.

Aceptada por el Divisi´on de Estudios de Posgrado

Dr. Igor S. Litvinchev Asesor y Director

Dr. Mauricio Cabrera R´ıos Revisor

MC. Gerardo Naranjo Sotomayor Revisor

Dr. Guadalupe Alan Castillo Rodr´ıguez Subdirector Divisi´on de Estudios de Posgrado

15 de Noviembre de 2005

”Quiero dedicar este trabajo a todos aquellos que me apoyaron: maestros, familia, amigos, pero especialmente a mis compa˜ neros de generaci´on del PISIS: Nancy, Leti, Fer, Fernadillo y Oswi, la hicimos bien.”

Agradecimientos Agradezco la oportunidad al PISIS y CONACYT por haberme permitido realizar mis estudios de maestr´ıa, mediante una beca de estudios de tiempo completo. Quiero expresar mi agradecimiento infinito a mi asesor Dr. Igor S. Litvinchev desde el principio confi´o y respaldo este proyecto. Por su paciencia y entusiasmo a lo largo de estos a˜ nos. Por la motivaci´on para presentar este trabajo en foros internacionales. Sin duda alguna este no hubiera sido logrado sin la vocaci´on y esfuerzo de todos los ´ profesores del PISIS: Dra. Ada Alvarez, Dr. Roger R´ıos, Dr. Oscar Chac´on, Dr. Cesar Villareal , Dr. Rodolfo Garc´ıa con quienes tuve el gusto de aprender en sus cursos. A todo el personal de Sintec, especialmente a Oscar Lozano, Roberto Palacios, Gerardo Naranjo, Jaime Ortega, por abrir las puertas a este proyecto. A todos los que en las u ´ltimas semanas de elaboraci´on de este trabajo dedicaron parte de su tiempo.

´Indice general

1. Introducci´ on

1

1.1. Ciencia de Transporte. . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2. Transporte como actividad econ´omica . . . . . . . . . . . . . . . . . . .

4

1.3. Objetivo de tesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

1.4. Organizaci´on de la tesis

. . . . . . . . . . . . . . . . . . . . . . . . . .

2. El problema y sus antecedentes

10 11

2.1. Introducci´on a los problemas de ruteo. . . . . . . . . . . . . . . . . . .

11

2.2. Trabajos sobre ruteo de veh´ıculos con ventanas de tiempo . . . . . . . .

14

3. Exposici´ on del Problema

21

3.1. Introducci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1.

21

Por qu´e optimizar? . . . . . . . . . . . . . . . . . . . . . . . . .

22

3.1.2. Sintec . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

3.1.3. Modelos Matem´aticos . . . . . . . . . . . . . . . . . . . . . . . .

24

3.2. Formulaci´on Matem´atica . . . . . . . . . . . . . . . . . . . . . . . . . .

26

3.2.1. Suposiciones del problema . . . . . . . . . . . . . . . . . . . . .

27

3.2.2. Definici´on del Modelo Matem´atico . . . . . . . . . . . . . . . . .

28

3.3. M´etodo de soluci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

3.3.1. Programaci´on Entera (MIP) . . . . . . . . . . . . . . . . . . . .

31

i

´INDICE GENERAL 3.3.2. Herramientas Computacionales . . . . . . . . . . . . . . . . . . 4. Casos Pr´ acticos

ii 32 34

4.1. Caso 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

4.2. Caso 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

5. Experimentos Computacionales

43

5.1. Generaci´on de problemas . . . . . . . . . . . . . . . . . . . . . . . . . .

43

5.2. Problemas de Asignaci´on de veh´ıculos con ventanas suaves de tiempo .

44

5.3. Problemas de Asignaci´on de veh´ıculos con ventanas duras de tiempo . .

47

6. Conclusiones y Recomendaciones

49

6.1. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49

6.2. Aportaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49

6.3. Recomendaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

50

Bibliograf´ıa

52

A. M´ etodo Ramificaci´ on y Cota A.1. Ramificaci´on-cotas (Branch and bound) . . . . . . . . . . . . . . . . . . B. AMPL

56 56 60

B.1. Lenguaje AMPL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

60

B.1.1. Reglas l´exicas de AMPL. . . . . . . . . . . . . . . . . . . . . . .

62

B.1.2. Los elementos de un conjunto. . . . . . . . . . . . . . . . . . . .

64

B.1.3. Expresiones que indexan y sub´ındices. . . . . . . . . . . . . . .

65

B.1.4. Expresiones aritm´eticas, l´ogicas y de conjuntos. Funciones matem´aticas. 67 B.1.5. Declaraciones de elementos del modelo. . . . . . . . . . . . . . .

72

´INDICE GENERAL

iii

B.1.6. Especificaci´on de datos. . . . . . . . . . . . . . . . . . . . . . .

79

B.1.7. Comandos del lenguaje. . . . . . . . . . . . . . . . . . . . . . .

94

C. Modelo en AMPL D. Carta Referencia Sintec

99 101

´Indice de Tablas 1.1. Factores que influyen en costo del transporte . . . . . . . . . . . . . . .

6

4.1. Par´ametros clientes . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

4.2. Par´ametros de los veh´ıculos . . . . . . . . . . . . . . . . . . . . . . . .

35

4.3. Costos Variables a cada destino . . . . . . . . . . . . . . . . . . . . . .

36

4.4. Resultados Clientes Veh´ıculos Sencillos . . . . . . . . . . . . . . . . . .

37

4.5. Resultados Clientes Veh´ıculos Dobles . . . . . . . . . . . . . . . . . . .

38

4.6. Resultados Caso Pr´actico 1

. . . . . . . . . . . . . . . . . . . . . . . .

38

4.7. Par´ametros clientes Caso 2 . . . . . . . . . . . . . . . . . . . . . . . . .

39

4.8. Par´ametros de los veh´ıculos . . . . . . . . . . . . . . . . . . . . . . . .

40

4.9. Costos Variables a cada destino . . . . . . . . . . . . . . . . . . . . . .

40

4.10. Programa de Distribuci´on Clientes Autoservicio . . . . . . . . . . . . .

41

4.11. Programa de Distribuci´on Clientes Autoservicio . . . . . . . . . . . . .

41

4.12. Programa de Distribuci´on Clientes Autoservicio (Cont...) . . . . . . . .

42

4.13. Resultados Caso Pr´actico 2

. . . . . . . . . . . . . . . . . . . . . . . .

42

5.1. Nomenclatura problemas generados . . . . . . . . . . . . . . . . . . . .

44

5.2. Resultados Ventanas Suaves 1-tipo de veh´ıculo . . . . . . . . . . . . . .

45

5.3. Resultados Ventanas Suaves . . . . . . . . . . . . . . . . . . . . . . . .

45

5.4. Resultados Veh´ıculos utilizados con Ventanas Suaves . . . . . . . . . .

46

iv

´INDICE DE TABLAS

v

5.5. Resultados Ventanas Duras . . . . . . . . . . . . . . . . . . . . . . . .

47

5.6. Resultados Veh´ıculos utilizados con Ventanas Duras . . . . . . . . . . .

48

B.1. Modelo b´asico del ejemplo . . . . . . . . . . . . . . . . . . . . . . . . .

61

B.2. Modelo general del ejemplo

. . . . . . . . . . . . . . . . . . . . . . . .

63

B.3. Datos para el ejemplo. . . . . . . . . . . . . . . . . . . . . . . . . . . .

63

B.4. Operadores aritm´eticos (A), l´ogicos (L) y de conjuntos (S). . . . . . . .

69

B.5. Funciones de generaci´on de variables aleatorias en AMPL. . . . . . . .

69

B.6. Funciones aritmticas en AMPL. . . . . . . . . . . . . . . . . . . . . . .

70

B.7. Fichero de lotes para el modelo del ejemplo 1.1 . . . . . . . . . . . . . .

95

´Indice de figuras 1.1. Distribuci´on del transporte de Carga en M´exico . . . . . . . . . . . . .

7

4.1. Red de distribuci´on Valle de M´exico . . . . . . . . . . . . . . . . . . . .

34

4.2. Red de distribuci´on Clientes Centralizados . . . . . . . . . . . . . . . .

39

5.1. Clientes vs Veh´ıculos utilizados . . . . . . . . . . . . . . . . . . . . . .

46

5.2. Clientes vs Veh´ıculos utilizados . . . . . . . . . . . . . . . . . . . . . .

48

´ A.1. Arbol de subproblemas generado en ramificaci´on y cotas . . . . . . . .

57

vi

Resumen Israel Cano Robles Candidato para el Grado de Maestro en Ciencias en Ingenier´ıa de Sistemas Universidad Aut´onoma de Nuevo Le´on Facultad de Ingenier´ıa Mec´anica y El´ectrica T´ıtulo del Estudio:

Asignaci´ on de Recursos de Transporte: Un Enfoque Pr´ actico

N´ umero de p´aginas: 115 Objetivos y m´ etodo de estudio: En muchas organizaciones, la administraci´on de las actividades de distribuci´on constituye un problema de toma de decisiones. Este problema ha cobrado m´as importancia debido a la contribuci´on de los costos de distribuci´on dentro de los costos totales. La mayor´ıa de las compa˜ n´ıas requieren de veh´ıculos para la recolecci´on y entrega dentro de una red de suministro o demanda. La utilizaci´on y ruteo eficiente de esta flotilla es el centro de la mayor´ıa de los problemas de ruteo. Particularmente los gerentes de distribuci´on se cuestionan — cu´antos veh´ıculos son necesarios para satisfacer demanda a un costo m´ınimo?— Esta pregunta es dif´ıcil de contestar dada la enorme gama de combinaciones de mezcla de flotilla y rutas que

pueden existir, esto nos da la posibilidad de formular el problema en que nos enfocamos en este trabajo. Dentro de las numerosas variantes del problema de ruteo de veh´ıculos, generalmente se comparten las siguientes caracter´ısticas: un conjunto de rutas debe ser dise˜ nado para los veh´ıculos; su origen y fin debe ser un dep´osito central. Los costos de ruteo asociados con los veh´ıculos son una parte de la composici´on total de los costos de distribuci´on y el costo de adquisici´on de flotilla y mantenimiento. En este trabajo consideramos el problema de ruteo con m´ ultiples tipos de veh´ıculos simult´aneamente con la determinaci´on de la composici´on de la flotilla heterog´enea, con el objetivo de satisfacer la demanda en un conjunto de clientes con cantidades demandadas y ventanas de tiempo conocidas, desde un dep´osito central o una planta de producci´on. El objetivo es minimizar la suma de los costos de adquisici´on (fijos) y los costos de ruteo (variables). Suponemos que tenemos una cantidad disponible de cada tipo de veh´ıculos, al menos igual al n´ umero de clientes. La demanda de cada uno de los clientes es m´as grande que la capacidad de cualquier veh´ıculo. Tambi´en consideramos solo las rutas directas entre el centro de distribuci´on y los clientes. De esta forma la red se puede ver del tipo estrella. Esta configuraci´on de red es com´ un donde los puntos de demanda son centros de distribuci´on y no los clientes finales. En contraste con el cl´asico problema de ruteo, un cliente tiene que ser visitado varias veces (tal vez por el mismo veh´ıculo) en orden de satisfacer su demanda adem´as se supone que se pueden dividir los env´ıos. Se consideran ventanas de tiempo suaves para permitir que el veh´ıculo llegue a un cliente antes o despu´es de esta ventana, en consecuencia el veh´ıculo incurre en costos adicionales dado las penalizaciones.

Tambi´en son consideradas las ventanas de tiempo duras en consecuencia se le proh´ıbe al veh´ıculo llegar fuera de los horarios de atenci´on. Para este problema se incluye la formulaci´on matem´atica y resultados de un estudio de dos casos pr´acticos presentados por Sintec y un conjunto de experimentos de problemas generados aleatoriamente. FIRMA DEL ASESOR: Dr. Igor S. Litvinchev

Cap´ıtulo 1 Introducci´ on “La curiosidad humana y el deseo por saber como se comporta el mundo que nos rodea establece un ´area f´ertil para la aplicaci´on de la investigaci´on de operaciones.” Randolph W. Hall

1.1.

Ciencia de Transporte.

En la antig¨ uedad el transporte era realizado por el hombre aprovechando medios como los animales de carga, y medios naturales como el viento, las corrientes de agua, fuerza de gravedad y algunos veh´ıculos sencillos. De igual manera se constru´ıan caminos y estaciones de carga y descarga, el control e inspecci´on solo concern´ıa a los viajantes. Hoy en d´ıa el movimiento de los veh´ıculos se debe a motores, la construcci´on de caminos y terminales. Existen nuevas tecnolog´ıas como Internet, las redes inal´ambricas,coberturas satelitales que nos hacen pensar en las marcadas diferencias existentes entre las formas de transporte actual y sus antecesoras. Tambi´en encontramos similitudes, existen veh´ıculos, caminos, terminales y controles que son ajustados para realizar ciertas funciones b´asicas, de los modos de transporte actualmente conocidos todos tienen capacidad de desplazarse, acelerar, frenar y cuentan

1

´ CAP´ITULO 1. INTRODUCCION

2

con mecanismos para almacenar combustible o energ´ıa para funcionar, diferenciar entre objetos y personas en las terminales, asignar y contener cargas de manera eficiente para ir de un lugar a otro. Al paso de los a˜ nos y de esta evoluci´on de modos de transporte, el hombre ha reconocido en la ciencia del transporte que cualquier modo de transporte contiene los mismos elementos: —veh´ıculos, un camino por donde transitar y terminales— operando bajo cierta pol´ıtica de control. La clara definici´on de estos elementos es u ´til para estar de acuerdo en que sea cual sea el modo de transporte estos elementos b´asicos conservan sus propiedades. Los veh´ıculos comprenden a todos los recursos m´oviles en las que pueden viajar personas o embarques de productos, proveen el espacio para hacer del viaje seguro y confortable. Los caminos son recursos ya establecidos como las carreteras y autopistas estos definen el camino f´ısico que utilizaran los veh´ıculos en su movimiento de un lugar a otro. Las terminales son los establecimientos estacionarios con la capacidad de organizar los viajes de personas objetos de acuerdo a su salida y entrada en las rutas de transportaci´on. Por u ´ltimo la pol´ıtica de control se refiere a las reglas que rigen el movimiento y trayectorias de todo el sistema de transporte. La ciencia de transporte en parte describe el comportamiento del hombre y de los sistemas cuando toman decisiones de transporte y por otra parte prescribe la forma en que se debe tomar esa decisi´on optimizando como objetivo el transporte. Como consecuencia del andar diario las personas tienen un amplia gama de elecciones que son tomadas de acuerdo a la formaci´on de h´abitos, circunstancias y otras ocasiones por deliberaci´on. Existen cuatro ramas que clasifican la toma de decisiones auxiliada por la ciencia de transporte La manera en que nos comportamos al conducir un veh´ıculo es decir las decisiones

´ CAP´ITULO 1. INTRODUCCION

3

rutinarias como la velocidad, la ruta y modo que seguimos para ir al lugar de trabajo, la escuela son decisiones de corto plazo mientras que la forma en que elegimos donde habitar, trabajar y como se forman las ciudades en zonas comerciales habitacionales e industriales definen de manera colectiva una rama de la ciencia del transporte. Cuando queremos explicar fen´omenos como la manera en que fluyen los veh´ıculos cuando pasan a trav´es de un camino y se encuentran con intersecciones, divisiones y combinaciones de caminos. Tambi´en cuando vemos el aumento de la tasa de flujo sobre un camino y sus relaciones con la disminuci´on de velocidad, el aumento de la densidad y como ocurren las primera filas o acumulamientos de veh´ıculos en las calle, se recurre a otra rama de la ciencia de transporte ampliamente estudiada y conocida como flujo en trafico y redes. Determinar el camino que seguir´a una unidad de un lugar a otro es la rama de la ciencia del transporte conocida como ruteo, dentro del ruteo existen tambi´en tres tareas b´asicas: asignaci´on (elegir el recurso que va a realizar la actividad de transporte), secuenciamiento (determinar el orden en que se realizaran las actividades del transporte) y rumbo o itinerario (el camino a seguir de una asignaci´on a otra). El ruteo no es exclusivo de veh´ıculos del tipo autom´ovil puede ser utilizado para camiones de carga aviones, contenedores de trenes, barcos y las tripulaciones que hacen que estos recursos funcionen. Administrar precisamente al personal que maneja las unidades cumpliendo las cargas laborales es un reto para esta rama de investigaci´on. Dise˜ nar las redes—caminos que ser´an utilizados para desplazar los productos desde su lugar de origen hasta su destino— es la u ´ltima rama de la ciencia que mencionaremos en este trabajo, el dise˜ no consiste en la localizaci´on de los almacenes, centros productivos, dep´ositos de veh´ıculos, estaciones y en el trazo de los caminos que ser´an utilizados y que unir´an las instalaciones f´ısicas unas con otras. Ejemplos de como deben

´ CAP´ITULO 1. INTRODUCCION

4

ser dise˜ nadas esta rutas las encontramos a diario los r´ıos, el sistema circulatorio o hasta en la forma de los ´arboles, sin embargo la construcci´on de redes por el hombre buscando ser m´as sofisticada a creado otras estructuras como las de mallas cuadriculadas, redes de anillos c´entricos y las de “hub and spoke ”. Hacer estos dise˜ nos de la manera m´as eficiente, es decir que siempre generen un beneficio en tiempo o econ´omico es una gran oportunidad para mostrar inter´es en la investigaci´on de estos temas.

1.2.

Transporte como actividad econ´ omica

Como se describi´o anteriormente el transporte puede ser considerado como una materia de estudio. Sin embargo la manera mas com´ un en que se conoce al transporte es como una actividad econ´omica. Sabemos que sin esta actividad ser´ıa imposible disponer de cualquier tipo de producto en el lugar que quisi´eramos. Esta generalizaci´on nos hace pensar en otro concepto conocido como “log´ıstica ”. La transportaci´on y log´ıstica con frecuencia se pueden confundir como el mismo concepto, aunado a esto cada quien lo nombra como mejor se adapte a su situaci´on y encontramos que este termino es conocido tambi´en como: Distribuci´ on, Log´ıstica industrial, Sistemas de respuesta r´ apida, Administraci´ on de cadena de suministro. En un intento por estandarizar la idea el Consejo de Administraci´on Log´ıstica (The Council of Logistics Management [CLM]) a proporcionado esta definici´on [3] para log´ıstica. El proceso de planeaci´on, implementaci´on y control efectivo y eficiente, del flujo y almacenamiento de bienes, servicios e informaci´on, desde un punto de origen hasta un punto de consumo, con el prop´osito de cumplir con requerimientos de un cliente.

Basados en esta definici´on ubicamos al transporte como parte de las actividades de la log´ıstica, consider´andolo con la capacidad de poder mover materia prima y bienes producidos desde un punto de origen a uno de destino donde se consumir´an. Tambi´en

´ CAP´ITULO 1. INTRODUCCION

5

involucra la selecci´on del modo (ej. avi´on, tren, barco, cami´on o tuber´ıas), ruteo de los embarques, asegurar el cumplimiento de las reglas del lugar donde se originan los embarques y la selecci´on de una compa˜ n´ıa de transporte. La importancia de esta se basa principalmente y en la mayor´ıa de las casos por su participaci´on en los costos totales de las actividades log´ısticas. Un sistema de transportaci´on eficiente es el sello distintivo de una sociedad industrializada a´ un y cuando su influencia como sector econ´omico es tan sutil que muy pocas veces vemos su impacto en nuestra vida diaria, solamente en EU los gastos de transportaci´on en 2002 fueron de cerca de 455 billones de d´olares. El impacto de la transportaci´on no solo contempla el sentido de participaci´on de los costos totales de un bien, tambi´en es importante la participaci´on que tiene para lograr una satisfacci´on del cliente. La transportaci´on es considerada como una actividad de valor agregado, es decir si el producto puede ser movido desde un lugar a otro se conoce como valor de lugar, adem´as para que el producto este disponible en el momento la velocidad y consistencia con que se mueve de un lugar a otro determina el valor de tiempo. Si el producto no se encuentra en el momento preciso en el lugar que se necesita puede traer repercusiones costosas como p´erdida de ventas, insatisfacci´on del cliente, disminuci´on de la producci´on cuando hablamos de sistemas de manufactura. Son conocidos los casos en la industria automotriz de las costosas multas por detenci´on de l´ıneas de producci´on como consecuencia de un incumplimiento de estos dos valores Tiempo y Lugar. Compa˜ n´ıas como FedEx, CSX, UPS,Ryder Integrated Logistics basan su ´exito en la capacidad de proveer un consistente tiempo en transito y un gran valor de lugar y tiempo a los productos de sus clientes.

´ CAP´ITULO 1. INTRODUCCION

6

En general los factores que influyen en el costo y precio del transporte se puede agrupar en dos a continuaci´on los podemos ver en la tabla (1.1). Factores relacionados con el Factores relacionados con el producto mercado Densidad Localizaci´on de mercados Estibamiento Legislaci´on actual para los transportistas Manejo Balance del tr´afico que entra y sale del mercado Responsabilidad por valor del pro- Temporizaci´on de los productos ducto Transporte dom´estico o internacional Tabla 1.1: Factores que influyen en costo del transporte De todos los modos de transporte disponibles—autotransporte, avi´on, barco, tren, ductos— que se pueden utilizar para transportar productos el modo de autotransporte tambi´en conocido como transporte por cami´on o trailer es uno de los mas conocidos y tambi´en motivo de este trabajo. Este sector se encuentra segmentado en nuestro pa´ıs como se muestra en la grafica 1.1 . El transporte de carga es el principal modo de transporte para muchos de los productos manufacturados como art´ıculos deportivos, juguetes, art´ıculos electr´onicos, enseres dom´esticos, ropa, medicamentos, equipo de oficina y en un 75 % es la elecci´on para transportar productos agr´ıcolas, como carne, vegetales, productos de elaboraci´on diaria, pan, cigarros y bebidas, de esta forma se transportan todo tipo de productos de manera r´apida y confiable con una m´ınima perdida o da˜ no del producto durante su recorrido. Al transporte que se realiza sin cruzar fronteras internacionales se le conoce como dom´estico, aunque preferentemente se realiza por trailer el movimiento de estos productos, este compite por los peque˜ nos embarques con el a´ereo, y contra el tren en los

´ CAP´ITULO 1. INTRODUCCION

7

Figura 1.1: Distribuci´on del transporte de Carga en M´exico grandes embarques. Lo que ha marcado la diferencia de elecci´on de ´este sobre las dem´as es lo eficiente que se vuelven las operaciones de carga y entrega de mercanc´ıas en las terminales camioneras en comparaci´on con las terminales a´ereas para cualquier tama˜ no del cargamento si la distancia recorrida es menor de 500 millas. Con respecto al tren cualquier embarque que exceda las 10000 libras ser´a predominante su elecci´on sobre la transportaci´on por cami´on. Una de las ventajas de esta forma de transporte sobre sus competidoras es la flexibilidad que le proporcionan los cerca de 4 millones de millas infraestructura en caminos que permiten llegar de un punto a otro en casi cualquier combinaci´on de origen y destino. Y la versatilidad que le da el poder mover productos de cualquier tama˜ no y peso a cualquier distancia. Por su flexibilidad y versatilidad se ha convertido en la forma de transporte dominante en Am´erica y otras partes del mundo adem´as de que a podido ser involucrada en los programas de justo a tiempo (JIT)1 con resultados en menores y confiables tiempos de transito. La tendencia a utilizar esta forma de transporte va en aumento dada su compatibilidad con 1

Just in Time, metodolog´ıa japonesa para un desempe˜ no de inventarios ‘cero’

´ CAP´ITULO 1. INTRODUCCION

8

las necesidades de la industria por mover sus productos, mientras los proveedores de estos servicios se esmeren en proveer un r´apido y eficiente servicio a precios competitivos respecto a sus competidores en aire y tren, la industria del transporte por trailer prosperara. Una vez que se ha seleccionado el modo de transporte una de las tareas de mayor importancia y repercusi´on en los costos es la del ruteo y secuenciamiento. Considerando las grandes inversiones en equipo y localizaci´on de instalaciones que conllevan los gastos operativos, los transportistas han reconocido al importancia de un buen ruteo y secuenciamiento para alcanzar los niveles de ganancias y servicio al cliente deseados. En los u ´ltimos a˜ nos estas ´areas han aumentado su importancia debido a factores de competencia, legislaci´on y factores econ´omicos, ejemplos de estos factores son los tratados de libre comercio establecidos entre las naciones, costo de combustible, situaci´on laboral y capacidad e innovaciones en los equipos. Los transportistas se han dado cuenta que utilizando esta rama de la ciencia del transporte se puede alcanzar beneficios considerables optimizando las actividades de ruteo y secuenciamiento, aunque aqu´ı no ahondaremos en que clase de t´ecnicas se utilizan es importante mencionar que los grandes grupos industriales del mundo ya han dado la oportunidad para probar el valor de estas propuestas y han visto su aportaci´on en la disminuci´on de los costos de transporte. Algunas de las estrategias que se siguen son: preasignaci´on de embarques para una ´area espec´ıfica de mercado al mismo tiempo que se disminuyen la frecuencia de los env´ıos o visitas provocando un ahorro para el transportista. La reducci´on de la frecuencia de la recolecci´on y entrega resulta en una disminuci´on del nivel de transporte necesario para entregar la misma cantidad de producto, as´ı el costo de transporte se reduce y la productividad aumenta. Otros ejemplos incluyen el

´ CAP´ITULO 1. INTRODUCCION

9

fijar las rutas en lugar de tener rutas variables para algunos embarques y modificaci´on a las horas de recepci´on de producto por parte del cliente, si el cliente puede aceptar entregas fuera de los horarios cr´ıticos, el transportista tendr´a una ventana de tiempo m´as grande que le permitir´a una mejor administraci´on del uso de los veh´ıculos. En general los beneficios para los transportistas que mejoran su ruteo y secuenciamiento incluyen mayor utilizaci´on de los veh´ıculos, niveles mayores de satisfacci´on al cliente, disminuci´on de los costos de transporte, reducci´on de la inversi´on en equipo y una mejor administraci´on de la toma de decisiones. Como ejemplo de la aportaci´on de una mejor asignaci´on y ruteo la empresa Baskin-Robbins una compa˜ nia fabricante de helados con 2500 tiendas en EU al utilizar una herramienta computacional para determinar rutas y secuencias de su flotilla de transporte obtuvo ahorros de un 10 % de las millas recorridas totales de la flotilla, lo que se traduce en un beneficio econ´omico de $180,000.[34]

1.3.

Objetivo de tesis

Teniendo en cuenta que todo aquel productor de bienes de consumo necesita del transporte para hacer llegar su producto a la mayor parte del mercado y que este es realizado por tractocamiones propios o rentados bajo un esquema 3PL, en una infraestructura carretera que conecta a las plantas de producci´on con los centros de distribuci´on. El problema de qu´e recurso(tractocami´on), el camino que seguir´a para cumplir con una demanda establecida y los horarios en que debe estar disponible para cumplir con un horario de atenci´on para descarga y carga. El objetivo de este trabajo de investigaci´on y tesis es construir un modelo matem´atico adecuado a este problema que d´e soluci´on al problema de asignaci´on de recursos de transporte.

´ CAP´ITULO 1. INTRODUCCION

10

Como objetivos de este modelo tenemos: Definir la cantidad ´optima de recursos de transporte que minimice el costo total de transporte (fijo + variable). Cumpliendo con las siguientes restricciones. Volumen a mover. Ventanas de carga en los or´ıgenes. Ventanas de descarga en los or´ıgenes La manera m´as clara de ver el objetivo es poder responder a las preguntas ¿Qu´e veh´ıculo? ¿A d´onde debe de ir? ¿A qu´e hora esta disponible? Este modelo adem´as deber´a de poder ser implementado y probado con datos reales. El ´exito de los resultados obtenidos podr´a servir como base para futuros proyectos en colaboraci´on con la industria.

1.4.

Organizaci´ on de la tesis

La estructura de este trabajo esta dada de la siguiente forma: en el Cap´ıtulo 2 presentamos un amplio recorrido por la historia de los trabajos que han buscado trabajar variantes de este problema. El Cap´ıtulo 3 comprende la exposici´on del problema, la formulaci´on y explicaci´on detallada del modelo matem´atico MIP que ser´a resuelto mediante las t´ecnicas de la programaci´on entera mixta. El Cap´ıtulo 4 comprende el estudio de dos casos pr´acticos presentados por Sintec. Enseguida se presentan los experimentos hechos con problemas aleatoriamente generados en el Cap´ıtulo 5 y en el Cap´ıtulo 6 se presentan las conclusiones y las recomendaciones para los trabajos futuros.

Cap´ıtulo 2 El problema y sus antecedentes Desde la propuesta de Dantzig para resolver el problema de asignaci´on de veh´ıculos conocido por sus siglas en ingl´es como (VRP), muchos investigadores han tratado este problema. En aquel momento Dantzing y Ramser[7] presentaban la primer formulaci´on matem´atica para un problema del mundo real, este consist´ıa en la la entrega de gasolina a las estaciones de servicio. Unos a˜ nos mas tarde Clarke y Wright proponen una efectiva heur´ıstica “greedy” que mejora la soluci´on de Dantzing-Ramser. A m´as de 40 a˜ nos de la publicaci´on de estos art´ıculos, se han propuesto muchos modelos, t´ecnicas de soluci´on exactas, aproximaciones por heur´ısticas para resolver el VRP y sus variantes. En este cap´ıtulo abordaremos algunos de estos modelos al igual que algunas de las metodolog´ıas exactas y heur´ısticas utilizadas en los u ´ltimos a˜ nos.

2.1.

Introducci´ on a los problemas de ruteo.

La b´ usqueda de una mejor manera de administrar las cadenas de suministro ha permitido el incremento en el uso de paquetes de optimizaci´on basados en investigaci´on de operaciones y modelaci´on matem´atica. El uso de estas t´ecnicas muestra ahorros significativos entre el 5 % al 20 % de los costos totales de transporte. Estos costos por

11

CAP´ITULO 2. EL PROBLEMA Y SUS ANTECEDENTES

12

su participaci´on global adquieren m´as importancia dentro de los costo total de cualquier producto. Los problemas conocidos como Problema de Ruteo de Veh´ıculo(VRP) o Problema de Asignaci´on de Veh´ıculos (VSP) se pueden describir de una manera sencilla como sigue: Existen plantas de producci´on, almacenes o dep´ ositos(origen) en donde se encuentra el producto terminado, es necesario hacer llegar a los clientes(destino) una cantidad de producto (demanda), los clientes se encuentran localizados a cierta distancia de los puntos de origen. Para llegar a ellos el producto se mueve por veh´ıculos a trav´es de caminos trazados(red de distribuci´ on) Habitualmente los VRP’s son una perfecta descripci´on de los sistemas de distribuci´on de compa˜ n´ıas como Bimbo, Coca-Cola, Pepsi, Sabritas, etc. en general situaciones de recolecci´on y entrega de productos o servicios, ejemplos de estas son la recolecci´on de basura, transporte escolar o de personal, y en algunos casos los sistemas tipo entrega a domicilio (taxis, pizzeria, mensajeria) pueden ser modelados de la misma forma. De acuerdo a las caracter´ısticas en los elementos b´asicos del problema como: red de caminos, clientes, dep´ositos, veh´ıculos y conductores se pueden diferenciar entre varias definiciones del problema 1. Red de caminos. Las redes de distribuci´on son generalmente representadas por gr´afos en donde las aristas representan secciones de carretera o calles y los v´ertices las intersecciones de los arcos en donde se encuentran los dep´ositos y clientes. Estos pueden ser dirig´ıdos o no dirig´ıdos dependiendo de la configuraci´on real de las calles y carreteras, es decir si son de un solo sentido o en ambas direcciones. Adem´as a cada arco se le asocia un costo que representa la distancia y un tiempo de viaje el cual puede depender del veh´ıculo y el per´ıodo durante el cual el arco es recorrido.

CAP´ITULO 2. EL PROBLEMA Y SUS ANTECEDENTES

13

2. Los clientes pueden asumir las siguientes caracter´ısticas: Son localizados en los v´ertices del gr´afo, Se define una cantidad de productos (demanda) posiblemente de diferentes tipos para ser entregados o recolectados Per´ıodos de tiempo durante los cuales los clientes pueden ser atendidos Tiempos requeridos para recibir y recolectar los productos (carga y descarga) y pueden depender del tipo de veh´ıculo Un subconjunto de veh´ıculos a utilizar debido a restricciones de acceso o requerimientos para su carga y descarga Para los casos en que la demanda no puede ser totalmente satisfecha para cada cliente, la cantidad a entregar o recolectar es menor y un grupo de clientes queda sin ser atendido, se considera agregar penalizaciones o prioridades de servicio asignadas 3. Entre las consideraciones de los dep´ositos podemos encontrar tipo y n´ umero de veh´ıculos asignados, cantidad de productos para los que tiene capacidad. En algunos casos los clientes son asignados a priori a cada dep´osito, y los veh´ıculos tienen que regresar al dep´osito al terminar el d´ıa. 4. Para efectuar la transportaci´on de los productos se usan flotillas de veh´ıculos que pueden estar compuestas de manera homog´enea o heterog´enea de acuerdo a los requerimientos de los clientes las caracter´ısticas que presentan son: Asignaci´on a un dep´osito central y la posibilidad de terminar su servicio en un dep´osito diferente Capacidad del veh´ıculo expresada como el m´aximo de peso, volumen, n´ umero de pallets que un veh´ıculo puede cargar.

CAP´ITULO 2. EL PROBLEMA Y SUS ANTECEDENTES

14

Posible divisi´on del veh´ıculo en compartimientos para transportar diferentes tipos de productos, diferenciados por capacidad Dispositivos para su carga y descarga Existen costos asociados con el uso de los veh´ıculos ($/km , $/hr ) 5. Hay restricciones de operaci´on referentes a los veh´ıculos como las derivadas por la contrataci´on de conductores de los veh´ıculos y a las rutas, m´axima carga del veh´ıculo, clientes de solo entrega, solo recolecci´on o ambas.

2.2.

Trabajos sobre ruteo de veh´ıculos con ventanas de tiempo

El problema de ruteo de veh´ıculos con ventanas de tiempo (VRPTW) es una extensi´on del problema de ruteo de veh´ıculos con capacidad (CVRP) en el que se considera lo siguiente; los veh´ıculos tienen una capacidad limitada y cada cliente i tiene incorporado un intervalo de tiempo [ai , bi ] al que llamaremos ventana de tiempo . Tiempo de viaje dado para cada punto (i, j) mas un tiempo de servicio para cada cliente si . El tiempo en que un cliente comienza a ser atendido est´a asociado a su ventana de tiempo y podr´a estar en espera en la ubicaci´on del cliente en un tiempo igual a si , en caso de que el veh´ıculo llegue antes del tiempo ai se le esta permitido esperar hasta que inicie el servicio. El VRPTW consiste en encontrar una colecci´on exacta de de P circuitos simples un m´ınimo costo que cumpla con lo siguiente: Cada circuito visita el dep´osito. Cada cliente se encuentra en un solo circuito.

CAP´ITULO 2. EL PROBLEMA Y SUS ANTECEDENTES

15

La suma de las demandas de los clientes localizados en un circuito no puede sobre pasar la capacidad del veh´ıculo. Para cada cliente i el servicio inicia con la ventana de tiempo [ai , bi ] y el veh´ıculo se detiene si instantes de tiempo. Dada la importancia de este problema en la vida cotidiana, se han publicado numerosos trabajos, en los que consta la diversidad de planteamientos que se puede presentar. A continuaci´on se exponen algunos de ellos publicados y desarrollados durante los u ´ltimos 20 a˜ nos Entre los trabajos que se pueden encontrar, algunos investigadores han desarrollado compendios especiales del problema entre estos se encuentra el de Bodin et al. [19] con un resumen de ruteo y secuenciamiento de veh´ıculos. Solomon y Desrosiers en[24] son mas espec´ıficos en problemas de ruteo con restricciones de temporalidad algunos a˜ nos m´as tarde Desrosieres et al. actualiz´o este estudio y lo publica en [12]. En cuanto a los m´etodos de soluci´on heur´ısticos y exactos de los problemas VRPTW puede encontrarse una compilaci´on en [26]. Los trabajos iniciales que consideraban restricciones de tiempo en problemas de ruteo, se originan en el estudio del problema del agente viajero con ventanas de tiempo (TSPTW) y el problema de “dial-a-ride ”servicio a domicilio. Christofides et al. [31] definieron una t´ecnica que combina la soluci´on por medio de ramificaci´on y cotas y programaci´on din´amica para relajar el espacio de soluci´on de TSPTW. En el marco de estos trabajos Baker [4] public´o un modelo matem´atico que considera solo variables continuas, esta formulaci´on adem´as de incluir una funci´on de valor absoluto lo que excluye el uso de t´ecnicas de soluci´on de programaci´on lineal. Desrosiers et al. [13] modelaron este problema consider´andolo el problema de m´ıni-

CAP´ITULO 2. EL PROBLEMA Y SUS ANTECEDENTES

16

mo costo de flujo en redes con restricciones de tiempo, con este se pudo resolver exitosamente algunos problemas de secuenciamiento de veh´ıculos escolares con hasta 233 nodos. Psaraftis [9] estudi´o el problema de un veh´ıculo con visita a varios puntos bajo demanda, donde varios puntos se refiere a diferentes puntos de recolecci´on y entrega de bienes, nos referimos al concepto de bajo demanda a que la utilizaci´on del veh´ıculo se presenta solo cuando alguien solicita el servicio ej. (repartidor de comida, servicio de taxis). En esta investigaci´on uso programaci´on din´amica para minimizar la medida de insatisfacci´on de un cliente por el tiempo total que paso en el veh´ıculo. Problemas con hasta 9 clientes se resolvieron ´optimamente. En [14] Desrosiers et al. presentan una formulaci´on de programaci´on din´amica hacia adelante para el mismo problema tratado por Psaraftis, estos resuelven problemas de reales con hasta 40 clientes, y concluyen que su m´etodo es lo suficientemente robusto para resolver problemas m´as grandes pero debido a que en los problemas de la vida real las ventanas de tiempo son demasiado ajustadas el espacio de soluci´on se ve fuertemente reducido. Siguiendo la misma l´ınea de investigaci´on, Sexton y Bodin [36] trabajaron el mismo problema con restricciones en los tiempos de entrega y desarrollaron una heur´ıstica basada en descomposici´on de Benders para encontrar rutas factibles. Los m´etodos de soluci´on exacta usualmente consisten en procedimientos de enumeraci´on exhaustiva como los conocidos como: ramificaci´on y cotas o programaci´on din´amica. Estas t´ecnicas pueden resultar con tiempos de computo muy largos dada la dificultad del problema [32], para lograr una reducci´on de los tiempos se utilizan t´ecnicas como la relajaci´on lagrangeana, generaci´on de columnas o planos cortantes como ramificaci´on y cortes. Kolen et al. [1] estudiaron el VRPTW considerando solo un dep´osito y un solo tipo de

CAP´ITULO 2. EL PROBLEMA Y SUS ANTECEDENTES

17

servicio (entrega o recolecci´on) exclusivamente. Utilizando una t´ecnica de ramificaci´on y cota para minimizar el total de la distancia de la ruta pudieron resolver problemas con hasta 15 clientes con diferentes tiempos en las ventanas de tiempo. A pesar del tama˜ no de los problemas, se puede se˜ nalar el tama˜ no y la frecuencia de la ventana como el factor mas importante para determinar la dificultad del problema. Ni la capacidad del veh´ıculo ni fijar el numero de veh´ıculos tienen un impacto cercano al de las ventanas de tiempo. Desrochers et al. en su trabajo [27] usa la t´ecnica de generaci´on de columnas para resolver algunos problemas con 100 nodos hasta optimalidad con la funci´on objetivo de minimizar la distancia total recorrida. La idea para lograr esto consiste en formular el VRPTW como un problema ”Set partitioning.en el que se consideran todas las rutas factibles impl´ıcitamente. Ya que este n´ umero de rutas crece exponencialmente con el numero de clientes solo una fracci´on de las rutas es incluida en el modelo. En cada iteraci´on del procedimiento se realiza un chequeo para determinar la existencia de una ruta a´ un no incluida que pueda reducir el costo, esto se logra por la soluci´on relajada de un subproblema de ruta m´as corta con restricciones de tiempo y capacidad. Si la ruta existe su columna correspondiente es agregada al modelo y el procedimiento se repite hasta que el conjunto completo de rutas es encontrado. Para encontrar soluciones enteras con este algoritmo se trabaja con un esquema ramificaci´on y cotas. Kohl[30] usa la t´ecnicas de relajaci´on lagrangeana para descartar la restricci´on de atender a todos los clientes. Como resultado de la relajaci´on se transforma en un subproblema de ruta m´as corta con restricciones de tiempo y capacidad el cuales un problema mas f´acil de resolver, de cualquier forma encontrar los mejores multiplicadores de Lagrange requiere un considerable esfuerzo computacional. Usando esta t´ecnica se han resuelto problemas con hasta 100 clientes.

CAP´ITULO 2. EL PROBLEMA Y SUS ANTECEDENTES

18

La combinaci´on de planos cortantes con una b´ usqueda exhaustiva es conocida como ramificaci´on y corte. En esta aproximaci´on el problema inicial en formulado como un problema entero mixto lineal. As´ı las restricciones de integralidad se relajan y el problema lineal resultante es optimizado, si la soluci´on es entera entonces el algoritmo termina con una soluci´on ´optima del problema original y si la soluci´on es fraccional se agregan desigualdades o cortes v´alidos al modelo y el procedimiento se repite. Cuando no se pueden identificar mas cortes por el procedimiento de separaci´on o el efecto de cualquier desigualdad es marginal y la ramificaci´on ocurre. Padberg y Rinaldi en su trabajo[28] primero utilizaron el m´etodo de planos cortantes para resolver instancias grandes del problema del agente viajero (TSP). Una t´ecnica similar fue usada por Hoffman y Padberg [18] para resolver un problema de secuenciamiento de tripulaci´on de aerol´ıneas, otro trabajo es el de Aranque [10] desarroll´o un algoritmo ramificaci´on y corte para un problema de ruteo de veh´ıculos con clientes id´enticos, Augerat [33] presenta nuevas desigualdades para el problema de capacidad sim´etrica de ruteo de veh´ıculos. La soluci´on por m´etodos exactos de este problema solo es efectiva en tiempo en problemas de tama˜ no relativamente chico, esto hace u ´til el uso de t´ecnicas heur´ısticas. Una t´ecnica heur´ıstica es capaz de encontrar buenas soluciones en un tiempo menor esto hace que sean t´ecnicas atractivas de soluci´on para los problemas de gran tama˜ no que se encuentran en la industria. A continuaci´on se citar´an algunos trabajos que hacen uso de las t´ecnicas heur´ısticas para la soluci´on de estos problemas. Nygard et al. [17] estudiaron una variante del VRPTW considerando u ´nicamente ventanas de tiempo de un lado es decir de cierre. Inicialmente los clientes se agrupan en “clusters” resolviendo el problema general de asignaci´on, el siguiente paso es calcular los subtours ´optimos para cada grupo o cluster y finalmente un procedimiento de cambio

CAP´ITULO 2. EL PROBLEMA Y SUS ANTECEDENTES

19

de rama para asegurar que las restricciones temporales son satisfechas. Solomon [22] propuso una heur´ıstica de inserci´on secuencial para el problema de minimizaci´on del tama˜ no de la flota con un solo tipo de servicio del VRPTW. Las rutas son construidas una a la vez por la inserci´on de clientes en al mejor posici´on de acuerdo con un par´ametro en funci´on de costo. Diferentes soluciones se obtienen por la variaci´on de los par´ametros de la funci´on de costo. El peor caso en la aplicaci´on de esta heur´ıstica es Ω(n), donde n es el n´ umero de clientes, se puede encontrar a mas detalle la explicaci´on del uso de esta heur´ıstica en [23], esto significa que en el peor caso la proporci´on de la diferencia de la soluci´on de la heur´ıstica contra la soluci´on ´optima crece proporcionalmente con el n´ umero de clientes. Potvin y Rousseau [11]desarrollaron una heur´ıstica paralela a la versi´on de Solomon, en esta se construyen varias rutas al mismo tiempo insertando clientes en la mejor posici´on entre las rutas completas parcialmente. Las t´ecnicas heur´ısticas usualmente son complementadas por t´ecnicas de b´ usqueda en la vecindad para obtener resultados ´optimos locales. Iniciando con una soluci´on factible una nueva soluci´on se obtiene por el intercambio de la posici´on de un peque˜ no grupo de los clientes usualmente dos o tres. El intercambio de la posici´on de los clientes se enumera exhaustivamente hasta que no existe alguna reducci´on en la funci´on objetivo. Baker y Schaffer [5]estudiaron algunos procedimientos de b´ usqueda local para el VRPTW modificando los procedimientos de 2-opt y 3-opt de intercambio utilizados el problema cl´asico de VRP para poder tomar en cuenta las restricciones de las ventanas de tiempo y capacidad de los veh´ıculos. Dos trabajos recientes [25]de Solomon et al. y [29] Savelsbergh han buscado una disminuci´on de la complejidad del intercambio de planos en el VRPTW. Dentro de las t´ecnicas heur´ısticas utilizadas para la soluci´on del VRPTW , las que t´ecnicas probabil´ısticas han recibido mayor atenci´on por parte de los investigadores

CAP´ITULO 2. EL PROBLEMA Y SUS ANTECEDENTES

20

debido a su habilidad para trascender de una optimalidad local. Este mejoramiento en la b´ usqueda se alcanza por la diversificaci´on de la misma, pasando de ´areas en el espacio de soluci´on, de mejora muy pobre hacia ´areas m´as prometedoras. Thangiah et al. [35] en su trabajo propusieron una combinaci´on de b´ usqueda tabu, algoritmos gen´eticos y recocido simulado para solucionar el VRPTW. Con este m´etodo se han alcanzado los mejores resultados conocidos para problemas cl´asicos encontrados en la literatura. Potvin et al.[15] desarrollaron un algoritmo de b´ usqueda tabu, este algoritmo utiliza un algoritmo de intercambio especial, con el fin de aprovechar al soluci´on dada por la heur´ıstica determin´ıstica de Solomon. Potvin and Bengio [16] siguieron una forma de trabajo similar y usan las soluciones obtenidas por la heur´ıstica de Solomon para generar nuevas soluciones a partir de un algoritmo gen´etico. Rochat y Tailard en [37] trabajan con una heur´ıstica de probabilidad que aprovecha las capacidades de diversificaci´on e intesificaci´on de anteriores trabajos con b´ usqueda tabu. Otros m´etodos son los basados en K-arboles. Fisher[21] extendi´o el trabajo realizado por el m´etodo 1-arbol para el problema de ruteo de veh´ıculos y el ruteo de veh´ıculos con ventanas de tiempo. En esta aproximaci´on se supone que cada ruta contiene al menos dos clientes, se formula un modelo matem´atico particular y las restricciones son relajadas por el m´etodo lagrangeano.

Cap´ıtulo 3 Exposici´ on del Problema En muchas organizaciones, la administraci´on de las actividades de distribuci´on constituye un problema de toma de decisiones. Este problema ha cobrado m´as importancia debido a la contribuci´on de los costos de distribuci´on dentro de los costos totales. La mayor´ıa de las compa˜ n´ıas requieren de veh´ıculos para la recolecci´on y entrega dentro de una red de suministro o demanda. La utilizaci´on y ruteo eficiente de esta flotilla es el n´ ucleo de la mayor´ıa de los problemas de ruteo. Una pregunta que se efect´ ua con frecuencia por los gerentes de distribuci´on es ¿Cu´antos veh´ıculos son necesarios para satisfacer una demanda a un costo m´ınimo? Esta pregunta es dif´ıcil de contestar dada la enorme gama de combinaciones de mezcla de flotilla y rutas que pueden existir, abriendo la posibilidad de formular el problema presentado en esta tesis.

3.1.

Introducci´ on

Los problemas de ruteo de veh´ıculos existen en un ambiente compuesto por redes de distribuci´on formadas con Plantas de Producci´ on y varios Centros de Distribuci´on, este ambiente facilita la concentraci´on de los productos para facilitar su acceso a los

21

´ DEL PROBLEMA CAP´ITULO 3. EXPOSICION

22

clientes finales. Para realizar el transporte desde las plantas hasta los centros de distribuci´on, existe un proceso de selecci´on del tipo y la cantidad de veh´ıculos a asignar para realizar esta tarea. Esta selecci´on da lugar a un proceso de toma de decisiones auxiliado por la Investigaci´on de Operaciones. Mediante este proceso se busca minimizar los costos totales de transporte esto es: el costo fijo que es en el que se incurre por la adquisici´on del veh´ıculo ya sea por compra o renta del mismo, independientemente se use o no, el costo variable que representa los costos por combustible y distancia entre la planta y el centro de distribuci´on siempre que este veh´ıculo sea utilizado. Adem´as de estos, nuestra red de distribuci´on esta sujeta a horarios de atenci´on para carga y descarga de los veh´ıculos en los centros de distribuci´on como en la planta estos espacios de tiempo son conocidos como ventanas de tiempo.

3.1.1.

Por qu´ e optimizar?

La naturaleza del problema nos presenta alternativas en la toma de decisiones para lograr ahorros en la operaci´on. Un n´ umero ilimitado de veh´ıculos disminuir´ıa el incumplimiento en las ventanas de tiempo de los Centros de distribuci´on as´ı como un menor n´ umero de viajes totales a cada CD. Como consecuencia el costo fijo total de la flotilla ser´a muy alto. Con un n´ umero limitado de veh´ıculos el incumplimiento en las ventanas de tiempo en los CD ser´ıa mayor, adem´as el n´ umero de viajes tambi´en ser´ıa mas grande, lo que hace nuestro costo variable aumente .

´ DEL PROBLEMA CAP´ITULO 3. EXPOSICION

23

Encontrar el equilibrio entre estas dos alternativas da la posibilidad de poder plantear esta situaci´on como un problema de optimizaci´on que se pueda resolver mediante t´ecnicas de optimizaci´on.

3.1.2.

Sintec

Para la realizaci´on de esta tesis se cont´o con el apoyo de Sintec empresa de consultor´ıa en Generaci´on de Valor, a trav´es del desarrollo e implementaci´on estrategias y tecnolog´ıas que fortalezcan el desempe˜ no de la Cadena de Valor. Dentro de las consultor´ıas establecidas en M´exico, Sintec es uno de los principales generadores de educaci´on y capacitaci´on en temas de Cadena de Demanda, Cadena de Suministro, Tecnolog´ıa de la Informaci´on y organizador del evento Visum. Sintec, fue fundada en 1987 en Monterrey N.L M´exico y desde su fundaci´on ha sido una empresa l´ıder comprometida con la generaci´on de valor a sus clientes. Entre los clientes con los que ha trabajado estan las m´as importantes de M´exico entre ellos Coca Cola FEMSA, Cerveceria Cuahtemoc, Lamosa, Liverpool,Cemex,Qualtia. Dada la experiencia y reconocimento que ha adquirido en estos a˜ nos de excelentes resultados con sus clientes, por su cercan´ıa con la pr´actica de las t´ecnicas de la investigaci´on de operaciones y los problemas de nuestro interes para el desarrollo de una tesis, se consider´o una empresa adecuada para realizar este trabajo, por su parte se nos acept´o como una propuesta seria de trabajo y tenemos el orgullo de ser aceptados para presentar una soluci´on a un problema t´ıpicamente expuesto a ellos. Durante sesiones de trabajo con los gerentes del ´area de suministro Roberto Palacios y Gerardo Naranjo se obtuvo la informaci´on necesaria para hacer de este problema presente en la pr´actica un modelo de optimizaci´on, estos modelos ser´an presentados a continuaci´on.

´ DEL PROBLEMA CAP´ITULO 3. EXPOSICION

3.1.3.

24

Modelos Matem´ aticos

La informaci´on presentada por Sintec describe el problema expuesto en la introducci´on de este cap´ıtulo. Recordemos que este problema consiste en la selecci´on de recursos de transporte dentro de una red de distribuci´on compuesta por una Planta de producci´on y Centros de Distribuci´on con restricciones de horarios de atenci´on para carga y descarga de producto en cada una de las instalaciones. En el desarrollo de los modelos de optimizaci´on que representar´an la realidad del problema, por la gran y variable existencia de trabajos que tratan el problema del ruteo de veh´ıculos con ventanas de tiempo se pens´o que se podr´ıa adaptar alguno de los modelos ya existentes sin embargo con el estudio mas profundo de estos modelos entendimos que las suposiciones que los investigadores tomaron para estos modelos en la mayor´ıa de de los casos no representaban las mismas suposiciones de nuestro problema. Crear un modelo que considerara los supuestos presentados por Sintec es el objetivo de este trabajo. El modelo se fue construyendo en un proceso de evoluci´on hasta llegar al modelo que representa lo m´as fiel posible la situaci´on de la red y sus restricciones es decir la descripci´on del problema. Cabe mencionar que se ha buscado mantener la linealidad de los modelos lo que nos permitir´ıa la soluci´on del mismo por las t´ecnicas ya conocidas para problemas del tipo MIP Estos modelos son los siguientes. 1. Modelo I. Las consideraciones que se modelan son las siguientes: El Veh´ıculo es usado una sola vez Se satisface la demanda en cada cliente y se respetan las ventanas de tiempo Existe un solo tipo de veh´ıculos, es decir todos los veh´ıculos tienen las mismas

´ DEL PROBLEMA CAP´ITULO 3. EXPOSICION

25

caracter´ısticas de capacidad. Las rutas son fijas y enumeradas Resultados de este modelo: Este modelo no ofrece ninguna optimizaci´on sobre los costos de transporte solo cumple con la asignaci´on de un veh´ıculo por cliente como m´ınimo y si requiere hacer mas viajes para satisfacer demanda asigna un veh´ıculo nuevo por cada viaje extra que requiera para satisfacer demanda. Es importante saber que la capacidad del veh´ıculo es menor o igual que la demanda. Esta formulaci´on se toma como base de los siguientes modelos. 2. Modelo II. Las consideraciones en este modelo son las siguientes: El veh´ıculo deja el dep´osito, visita un cliente al terminar regresa al dep´osito y vuelve a visitar al mismo cliente hasta satisfacer demanda. Se satisface la demanda en cada cliente y se respetan las ventanas de tiempo Existe un solo tipo de veh´ıculos, es decir todos los veh´ıculos tienen las mismas caracter´ısticas de capacidad Las rutas son fijas y enumeradas Resultados de este modelo: Como consecuencia de permitir hacer varios recorridos por veh´ıculo, la cantidad de veh´ıculos asignados es igual al n´ umero de clientes. La toma de decisiones parte de los horarios en que deben ser asignadas las salidas en cada una de las ocasiones en que el veh´ıculo salga a realizar una entrega. Existen penalizaciones por llegadas temprano (el centro de distribuci´on aun no ha abierto) y por llegadas tarde (el centro de distribuci´on ya cerro). Por lo que busca el mejor acomodo en las salidas de los veh´ıculos para evitar violaciones en los horarios de los centros de distribuci´on.

´ DEL PROBLEMA CAP´ITULO 3. EXPOSICION

26

3. Modelo III Las consideraciones de este modelo son las siguientes: El veh´ıculo parte del dep´osito con el fin de visitar un cliente, este es visitado las ocasiones necesarias para satisfacer demanda Se satisface la demanda en cada cliente y se respetan las ventanas de tiempo Existe tres tipos de veh´ıculos, diferenciados por su capacidad. Resultados de este modelo: Contar con hasta tres tipos de veh´ıculo hace una asignaci´on de estos de acuerdo a las demandas de los clientes y a las diferentes capacidades de los veh´ıculos. Este modelo genera soluciones en la parte de la optimizaci´on de los costos variables. De acuerdo a las ventanas de tiempo se elige entre mandar un cami´on de la menor capacidad varias veces o uno de mayor capacidad un n´ umero menor de veces. Como resultado final de esta evoluci´on de modelos se obtiene un modelo matem´atico del tipo Entero Mixto Lineal (MIP)

3.2.

Formulaci´ on Matem´ atica

Como ya se ha descrito el problema que se trata de solucionar en este trabajo cosiste en la selecci´on de los recursos de transporte para distribuir productos entre una planta de producci´on y los centros de distribuci´on que mas adelante se har´an cargo de hacerlo llegar a los clientes finales. La soluci´on a este problema considera las siguientes suposiciones. Los t´erminos planta de producci´on y centros de distribuci´on son una particularidad de nuestro problema. A estos tambi´en se les puede mencionar como dep´osito y clientes respectivamente

´ DEL PROBLEMA CAP´ITULO 3. EXPOSICION

3.2.1.

27

Suposiciones del problema

1. Se satisface la demanda de todos los clientes. Esto significa que para todos los centros de distribuci´on que se encuentren asignados a una planta de producci´on se cumple con la oferta de servicio, es decir se le entrega el producto requerido en tiempo y cantidad. 2. Solo se calcula el tiempo de inicio del primer viaje de cada uno de los veh´ıculos. Es decir la optimizaci´on del tiempo al que debe iniciar cada viaje considera el mejor primer tiempo para iniciar la entrega de todos los pedidos que pueda hacer ese veh´ıculo de acuerdo a las ventanas de tiempo de los centros de distribuci´on 3. Existen las penalizaciones por llegada fuera del horario de servicio. Esto significa, que se puede ajustar el nivel de servicio que se desea proveer a los centros de distribuci´on. Las penalizaci´on por llegada fuera del horario de servicio se puede fijar en tarifas muy altas lo que nos representa la situaci´on en la que no se permite la violaci´on al horario de servicio, por consiguiente el nivel de servicio es de 100 % , por el contrario si se requiere presentar la situaci´on en que se sacrifique el nivel de servicio estas tarifas se ajustan en costos a los que el modelo eval´ ua, y as´ı obtener una selecci´on entre salir del horario permitido o adquirir mas veh´ıculos de acuerdo al costo. 4. La capacidad m´axima de cualquiera de los tipos de veh´ıculos disponibles es inferior a la demanda de los centros de distribuci´on, es decir en un solo cami´on y un viaje no se podr´ıa satisfacer la demanda.

´ DEL PROBLEMA CAP´ITULO 3. EXPOSICION

28

5. Los veh´ıculos pueden visitar a un cliente tantas veces se ha necesario para satisfacer la demanda dentro de las ventanas de tiempo de cada cliente. Otra forma en la que se presenta este problema es cuando el cliente tiene una demanda m´ ultiplo de la capacidad de los veh´ıculos. El abastecimiento de las estaciones de servicio de PEMEX es el ejemplo de este tipo de problema. En este la demanda a satisfacer es por “pipas ”completas de combustible, estas deben visitar la estaci´on de servicio 2 o 3 veces por d´ıa. 6. El problema es determin´ıstico.

3.2.2.

Definici´ on del Modelo Matem´ atico

1. El modelo matem´atico resultante, definido por las restricciones y la funci´on objetivo, se plantea como un modelo Lineal Entero Mixto (MIP) y se utiliza la siguiente notaci´on. Conjuntos e ´Indices I

Conjunto de los clientes

J

Conjunto de los viajes

K

Conjunto de los veh´ıculos

i=´Indice de los Clientes i, ∈ I = {0, 1, 2, 3..I} El cliente 0 es la planta de producci´on ocasionalemente tambien se conoce como dep´osito j=´Indice de los viajes j ∈ J = {1, 2, 3..J} k=´Indice de los Veh´ıculos k ∈ K = {1, 2, 3..K}

´ DEL PROBLEMA CAP´ITULO 3. EXPOSICION

29

Par´ ametros Ei = La hora de apertura de la ventana de tiempo en cada cliente i ∈ I. Li =La hora de cierre de la ventana de tiempo en cada cliente i ∈ I. Cikt = Costo de viaje al cliente i con el veh´ıculo k del tipo t; i ∈ I, k ∈ K, t ∈ T. Fkt =Costo Fijo del veh´ıculo k del tipo t; k ∈ K, t ∈ T . Cdi =Costo por llegada tarde al cliente i; i ∈ I. Cei =Costo por llegada temprano al cliente i; i ∈ I. Di =Demanda en cada cliente i ;i ∈ I. θi =Tiempo que dura el recorrido al cliente i; i ∈ I. Qkt =Capacidad del veh´ıculo k tipo t; k ∈ K, t ∈ T. Variables    1 Si el cliente i es visitado en el viaje j por el vehiculo k. Xijk =   0 Si no

Yk =

   1

Si el veh´ıculo k es usado

  0

Si no

Sjk

=Tiempo en que sale el veh´ıculo k en el viaje j.

+ Wijk

=Tiempo que espera el veh´ıculo k en el cliente i en su viaje j

− Wijk

=Tiempo que esta retrasado el veh´ıculo k en el cliente i en su viaje j

Ver que el uso del ´ındice j como un contador interno discreto del tiempo para cada veh´ıculo k, asi en cualquier viaje j el veh´ıculo k puede estar con un cliente o permanecer en el dep´osito (i = 0)

´ DEL PROBLEMA CAP´ITULO 3. EXPOSICION

30

Formulaci´ on

m´ın

X

Fk Yk +

k

X

+ − Cik Xijk + Cei Wijk + Cdi Wijk




(3.1)

ijk

Sujeto a:

X0jk +

X

Xijk = 1; j ∈ J, k ∈ K

(3.2)

i6=0

X Jk −

Qk Xijk ≥ di ; i ∈ I/0

X

(3.3)

X0jk ≤ Yk Jk ; k ∈ K

(3.4)

X

(3.5)

Sj+1,k ≥ Sjk +

Xijk 2θi ; j ∈ J, k ∈ K

+ Wijk ≥ Ei Xijk − (Sjk + θi Xijk ) ; i ∈ I, j ∈ J, k ∈ K

(3.6)

− Wijk ≥ (Sjk + θi Xijk ) − Li − M (1 − Xijk ) ; i ∈ I, j ∈ J, k ∈ K

(3.7)

+ − Xijk , Yk ∈ {0, 1} , Wijk , Wijk , Sjk ≥ 0

(3.8)

La expresi´on 3.1 representa la funci´on objetivo donde se minimiza el total de los costos fijos, costos de viaje y costos por desviaciones de la ventana de atenci´on a cliente. La minimizaci´on resulta de la obtenci´on de los mejores valores de las variables de + + decisi´on Xijk, Yk , Wijk , Wijk que minimicen el costo total.

El conjunto de las restricciones 3.2 asegura que para cualquier viaje un veh´ıculo se encuentra exactamente en un cliente o en el dep´osito (cliente (0). Una restricci´on obligatoria en la mayor´ıa de los problemas de ruteo es la de cumplimiento de la demanda en los clientes esta se asegura con la expresi´on 3.3, esta establece que la demanda de cada cliente debe ser satisfecha. El conjunto de las restricciones 3.4 junto con el objetivo de minimizar aseguran que s´ı el veh´ıculo permanece en todos los viajes en el dep´osito este no ha sido usado. Las

´ DEL PROBLEMA CAP´ITULO 3. EXPOSICION

31

siguientes restricciones formulan las condiciones que se tienen sobre el tiempo as´ı el conjunto de restricciones 3.5 determina que un viaje solo puede iniciar hasta que el veh´ıculo k ha regresado al dep´osito de su viaje previo. La restricci´on del tipo 3.6 en conjunto con el objetivo de minimizaci´on asegura que si en cualquier viaje j, el cliente no es visitado (Xijk = 0) entonces no hay costo por + llegar temprano dado que (Wijk = 0), si el cliente si es visitado (Xijk = 1) el calculo de

la desviaci´on del tiempo se calcula de forma normal . De manera similar las restricciones 3.7 estiman el tiempo por llegada despu´es del fin de la ventana de tiempo. Aqu´ı M es un n´ umero entero positivo(M > Sjk − Li ). + − Es claro que en 3.6 y en 3.7 Wijk ≥ 0 solo para Sjk + ti < Ei mientras que Wijk ≥0

+ − solo para Sjk + ti > Li . As´ı para Ei < Li siempre existe Wijk Wijk = 0. La soluci´on

de 3.1-3.8 indica la cantidad de veh´ıculos a ser usados (Yk ), provee de un programa de distribuci´on dado por el orden de las visitas (Xijk ) y el horario en que los veh´ıculos deben despacharse en cada viaje (Sjk ).

3.3. 3.3.1.

M´ etodo de soluci´ on Programaci´ on Entera (MIP)

En contraste con los problemas de programaci´on lineal, los problemas formulados en programaci´on entera tienen mayor dificultad para resolverlos. En realidad no existe un algoritmo de aplicaci´on general que pueda resolver este tipo de problemas. La falta de este algoritmo general da cabida a intentar resolver este tipo de problemas mediante varios tipos de algoritmos. Existen tres categor´ıas principales de algoritmos de soluci´on:[2] (a) Algoritmos Exactos, estos aseguran la obtenci´on de una soluci´on ´optima a expensas

´ DEL PROBLEMA CAP´ITULO 3. EXPOSICION

32

de un n´ umero alto de iteraciones. Dentro de este grupo se encuentran los algoritmos planos cortantes, ramificaci´on - cota, ramificaci´on-corte y programaci´on din´amica. (b) Algoritmos de Aproximaci´on, estos obtienen una soluci´on suboptima en un tiempo polinomial junto con una cota respecto al grado de suboptimalidad presente. (c) Algoritmos heur´ısticos proveen una soluci´on suboptima , pero sin garantizar su calidad, adem´as su tiempo de ejecuci´on no se garantiza que sea polinomial, estudios emp´ıricos apuntan a que en la mayor´ıa de los casos se logra una buena soluci´on r´apidamente, algunos ejemplos de estos m´etodos son las b´ usquedas locales, recocido simulado, b´ usqueda TABU, Algoritmos gen´eticos. En la b´ usqueda de la soluci´on de nuestra formulaci´on se utiliza la t´ecnica de ramificaci´on-cota, esta es muy utilizada en las herramientas computacionales dise˜ nadas para resolver estos problemas. Como se explica mas adelante las herramientas computacionales logran implementar estos algoritmos con ´exito adem´as de resolver problemas muy grandes en poco tiempo.

3.3.2.

Herramientas Computacionales

Aunque las t´ecnicas de soluci´on puedan realizarse a “mano”, en la realidad es dif´ıcil encontrar problemas que se puedan solucionar de forma manual, el apoyo de las herramientas computacionales ha permitido a trav´es de los a˜ nos incrementar la dificultad de los problemas a resolver, el avance en las tecnolog´ıas computacionales a dado, mas libertad para plantear problemas mas complejos y que requieran de mas c´alculos. Para solucionar el modelo matem´atico planteado en este trabajo se utilizaron dos herramientas computacionales, la primera es el lenguaje modelador, este programa es utilizado en la creaci´on del modelo matem´atico de forma que la computadora lo pueda entender y as´ı resolver. Existe gran variedad de modeladores matematicos entre los que

´ DEL PROBLEMA CAP´ITULO 3. EXPOSICION

33

se encuentran LINDO, GAMMS, AMPL,XPress MP, etc [6]. Un lenguaje modelador toma la formulaci´on matem´atica anteriormente descrita y transforma en un conjunto de instrucciones que mas adelante podr´an ser interpretadas por otro programa conocido como el motor de soluci´on (solver), esta es la segunda herramienta necesaria para resolver problemas de optimizaci´on. Entre los motores de soluci´on uno de los mas conocidos y robusto es CPLEX de Ilog este motor de soluci´on contiene los algoritmos de soluci´on para PL,MIP,QP, adem´as de este existen otros solucionadores como LINGO, MOSEK,SOPT, XPress con variantes de capacidad en el tipo de problemas que resuelven. En el articulo [6] se describe una encuesta actualizada del software disponible para solucionar los problemas de la programaci´on lineal. Como lenguaje modelador para resolver nuestro problema se selecciono AMPL por ser una herramienta en la que f´acilmente se puede implementar cualquier formulaci´on matem´atica propuesta. En AMPL la formulaci´on matem´atica se divide en dos elementos, uno el modelo matem´atico es decir la funci´on objetivo, las restricciones y las variables, el otro elemento son los datos concretos del problema a resolver. Estos dos elementos se guardan por separado en dos archivos uno es el modelonombre.mod y el que contiene los datos modelonombre.dat. Una vez que se tiene la formulaci´on del problema en AMPL se resuelve mediante el solver CPLEX de Ilog, en nuestro caso Cplex implementa un algoritmo de BranchBound muy similar al explicado anteriormente para resolver el problema. Para mas detalle sobre AMPL y Cplex en la secci´on de Ap´endices, se encuentra un resumen con lo mas relevante de las herramientas.

Cap´ıtulo 4 Casos Pr´ acticos Con el apoyo de Sintec se pudieron plantear dos problemas pr´acticos presentes en sus clientes. Para dos empresas de productos de consumo que tuvieron la necesidad definir el tama˜ no y tipo de la flota de transporte para realizar la distribuci´on de sus productos. En ambos casos se considera de gran importancia el nivel de servicio otorgado por estas compa˜ nias, y la implicaciones de no satisfacer al cliente por lo que la definici´on de la flota esta basada en supuestos de servicio.

4.1.

Caso 1

Figura 4.1: Red de distribuci´on Valle de M´exico El caso uno se localiza en una red de distribuci´on en el ´area del Valle de M´exico 34

´ CAP´ITULO 4. CASOS PRACTICOS

35

y esta formada por una planta de producci´on y 13 centros de distribuci´on, la figura( 4.1)muestra la una vista de la red cada uno de estos centros de distribuci´on tiene horario definido de apertura de 8:00 a.m y de cierre de 5:00 p.m, estos son estrictos en su cumplimiento debido al enfoque de servicio en el que se est´an plateando los problemas. La tabla 4.1 muestra los datos de cada uno de los centros de distribuci´on en este caso los costos por llegada adelantada o en retraso se consideran los suficientemente grandes para evitar la llegada fuera de las ventanas y resolver el modelo con las ventanas de tiempo duras. Cliente

Hora apertura cierre Dep´osito 0 24 La Viga 8 17 Vallejo 8 17 Zaragoza 8 17 Tlalpan 8 17 Iztapalapa 8 17 Mixcoac 8 17 Tlalnepanatla 8 17 Cuatitlan 8 17 Huixquilucan 8 17 Reyes 8 17 Chalco 8 17 Texcoco 8 17 Coacalo 8 17

Costos Demanda Adelantado Retrasado 0 0 0 100000 100000 772.12 100000 100000 870.47 100000 100000 2300.80 100000 100000 2401.05 100000 100000 2674.23 100000 100000 3671.67 100000 100000 4807.42 100000 100000 5156.43 100000 100000 7999.24 100000 100000 8521.68 100000 100000 8893.52 100000 100000 10878.64 100000 100000 12452.37

Tiempo Recorrido 0 3.63 3.63 4.63 4.13 4.04 4.63 3.63 1.63 4.13 4.63 4.63 5.63 5.125

Tabla 4.1: Par´ametros clientes Los datos de los veh´ıculos utilizados se presentan en la siguiente tabla Veh´ıculos 1-29 30-50

Costo fijo Capacidad 10000 1440 15000 2880

Tabla 4.2: Par´ametros de los veh´ıculos Para cada destino se tiene diferente costo variable dependiendo de factores como la distancia y tipo de caminos transitados

´ CAP´ITULO 4. CASOS PRACTICOS Destino Laviga Vallejo Zaragoza Tlalpan Iztapalapa Mixcoac Tlalnepantla Cuatitlan Huixquilucan Reyes Chalco Texcoco Coacalco

36 Costo Variable $1103 $1116 $1181 $1168 $1094 $1116 $1160 $1203 $1081 $1203 $1344 $1269 $1291

Tabla 4.3: Costos Variables a cada destino Como resultado del modelo se obtiene un programa de distribuci´on con detalle en las horas a las que debe salir, el destino de cada veh´ıculo, por cada uno de los viajes de salida, para este problema el m´aximo n´ umero de viajes que puede realizar cada veh´ıculo es de 7 dado el tiempo de recorrido que hay entre el dep´osito y los centros de distribuci´on. Los resultados de secuenciamiento se presentan a continuaci´on. Estos est´an divididos en dos partes de acuerdo a la capacidad de los veh´ıculos primero se muestran los veh´ıculos de capacidad sencilla ver tabla 4.4 es decir trailer de una caja. A continuaci´on se presenta el programa de distribuci´on para los veh´ıculos dobles o “full ”ver la tabla(4.5). Los resultados mostrados en estas tablas se pueden ilustrar con el siguiente ejemplo: El veh´ıculo 1 inicia su viaje hacia Reyes a las 3.37 (aproximadamente las 3:22 horas), regresa al dep´osito a las 12.63 (aproximadamente las 12:37), por las consideraciones hechas en este problema suponemos disponibilidad inmediata para iniciar el siguiente viaje, as´ı el veh´ıculo 1 es asignado para seguir hacia Vallejo. Una conclusi´on impor-

´ CAP´ITULO 4. CASOS PRACTICOS

Veh´ıculo Destino 1 Reyes 1 Vallejo 2 Coacalco 3 Huixquilucan 3 Reyes 4 Huixquilucan 4 Chalco 5 Chalco 6 Chalco 7 Coacalco 8 Reyes 8 La Viga 9 Chalco 10 Chalco 11 Reyes 12 Coacalco 13 Coacalco 14 Coacalco

Programa de Distribuci´ on Tiempo Inicio Tiempo de viaje 3.37 9.26 12.63 7.26 2.875 10.25 3.87 8.26 12.13 9.26 3.87 8.26 12.13 9.26 3.87 9.26 3.37 9.26 2.875 10.25 3.37 9.26 12.63 7.26 3.37 9.26 3.37 9.26 3.37 9.26 2.875 10.25 2.875 10.25 2.875 10.25

37

Tiempo disponibilidad 12.63 19.89 13.125 12.13 21.39 12.13 21.39 13.13 12.63 13.125 12.63 19.89 12.63 12.63 12.63 13.125 13.125 13.125

Tabla 4.4: Resultados Clientes Veh´ıculos Sencillos tante de los resultados obtenidos es que de un total de 50 veh´ıculos disponibles solo se requieren 25 para la satisfacci´on de la demanda de los 13 clientes asignados de la siguiente forma: 14 veh´ıculos de capacidad sencilla y 11 veh´ıculos de doble capacidad. Los resultados como el tiempo de soluci´on se muestran en la siguiente tabla ( 4.6). Aunque en este tiempo no obtenemos una soluci´on ´optima nuestra soluci´on factible alcanzada en 1 hora resulta una excelente propuesta dado el n´ umero de veh´ıculos a utilizar en total para cumplir con el servicio. Es importante mencionar que la optimalidad del problema resulta ser un criterio subjetivo para evaluar la efectividad de nuestro modelo, la optimalidad de un resultado en este tipo de problemas se comprueba hasta que se explora la totalidad del ´arbol creado por el m´etodo de ramificaci´on y cota. En su aplicaci´on en los problemas reales, este ´arbol puede alcanzar un tama˜ no en

´ CAP´ITULO 4. CASOS PRACTICOS

Veh´ıculo Destino 15 Reyes 15 Tlapan 16 Tlalnepantla 16 Mixcoac 17 Iztapa 17 Chalco 18 Texcoco 18 Cuatitlan 19 Texcoco 20 Mixcoac 20 Huixquilucan 21 Huixquilucan 21 Zaragoza 22 Tlalnepantla 22 Coacalco 23 Coacalco 24 Texcoco 25 Texcoco 25 Cuatitlan

Programa de Distribuci´ on Tiempo Inicio Tiempo de viaje 3.37 9.26 12.63 8.26 4.37 7.26 11.63 9.26 3.96 8.08 12.04 9.26 2.37 11.26 13.63 3.26 2.37 11.26 3.37 9.26 12.63 8.26 3.87 8.26 12.13 9.26 4.37 7.26 11.63 10.25 2.87 10.25 2.37 11.26 2.37 11.26 13.63 3.26

38

Tiempo disponibilidad 12.63 20.89 11.63 20.89 12.04 21.3 13.63 16.89 13.63 12.63 20.89 12.13 21.39 11.63 21.88 13.12 13.63 13.63 16.89

Tabla 4.5: Resultados Clientes Veh´ıculos Dobles el que por la restricci´on del tiempo la exploraci´on total del ´arbol resulta intrascendente cuando con un tiempo l´ımite se alcanza una soluci´on que satisface el requerimiento de beneficios esperados. ´ Nombre del Problema Tiempo CPU Nodos Arbol Objetivo VrpSin1 3,706 Seg 31,513 $ 350,136 Tabla 4.6: Resultados Caso Pr´actico 1

4.2.

Caso 2

El caso dos se presenta para otro cliente de Sintec, en este la red de distribuci´on varia un poco y solo modelamos un segmento de los clientes de esta empresa de productos

´ CAP´ITULO 4. CASOS PRACTICOS

39

de consumo (GAMESA). La red esta formada por una planta productora situada en Monterrey, N.L y 5 de sus clientes de mayor volumen y con entrega centralizada en sus centros de distribuci´on, este tipo de clientes fue seleccionado por las suposiciones en las que se baso la formulaci´on del modelo general.

Figura 4.2: Red de distribuci´on Clientes Centralizados Es decir estos clientes cumplen con los requisitos de tener una demanda mayor a la capacidad de los veh´ıculos disponibles, poder ser visitados mas de una vez si es necesario para satisfacer la demanda y tener ventanas tiempo para recepci´on de producto. De igual manera que con el caso uno se presentan los datos de este problema en la tabla 4.7 Cliente Planta HEB GCA SCM WBM WSC

Hora apertura cierre 0 0 6.5 22.5 7 22 0 23.98 0 12 0 12

Costos Demanda Adelantado Retrasado 0 0 0 100000 100000 191 100000 100000 114 100000 100000 142 100000 100000 240 100000 100000 201

Tabla 4.7: Par´ametros clientes Caso 2

Tiempo Recorrido 0 8.54 4.11 6.93 5.88 5.8

´ CAP´ITULO 4. CASOS PRACTICOS

40

Los datos de los veh´ıculos utilizados se presentan en la siguiente tabla Veh´ıculos 1-10 11-15

Costo fijo Capacidad 10000 24 20000 40

Tabla 4.8: Par´ametros de los veh´ıculos En este caso, cada uno de los clientes esta situado en un rango de distancia considerado por la empresa como un per´ımetro m´ınimo o “local ”por lo que el costo en el que se incurre en cada uno de los viajes es el mismo. Destino HEB GCA SCM WBM WSC

Descripci´on HEB Gigante Soriana Walmart Mty Walmart Super C

Costo Variable $300 $300 $300 $300 $300

Tabla 4.9: Costos Variables a cada destino El resultado de este problema de igual forma se presenta como un programa de distribuci´on en el que se detalla la hora de salida y el destino de cada uno de los viajes ejecutados. Para este problema el n´ umero m´aximo de viajes que puede realizar un veh´ıculo es de 5. Es decir el cliente mas cercano se encuentra a 4.1 horas de distancia de la planta de producci´on, por lo que en 24 horas cualquier veh´ıculo cuando mucho podr´a ir y venir 5 veces a este cliente, de acuerdo a esta relaci´on mientras mas lejos este el cliente menos viajes consecutivos en un d´ıa se pueden realizar a este. Otra consideraci´on es que el tiempo definido en los par´ametros ya incluye los tiempos de carga y descarga y son totalmente sim´etricos. Los resultados para este caso resultan muy buenos puesto que actualmente se cuenta con una flota dedicada de 15 veh´ıculos y nuestros resultados generan un programa que satisface la demanda de los clientes con 7 veh´ıculos.

´ CAP´ITULO 4. CASOS PRACTICOS

41

Programa de Distribuci´ on Veh´ıculo Destino Tiempo Inicio Tiempo de viaje Tiempo disponibilidad 2 WBM 0 5.88 5.88 2 WSC 5.88 5.8 11.68 2 HEB 11.68 8.54 20.22 2 SCM 20.22 6.92 27.14 4 WSC 0 5.8 5.8 4 WBM 5.8 5.88 11.68 4 HEB 11.68 8.54 20.22 4 SCM 20.22 6.92 27.14 6 WSC 0 5.8 5.8 6 WSC 5.8 5.8 11.6 6 HEB 11.6 8.54 20.14 6 SCM 20.14 6.92 27.06 Tabla 4.10: Programa de Distribuci´on Clientes Autoservicio De estos tres son de capacidad sencilla como se ve en la tabla (4.10). Y los restantes cuatro, de capacidad doble los resultados se presentan en la tabla(4.11) Programa de Distribuci´ on Veh´ıculo Destino Tiempo Inicio Tiempo de viaje Tiempo disponibilidad 12 WSC 0 5.8 5.8 12 WBM 5.8 5.88 11.68 12 GCA 11.68 4.1 15.78 12 GCA 15.78 4.1 19.88 13 WBM 0 5.88 5.88 13 WSC 5.88 5.8 11.68 13 HEB 11.68 8.54 20.22 13 SCM 20.22 6.92 27.14 14 WSC 0 5.8 5.8 14 WBM 5.8 5.88 11.68 14 GCA 11.68 4.1 15.78 14 HEB 15.78 8.54 24.32 Tabla 4.11: Programa de Distribuci´on Clientes Autoservicio

´ CAP´ITULO 4. CASOS PRACTICOS

42

Programa de Distribuci´ on Veh´ıculo Destino Tiempo Inicio Tiempo de viaje Tiempo disponibilidad 15 WBM 5.88 5.88 11.76 15 HEB 11.76 8.54 20.3 15 SCM 20.3 6.92 27.22 Tabla 4.12: Programa de Distribuci´on Clientes Autoservicio (Cont...) Nuevamente obtenemos un resultado satisfactorio en poco tiempo, este secuenciamiento adem´as produce una disminuci´on de los veh´ıculos con los que se cuenta actualmente. ´ Nombre del Problema Tiempo CPU Nodos Arbol Objetivo VrpSin2 1,130 Seg 69187 $ 298,400 Tabla 4.13: Resultados Caso Pr´actico 2

Cap´ıtulo 5 Experimentos Computacionales Dentro de este cap´ıtulo se demuestran resultados de varios problemas generados aleatoriamente con el fin de evaluar y generar conclusiones de la efectividad del modelo propuesto. Se determinaron dos tipos de pruebas: 1)Problemas de tipo ventanas de tiempo suave, es decir problemas en los que se es permitido la llegada de los veh´ıculos fuera de las ventanas de atenci´on pagando un costo. 2)Problemas de tipo ventanas de tiempo duras, es decir problemas en los que la llegada fuera de los horarios de atenci´on NO es permitida bajo ninguna circunstancia.

5.1.

Generaci´ on de problemas

Para la elaboraci´on de de los experimentos computacionales se requiri´o de la codificaci´on de un programa en Lenguaje C++ y de la definici´on de una nomenclatura clara que nos permita identificar las dimensiones y diferentes tipos de problemas generados. El programa en Lenguaje C++ nos permite escribir el archivo de los datos modelo.dat que es necesario para que AMPL pueda resolver el modelo, la necesidad de este programa se justifica en la rapidez con la que se pueden escribir problemas en los que la cantidad de los clientes y veh´ıculos nos generan tablas de datos de ms de 5 renglones

43

CAP´ITULO 5. EXPERIMENTOS COMPUTACIONALES

44

Nombre del Problema Significado vrpxxzzyy-j-h xx Cantidad de clientes zz Cantidad de veh´ıculos yy Tipo de veh´ıculos j N´ umero de viajes h Si es problema con las ventanas duras Tabla 5.1: Nomenclatura problemas generados por 10 columnas, es decir escribir a “mano ”un problema de 5 clientes con 10 veh´ıculos no consume mucho tiempo, sin embargo al querer probar nuestro modelo con instancias mas grandes como, 50 veh´ıculos 80 clientes resulta una tarea complicada escribir una tabla de 4000 datos. El programa genera un archivo con el formato de los archivos .dat que requiere AMPL, introduciendo los par´ametros: n´ umero de veh´ıculos, n´ umero de clientes, viajes, estos datos definen los conjuntos del modelo, ademas aleatoriamente se generan los costos fijos, variables, penalizaciones por violar ventanas de tiempo, demanda y tiempos de viaje. El archivo de salida de este programa sigue las siguientes reglas de nomenclatura. Tabla( 5.1) De esta forma con leer el nombre del problema podemos darnos cuenta de las dimensiones y del tipo que es. Por ejemplo un problema con nombre vrp3030-1-7.dat define a un problema de tama˜ no 30 clientes con 30 veh´ıculos de 1 solo tipo y con 7 viajes. Si se requiere de las ventanas del tipo duro se agrega una -h como u ´ltimo par´ametro.

5.2.

Problemas de Asignaci´ on de veh´ıculos con ventanas suaves de tiempo

Se ejecutaron pruebas de diferente tama˜ no teniendo como criterio para definir los veh´ıculos iniciales como el mismo n´ umero que el de los clientes. Se probaron dos es-

CAP´ITULO 5. EXPERIMENTOS COMPUTACIONALES

45

cenarios: con un solo tipo de veh´ıculo disponible y con veh´ıculos de diferentes tipos (capacidad). Dentro de este conjunto problemas solo se considera las ventanas de tiempo que pueden incumplirse con el pago de un costo de acuerdo al tiempo que quede fuera de las ventanas. Debido al tama˜ no de los problemas, el optimizador tiene que tener un criterio de interrupci´on, para todos los casos se decidi´o que fuera un tiempo total de ejecuci´on de 7 hrs CPU. Por lo que el algoritmo utilizado por CPLEX se detiene si no obtiene una soluci´on entera en un lapso de 7 horas. Los resultados de los problemas con un solo tipo de veh´ıculo se presentan a continuaci´on Nombre del Problema vrp3060-1-7 vrp3260-1-7 vrp4060-1-7 vrp4560-1-7-1 vrp5060-1-7 vrp50100-1-7-1

Tiempo CPU 3.08 Seg 303.2 Seg 18.4 Seg 5.34 Seg 8.4 Seg 10.82 Seg

Valor Objetivo $93,474 $ 76,877 $ 114,753 $134,476 $ 143,379 $ 173,773

Tabla 5.2: Resultados Ventanas Suaves 1-tipo de veh´ıculo Los resultados definiendo varios tipos de veh´ıculos se presentan a continuaci´on Nombre del Problema vrp3030-2-7 vrp3060-3-7 vrp4030-2-7 vrp4030-3-7-1 vrp4030-3-7 vrp5060-3-7-1 vrp5060-3-7 vrp6075-2-7-1 vrp6075-2-7 vrp5060-2-7

Tiempo CPU 3.05 Seg 3.21 Seg 596.9 Seg .58 Seg 106.46 Seg 3.28 Seg 497.76 Seg 17.94 Seg 5.64 Seg 5.69 Seg

Valor Objetivo $36,573 $ 105,235 $ 85,668 $ 54,392 $ 169,340 $ 133,135 $ 181,266 $ 1,166,241 $ 126,991

Tabla 5.3: Resultados Ventanas Suaves

CAP´ITULO 5. EXPERIMENTOS COMPUTACIONALES

46

En esta tabla se pueden observar los tiempos de soluci´on de los problemas propuestos aleatoriamente as´ı como el valor de la funci´on objetivo. Para estos problemas de acuerdo con las ventanas suaves el total del costo esta compuesto s´olo por los costos fijos y los costos variables de cada ruta. Nombre del Problema N. Cliente vrp3030-2-7 30 vrp3060-3-7 30 vrp4030-2-7 40 vrp4030-3-7-1 40 vrp4030-3-7 40 vrp5060-3-7-1 50 vrp5060-3-7 50 vrp6075-2-7-1 60 2 vrp6075-2-7 60 vrp5060-2-7 50

V. Originales 30 60 30 30 60 60 75 75 60

V. Soluci´on 4 20 17 8 33 26 46 54 39

Tabla 5.4: Resultados Veh´ıculos utilizados con Ventanas Suaves De igual forma que en los casos pr´acticos es importante hacer notar la cantidad final de veh´ıculos que se utilizar´ıan para cumplir con el programa de distribuci´on propuesto en la soluci´on de cada uno de estos problemas.

Figura 5.1: Clientes vs Veh´ıculos utilizados

CAP´ITULO 5. EXPERIMENTOS COMPUTACIONALES

47

En los problemas con las ventanas de atenci´on suaves, se puede apreciar un uso reducido de veh´ıculos, como consecuencia del poder llegar en cualquier momento al cliente, los veh´ıculos son asignados a poder realizar un viaje en cualquier momento.

5.3.

Problemas de Asignaci´ on de veh´ıculos con ventanas duras de tiempo

Adem´as de las pruebas realizadas con conjuntos de datos de ventanas de tiempo suaves se decidi´o crear algunos experimentos con ventanas, que no permitieran la violaci´on a estas. De nueva cuenta se hacen experimentos con un y varios tipos de veh´ıculos. Los resultados de estos experimentos se muestran a continuaci´on. Tambi´en se consideran los casos con diferentes tipos de veh´ıculos. Nombre del Problema Tiempo CPU Valor Objetivo vrp3050-3-7-1-h 21,603 Seg $432832 vrp3050-3-7-h 21,603 Seg $ 1525350 vrp4060-3-7-1-h 21,603 Seg $ 5013390 vrp4060-3-7-h 21,603 Seg $3426420 vrp5060-3-7-1-h - Seg vrp5060-3-7-h - Seg vrp6060-3-7-1-h - Seg vrp6060-3-7-h - Seg vrp6075-3-7-h 21,603Seg $ 9486240 vrp6080-3-7-h - Seg $ 9486240 Tabla 5.5: Resultados Ventanas Duras Como criterio de interrupci´on se sigue con las mismas 7 hrs CPU con las que se ejecutaron los problemas de ventanas suaves. En estos resultados es notable, la falta de una soluci´on entera para algunos problemas, esto debido a nuestros criterios de interrupci´on de la optimizaci´on con las que se

CAP´ITULO 5. EXPERIMENTOS COMPUTACIONALES

48

ejecuta cada uno de estos. En las tablas la celda con un gui´on significa que no se pudo obtener la soluci´on entera antes de interrupci´on. Nombre del Problema N Clientes V. Originales vrp3050-3-7-1-h 30 50 vrp3050-3-7-h 30 50 vrp4060-3-7-1-h 40 60 vrp4060-3-7-h 40 60 vrp5060-3-7-1-h 50 60 vrp5060-3-7-h 50 60 vrp6060-3-7-1-h 60 60 vrp6060-3-7-h 60 60 vrp6075-3-7-h 60 75 vrp6080-3-7-h 60 80

V. Soluci´on 50 40 46 39 67 72

Tabla 5.6: Resultados Veh´ıculos utilizados con Ventanas Duras En el caso de los problemas con ventanas dura, el problema es mas restringido y llegar a la soluci´on entera dentro del tiempo que se marco como l´ımite no es suficiente. Este mismo factor tambi´en incrementa el uso de veh´ıculos, hace sentido que a un menor tiempo en las ventanas de atenci´on de los clientes, se env´ıen veh´ıculos al mismo tiempo, pues por las distancias a recorrer no alcanzar´ıa a realizar dos viajes y cumplir con las ventanas.

Figura 5.2: Clientes vs Veh´ıculos utilizados

Cap´ıtulo 6 Conclusiones y Recomendaciones 6.1.

Conclusiones

La principal diferencia del modelo propuesto contra las formulaciones cl´asicas del problema de ruteo esta en la suposici´on de la capacidad de los veh´ıculos es significativamente menor que la demanda de los clientes. Esto es t´ıpico de los niveles mas altos de transportaci´on donde los productos necesitan ser entregados desde una planta de producci´on (dep´osito) a centros de distribuci´on generales (clientes) usando veh´ıculos relativamente peque˜ nos. Teniendo en cuenta esta suposici´on se considera a la red con una topolog´ıa tipo estrella, donde solo rutas directas entre el dep´osito y los clientes es permitida. Bajo este sistema un cliente puede ser visitado repetidas ocasiones por el mismo veh´ıculo y esta es otra diferencia de los modelos cl´asicos.

6.2.

Aportaciones

Se considera la principal aportaci´on de este trabajo la formulaci´on de un modelo matem´atico que nace de una problem´atica real. Hasta el momento no se conoce un

49

CAP´ITULO 6. CONCLUSIONES Y RECOMENDACIONES

50

modelo del tipo entero mixto lineal con las suposiciones establecidas, los resultados se consideran exitosos debido a su utilidad en una implementaci´on real. Los resultados del presente trabajo han sido publicados en: 1. Cano Robles Israel(2005) The fleet size and mix problem for vehicle routing in a star-case network. En Techiniques and Methodologies for Modelling and Simulation of Systems, Morelia, M´exico. Abril 2. Cano Robles Israel(2005) Modeling Vehicle Routing in a Star-Case Transportation Network. En Memoria del XIV Congreso Internacional de Computaci´on CIC 2005, D.F, M´exico. Septiembre Y presentados en 1. Cano Robles Israel (2004)Asignaci´on de recursos de transporte sujeto a nivel de servicio Ciclo de seminarios del PISIS, FIME, UANL, Mayo - Noviembre 2. Cano Robles Israel(2005) Asignaci´on de Recursos de transporte sujeto a nivel de servicio. ENOAN XV, Morelia, M´exico. Abril 3. Cano Robles Israel(2005) The fleet size and mix problem for vehicle routing in a star-case network. International Conference on Modelling and Simulation AMSE 2005, Morelia, M´exico. Abril 4. Cano Robles Israel(2005) Modeling Vehicle Routing in a Star-Case Transportation Network. En Memoria del XIV Congreso Internacional de Computaci´on CIC 2005, IPN, D.F, M´exico. Septiembre

6.3.

Recomendaciones

El estudio computacional indica que problemas de tama˜ no mediano pueden ser resueltos por software comercial en tiempo razonable. Sin embargo para problemas m´as

CAP´ITULO 6. CONCLUSIONES Y RECOMENDACIONES

51

grandes son necesarias t´ecnicas de soluci´on m´as r´apidas. Estas puede ser un ´area para la investigaci´on en el futuro. Adem´as se pueden agregar algunos cambios en la formulaci´on para considerar las siguientes situaciones: Considerar la existencia de mas de un dep´osito central Existencia de restricciones en la capacidad de recibo de veh´ıculos en el tiempo, en cada uno de los clientes. Es decir cuantos veh´ıculos por hora pueden ser recibidos. Posibilidad tener las ventanas de tiempo mul’tiples. Es decir tener para varios d´ıas diferentes horarios de recibo.

Bibliograf´ıa [1] A. Kolen, A. Rinnooy Kan, and H. Mercure. Vehicle routing with timw windows. Operations Research, 35(2):266-273, 1987. [2] B. Dimitris, Tsitsiklis, John N. Introduction to Linear Optimization, Athena Scientific,1997 [3] Council of Logistics Managment What’s It All About? Oak Brook, IL, 1993. [4] E. Baker. An exact algorithn for the time constrained traveling salesman problem. Operations Research, 31(5):938-945, 1983 [5] E. Baker and J. Schaffer. Solution improvement heuristics for the vehicle routing and scheduling problem with time window constraints. American Journal of Mathematical and Management Sciences, 6 (3,4):261-300,1988 [6] F. Robert, Software Survey: Linear Programming INFORMS OR/MS Today, 32(3),2005 [7] G.B. Dantzing and J.H. Ramser “The truck dispatching problem.”Management Science, 6:80, 1959. [8] Hall, H. Randolph, Handbook of Transportation Science, 2nd Edition, Kluwer Academic Publishers, 2003 [9] H. Psaraftis. A dynamic programming solution to the single vehicle many to many immediate request dial-a-ride problem. Transportation Science, 14(2):154,1980. 52

BIBLIOGRAF´IA

53

[10] J.Aranque, G. Kudwa, T. Morin, and J. Penky. A branch-and-cut algorithm for vehicle routing problems. Annals of Operations Research, 50: 35-59,1994 [11] J. Potvin and J. Rousseau. A parallel route building algorithm for the vehicle routing and scheduling problem with time windows. European Journal of Operational Research, 66: 331-340, 1991 [12] J. Desrosiers, M. Solomon and F. Soumis. Time constrained routing and scheduling. In M. Ball, T Magnati, C. Momma, G. Nemhauser, editors, Handbooks in Operations Research and Management Science:Networks. North-Holland, 1994. [13] J. Desrosiers, M. Sauve and F. Soumis. Langrangian relaxation methods for solving the minimum fleet size multiple traveling salesman problem with time windows. Management Science 34(8):1005-1022,1988. [14] J. Desrosiers, Y. Dumas, and F. Soumis. A dynamic programing solution of the large-scale single- vehicle dial-a-ride problem with time windows. American Journal of Mathematics and Management Sciences, 6(3&4):301-325,1986. [15] J. Potvin, T. Kervahut, B. Garcia, and J. Rousseau. The vehicle routing problem with time windows, Part I: Tabu search. INFORMS Journal on Computing, 8(2): 158-164,1996. [16] J. Potvin and S. Bengio. The vehicle routing problem with time windows, Part II: Genetic search. INFORMS Journal on Computing, 8(2):165-172,1996. [17] K. Nygard, P. Greenberg, W. Bolkan, and E. Swenson. Generalized assignment methods for the deadline vehicle routing problem. In B. Golden and A. Assad, editors, Vehicle Routing. Methods and Studies, p. 107-126 North Holland, Amsterdam, 1988.

BIBLIOGRAF´IA

54

[18] K. Hoffman and M. Padberg. Solving airlane crew scheduling problems by branchand-cut. Management Science, 39 (6) 657-683, 1993. [19] L. Bodin, B. Golden, A. Assad and M. Ball. Routing and scheduling of vehicles and crews the state of the art. Computers & Operations Research, 10:63-211, 1983 [20] L. Lilian, R. Michael , B. David, “A global view og industrial logistics”, European Journal of Operational Research, 129(1) 231-234. [21] Marshall L. Fisher,Kurt O J¨ornstern and Oli B. Madsen “Vehicle Routing with time windows two optimization algorithms”,Operations Research, 45(3): 488-492 [22] M. Solomon. Algorithms for the vehicle routing and scheduling problem with time window constraints. Operations Research 35(2):254-265,1987. [23] M. Solomon. On the worst-case performance of some heuristics for the vehicle routing and scheduling problem with time windows constraints. Networks, 16:161174,1986. [24] M. Solomon and J. Desrosiers. Time window constrained routing and scheduling problems. Transportation Science, 22 (1):1-13,1988. [25] M. Solomon, E. Baker And J. Schaffer. Vehicle routing and scheduling problems with time windows constraints: Efficient implementations of solution improvement procedures. In B. Golden and A. Assad, editors, Vehicle Routing: Methods and Studies, pages 85-105. North-Holland, Amsterdam,1988 [26] M. Desrochers, J. Lenstra, M. Savelsbergh, and F Soumis. Vehicle routing with time windows: Optimization and approximation. In B. Golden and A. Assad, editors, Vehicle Routing:Methods and Studies, p. 65-84. North Holland, Amsterdam, 1988.

BIBLIOGRAF´IA

55

[27] M. Desrochers, J. Desrosiers, and M. Solomon. A new optimization algorithm for the vehicle routing problem with time windows. Operations Research, 40(2) 342354, 1992. [28] M. Padberg and G. Rinaldi. A branch-and-cut algorithm for the resolution of large scale symmetric traveling salesman problems. SIAM Reviews 33(1):60-100,1991. [29] M. Savelsbergh. The vehicle routing problem with time windows: Minimizing route duration. ORSA Journal on Computing 4(2):146-154,1992 [30] N. Kohl. Exact Methods for Time Constrained Routing and Related Scheduling Problems. PhD thesis, Technical University of Denamark. Copenhagen, 1995. [31] N. Christofides, A. Mingozzi, and P. Toth. State-space relaxation for the computation of bounds to routing problems. Networks 11:145-164. 1981. [32] P. Toth, D. Vigo. The Vehicle Routing Problem. SIAM, 2001. [33] P. Augerat. Approache Poly´edrale du Probl`eme de Tourn´ees de V´ehicules. PhD thesis, Institut National Polytechnique de Greenoble, France,1995. [34] “Routing Software Prevents Scheduling Meltdown ”,Logistics Management 35, no 6 (june 1996) p 85. [35] S. Thangiah, K. Nygard, and P. Juell, Gideon: A genetic algorithm system for vehicle routing with time windows. In Proceedings of the 7th IEEE Conference on Artificial Intelligence Applications, p422-425, Miami 1991 [36] T. Sexton and L.Bodin. Optimizing single vehicle many-to-many operations with desired delivery times. Transportation Science, 19:378-435, 1985. [37] Y.Rochat and E. Taillard.Probabilistic diversification and intensification in local search for vehicle routing. Journal of Heuristics, 1:147-167,1995.

Ap´ endice A M´ etodo Ramificaci´ on y Cota A.1.

Ramificaci´ on-cotas (Branch and bound)

La t´ecnica de ramificaci´on-cotas usa un principio b´asico “divide y conquista ” para explorar el conjunto de soluciones enteras factibles, aunque en lugar de explorar todas y cada una de las soluciones factibles. La t´ecnica usa cotas en los costos ´optimos para explorar sobre algunas secciones del conjunto de soluciones factibles. Sea F el conjunto de soluciones factibles al problema

m´ın c0 x s.t x ∈F Podemos dividir al conjunto F en una colecci´on finita de subconjuntos F1 , ....Fk , y resolver por separado cada uno de estos problemas m´ın c0 x s.t x ∈ Fi, i = 1, ..., k. Despu´es comparamos las soluciones optimas de los subproblemas y escogemos la mejor de ellas. Cada subproblema puede ser casi tan dif´ıcil como el problema original 56

´ ´ ´ Y COTA APENDICE A. METODO RAMIFICACION

57

eso nos sugiere intentar resolver cada subproblema por medio del mismo m´etodo, esto es seguir dividiendo el problema en subproblemas, este procedimiento es la parte de ramificaci´on del m´etodo, creando asi un ´arbol de subproblemas A.1

´ Figura A.1: Arbol de subproblemas generado en ramificaci´on y cotas Se supone la existencia de un algoritmo eficiente en el que para cada Fi de inter´es, se calcula una cota inferior b (Fi ) del costo ´optimo de subproblema correspondiente esto es , b (Fi ) ≤ m´ın c0 x x∈Fi

La idea principal del m´etodo consiste en que mientras que el costo ´optimo del subproblema es dif´ıcil de calcular optimamente, una cota del mismo puede resultar mas f´acil de obtener. Un forma usual de obtener dicha cota es usando el costo ´optimo de la relajaci´on lineal del problema. Durante el transcurso del algoritmo ocasionalmente se resuelven problemas a optimalidad o simplemente se eval´ ua el costo de ciertas soluciones factibles, esto nos permite mantener una cota superior U en el costo ´optimo, la cual puede ser el costo de la mejor soluci´on encontrada hasta el momento. La esencia del m´etodo cae en la siguiente observaci´on. Si la cota inferior b (Fi ) correspondiente a un subproblema en particular satisface b (Fi ) ≥ U , entonces este

´ ´ ´ Y COTA APENDICE A. METODO RAMIFICACION

58

problema no debe ser considerado en el las siguientes iteraciones dado que la soluci´on del subproblema no supera la mejor soluci´on factible encontrada hasta ese momento. En resumen el algoritmo a nivel general se describe a continuaci´on. En cualquier punto el algoritmo guarda en memoria un conjunto de los subproblemas activos y el costo U de la mejor la mejor soluci´on factible encontrada hasta ese momento. Inicialmente U toma el valor de ∞ o el costo de alguna soluci´on factible si est´a se encuentra disponible, as´ı la iteraci´on t´ıpica del algoritmo es de la siguiente forma 1.Seleccionar un subproblema Fi 2.Si el subproblema es infactible, se elimina, de otra forma se calcula la cota b (Fi ) para el subproblema correspondiente. 3.Si b (Fi ) ≥ U se elimina el subproblema 4.Si b (Fi ) < U se puede obtener una soluci´on ´optima al subproblema o quebrar este en sus correspondientes subproblemas estos se agregan a la lista de subproblemas activos. En este algoritmo existen algunos par´ametros libres en la mayor´ıa de los casos las mejores opciones son dictadas por la experiencia y el tipo del problema que se trata de resolver. Ejemplos de estos par´ametros son: (a) Existen diferentes maneras de seleccionar un subproblema de activo, dos de las mas usadas son “breath first search ”y b´ usqueda del primero m´as profundo. (b) Hay varias formas de determinar la cota inferior b (Fi ) del costo optimo del los subproblemas, la mas com´ un es considerar la relajaci´on lineal del subproblema. (c) Existen muchas formas de quebrar el problema en subproblemas. Como ilustraci´on, suponemos que usamos como cota inferior b(Fi ) el costo optimo del al relajaci´on lineal donde las restricciones de integralidad son ignoradas. Si se obtiene una soluci´on ´optima entera del problema relajado esta autom´aticamente es una

´ ´ ´ Y COTA APENDICE A. METODO RAMIFICACION

59

soluci´on ´optima para el correspondiente problema entero, eso evita la expansi´on en los subproblemas. El siguiente paso es actualizar U (si la soluci´on obtenida es mejor que el valor previo de U ) y as´ı podemos eliminar el actual subproblema, si la soluci´on x∗ al problema lineal relajado no es entera , entonces se escoge un componente xi para el que x∗i no es entero y se crean dos subproblemas agregando las siguientes restricciones xi ≤ bx∗i c,

or

xi ≥ dx∗i e

Ap´ endice B AMPL B.1.

Lenguaje AMPL

AMPL es un lenguaje de modelado algebraico para programaci´on matem´atica: un lenguaje capaz de expresar en notaci´on algebraica problemas de optimizaci´on tales como los problemas de programaci´on lineal. Veamos un peque˜ no ejemplo. Ejemplo 1.1. Una compa˜ n´ıa fabrica tres productos, P1 , P2 y P3 , que precisan para su elaboraci´on dos materias primas, M1 y M2 . Las disponibilidades semanales de estas materias son 25 y 30 unidades, respectivamente. El beneficio neto que proporciona cada unidad de producto, as´ı como las unidades de materia prima que necesita para su elaboraci´on, vienen dados en la siguiente tabla: P1

P2

P3

M1

1

2

2

M2

2

1

3

Beneficio (u.m.) 2

6

3

Planificar la producci´on semanal de forma que se maximice el beneficio. Soluci´on:

60

´ APENDICE B. AMPL

61

Sean x1 , x2 , x3 (xi ) la cantidad producida de P1 , P2 y P3 respectivamente (Pi , i = 1, 2, 3). El problema a resolver ser´ıa el siguiente: m´ax z = 2x1 + 6x2 + 3x3 s.a.

x1 + 2x2 + 2x3

≤ 25

2x1 + x2 + 3x3

≤ 30

x 1 , x2 , x3

≥0

El modelo (modelo+datos) escrito en AMPL del ejemplo 1.1 es el siguiente: # FABRICACION DE 3 PRODUCTOS CON 2 MATERIAS PRIMAS # VARIABLES DE DECISION Y RESTRICCIONES DE NO NEGATIVIDAD var x1 >= 0; var x2 >= 0; var x3 >= 0; # FUNCION OBJETIVO DEL MODELO maximize z : 2*x1 + 6*x2 + 3*x3; # RESTRICCIONES DEL MODELO subject to restriccion1 : x1 + 2*x2 + 2*x3 =0, integer; # CONJUNTOS DE INDICES set PRODUCTOS := 1..n; set MPRIMAS := 1..m; # VARIABLES DE DECISION Y RESTRICCIONES NO NEGATIVIDAD var x {j in PRODUCTOS} >= 0; # MAS PARAMETROS DEL MODELO param c {i in PRODUCTOS}; param b {j in MPRIMAS}; param a {(i,j) in {MPRIMAS,PRODUCTOS}}; # FUNCION OBJETIVO DEL MODELO maximize z : sum {j in PRODUCTOS} c[j]*x[j]; # RESTRICCIONES DEL MODELO subject to restriccion {i in MPRIMAS} : sum {j in PRODUCTOS} a[i,j]*x[j] 0; Cada elemento de la lista de datos consta de un miembro del conjunto y de un valor; set PROD:= plato cuchillo tenedor ;

´ APENDICE B. AMPL

85

param valor := plato 200 cuchillo 140 tenedor 160 ; equivalentemente: param valor := plato 200, cuchillo 140, tenedor 160 ; A menudo necesitamos datos para varios par´ametros que est´an indexados sobre el mismo conjunto, en esta situaci´on puede escribirse: param valor := plato 200 cuchillo 140 tenedor 160 ; param benefi := plato 25 cuchillo 30 tenedor 29 ; param market := plato 6000 cuchillo 4000 tenedor 3500 ; o param:

valor

benefi market :=

plato

200

25

6000

cuchillo

140

30

4000

tenedor 160 29 3500 ; Los dos puntos despu´es de la palabra clave param es obligatoria; indica que damos valores para varios par´ametros. Si se sigue con el nombre del conjunto PROD y otros dos puntos: param:

PROD:

valor benefi

market :=

plato

200

25

6000

cuchillo

140

30

4000

tenedor 160 29 3500 ; entonces los elementos del conjunto PROD son definidos tambi´en con este comando, evitando as´ı la definici´on con el comando set PROD; el efecto es combinar las especificaciones del conjunto y los tres par´ametros indexados sobre ´el. Par´ametros bidimensionales

´ APENDICE B. AMPL

86

Los valores de un par´ametro indexado sobre dos conjuntos, son generalmente introducidos como: set ORIG; set DEST; param costo {ORIG,DEST} >= 0; data param costo: CA CO

HU

AL

JA MA GR :=

SE

39 14

11

14

16

82 8

MD

27 9

12

9

26

95 17

BA 24 14 17 13 28 99 20 ; Las etiquetas en las filas dan el primer ´ındice y las etiquetas de las columnas dan el segundo ´ındice, as´ı por ejemplo, costo[“SE”,“CA”] se ha definido a 39. Podemos usar la notaci´on (tr): param costo ( tr ): SE MD BA CA

39 27 24

CO

14 9

14

... ; Cuando las tablas son grandes pueden utilizarse caracteres de nueva l´ınea en cualquier lugar, o tambi´en emplear el siguiente formato:

´ APENDICE B. AMPL

param costo :

87

CA

CO HU

AL :=

SE

39

14

11

14

MD

27

9

12

9

BA

24

14

17

13

:

JA MA

GR :=

SE

16

82

8

MD

26

95

17

BA

28

99

20

Los dos puntos indica el comienzo de cada nueva subtabla; cada una tiene las misma etiquetas de filas, pero diferentes etiquetas de columna. El par´ametro no tiene porque estar indexado sobre todas las combinaciones de miembros de ORIG y DEST, sino tan s´olo de un subconjunto de esos pares: set LINKS within { ORIG , DEST }; param costo { LINKS } >= 0; Como se vio en la secci´on anterior, el conjunto LINKS puede definirse como: param costo: CA CO SE .

14

MD 27 9

HU

AL

JA MA GR

11

.

16 .

8

12

9

26 .

17

BA 24 . . 13 28 99 . ; Donde un “+” indica un miembro del conjunto, la tabla para costo da un valor. Donde un “-” indica que no pertenece, la tabla contiene un punto “.”. El punto puede aparecer en cualquier tabla AMPL para indicar “valor no especificado aqu´ı”. Es posible definir un s´ımbolo diferente, por ejemplo –, al incluir el siguiente comando en data: defaultsym \--";

´ APENDICE B. AMPL

88

el cual puede ser desactivado al introducir el comando: nodefaultsym ; Tambi´en es posible introducir los datos del siguiente modo: param costo := SE CO 14 SE HU 11 SE JA 16 SE GR 8 MD CA 27 ... ; Cuando un par´ametro est´a indexado sobre un subconjunto poco denso de pares, una lista puede ser m´as compacta y legible que la representaci´on tabular, la cual estar´ıa formada mayoritariamente por puntos. Otra ventaja del formato lista es que, como en el caso unidimensional, los datos para varias componentes pueden darse juntos: param:

LINKS: costo limit := SE CO

14

1000

SE HU

11

800

SE JA

16

1200

SE GR

8

1100

MD CA

27

1200

MD CO

9

600

MD HU

12

900

MD AL

9

950

MD JA

26

1000

MD GR

17

800

BA CA

24

1500

BA AL

13

1400

BA JA

28

1500

BA MA

99

1200 ;

´ APENDICE B. AMPL

89

Esta tabla da simult´aneamente los miembros de LINKS y los valores para costo, y tambi´en los valores para otros par´ametros, limit, que est´a tambi´en indexado sobre LINKS. Finalmente, la lista de datos para costo puede escribirse m´as concisamente al organizarla en trozos, como se mencion´o para los miembros del conjunto LINKS en la secci´on previa. set LINKS := (SE ,*) CO HU JA GR ... ;

param costo := [SE ,*] CO 14 HU 11 JA 16 GR 8 [MD ,*] CA 27 CO 9 HU 12 AL 9 JA 26 GR 17 [BA ,*] CA 24 AL 13 JA 28 MA 99 ; Par´ametros multidimensionales. Podr´ıamos introducirlos de las siguientes formas: set ORIG ; set DEST ; set PROD ; set RUTAS within { ORIG,DEST,PROD }; param costo { RUTAS } >= 0; lista simple param costo := MD CO plato 9 MD CO cuchillo 8 MD CA plato 27 MD CA cuchillo 23 MD GR plato 17 ... ; uso de trozos

´ APENDICE B. AMPL

90

param costo := [MD, *, plato ] CA 27 CO 9 HU 12 JA 26 GR 17 [BA, *, plato ] CA 24 AL 13 JA 28 MA 99 ... ; uso de trozos param costo := [*, CA, *] MD plato 27 MD cuchillo 23 BA plato 24 [*, CO, *] MD plato 9 MD cuchillo 8 ... ; uso de trozos 2 dimensiones y tablas param costo := [*,*, plato ]:

CA CO HU

JA

MA GR :=

MD 27 9

12

.

26 .

BA 24 .

.

13

28 99 .

AL

JA

[*,*, cuchillo ]:

CA CO HU

SE .

17

MA GR

.

11

.

16 .

8

MD 23 8

10

9

21 .

.

.

.

.

BA . . Se puede emplear la notaci´on (tr). Otro ejemplo:

AL

81 . ;

´ APENDICE B. AMPL

91

set PROD ; set AREA { PROD }; param T > 0; param renta {p in PROD , AREA [p ], 1 ..T } >= 0; data param T := 4; set PROD := plato cuchillo ; set AREA [ plato ] := este norte ; set AREA [ cuchillo ] := este oeste export ;

param renta := [ plato, *,*]:

1

2

3

4 :=

este

25.0 26.0

27.0 27.0

norte

26.5 27.5

28.0 28.5

[ cuchillo, *,*]:

1

2

3

4 :=

este

30

35

37

39

oeste

29

32

33

35

export

25

25

25

28 ;

Valores por defecto. AMPL comprueba que los comandos de datos asignan valores para exactamente todos los par´ametros en el modelo. AMPL dar´a un mensaje de error si damos un valor para un par´ametro inexistente, o nos olvidamos de dar un valor a un par´ametro que existe. Si el mismo valor apareciera muchas veces en un comando de datos, podemos especificar la frase default. Por ejemplo,

´ APENDICE B. AMPL

92

set ORIG ; set DEST ; set PROD ; param costo { ORIG,DEST,PROD } >= 0; data param costo defaul t 9999 := [*,*, plato ]:

CA CO HU

AL

JA

MA GR :=

MD 27 9

12

.

26 .

BA 24 .

.

13

28 99 .

AL

JA

[*,*, cuchillo ]:

CA CO HU

SE .

17

MA GR :=

.

11

.

16 .

8

MD 23 8

10

9

21 .

.

BA . . . . . 81 . ; Tanto a los par´ametros missing (como costo[“SE”,“CA”,“plato”]), como a los marcados como omitidos con el uso de un punto (como costo[“SE”,“CA”,“cuchillo”]), se les asignar´a el valor 9999. En total, hay 24 con valor 9999. La caracter´ıstica default es especialmente u ´til cuando queremos que todos los par´ametros de una colecci´on indexada tengan el mismo valor. Por ejemplo: param oferta { ORIG } >= 0; param demanda { DEST } >= 0; data param oferta default 1 ; param demanda default 1 ; Tambi´en, como se explic´o en secciones anteriores, una declaraci´on de par´ametro puede incluir una expresi´on default. Por ejemplo: param costo { ORIG,DEST,PROD } >= 0, default 9999;

´ APENDICE B. AMPL

93

Sin embargo, es mejor poner la frase default en los comandos de datos. La frase default deber´ıa ir en el modelo cuando queremos que el valor por defecto dependa de alguna forma de otros datos. Por ejemplo, un costo arbitrariamente grande podr´ıa darse para cada producto al especificar: param gran costo { PROD } > 0; param costo { ORIG,DEST,p in PROD } >= 0, default gran costo [p]; Datos para variables y restricciones. Opcionalmente podemos asignar valores iniciales a las variables o restricciones del modelo, usando cualquiera de las opciones para asignar valores a par´ametros. El nombre de la variable almacena su valor, y el nombre de la restricci´on el valor de la variable dual asociada. var Tans:

CA

CO

HU

SE

100

100

MD

900

100

AL

JA

MA

GR :=

800 100 100

500

200

100 500 500

200

200

BA 100 900 100 500 100 900 200 Tambi´en con una tabla simple podemos dar valores a par´ametros (valor, benefi, market) y variables (Make): param:

valor

benefi market

Make :=

plato

200

25

6000

3000

cuchillo

140

30

4000

2500

tenedor 160 29 3500 1500 ; Los valores iniciales de las variables (o expresiones que envuelven esos valores iniciales) pueden verse antes de escribir solve, usando los comandos display, print o printf. El uso m´as com´ un de asignar valores iniciales a variables o restricciones es dar un punto de arranque para resolver un problema de optimizaci´on no lineal.

´ APENDICE B. AMPL

B.1.7.

94

Comandos del lenguaje.

La llamada a AMPL normalmente causa la entrada en un entorno de comandos, donde los comandos pueden ser introducidos interactivamente. Las declaraciones del modelo y las instrucciones de introducci´on de datos son tambi´en aceptadas como comandos. El entorno de comandos de AMPL reconoce dos modos. En modo modelo, reconoce las declaraciones del modelo y todos los comandos que se describir´an a continuaci´on. El otro modo es el modo datos, en el cual s´olo se reconocen instrucciones referentes a la introducci´on de datos. El entorno siempre vuelve al modo modelo al encontrar una palabra clave que no comience con la palabra data. Una frase de la forma: include fichero ; trae el contenido del fichero al entorno de comandos de AMPL. Los comandos include pueden estar anidados, ellos son reconocidos en modo modelo y en modo datos. Las secuencias: model; include fichero ; data; include fichero ; pueden abreviarse como: model fichero ; data fichero ; Los comandos no son parte de un modelo, pero producen que AMPL act´ ue como se describe en la tabla 7. Los comandos distintos a data, end, include, quit y shell producen que AMPL entre en modo modelo. Desde la l´ınea de comandos de AMPL podemos escribir, por ejemplo: ampl: include ejemplo1.run ; siendo el fichero ejemplo1.run (tabla 8), un fichero por lotes que almacena la secuen-

´ APENDICE B. AMPL

95 # EJEMPLO1.RUN option solver cplex; model ejemplo1.mod ; data ejemplo1.dat ; solve ; display z; display x; display restriccion.slack ;

Tabla B.7: Fichero de lotes para el modelo del ejemplo 1.1 cia de comandos necesarios para resolver el ejemplo 1.1.

Los comandos display, print y printf imprimen expresiones arbitrarias. Tienen el siguiente formato: display [conjunto: ] lista–argumentos [redireccion]; print [conjunto: ] lista–argumentos [redireccion]; printf [conjunto: ] fmt, lista–argumentos [redireccion];

´ APENDICE B. AMPL

96

Comandos

Significado

break

termina un bucle for o while

close

cierra un fichero

continue

salta al final del cuerpo del bucle

data

cambia a modo datos; opcionalmente incluye un fichero

display

imprime elementos del modelo y expresiones

delete

elimina un componente previamente declarado

drop

elimina una restricci´on u objetivo

end

finaliza la entrada del fichero de entrada actual

expand

muestra expl´ıcitamente el modelo

fix

fija una variable a su valor actual

for { indx }{ cp }

bucle for

if lexpr then {}

comprueba una condici´on

include

incluye ficheros

let

cambia los valores de los datos (:=)

match(cad,mod)

posici´on de mod en cad

model

cambia al modo modelo; opcionalmente incluye un fichero

objective

selecciona un objetivo a optimizar

option

define o muestra valores opcionales

print

imprime elementos del modelo sin formatear

printf

imprime elementos del modelo formateados (\n, %7.1f)

problem nb: def.

define un problema

purge

elimina un componente y los dependientes de ´el

quit

termina AMPL

read

lee datos de un fichero o de la consola (¡-)

redeclare

redefine un componente ya definido

´ APENDICE B. AMPL

97

Comandos

Significado

repeat while lexpr { cp }

repite un bloque de comandos mientras V.

repeat until lexpr { cp }

repite un bloque de comandos hasta F.

repeat { cp } while lexpr repite un bloque de comandos mientras V. repeat { cp } until lexpr

repite un bloque de comandos hasta F.

reset

reinicia elementos espec´ıficos a su estado inicial

restore

deshace un comando drop

shell

temporalmente sale al sistema operativo

show

muestra componentes del modelo

solution

importa valores de variables de un solver

solve

env´ıa elementos actuales a un solver y devuelve la soluci´on

step

n avanza n pasos en la ejecuci´on de ficheros por lotes

update

permite actualizar datos

unfix

deshace un comando fix

write

escribe en un fichero partes de un problema

xref

muestra dependencias del modelo

Si el conjunto est´a presente, su campo de acci´on se extiende hasta el final del comando, y causa una ejecuci´on del comando para cada miembro del conjunto. La lista-argumentos es una lista de expresiones separadas por comas. El opcional redireccin tiene una de las dos formas siguientes: > fichero >> fichero La primera abre por primera vez un fichero para escribir, y la segunda a˜nade al fichero ya creado, aunque > act´ ua igual que >>, si el fichero est´a ya abierto. Con el comando option se puede conseguir que la salida que se ha solicitado tenga un formato

´ APENDICE B. AMPL

98

espec´ıfico. Por ejemplo: option display precision 3; option omit zero rows 1; La primera especifica la precisi´on de salida (0 equivale a ninguna) y la segunda omite las salidas con valor cero (por defecto es 0, es decir no omite los valores cero). Otras opciones son: option solver msg 0; option relax integrality 1; option presolve 0; option show stats 1; option times 1; option gentimes 1; option log file ’hola.tmp ’; option solution round 6; option single step 1;

Ap´ endice C Modelo en AMPL

Declaracion de Conjuntos Set Vehiculos; # Declaracion del Conjunto de los Vehiculos Set Clientes; # Declaracion del Conjunto de los Clientes incluye al dep´ osito (Cliente =0) Set Viajes ordered; # Declaracion del Conjunto de los Viajes Set Cliente; # Declaracion del Conjunto de los Clientes (Solo los CD) param LlegadaE Clientes >=0; param LlegadaL Clientes >=0; param LlegadaL Clientes >=0; param Costo Clientes,Vehiculos >=0; param Fijo Vehiculos >=0; param CostoE Clientes >=0; param CostoD Clientes >=0; param Demanda Clientes >=0; param Tiempo Clientes >=0; param Capacidad Vehiculos >=0;

99

´ APENDICE C. MODELO EN AMPL

100

# Declaracion de Varibles var Camionrecorrido Clientes,Viajes,Vehiculos binary; #Declaracion de la variable Xijk, como binarias var Uso Vehiculos binary; # Declaracion de la variable Yk como binaria var SalidaV Viajes,Vehiculos >=0; # Declaracion de la variable Sijk como continua var Espera Clientes,Viajes,Vehiculos >=0; #Declaracion de la variable Wijk(+) como continua var Retraso Clientes,Viajes,Vehiculos >=0; # Declaracion de la variable Wijk(-) como continua Funcion Objetivo minimize costo total: sum i in Clientes,j in Viajes,k in Vehiculos Costo[i,k]*Camionrecorrido[i,j,k] + sum k in Vehiculos Fijo[k]*Uso[k] + sum i in Clientes,j in Viajes,k in Vehiculos CostoE[i]*Espera[i,j,k] + sum i in Clientes,j in Viajes,k in Vehiculos CostoD[i]*Retraso[i,j,k]; # Restriccion (2) subject to visita j in Viajes, k in Vehiculos : Camionrecorrido[0,j,k]+sumh in Cliente Camionrecorrido[h,j,k]=1; # Restriccion (3) subject to Demandav h in Cliente: sum j in Viajes,k in Vehiculos Camionrecorrido[h,j,k]*Capacidad[k]>=Demanda[h]; # Restriccion (4) subject to cuatro k in Vehiculos: 7 - sum j in ViajesCamionrecorrido[0,j,k]=SalidaV[j,k]+(Camionrecorrido[i,j,k]*Tiempo[i] -LlegadaL[i]-2000*(1-Camionrecorrido[i,j,k])

Ap´ endice D Carta Referencia Sintec

101