Teoria De Grafos Aplicada A Circuitos

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

Aplicaci´n de la Teor´ de Grafos para mejorar
o
ıa
la planificaci´n de rutas de trabajo de una
o
empresa del sector de la distribuci´n autom´tica
o
a
Puchades Cort´s, Vanesa
e
Semacaf M´quinasde Caf´ S.L.
a
e
Correo electr´nico: semacaf@alcoi.com
o

Mula Bru, Josefa
Centro de Investigaci´n de Gesti´n e Ingenier´ de Producci´n
o
o
ıa
o
Universidad Polit´cnica de Valencia
e
Correo electr´nico: fmula@cigip.upv.es
o

Rodr´
ıguez Villalobos, Alejandro
Departamento de Organizaci´n de Empresas
o
Universidad Polit´cnica de Valencia
e
Correo electr´nico:arodriguez@doe.upv.es
o

RESUMEN
En la actualidad, la gesti´n de rutas es un aspecto fundamental en las emo
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 estudia el caso de la empresa Semacaf M´quinas de Caf´ S.L., perteneciente al
a
e
sector de la distribuci´n autom´tica, que quiere evaluar laefectividad de su
o
a
pol´
ıtica actual de rutas y compararla con la pol´
ıtica optima obtenida me´
diante las aplicaciones inform´ticas Grafos y Rutas, basadas en algoritmos
a
pertenecientes a la Teor´ de Grafos.
ıa
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 loscostes anteriormente mencionados, as´ como de
ı
evaluar la pol´
ıtica actual de gesti´n de rutas de la empresa.
o
Palabras clave: Teor´ de Grafos; planificaci´n de rutas; problema del
ıa
o
viajante; sector del vending.
Clasificaci´n JEL: C61; L00.
o
2000MSC: 90B10; 90B90.

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

7

An application of GraphTheory
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 companies 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´quinas de Caf´ S.L. is studied. This company belongs to the
a
e
sector ofautomatic 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 accomplishesthe objectives 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 endiferentes 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 sepuede 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...