.

Primer Congreso de Logstica y Gestin de la Cadena de Suministro

Zaragoza, 12 y 13 de Septiembre de 2007

HACIA LA OPTIMIZACIN DEL TRANSPORTE. DESARROLLO DE

UN SOFTWARE PARA CLCULO DE RUTAS DE VEHCULOS Y
GESTIN DE FLOTAS
A. Rodrguez
Universidad Politcnica de Valencia
Abstract
The paper presents the last results of this I+D+I project whose main objective is the
development of professional software that solves real problems of fleets of capacited vehicles
(CVRP), management and routing calculation. This software combines three elements
intelligently: geographic information system (GIS), the logistic system information (VRP-XML),
and the mathematical models for combinatorial optimization, that allows solve the routing
problems.
Keywords: CVRP, routing software, VRP-XML
Resumen
El artculo presenta los resultados alcanzados actuales de un proyecto de I+D+I cuyo
principal objetivo es el desarrollo de una herramienta informtica profesional que resuelva
problemas reales de flotas de vehculos capacitados (CVRP), el clculo de rutas, y su
gestin. Este software combina inteligentemente tres elementos: el sistema de informacin
geogrfica (GIS), la informacin del sistema logstico (VRP-XML), los modelos matemticos y
tcnicas de optimizacin combinatoria que conjuntamente permiten resolver los problemas
de rutas para flotas de vehculos.
Palabras clave: CVRP, software, clculo de rutas, VRP-XML
1. LOS PROBLEMAS DE RUTAS DE VEHCULOS (VRP)
1.1 Introduccin
Los problemas de rutas de vehculos o de distribucin fsica de mercancas desde
almacenes a clientes aparecen en la literatura cientfica como Vehicle Routing Problems,
ms comnmente como VRP. Tambin se puede encontrar, aunque en menor medida,
referencias como Vehicle Scheduling Problems. En trminos generales, un problema de
rutas de vehculos consiste en determinar las rutas de un conjunto (o flota) de vehculos que
deben iniciar un recorrido (y finalizarlo) en los almacenes (o depsitos) para atender la
demanda de servicio de un conjunto disperso de clientes sobre una red. Como se ver a
continuacin, las diferentes caractersticas de los clientes, la demanda, los almacenes y los
vehculos, as como de las restricciones operativas sobre las rutas, horarios, etc. dan lugar a
gran nmero de variantes del problema. En la literatura, algunos autores han intentado
clasificar y simplificar la gran variedad de posibles problemas, como por ejemplo los criterios
propuestos por (Bodin y Golden, 1981) y (Desrochers et al. 1990); que intentan reflejar y
ordenar las principales caractersticas en aspectos como: el almacn o depsito, la flota, la
demanda, el servicio y el objetivo a alcanzar. Esta clasificacin de los problemas, ha

facilitado tanto el desarrollo de modelos matemticos y estrategias de resolucin, como la

toma de decisiones por parte de las empresas.
1.2 La red de transporte
La red de carreteras o servicio utilizada para el transporte de bienes, se describe
generalmente como un grafo donde los arcos representan los segmentos o secciones de las
vas, y los vrtices corresponden a las uniones o nodos de la red. En algunos casos los
clientes o los depsitos pueden estar situados en dichos nodos, mientras que en otros casos
pueden estar localizados en un arco del grafo. Los arcos (y por consiguiente el grafo) puede
ser dirigidos o no dirigidos, dependiendo de si pueden ser circulados en un nico sentido o
en ambos (por ejemplo, calles de una nica direccin o de ambos sentidos de circulacin).
Cada arco tendr asociado un coste que puede representar su longitud en distancia, el
tiempo de viaje, o el coste monetario del mismo. Alguno de estos parmetros pueden a su
vez depender del tipo de vehculo o del momento en el que se recorra este arco (por
ejemplo, las condiciones del trfico en un momento dado).
1.3 Los clientes y su servicio
Cada cliente tendr cierta necesidad de servicio o demanda que deber ser atendida por
algn vehculo. Es comn que la demanda sea la necesidad de un conjunto de productos
que ocupan volumen y peso en los vehculos, y como la capacidad de transporte del vehculo
es limitada, es usual que un mismo vehculo no pueda satisfacer la demanda de todos los
clientes. El servicio a los clientes no siempre implica distribuir producto desde el almacn
hacia ellos, tambin puede entenderse que los clientes son proveedores, y por tanto se
tratara de recoger mercanca para aprovisionar un almacn. En el caso de tratarse de una
necesidad de servicio, el cliente simplemente debe ser visitado por el vehculo. Un mismo
vehculo podra (en teora) visitar a todos los clientes. El servicio requerido por el cliente
podra ser tambin el de ser transportado hacia otra ubicacin (servicio de transporte). En
muchas ocasiones se trata de visitar al cliente exactamente una vez, sin embargo, en otros
casos puede aceptarse que su demanda pueda ser atendida de manera fragmentada o por
vehculos diferentes. Los clientes podran tener restricciones de horario, en forma de
intervalos o ventanas de tiempo dentro de las cuales se debe atender su servicio. Tambin
podra tenerse en cuenta no slo el tiempo de recorrido por la red, sino el tiempo de servicio
al cliente (carga y descarga).
Tambin podran existir restricciones de asociacin entre vehculos y clientes, de manera
que determinados clientes slo puedan ser atendidos por determinados vehculos (por
ejemplo, vehculos grandes y pesados que no pueden circular por calles estrechas o el
centro urbano).
1.4 Los almacenes o depsitos
Tanto los productos a transportar (si los hubiera) como los vehculos, suelen estar
localizados en los depsitos (almacenes, centros de trnsito, muelles o cocheras). Es
habitual que las rutas den comienzo y/o finalicen en dichos depsitos. Aunque en algunos
casos es diferente (por ejemplo, el viaje debe finalizar donde pernocta o finaliza la jornada el
conductor). Pueden existir varios almacenes o depsitos con localizacin y otras
caractersticas diferenciadoras (capacidad mxima de servicio o produccin, horario, flota en
origen, etc.). La flota asociada al depsito puede ser conocida o parte del objetivo a

determinar. Debido al tiempo y espacio necesario para preparar y gestionar los vehculos,
podra darse el caso de limitar el nmero de vehculos que operan a la vez en un mismo
depsito (congestin de muelles).
1.5 La flota de vehculos
Los vehculos se definen por un conjunto de atributos, como su capacidad de carga en peso,
en volumen, sus costes asociados, etc. En un vehculo se pueden transportar diferentes tipos
de productos o uno slo, asimismo su contenedor podra estar compartimentado o no. En la
utilizacin de un vehculo se incurre en unos costes fijos por uso, y variables en funcin del
tiempo, distancia u otros parmetros. Cuando los vehculos comparten unas mismas
caractersticas se dice que la flota es homognea, y si son diferentes flota heterognea. El
nmero de vehculos disponibles de una flota puede ser un dato conocido o una variable de
decisin. Es comn que el objetivo sea intentar utilizar la menor cantidad de vehculos y en
segundo lugar minimizar la distancia o tiempo empleado de su ruta. La legislacin o los
convenios laborales pueden imponer restricciones sobre el tiempo mximo que un vehculo
debe estar en circulacin (descanso o relevo de conductores), su velocidad y carga mxima,
e incluso el paso por determinadas zonas de la red. Es interesante en ocasiones intentar
equilibrar las cargas de trabajo de los conductores, el tiempo o carga de los vehculos.
1.6. Las rutas
Los problemas de rutas de vehculos tratan por tanto de determinar la ruta o rutas para cada
uno de los vehculos de la flota cumpliendo con todo el conjunto de restricciones e intentando
alcanzar los objetivos propuestos. La funcin objetivo puede ser por ejemplo: minimizar los
costes fijos, minimizar los costes totales, minimizar el nmero de vehculos requeridos,
minimizar el tiempo total de transporte y/o la distancia total recorrida, minimizar las esperas,
maximizar el beneficio de la operacin, maximizar la funcin de utilidad del cliente, o su
beneficio y satisfaccin. En general en la literatura se asume que un vehculo slo recorrer
una ruta en el perodo de planificacin, pero tambin se pueden encontrar modelos en los
que un mismo vehculo podra participar de ms de una ruta. La siguiente Figura 1
(elaboracin propia) representa un ejemplo tpico de solucin a un problema de rutas.
clientes

RUTA 1

RUTA 2
depsito

RUTA 4
RUTA 3

Fig. 1 Ejemplo de la solucin a un problema bsico VRP (elaboracin propia).

En la figura se puede observar 4 rutas diferentes con origen y destino final en el depsito
central. Los arcos de la ruta solucin deben ser necesariamente arcos de la red de
transporte. Como se ha visto anteriormente, los problemas de rutas son en realidad un
amplio y complejo abanico de casos. Por otro lado, y tal y como subraya (Yepes, 2002), un
caso real se define como resultado de la combinacin de varias de estas caractersticas. El
propio conjunto y variedad de caractersticas origina por explosin combinatoria y enorme
nmero de posibles problemas (cada uno con su casustica concreta).
2. LA INTEGRACIN LOGSTICA
2.1 Objetivos
El desarrollo que se presenta en esta comunicacin tiene como objetivos: facilitar la
resolucin de problemas reales de flotas de vehculos capacitados CVRP, el clculo de rutas,
y su gestin. En este desarrollo informtico se integra inteligentemente tres elementos
(Figura 2): el sistema de informacin geogrfica SIG, la informacin del sistema logstico
(VRP-XML), los modelos matemticos y tcnicas de optimizacin combinatoria que
conjuntamente permiten resolver los problemas de rutas para flotas de vehculos, Toth et al.
(2001 pg. 1-26).

Fig. 2 Pantallas del software desarrollado.

El xito en la gestin logstica depende de la capacidad de integracin (informacin y
sistemas, proveedores y clientes, recursos y decisiones, etc.). Por ello, en este proyecto se
ha prestado especial inters a la integracin necesaria para la optimizacin del transporte, la
toma de decisiones y la gestin de flotas.
2.2 Desarrollo y estructura
La herramienta informtica desarrollada se ha estructurado de un modo abierto pero
integrado. Todo el cdigo fuente ha sido programado en Microsoft Visual Studio .NET, esto
permite integrar fcilmente mdulos y nuevas funciones programadas en diferentes lenguaje
de programacin .NET, a la vez que garantiza su funcionamiento en nuevas plataformas
como Windows Vista, Windows 64-bit, Windows Mobile. La estructura del programa es
modular, flexible y escalable (Figura 3). La programacin orientada a objetos, y su estructura
basada en clases y libreras (.dll), permite fcilmente incorporar nuevas funciones y anlisis,

o mejorar los existentes.

Como se puede observar en la siguiente figura la herramienta combina e integra tres
elementos: el sistema de informacin geogrfica SIG, la informacin del sistema logstico
(VRP-XML) y toda la informacin del sistema empresarial necesaria para crear y resolver los
modelos matemticos mediante tcnicas de optimizacin combinatoria.
2.1.1 El sistema de informacin geogrfico (SIG)
El SIG es una coleccin organizada de datos geogrficos que permite analizar y desplegar
en todas sus formas la informacin geogrficamente referenciada. En este caso el SIG se
utiliza para las siguientes funciones:
Geo-localizacin (geocoding) de los depsitos, clientes y proveedores
Anlisis de la red de transporte, red de carreteras, sentido de circulacin de las vas,
trfico, etc.
Clculo de itinerarios, caminos mnimos (en tiempo y/o distancia)
Representacin y seguimiento (tracking) de las rutas para cada vehculo
El modo en el que se realiza la conectividad con el sistema de informacin geogrfica (SIG),
su vnculo con el clculo, el anlisis y la gestin del proceso logstico es una de las
aportaciones clave en este trabajo. A diferencia de otro software existente en el mercado,
ste no trabaja con informacin de toda la red SIG, sino que a partir de la informacin VRPXML y tras un proceso de consultas se construye un grafo reducido que slo contiene la
informacin de la red necesaria en el proceso de modelado y resolucin del problema CVRP.
Esto mejora notablemente la eficiencia de la gestin de la informacin y reduce los tiempos
computacionales necesarios.

Fig. 3 Estructura y principales componentes del proyecto Rutas.

2.1.2 VRP-XML y el sistema de informacin empresarial
Para el modelado, resolucin y anlisis de este tipo de problemas, es necesario gestionar
una enorme cantidad de informacin: datos sobre las caractersticas de la flota de vehculos,

los planes de ruta, los cargamentos, depsitos y recogidas, informacin geogrfica, las
restricciones y la funcin objetivo, etc. Tal y como se explica en Rodrguez (2006), se trata de
una estructura de etiquetas VRP-XML que define los elementos de un documento que facilita
el intercambio de datos en el contexto de los VRP (Vehicle Routing Problems). Todava no
existe un estndar consolidado para el intercambio de datos en este mbito de trabajo, pero
la estructura propuesta ha demostrado su validez en la aplicacin empresarial de este
proyecto. El mdulo VRP-XML se enlaza fcilmente con el sistema de informacin
empresarial (ERP), compartiendo datos de: clientes, servicios y rdenes de trabajo,
informacin sobre costes de operaciones, disponibilidad e informacin sobre los recursos
logsticos (flota de vehculos), ventanas horarias y otro tipo de restricciones, etc. Adems
este tipo de problemas son dinmicos y cambian en el tiempo, sus datos deben de estar
soportados por una estructura flexible, capaz no slo de atender tal cantidad de informacin
segn los actuales requerimientos de la empresa, sino tambin los futuros del sistema
logstico (ampliacin del nmero de clientes, de la flota de vehculos, nuevas restricciones,
etc.).
2.1.3 Modelado y resolucin CVRP
Como es conocido, los problemas CVRP son complejos de modelar y de resolver, ya que
pertenecen al tipo de problemas NP-completo. El gestor y decisor del sistema logstico
demanda una herramienta (Figura 4) que le haga transparente el proceso de modelado y
optimizacin (o clculo de soluciones factibles), pero que en cambio le permita explorar con
detalle la bondad de la soluciones ayudndole en su toma de decisiones y le facilite la
gestin (rdenes de trabajo, control, etc.).
Para poder resolver la gran variedad de tipos de problema VRP, el programa rene y
combina diferentes heursticas y modelos de optimizacin. El usuario podr elegir el tipo de
anlisis a realizar (Tabla 1) y el software automticamente validar la integridad de los datos
y el problema planteado. Hay que subrayar que una de las aportaciones ms importantes de
este proyecto ha sido el desarrollo de las rutinas de modelado, y del cdigo fuente necesario
para la resolucin de los problemas de programacin lineal entera mixta. Esto es, el
programa es capaz de realizar de manera transparente al usuario y en pocos instantes, el
modelo de programacin lineal necesario para la resolucin y el anlisis del problema, que el
usuario haya definido en el grafo y en su estructura de meta-datos.

Anlisis
DMP

Descripcin
Delivery Man Problem: Ciclo Hamiltoniano con inicio y fin en una
localizacin seleccionada.
SHP
Shortest Hamiltonian Path: Camino Hamiltoniano con inicio en la
localizacin A y fin en la B.
TSP
Traveling Salesman Problem: Problema del Viajante de Comercio.
m-TSP
Problema de los m Viajantes de Comercio.
CVRP
Capacited Vehicle Routing Problem: Problema de Rutas con Vehculos
Capacitados. Funciones objetivo: mn. distancia, mn. nm. vehculos,
mn. coste total (coste variable + coste fijo flota), etc.
Extensin del CVRP con limitaciones en el mximo nmero de clientes a
visitar, y la mxima distancia (o coste) requerido. CVRP single customer
routes - con o sin la restriccin de visitar 1 slo cliente por vehculo
DCVRP
Distance-Constrained Capacited Vehicle Routing Problem: Problema de
Rutas con Vehculos Capacitados con limitaciones de distancia y/o
clientes.
BPP
Asignacin de vehculos a clientes para optimizar el uso de la flota y
minimizar el coste de envo por unidad de producto.
VRPTW
VRP with Time Window: Problema de Rutas de Vehculos Capacitados
con Ventanas de Tiempo. Tiempos de servicio (recogida y/o entrega).
En la actualidad se estn implementando extensiones a este anlisis.
Tabla. 1 Anlisis VRP implementados.
El problema CVRP bsico trata de determinar los recorridos de k vehculos de capacidad Ck
que partiendo de un origen comn deben pasar por un conjunto de lugares de inters
(clientes) para recoger o distribuir mercancas segn una demanda di, y volver de nuevo al
origen de manera que la distancia total recorrida (el coste o el tiempo empleado) por el
conjunto de vehculos sea mnima.
A continuacin se muestra el modelo de tres subndices (1). Para un conjunto i, j de nodos
del grafo, se expresa la funcin objetivo que intentar minimizar el coste total de todos los
arcos recorridos en la solucin. La variable binaria Xijk indica si el vehculo k tendr una ruta
utilizando el arco ij. Mientras, la variable binaria Yik indica si el nodo i con demanda di ser
atendido por el vehculo k con capacidad Ck. Como se puede ver en la primera restriccin
cada nodo cliente deber ser atendido nicamente por un vehculo (en el problema bsico
CVRP). En cambio del nodo origen 0 pueden partir todos los vehculos K de la flota. A
continuacin aparecen las restricciones de continuidad donde el vehculo que llegue a un
cliente deber tambin partir desde l. Tan slo faltan las restricciones de capacidad: la
demanda atendida por un vehculo (suma de di) no debe exceder su capacidad Ck. En el
caso en que todos los vehculos tengan la misma capacidad, los valores Ck sern iguales.
Por ltimo aparecen las condiciones de Miller y Tucker (1960), y la definicin de variables
binarias.

(1)

En el tipo de problema ms sencillo no se tiene en cuenta el horario de entrega o recogida

en cada lugar de inters (ventanas horarias - VRPTW). La funcin objetivo podra ser:
minimizar el nmero total de vehculos (o conductores) requeridos para dar servicio a todos
los clientes, minimizar los costes fijos asociados con el uso de los vehculos (o los
conductores), minimizar el coste total de transporte (coste fijo ms variable de la ruta),
balancear las rutas (por tiempo de viaje o carga de vehculo), minimizar las penalizaciones
asociadas para un servicio parcial a los clientes, etc.
Para resolver los modelos de optimizacin, se cuenta con la ayuda de lp_solve; se trata de
un solver de programacin linear entera mixta de licencia libre (LGPL - GNU lesser general
public license). Este solucionador resuelve modelos de programacin lineal (mixta) puros,
con variables enteras/binarias, conjuntos semi-continuos y special ordered sets (SOS). No
tiene lmite en el tamao de los modelos y acepta ficheros de entrada en formatos .lp y .mps.
Tambin se puede usar la librera del solver para ser llamada desde lenguajes de
programacin como: C, VB, .NET, Delphi, Excel, Java, etc. Est escrito en ANSI C y puede
ser compilado para distintas plataformas como Linux y Windows. Tambin se puede
encontrar LUSOL, un sistema avanzado de factorizacin LU y resolucin de ecuaciones
integrado en lp_solve v5 en el paquete bfp. Tambin es importante citar la utilizacin de
ficheros de datos auxiliares que son tiles para la resolucin de problemas de rutas.
Actualmente se utilizan dos formatos de fichero para la definicin de modelos de
programacin lineal entera mixta (MILP), se trata de estndares (.lp, .mps) que sirven de
pasarela entre la aplicacin y el solucionador de problemas de optimizacin (Solver
lp_solve).

Fig. 4 Integracin de la informacin en el software Rutas.

2.1.4 Otras funciones
Adems de todo lo anterior, el software integra todo un conjunto de funciones que facilita la
interaccin con otros elementos de la cadena logstica (proveedores y clientes, vehculos,
otros sistemas: ERP-CRM, etc.) como por ejemplo:

Localizacin de clientes, centros de trnsito y almacenes (geocoding, waypoints)

Seleccin optimizada de vehculos (flota propia vs. subcontratada)
Definicin de zonas de distribucin
Planificacin de rutas de reparto y aprovisionamiento
Clculo y gestin de distancias, tiempos y costes de transporte
Definicin y anlisis de ventanas horarias de entrega o recogida
Seguimiento de vehculos (GPS tracking)
Intercambiar informacin sobre localizaciones e itinerarios con su navegador GPS
Generacin de mapas, mejora de la documentacin logstica
Exportar informacin sobre localizaciones e itinerarios para otro software cartogrfico
(Google Earth, OziExplorer, GPS Visualizer, CompeGPS, Google Maps, GPS
TrackMaker, etc.)

3. PRIMEROS RESULTADOS Y CONCLUSIONES

En este proyecto de accin-investigacin se est teniendo la oportunidad de validar el
desarrollo mediante la resolucin de problemas reales en empresa. Por cuestiones de
confidencialidad no ha sido posible mostrar todava en este artculo informacin detallada al
respecto, pero cabe sealar la gran aceptacin y bondad de los primeros resultados
aportados por esta herramienta en las empresas piloto que han participado del proyecto

(transporte internacional, distribucin farmacutica, vending, sector agro-alimentario).

Como se puede observar en la siguiente (Figura 5), la herramienta est teniendo una gran
acogida y muy buena valoracin entre las empresas piloto. Un 69,23% de las empresas
consiguieron mejoras econmicas en sus procesos de transporte del orden del 15-30%
respecto a su situacin inicial.

Fig. 5 Resultados de la experiencia piloto del software Rutas.

En la actualidad el proyecto de investigacin y desarrollo sigue en desarrollo. Se est
abriendo el proceso de validacin y financiacin a nuevas empresas-piloto. Adems se estn
programando nuevos modelos MILP para otros problemas VRP y algunas heursticas para
casos concretos. Peridicamente se actualiza el solver de optimizacin con nuevas mejoras.
Adems se est mejorando y ampliando el mdulo de generacin de informes y anlisis de
las soluciones. En prximos artculos se espera poder presentar resultados ms detallados y
extensos sobre la valoracin y utilizacin de esta herramienta en las empresas-piloto
REFERENCIAS
Bodin, L., Golden, B., 1981. Classification in Vehicle-Routing and Scheduling, Networks, 11
(2), 97-108.
Desrochers, M., Lenstra, J. K., Savelsbergh, M. W. P., 1990. A Classification Scheme for
Vehicle-Routing and Scheduling Problems, European Journal of Operational Research, 46
(3), 322-332.
Miller, C. and Tucker A., Zemlin R., 1960. Integer programming formulations and traveling
salesman problems, J. of the ACM, 7 326-329.
Rodrguez, A., 2006. VRP-XML: Lenguaje de marcas extensible para los problemas de rutas
de vehculos. X Congreso de Ingeniera de Organizacin, Valencia.
Toth, P., Vigo, D., 2001. An overview of vehicle routing problems. In the Vehicle Routing
Problem. Ed. Society for Industrial and Applied Mathematics, Philadelphia.
Yepes, V., 2002. Optimizacin heurstica econmica aplicada a las redes de transporte del
tipo VRPTW, Escuela Tcnica Superior de Ingenieros de Caminos, Canales y Puertos,
Universidad Politcnica de Valencia.

CORRESPONDENCIA
Prof. Alejandro Rodrguez Villalobos
Universidad Politcnica de Valencia
EPSA - Plaza Ferrndiz-Carbonell, 2
E-03801 Alcoy Alicante (Espaa)
Tfno: +34 96 652 84 89
Fax: +34 96 652 84 89
Email: [email protected]