PDF de programación - Aplicación de la Teoría de Grafos para mejorar la planificación de rutas de trabajo de una empresa del sector de la distribución automática

REVISTA DE M ´ETODOS CUANTITATIVOS PARA
LA ECONOM´IA Y LA EMPRESA (6). P´aginas 7–22.
Diciembre de 2008.
ISSN: 1886-516X. D.L: SE-2927-06.
URL: http://www.upo.es/RevMetCuant/art21.pdf

Aplicaci´on de la Teor´ıa de Grafos para mejorar

la planificaci´on de rutas de trabajo de una

empresa del sector de la distribuci´on autom´atica

Puchades Cort´es, Vanesa

Semacaf M´aquinas de Caf´e S.L.

Correo electr´onico: [email protected]

Mula Bru, Josefa

Centro de Investigaci´on de Gesti´on e Ingenier´ıa de Producci´on

Universidad Polit´ecnica de Valencia

Correo electr´onico: [email protected]

Rodr´ıguez Villalobos, Alejandro

Departamento de Organizaci´on de Empresas

Universidad Polit´ecnica de Valencia

Correo electr´onico: [email protected]

RESUMEN

En la actualidad, la gesti´on de rutas es un aspecto fundamental en las em-
presas cuya actividad se basa principalmente en el transporte, ya que supone
elevados costes de carburantes, mano de obra, etc. En este art´ıculo, se estu-
dia el caso de la empresa Semacaf M´aquinas de Caf´e S.L., perteneciente al
sector de la distribuci´on autom´atica, que quiere evaluar la efectividad de su
pol´ıtica actual de rutas y compararla con la pol´ıtica ´optima obtenida me-
diante las aplicaciones inform´aticas Grafos y Rutas, basadas en algoritmos
pertenecientes a la Teor´ıa de Grafos.

En este trabajo se aplica el algoritmo del Problema del Viajante, que se
adapta a las caracter´ısticas del problema de la empresa y que cumple los
objetivos de minimizar los costes anteriormente mencionados, as´ı como de
evaluar la pol´ıtica actual de gesti´on de rutas de la empresa.

Palabras clave: Teor´ıa de Grafos; planificaci´on de rutas; problema del
viajante; sector del vending.
Clasificaci´on JEL: C61; L00.
2000MSC: 90B10; 90B90.

Art´ıculo recibido el 24 de julio de 2008 y aceptado el 21 de octubre de 2008.

7

An application of Graph Theory

to improve the planning of work routes

for a company in the vending sector

ABSTRACT

Currently, the routing management is an important aspect in those com-
panies whose activity is mainly based on the transport, since it involves
high costs of fuel, manpower, etc. In this paper, the case of the company
Semacaf M´aquinas de Caf´e S.L. is studied. This company belongs to the
sector of automatic distribution and pursues to evaluate the effectiveness of
its current policy about planning routes and to compare it with the optimal
policy obtained through the software applications, Grafos and Rutas, based
on algorithms belonging to Graph Theory.

In this paper, the Traveling Salesman Problem (TSP) is applied, due to
the characteristics of the problem and because it accomplishes the objec-
tives of minimizing the previously mentioned costs, as well as evaluating the
current policy of routing management of the company.

Keywords: Graph Theory; routing planning; travelling salesman problem;
vending sector.
JEL classification: C61; L00.
2000MSC: 90B10; 90B90.

8

1 Introducción
Actualmente, la Teoría de Grafos permite esquematizar y resolver muchos problemas en
diferentes campos de la ciencia y la tecnología. En particular, también se viene
utilizando dicha teoría para modelar y resolver distintos problemas referidos a la
eficiencia del transporte.

Los problemas de rutas de vehículos o de distribución física de mercancías desde
almacenes a clientes aparecen en la literatura científica como Vehicle Routing Problems,
o más comúnmente como VRP. También se puede encontrar, aunque en menor medida,
referencias como Vehicle Scheduling Problems. En términos generales, un problema de
rutas de vehículos consiste en determinar las rutas de un conjunto (o flota) de vehículos
que deben iniciar un recorrido (y finalizarlo) en los almacenes (o depósitos) para
atender la demanda de servicio de un conjunto disperso de clientes sobre una red.

El transporte es uno de los sectores que más aporta a la generación de riqueza
(desde hace años, por encima del 5% del valor añadido bruto nacional de España). El
transporte por carretera muestra un comportamiento netamente superior al resto de los
modos y actividades de transporte (ferroviario, marítimo y aéreo) en cuanto a
generación de valor por parte de los operadores españoles. Por el contrario, el sector del
transporte está integrado en su mayoría por pequeñas empresas, con desigual situación
frente a la formación de sus trabajadores. Una gran parte del tejido empresarial se
mantiene con estructuras anticuadas en su funcionamiento y la formación no forma
parte de su cultura. Según Ministerio de Fomento (2001), el equipamiento informático
del sector es escaso y su hábito de uso mínimo.

En este artículo se expone el método actual de gestión de rutas llevada a cabo
por la empresa objeto de la aplicación: una empresa de vending, cuyo negocio consiste
en la distribución de productos de consumo para máquinas expendedoras automáticas
(aperitivos, café, bebidas y refrescos, etc.). Como otras pymes, esta empresa está sujeta
a la incertidumbre del mercado (en términos de consumo, coste de los combustibles,
complejidad de planificación, etc.) y le resulta particularmente interesante la integración
de las herramientas más adecuadas para la resolución de sus problemas de gestión de
rutas. En concreto, el caso real presentado servirá para demostrar cómo las técnicas de
investigación operativa relativas al cálculo de rutas y el uso de tecnologías de la
información pueden ayudar a contrarrestar los desequilibrios existentes entre la
importancia del sector y su capacidad-calidad de servicio.



9

Para ello, en este trabajo fue necesario analizar todos los factores que se tienen
en cuenta a la hora de elaborar las rutas diarias de cada operario: la planificación inicial
de las rutas llevada a cabo por el jefe de taller y la encargada de control y gestión de los
equipos, así como los cambios llevados a cabo por los operarios en esta ruta decidiendo
el orden de las visitas en base a diferentes factores no considerados en la determinación
de la ruta inicial, tales como: el consumo diario actual del cliente, la zona geográfica, las
necesidades específicas del cliente, la comodidad, el tráfico, etc.

Este estudio pretende acercar a las pymes la utilidad y bondad de las técnicas de
investigación operativa (en ocasiones más próxima a la investigación científica pura que
a la realidad cotidiana de las empresas). Una de las aportaciones de esta investigación es
cuantificar el grado de mejora potencial en términos de reducción de costes en una
empresa del sector de la distribución (vending). Además, en esta ocasión se utilizará un
novedoso software de planificación de rutas y gestión de flotas.

El documento se ha estructurado de la siguiente forma. En la Sección 2 se
resumen los modelos principales basados en la Teoría de Grafos con los que puede
afrontarse el problema tratado en la presente publicación y otros similares; además, se
justifica la selección del modelo usado y su implantación en la empresa. La Sección 3
sirve para comentar brevemente las herramientas utilizadas para la obtención de la ruta
óptima. La Sección 4 describe el caso de estudio; una primera parte se dedica a la
planificación actual de las rutas de trabajo de la empresa y después se plantea la
propuesta de mejora para la planificación de rutas actual de la empresa. Finalmente, en
la Sección 5 se exponen las conclusiones obtenidas a lo largo de este trabajo y las líneas
futuras de actuación.

2 Revisión de modelos basados en la Teoría de Grafos
Los historiadores de la ciencia y de las matemáticas establecen el inicio de la Teoría de
Grafos con el trabajo de Euler (1736). En 1852, Francis Guthrie formuló el problema de
los cuatro colores para colorear un mapa cartográfico. Este problema puede considerarse
como el más famoso y productivo de la Teoría de Grafos e hizo que un gran número de
matemáticos, tales como Cayley, Hamilton, De Morgan, Kempe, Tait o Ramsey, se
preocupasen por estudiar y desarrollar esta teoría. Sin embargo, se tardó más de un siglo
en demostrar su resultado (Appel y Haken, 1977a,b), lo que requirió del uso de
ordenadores potentes para su consecución. Por su parte, Hierholzer (1873) proporcionó
una caracterización de los grafos denominados eulerianos como aquellos que son



10

conexos y todos sus nodos tienen valencia par. No obstante, el término “grafo” es
introducido por primera vez en el trabajo de Sylvester (1878). A continuación se revisan
los modelos correspondientes a dos grandes grupos de problemas basados en la
programación lineal.

Por una parte, están los problemas de transporte, asignación y transbordo, que

forman parte de los problemas de flujo de red (Taha, 2004):

- Problema de transporte: trata una situación en la cual se envía un bien desde uno o
varios puntos de origen hasta uno o varios puntos de destino con el objetivo de
determinar la cantidad enviada, satisfaciendo al mismo tiempo las restricciones de la
oferta y la demanda, y minimizando el coste total del envío. Este problema también
se caracteriza por suponer que el coste de envío en una ruta determinada es
directamente proporcional al número de unidades enviadas en esa ruta. En lo
referente a su resolución, se utiliza el algoritmo de transporte. El algoritmo de
transporte es un método de resolución para problemas de transporte que emplea el
método simplex. La segunda fase del algoritmo (es decir, obtener una solución
básica inicial del problema) utiliza habitualmente alguno de estos tres métodos
(Winston, 2005): método de la esquina noroeste; método del coste menor; y método
de aproximación de Vogel