CONTRASTACIÓN DE LOS MODELOS DE PROGRAMACIÓN LINEAL CON ... - Oviedo/Trabajos/PDF/57.pdf ·...

1

Reservados todos los derechos. Este documento ha sido extraído del CD Rom “Anales de Economía Aplicada. XIV Reunión ASEPELT-España. Oviedo, 22 y 23 de Junio de 2000”. ISBN: 84-699-2357-9

CONTRASTACIÓN DE LOS MODELOS DE PROGRAMACIÓN LINEAL CON LOS HEURÍSTICOS EN LA RESOLUCIÓN DE UN PROBLEMA VRP EN UNA EMPRESA

CONSERVERA

Javier Faulín1 - [email protected] Fernando Jiménez Torres2 - [email protected]

1 Universidad Pública de Navarra 2 Universidad de Zaragoza

2

CONTRASTACIÓN DE LOS MODELOS DE PROGRAMACIÓN LINEAL

CON LOS HEURÍSTICOS EN LA RESOLUCIÓN DE UN PROBLEMA VRP EN UNA EMPRESA CONSERVERA.

Javier Faulín1, Fernando Jiménez Torres2.

1Departamento de Estadística e Investigación Operativa. Universidad Pública de Navarra. 2Departamento de Métodos Estadísticos. Universidad de Zaragoza.

ABSTRACT

Las empresas conserveras tienen unas necesidades logísticas de características peculiares en relación con las de otros sectores. En este trabajo, se pretende establecer una comparación entre los métodos heurísticos y de programación lineal a la hora de cálculo de rutas óptimas de recogida de materias primas y de distribución de productos terminados. Estas rutas se calculan, por una parte, mediante modelos lineales de programación matemática teniendo en cuenta las restricciones en las que aparecen involucrados los vehículos de transporte. Por otro lado, se emplean los algoritmos de barrido y de Clark-Wright. Los resultados finales se muestran y comparan en una tabla, estableciendo cuáles son las rutas mejores. Palabras y frases clave: Logística empresarial, actividades del transporte, programación lineal, métodos heurísticos, sector conservero. Clasificación UNESCO: 1207.04.

INTRODUCCIÓN

En este trabajo se pretende dar una visión de la aplicación de diversos algoritmos

heurísticos sencillos (algoritmo de barrido y de Clark y Wright) y su mejora con un método

exacto de programación lineal para la resolución práctica de un problema Vehicle Routing

Problem (VRP) de dimensión pequeña. El caso de aplicación se centró en la empresa ACSA,

productora de conservas enlatadas en Navarra. Especifiquemos a continuación las

características técnicas del problema antes de dar las soluciones correspondientes a cada uno de

los algoritmos propuestos. La gestión diaria del transporte de distribución durante once días, se

basa en determinar el número de viajes a realizar y los nodos integrantes de cada uno de ellos.

Así, el problema a solucionar cada jornada por el decisor en ACSA es un VRP, con las

siguientes características:

- Tamaño de flota desconocido.

-Flota homogénea, en cuanto a la capacidad de los vehículos: el volumen de carga de los camiones

frigoríficos utilizados por ACSA es de 20.000kgs.

- Depósito único.

- Demandas determinísticas.

- Operaciones de reparto.

- Red orientada.

-Objetivo: minimizar distancias.

2

1. EVOLUCIÓN Y CARACTERÍSTICAS GENERALES.

ALIMENTOS CONGELADOS S.A., cuyo nombre comercial es ACSA, fue fundada en el

año 1957 en la localidad de Marcilla 1. Hasta los años setenta, esta empresa no pudo desarrollar su

actividad congeladora, debido a la falta de medios técnicos. Por esto, durante estos años, el negocio

de la empresa se dirigió hacia el sector de las conservas, pero sólo de forma temporal. A partir de

la década de los setenta, la empresa comenzó a desarrollarse y a tener resultados positivos, fruto de

los cuales fueron la construcción de tres nuevas plantas:

- Peralta, en 1974.

- Badajoz, en 1980.

- Olmedo (Valladolid), en 1985.

En los años ochenta, la empresa fue adquirida por el Banco de Bilbao a través de una

teneduría de acciones que abarcaba no sólo esta empresa, sino también Miko y Avidesa, a pesar de

lo cual nunca llegó a perder su independencia de gestión. En marzo de 1995, el grupo formado por

Miko, Avidesa y Alimentos Congelados fue adquirido por el GRUPO NESTLÉ por alrededor de

40.000 millones de pesetas.

ACSA es una empresa que se dedica a la producción y comercialización de verduras

congeladas, bien sea de forma individual o combinada. Sus principales productos son: guisantes,

judías, coliflor, espinacas, patatas, zanahoria, habas, coles de Bruselas, bróculi, pimientos (rojos,

verdes, en tiras...), maíz dulce, ensaladilla rusa, ensalada oriental, ensalada americana, verdura para

sopa y verdura para paella. Esta gran variedad de productos obliga a la empresa a aprovisionarse de

materia prima durante todo el año, si bien las cosechas más importantes son las del guisante, alubias

y pimiento. El volumen de verduras tratado asciende hasta 60.000Tns/año.

El volumen de ventas de la empresa es de unos 9.000 millones de pesetas anuales, de los

cuales alrededor del 30% son exportaciones.

El numero de empleados asciende a setecientos en las épocas de más trabajo, la mitad de

los cuales realizan su labor en la planta de Marcilla.

En las plantas de Peralta, Badajoz y Olmedo se trabaja con producto base (materia prima

limpia y congelada), mientras que en Marcilla se realiza el acondicionamiento del producto. En el

momento actual, la planta de Marcilla es la principal y de la que dependen las tres restantes.

Antes de pasar a la descripción de las actividades logísticas, y para conocer mejor las

características generales de ACSA, se va a analizar el balance de situación y la cuenta de pérdidas

XIV Reunión Anual de ASEPELT-España Oviedo, 22-23 de Junio de 2000

3

y ganancias correspondientes al ejercicio de 1995, las cuales se muestran en las Tablas 1 y 2,

respectivamente. Para esto, y siguiendo el mismo esquema que en los capítulos correspondientes a

BAJAMAR y GUTARRA, vamos a calcular los ratios que nos permitan obtener la posición

financiera, nivel de endeudamiento, eficiencia operativa y rentabilidad de ACSA, y conocer, así, de

forma más profunda, su situación actual.

2. ACTIVIDADES LOGÍSTICAS.

En este apartado se pretende destacar, en primer lugar, la distribución de la responsabilidad

en la gestión de las actividades logísticas en una empresa como ACSA: congeladora, de gran

tamaño y que pertenece a un grupo multinacional. En sentido, vamos a comprobar cómo la

incorporación de ACSA al GRUPO NESTLÉ ha afectado directamente a su estructura

organizativa y al modo de gestionar sus actividades logísticas. Sin embargo, estos cambios no se

produjeron hasta un año después de su integración. De este modo, hasta marzo de 1996, el

organigrama de ACSA era el descrito en la Figura 1.

Administración

Peralta Olmedo Badajoz

Producción Marketing Direcciónde ventas

Direcciónde trading

Dirección ACSA

Figura 1. Organigrama de ACSA hasta marzo de 1996.

Desde el punto de vista de la logística, su gestión se realizaba desde los departamentos de

producción, dirección de ventas y dirección de trading, respectivamente. En cuanto al primero,

se ocupaba de las actividades de aprovisionamiento de la materia prima y del producto base. Por

tanto, el transporte de aprovisionamiento, el transporte interno y la gestión de stocks del producto

base formaba parte del área de responsabilidad del director de producción. En cuanto a la

distribución, ésta se repartía entre dirección de ventas y dirección de trading. La primera se

encargaba de la distribución y venta de los productos finales con marca propia, y de parte de los

vendidos con marca de distribuidores. Para esto, la empresa contaba con cuatro delegaciones

1 Se trata de una población de unos 2.500 habitantes, situada en la zona Medio Oriental de Navarra, a unos 70 kms. de Pamplona.


4

(Málaga, Barcelona, Madrid y Sevilla), y varias jefaturas regionales, donde los representantes se

encargaban de obtener los pedidos y de repartir el producto final de forma directa a los clientes.

A partir de marzo de 1996, la dirección de ACSA pasó a depender de forma activa de la

dirección de ultracongelados de NESTLÉ, formada por el conjunto de empresas de productos

congelados de este grupo (Fundis,...). Esto dio lugar a una nueva estructura organizativa, que se

refleja en la Figura 2.

En este nuevo organigrama, los departamentos de marketing y dirección de ventas han

pasado a depender directamente de la dirección de ultracongelados de NESTLÉ. A su vez, se

creó un departamento de logística en la sede central de Barcelona, desde la cual se gestiona la

distribución de los productos finales a dos centros logísticos de NESTLÉ, localizados en Tarrasa y

Alcalá de Henares, respectivamente. Sólo en casos muy concretos se reparte producto final a la s

delegaciones o distribuidores directamente desde la factoría de Marcilla.

Marketing Logistica

Ventas

Administración

Factoriade Peralta

Factoriade Olmedo

Factoriade Badajoz

Producción Dirección detrading

Programacióndel envasado

Camara yexpedición

Logistica

Dirección ACSA

Direccion deUltracongelados

de Nestlé

Figura 2. Organigrama de ACSA a partir de marzo de 1996.

A su vez, se creó un departamento de logística en ACSA, cuya función es doble, respecto

al producto base:

- Programación del envasado: coordina los pedidos realizados desde Barcelona y desde la

dirección de trading con el departamento de producción.

- Cámara y expedición.


5

Por tanto, en este momento, y respecto al producto en sus diferentes fases, depende de los

siguientes departamentos:

- Materias primas y accesorios: departamento de producción de ACSA.

- Producto base: departamentos de producción y logística de ACSA.

- Producto final: departamento de logística de la dirección de ultracongelados de

NESTLÉ.

Nos encontramos, así, ante una empresa en la que las actividades logísticas están

integradas en las áreas de aprovisionamiento y producción, por un lado, y distribución, por otro. Sin

embargo, no existe una coordinación aprovisionamiento-distribución, ya que ambas actividades son

gestionadas por diferentes departamentos de modo independiente. Por tanto, de aquí se deduce que

en ninguno de los dos sistemas descritos existen rutas que combinen aprovisionamiento y

distribución de forma conjunta. Esta situación, tal como se citaba en el capítulo 3, es común a todas

las empresas de tamaño grande, donde las actividades de aprovisionamiento y distribución se

gestionan generalmente de forma independiente.

Esta situación está prevista que cambie en 1998, con la sustitución de los centros logísticos

de Tarrasa y Alcalá de Henares por uno ubicado en Marcilla. Éste será el lugar que centralice el

total de productos finales de las fábricas congeladoras de NESTLÉ. Esto hará que las funciones

referentes al transporte de producto final se gestionen directamente desde la factoría de ACSA.

2.1. Aprovisionamiento:

Uno de los aspectos más reseñables de ACSA es la no existencia de una política de

integración vertical respecto a los proveedores de materia prima. La gestión de las actividades de

aprovisionamiento se realiza en función del listado de todos los agricultores con que tiene contrato, y

en los que se especifica, el lugar y la extensión del terreno cultivado. Con estos datos, la empresa

hace una estimación de los kilos que va a recoger de cada producto. Así, los contactos con los

agricultores son nulos, por lo que la empresa se limita a recoger sus productos sin que exista, tal

como ocurre en otras empresas congeladoras, una integración vertical entre agricultores y empresa.

Este hecho se reafirma en la no especificación de un departamento propio que permita adecuar la

oferta de materias primas con la demanda de producto final a través de la especificación de fechas

de siembra, seguimiento continuo de los cultivos y coordinación con el proceso productivo en los

períodos de recolección.

La razón de que se construyeran las plantas de Badajoz y Olmedo fue, en parte, a que

permitía que las cosechas de las diferentes verduras tratadas por la empresa fueran más largas.


6

Hay que recordar que, debido al diferente clima, existen diferencias entre los períodos de

recolección de una región a otra (Ministerio de Agricultura, Pesca y Alimentación (1982)). Por su

parte, la diversificación de los centros de elaboración de la materia prima permite que el transporte

de aprovisionamiento sea menor que si se centrara en una única planta. Esto redunda en una mejora

de la calidad de las materias primas, ya que el grado de manipulación es bajo.

2.2. Gestión del inventario de producto base:

D. Sabin Goicolea, director general de ACSA, puso especial énfasis en resaltar que uno de

los principales problemas de esta empresa es la gestión del almacenamiento de producto base.

Esta problemática radica en que la materia prima recibida en fresco debe pasar de forma inmediata

al proceso de producción. Esto obliga a la empresa a eliminar, prácticamente, el almacenamiento de

producto en fresco. Esta situación es similar a la que se da en las empresas conserveras, pero a

diferencia de éstas, el hecho de no mantener un nivel de existencias de materia prima no se plasma

en la necesidad de elaborar sus productos finales durante las campañas de recolección de las

materias primas. Esto viene dado, tal como se detalló en el capítulo 3, por la imposibilidad en las

empresas conserveras de elaborar un producto en curso, tal como el producto base, con un grado

de perecederibilidad menor que el producto final. A su vez, los problemas que acarrea esta situación

en las empresas congeladoras se ven acentuados por los siguientes factores:

- El volumen de producción de una empresa congeladora es, en general, sensiblemente

superior al de una empresa conservera.

- El transporte y almacenamiento del producto base es muy caro, en cuanto requieren

camiones y locales dotados de cámaras frigoríficas.

- La necesidad de recurrir a cámaras frigoríficas hace difícil encontrar locales adecuados

para subcontratar esta función.

- La excesiva manipulación del producto base puede repercutir en una menoscabo de la

calidad del producto final.

Una vez que la empresa elabora el producto base, tiene dos opciones: almacenar dicho

producto o continuar el proceso productivo y elaborar el producto final. Ante esta disyuntiva,

ACSA siempre ha optado por la primera, y mantener únicamente en inventario de producto final

una cantidad equivalente a la demanda de dos semanas. El resto de inventario pertenece a

producto base. La evolución del nivel medio de almacenamiento del producto en curso responde al

gráfico representado en la Figura 3.


7

N i v e l d ee x i s t e n c i a s

T i e m p o

C a p a c i d a dm á x i m a

M a r z o N o v i e m b r e

Figura 3. Evolución tradicional del nivel de existencias de producto base en ACSA.

El nivel de inventario del producto base alcanza su nivel mínimo en marzo, cuando

comienzan las primeras campañas; a partir de esta fecha va aumentando, llegando a su nivel

máximo en noviembre, con la finalización de las campañas. Esto hace que la capacidad de la

empresa para almacenar producto base esté ociosa, aproximadamente, durante la primera mitad

del año. Durante la segunda mitad, la empresa se ve obligada a recurrir al alquiler, bien sea a costo

fijo o variable, de cámaras frigoríficas.

N i v e l d ee x i s t e n c i a s

T i e m p o

C a p a c i d a dm á x i m a

M a r z o N o v i e m b r e

Figura 4. Evolución tradicional del nivel de existencias de producto base en ACSA.

Este problema se ha acentuado en los últimos años, con el aumento de la demanda y de la

absorción de la producción de la planta de Badajoz. Así, se ha pasado de una situación similar a la

representada en la Figura 3, a otra muy distinta, tal como se muestra en la Figura 4.

En esta figura se observa cómo la capacidad de inventario de la empresa se sobrepasa con

facilidad, lo cual obliga a ACSA a recurrir al alquiler de cámaras frigoríficas. Este problema se

acentúa por la dificultada de encontrar locales que permitan el almacenamiento de producto

congelado y su alto coste.

2.3. Actividades del transporte de aprovisionamiento y distribución:


8

Para las empresas congeladoras, el coste del transporte es mucho más importante que para

otras empresas, ya que los productos que comercializan son de bajo valor. Esto hace que el

porcentaje de los costes del transporte sea más alto que en el resto de ramas del sector.

La política de la empresa en el tema del transporte se centra en intentar planificar a largo

plazo, si bien la realidad es que esta planificación es tan sólo orientativa, ya que los ajustes se

confeccionan día a día .

Para hablar del transporte en esta empresa, hay que distinguir entre el transporte de

aprovisionamiento y de distribución. La Figura 5 muestra gráficamente la estructura del transporte

en ACSA.

Centros

de

aprovisio-namiento

Factoría de ACSAen Marcilla

Factoría de ACSAen Peralta

Factoría de ACSAen Olmedo

Factoría de ACSAen Badajoz

Delegaciones(Almacenesregionales)

Clientes

(1) (1) (1)

(2)

(3)

(3’)(4)

Figura 5. Estructura del transporte en ACSA.

a) Transporte de aprovisionamiento:

La gestión del transporte de aprovisionamiento no se ha visto afectada por los cambios

organizativos de la empresa en los últimos años. En este aspecto, hay que diferenciar dos

situaciones diferentes, ambas representadas por el enlace (2) en la Figura .5. Por un lado, en el caso

de las materias primas ubicadas cerca de la factoría, el traslado lo realizan directamente los

agricultores. Por otro lado, cuando los productos se encuentran en lugares más ale jados de la

factoría, la empresa trabaja con transportistas autónomos de la zona. Aunque éstos no tienen una

relación contractual fija con la misma, sí existe la política de trabajar siempre con los mismos

transportistas. El precio se fija por zonas, y en función del tipo de camión (trailer, cuatro ejes, tres

ejes o dos ejes).

La planificación de las actividades de aprovisionamiento se realiza día a día , decidiendo,

por un lado, cuántos camiones va a necesitar y, por otro, las rutas a seguir. En este aspecto hay que

incluir el transporte de producto base, desde las plantas de Peralta, Badajoz y Olmedo, a la de


9

Marcilla. Este transporte se realiza con camiones frigoríficos a través de agencias de transporte

(enlaces (1)).

b) Transporte de distribución:

A partir de la Figura 5 se puede deducir que el sistema de distribución física adoptado por

ACSA responde a un sistema mixto de reparto y de almacenes regionales, representada por las

cuatro delegaciones de Madrid, Barcelona, Sevilla y Málaga. Las tres primeras se instalaron por

motivos de población, mientras que la de Málaga para conseguir una mayor implantación en esa

zona. La razón de que no hubiera delegaciones en el Norte es que la empresa se ha beneficiado en

esta zona de la red de distribuidores de Miko.

Cada delegación está compuesta por:

- Un delegado.

- Uno o dos jefes de equipo.

- Cinco vendedores de equipo.

- Repartidores con camiones.

- Personas para la preparación de pedidos y rutas.

- Un jefe de área, promotor de ventas del área geográfica circundante.

Respecto a la distribución del producto a los minoristas o a las delegaciones, se hacía a

través de dos empresas de transporte (enlaces (3) y (3’)). La razón de que sólo se trabajase con

dos agencias es que el transporte de los productos finales requiere el uso de camiones frigoríficos,

por lo que la oferta de agencias es limitada. En cuanto al transporte del producto final desde las

delegaciones hasta el punto de venta (enlace (4)), se realizaba a través de repartidores con

camiones propios. Estos camiones eran pequeños (4.000-5.000kgs), si bien nunca se agotaba su

capacidad. Las rutas a seguir por los camiones se confeccionaban desde la propia delegación.

Una vez analizadas las actividades de producción, aprovisionamiento y distribución, se

puede observar la ausencia de transporte propio en la empresa. Las razones por las que ACSA

nunca ha trabajado con vehículos de su propiedad son las siguientes:

- Permite no ampliar la plantilla.

- Los costes de personal son menores, ya que sólo cobran cuando realizan los pedidos.

- El hecho de ser una empresa con un volumen de materias primas muy grande hace que

los transportistas le den prioridad frente a las empresas pequeñas, por lo que el riesgo de no

encontrar transportistas en un momento dado es muy pequeño.


10

Sin embargo, el principal motivo por el que los responsables de la empresa nunca se han

planteado gestionar el transporte con vehículos propios es la consciencia de que ACSA no se

dedica al transporte, sino a la elaboración de verduras congeladas. Así, el volumen diario de

producto final que mueve la empresa requeriría tener una flota considerable de vehículos, lo cual

implicaría la creación de un departamento dedicado exclusivamente al uso y gestión de los mismos.

3. ESTUDIOS REALIZADOS: DESCRIPCIÓN Y METODOLOGÍA. El análisis cualitativo de la situación actual de ACSA y de las actividades logísticas nos ha

permitido comprobar que nos encontramos ante una empresa con características muy diferentes a

las utilizadas como campo de aplicación en los dos capítulos anteriores (BAJAMAR y

GUTARRA). Este hecho va a repercutir en la naturaleza del estudio cualitativo a confeccionar en

esta empresa. Dicho trabajo va a estar marcado por tres factores decisivos:

- No existencia de transporte propio en la empresa.

- Situación de transición en ACSA.

- Disponibilidad de datos.

3.1. Aspectos generales:

Durante los meses de agosto, septiembre y octubre de 1995 hubo 51 días en los que se

realizaron repartos de producto final. La Tabla 3 resume las magnitudes y ratios que nos permiten

conocer las características de la distribución de producto final en ACSA.

TABLA 3

ASPECTOS GENERALES DEL TRANSPORTE DE DISTRIBUCIÓN EN ACSA2

AGOSTO -

SEPTIEMBRE3

OCTUBRE TOTAL

TOTAL KILOGRAMOS 2.765.483 2.313.619 5.079.102

TOTAL PESETAS 15.498.716 11.865.632 27.364.348

NÚMERO DE

LOCALIDADES

395 355 750

NÚMERO DE VIAJES 164 140 304

2 Estos datos sólo hacen referencia a una de las dos agencias de transporte con las que trabaja ACSA. De la segunda sólo se obtuvo el dato referente al coste total durante estos meses (10.546.267pts). 3 Se han agrupado los meses de agosto y septiembre, ya que el número de días en los que se realizaron viajes durante agosto fue únicamente de cuatro


11

NÚMERO DE DÍAS 28 23 51

PESETAS/KILOGRAMO 5,60 5,13 5,39

PESETAS/VIAJE 94.504 84.755 90.014

PESETAS/DÍA 553.526 515.987 536.556

LOCALIDADES/DÍA 14,11 15,43 14,71

VIAJES/DÍA 5,86 6,09 5,96

LOCALIDADES/VIAJE 2,41 2,54 2,47

KGMS./LOCALIDADES 7.001 6.517 6.772

KILOGRAMOS/VIAJE 16.863 16.526 16.708

KILOGRAMOS/DÍA 98.767 100.592 99.590

Fuente: Elaboración propia.

A partir de estos datos, se pueden obtener las siguientes conclusiones:

1) Importancia de los costes de transporte de distribución: si suponemos una media de

260viajes/año, y aplicando una regla proporcional, el total de costes de transporte de distribución

supone alrededor de 120 millones de pesetas (2% de los costes totales). A su vez, estos datos

confirman el hecho de que el coste por kilogramo transportado supone entre 5 y 6pts/kg, cuando,

por ejemplo, en GUTARRA era de unas tres pesetas por kilogramo de producto final.

2) Número de viajes por día: la empresa utiliza un número medio de camiones/día de seis, lo

que unido al hecho de que no se han contabilizado los datos de la segunda agencia, da muestra del

tamaño de la flota que necesitaría la empresa en caso de gestionar su actividad con transporte

propio, y la complejidad que ello implicaría.

3) Localidades por viaje : aunque la Tabla 3 nos muestra un dato de 2,47repartos/viaje, esta

cifra es equívoca, en cuanto que se pueden clasificar los viajes en dos tipos: de reparto único y de

reparto múltiple. Así, de los 304 viajes realizados durante los tres meses, 163 fueron de reparto

único, lo que representa más del 53% de los mismos. Estas diferencias se deben al tipo de

destinatarios del producto final: clientes o delegaciones. En el primer caso, los pedidos son de menor

tamaño, mientras que en el segundo se trabaja con cargas completas. De este modo, una de las

ventajas de utilizar delegaciones radica en que facilita la descentralización de parte de la gestión

diaria del transporte de distribución, facilitando la consolidación de las cargas y el diseño de las

rutas.

4) Intensidad de uso de la capacidad de los vehículos: el volumen de carga de un camión

frigorífico es de 20.000kgs. Así, ACSA utiliza, de media, un 83,5% de la capacidad de los vehículos,

lo cual se puede considerar como un uso eficiente de los mismos. Este hecho viene facilitado por la


12

política de delegaciones citada en el párrafo anterior, ya que permite viajes de carga completa

desde la factoría de Marcilla.

5) Ámbito geográfico: las localidades visitadas abarcan el conjunto del territorio peninsular,

si bien Madrid y Barcelona son los destinos principales.

3.2. Planificación en la gestión del reparto de distribución con transporte ajeno:

En este apartado se pretende aplicar técnicas relacionadas con la programación lineal y la

teoría de redes para gestionar de forma eficiente la toma de decisiones tácticas en el ámbito

logístico de ACSA.

3.2.1. Descripción del problema:

La gestión diaria del transporte de distribución se basa en determinar el número de viajes a

realizar y los nodos integrantes de cada uno de ellos. Así, el problema a solucionar cada jornada por

el responsable de esta decisión en ACSA es similar al descrito en el Vehicle Routing Problem

(VRP), con las siguientes características:

- Tamaño de flota desconocido.

- Flota homogénea, en cuanto a la capacidad de los vehículos: el volumen de carga de los

camiones frigoríficos utilizados por ACSA es de 20.000kgs.

- Depósito único.

- Demandas determinísticas.

- Operaciones de reparto.

- Red orientada.

- Objetivo: minimizar distancias.

Al igual que en los capítulos anteriores, se intentó diseñar un programa lineal que ayudara a

la empresa a gestionar sus actividades diarias de transporte y comparar la eficiencia de sus

decisiones con las exactas, obtenidas con la programación lineal.

La estructura del modelo lineal a desarrollar era la siguiente:

- Función objetivo: minimizar la distancia, teniendo en cuenta que las tarifas de las agencias

de transporte están en función del kilometraje.

- Restricciones:

- Satisfacer la demanda de cada centro de distribución.

- No superar la capacidad de los camiones.

- Evitar ciclos que no incluyeran el nodo asociado a la factoría.


13

En principio, el hecho de no tener en cuenta las restricciones referentes al tiempo a recorrer

por cada vehículo, y la no existencia de costes facilitaban la construcción de un programa lineal. Sin

embargo, existían dos dificultades añadidas:

- No se conoce, a priori, el número de vehículos disponibles.

- Cada programa lineal debería incluir, de media, más de catorce centros de

distribución (ver Tabla 3).

El primer problema se podría resolver fijando un número de vehículos superior a los

necesarios (seis, como media), ya que la empresa puede recurrir a todos los vehículos que necesite:

las agencias no le imponen ninguna limitación de vehículos. Sin embargo, el segundo problema tiene

una resolución más difícil, en cuanto afecta al número de variables y restricciones del problema.

Así, el hecho de que el VRP sea un problema NP-completo implica que su complejidad de

resolución aumenta de forma exponencial con el número de nodos integrantes del problema. Esto se

debe, principalmente, a la existencia de ciclos que no incluyen el nodo asociado a la factoría, y que

hacen aumentar de forma importante el número de restricciones específicas para evitar que no se

den en la solución final

Por esto, se decidió que el mejor modo de resolver el problema planteado al responsable de

logística en ACSA era utilizar un algoritmo heurístico que determinara el número de camiones que

iba a necesitar, y el número de nodos a visitar por cada uno de ellos. A su vez, los subproblemas

referentes a las rutas de cada vehículo se resolverán a través del programa lineal asociado al TSP.

Así, este trabajo no debe ser analizado como un medio de comprobar la eficiencia de

las decisiones tomadas por ACSA en su momento, sino adoptar un modelo de toma de

decisiones y determinar el tipo de información obtenida al implementar técnicas de

programación lineal como herramienta de apoyo en empresas con un alto volumen de

negocio y sin transporte propio , hechos que no concurrían en las empresas analizadas en los

capítulos 5 y 6, y una de las razones por las que fue elegida.

3.2.2. Proceso de diseño de rutas:

El proceso de diseño de rutas en ACSA tiene unas características completamente

diferentes a las analizadas en BAJAMAR y GUTARRA. Mientras que en éstas, los responsables

de la gestión de rutas se centran en controlar los viajes de carga completa de las agencias y la

planificación de nodos a visitar por los chóferes y vehículos de la propia empresa, en ACSA su

función se centra en determinar el número de vehículos que van a necesitar cada día y las rutas

que van a tomar. El gran volumen de ventas de la empresa ha hecho que no se hayan podido utilizar

técnicas de programación lineal como herramienta principal, sino que se han aplicado algoritmos


14

heurísticos para obtener soluciones iniciales y a partir de las mismas se ha aplicado programación

lineal para mejorarlas. En concreto, los dos algoritmos que se han manejado son los siguientes:

algoritmo de barrido y algoritmo de Clarke-Wright. En el anexo 1 se detallan sus

características, y las fases a seguir para resolver problemas VRP con cada uno de ellos.

En total, el número de días en que se llevó a cabo este proceso fueron once. En principio,

se pensó aplicar ambos algoritmos en los 51 días de los que se disponían las demandas diarias de

los centros de distribución, pero se optó por implementar únicamente aquellos días de septiembre y

agosto en los que se realizaron viajes con cinco o más localidades, y que, por tanto, permiten la

aplicación de problemas TSP resueltos con programación lineal.

El proceso a través del cual se han resuelto los problemas VRP asociados a la gestión

diaria del transporte de distribución en ACSA está representado en la Figura 6. En el anexo 2 se

detalla el conjunto de nodos que forman parte de cada uno de los días analizados y sus demandas.

Una vez concretados los días a estudiar se construyó la matriz de distancias asociada a cada

jornada (su elaboración se realizó, al igual que en los capítulos 5 y 6, con el programa AUTO

ROUTE EXPRESS). Seguidamente, para resolver los problemas con los dos algoritmos elegidos, se

pasó a las siguientes fases:

- Algoritmo de barrido: representación gráfica.

- Algoritmo de Clarke-Wright: obtención de los coeficientes d1i+d1j-dij, donde:

d1i = distancia del nodo 1 (factoría de ACSA a Marcilla) al centro de distribución i.

d1j = distancia del nodo 1 (factoría de ACSA a Marcilla) al centro de distribución j.

dij = distancia del centro de distribución i al centro de distribución j.


15

Datos del problema: - Nodos intervinientes - Demanda

Matriz de distancias

Representación gráficade los centros de distribución

Obtención de loscoeficientes d1i+d1j-dij

Aplicación dealgoritmo de

barrido

Aplicación dealgoritmo de

Clarke-Wright

Solución (1) Solución (1’)

Aplicación de [PLG3] a la solución (1)

Aplicación de [PLG3] a la solución (1’)

Solución (2) Solución (2’)

Comparación de soluciones

SOLUCIÓN FINAL

Figura 6. Proceso de resolución de problemas VRP con los algoritmos de barrido y de Clarke-

Wright.

La siguiente fase consistió en aplicar ambos algoritmos y encontrar una primera solución

factible. A partir de la misma, se determina el número de vehículos a utilizar y los centros de

distribución a visitar por cada vehículo. Con esta situación, se pasa al diseño de programas TSP


16

para encontrar la planificación óptima de visitas asociada a cada una de las rutas con cinco o más

nodos4, y su resolución a través del modelo [PLG3], desarrollado entre otros, en Moore et al (1993):

Variables de decisión:

x ijk = variables binarias, que toman valor 1 si la ruta óptima incluye un viaje desde el nodo

i al nodo j en la rama k ; de otro modo, la variable tomará valor cero.

Función objetivo:

Min d xij ijkk

n

j

n

(i j)i=1

n

≠==

∑∑∑11

La función objetivo consiste en minimizar la distancia total del viaje, donde dij representa la

distancia del nodo i al nodo j.

Restricciones:

x = jj

n

1 12

1=

∑ (1)

x = (k= , ,....,n- ; i j)ijkj

n

i

n

1 2 3 122

≠==

∑∑ (2)

x = i ni

n

12

1=∑ (3)

x = (i= , ,..., n ; i j Si j= , k=n ; o si k=n, j=ojkk

n

j

n

1 2 3 1 121 ==

∑∑ ≠ ) (4)

x = (j= , ,..., n ; i j Si i= , k= ; o si k= , i=ojkk

n

j

n

1 2 3 1 1 1 11

1

1 =

−

=∑∑ ≠ ) (5)

x x ( j = , ,..., n ; i jj jp1 1 2 2 3 = )p =2

n

∑ ≠ (6)

x x ( j = , ,...., n ; i j ; k = , ,..., n- )ijk jpki

n

= p =2

n

+=

≠∑∑ 12

2 3 2 3 2 (7)

x = x ( j= , ,...,n ; i j)ijn j ni

n

−=

≠∑ 1 12

2 3 (8)

La justificación de estas restricciones es la siguiente:

4 No se aplicó en los casos con tres y cuatro nodos porque en éstos se podía hallar la solución óptima de forma más rápida, obteniendo todas las combinaciones posibles, y eligiendo la mejor.


17

(1), (2) y (3): Este conjunto garantiza que cada uno de los n nodos es visitado sólo una vez,

comenzando y finalizando el viaje en el nodo 1.

(4): Asegura que de cada nodo va a salir exactamente un arco en la solución final.

(5): Asegura que de cada nodo va a llegar exactamente un arco en la solución final.

(6), (7) y (8): Estas restricciones garantizan que si la rama k finaliza en el nodo i, la rama

k+1 bebe comenzar en el mismo nodo j.

El total de variables y restricciones según el número de nodos se muestra en la Tabla 4.

TABLA 4

TAMAÑO DEL PROGRAMA LINEAL ASOCIADO AL MODELO TSP SEGÚN EL

NÚMERO DE NODOS

Nodos Variables Restricciones

3 7 11

4 18 19

5 44 29

6 90 41

7 162 55

8 264 71

9 408 89

10 594 109

11 830 131


Como se puede observar, el número de variables y restricciones aumenta exponencialmente

con el número de nodos, si bien afecta sobremanera al número de variables.

Con la aplicación de [PLG3] se mejora los resultados obtenidos con los algoritmos de

barrido y de Clarke-Wright y, a su vez, se muestra de forma práctica la relación entre los problemas

VRP y TSP, explicada en el capítulo 4. En el anexo 2 se detalla en qué rutas se llevaron a cabo la

implementación del modelo de programación lineal asociado a la resolución de problemas TSP y las

soluciones obtenidas.

3.2.3. Resultados obtenidos:


18

En la Tabla 5 se muestran las distancias totales asociadas a las rutas diseñadas por la

empresa, y las obtenidas en el proceso descrito en la Figura 6:

- Solución (1): aplicación del algoritmo de barrido.

- Solución (1’): aplicación del [PLG3] sobre la solución (1).

- Solución (2): aplicación del algoritmo de Clarke-Wright.

- Solución (2’): aplicación del [PLG3] sobre la solución (2)

TABLA 5

DISTANCIAS TOTALES ASOCIADAS A LAS RUTAS OBTENIDAS SEGÚN EL

PROCESO DISEÑADO EN LA FIGURA 6 Y LAS IMPLEMENTADAS POR ACSA

DISTANCIAS (KILÓMETROS)

EMPRES

A

ALGORITMO DE BARRIDO ALGORITMO DE CLARKE-

WRIGHT

SOL.

(1)

%

MEJOR

A

SOL.

(2)

%

MEJOR

A

SOL.

(1’)

%

MEJOR

A

SOL.

(2’)

%

MEJOR

A

DÍA 1 1.842 2.491 -35,0 1.794 2,6 1.794 2,6 1.794 2,6

DÍA 2 5.022 5.022 0 5.022 0 5.022 0 5.022 0

DÍA 3 11.582 10.78

2

9,0 10.61

0

8,4 11.03

3

4,7 11.03

3

4,7

DÍA 4 10.321 10.31

2

0 10.15

6

1,6 10.32

1

0 10.29

9

0,2

DÍA 5 8.824 7.080 19,7 7.080 19,7 9.124 -3,4 9.123 -3,4

DÍA 6 10.017 8.954 10,6 8.954 10,6 8.954 10,6 8.954 10,6

DÍA 7 7.484 6.390 14,6 6.390 14,6 6.390 14,6 6.390 14,6

DÍA 8 10.534 9.961 5,4 9.793 7 9.889 6,9 9.799 7

DÍA 9 8.633 8.461 2,0 8.450 2,1 8.461 2 8.450 2,1

DÍA 10 9.637 9.171 4,8 9.171 4,8 10.28

3

-6,7 10.00

3

-6,7

DÍA 11 6.840 6.773 1,0 5.705 16,6 5.705 16,6 5.705 16,6

TOTA

L

90.736 85.39

7

5,9 83.12

5

9,15 90.64

0

0,1 86.57

2

4,6



19

Con estos datos, podemos comparar las soluciones y determinar cuál sería la mejor y si

existen grandes diferencias respecto a las rutas diseñadas por la empresa. En concreto, las

principales conclusiones que se pueden obtener de estos datos son las siguientes:

1) Aunque ambos algoritmos se caracterizan por su sencillez de resolución, el algoritmo de

barrido es de una resolución inmediata, ya que tan sólo es necesario representar en un mapa los

nodos del problema, y realizar el barrido. Por contra, el algoritmo de Clarke-Wright sólo implica la

utilización de un programa de ordenador para hallar las distancias y una hoja de cálculo para

obtener los coeficientes (d1i+d1j-dij). Sin embargo, en empresas no acostumbradas a utilizar este tipo

de técnicas, dichos requerimientos pueden ser suficientes para no decidirse a implementar estas

técnicas.

2) El porcentaje de mejora del total de los once días de las cuatro soluciones obtenidas varía

entre el 9% y el 0,1%, por lo que no todos los métodos dan el mismo resultado. En general, los

resultados obtenidos con el algoritmo de barrido, una vez aplicado los programas lineales asociados

al TSP, es la opción que reporta mejores resultados. De hecho, en todos los caso, la mejor solución

coincide con la solución (2), consecuencia de aplicar el algoritmo de barrido y seguidamente, el

modelo [PLG3].

3) En este trabajo, la aplicación de técnicas de programación lineal como técnica de apoyo

tiene sentido cuando los algoritmos implementados de una solución inicial de forma inmediata y

sencilla, pudiendo ser mejorada con técnicas de programación lineal aplicadas al TSP.

5) Aunque sólo se ha analizado el ámbito de distribución, se podría haber estudiado, a su

vez, el área de aprovisionamiento, pero la falta de datos lo ha imposibilitado. Por tanto, estas

técnicas deben ser vistas como un medio para facilitar la toma de decisiones en la gestión del

transporte, en general.

En este caso, la utilidad de la programación lineal se enmarca en el ámbito exclusivo de la

gestión de rutas, ya que en este caso, la posibilidad de analizar cambios de carácter estratégico en

la gestión de las actividades logísticas no existe.

4. CONCLUSIONES.

Una de las razones por las que se eligió ACSA es que durante los últimos años ha sufrido

una serie de cambios organizativos que han afectado de forma directa a la gestión de sus

actividades logísticas y, especialmente, en el área de distribución. Este hecho nos permite

comprobar dos ejemplos de gestión logística en una misma empresa a lo largo del tiempo: una

correspondiente a una sociedad independiente (hasta marzo de 1996) y otro caso en el que la


20

empresa está integrada en un grupo multinacional. A su vez, el hecho de que nos encontremos con

la empresa del sector que mueve un mayor volumen de negocio y que, a su vez, esté integrada en

un grupo multinacional, hace que las características de esta empresa, la gestión de las actividades

logísticas y la aplicación de técnicas de programación lineal sean completamente diferentes a las

otras empresas del mismo sector.

Las conclusiones se dividen en dos apartados: los referentes a las actividades logísticas en

general y las asociadas al trabajo empírico realizado.

4.1. Conclusiones sobre las actividades logísticas:

1) Percepción de los problemas principales de una empresa congeladora: al igual que en las

sociedades conserveras, la imposibilidad de almacenar materia prima es el origen del problema más

importante de estas empresas. Sin embargo, este hecho no va a repercutir en el inventario del

producto final, sin el en del producto en curso. A su vez, el hecho de que trabaje con productos

congelados va a dificultar la realización de este producto, y va a encarecer su mantenimiento.

2) Gestión de las actividades logísticas en una empresa multinacional: los cambios de

política habidos en ACSA durante los últimos años nos ha permitido comprobar los diferentes

grados de integración con la sede central, y modos de centralizar y descentralizar las actividades de

transporte.

3) La política de distribución se facilita con la existencia de delegaciones, ya que permite la

descentralización de las actividades de transporte y la planificación de viajes de carga completa.

4) El alto número de vehículos utilizados cada día hace que la empresa no se plantee la

utilización de vehículos propios.

4.2. Conclusiones asociadas a la aplicación de la programación lineal:

1) En rutas con un alto número de centros de distribución, la implementación única de

programación lineal para gestionar las rutas de transporte se ve dificultada por la complejidad del

problema, lo que hace que en estos casos, tan sólo pueda ser utilizada como técnica de apoyo.

2) La principal utilidad de del trabajo empírico desarrollado en ACSA es la construcción de

un modelos de toma de decisiones en la gestión de rutas con transporte ajeno basado en un

algoritmo multifásico, apoyado en técnicas heurísticas y de programación lineal.

3) La principal limitación del modelo implementado es doble: por un lado, no permite

encontrar la solución exacta y, por otro, no incluye restricciones asociadas al orden de prioridad de

los pedidos y a las restricciones horarias de los centros de distribución, tal como ocurre en los

modelos VRPTW.


21

4) La aplicación de técnicas cuantitativas para determinar la gestión del transporte de

distribución con agencias puede redundar de forma positiva en los costes de transporte de ACSA y,

en general, de aquellas empresas congeladoras donde la gestión del transporte de distribución se

realiza exclusivamente con agencias. Sin embargo, al trabajar únicamente con transporte ajeno, el

uso postoptimal de [PLG3] es muy limitado, ya que no se pueden comprobar los efectos de cambios

provocados en los costes, variación en la flota.

REFERENCIAS.

Alfaro, J.A. (1998):Análisis de casos en el sector conservero de Navarra. Aplicación de la Programación Lineal en la gestión logística. Tesis Doctoral. Universidad de Navarra.

Faulín, J. y García del Valle, A. (1999): "Monitoring the Applications of the Transportation Problem in Canning Companies using Linear Programming". INFORMS Spring Meeting. Cincinnati (USA). 2-5 Mayo 1999. (Referencia Internet http://mgmt.bus.okstate.edu/cgi-bin/posting/get/presentation429.html.)

Federgruen, A. y Simchi-Levi, D. (1995): "Analysis of Vehicle Routing and Inventory-Routing Problems". Network Routing. Handbooks in Operations Research and Management Science. Vol.8 North-Holland.

CONTRASTACIÓN DE LOS MODELOS DE PROGRAMACIÓN LINEAL CON ... - Oviedo/Trabajos/PDF/57.pdf ·...

Documents

Transcript of CONTRASTACIÓN DE LOS MODELOS DE PROGRAMACIÓN LINEAL CON ... - Oviedo/Trabajos/PDF/57.pdf ·...