1

UNIVERSIDAD DE CHILE FACULTAD DE CIENCIAS FISICAS Y MATEMATICAS

DEPARTAMENTO DE INGENIERIA INDUSTRIAL

HEURISTICA PARA LA ASIGNACIÓN Y DESPACHO DE UNA EMPRESA ELABORADORA Y DISTRIBUIDORA DE

CERVEZAS

TESIS PARA OPTAR AL GRADO DE MAGíSTER EN GESTIÓN DE OPERACIONES

RICARDO ANTONIO SAN MARTÍN ZURITA

SANTIAGO DE CHILE

Agosto, 2011

UNIVERSIDAD DE CHILE FACULTAD DE CIENCIAS FISICAS Y MATEMATICAS

DEPARTAMENTO DE INGENIERIA INDUSTRIAL

HEURISTICA PARA LA ASIGNACIÓN Y DESPACHO DE UNA EMPRESA ELABORADORA Y DISTRIBUIDORA DE

CERVEZAS

TESIS PARA OPTAR AL GRADO DE MAGíSTER EN GESTIÓN DE OPERACIONES

RICARDO ANTONIO SAN MARTÍN ZURITA

PROFESOR GUIA

Pablo Andrés Rey

MIEMBROS DE LA COMISIÓN EVALUADORA Enrique Jofré Rojas

Rafael Epstein Numhauser Francisco Tubino Córtes

SANTIAGO DE CHILE

Agosto, 2011

3

1 Introducción .......................................................................................... 5

2 Descripción de la Empresa .................................................................... 9

3 Descripción y Planteamiento del problema ........................................ 11

4 Alcances del trabajo ............................................................................ 13

5 Objetivo de la Tesis ............................................................................. 14

5.1 Objetivos específicos ...................................................................... 14

6 Marco Teórico ..................................................................................... 15

7 Metodología utilizada .......................................................................... 21

7.1 Heurística Utilizada ........................................................................ 22

7.1.1 Descripción Método Obtención Solución Inicial Factible .... 22

7.1.2 Descripción Método Obtención de Mejora de Solución ....... 23

7.2 Programación de Operaciones actual ............................................. 25

7.2.1 Calibración de la Metodología ............................................. 28

7.3 Descripción Programa Computacional ........................................... 33

8 Resultados ........................................................................................... 36

8.1 Cálculo de nuevas rutas mejoradas ................................................. 36

8.2 Diferencias en distancias recorridas ............................................... 40

8.3 Diferencias en tiempos empleados ................................................. 41

8.4 Valorización de Beneficios y Ahorros para la Empresa con los nuevos resultados de distancia y tiempos empleados ............................. 42

8.5 Cálculo de tiempos de Procesamiento ............................................ 43

8.6 Propuesta de Sistema de Trabajo para Implementación de nueva herramienta de Programación ................................................................. 45

9 Conclusiones y Comentarios ............................................................... 46

10 Bibliografía .......................................................................................... 48

HEURISTICA PARA LA ASIGNACIÓN Y DESPACHO DE UNA EMPRESA ELABORADORA Y DISTRIBUIDORA DE CERVEZAS

Este trabajo de Tesis tiene como objetivo rediseñar e implementar una metodología que permita apoyar las decisiones de asignación y despacho de cajas de cerveza para una empresa de elaboración y distribución en Santiago de Chile. Las actuales condiciones de baja utilización de la flota de camiones de despacho, extenuantes jornadas de trabajo, altos costos de transporte producto de planes de mantención por fallas en lugar de preventivas y bajos índices de niveles de servicio (bajo el 90%) son las razones que explican el desarrollo de esta tesis. La metodología empleada corresponde al rediseño e implementación computacional de una heurística que permita mejorar los índices actuales de utilización de camiones, mejorar los niveles de servicio a clientes y bajar las jornadas de trabajo. Esta heurística que se implementará corresponde a un trabajo realizado por los investigadores Sam Thangiah (USA) y Tong Sun (USA) de Computer Science Department Slippery Rock University, Jean-Yves Potvin (Canada) de Center for Research on Transportation Univesité de Montréal, el cual ha sido adaptado a la problemática de asignación y ruteo en el despacho de los pedidos de Santiago de Chile. La heurística en términos simples permite asignar los pedidos de clientes (cajas de cervezas) a cada camión con un orden establecido de despacho que permite cumplir los horarios de atención de los clientes y minimiza los costos de transporte a través de 2 etapas: primero la obtención de una “buena” solución inicial factible y en segundo lugar un procedimiento de mejora de la solución. Los resultados obtenidos para este problema particular conducen a ahorros económicos directos e indirectos. En cuanto a los ahorros directos, estos contemplan ahorros de menores distancias recorridas por los camiones por la utilización de esta herramienta de alrededor de 50 km/dia-camion y ahorros indirectos por concepto de mayores ventas por mayores despachos del orden de 10 a 13% más cajas de cerveza despachadas por día-camion. Ambos beneficios consolidados para toda la flota y para un período de un mes, entregan un beneficio o Ahorro de MM$16, que corresponde a un 1% de la venta mensual. Los resultados anteriores muestran las indudables ventajas de utilizar este tipo de herramientas sencillas de implementar y con un alto valor económico (respecto de la inversión requerida y el costo de implementación), sobretodo tomando en cuenta el alto nivel de competitividad que existe en este tipo de industrias.

5

1 Introducción Los inicios en la elaboración de cervezas en el mundo, se estima que fue hace unos 30 mil años. La mitad del siglo XIX marcó el inicio de la industria cervecera en Chile, de la mano de 2 pioneros: Joaquín Plagemann, que en 1850 abre en Valparaíso la primera fábrica en el país, y el inmigrante alemán Carlos Andwandter, que comienza un año más tarde esta tradición en Valdivia. Desde ese entonces, la cerveza ha logrado posicionarse en Chile como la bebida alcohólica de mayor consumo per cápita, seguida del vino, el pisco y el ron. Pese a ello, la industria he estado viviendo un estancamiento y que parte del consumo se ha ido hacia otras bebidas alcohólicas, como vino y pisco, junto con el hecho de que han cambiado las ocasiones de consumo y son cada vez menos las personas que beben cerveza en sus hogares. Durante los '90, el consumo de cerveza experimentó un crecimiento anual explosivo, casi duplicando su demanda de 15,7 litros per cápita en los años '70 a 26,1 litros en 1998. En el año 2009 se consumieron aproximadamente 37 litros por persona, que es bajo en comparación con otros países, como Argentina, Brasil, ó Alemania. Pero algo distinto está pasando en el segmento premium. Pese al bajo crecimiento visto en la industria, este espacio ha demostrado un comportamiento particularmente positivo. Los líderes en el mercado chileno1 Compañía Cervecerías Unidas (CCU) tiene un 82% de participación de mercado en el rubro cervezas, donde el producto que lidera el mercado es Cristal con 60% de las ventas. En el caso de las premium, esta compañía también mantiene su primera posición, con Heineken a la cabeza (35%). Las cervezas que se consumen en Chile, 9,6% corresponde a bebidas premium o finas, mientras que 1% son importadas. Acá destacan las marcas Corona, Grölsch e Imperial, comercializadas por Distribuidora Errázuriz; en tanto Cervecerías Chile trae Quilmes y Paceña. Además, Embotelladora Hochschild y Warsteiner comercializarán las cervezas Warsteiner, Isenbeck y Diosa, que serán importadas de Argentina, aunque las dos últimas estarán dirigidas a un segmento más masivo. En tanto, las internacionalmente conocidas Heineken y Paulaner son elaboradas por CCU bajo licencia, en cambio Budweiser es importada desde Argentina por esta misma empresa, la que además cuenta con las marcas nacionales Royal, Austral (Punta Arenas) y Kunstmann (Valdivia). En estas dos últimas, la compañía del grupo Luksic posee 50% de la propiedad. En CCU, el 8% de la producción corresponde a cerveza premium. Con las seis marcas se abarca el 90% del mercado, el 10% restante está bastante atomizado, principalmente por cervezas importadas. ______________________________________________________________________

(1) Diario Estrategia (21/01/2010)

Se entiende por Premium todas aquellas que no son de consumo masivo, que apuntan más bien a un nicho específico dentro del mercado. En ese sentido, todas las importadas entran dentro de esa categoría, aunque en su país de origen no lo sean. Demanda Pese a que el consumo per cápita en Chile está por los 37 litros, hay hábitos que hacen pensar que este va a seguir creciendo. En el caso de las cervezas finas, esto es particularmente especial, ya que para 2010 se esperaba que el segmento premium creciera a tasas de 14%. En ese sentido, Chile es lo más parecido a un país desarrollado dentro de Sudamérica. En el 2009, la producción anual del país alcanzó a los 5,5 millones hectolitros, de los cuales unos 550 mil hectolitros corresponden a Premium. Por tratarse de un producto refrescante, las personas prefieren beber cerveza en los meses de más calor, además de existir mayores oportunidades de consumo incentivados por las vacaciones, de esto se deducea el hecho que la cerveza presenta una demanda estacional. En el caso de las cervezas premium, estas tienen mayor acogida en el segmento socioeconómico ABC1, además de estar presentes en pub’s, restaurantes, hoteles y centros de recreación. Junto con esto, se pueden encontrar en tiendas especializadas, supermercados y botillerías, aunque en menor medida en estas últimas.

7

La Industria de la Cerveza en Chile La principal característica del mercado de la cerveza en Chile es que es una sola empresa, Compañía Cerveceras Unidas (CCU) controla casi 85% de las ventas de la bebida con sus marcas Cristal, escudo, Heineken y Budweiser, entre otras, dominando así la facturación de la industria, que alcanzó los US$330 millones. No obstante esta situación al parecer irá cambiando con el tiempo, ya que un actor menor, pero no menos relevante, Cervecerías Chile, que en el país opera con Becker, Báltica y Paceña, luego de varios años intentando aumentar su participación, finalmente dio con el palo al gato y con el ingreso de cerveza Brahma a su lista, en poco menos de tres meses ha ido sistemáticamente haciéndose espacio y quitándole consumidores a Cristal, la marca más fuerte de la CCU. La entrada de la nueva marca se esperaba en el país hace más de tres años, pero lo concentrado del mercado le impedía ingresar con tranquilidad, no obstante su arribo dejo en claro que aún existe espacio para nuevos actores. El mercado es tremendamente dinámico producto de la competencia generada como consecuencia del ingreso de algunas marcas, y del incremento en la actividad comunicacional y promocional, tanto al cliente como al consumidor. Durante mucho tiempo CCH jugó un rol relativamente pasivo, lo que estableció determinados estándares de desempeño y competitividad, pero esto ha cambiado y ha tomado una posición más agresiva y basta sólo con ver la fuerte campaña publicitaria que han desarrollado alrededor de su nuevo producto. Si bien no hay cifras oficiales que demuestren cuánto ha sido el impacto de Brahma en el mercado cervecero, se presume que ha permitido a Cervecerías Chile ganar alrededor de 3 o 4 puntos porcentuales. En la última década, la industria ha crecido a un ritmo mensual de entre 10% y 12%, en parte gracias al ingreso del nuevo actor y también por el alza en el precio de los vinos, y la competitividad y ese diferencial generó un volcamiento de la demanda por la cerveza, lo que incluso ha permitido subir los precios. Tal ha sido el impacto que, en términos de volumen, se prevé un crecimiento para CCH por sobre un 50%, desde los 380.000 hectolitros que vendieron el año pasado. No obstante, aún hay mucho que hacer en términos de crecimiento y de consumo per cápita en el país, es por esto que Cervecería Chile ya está trabajando algunas importantes inversiones con relación a su capacidad de producción. Consumo Si bien la entrada de Brahma generó una competencia más fuerte, lo que se tradujo en mayores y mejores beneficios para los consumidores, aún Chile está muy lejos de ser un país bebedor de cerveza. La industria ha logrado posicionarse y ha alcanzado segmentos antes desconocidos, como las mujeres, que ahora representan más del 40% de las ventas. En esta dirección es que la CCU realiza constantes esfuerzos para aumentar la venta de la bebida y por lo mismo ha implementado el Plan ACC (Aumento de Consumo de

Cerveza), que entre otras cosas, desarrolla nuevos productos, empaques, y genera nuevos canales de distribución. El objetivo principal de esta estrategia es aumentar las ocasiones de consumo y atraer nuevos clientes. Por esto es que se le ha dado cierto énfasis al segmento premium, que en términos proporcionales ha duplicado su crecimiento en los últimos 10 años, pasando de 4% a 8%. Las marcas dominantes en este sector son Heineken, que concentra alrededor de 35%, luego Corona con 26%, Royal cercano a 18%, y más abajo están Austral, Budweiser, Kuntsmann, Paulaner y Paceña. Además está la alemana Isenbeck, que actualmente comercializa su marca La Diosa a cargo de Bebidas Tomy, de la distribuidora propiedad de Hernán Hoschild, que está evaluando aumentar su presencia en el país una vez que logre consolidar su consumo. Es así como las cervezas importadas han ganado terreno para todos los paladares, y en los próximos años se prometen sorpresas por parte de Cervecerías Chile, ya que el holding que controla a la compañía, InBev, maneja dentro de sus marcas a la belga Stella Artois y a la alemana Beck's, que si bien es posible encontrarlas en el mercado chileno su distribución es extremadamente reducida. Dentro del rango premium e importadas, pero con un mercado mucho menor, de alrededor de 900 cajas mensuales, están las cervezas belgas que ingresa a Chile desde hace 10 años Thierry Swysen: Saint Paul, Scaldis y Cuvée des Trolls, entre otras. Durante esta década de funcionamiento la pequeña empresa ha creado una cartera de clientes estables con más de 300 restoranes, botillerías, bares y pubs en casi todo Chile, de Arica a Chiloé. Cerveza Artesanal Chile ha sido testigo de una invasión de productores caseros, sobretodo en el sur del país, donde gran parte de la población tiene ascendencia alemana y por lo tanto un gusto natural por la cerveza. Uno de ellos es Alberto Peters, quien simplemente se dedicó a la elaboración propia. Es que Peters & Hitschfeld nació con la idea para el consumo propio, no obstante, con cada vez más pedidos de sus amigos, decidió que podría ser algo más de un hobby y hoy cuenta con una producción de 400 litros mensuales, los cuales distribuye a los pubs de la zona de Chinquihue, en la Décima Región.

9

2 Descripción de la Empresa Cervecería y Maltería Quilmes (QUINSA), fue fundada en 1888 por Otto Petter Bemberg. Los orígenes de la cervecería se remontan al año 1852, cuando llegó a la Argentina Don Otto Petter Bemberg y fundó su primera empresa dedicada a la importación de tejidos, y a la exportación de granos, cueros y lanas. Mas adelante, ya en 1886 la familia Bemberg fundó la destilería de alcohol de grano Franco-Argentina en Buenos Aires, en la localidad llamada hoy Guillermo E.Hudson. En enero de 2003 se concreta el acuerdo de integración entre Quinsa y Ambev (American Beverage Company), principal empresa cervecera del Brasil y de América del Sur. Sus marcas principales son: Brahma, Skol, Antártica, Patricia, Norteña y Ouro Fino. De esta manera, Quinsa se consolida en los negocios de los países donde opera y se abren nuevas perspectivas de crecimiento en la región. En marzo, se formaliza la integración de ambas compañías, con la incorporación de las operaciones de Ambev Cono Sur a la estructura de Quinsa en Argentina, Paraguay y Uruguay, iniciándose una nueva etapa en la historia y porvenir de Quinsa. La empresa Cervecería Chile S.A. pertenece al grupo Quinsa que es una compañía holding con presencia en el negocio en bebidas y en malterías en cinco países de Sudamérica. Sus marcas de cervezas son líderes indiscutibles en Argentina, Bolivia, Paraguay y Uruguay, y tienen buena presencia en Chile. Además, a partir de la alianza estratégica con Companhia de Bebidas das Americas-Ambev, tiene un acuerdo para producir y vender en Argentina, Bolivia, Paraguay y Uruguay las marcas de Ambev. Durante los últimos años Quinsa ha seguido una exitosa estrategia de crecimiento basada en la expansión geográfica incorporando nuevos negocios en Bolivia y Chile y en la diversificación relacionada con el desarrollo comercial en el mercado de las aguas minerales y con su incorporación en el negocio de los jugos, gaseosas y bebidas isotónicas. El crecimiento de la empresa en la zona fue un factor decisivo para la expansión misma de la localidad, que con el tiempo y el progreso de la cervecera fue llamada la “ciudad industrial”, cuando por los años 30 los progresos tecnológicos la encaminaron por un incansable crecimiento. La compra de un gigante2 AmBev es la compañía de cervezas más grande del mundo, y se apuntala en el enorme consumo de Brasil, donde posee el control de Brahma. La compañía belga-brasileña ya poseía más del 50% de la firma, que había adquirido en el 2002. AmBev se quedó con el 91% del paquete accionario de Quinsa, la empresa dueña de Cervecería Quilmes, por u$s1.200 millones Por los años sesenta, y ya con el la televisión como medio de comunicación instalado, Quilmes no desaprovechó esa oportunidad y supo adaptarse a los cambios.

(2) Diario Estrategia y Página oficial de la Empresa

Los cantantes de moda de aquel entonces eran los encargados de verbalizar los jingles de la empresa y así convertirla una figura femenina con “La espumita”. Ya en 1998 la compañía argentina comenzó a exportarse a los Estados Unidos y Europa y ganó el número uno en su país. Quilmes pertenece al grupo Quinsa, cuya rama principal es la de la cerveza, pero también está la división de aguas, en donde se comercializa Eco de los Andes Sociedad Anónima, que nace a partir de una asociación con Perrier- Vittel. Además, la compañía incursionó fuerte en el negocio de gaseosas con la compra de BAESA, es decir, la franquicia de Pepsi.

11

3 Descripción y Planteamiento del problema El mercado de la cerveza en Chile se reparte en 82% para CCU y 15,6% Cervecería Chile y 2,4% restante corresponde principalmente a importadores. Esta distribución, trae consigo una connotación especial para cualquier compañía que construye sus decisiones estratégicas (Operacional, Marketing, Financiero, etc.). Bajo esta perspectiva Cervecería Chile, desde 1991, año en que ingresó al mercado chileno, ha mostrado números negativos en su función de utilidad final. Es por ello, que Quilmes-Ambev (Empresa Matriz y propietaria de CCH) han entregado a la actual plana ejecutiva, una directriz única, de obtener una operación con rentabilidad positiva (o auto financiable). Un costo muy incidente en esta directriz es el costo de distribución (33%). El actual sistema de distribución cuenta con una planta de producción en la ciudad de Santiago, y con centros de distribución propios en las ciudades de Quilpué (V región), Concepción, Serena, Temuco y además cuenta con distribución externa en la X región y en la I y II regiónes. Sin embargo, el alcance o ámbito de este estudio se enfocará en la distribución de Santiago en dónde se concentra aproximadamente el 50% de los despachos país. CCH produce 3 marcas de cerveza: Becker (Marca Premium), Báltica y Brahma e importa cerveza Paceña (desde Bolivia). La Participación de mercado es de 15,6% aproximadamente con una venta de 3.000 a 5.000 cajas diarias distribuidas entre 3 Unidades de Negocio: Supermercados, Refrigerados (en esta tesis serán denominados como Pubs), Botillerías. El problema que enfrenta la empresa se puede resumir en el siguiente párrafo: La baja participación de mercado actual (15,6%) que posee CCH en la actualidad conlleva a despacho de pedidos sin envases vacíos devueltos, pedidos sin dinero, altos tiempos de espera, etc. Esta posición desventajosa en el mercado trae además consecuencias sobre jornadas extenuantes de distribución (08:00 hrs. a 24:00 hrs.), rutas excesivas en distancia (un cliente pequeño solicita varias veces en la semana en lugar de 1 ó 2 veces). Todo lo anterior se traduce en un alto costo de distribución, lo cual conlleva bajos márgenes que no le permiten a la empresa aumentar su participación de mercado. Lo anterior trae como consecuencia que los camiones se llenan en primera instancia de clientes (cada pedido de 1 a 2 cajas máximo) más que de productos (diariamente se atienden en promedio 40 Supermercado, 150 Pub y 360 Botillerías). En total, la empresa tiene entre RM (Región Metropolitana más Litoral Central más Rancagua y más Los Andes), 6.200 clientes: 200 Supermercado, 1.000 Pub y 5.000 Botillerías. El sistema actual de transporte en Cervecería Chile es totalmente externo, y participan alrededor de 6 a 7 empresarios transportistas en RM, con una flota que varía entre 17 (período de invierno) y 34 camiones (Verano). La capacidad de los camiones es de 6 toneladas o lo que equivale aproximadamente a 500 cajas de cerveza.

El sistema actual de despacho, no permite un adecuado sistema de mantención preventiva de los camiones, lo que se traduce en continuos atrasos y anulaciones de pedido por fallas de máquinas en ruta. Lo anterior también tiene repercusiones serias sobre el personal humano de transporte, quienes soportan largas y extenuantes jornadas muchas veces de más de 17 hrs. de trabajo. En resumen, un sistema altamente ineficiente (60% de utilización de los camiones) con altos costos de transporte y bajo nivel de servicio (se despacha menos del 85% de las cajas planificadas diariamente). La alta plana ejecutiva esta convencida que en la actualidad los costos de transporte se pueden bajar entre un 10 y un 20% y además aumentar el nivel de servicio por sobre el 85%.

13

4 Alcances del Trabajo El alcance o ámbito del proyecto está localizado en el área de distribución de Santiago. Es importante mencionar que los recursos de transporte son compartidos eventualmente con los sistemas de distribución de regiones a través del préstamo por ciertos períodos para apoyar el despacho, sin embargo estos son poco representativos y bastante esporádicos por lo cual no serán considerados en este estudio. Se consideraran para Santiago 3 unidades de negocio que poseen características distintas para el despacho: Unidad Supermercado (26%), Unidad Refrigerado (24%) y Unidad Hogar (50%) en relación a tiempos de descarga, tiempos de espera (por clientes), margen operacional, etc. Los clientes poseen ventanas horarias (inicio y fin), y cada cliente debe ser atendido por un camión. Los costos de transporte consideran un costo variable por caja despachada y un costo fijo por camión disponible/día (considera gasto chofer y peoneta): - Cobro Tarifa Variable: Costo por Caja ($170/caja despachada) (70% Gto. Transp. Tot) - Cobro Fijo agregado: Colación, uniformes, etc. Para efectos de este trabajo se considerará una jornada máxima de trabajo de 14 hrs. diarias. Sólo existe un depósito de despacho para Santiago y que se encuentra en Panamericana Norte 9600, Comuna de Quilicura. La empresa realiza actualmente sólo un viaje diario por camión, de manera de evitar altos costos de transporte para volver a cargar a la bodega (bodega que se encuentra distanciada del centro de gravedad de su demanda).

5 Objetivo de la Tesis Modelamiento e implementación de un sistema de asignación y despacho de pedidos en Santiago atraves de una herramienta heurística de asignación, de manera de minimizar el costo de transporte y que permita un nivel de servicio por sobre el 85% (nivel de servicio medido como % de cajas despachadas dentro del día) 5.1 Objetivos específicos

- Modelar la situación actual de despacho a través de una aproximación heurística, que permita minimizar los costos de transporte a través de la asignación eficiente de pedidos a camiones y de la secuenciación o ruteo de los mismos.

- Implementación computacional de un sistema de programación de despacho, que considere la herramienta de modelación matemática y la experiencia y el conocimiento instantáneo de las condiciones actuales del despacho.

- Evaluación de la eficiciencia de la metodología propuesta a partir de datos históricos.

15

6 Marco Teórico El problema de distribuir productos desde ciertos depósitos a sus usuarios finales juega un papel central en la gestión de algunos sistemas logísticos y su adecuada planificación puede significar considerables ahorros. Esos potenciales ahorros justifican en gran medida la utilización de técnicas de Investigación Operativa como facilitadoras de la planificación, dado que se estima que los costos del transporte representan entre el 10% y el 20% del costo final de los bienes. En ese sentido, en las últimas cinco décadas han visto un enorme esfuerzo por resolver estos problemas. En 1959, Dantzig y Ramser [1] realizaron por primera vez una formulación del problema para una aplicación de distribución de combustible. Cinco años más tarde, Clarke y Wright [2] propusieron el primer algoritmo que resultó efectivo para su resolución: el popular Algoritmo de Ahorros. A partir de estos trabajos, el área de Ruteo de Vehículos ha crecido de manera explosiva. Por un lado, hacia modelos que incorporen cada vez más características de la realidad, y, por otro lado, en la búsqueda de algoritmos que permitan resolver los problemas de manera eficiente. Estos modelos y algoritmos deben su éxito, en buena parte, a la evolución de los sistemas informáticos. El crecimiento en el poder de cómputo y la baja en sus costos, ha permitido disminuir los tiempos de ejecución de los algoritmos. Por otro lado, el desarrollo de los Sistemas de Información Geográfica resulta fundamental para lograr una adecuada interacción de los modelos y algoritmos con los encargados de realizar la planificación. Pero el interés que reviste el área no es puramente práctico. Los Problemas de Ruteo de Vehículos son Problemas de Optimización Combinatoria y pertenecen, en su mayoría, a la clase NP-Hard. La motivación académica por resolverlos radica en que no es posible construir algoritmos que en tiempo polinomial resuelvan cualquier instancia del problema (a no ser que P = NP). Características de los Problemas A grandes rasgos un problema de ruteo de vehículos consiste en, dado un conjunto de clientes y depósitos dispersos geográficamente y una flota de vehículos, determinar un conjunto de rutas de costo mínimo que comiencen y terminen en los depósitos, para que los vehículos visiten a los clientes. Las características de los clientes, depósitos y vehículos, así como diferentes restricciones operativas sobre las rutas, dan lugar a diferentes variantes del problema. Los Clientes Cada cliente tiene cierta demanda que deberá ser satisfecha por algún vehículo. En muchos casos, la demanda es un bien que ocupa lugar en los vehículos y es usual que un mismo vehículo no pueda satisfacer la demanda de todos los clientes en una misma ruta. Un caso equivalente al anterior ocurre cuando los clientes son proveedores y lo que se desea es recoger la mercadería y transportarla hacia el depósito. También podría ocurrir que la mercadería deba ser transportada a los clientes pero no esté inicialmente en el

depósito, sino distribuida en ciertos sitios proveedores. En este caso, los proveedores deben ser visitados antes que los clientes. En otros casos la demanda no es un bien sino un servicio: el cliente simplemente debe ser visitado por el vehículo. Un mismo vehículo podría, potencialmente, visitar a todos los clientes. En otra variante del problema, cada cliente tiene una ubicación y desea ser transportado hacia otro sitio. Aquí la capacidad del vehículo impone una cota sobre la cantidad de clientes que puede alojar simultáneamente. Es usual que cada cliente deba ser visitado exactamente una vez. Sin embargo, en ciertos casos se acepta que la demanda de un cliente sea satisfecha en momentos diferentes y por vehículos diferentes. Los clientes podrían tener restricciones relativas su horario de servicio. Usualmente estas restricciones se expresan en forma de intervalos de tiempo (llamados ventanas de tiempo) en los que se puede arribar al cliente. En problemas con varios vehículos diferentes podría existir restricciones de compatibilidad entre ´estos y los clientes. En estos casos, cada cliente sólo puede ser visitado por algunos de los vehículos (por ejemplo, algunos vehículos muy pesados no pueden ingresar en ciertas localidades). Los Depósitos Tanto los vehículos como las mercaderías a distribuir (si las hubiera) suelen estar ubicadas en depósitos. Usualmente se exige que cada ruta comience y finalice en un mismo depósito, aunque este podría no ser el caso en algunas aplicaciones (por ejemplo, podría ser que el viaje debiera finalizar en el domicilio del conductor del vehículo). En los problemas con múltiples depósitos cada uno de estos tiene diferentes características, por ejemplo, su ubicación y capacidad máxima de producción. Podría ocurrir que cada depósito tenga una flota de vehículos asignada a priori o que dicha asignación sea parte de lo que se desea determinar. Los depósitos, al igual que los clientes, podrían tener ventanas de tiempo asociadas. En algunos casos debe considerarse el tiempo necesario para cargar o preparar un vehículo antes de que comience su ruta, o el tiempo invertido en su limpieza al regresar. Incluso, por limitaciones de los propios depósitos, podría querer evitarse que demasiados vehículos estén operando en un mismo depósito a la vez (es decir, la congestión del depósito). Los Vehículos La capacidad de un vehículo podría tener varias dimensiones, como por ejemplo peso y volumen. Cuando en un mismo problema existen diferentes mercaderías, los vehículos podrían tener compartimentos, de modo que la capacidad del vehículo dependa de la mercadería de que se trate. En general, cada vehículo tiene asociado un costo fijo en el que se incurre al utilizarlo y un costo variable proporcional a la distancia que recorra. Los problemas en que los atributos (capacidad, costo, etc.) son los mismos para todos los vehículos se denominan de flota homogénea, y, si hay diferencias, de flota heterogénea. La cantidad de vehículos disponibles podría ser un dato de entrada o una variable de decisión. El objetivo más usual suele ser utilizar la menor cantidad de vehículos y minimizar la distancia recorrida ocupa un segundo lugar. Regulaciones legales podrían imponer restricciones sobre el tiempo máximo que un vehículo puede

17

estar en circulación e incluso prohibir el pasaje de ciertos vehículos por ciertas zonas. En algunos casos se desea que la cantidad de trabajo realizado por los vehículos (usualmente el tiempo de viaje) no sea muy dispar. En general se asume que cada vehículo recorre una sola ruta en el período de planificación. Para situar inicialmente este tipo de problemática, es importante contextualizarlo dentro del proceso de toma de decisiones de distribución de una empresa. A saber, existen:

- Decisiones respecto de la capacidad y localización de las instalaciones (plantas o almacenes): Este tipo de decisiones corresponde a una decisión de tipo estratégico.

- Decisiones sobre la definición del tamaño y mezcla de los medios de transporte es de vital relevancia: Esta decisión más bien corresponde a una decisión de tipo táctico.

- Decisiones respecto a la asignación de carga a los respectivos transportes y la determinación de la ruta de los vehículos a través de un set de consumidores, y su programación para satisfacer limitaciones de tiempo y precedencias: Este tipo de decisión corresponde a una decisión de tipo operativo y es efectivamente el tipo de problemática que abordaremos en este trabajo.

En el caso de la problemática de ruteo planteada en el punto anterior, esta se agrupa dentro de los problemas de optimización combinatorial. En ellos las variables de decisión son enteras y por lo general el espacio de soluciones está formado por subconjuntos de números naturales. En el caso de la optimización combinatorial, se trata de hallar el mejor valor entre un número finito de posibilidades, pero la enumeración de este conjunto de posibilidades resulta prácticamente imposible, aún para instancias de tamaño moderado. Pronto comenzaron a modelarse de esta manera aplicaciones más técnicas, y hoy vemos problemas de optimización discreta casi en cada campo del conocimiento: diseño de campañas de marketing, planeamiento de inversiones, secuenciamiento de genes, posicionamiento de satélites, determinación del tamaño de vehículos y las rutas de medios de transporte, asignación de trabajadores a tareas. La lista parece interminable aún en áreas como deportes, arqueología o psicología. El problema de Ruteo de vehículos es uno de los problemas NP de optimización combinatoria mas conocidos. Este problema consiste en un conjunto de clientes con demanda que deben ser abastecidos por un único depósito. Para ello se cuenta con una serie de vehículos con la misma capacidad, los cuales deben partir y regresar al depósito. Cada cliente debe ser visitado una única vez por un vehículo. La solución de este problema busca minimizar la distancia recorrida y el tiempo empleado por estos vehículos, pero satisfaciendo la demanda de todos los clientes, no violando la capacidad de los vehículos, ni el tiempo disponible de cada vehículo, ni los tiempos de entrega de los clientes. Los problemas de ruteo y programación tienen un impacto relevante en el costo de transporte y el nivel de servicio al cliente.

Se identifican 3 tipos básicos de problemas asociados a rutas y transportes: 1.- Encontrar una ruta en una red donde el origen es diferente al punto destino 2.- Definir rutas de transporte entre múltiples orígenes y destinos 3.- El problema de rutear vehículos La solución del primer tipo de problema se facilita mediante el uso de métodos para encontrar los caminos más cortos entre puntos. El segundo tipo de problema ha sido resuelto mediante la aplicación del método de transporte y variaciones de éste. La solución del tercer tipo de problema incluye la utilización de numerosos y diversos modelos como el del agente viajero (TSP), ruteo de vehículos (VRP), el VRP con ventanas de tiempo (VRPTW), el problema de recoger y entregar (PDP), el problema de ruteo e inventario (IRP), y otros. Dependiendo de las restricciones, la mayoría de los problemas de ruteo de vehículos puede clasificarse en (16): 1. TSP (Traveling Salesman Problem): Cuando se trata de solucionar este problema

teniendo en cuenta únicamente la restricción de que se deben visitar todos los clientes una única vez, el problema de ruteo de vehículos se conoce como TSP. Para este problema se cuenta con un único vehículo sin límite de capacidad; y no se tiene un depósito sino algunos clientes, en este caso sin una demanda específica, que deben ser visitados, minimizando la distancia recorrida. Los datos de entrada son las distancias entre los clientes o ubicación de los mismos.

2. CVRP ( Capacitated Vehicle Routing Problem): Cuando se tienen en cuenta las

restricciones de que se deben visitar todos los clientes una única vez y suplir su demanda total y además no violar la capacidad de los vehículos, el problema de ruteo de vehículos se conoce como CVRP. Para la solución de este problema se cuenta con n vehículos con capacidad única y específica, que deben partir y regresar a un depósito en cada secuencia de visita de clientes. La función objetivo puede ser minimizar la distancia total recorrida por todos los vehículos.

3. TCVRP (Time Constrained Vehicle Routing Problem): Cuando se tienen en cuenta además de las restricciones del caso anterior, no violar el tiempo disponible que tienen los vehículos para realizar su recorrido, el problema de ruteo de vehículos se conoce como TCVRP. Para la solución de este problema se cuenta con n vehículos con capacidad única y específica y tiempo de atención por secuencia, que deben partir y regresar a un depósito en cada secuencia de visita de clientes. La función objetivo sigue siendo minimizar la distancia total recorrida por todos los vehículos. Los datos de entrada son las distancias entre los clientes o ubicación de los mismos, las demandas de cada cliente, la capacidad de los vehículos y el tiempo de atención de los vehículos. (3) http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/

19

4. CVRPTW (Capacitated Vehicle Routing Problem with Time Windows): Cuando se tiene en cuenta además de las restricciones del caso anterior, no violar los horarios de recepción de mercancía de los clientes, el problema de ruteo de vehículos se conoce como CVRPTW. Para la solución de este problema se cuenta con n vehículos con capacidad única y específica y tiempo de atención por secuencia, que deben partir y regresar a un depósito en cada secuencia de visita de clientes, y

5. además cada cliente especifica un horario de recepción de mercancía que debe ser cumplido. La función objetivo sigue siendo minimizar la distancia total recorrida por todos los vehículos. Los datos de entrada son las distancias entre los clientes o ubicación de los mismos, las demandas de cada cliente, la capacidad de los vehículos, el tiempo de atención de los vehículos y los horarios de atención de los clientes.

6. PVRP (Periodic Vehicle Routing Problem): Para este caso se tienen en cuenta las Restricciones de que un cliente debe ser visitado al menos un día durante un período de días; los vehículos tienen una capacidad específica, los clientes una demanda que debe ser satisfecha y posiblemente unas ventanas de tiempo que también deben ser cumplidas.

Para el caso de nuestra Tesis y ventanas de tiempo, se ajusta el problema de ruteo de vehículos (CVRPTW) con restricción de capacidad, el cuál posee las siguientes características:

• Se tiene una flota de vehículos idénticos para hacer entregas de un almacén central a un conjunto de clientes.

• El problema básico consiste en determinar K rutas de cada vehículo, dónde cada ruta inicia y termina en el almacén central después de realizar una secuencia de visitas a un set de clientes. Cada cliente se asigna a un vehículo solamente y la capacidad del vehículo no debe excederse. Todo al mínimo costo.

• La determinación puede resultar en rutas fijas a realizar o en rutas variables en cada período que dependerán de la demanda de los clientes.

Aspectos adicionales del problema (CVRPTW): • Otras características de los vehículos:

– Vehículos diferentes (no es el caso de esta Tesis en particular) – Limitaciones simúltaneas (volúmen y peso). – Capacidad compartida de varios tipos de artículos – Compatibilidad entre vehículo y cliente. – Varios viajes en el horizonte de planeación

• Además de entregar se requiere recoger artículos • Limitación en el tiempo total del viaje. • La existencia de “ventanas de tiempo” con los clientes. • Limitaciones de precedencia entre clientes. • La existencia de almacenes múltiples con sets de vehículos asignados a ellos. • En lugar de cantidad fija de vehículos, definir cuántos. • Entrega a ciertos clientes es opcional incurriéndose en castigo.

• Determinar cantidad de artículos y rutas para abastecer clientes

Los Algoritmos de solución que se vislumbran son 3 y que son desarrollados para resolver el problema de ruteo de vehículos4:

1.- Algoritmos de Primera Generación.- Consiste de métodos heurísticos. El algoritmo representativo es el de Clarke and Wright, que es el que ha perdurado por su flexibilidad para considerar restricciones de diversa naturaleza.

Los algoritmos de primera generación pueden ser de los siguientes tipos: • Algoritmos de Construcción de Rutas.- En éstos, un enlace entre 2 clientes

se incluye secuencialmente hasta que todos han sido asignados a una ruta. Cada vez que se agrega un cliente, se determina si la capacidad del vehículo y otras restricciones adicionales se satisfacen. La selección de un enlace se basa en los ahorros en costo.

• Algoritmos de Mejora de Rutas.- Éstos inician con una ruta factible y en cada iteración, alguna combinación de intercambio de enlaces que sea factible y ahorre costos se lleva a cabo.

• Algoritmos de 2 Fases.- Los algoritmos de este tipo inician asignando clientes a cada vehículo sin violar su capacidad como primera fase. Posteriormente se define la secuencia en que cada cliente debe ser visitado como una segunda fase.

2.- Algoritmos de Segunda Generación.- Se caracterizan por la aplicación de programación matemática optimizante para desarrollar métodos de solución, mediante la utilización de modelos que aproximaban el problema de ruteo.

• Los algoritmos de ésta generación son heurísticos basados en programación matemática. Los más representativos se basan en la solución de los problemas de asignación generalizada y el de “set partitioning”.

• El algoritmo de Fisher & Jaikumar (1981) consiste en 2 fases; La primera resuelve el problema de asignación generalizada para asignar clientes a los vehículos y; La segunda fase resuelve problemas del agente viajero para definir la secuencia de visitas en cada ruta para cada vehículo.

3.- Algoritmos de Tercera Generación.- La investigación sobre el problema de ruteo se centra en el desarrollo de algoritmos “robustos” que puedan aplicarse a una amplia gama de situaciones problemáticas. Un enfoque para lograr lo anterior es la utilización de enfoques interactivos a través de interfaces con el tomador de decisiones, otro enfoque es la utilización de la inteligencia artificial.

• Los algoritmos son incorporados a sistemas computacionales con alto grado de interacción del tomador de decisiones.

• Algunos incorporan el uso de mapas digitales “inteligentes”.

(4) http://www.uv.es/asepuma/XIII/comunica/comunica_44.pdf

21

7 Metodología utilizada Las metodologías optimizantes para resolver el problema de asignación de cargas a camiones y la secuenciación del despacho con ventanas de tiempo son tratadas y resueltas desde hace tiempo (lo anterior producto también del considerable aumento de capacidad de las nuevas tecnologías para resolver este tipo de problemas). En estas condiciones se hace interesante plantear alternativas de tipo heurístico que permitan visualizar una variedad de alternativas de solución (ruteos alternativos) de forma sencilla, barata y en corto tiempo y que además permitan la decisión del programador responsable con herramientas del tipo ¿Qué pasa sí? En la actualidad, el área de programación de la empresa utiliza un software de apoyo llamado RoadShow5 que sólo se utiliza su parte gráfica, para generar rutas factibles (el sistema no optimiza pues no tiene alimentado los tiempos reales de viaje e implementar el módulo de optimización superaba los costos esperados de la empresa). En rigor, el chofer (transporte externo) genera su propia secuencia de entrega. La heurística debe considerar minimizar los costos de transporte a través de minimizar la cantidad de kilómetros recorridos y el tiempo empleado (básicamente el tiempo de viaje) de manera de minimizar la cantidad de camiones necesarios y maximizar la cantidad de cajas y clientes despachados, cumpliendo las restricciones de jornada máxima para cada camión, cumplimiento de las ventanas horarias de atención de clientes y capacidades físicas de los camiones. El tipo de heurística que se propone posee 2 etapas características: 1.- Una etapa de construcción de rutas factibles, que en función de las restricciones del problema (número de camiones, capacidades, tiempos de jornada máximo, etc.) genera un conjunto de soluciones iniciales. 2.- Una etapa de mejoramiento de la solución inicial: En esta etapa se conideran intercambio de clientes entre distintas rutas. Este tipop de intercambios son conocidos en la literatura como λ- interchange. Una particularidad de este tipo de heurísticas es que entrega una solución bastante cercana al óptimo (2,5% cercana al óptimo, de acuerdo a “[3]”) con un tiempo de procesamiento adecuado (vital para la empresa en cuestión que requiere de un conjunto de alternativas de solución en un breve plazo) y además permite resolver un problema de tamaño relevante (entre 100 y 150 clientes en la ruta)

(5) www.descartes.com (1976)

7.1 Heurística Utilizada La heurística se seleccionó de acuerdo a sus características de modelar adecuadamente el problema, su simplicidad para la formulación y finalmente por responder satisfactoriamente con los tiempos de obtención de soluciones. El método consiste en el desarrollo de 2 etapas, la primera la búsqueda de 1 solución factible (rutas factibles que cumplan capacidad del camión, ventanas de tiempo de clientes y ventanas máximas de trabajo (jornadas de trabajo choferes)) y luego el mejoramiento de la solución inicial a través del intercambio de clientes entre rutas (probando una cantidad finitas de intercambios en forma ordenada). 7.1.1 Descripción Método Obtención Solución Inicial Factible La solución inicial de este método se logra con la construcción de las rutas una por una. Cada ruta posee inicialmente un cliente semilla sobre el cual se van agregando clientes no ruteados uno por uno. La ruta concluye cuando los clientes no ruteados que restan no son factibles de incluir en ésta por infactibilidades de capacidad, no cumplir las ventanas de horario o jornada de trabajo y se prosigue con la construcción de una nueva ruta para el cual se debe elegir un nuevo cliente semilla y así sucesivamente. La elección tanto de los clientes semilla como el mejor próximo cliente a insertar en las rutas se realiza a través de funciones de costo, en las cuales participan: Distancia, Tiempo máximo de ventana, ángulo de desfase con bodega, Tiempo total de ruta, etc. Estas funciones de costo son: Función de costo para seleccionar cliente Semilla (o primer cliente): Minimizar Función de Costo (Cliente semilla) = −α d0u + β lu + γ angleu dónde α, β y γ son constantes fijas y d0u es la distancia del cliente semilla al último cliente de la ruta anterior, lu es el tiempo máximo de la ventana horaria del cliente semilla y angleu es el ángulo entre el cliente semilla y el último cliente insertado en la ruta anterior. En el caso de la primera ruta el cliente semilla se calcula respecto del eje que generan el punto de ubicación de la bodega y el eje x. Función de costo para inserción de clientes en rutas ya iniciadas: Función de Costo (Cliente semilla) = Dnew(i,u,j),k+ φWnew(i,u,j),k (Minimizar) dónde Dnew(i,u,j),k corresponde a la distancia total acumulada de la ruta k con el nuevo cliente a insertar y Wnew(i,u,j),k corresponde al tiempo total acumulado de la ruta con la inserción del nuevo cliente. Claramente para esta inserción sólo se consideran aquellos clientes que en su inserción cumplen las restricciones de capacidad del camión, ventanas horarias de los clientes y jornada de trabajo del camión.

23

Con lo anterior se obtiene la solución inicial factible, que el método mejora en la segunda etapa que se describe a continuación. 7.1.2 Descripción Método Obtención de Mejora de Solución Las rutas construidas inicialmente con el algoritmo descrito en el punto 6.1.1, poseen un costo asociado a la distancia y el tiempo empleado. La idea del algoritmo de mejora es tomar pares de rutas e intercambiar clientes y revisar si la función de costo disminuye. Si disminuye, el método considera que esta nueva solución es la solución actual (notar que no necesariamente factible) y se comienza el ciclo de revisión de los Operadores. El método de mejora se basa en la utilización de 8 Operadores de intercambio de clientes entre pares de rutas. Operador1: (0,1) Operador5: (2,0) Operador2: (1,0) Operador6: (2,1) Operador3: (1,1) Operador7: (1,2) Operador4: (0,2) Operador8: (2,2) Los números entre paréntesis indican la cantidad de clientes que se intercambian entre 2 rutas cualesquiera, por ejemplo en el caso Operador6 (2,1), el procedimiento es pasar 2 clientes de la ruta 1 a la ruta 2 y pasar 1 cliente de la ruta 2 a la 1. Para una cantidad de k rutas, la cantidad de comparaciones de a pares de rutas equivalen a (k!) / ((k-2)! 2!) , lo que se traduce en (k (k-1) /2) comparaciones. En cada comparación de a pares, el sistema (inicialmente) utiliza el Operador1, Operador2, y así sucesivamente hasta el operador8, para comenzar su intercambio de clientes entre las rutas. El proceso en cada Operador es el siguiente; Se intercambian los primeros n1 clientes de la ruta 1 y n2 clientes de la ruta 2 (es importante recalcar que los n1 ó n2 clientes que se toman siempre son consecutivos en la ruta), luego se va calculando la función de costos (que se explicará más adelante) y si esta función disminuye del valor inicial, este nuevo intercambio pasas a ser la nueva solución actual y todo parte nuevamente. De no haber una disminución en la función de costos, se produce un intercambio de los n1 clientes dentro de su nueva ruta en forma secuencial, ordenada y definida. Al final de todos los posibles cambios de posición de los clientes de intercambio (pues no lograron disminuir la función de costo inicial), se pasa al Operador siguiente según el orden definido y se sigue así sucesivamente. La función de costo que se revisa constantemente es la definida por la heurística planteada: C(S) = ∑ Dk + Φ Wk + η Ok + κ Tk donde Dk es la distancia total de la ruta k, Wk es el tiempo total de la ruta k, Ok es suma total de sobrecapacidad del móvil de la ruta k (sobrecapacidad por sobre la capacidad nominal definida) y Tk es el exceso de tiempo acumulado en la ruta por llegar sobre los tiempos máximos de las ventanas de tiempo de los clientes, bodega y tiempo máximo de jornada del chofer del móvil.

Φ, η y κ son parámetros que penalizan en la función de costos los excesos en capacidad y de tiempos de entrega de los clientes en la ruta. Una conclusión relevante es de que las soluciones posteriores a la solución inicial factible, con la que comienza el método, puede convertirse en infactible en la medida que los costos por penalizaciones (por sobrecapacidad o exceso de tiempos de entrega) sean menores que los costos directos de tiempo y distancia. Los valores recomendados en [3] para estos parámetros son: 1% de Dk para Φ, 7% de Dk para η y 6% de Dk para κ.

25

7.2 Programación de Operaciones actual La programación de la asignación de pedidos a camiones y la secuencia de despacho en la actualidad es realizada por una persona, que por medio de un software (RoadShow) que le permite observar los pedidos de los clientes en el mapa de Santiago, le ayuda a construir las rutas en forma manual. Este proceso de programación para los pedidos del día siguiente, es realizado posterior al proceso de bajada de pedidos de los vendedores desde sus máquinas tomadoras de pedidos (HandHeld Psion). Este último proceso culmina alrededor de las 21 hr., y desde este momento comienza el proceso de programación que demora alrededor de 1 a 1,5 hrs. diariamente. El comportamiento de la venta de cervezas, como se entenderá es bastante estacional, incrementándose al doble la venta en los períodos de primavera-verano. Es así también como el requerimiento de camiones en este período se incrementa ostensiblemente. El desarrollo de esta memoria se hará en un mes característico estacional del período primavera-verano, pues es aquí donde se pueden visualizar mejor los ahorros posibles de obtener con algoritmos como éste que se dirigen hacia minimizar el tiempo de despacho empleado (y que tiene cierta relación directa final con la distancia total recorrida). Se eligió un mes de demanda pasado sobre el cual se conocieran los siguientes datos: Proyección de ventas, Programación de despachos, Despacho real. Esta información se conoce día a día para el mes de Diciembre de 2008. A continuación se muestra los datos de proyección de ventas de cajas de cervezas por día (no se consideran días domingos), se consideran los 3 tipos de negocios (Botillerías, Supermercados y Pub) y además se separa por cuadrante (grupo de comunas) de despacho (se consideran 4 cuadrantes en Santiago)

Tabla 7.2.a

La configuración de estos grupos tuvo en consideración equilibrar la demanda de cajas de cervezas, la cantidad de clientes por grupo, la distancia promedio de clientes, entre otros. La demanda en cajas, día por día, por tipo de negocio y por grupo comunal es la siguiente:

Tabla 7.2.b Demanda en cajas de Cervezas

La misma proyección de demanda anterior medida como número de clientes, día por día, por tipo de negocio y por grupo comunal es la siguiente:

Tabla 7.2.c Demanda en Nro. Clientes

27

También se dispone para este período, número de clientes insatisfechos. y el porcentaje de no despacho de cervezas en número de cajas.

Tabla. 7.2.d porcentaje de no despacho en clientes y en cajas por dia Si uno grafica tanto la demanda por cajas o demanda de número de clientes, se puede dar cuenta de que esta crece dentro de la semana (es decir de lunes a sábado va creciendo la demanda) y además se observa existe una tendencia de crecimiento semana a semana, tal como se ve en el gráfico siguiente (demanda en cajas/día):

Grafico 7.2.e Demanda en cajas/dia (Comportamiento representativo para cualquier mes del año) 7.2.1 Calibración de la Metodología Para poder modelar el sistema de transporte de esta empresa en particular, se utilizaron varios supuestos necesarios de describir:

• Los puntos geográficos de casi 5.000 clientes se geo-referenciaron con información de la dirección del cliente y de Mapcity.

• Los tiempos de viaje entre bodega y clientes o entre cliente y cliente, se determinaran a través del cálculo de tiempo derivado de la distancia euclidiano entre los puntos y la velocidad media de traslado (que se estimó en 40 km/hora)

• Los tiempos de espera de clientes (para iniciar descarga) y los tiempos de descarga de cajas (seg./caja) se obtuvieron de acuerdo a estudios de tiempos en muestras a visitas de distintos tipos de negocios en los despachos (Botillería, Pub, Supermercado). Los resultados se muestran en la tabla siguiente: Tiempos de Espera en segundos: Botillerías: Los clientes botillerías poseen tiempos de espera de 700, 1000, 1200, 1250, 1300, 1500, 2200, 4000 y 4500 segundos. PUB: Los clientes Pub poseen tiempos de espera de 700, 1000, 1200, 1250, 1300, 1500, 2200, 6500 y 7000 segundos. SPMK: Los clientes Pub poseen tiempos de espera de 700, 1000, 1200, 1250, 1300, 1500, 5000, 14350 y 14400 segundos. Tiempo de Descarga por caja (seg./caja): En este parámetro, tanto los clientes de Botillería, PUB y SPMK tienen comportamientos similares y sus valores oscilan entre: 10, 15, 20, 25, 30, 35 y 40 seg/caja

29

• Las ventanas horarias fueron censadas por cada vendedor con sus respectivos

clientes (y son las horas que exigieron los clientes para la entrega de su producto)

• La hora de comienzo de los despachos es 07:00 AM, y la duración máxima de la jornada corresponde a 14 hr./día

• Los camiones de despacho corresponden al mismo modelo y capacidad (500 cajas)

Con la información obtenida en el punto 7.2.d y de acuerdo a los parámetros y restricciones definidos en el punto 7.2.e, se logró calibrar esta información con la información proveniente de la programación y despacho real (despachos realizados y % de rechazo por fuera de horario u otro). A continuación se muestran elementos de esta validación para los primeros dos días del período del cual se dispone la demanda:

31

Esta programación corresponde a la programación real del día 1 de Diciembre de 2008 del grupo de comunas nro.1 (Huechuraba, Recoleta, Providencia, Ñuñoa, Vitacura, Las Condes, La Reina, Lo Barnechea, Colina) y en donde cada color representa una ruta (hay un total de 5 rutas para este grupo de comunas). Las columnas muestran el tipo de negocio, ID Cliente (código), Nro. Cajas demandadas, Comuna, Grupo Comuna, Distancia (mt.) (Desde el cliente anterior, si es el primero corresponde a la distancia desde la Bodega), Tiempo de Viaje y Hora de Llegada (en formato decimal). La Hora de llegada, en el último cliente de cada ruta muestra que el horario máximo de despacho corresponde a las 22 hrs. (por lo tanto una jornada máxima de 15 hrs.) Recordemos que cada ruta corresponde a la ruta real programada ese día y los datos expuestos en la tabla anterior fueron calculados con los parámetros supuestos, por lo tanto la equivalencia entre los resultados reales con los modelados a través de los parámetros validan la metodología y los parámetros a utilizar. Lo anterior confirma los parámetros supuestos de análisis, entre otros: La Distancia euclediana utilizada para definir la distancia a cubrir efectiva por los móviles; La velocidad de desplazamiento promedio de 40 Km/hra. (Éstas son las más importantes)

Figura 7.2.1.a En la figura anterior se muestra el proceso de cálculo de distancia entre dos puntos (en el ejemplo entre la Bodega Central y un cliente particular). La línea continua muestra el cálculo simple de la distancia euclidiana entre dos puntos que en el caso del ejemplo corresponde a 6,076 km. y en línea segmentada se muestra el camino y distancia real entre los dos puntos y esta corresponde a 6,54 km., la diferencia es aproximadamente

7%. Esta diferencia si bien es cierto es importante en este trabajo de tesis se amortigua con el valor de rapidez promedio (menor a la medida en tiempo real). Lo anterior se verifica y valida con la programación de los primeros días en donde tal como se manifestó se dispone de la programación real de esos días, con la cantidad de clientes reales a los cuales se despachó, su secuencia, sus tiempos y aquellos clientes no despachados y se comparó con los resultados de la programación realizada con los parámetros de rapidez, tiempos de carga, tiempos de espera y la forma de cálculo de la distancia entre dos puntos (euclidiana).

33

7.3 Descripción Programa Computacional La Heurística explicada en 7.1, que se aplica a una empresa elaboradora y distribuidora de cervezas, tiene entre sus característica su facilidad para implementación y simpleza, para un conjunto de 130 a 150 clientes. Sus resultados indican que su función objetivo de minimizar los costos de transportes (distancia y tiempo) se logra en una vecindad del 2,5 a 3,0% por arriba del valor óptimo. Con estas antecedentes se detalla los requerimientos con los cuales se construyó la solución informática: Requerimientos de Acceso de datos 1. Los métodos de acceso de datos son realizados a través de los objetos de acceso de datos (ADO.net) para el controlador de conectividad a SQL a Bases de Datos Access y Excel. 2. Se utiliza una clase de manejo de datos común a la aplicación, de forma de minimizar errores por códigos redundantes y centralizar las llamadas al servidor de datos en forma unificada. 3. Se desarrolló de una componente liviana y común de acceso de datos para Access. Denominada Calculo de Rutas.exe. 4. La solución consta de una interfaz de ingreso de Información por pantalla (Fig. Nº 1), información de clientes obtenidas a través de access y los resultados serán mostrados a través de una planilla Excel. Figura Nro.1

Implementación tecnológica La Aplicación propuesta fue desarrollada en Microsoft.NET Framework consistente en la utilización de herramientas y lenguajes tales como: • Clases Componentes desarrolladas bajo el nuevo lenguaje orientado a objetos Visual Basic.NET. • Acceso a datos mediante ADO.NET y ODBC de gran performance y solidez. • Microsoft Windows 2000 o superior. • Access • Excel El texto de de la aplicación se muestra en el Anexo A. El formato de los datos de entrada (y parámetros) y los resultados de la corrida de la aplicación se entregan en planilla Excel con el siguiente formato: Formato Datos de Entrada:

Id_cliente : Código correlativo del cliente para la aplicación Cod_Cliente : Código del Cliente interno para la empresa pos_x : Coordenada x del cliente en mapcity pos_y : Coordenada y del cliente en mapcity Demanda : Pedido de cervezas en unidades de cajas tpo_descarga : Tiempo de descarga por caja para este tipo de cliente tpo_espera : Tiempo espera de los repartidores antes de iniciar descarga en el cliente tpo_min : Ventana de tiempo inicial del cliente tpo_max : Ventana de tiempo final del cliente

35

Formato Datos de Salida (Output o resultados):

Cada columna representa una ruta de un camión que distribuye los pedidos de los clientes (en el orden establecido (primero de arriba hacia abajo), el primer cliente de una ruta siempre es el id_cliente=”1” que representa la Bodega Central). En este ejemplo, la solución considera 5 rutas (factibles además). En este ejemplo, el programa entrega como resultado que para la Ruta 1 (El valor de la función de costo para esa ruta fue de 21.410 y luego el programa describe la secuencia ordenada: Se parte por el cliente 1 (Bodega) en donde se carga los productos y luego el primer cliente a atender es el Id_cliente 85, luego el 87, luego el 74 y asi sucesivamente terminando con el cliente id_76.

8 Resultados Para llevar a cabo el procedimiento de obtención de resultados mediante esta heurística, se procedió a elegir 2 días de cada semana que representen fielmente las condiciones de borde de un período de alta demanda como es Diciembre 2008. Si miramos la gráfica de la Figura 7.2.3 (pag.25), se puede observar principalmente que en los tres tipos de clientes de esta empresa sus valores extremos se muestran los días 2 y 5 (Martes y Viernes respectivamente) de cada semana. Se utilizaran por lo tanto, estas 4 semanas de Diciembre para efectos de mostrar los resultados comparativos de la programación real y la programación a través de la heurística propuesta en este trabajo. 8.1 Cálculo de nuevas rutas mejoradas En todos y cada uno de los días seleccionados para realizar la comparación se observaron indicadores de desempeño más eficientes con ahorros relevantes en distancias recorridas y tiempos empleados, además de ahorros en número de camiones a programar (en un rango de 1 a 4 camiones/día). A continuación se muestra la programación real para el día 2 y 5 de la primera semana de Diciembre (se presenta en la tabla siguiente una muestra de 2 camiones), en donde se puede observar en colores distintos los camiones programados (para el tipo de Comuna 1, que corresponde a Huechuraba, Recoleta, Providencia, Ñuñoa, Vitacura, Las Condes, La Reina, Lo Barnechea, Colina)

37

Esta programación cumple con las restricciones de no programar más de 500 cajas por camión y no trabajar más de 14 horas diarias.

Tanto para el día 2 como para el día 5, los camiones programados en función de la demanda para ese día y las restricciones fueron 6 y 7 camiones respectivamente. Para la programación propuesta según la heurística analizada entrega los siguientes resultados para los días 2 y 5 respectivamente:

39

Para la programación consolidada de estos 2 días, se concluye primero que la cantidad de camiones utilizados es de 6 y 7 camiones respectivamente, lo cual no muestra signos de ahorro respecto de la programación actual (6 y 7 camiones también), sin embargo la diferencia o la eficiencia se verá después reflejada en los tiempos y distancias empleados por estos camiones en recorrer y descargar los productos a los clientes. Otro elemento importante a considerar corresponde a que la actual programación de la empresa considera relevante en cada comuna programar todos los clientes de un mismo tipo (por ejemplo Pub), en cambio la heurística propuesta promueve programar los clientes independiente de su tipo, en secuencia de acuerdo a sus tiempos, distancia y cumplimiento de restricciones (ventanas horarias, sobretodo el caso de supermercados) que minimicen la distancia y el tiempo total empleado.

8.2 Diferencias en distancias recorridas En el período analizado de 4 semanas de Diciembre, que se traducen en 8 días hábiles, de los cuales 4 son días martes y 4 días viernes, ambos días muy representativos del comportamiento semanal de la demanda como se puede observar en la figura 7.2.3, donde cada color representa una semana diferente.

Se pueden observar ahorros importantes del orden del 51% al 58% respecto de la distancia total de la flota programada con el método actual. Esto claramente redunda en

41

menor costo de combustible que finalmente se puede traducir en un menor costo variable para la empresa y además en un importante reducción de tiempo de viajes, lo cual puede permitir un aumento de la utilización de los camiones mediante una mayor carga de pedidos de clientes en cada camión (recordar que esta empresa tiene una baja utilización de los camiones del orden del 37%). 8.3 Diferencias en tiempos empleados Al igual que en el caso de las distancias recorridas, los tiempos requeridos para la distribución según la heurística propuesta reducen entre un 7,6% y un 12,4% (intervalo porcentual de ahorro para las 4 semanas de análisis (Diciembre 2008). Lo anterior significa ahorrar en promedio diariamente entre 1 y 2 horas de distribución, con el consiguiente beneficio de poder aumentar el despacho diario promedio por camión.

A medida que aumenta la cantidad de cajas a despachar o la cantidad de clientes a distribuir, el ahorro muestra una pequeña tendencia a crecer, lo que resulta más o menos razonable. 8.4 Valorización de Beneficios y Ahorros para la Empresa con los nuevos

resultados de distancia y tiempos empleados Es posible detectar 2 formas de ahorro de costos con esta herramienta, uno de forma directa y otro de forma indirecta. Beneficio Directo: Por el lado de ahorro de distancias a recorrer existe un beneficio directo que tiene que ver con el menor combustible a consumir y por otra parte se tiene un beneficio relacionado con un menor desgaste de los camiones (menos desgaste de neumáticos, menor gasto de amortiguadores y repuestos en general (menores costos de mantención)). Beneficio Indirecto: Respecto de los ahorros en los tiempos de viaje, estos se traducen en disponibilidad de mayor cantidad de horas para despachar mayor cantidad a cajas a un mayor número de clientes (esta probabilidad es alta pues la empresa tiene en la actualidad un porcentaje alto de producto rechazado principalmente por atrasos (aprox. 10%)). A continuación se hará un breve cálculo de los ahorros monetarios posibles producto de estas mejoras para dimensionar las bondades y robustez de la propuesta: Beneficio Directo: Ahorro Combustible Camion 6 Toneladas con rendimiento de 2,5 km/lt. El ahorro promedio en distancia menor recorrida es de 50 km/dia-camion. Si se considera un valor del diesel de $496/lt (27/08/10) esto implica un ahorro de $12.400/dia-camion aproximadamente, lo cual corresponde a un 25% de la tarifa diaria que recibe el transportista por sus servicios. Además se puede calcular un ahorro por menor desgaste del camión, este ítem se puede estimar haciendo un cálculo fácil de ahorro por mayor tiempo entre mantenciones preventivas ($30.000/mes ó $2.000/día) Beneficio Indirecto: Si tomamos en cuenta el comentario hecho en el punto 7.1.3, en donde los ahorros de tiempos promedio estimados son de 1 a 2 horas dia-camion, si además consideramos que un camión en promedio (para el período considerado, 4 semanas de Diciembre 2008) despacha 188 cajas/dia-camion ó 13 cajas/hora-camion, podemos estimar la cantidad de despachos adicionales que podríamos lograr (tomando en consideración que existe un alto % de producto rechazado por atraso en la entrega) por camión es de 26 cajas adicionales/camión-dia, si consideramos que la empresa logra como margen operacional por caja despachada $240, entonces tendremos un beneficio adicional de $6.240/dia Beneficios o Ahorros resumidos por propuesta de Tesis

Beneficio o Ahorro ($/dia-camion)

Directo Indirecto Combustible Mantención Mayores Ventas

Menores Tpos.y Distancias $12.400 $2.000 $6.240 Total Beneficios o Ahorros $20.640

43

Si estos ahorros o beneficios por dia-camion, lo traspasamos a la flota completa y a la cantidad de dia/mes normal, la cifra asciende aproximadamente a MM$16/mes, esto corresponde a un 1% de las ventas mensuales (valores), lo cual es muy razonable para un mercado bastante competitivo en donde cualquier % de ahorro en costos variables es muy relevante para lograr una ventaja competitiva.

8.5 Cálculo de tiempos de Procesamiento Los tiempos de procesamiento de la herramienta resultaron razonables y bastante accesibles para lograr correr el programa propuesto en la noche de cada día, una vez alimentado los pedidos de cervezas para el día siguiente. En este sentido, los tiempos dependen de la cantidad de clientes a programar. Asi entonces se obtuvo la siguiente tabla de tiempos promedio en varias corridas del programa:

Número de Clientes

Tiempo de Corrida (seg)

60 20 90 50 120 120 150 210 180 375 210 650 240 750 270 800 300 990 330 1.050

Se corrieron por cada número de clientes alrededor de 10 corridas distintas, y los valores que se muestran son lo valores promedio con un desviación estándar de 5%. Si consideramos que el programa debe correr 4 cuadrantes (Grupos de comunas) diariamente y tomamos el caso mas limitante que sería tener todos los cuadrantes con

0

200

400

600

800

1000

1200

0 100 200 300 400

Tiempo de Corrida (seg) por Nro. de Clientes

Tiempo de Corrida (seg)

una cantidad de clientes máxima de 330 tendriamos un tiempo total de procesamiento de 70 minutos aproximadamente, tiempo muy razonable y acotado, pues el término de vaciado de las cargas de pedidos de los vendedores culmina a mar tardar a las 21 hrs., por lo tanto, si el procesamiento de los datos demora el máximo de tiempo calculado anteriormente, los resultados para cargar los camiones no comenzaría mas alla de las 22:30 hrs., que es un tiempo bastante razonable y accesible para las operaciones actuales de cargado de camiones en la bodega de la empresa (este proceso de cargado demora alrededor de 4 hrs. (es realizado en turno de madrugada, de manera que los camiones cargados son retirados por los choferes alrededor de las 7:00 am.)

45

8.6 Propuesta de Sistema de Trabajo para Implementación de nueva herramienta de Programación

A continuación, se propone hacer una propuesta de los posibles sistemas de trabajo con su organigrama para la implementación de la herramienta propuesta: El sistema requiere de un equipo PC (Programación) de minimo 2 Ggbyte de RAM y 2,5 Ghz de velocidad con procesador matemático. El Sistema debiera funcionar de la siguiente manera: El Administrador del Sistema (puede ser el operador de programación actual) mensualmente revisa los parámetros del sistema, es decir la velocidad promedio de los camiones, la actualización de nuevos clientes con sus coordenadas y tiempos de ventana de atención, revisión de los tiempos de descarga y espera de cada cliente (debiera revisar al menos un conjunto no menor de 50 clientes al mes). Diariamente, luego de ingresado y validado los pedidos desde las hanheld de los vendedores al Computador Central, este último debe generar una planilla Excel que exportará al PC de Programación, con los datos de ingreso de pedidos para el día siguiente, tal como aparece en el punto 6.3. Posteriormente, el Administrador debe correr la aplicación en su computador, ingresando los parámetros de corrida (Nro. de clientes, Hora Inicio Despacho, Tiempo máximo jornada, capacidad camiones (cajas). Luego el programa de asignación de pedidos a camiones es entregado al Computador Central a través de una planilla Excel descrita también en el punto 6.3, de esta manera el Computador Central finalmente genera los voucher de carga para camiones hacia bodega. El Administrador en conjunto con el Jefe de Distribución deben hacer una labor de control y supervisión de cumplimiento de la secuencia de despacho establecida en el programa, de esta manera se valida la información de clientes (ventanas horarias, coordenadas del local, etc.) y además se supervisa a los choferes de los camiones en su labor. El sistema propuesto no provee una interfaz de indicadores pero se requiere llevar un control exhaustivo de los datos e indicadores de gestión relevantes: Cajas despachadas por camión-dia, Utilizacion del Camion (Cajas despachadas/Capacidad Cajas), Porcentaje de Rechazo por camión-dia, Kilometros recorridos por Camion-dia, Tiempos totales de jornada camión-dia (tomados por vigilancia a la salida y entrada de los camiones al final de la jornada), entre otros.

9 Conclusiones y Comentarios La alternativa propuesta es robusta, práctica y económicamente rentable. Es una herramienta sencilla e intuitiva, que logra resultados muy atractivos respecto de una situación base ó inicial bastante sencilla y que representa un valor alto de costo para la empresa actualmente. La alternativa de programar los clientes en secuencia sólo ordenados primero por la comuna (o grupo) y luego por el tipo de establecimiento, permite una serie de mejoras que la herramienta propuesta logra en forma rápida y precisa. Los ahorros obtenidos permiten bajar los costos actuales de las taerifas cancaladas a los transportistas a través de realizar nuevas negociaciones de los contratos bajando fuertemente sobretodo los costos variables de despacho por caja ($170 actuales). Esta baja puede llegar a un 25% de la actual tarifa, según lo calculado en el punto 7.1.4. algo parecido ocurre con el ahorro proveniente del menor desgaste de los camiones y que en el punto 7.1.4 se estimó aproximadamente en un 4%, lo que consolidado nos muestra un ahorro del 30% de la tarifa actual como potencial ahorro neto. Además se debe agregar a esto, los potenciales beneficios que puede traer el ahorro de tiempos en los despachos, que como vimos en el punto 7.1.3 ahorros que permitirían 1 o 2 horas más de despacho normal en cada camión-día. Lo anterior puede permitir un beneficio en venta adicional que represente equivalencia con un ahorro de costos variables del 12,5%. Lo anterior puede permitir un ahorro consolidado mes de alrededor del 30% en los costos de flete de la empresa en la Region Metropolitana (recordar que los costos de flete representan un 33% del costo total del producto) y lo que finalmente puede redundar en un ahorro del 10% en los costos operacionales de la empresa. Es una cifra bastante atractiva para un mercado muy competitivo y muy concentrado. Desde el punto de vista técnico, la herramienta muestra un muy buen desempeño respecto a los tiempos de procesamiento incluso con un cantidad de clientes para la cual la bibliografía utilizada no recomienda utilizar (sobre 100 clientes). En el caso mas extremo probado en le mes de estudio, 320 clientes para un grupo de comunas, la herramienta demoró un tiempo de 1.035 segundos (aproximadamente 18 minutos). Estos tiempos son bastante útiles y prácticos para la implementación de esta solución, pues debe coordinarse finalmente en la noche con la carga posterior de los camiones en Bodega (Ciclo Entrega Pedidos (fin 21 hrs.), Programación Heurística (fin 23 hrs.), carga camiones (04:00 am)). Las limitaciones de este sistema, tienen relación con la forma de cáluclo simplificada de las distancias entre clientes o entre clientes y bodega, se utiliza la distancia euclediana y esta distancia no calcula exactamente la distancia entre los puntos (y menos considera los transitos de la vía y las horas de congestion), y por ende los tiempos reales de viaje, sin embargo es una muy buena aproximación para esta primera etapa de sistema de ruteo.

47

Como conclusión final, el tesista sugiere la utilización de esta herramienta para ser aplicada en problemáticas que poseen las siguientes características:

- 1 depósito de entrada y salida de camiones - Menos de 350 clientes a programar - Ventanas de tiempo definidas por cliente - Capacidad de camiones homogénea - Jornada de trabajo fija y constante para camiones - Tiempo de descarga de cajas, tiempo de espera y tiempos de viaje conocidos por

cliente. Con estos requerimientos, la heurística planteada resuelvo problemas de mediana complejidad en tiempos razonables (< 2 hrs.) y con resultados muy robustos y atractivos.

10 Bibliografía [1] Dantzig, G.B.; Ramser, J.H. (1959). "The Truck Dispatching Problem". Management Science 6(1):80–91. [2] G.Clarke y J.M. Wright,”Scheduling of vehicles from a Central Depot to a Number of Delivery Points” (1964) [3] Heuristic Approches to vehicle routing with backhauls and time windows, Sam Thangiah, Jean Yves Potvin and Tong Sun, International Journal of Computers and O.Research, 2001 [4] Memoria de Título: Sistema de Programación de despacho para la empresa Gerdau Aza, Autor: Sr. Enzo Ravera, 2002. [5] Apuntes Cursos: Modelos y Algoritmos de Optimización y Logística y Producción [6] “The Vehicle Routing Problem”, Paolo Toth & Daniele Vigo, 2002

49

Anexo A Aplicación Heurística para Ruteo de Vehículos con restricción de Capacidad y clientes con ventanas de tiempo. Imports System.Math Public Class Form1 Inherits System.Windows.Forms.Form 'Public ConnStr = "Provider=SQLOLEDB.1;Password=sa;Persist Security Info=True;User ID=sa;Initial Catalog=RutaVehiculos;Data Source=matrix1;Application Name=Vehiculos;Connect Timeout=360" Public sRuta = Application.StartupPath Public ConnStr = "Provider=Microsoft.Jet.OLEDB.4.0;Data Source=" & sRuta & "\clientes.xls;Extended Properties=""Excel 8.0;HDR=YES;""" Public ConnAccess = "Provider=Microsoft.Jet.OLEDB.4.0;Data Source=" & sRuta & "\resultados.mdb" Friend WithEvents StatusStrip1 As System.Windows.Forms.StatusStrip Friend WithEvents ToolStripProgressBar1 As System.Windows.Forms.ToolStripProgressBar Friend WithEvents BW_ProgressBar As System.ComponentModel.BackgroundWorker Private m_NewValue As Integer = 0 Private m_BackThread_Stop As Boolean = False Private m_PB_Maximum As Integer = 100 Private m_ThreadTimer As Integer = 10 Private Delegate Sub UpdateProgressbarHandler(ByVal NewValue As Integer) Public vdata As Object #Region " Windows Form Designer generated code " Public Sub New() MyBase.New() 'This call is required by the Windows Form Designer. InitializeComponent() 'Add any initialization after the InitializeComponent() call End Sub 'Form overrides dispose to clean up the component list. Protected Overloads Overrides Sub Dispose(ByVal disposing As Boolean) If disposing Then If Not (components Is Nothing) Then components.Dispose()

End If End If MyBase.Dispose(disposing) End Sub 'Required by the Windows Form Designer Private components As System.ComponentModel.IContainer 'NOTE: The following procedure is required by the Windows Form Designer 'It can be modified using the Windows Form Designer. 'Do not modify it using the code editor. Friend WithEvents Button1 As System.Windows.Forms.Button Friend WithEvents Label1 As System.Windows.Forms.Label Friend WithEvents txt_nroclientes As System.Windows.Forms.TextBox Friend WithEvents Label2 As System.Windows.Forms.Label Friend WithEvents txt_capacidad As System.Windows.Forms.TextBox Friend WithEvents Label3 As System.Windows.Forms.Label Friend WithEvents txt_velocidad As System.Windows.Forms.TextBox Friend WithEvents txt_tiempoinicio As System.Windows.Forms.Label Friend WithEvents Label4 As System.Windows.Forms.Label Friend WithEvents txt_tiempomaximo As System.Windows.Forms.TextBox Friend WithEvents txt_tiempoini As System.Windows.Forms.TextBox Friend WithEvents Label5 As System.Windows.Forms.Label Friend WithEvents Label6 As System.Windows.Forms.Label Friend WithEvents txtinicio As System.Windows.Forms.TextBox Friend WithEvents txttermino As System.Windows.Forms.TextBox <System.Diagnostics.DebuggerStepThrough()> Private Sub InitializeComponent() Me.Button1 = New System.Windows.Forms.Button Me.Label1 = New System.Windows.Forms.Label Me.txt_nroclientes = New System.Windows.Forms.TextBox Me.Label2 = New System.Windows.Forms.Label Me.txt_capacidad = New System.Windows.Forms.TextBox Me.Label3 = New System.Windows.Forms.Label Me.txt_velocidad = New System.Windows.Forms.TextBox Me.txt_tiempoinicio = New System.Windows.Forms.Label Me.txt_tiempoini = New System.Windows.Forms.TextBox Me.Label4 = New System.Windows.Forms.Label Me.txt_tiempomaximo = New System.Windows.Forms.TextBox Me.Label5 = New System.Windows.Forms.Label Me.Label6 = New System.Windows.Forms.Label Me.txtinicio = New System.Windows.Forms.TextBox Me.txttermino = New System.Windows.Forms.TextBox Me.StatusStrip1 = New System.Windows.Forms.StatusStrip Me.ToolStripProgressBar1 = New System.Windows.Forms.ToolStripProgressBar Me.BW_ProgressBar = New System.ComponentModel.BackgroundWorker Me.StatusStrip1.SuspendLayout() Me.SuspendLayout() ' 'Button1 '

51

Me.Button1.BackColor = System.Drawing.SystemColors.Desktop Me.Button1.ForeColor = System.Drawing.SystemColors.ControlLightLight Me.Button1.Location = New System.Drawing.Point(112, 216) Me.Button1.Name = "Button1" Me.Button1.Size = New System.Drawing.Size(152, 23) Me.Button1.TabIndex = 0 Me.Button1.Text = "Ejecutar" Me.Button1.UseVisualStyleBackColor = False ' 'Label1 ' Me.Label1.Location = New System.Drawing.Point(8, 15) Me.Label1.Name = "Label1" Me.Label1.Size = New System.Drawing.Size(100, 16) Me.Label1.TabIndex = 1 Me.Label1.Text = "Nro Clientes :" ' 'txt_nroclientes ' Me.txt_nroclientes.Location = New System.Drawing.Point(104, 11) Me.txt_nroclientes.Name = "txt_nroclientes" Me.txt_nroclientes.Size = New System.Drawing.Size(100, 20) Me.txt_nroclientes.TabIndex = 2 Me.txt_nroclientes.Text = "0" ' 'Label2 ' Me.Label2.Location = New System.Drawing.Point(8, 38) Me.Label2.Name = "Label2" Me.Label2.Size = New System.Drawing.Size(64, 23) Me.Label2.TabIndex = 3 Me.Label2.Text = "Capacidad :" ' 'txt_capacidad ' Me.txt_capacidad.Location = New System.Drawing.Point(104, 38) Me.txt_capacidad.Name = "txt_capacidad" Me.txt_capacidad.Size = New System.Drawing.Size(100, 20) Me.txt_capacidad.TabIndex = 4 Me.txt_capacidad.Text = "500" ' 'Label3 ' Me.Label3.Location = New System.Drawing.Point(8, 64) Me.Label3.Name = "Label3" Me.Label3.Size = New System.Drawing.Size(100, 23) Me.Label3.TabIndex = 5 Me.Label3.Text = "Velocidad :" ' 'txt_velocidad

' Me.txt_velocidad.Location = New System.Drawing.Point(104, 63) Me.txt_velocidad.Name = "txt_velocidad" Me.txt_velocidad.Size = New System.Drawing.Size(100, 20) Me.txt_velocidad.TabIndex = 6 Me.txt_velocidad.Text = "40" ' 'txt_tiempoinicio ' Me.txt_tiempoinicio.Location = New System.Drawing.Point(8, 88) Me.txt_tiempoinicio.Name = "txt_tiempoinicio" Me.txt_tiempoinicio.Size = New System.Drawing.Size(100, 23) Me.txt_tiempoinicio.TabIndex = 7 Me.txt_tiempoinicio.Text = "Tiempo Inicio :" ' 'txt_tiempoini ' Me.txt_tiempoini.Location = New System.Drawing.Point(104, 87) Me.txt_tiempoini.Name = "txt_tiempoini" Me.txt_tiempoini.Size = New System.Drawing.Size(100, 20) Me.txt_tiempoini.TabIndex = 8 Me.txt_tiempoini.Text = "0" ' 'Label4 ' Me.Label4.Location = New System.Drawing.Point(8, 112) Me.Label4.Name = "Label4" Me.Label4.Size = New System.Drawing.Size(88, 23) Me.Label4.TabIndex = 9 Me.Label4.Text = "Tiempo Máximo" ' 'txt_tiempomaximo ' Me.txt_tiempomaximo.Location = New System.Drawing.Point(104, 112) Me.txt_tiempomaximo.Name = "txt_tiempomaximo" Me.txt_tiempomaximo.Size = New System.Drawing.Size(100, 20) Me.txt_tiempomaximo.TabIndex = 10 Me.txt_tiempomaximo.Text = "14" ' 'Label5 ' Me.Label5.Location = New System.Drawing.Point(32, 152) Me.Label5.Name = "Label5" Me.Label5.Size = New System.Drawing.Size(100, 23) Me.Label5.TabIndex = 11 Me.Label5.Text = "Inicio" ' 'Label6 ' Me.Label6.Location = New System.Drawing.Point(32, 176)

53

Me.Label6.Name = "Label6" Me.Label6.Size = New System.Drawing.Size(100, 23) Me.Label6.TabIndex = 12 Me.Label6.Text = "Termino" ' 'txtinicio ' Me.txtinicio.Location = New System.Drawing.Point(136, 152) Me.txtinicio.Name = "txtinicio" Me.txtinicio.Size = New System.Drawing.Size(88, 20) Me.txtinicio.TabIndex = 13 ' 'txttermino ' Me.txttermino.Location = New System.Drawing.Point(136, 176) Me.txttermino.Name = "txttermino" Me.txttermino.Size = New System.Drawing.Size(88, 20) Me.txttermino.TabIndex = 14 ' 'StatusStrip1 ' Me.StatusStrip1.Items.AddRange(New System.Windows.Forms.ToolStripItem() {Me.ToolStripProgressBar1}) Me.StatusStrip1.Location = New System.Drawing.Point(0, 304) Me.StatusStrip1.Name = "StatusStrip1" Me.StatusStrip1.Size = New System.Drawing.Size(376, 22) Me.StatusStrip1.TabIndex = 15 Me.StatusStrip1.Text = "StatusStrip1" ' 'ToolStripProgressBar1 ' Me.ToolStripProgressBar1.ForeColor = System.Drawing.Color.YellowGreen Me.ToolStripProgressBar1.Name = "ToolStripProgressBar1" Me.ToolStripProgressBar1.Size = New System.Drawing.Size(225, 16) ' 'Form1 ' Me.AutoScaleBaseSize = New System.Drawing.Size(5, 13) Me.ClientSize = New System.Drawing.Size(376, 326) Me.Controls.Add(Me.StatusStrip1) Me.Controls.Add(Me.txttermino) Me.Controls.Add(Me.txtinicio) Me.Controls.Add(Me.Label6) Me.Controls.Add(Me.Label5) Me.Controls.Add(Me.txt_tiempomaximo) Me.Controls.Add(Me.Label4) Me.Controls.Add(Me.txt_tiempoini) Me.Controls.Add(Me.txt_tiempoinicio) Me.Controls.Add(Me.txt_velocidad) Me.Controls.Add(Me.Label3)

Me.Controls.Add(Me.txt_capacidad) Me.Controls.Add(Me.Label2) Me.Controls.Add(Me.txt_nroclientes) Me.Controls.Add(Me.Label1) Me.Controls.Add(Me.Button1) Me.Name = "Form1" Me.RightToLeft = System.Windows.Forms.RightToLeft.No Me.StartPosition = System.Windows.Forms.FormStartPosition.CenterScreen Me.Text = "Proceso de Cálculo" Me.TransparencyKey = System.Drawing.Color.FromArgb(CType(CType(224, Byte), Integer), CType(CType(224, Byte), Integer), CType(CType(224, Byte), Integer)) Me.StatusStrip1.ResumeLayout(False) Me.StatusStrip1.PerformLayout() Me.ResumeLayout(False) Me.PerformLayout() End Sub #End Region Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click Dim iRetSearch, x, ObtieneDatos, GrabaDatos As Integer Dim sSql As String 'Dim vdata As Object Dim objCoa As COA_Access.AccessDB objCoa = New COA_Access.AccessDB txtinicio.Text = "" txttermino.Text = "" Me.Refresh() Application.DoEvents() Me.Refresh() Try If BW_ProgressBar.IsBusy = False Then m_BackThread_Stop = False BW_ProgressBar.RunWorkerAsync() End If Catch ex As Exception BW_ProgressBar.CancelAsync() BW_ProgressBar.Dispose() End Try Me.Refresh() Application.DoEvents() Application.EnableVisualStyles()

55

Me.Refresh() sSql = "SELECT id_Cliente, cod_cliente, pos_x, pox_y, demanda, tpo_descarga, tpo_espera, tpo_min, tpo_max FROM [DatosCliente$]" ObtieneDatos = objCoa.ExecuteSql_Records(sSql, vdata, ConnStr) 'vdata(0,x) = id_cliente 'vdata(1,x) = cod_cliente 'vdata(2,x) = pos_x 'vdata(3,x) = pox_y 'vdata(4,x) = demanda 'vdata(5,x) = tpo_descarga 'vdata(6,x) = tpo_espera 'vdata(7,x) = tpo_min 'vdata(8,x) = tpo_max txtinicio.Text = Hour(Now()) & ":" & Minute(Now()) & ":" & Second(Now()) Call Principal() Dim sValor, sSQL1, sSQlfinal As String Dim sValorAlpha, sSQLAlpha, sSQL1Alpha, sSQlfinalAlpha As String Dim sValorBeta, sSQLBeta, sSQL1Beta, sSQlfinalBeta As String 'sSql = "UPDATE [Resultados$] set ruta1=0,ruta2=0, ruta3=0,ruta4=0,ruta5=0" 'GrabaDatos = objCoa.ExecuteSql_NoRecordsRS(sSql, ConnStr) sSql = "DELETE FROM [Resultados] " GrabaDatos = objCoa.ExecuteSql_NoRecordsRS(sSql, ConnAccess) sSql = "DELETE FROM [ResultadosAlpha] " GrabaDatos = objCoa.ExecuteSql_NoRecordsRS(sSql, ConnAccess) sSql = "DELETE FROM [ResultadosBeta] " GrabaDatos = objCoa.ExecuteSql_NoRecordsRS(sSql, ConnAccess) For b = 0 To num_clientes + 1 sSQL1 = "INSERT INTO [Resultados] (" sValor = "" sSql = "" sSQL1Alpha = "INSERT INTO [ResultadosAlpha] (" sValorAlpha = "" sSQLAlpha = "" sSQL1Beta = "INSERT INTO [ResultadosBeta] (" sValorBeta = ""

sSQLBeta = "" For a = 1 To k sValor = sValor & "ruta" & CStr(a) & "," sSql = sSql & solfact(a, b) & "," sValorAlpha = sValorAlpha & "ruta" & CStr(a) & "," sSQLAlpha = sSQLAlpha & fact(a, b) & "," sValorBeta = sValorBeta & "ruta" & CStr(a) & "," sSQLBeta = sSQLBeta & alt_nva(a, b) & "," ' ActiveSheet.Cells(b + 150, 10 + a) = fact(a, b) ''' ActiveSheet.Cells(b + 150, 10 + k + a) = alt_nva(a, b) ''' ActiveSheet.Cells(b + 150, 10 + 2 * k + a) = solfact(a, b) Next a sValor = Mid(sValor, 1, Len(sValor) - 1) & ")" sValorAlpha = Mid(sValorAlpha, 1, Len(sValorAlpha) - 1) & ")" sValorBeta = Mid(sValorBeta, 1, Len(sValorBeta) - 1) & ")" sSql = Mid(sSql, 1, Len(sSql) - 1) & ")" sSQlfinal = sSQL1 & sValor & " values (" & sSql GrabaDatos = objCoa.ExecuteSql_NoRecordsRS(sSQlfinal, ConnAccess) sSQLAlpha = Mid(sSQLAlpha, 1, Len(sSQLAlpha) - 1) & ")" sSQlfinalAlpha = sSQL1Alpha & sValorAlpha & " values (" & sSQLAlpha GrabaDatos = objCoa.ExecuteSql_NoRecordsRS(sSQlfinalAlpha, ConnAccess) sSQLBeta = Mid(sSQLBeta, 1, Len(sSQLBeta) - 1) & ")" sSQlfinalBeta = sSQL1Beta & sValorBeta & " values (" & sSQLBeta GrabaDatos = objCoa.ExecuteSql_NoRecordsRS(sSQlfinalBeta, ConnAccess) Next b 'For x = 0 To UBound(solfact, 2) ' sSql = "DELETE FROM [Resultados$]" 'sSql = "INSERT INTO [Resultados$] values (1,2,3,4,10)" 'GrabaDatos = objCoa.ExecuteSql_NoRecordsRS(sSql, ConnStr) 'Next objCoa = Nothing txttermino.Text = Hour(Now()) & ":" & Minute(Now()) & ":" & Second(Now()) MsgBox("fin")

57

m_BackThread_Stop = True BW_ProgressBar.CancelAsync() ToolStripProgressBar1.Value = 0 End Sub Public Clientes_pos(0, 0) As Double Public Clientes_tpos(0, 0) As Double Public Clientes_ventana(0, 0) As Double Public Demanda() As Integer Public Distancia(0, 0) As Double Public Tiempo_viaje(0, 0) As Double Public angulo(0, 0) As Double Public capacidad As Integer Public ubica As Double Public a As Integer Public cont_may As Integer Public b As Integer Public i As Integer Public u As Integer Public X As Integer Public Y As Integer Public m As Integer Public pp As Integer Public cont As Single Public cont11 As Single Public cont12 As Single Public cont21 As Single Public cont22 As Single Public cont31 As Single Public cont32 As Single Public cont41 As Single Public cont42 As Single Public cont51 As Single Public cont52 As Single Public cont61 As Single Public cont62 As Single Public cont71 As Single Public cont72 As Single Public cont81 As Single Public cont82 As Single Public j As Integer Public p As Integer Public w As Integer Public s As Integer

Public r As Integer Public v As Integer Public q As Integer Public Infact As Double Public Infact_rest As Double Public pivote As Integer Public pivote1, pivote2, pivote3, pivote4, pivot1, pivot2, pivot3, pivot4, pivot5 As Integer Public contador As Integer Public ultimo_f() As Integer Public ultimo_f2() As Integer Public ultimo_a() As Integer Public ultimo_a2() As Integer Public ultimo_a_nva() As Integer Public ultimo_a_nva2() As Integer Public solinic(0, 0) As Double Public solfact(0, 0) As Double Public solfact_2(0, 0) As Double Public fact(0, 0) As Double Public fact_2(0, 0) As Double Public alt(0, 0) As Double Public alt_2(0, 0) As Double Public alt_nva(0, 0) As Double Public alt_nva_2(0, 0) As Double Public costo_minimo As Double Public costo_fact As Double Public costo_alt As Double Public costo_alt_rest As Double Public termino As Boolean Public nva_alt As Boolean Public rest_rut_mayor As Boolean Public carga As Integer Public costo_mejora As Double Public exceso_tpo As Double Public ww As Double Public zz As Double Public k As Integer Public velocidad As Integer Public tm As Double Public t_ini As Double Public inicio As Long Public fin As Double Public fin2 As Double Public finales As Boolean Public t As Integer Public cai As Integer Public ncnr As Integer

59

Public pos As Integer Public costo_semilla_min As Double Public costo_min As Double Public costo_insercion As Double Public min_costo_ins As Double Public fact_cap As Boolean Public cte_inserto As Integer Public pto_ins As Integer Public puesto_insercion As Integer Public cliente_inserto As Integer Public suma_cajas As Integer Public tpo_inicial As Double Public tpo_final As Double Public tpo_inicio As Double Public tpo_viaje As Double Public tpo_fin As Double Public longitud As Double Public tpo_maximo As Double Public tpo_descarga As Double Public tpo_espera As Double Public indice As Integer Public semilla() As Integer Public capac_cam As Boolean Public tpo_excedido As Boolean Public num_clientes As Integer Public cro() As Integer Public cr() As Integer Public crut As Integer Public cnr() As Integer Public costo() As Double Public ruta(0, 0) As Integer Public total_clientes As Integer Public gg, kk, ss, rr, n, aa, bb, cc, tt, dd, ee, xx, aux, aux1, aux2, aux5, tz, tu, ff, tv, tw, ilargo As Integer Public Sub Principal() ubica = 0 'inicio = Hour(Now()) capacidad = txt_capacidad.Text velocidad = txt_velocidad.Text num_clientes = txt_nroclientes.Text total_clientes = num_clientes + 1 tm = txt_tiempomaximo.Text tpo_maximo = tm * CLng(3600) cont_may = 0

t_ini = txt_tiempoini.Text tpo_inicio = t_ini * CLng(3600) ReDim Clientes_pos(total_clientes, 2) ReDim Clientes_tpos(total_clientes, 2) ReDim Clientes_ventana(total_clientes, 2) ReDim Demanda(total_clientes) ReDim Distancia(total_clientes, total_clientes) ReDim Tiempo_viaje(total_clientes, total_clientes) ReDim angulo(total_clientes, total_clientes) ReDim costo(num_clientes + 2) ReDim cro(num_clientes + 2) ReDim cnr(num_clientes + 2) ReDim cr(num_clientes + 2) ReDim ruta(total_clientes, total_clientes) ReDim costo(total_clientes) ReDim semilla(num_clientes) ReDim ultimo_f(total_clientes) ReDim ultimo_f2(total_clientes) ReDim ultimo_a(total_clientes) ReDim ultimo_a2(total_clientes) ReDim ultimo_a_nva(total_clientes) ReDim ultimo_a_nva2(total_clientes) ReDim fact(total_clientes, num_clientes + 2) ReDim solinic(total_clientes, total_clientes) ReDim solfact(total_clientes, total_clientes) ReDim solfact_2(total_clientes, total_clientes) ReDim alt(total_clientes, total_clientes) ReDim alt_nva(total_clientes, num_clientes + 3) ReDim fact_2(total_clientes, total_clientes) ReDim alt_2(total_clientes, total_clientes) ReDim alt_nva_2(total_clientes, total_clientes) Dim z As Integer z = 0 For i = 1 To total_clientes Clientes_pos(i, 1) = vdata(2, z) 'posx Clientes_pos(i, 2) = vdata(3, z) 'posy Clientes_tpos(i, 1) = vdata(5, z) 'tpo_descarga Clientes_tpos(i, 2) = vdata(6, z) ' tpo_espera Clientes_ventana(i, 1) = vdata(7, z) 'tpo_min Clientes_ventana(i, 2) = vdata(8, z) 'tpo_max Demanda(i) = vdata(4, z) 'demanda z += 1 Next i

61

'vdata(0,x) = id_cliente 'vdata(1,x) = cod_cliente 'vdata(2,x) = pos_x 'vdata(3,x) = pox_y 'vdata(4,x) = demanda 'vdata(5,x) = tpo_descarga 'vdata(6,x) = tpo_espera 'vdata(7,x) = tpo_min 'vdata(8,x) = tpo_max For i = 1 To total_clientes For j = 1 To total_clientes 'inicializar matriz ruta con 0 ruta(i, j) = 0 If i = j Then Distancia(i, j) = 0 Tiempo_viaje(i, j) = 0 angulo(i, j) = 0 Else Distancia(i, j) = Sqrt((Clientes_pos(i, 1) - Clientes_pos(j, 1)) ^ 2 + ((Clientes_pos(i, 2) - Clientes_pos(j, 2)) ^ 2)) Tiempo_viaje(i, j) = (Distancia(i, j) / velocidad) * 3600 If i = 1 Then For u = 2 To total_clientes X = Clientes_pos(u, 1) - Clientes_pos(1, 1) Y = Clientes_pos(u, 2) - Clientes_pos(1, 2) If X >= 0 AndAlso Y = 0 Then angulo(1, u) = 0 End If If X > 0 AndAlso Y > 0 Then angulo(1, u) = (Atan(Y / X) * 180 / 3.14159265358979) End If If X = 0 AndAlso Y >= 0 Then angulo(1, u) = 90 End If If X < 0 AndAlso Y > 0 Then angulo(1, u) = 180 + (Atan(Y / X) * 180 / 3.14159265358979) End If If X < 0 AndAlso Y = 0 Then angulo(1, u) = 180 End If If X < 0 AndAlso Y < 0 Then angulo(1, u) = 180 + (Atan(Y / X) * 180 / 3.14159265358979) End If If X = 0 AndAlso Y < 0 Then angulo(1, u) = 270 End If If X > 0 AndAlso Y < 0 Then angulo(1, u) = 360 + (Atan(Y / X) * 180 / 3.14159265358979) End If

Next u Else If angulo(1, j) < angulo(1, i) Then angulo(i, j) = 360 + angulo(1, j) - angulo(1, i) Else angulo(i, j) = angulo(1, j) - angulo(1, i) End If End If End If Next j Next i ncnr = num_clientes For i = 1 To total_clientes cr(i) = 0 cnr(i) = 1 Next i cnr(num_clientes + 2) = -1 t = 1 k = 1 crut = num_clientes - ncnr + 1 cr(1) = 1 : cnr(1) = 0 Do While ncnr > 0 costo_semilla_min = 9.0E+99 ruta(k, 1) = 1 pos = 2 j = 1 Do While cnr(j) >= 0 '(Elijo cliente semilla) If cnr(j) <> 0 Then If j = 1 Then costo(1) = 9.0E+99 End If costo(j) = -0.7 * Distancia(1, j) + 0.2 * Clientes_ventana(j, 2) + 0.1 * angulo(t, j) suma_cajas = Demanda(j) tpo_viaje = Tiempo_viaje(1, j) tpo_espera = Clientes_tpos(j, 2) tpo_descarga = Clientes_tpos(j, 1) * Demanda(j) tpo_final = tpo_inicio + tpo_viaje + tpo_espera + tpo_descarga If costo(j) < costo_semilla_min AndAlso suma_cajas <= capacidad AndAlso tpo_final < Clientes_ventana(j, 2) Then costo_semilla_min = costo(j) semilla(k) = j indice = j End If j += 1

63

Else j += 1 End If Loop ruta(k, semilla(k)) = pos crut += 1 ncnr -= 1 cnr(indice) = 0 cr(semilla(k)) = 1 'total va sumando la cantidad de clientes ruteados capac_cam = True 'calcula insercion a ruta t = semilla(k) Do While capac_cam = True AndAlso ncnr > 0 costo_min = 9.0E+99 j = 1 cte_inserto = 0 pto_ins = 0 Do While cnr(j) >= 0 'busco cliente con min costo a insertar en ruta k If cnr(j) <> 0 Then cai = j Call Busca_min_costo_factible_insercion() 'para cliente cai If min_costo_ins < costo_min Then costo_min = min_costo_ins pto_ins = puesto_insercion cte_inserto = cliente_inserto End If End If j += 1 Loop If cte_inserto <> 0 Then pos += 1 If pos >= pto_ins + 1 Then For j = pos To pto_ins + 1 Step -1 cro(j) = cro(j - 1) Next j cro(pto_ins) = cte_inserto Else cro(pto_ins) = cte_inserto End If cr(cte_inserto) = 1 : cnr(cte_inserto) = 0 t = cte_inserto 'ultimo cliente ruteado de ruta anterior (para calculo de angulo en cliente semilla nueva ruta ncnr -= 1 crut += 1 For u = 1 To pos If u < pto_ins Then

ruta(k, cro(u)) = u End If If u = pto_ins Then ruta(k, cte_inserto) = pto_ins End If If u > pto_ins Then ruta(k, cro(u)) = u End If Next u Else capac_cam = False End If Loop If ncnr > 0 Then k += 1 'se acabo la ruta k y se incrementa en 1 For u = 1 To total_clientes cro(u) = 0 Next u Else 'se terminaron clientes End If Loop 'Sheets("Hoja1").Activate() 'For i = 1 To k ' For j = 1 To total_clientes ' ActiveSheet.Cells(j + 2, 12 + i) = ruta(i, j) ' Next j 'Next i 'fin = Hour(Now()) 'Sheets("Hoja1").Range("A150") = fin - inicio ' aqui termina la parte solucion inicial factible ' aqui comienza la mejora de solucion segun Lambda interchange contador = 1

65

For i = 1 To k ultimo_f(i) = 0 ultimo_a(i) = 0 ultimo_a_nva(i) = 0 For j = 1 To total_clientes If ruta(i, j) <> 0 Then solinic(i, ruta(i, j)) = j solfact(i, ruta(i, j)) = j fact(i, ruta(i, j)) = j alt(i, ruta(i, j)) = j alt_nva(i, ruta(i, j)) = j If ruta(i, j) > ultimo_f(i) Then ultimo_f(i) = ruta(i, j) ultimo_a(i) = ruta(i, j) ultimo_a_nva(i) = ruta(i, j) End If End If Next j Next i For i = 1 To k fact(i, num_clientes + 2) = -1 Next i 'gg = 1 Call calcula_costo() costo_minimo = costo_fact For i = 1 To k alt(i, 0) = fact(i, 0) alt_nva(i, 0) = fact(i, 0) solfact(i, 0) = fact(i, 0) Next i 'Cálculo de rutas a comparar contador = 2 termino = False cont11 = 0 cont12 = 0 cont21 = 0 cont22 = 0 cont31 = 0 cont32 = 0 cont41 = 0 cont42 = 0 cont51 = 0 cont52 = 0 cont61 = 0 cont62 = 0 cont71 = 0

cont72 = 0 cont81 = 0 cont82 = 0 kk = 0 Do While termino = False nva_alt = False For i = k To 1 Step -1 If nva_alt = True Then Exit For End If For j = i - 1 To 1 Step -1 If nva_alt = True Then Exit For End If For p = 1 To 8 If costo_minimo < 290000 Then gg = 1 End If If nva_alt = True Then Exit For End If If p = 1 Then If ultimo_a_nva(j) >= 2 Then 'ww = Hour(Now()) '''cont11 += 1 Call Operador1() If nva_alt = True Then gg = 1 kk += 1 For rr = 1 To k For ss = 1 To total_clientes ''' ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss, 55 + rr) = alt_nva(rr, ss) Next ss Next rr 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr) = costo_alt 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 1) = p 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 2) = i 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 3) = j

67

'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 4) = Infact 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 5) = ubica End If 'zz = Hour(Now()) 'cont12 += zz - ww End If End If If p = 2 Then If ultimo_a_nva(i) >= 2 Then 'ww = Hour(Now()) '''cont21 += 1 Call Operador2() If nva_alt = True Then gg = 1 kk += 1 For rr = 1 To k For ss = 1 To total_clientes '''ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss, 55 + rr) = alt_nva(rr, ss) Next ss Next rr 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr) = costo_alt 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 1) = p 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 2) = i 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 3) = j 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 4) = Infact 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 5) = ubica End If 'zz = Hour(Now()) '''cont22 += zz - ww End If End If If p = 3 Then If ultimo_a_nva(i) >= 2 AndAlso ultimo_a_nva(j) >= 2 Then 'ww = Hour(Now()) '''cont31 += 1 Call Operador3() If nva_alt = True Then gg = 1 kk += 1

For rr = 1 To k For ss = 1 To total_clientes ''' ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss, 55 + rr) = alt_nva(rr, ss) Next ss Next rr 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr) = costo_alt 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 1) = p 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 2) = i 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 3) = j 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 4) = Infact 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 5) = ubica End If 'zz = Hour(Now()) '''cont32 += zz - ww End If End If If p = 4 Then If ultimo_a_nva(j) >= 4 Then 'ww = Hour(Now()) '''cont41 += 1 Call Operador4() If nva_alt = True Then gg = 1 kk += 1 For rr = 1 To k For ss = 1 To total_clientes '''ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss, 55 + rr) = alt_nva(rr, ss) Next ss Next rr 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr) = costo_alt 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 1) = p 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 2) = i 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 3) = j 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 4) = Infact 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 5) = ubica

69

End If 'zz = Hour(Now()) '''cont42 += zz - ww End If End If If p = 5 Then If ultimo_a_nva(i) >= 4 Then 'ww = Hour(Now()) '''cont51 += 1 Call Operador5() If nva_alt = True Then gg = 1 kk += 1 For rr = 1 To k For ss = 1 To total_clientes '''ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss, 55 + rr) = alt_nva(rr, ss) Next ss Next rr 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr) = costo_alt 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 1) = p 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 2) = i 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 3) = j 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 4) = Infact 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 5) = ubica End If 'zz = Hour(Now()) '''cont52 += zz - ww End If End If If p = 6 Then If (ultimo_a_nva(i) >= 2 AndAlso ultimo_a_nva(j) >= 3) Then 'ww = Hour(Now()) '''cont61 += 1 Call Operador6() If nva_alt = True Then gg = 1 kk += 1 For rr = 1 To k For ss = 1 To total_clientes ''' ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss, 55 + rr) = alt_nva(rr, ss)

Next ss Next rr 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr) = costo_alt 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 1) = p 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 2) = i 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 3) = j 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 4) = Infact 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 5) = ubica End If 'zz = Hour(Now()) '''cont62 += zz - ww End If End If If p = 7 Then 'gg = 1 If (ultimo_a_nva(j) >= 2 AndAlso ultimo_a_nva(i) >= 3) Then 'ww = Hour(Now()) '''cont71 += 1 Call Operador7() If nva_alt = True Then gg = 1 kk += 1 For rr = 1 To k For ss = 1 To total_clientes '''ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss, 55 + rr) = alt_nva(rr, ss) Next ss Next rr 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr) = costo_alt 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 1) = p 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 2) = i 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 3) = j 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 4) = Infact 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 5) = ubica End If 'zz = Hour(Now()) '''cont72 += zz - ww

71

End If End If If p = 8 Then 'gg = 1 If (ultimo_a_nva(i) >= 3 AndAlso ultimo_a_nva(j) >= 4) OrElse (ultimo_a_nva(i) >= 4 AndAlso ultimo_a_nva(j) >= 3) Then 'ww = Hour(Now()) '''cont81 += 1 Call Operador8() If nva_alt = True Then gg = 1 kk += 1 For rr = 1 To k For ss = 1 To total_clientes ''' ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss, 55 + rr) = alt_nva(rr, ss) Next ss Next rr 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr) = costo_alt 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 1) = p 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 2) = i 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 3) = j 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 4) = Infact 'ActiveSheet.Cells(16 + (num_clientes + 1) * (kk - 1) + ss - 1, 55 + rr + 5) = ubica End If 'zz = Hour(Now()) '''cont82 += zz - ww If j = 2 AndAlso i = 1 Then gg = 1 End If End If End If Next p Next j Next i 'termino = True If nva_alt = False Then termino = True End If Loop '''ActiveSheet.Cells(3, 12) = costo_fact

'''For a = 1 To k ''' For b = 0 To num_clientes + 1 ''' ActiveSheet.Cells(b + 150, 10 + a) = fact(a, b) ''' ActiveSheet.Cells(b + 150, 10 + k + a) = alt_nva(a, b) ''' ActiveSheet.Cells(b + 150, 10 + 2 * k + a) = solfact(a, b) ''' Next b '''Next a '''If fact(1, num_clientes + 2) = -2 Then ''' ActiveSheet.Cells(158, 2) = "Infactible" '''Else ''' ActiveSheet.Cells(158, 2) = "Factible" '''End If 'fin2 = Hour(Now()) '''Sheets("Hoja1").Range("A152") = fin2 - inicio ' aqui termina la parte solucion inicial factible gg = 1 'MsgBox("fin" & fin2) End Sub Public Sub Busca_min_costo_factible_insercion() For i = 1 To total_clientes If ruta(k, i) > 0 Then cro(ruta(k, i)) = i End If Next i min_costo_ins = 9.0E+99 fact_cap = True For m = 2 To pos + 1 If fact_cap = True Then 'calcula costo insercion con cliente nr en cada posicion posible tpo_fin = tpo_inicio tpo_excedido = False longitud = 0 For n = 2 To pos + 1 If tpo_excedido = False Then If n = m Then tpo_fin += Tiempo_viaje(cro(n - 1), cai) + Clientes_tpos(cai, 1) * Demanda(cai) + Clientes_tpos(cai, 2) If tpo_fin < Clientes_ventana(cai, 1) Then

73

tpo_fin = Clientes_ventana(cai, 1) End If If tpo_fin > Clientes_ventana(cai, 2) OrElse tpo_fin - tpo_inicio > tpo_maximo Then tpo_excedido = True Else longitud += Distancia(cro(n - 1), cai) End If End If If n = m + 1 Then tpo_fin += Tiempo_viaje(cai, cro(n - 1)) + Clientes_tpos(cro(n - 1), 1) * Demanda(cro(n - 1)) + Clientes_tpos(cro(n - 1), 2) If tpo_fin < Clientes_ventana(cro(n - 1), 1) Then tpo_fin = Clientes_ventana(cro(n - 1), 1) End If If tpo_fin > Clientes_ventana(cro(n - 1), 2) OrElse tpo_fin - tpo_inicio > tpo_maximo Then tpo_excedido = True Else longitud += Distancia(cai, cro(n - 1)) End If End If If n > m + 1 Then tpo_fin += Tiempo_viaje(cro(n - 2), cro(n - 1)) + Clientes_tpos(cro(n - 1), 1) * Demanda(cro(n - 1)) + Clientes_tpos(cro(n - 1), 2) If tpo_fin < Clientes_ventana(cro(n - 1), 1) Then tpo_fin = Clientes_ventana(cro(n - 1), 1) End If If tpo_fin > Clientes_ventana(cro(n - 1), 2) OrElse tpo_fin - tpo_inicio > tpo_maximo Then tpo_excedido = True Else longitud += Distancia(cro(n - 2), cro(n - 1)) End If End If If n < m Then tpo_fin += Tiempo_viaje(cro(n - 1), cro(n)) + Clientes_tpos(cro(n), 1) * Demanda(cro(n)) + Clientes_tpos(cro(n), 2) If tpo_fin < Clientes_ventana(cro(n), 1) Then tpo_fin = Clientes_ventana(cro(n), 1) End If If tpo_fin > Clientes_ventana(cro(n), 2) OrElse tpo_fin - tpo_inicio > tpo_maximo Then tpo_excedido = True Else longitud += Distancia(cro(n - 1), cro(n)) End If End If End If If n = pos + 1 AndAlso tpo_excedido = False Then

If m = pos + 1 Then tpo_fin += Tiempo_viaje(cai, 1) End If If m <= pos Then tpo_fin += Tiempo_viaje(cro(n - 1), 1) End If If tpo_fin > Clientes_ventana(1, 2) OrElse tpo_fin - tpo_inicio > tpo_maximo Then tpo_excedido = True Else If m = pos + 1 Then longitud += Distancia(cai, 1) End If If m <= pos Then longitud += Distancia(cro(n - 1), 1) End If End If End If Next n suma_cajas = 0 : fact_cap = True If tpo_excedido = False Then For aux = 1 To pos suma_cajas += Demanda(cro(aux)) Next aux suma_cajas += Demanda(cai) If suma_cajas <= capacidad Then 'combinacion factible 'calcula costo de ruta factible costo_insercion = longitud + 0.01 * longitud * (tpo_fin - tpo_inicio) If costo_insercion < min_costo_ins Then min_costo_ins = costo_insercion puesto_insercion = m cliente_inserto = cai End If Else fact_cap = False End If End If 'no hay insercion factible en cuanto a ventanas de tiempo End If Next m If tpo_excedido = True OrElse fact_cap = False Then 'no sirve cliente cai , es infactible min_costo_ins = 9.0E+99 End If End Sub Public Sub calcula_costo() Dim ilargo As Integer ubica += 1

75

'If ubica = 3511241 Then ' gg = 1 'End If 'calculo costo lambda interchange de rutas alternativas e inicial If contador = 1 Then costo_fact = 0 For a = 1 To k costo_mejora = 0 exceso_tpo = 0 tpo_fin = tpo_inicio longitud = 0 carga = 0 ilargo = (ultimo_f(a) - 1) For b = 1 To ilargo tpo_fin += Tiempo_viaje(fact(a, b), fact(a, b + 1)) + Clientes_tpos(fact(a, b + 1), 1) * Demanda(fact(a, b + 1)) + Clientes_tpos(fact(a, b + 1), 2) exceso_tpo += (Abs(tpo_fin - Clientes_ventana(fact(a, b + 1), 2)) + (tpo_fin - Clientes_ventana(fact(a, b + 1), 2))) / 2 longitud += Distancia(fact(a, b), fact(a, b + 1)) carga += Demanda(fact(a, b + 1)) Next b longitud += Distancia(fact(a, ultimo_f(a)), 1) tpo_fin += Tiempo_viaje(fact(a, ultimo_f(a)), 1) exceso_tpo += ((Abs(tpo_fin - Clientes_ventana(1, 2)) + (tpo_fin - Clientes_ventana(1, 2))) / 2) costo_mejora += longitud + 0.01 * longitud * tpo_fin + 10000 * longitud * ((Abs(carga - capacidad) + (carga - capacidad)) / 2) + 10000 * longitud * exceso_tpo costo_mejora += 10000 * longitud * ((Abs(tpo_fin - tpo_inicio - tpo_maximo) + (tpo_fin - tpo_inicio - tpo_maximo)) / 2) fact(a, 0) = costo_mejora costo_fact += costo_mejora Next a Else If cont = 1 Then Infact = 1 costo_alt = 0 For a = 1 To k If a <> i AndAlso a <> j Then exceso_tpo = 0 tpo_fin = tpo_inicio longitud = 0 carga = 0 ilargo = (ultimo_a_nva(a) - 1) For b = 1 To ilargo tpo_fin += Tiempo_viaje(alt_nva(a, b), alt_nva(a, b + 1)) + Clientes_tpos(alt_nva(a, b + 1), 1) * Demanda(alt_nva(a, b + 1)) + Clientes_tpos(alt_nva(a, b + 1), 2) exceso_tpo += ((Abs(tpo_fin - Clientes_ventana(alt_nva(a, b + 1), 2)) + (tpo_fin - Clientes_ventana(alt_nva(a, b + 1), 2))) / 2)

If exceso_tpo > 0 Then Infact *= 0 Else Infact *= 1 End If longitud += Distancia(alt_nva(a, b), alt_nva(a, b + 1)) carga += Demanda(alt_nva(a, b + 1)) Next b longitud += Distancia(alt_nva(a, ultimo_a_nva(a)), 1) tpo_fin += Tiempo_viaje(alt_nva(a, ultimo_a_nva(a)), 1) exceso_tpo += ((Abs(tpo_fin - Clientes_ventana(1, 2)) + (tpo_fin - Clientes_ventana(1, 2))) / 2) If exceso_tpo > 0 Then Infact *= 0 Else Infact *= 1 End If costo_mejora = longitud + 0.01 * longitud * tpo_fin + 10000 * longitud * ((Abs(carga - capacidad) + (carga - capacidad)) / 2) + 10000 * longitud * exceso_tpo If carga > capacidad Then Infact *= 0 Else Infact *= 1 End If costo_mejora += 10000 * longitud * ((Abs(tpo_fin - tpo_inicio - tpo_maximo) + (tpo_fin - tpo_inicio - tpo_maximo)) / 2) If tpo_fin - tpo_inicio > tpo_maximo Then Infact *= 0 Else Infact *= 1 End If alt_nva(a, 0) = costo_mejora costo_alt += costo_mejora End If Next a rest_rut_mayor = False If costo_alt >= costo_minimo Then rest_rut_mayor = True cont_may += 1 End If Infact_rest = Infact costo_alt_rest = costo_alt a = i finales = False Do While finales = False exceso_tpo = 0 tpo_fin = tpo_inicio longitud = 0 carga = 0

77

ilargo = (ultimo_a_nva(a) - 1) For b = 1 To ilargo tpo_fin += Tiempo_viaje(alt_nva(a, b), alt_nva(a, b + 1)) + Clientes_tpos(alt_nva(a, b + 1), 1) * Demanda(alt_nva(a, b + 1)) + Clientes_tpos(alt_nva(a, b + 1), 2) exceso_tpo += ((Abs(tpo_fin - Clientes_ventana(alt_nva(a, b + 1), 2)) + (tpo_fin - Clientes_ventana(alt_nva(a, b + 1), 2))) / 2) If exceso_tpo > 0 Then Infact *= 0 Else Infact *= 1 End If longitud += Distancia(alt_nva(a, b), alt_nva(a, b + 1)) carga += Demanda(alt_nva(a, b + 1)) Next b longitud += Distancia(alt_nva(a, ultimo_a_nva(a)), 1) tpo_fin += Tiempo_viaje(alt_nva(a, ultimo_a_nva(a)), 1) exceso_tpo += ((Abs(tpo_fin - Clientes_ventana(1, 2)) + (tpo_fin - Clientes_ventana(1, 2))) / 2) If exceso_tpo > 0 Then Infact *= 0 Else Infact *= 1 End If costo_mejora = longitud + 0.01 * longitud * tpo_fin + 10000 * longitud * ((Abs(carga - capacidad) + (carga - capacidad)) / 2) + 10000 * longitud * exceso_tpo If carga > capacidad Then Infact *= 0 Else Infact *= 1 End If costo_mejora += 10000 * longitud * ((Abs(tpo_fin - tpo_inicio - tpo_maximo) + (tpo_fin - tpo_inicio - tpo_maximo)) / 2) If tpo_fin - tpo_inicio > tpo_maximo Then Infact *= 0 Else Infact *= 1 End If alt_nva(a, 0) = costo_mejora costo_alt += costo_mejora If a = i Then a = j Else finales = True End If Loop Else costo_alt = 0 Infact = Infact_rest a = i

finales = False Do While finales = False exceso_tpo = 0 tpo_fin = tpo_inicio longitud = 0 carga = 0 ilargo = (ultimo_a_nva(a) - 1) For b = 1 To ilargo tpo_fin += Tiempo_viaje(alt_nva(a, b), alt_nva(a, b + 1)) + Clientes_tpos(alt_nva(a, b + 1), 1) * Demanda(alt_nva(a, b + 1)) + Clientes_tpos(alt_nva(a, b + 1), 2) exceso_tpo += ((Abs(tpo_fin - Clientes_ventana(alt_nva(a, b + 1), 2)) + (tpo_fin - Clientes_ventana(alt_nva(a, b + 1), 2))) / 2) If exceso_tpo > 0 Then Infact *= 0 Else Infact *= 1 End If longitud += Distancia(alt_nva(a, b), alt_nva(a, b + 1)) carga += Demanda(alt_nva(a, b + 1)) Next b longitud += Distancia(alt_nva(a, ultimo_a_nva(a)), 1) tpo_fin += Tiempo_viaje(alt_nva(a, ultimo_a_nva(a)), 1) exceso_tpo += ((Abs(tpo_fin - Clientes_ventana(1, 2)) + (tpo_fin - Clientes_ventana(1, 2))) / 2) If exceso_tpo > 0 Then Infact *= 0 Else Infact *= 1 End If costo_mejora = longitud + 0.01 * longitud * tpo_fin + 10000 * longitud * ((Abs(carga - capacidad) + (carga - capacidad)) / 2) + 10000 * longitud * exceso_tpo If carga > capacidad Then Infact *= 0 Else Infact *= 1 End If costo_mejora += 10000 * longitud * ((Abs(tpo_fin - tpo_inicio - tpo_maximo) + (tpo_fin - tpo_inicio - tpo_maximo)) / 2) If tpo_fin - tpo_inicio > tpo_maximo Then Infact *= 0 Else Infact *= 1 End If alt_nva(a, 0) = costo_mejora costo_alt += costo_mejora If a = i Then a = j Else finales = True

79

End If Loop costo_alt += costo_alt_rest End If End If End Sub Public Sub Operador1() Dim ilargo As Integer Dim ilargo2 As Integer 'operador ( 0,1 ) w = ultimo_a_nva(j) aa = ultimo_a_nva(i) If w > 2 Then For s = 2 To w If nva_alt = False Then 'hay que poner un indicador por si ultimo_a_nva(i)< 2 ....??? ilargo = ultimo_a_nva(i) + 1 For r = ilargo To 3 Step -1 alt_nva(i, r) = alt_nva(i, r - 1) Next r ultimo_a_nva(i) += 1 ultimo_a(i) += 1 alt_nva(i, 2) = alt_nva(j, s) ilargo = ultimo_a_nva(j) For r = s To ilargo If r < ultimo_a_nva(j) Then alt_nva(j, r) = alt_nva(j, r + 1) End If Next r alt_nva(j, ultimo_a_nva(j)) = 0 ultimo_a_nva(j) -= 1 ultimo_a(j) -= 1 For bb = 0 To total_clientes alt(i, bb) = alt_nva(i, bb) alt(j, bb) = alt_nva(j, bb) Next bb For q = 1 To k ultimo_a(q) = ultimo_a_nva(q) Next q cont = 0 pivote = alt_nva(i, 2) ilargo = ultimo_a_nva(i) For v = 2 To ilargo If v <> 2 Then ilargo2 = v - 1

For cc = 2 To ilargo2 alt_nva(i, cc) = alt_nva(i, cc + 1) Next cc alt_nva(i, v) = pivote End If cont += 1 Call calcula_costo() If rest_rut_mayor Then Exit For End If 'If costo_alt > 227708 And costo_alt < 227709 And p = 1 Then ' gg = 1 'End If If costo_alt < costo_minimo Then costo_minimo = costo_alt For q = 0 To total_clientes alt(i, q) = alt_nva(i, q) fact(i, q) = alt_nva(i, q) alt(j, q) = alt_nva(j, q) fact(j, q) = alt_nva(j, q) Next q For q = 1 To k ultimo_a(q) = ultimo_a_nva(q) ultimo_f(q) = ultimo_a_nva(q) Next q If Infact <> 0 Then For pp = 1 To k For q = 0 To total_clientes solfact(pp, q) = alt_nva(pp, q) Next q Next pp For q = 1 To k fact(q, num_clientes + 2) = -1 Next q Else For q = 1 To k fact(q, num_clientes + 2) = -2 Next q End If nva_alt = True Exit For Else For q = 0 To total_clientes alt_nva(i, q) = alt(i, q) alt_nva(j, q) = alt(j, q) Next q End If Next v Else Exit For

81

End If If nva_alt = False Then For tt = 1 To k ultimo_a_nva(tt) = ultimo_f(tt) ultimo_a(tt) = ultimo_f(tt) Next tt For q = 0 To total_clientes alt_nva(i, q) = fact(i, q) alt(i, q) = fact(i, q) alt_nva(j, q) = fact(j, q) alt(j, q) = fact(j, q) Next q End If Next s End If End Sub Public Sub Operador2() 'Operador (1, 0) 'intercambio rutas i por j y j por i For dd = 0 To total_clientes fact_2(i, dd) = fact(i, dd) fact_2(j, dd) = fact(j, dd) solfact_2(i, dd) = solfact(i, dd) solfact_2(j, dd) = solfact(j, dd) alt_2(i, dd) = alt(i, dd) alt_2(j, dd) = alt(j, dd) alt_nva_2(i, dd) = alt_nva(i, dd) alt_nva_2(j, dd) = alt_nva(j, dd) Next dd ultimo_f2(i) = ultimo_f(i) ultimo_f2(j) = ultimo_f(j) ultimo_a2(i) = ultimo_a(i) ultimo_a2(j) = ultimo_a(j) ultimo_a_nva2(i) = ultimo_a_nva(i) ultimo_a_nva2(j) = ultimo_a_nva(j) For ee = 0 To total_clientes fact(i, ee) = fact_2(j, ee) fact(j, ee) = fact_2(i, ee) solfact(i, ee) = solfact_2(j, ee) solfact(j, ee) = solfact_2(i, ee)

alt(i, ee) = alt_2(j, ee) alt(j, ee) = alt_2(i, ee) alt_nva(i, ee) = alt_nva_2(j, ee) alt_nva(j, ee) = alt_nva_2(i, ee) Next ee ultimo_f(i) = ultimo_f2(j) ultimo_f(j) = ultimo_f2(i) ultimo_a(i) = ultimo_a2(j) ultimo_a(j) = ultimo_a2(i) ultimo_a_nva(i) = ultimo_a_nva2(j) ultimo_a_nva(j) = ultimo_a_nva2(i) Call Operador1() tt = 12345 '''ActiveSheet.Cells(34, 11) = tt For dd = 0 To total_clientes fact_2(i, dd) = fact(i, dd) fact_2(j, dd) = fact(j, dd) solfact_2(i, dd) = solfact(i, dd) solfact_2(j, dd) = solfact(j, dd) alt_2(i, dd) = alt(i, dd) alt_2(j, dd) = alt(j, dd) alt_nva_2(i, dd) = alt_nva(i, dd) alt_nva_2(j, dd) = alt_nva(j, dd) Next dd ultimo_f2(i) = ultimo_f(i) ultimo_f2(j) = ultimo_f(j) ultimo_a2(i) = ultimo_a(i) ultimo_a2(j) = ultimo_a(j) ultimo_a_nva2(i) = ultimo_a_nva(i) ultimo_a_nva2(j) = ultimo_a_nva(j) For ee = 0 To total_clientes fact(i, ee) = fact_2(j, ee) fact(j, ee) = fact_2(i, ee) solfact(i, ee) = solfact_2(j, ee) solfact(j, ee) = solfact_2(i, ee)

83

alt(i, ee) = alt_2(j, ee) alt(j, ee) = alt_2(i, ee) alt_nva(i, ee) = alt_nva_2(j, ee) alt_nva(j, ee) = alt_nva_2(i, ee) Next ee ultimo_f(i) = ultimo_f2(j) ultimo_f(j) = ultimo_f2(i) ultimo_a(i) = ultimo_a2(j) ultimo_a(j) = ultimo_a2(i) ultimo_a_nva(i) = ultimo_a_nva2(j) ultimo_a_nva(j) = ultimo_a_nva2(i) End Sub Public Sub Operador3() 'operador ( 1,1 ) Dim ilargo As Integer Dim ilargo2 As Integer w = ultimo_a_nva(j) aa = ultimo_a_nva(i) If w >= 2 AndAlso aa >= 2 Then For u = 2 To aa If nva_alt = True Then Exit For End If For s = 2 To w If nva_alt = False Then 'hago intercambio entre 1 elem.de i y 1 elem.de j aux = alt_nva(i, u) ilargo = ultimo_a_nva(i) + 1 For xx = ilargo To 3 Step -1 alt_nva(i, xx) = alt_nva(i, xx - 1) Next xx alt_nva(i, 2) = alt_nva(j, s) ilargo = ultimo_a_nva(j) + 1 For xx = ilargo To 3 Step -1 alt_nva(j, xx) = alt_nva(j, xx - 1) Next xx alt_nva(j, 2) = aux ilargo = u + 1 For xx = ilargo To aa + 1 alt_nva(i, xx) = alt_nva(i, xx + 1)

Next xx ilargo = s + 1 For xx = ilargo To w + 1 alt_nva(j, xx) = alt_nva(j, xx + 1) Next xx For bb = 0 To total_clientes alt(i, bb) = alt_nva(i, bb) alt(j, bb) = alt_nva(j, bb) Next bb For q = 1 To k ultimo_a(q) = ultimo_a_nva(q) Next q tu = 54321 '''ActiveSheet.Cells(35, 11) = tu cont = 0 pivote2 = alt_nva(j, 2) ilargo = ultimo_a_nva(j) For ee = 2 To ilargo If ee <> 2 Then For dd = 2 To ee - 1 alt_nva(j, dd) = alt_nva(j, dd + 1) Next dd alt_nva(j, ee) = pivote2 End If pivote = alt_nva(i, 2) ilargo2 = ultimo_a_nva(i) For v = 2 To ilargo2 If v <> 2 Then For cc = 2 To v - 1 alt_nva(i, cc) = alt_nva(i, cc + 1) Next cc alt_nva(i, v) = pivote End If cont += 1 Call calcula_costo() If rest_rut_mayor Then Exit For End If 'If costo_alt > 243954 And costo_alt < 243955 And p = 3 Then ' gg = 1 'End If If costo_alt < costo_minimo Then costo_minimo = costo_alt For q = 0 To total_clientes alt(i, q) = alt_nva(i, q)

85

fact(i, q) = alt_nva(i, q) alt(j, q) = alt_nva(j, q) fact(j, q) = alt_nva(j, q) Next q For q = 1 To k ultimo_a(q) = ultimo_a_nva(q) ultimo_f(q) = ultimo_a_nva(q) Next q If Infact <> 0 Then For pp = 1 To k For q = 0 To total_clientes solfact(pp, q) = alt_nva(pp, q) Next q Next pp For q = 1 To k fact(q, num_clientes + 2) = -1 Next q Else For q = 1 To k fact(q, num_clientes + 2) = -2 Next q End If nva_alt = True Exit For Else For q = 0 To total_clientes alt_nva(i, q) = alt(i, q) Next q End If Next v If nva_alt = True Then Exit For End If For q = 0 To total_clientes alt_nva(j, q) = alt(j, q) Next q Next ee If nva_alt = False Then For tt = 1 To k ultimo_a_nva(tt) = ultimo_f(tt) Next tt For q = 0 To total_clientes alt_nva(i, q) = fact(i, q) alt(i, q) = fact(i, q) alt_nva(j, q) = fact(j, q) alt(j, q) = fact(j, q) Next q Else Exit For End If

Else Exit For End If Next s Next u End If End Sub Public Sub Operador4() Dim ilargo As Integer Dim ilargo2 As Integer 'operador ( 0,2 ) w = ultimo_a_nva(j) aa = ultimo_a_nva(i) If w > 3 Then ilargo = w - 1 For s = 2 To ilargo If nva_alt = False Then 'hay que poner un indicador por si ultimo_a_nva(i)< 2 ....??? ilargo2 = ultimo_a_nva(i) + 2 For r = ilargo2 To 4 Step -1 alt_nva(i, r) = alt_nva(i, r - 2) Next r ultimo_a_nva(i) += 2 alt_nva(i, 2) = alt_nva(j, s) alt_nva(i, 3) = alt_nva(j, s + 1) ilargo2 = ultimo_a_nva(j) - 2 For r = s To ilargo2 alt_nva(j, r) = alt_nva(j, r + 2) Next r alt_nva(j, ultimo_a_nva(j) - 1) = 0 alt_nva(j, ultimo_a_nva(j)) = 0 ultimo_a_nva(j) -= 2 For bb = 0 To total_clientes alt(i, bb) = alt_nva(i, bb) alt(j, bb) = alt_nva(j, bb) Next bb For q = 1 To k ultimo_a(q) = ultimo_a_nva(q) Next q tv = 99999

87

'ActiveSheet.Cells(36, 11) = tv cont = 0 pivot1 = alt_nva(i, 2) pivot2 = alt_nva(i, 3) ilargo = ultimo_a_nva(i) - 1 For v = 2 To ilargo If v <> 2 Then For cc = 2 To v - 1 alt_nva(i, cc) = alt_nva(i, cc + 2) Next cc alt_nva(i, v) = pivot1 alt_nva(i, v + 1) = pivot2 End If cont += 1 Call calcula_costo() If rest_rut_mayor Then Exit For End If 'If costo_alt > 238993 And costo_alt < 238994 And p = 5 Then ' gg = 1 'End If If costo_alt < costo_minimo Then costo_minimo = costo_alt For q = 0 To total_clientes alt(i, q) = alt_nva(i, q) alt(j, q) = alt_nva(j, q) fact(i, q) = alt_nva(i, q) fact(j, q) = alt_nva(j, q) Next q For q = 1 To k ultimo_a(q) = ultimo_a_nva(q) ultimo_f(q) = ultimo_a_nva(q) Next q If Infact <> 0 Then For pp = 1 To k For q = 0 To total_clientes solfact(pp, q) = alt_nva(pp, q) Next q Next pp For q = 0 To total_clientes fact(i, q) = alt_nva(i, q) Next q If num_clientes > ultimo_a_nva(i) - 1 Then For q = ultimo_a_nva(i) + 1 To total_clientes fact(i, q) = 0 Next q End If For q = 0 To total_clientes

fact(j, q) = alt_nva(j, q) Next q If num_clientes > ultimo_a_nva(j) - 1 Then For q = ultimo_a_nva(j) + 1 To total_clientes fact(j, q) = 0 Next q End If For q = 1 To k ultimo_f(q) = ultimo_a_nva(q) Next q End If nva_alt = True Exit For Else For q = 0 To total_clientes alt_nva(i, q) = alt(i, q) Next q For q = 0 To total_clientes alt_nva(j, q) = alt(j, q) Next q End If Next v If nva_alt = False Then For tt = 1 To k ultimo_a_nva(tt) = ultimo_f(tt) Next tt For q = 0 To total_clientes alt_nva(i, q) = fact(i, q) alt_nva(j, q) = fact(j, q) alt(i, q) = fact(i, q) alt(j, q) = fact(j, q) Next q End If Else Exit For End If Next s End If End Sub Public Sub Operador5() 'Operador (2, 0) 'intercambio rutas i por j y j por i Dim ilargo As Integer Dim ilargo2 As Integer For dd = 0 To total_clientes fact_2(i, dd) = fact(i, dd)

89

fact_2(j, dd) = fact(j, dd) solfact_2(i, dd) = solfact(i, dd) solfact_2(j, dd) = solfact(j, dd) alt_2(i, dd) = alt(i, dd) alt_2(j, dd) = alt(j, dd) alt_nva_2(i, dd) = alt_nva(i, dd) alt_nva_2(j, dd) = alt_nva(j, dd) Next dd ultimo_f2(i) = ultimo_f(i) ultimo_f2(j) = ultimo_f(j) ultimo_a2(i) = ultimo_a(i) ultimo_a2(j) = ultimo_a(j) ultimo_a_nva2(i) = ultimo_a_nva(i) ultimo_a_nva2(j) = ultimo_a_nva(j) For ee = 0 To total_clientes fact(i, ee) = fact_2(j, ee) fact(j, ee) = fact_2(i, ee) solfact(i, ee) = solfact_2(j, ee) solfact(j, ee) = solfact_2(i, ee) alt(i, ee) = alt_2(j, ee) alt(j, ee) = alt_2(i, ee) alt_nva(i, ee) = alt_nva_2(j, ee) alt_nva(j, ee) = alt_nva_2(i, ee) Next ee ultimo_f(i) = ultimo_f2(j) ultimo_f(j) = ultimo_f2(i) ultimo_a(i) = ultimo_a2(j) ultimo_a(j) = ultimo_a2(i) ultimo_a_nva(i) = ultimo_a_nva2(j) ultimo_a_nva(j) = ultimo_a_nva2(i) Call Operador4() tw = 11111 'ActiveSheet.Cells(37, 11) = tw For dd = 0 To total_clientes fact_2(i, dd) = fact(i, dd) fact_2(j, dd) = fact(j, dd)

solfact_2(i, dd) = solfact(i, dd) solfact_2(j, dd) = solfact(j, dd) alt_2(i, dd) = alt(i, dd) alt_2(j, dd) = alt(j, dd) alt_nva_2(i, dd) = alt_nva(i, dd) alt_nva_2(j, dd) = alt_nva(j, dd) Next dd ultimo_f2(i) = ultimo_f(i) ultimo_f2(j) = ultimo_f(j) ultimo_a2(i) = ultimo_a(i) ultimo_a2(j) = ultimo_a(j) ultimo_a_nva2(i) = ultimo_a_nva(i) ultimo_a_nva2(j) = ultimo_a_nva(j) For ee = 0 To total_clientes fact(i, ee) = fact_2(j, ee) fact(j, ee) = fact_2(i, ee) solfact(i, ee) = solfact_2(j, ee) solfact(j, ee) = solfact_2(i, ee) alt(i, ee) = alt_2(j, ee) alt(j, ee) = alt_2(i, ee) alt_nva(i, ee) = alt_nva_2(j, ee) alt_nva(j, ee) = alt_nva_2(i, ee) Next ee ultimo_f(i) = ultimo_f2(j) ultimo_f(j) = ultimo_f2(i) ultimo_a(i) = ultimo_a2(j) ultimo_a(j) = ultimo_a2(i) ultimo_a_nva(i) = ultimo_a_nva2(j) ultimo_a_nva(j) = ultimo_a_nva2(i) End Sub Public Sub Operador6() 'operador ( 1,2 ) Dim ilargo As Integer Dim ilargo2 As Integer Dim ilargo3 As Integer Dim ilargo4 As Integer

91

w = ultimo_a_nva(j) aa = ultimo_a_nva(i) If w >= 3 AndAlso aa >= 2 Then For u = 2 To aa If nva_alt = True Then Exit For End If ilargo = w - 1 For s = 2 To ilargo If nva_alt = False Then 'hago intercambio entre 1 elem.de i y 2 elem.de j aux = alt_nva(i, u) ilargo2 = ultimo_a_nva(i) For xx = u To ilargo2 If xx < total_clientes Then alt_nva(i, xx) = alt_nva(i, xx + 1) Else alt_nva(i, xx) = 0 End If Next xx If ultimo_a_nva(i) >= 3 Then ilargo2 = ultimo_a_nva(i) - 1 For xx = ilargo2 To 2 Step -1 alt_nva(i, xx + 2) = alt_nva(i, xx) Next xx alt_nva(i, 2) = alt_nva(j, s) alt_nva(i, 3) = alt_nva(j, s + 1) Else alt_nva(i, 2) = alt_nva(j, s) alt_nva(i, 3) = alt_nva(j, s + 1) End If If s = w - 1 Then alt_nva(j, s) = 0 alt_nva(j, s + 1) = 0 Else ilargo2 = ultimo_a_nva(j) - 2 For xx = s To ilargo2 alt_nva(j, xx) = alt_nva(j, xx + 2) Next xx alt_nva(j, ultimo_a_nva(j) - 1) = 0 alt_nva(j, ultimo_a_nva(j)) = 0 End If

If ultimo_a_nva(j) > 3 Then ilargo2 = ultimo_a_nva(j) - 2 For xx = ilargo2 To 2 Step -1 alt_nva(j, xx + 1) = alt_nva(j, xx) Next xx alt_nva(j, 2) = aux Else alt_nva(j, 2) = aux End If ultimo_a_nva(i) += 1 ultimo_a_nva(j) -= 1 For bb = 0 To total_clientes alt(i, bb) = alt_nva(i, bb) alt(j, bb) = alt_nva(j, bb) Next bb For q = 1 To k ultimo_a(q) = ultimo_a_nva(q) Next q tu = 55555 '''ActiveSheet.Cells(35, 11) = tu cont = 0 pivot3 = alt_nva(i, 2) pivot4 = alt_nva(i, 3) ilargo2 = ultimo_a_nva(i) - 1 For ee = 2 To ilargo2 If ee <> 2 Then ilargo3 = ee - 1 For dd = 2 To ilargo3 alt_nva(i, dd) = alt_nva(i, dd + 2) Next dd alt_nva(i, ee) = pivot3 alt_nva(i, ee + 1) = pivot4 End If pivot5 = alt_nva(j, 2) ilargo3 = ultimo_a_nva(j) For ff = 2 To ilargo3 If ff <> 2 Then ilargo4 = ff - 1 For cc = 2 To ilargo4 alt_nva(j, cc) = alt_nva(j, cc + 1) Next cc alt_nva(j, ff) = pivot5 End If cont += 1 Call calcula_costo()

93

If rest_rut_mayor Then Exit For End If 'If costo_alt > 515037.8336412 And costo_alt < 515037.8336413 And p = 6 Then ' gg = 1 'End If If costo_alt < costo_minimo Then costo_minimo = costo_alt For q = 0 To total_clientes alt(i, q) = alt_nva(i, q) fact(i, q) = alt_nva(i, q) alt(j, q) = alt_nva(j, q) fact(j, q) = alt_nva(j, q) Next q For q = 1 To k ultimo_a(q) = ultimo_a_nva(q) ultimo_f(q) = ultimo_a_nva(q) Next q If Infact <> 0 Then For pp = 1 To k For q = 0 To total_clientes solfact(pp, q) = alt_nva(pp, q) Next q Next pp For q = 1 To k fact(q, num_clientes + 2) = -1 Next q Else For q = 1 To k fact(q, num_clientes + 2) = -2 Next q End If nva_alt = True Exit For Else For q = 0 To total_clientes alt_nva(j, q) = alt(j, q) Next q End If Next ff If nva_alt = True Then Exit For End If For q = 0 To total_clientes alt_nva(i, q) = alt(i, q) Next q Next ee If nva_alt = False Then For tt = 1 To k

ultimo_a_nva(tt) = ultimo_f(tt) Next tt For q = 0 To total_clientes alt_nva(i, q) = fact(i, q) alt_nva(j, q) = fact(j, q) alt(i, q) = fact(i, q) alt(j, q) = fact(j, q) Next q End If Else Exit For End If Next s Next u End If End Sub Public Sub Operador7() 'Operador (2,1) 'intercambio rutas i por j y j por i For dd = 0 To total_clientes fact_2(i, dd) = fact(i, dd) fact_2(j, dd) = fact(j, dd) solfact_2(i, dd) = solfact(i, dd) solfact_2(j, dd) = solfact(j, dd) alt_2(i, dd) = alt(i, dd) alt_2(j, dd) = alt(j, dd) alt_nva_2(i, dd) = alt_nva(i, dd) alt_nva_2(j, dd) = alt_nva(j, dd) Next dd ultimo_f2(i) = ultimo_f(i) ultimo_f2(j) = ultimo_f(j) ultimo_a2(i) = ultimo_a(i) ultimo_a2(j) = ultimo_a(j) ultimo_a_nva2(i) = ultimo_a_nva(i) ultimo_a_nva2(j) = ultimo_a_nva(j) For ee = 0 To total_clientes fact(i, ee) = fact_2(j, ee) fact(j, ee) = fact_2(i, ee) solfact(i, ee) = solfact_2(j, ee)

95

solfact(j, ee) = solfact_2(i, ee) alt(i, ee) = alt_2(j, ee) alt(j, ee) = alt_2(i, ee) alt_nva(i, ee) = alt_nva_2(j, ee) alt_nva(j, ee) = alt_nva_2(i, ee) Next ee ultimo_f(i) = ultimo_f2(j) ultimo_f(j) = ultimo_f2(i) ultimo_a(i) = ultimo_a2(j) ultimo_a(j) = ultimo_a2(i) ultimo_a_nva(i) = ultimo_a_nva2(j) ultimo_a_nva(j) = ultimo_a_nva2(i) Call Operador6() tz = 33333 '''ActiveSheet.Cells(37, 11) = tz For dd = 0 To total_clientes fact_2(i, dd) = fact(i, dd) fact_2(j, dd) = fact(j, dd) solfact_2(i, dd) = solfact(i, dd) solfact_2(j, dd) = solfact(j, dd) alt_2(i, dd) = alt(i, dd) alt_2(j, dd) = alt(j, dd) alt_nva_2(i, dd) = alt_nva(i, dd) alt_nva_2(j, dd) = alt_nva(j, dd) Next dd ultimo_f2(i) = ultimo_f(i) ultimo_f2(j) = ultimo_f(j) ultimo_a2(i) = ultimo_a(i) ultimo_a2(j) = ultimo_a(j) ultimo_a_nva2(i) = ultimo_a_nva(i) ultimo_a_nva2(j) = ultimo_a_nva(j) For ee = 0 To total_clientes fact(i, ee) = fact_2(j, ee) fact(j, ee) = fact_2(i, ee) solfact(i, ee) = solfact_2(j, ee) solfact(j, ee) = solfact_2(i, ee)

alt(i, ee) = alt_2(j, ee) alt(j, ee) = alt_2(i, ee) alt_nva(i, ee) = alt_nva_2(j, ee) alt_nva(j, ee) = alt_nva_2(i, ee) Next ee ultimo_f(i) = ultimo_f2(j) ultimo_f(j) = ultimo_f2(i) ultimo_a(i) = ultimo_a2(j) ultimo_a(j) = ultimo_a2(i) ultimo_a_nva(i) = ultimo_a_nva2(j) ultimo_a_nva(j) = ultimo_a_nva2(i) End Sub Public Sub Operador8() 'operador ( 2,2 ) Dim ilargo As Integer Dim ilargo2 As Integer Dim ilargo3 As Integer Dim ilargo4 As Integer Dim ilargo5 As Integer w = ultimo_a_nva(j) aa = ultimo_a_nva(i) If (w >= 3 AndAlso aa >= 4) OrElse (w >= 4 AndAlso aa >= 3) Then ilargo = aa - 1 For u = 2 To ilargo If nva_alt = True Then Exit For End If ilargo2 = w - 1 For s = 2 To ilargo2 If nva_alt = False Then 'hago intercambio entre 2 elem.de i y 2 elem.de j aux1 = alt_nva(i, u) aux2 = alt_nva(i, u + 1) ilargo3 = ultimo_a_nva(i) + 2 For xx = ilargo3 To 4 Step -1 alt_nva(i, xx) = alt_nva(i, xx - 2) Next xx alt_nva(i, 2) = alt_nva(j, s) alt_nva(i, 3) = alt_nva(j, s + 1) ilargo3 = ultimo_a_nva(j) + 2

97

For xx = ilargo3 To 4 Step -1 alt_nva(j, xx) = alt_nva(j, xx - 2) Next xx alt_nva(j, 2) = aux1 alt_nva(j, 3) = aux2 ilargo3 = u + 2 ilargo4 = aa + 2 For xx = ilargo3 To ilargo4 alt_nva(i, xx) = alt_nva(i, xx + 2) Next xx ilargo3 = s + 2 ilargo4 = w + 2 For xx = ilargo3 To ilargo4 alt_nva(j, xx) = alt_nva(j, xx + 2) Next xx For bb = 0 To total_clientes alt(i, bb) = alt_nva(i, bb) alt(j, bb) = alt_nva(j, bb) Next bb For q = 1 To k ultimo_a(q) = ultimo_a_nva(q) Next q tu = 88888 '''ActiveSheet.Cells(35, 11) = tu cont = 0 pivote1 = alt_nva(j, 2) pivote2 = alt_nva(j, 3) ilargo3 = ultimo_a_nva(j) - 1 For ee = 2 To ilargo3 If ee <> 2 Then ilargo4 = ee - 1 For dd = 2 To ilargo4 alt_nva(j, dd) = alt_nva(j, dd + 2) Next dd alt_nva(j, ee) = pivote1 alt_nva(j, ee + 1) = pivote2 End If pivote3 = alt_nva(i, 2) pivote4 = alt_nva(i, 3)

ilargo4 = ultimo_a_nva(i) - 1 For v = 2 To ilargo4 If v <> 2 Then ilargo5 = v - 1 For cc = 2 To ilargo5 alt_nva(i, cc) = alt_nva(i, cc + 2) Next cc alt_nva(i, v) = pivote3 alt_nva(i, v + 1) = pivote4 End If cont += 1 Call calcula_costo() If rest_rut_mayor Then Exit For End If 'If costo_alt > 1035891.9084249 And costo_alt < 1035891.908425 And p = 8 Then ' gg = 1 'End If If costo_alt < costo_minimo Then costo_minimo = costo_alt For q = 0 To total_clientes alt(i, q) = alt_nva(i, q) fact(i, q) = alt_nva(i, q) alt(j, q) = alt_nva(j, q) fact(j, q) = alt_nva(j, q) Next q For q = 1 To k ultimo_a(q) = ultimo_a_nva(q) ultimo_f(q) = ultimo_a_nva(q) Next q If Infact <> 0 Then For pp = 1 To k For q = 0 To total_clientes solfact(pp, q) = alt_nva(pp, q) Next q Next pp For q = 1 To k fact(q, num_clientes + 2) = -1 Next q Else For q = 1 To k fact(q, num_clientes + 2) = -2 Next q End If nva_alt = True Exit For Else For q = 0 To total_clientes alt_nva(i, q) = alt(i, q)

99

Next q End If Next v If nva_alt = True Then Exit For End If For q = 0 To total_clientes alt_nva(j, q) = alt(j, q) Next q Next ee If nva_alt = False Then For tt = 1 To k ultimo_a_nva(tt) = ultimo_f(tt) Next tt For q = 0 To total_clientes alt_nva(i, q) = fact(i, q) alt_nva(j, q) = fact(j, q) alt(i, q) = fact(i, q) alt(j, q) = fact(j, q) Next q Else Exit For End If Else Exit For End If Next s Next u End If End Sub Private Sub BW_ProgressBar_DoWork(ByVal sender As System.Object, ByVal e As System.ComponentModel.DoWorkEventArgs) Handles BW_ProgressBar.DoWork Dim i As Integer = 0 Try If BW_ProgressBar.CancellationPending Then e.Cancel = True Return End If CalcNextValue(m_NewValue) System.Threading.Thread.Sleep(m_ThreadTimer) BW_ProgressBar.ReportProgress(i, New Object() {m_NewValue}) Catch ex As Exception

BW_ProgressBar.CancelAsync() BW_ProgressBar.Dispose() End Try End Sub Private Sub BW_ProgressBar_ProgressChanged(ByVal sender As Object, ByVal e As System.ComponentModel.ProgressChangedEventArgs) Handles BW_ProgressBar.ProgressChanged If m_BackThread_Stop = False Then Invoke(New UpdateProgressbarHandler(AddressOf SetProgressbarValue), New Object() {m_NewValue}) End If End Sub Private Sub BW_ProgressBar_RunWorkerCompleted(ByVal sender As Object, ByVal e As System.ComponentModel.RunWorkerCompletedEventArgs) Handles BW_ProgressBar.RunWorkerCompleted Try If e.Cancelled = False Then BW_ProgressBar.Dispose() If m_BackThread_Stop = False Then BW_ProgressBar.RunWorkerAsync() End If End If Catch ex As Exception BW_ProgressBar.Dispose() BW_ProgressBar.CancelAsync() End Try End Sub Private Function CalcNextValue(ByVal oldValue As Integer) As Integer Try If m_NewValue < m_PB_Maximum Then m_NewValue = oldValue + 1 Else m_NewValue = 0 End If Return m_NewValue Catch ex As Exception m_NewValue = 0 Return m_NewValue End Try End Function Private Sub SetProgressbarValue(ByVal value As Integer) ToolStripProgressBar1.Value = value End Sub Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load

101

BW_ProgressBar.WorkerReportsProgress = True BW_ProgressBar.WorkerSupportsCancellation = True ToolStripProgressBar1.Minimum = 0 ToolStripProgressBar1.Maximum = m_PB_Maximum End Sub 'Private Sub BTN_Start_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles BTN_Start.Click ' Try ' If BW_ProgressBar.IsBusy = False Then ' m_BackThread_Stop = False ' BW_ProgressBar.RunWorkerAsync() ' End If ' Catch ex As Exception ' BW_ProgressBar.CancelAsync() ' BW_ProgressBar.Dispose() ' End Try 'End Sub 'Private Sub BTN_Ende_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles BTN_Stoppen.Click ' m_BackThread_Stop = True ' BW_ProgressBar.CancelAsync() ' ToolStripProgressBar1.Value = 0 'End Sub 'Private Sub BTN_Beenden_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles BTN_Beenden.Click ' Try ' m_BackThread_Stop = True ' BW_ProgressBar.CancelAsync() ' BW_ProgressBar.Dispose() ' ToolStripProgressBar1.Value = 0 ' End ' Catch ex As Exception ' BW_ProgressBar.Dispose() ' End ' End Try 'End Sub End Class