DISEÑO DE UN MODELO DE RUTEO DE VEHICULOS PARA EL

ABASTECIMIENTO DE COMBUSTIBLE EN UNA EMPRESA

PRESTADORA DE SERVICIO PUBLICOS EN EL MUNICIPIO DE
CALI
Esta propuesta está enfocada a la optimización del recorrió en el abastecimiento de combustible de los
vehículos en la zona urbana del municipio de Cali, donde se puede ver representado en el plan de rutas
diseñado mediante la metodología propuesta del problema del viajante, que se caracteriza por buscar un
adecuado recorrido de los carros obteniendo una distancia total mínima, teniendo en cuenta las vías y entre
otros aspectos relevantes.

JULIO CESAR MAMBUSCAY TERAN1, DIEGO FDO HURTADO MONTAÑO2.

RESUMEN

El trabajo desarrollado busca optimizar el recorrido que debe realizar los vehículos de la empresa prestadora
de servicio público en el casco urbano del municipio de Cali para abastecer combustible , Valle del Cauca,
mediante un modelo de tabla dinámica que representa las principales características de las rutas actuales de
abastecimiento que tiene la empresa prestadora de servicio público en municipio de Cali , mediante la
aplicación del Api Google Maps, el cual se busca obtener una solución en términos de minimizar la distancia
total y el tiempo total recorridos durante el abastecimiento de combustible, comparando los resultados
obtenidos versus los resultados del sistema actual que tiene la empresa prestadora de servicio público en
municipio de Cali, referente a la distancia total y tiempo total recorridos.
El estudio va contar tres etapas principales: En la primera etapa se va realizar un diagnóstico al sistema actual
de abastecimiento de combustible de los vehículos de la empresa prestadora de servicio público, donde se va
hacer un diagnóstico de las principales causas de sistema mediante tabla dinámica que muestra cada cuánto
van abastecer los vehículos y cuáles son las estaciones de servicio más utilizadas por los conductores. La
segunda etapa se va realizar un diseño de la estructura del modelo de ruteo de la empresa prestadora de
servicio, cual va calculando cada una de las distancias de los recorridos de los vehículos que arranca desde su
punto de pernocta hasta la estaciones de servicios más cercanas, evidenciando que la operaciones se realiza
muchas veces hasta altas horas de la noche y se repiten muchas de las calles en cada uno de los recorridos,
cual se hará por Google Maps. La tercera etapa va consistir en la programación, donde se va logra aplicar el
método de k-vecino más cercano para generar las posibles rutas de acuerdo al punto de pernocta a la estación
más cercana, Luego se aplicó el api google Maps para buscar cuál de las rutas generadas por el Application
Programan Interface era la mejor. Para la solución de las rutas de cada uno de los recorridos de la zona urbana
del municipio de Cali. Algunas condiciones que se ponen es que siempre el conductor utilice la misma ruta que
le asignes a cada punto de pernocta a la estación de servicio más cercana.

Palabras clave: Investigación de operaciones, logística, transporte, modelo, distribución, optimización,

heurísticas, Metaheurísticas, ruteo, Api de Google Maps, método, Estaciones de servicio, pernocta.

1
Ingeniero Industrial con práctica en el área de Administración, producción y calidad con habilidades para dirigir,
coordinar y supervisar personal, al frente de la realización y control de presupuestos, manejo de inventarios,
documentación de procesos, altamente comprometida integra y responsable, con habilidades para el uso de sistemas y
tecnologías de información, análisis de datos, indicadores de gestión.
2
Ingeniero Industrial con práctica en el área de Administración, producción y calidad con habilidades para dirigir,
coordinar y supervisar personal, al frente de la realización y control de presupuestos, manejo de inventarios,
documentación de procesos, altamente comprometida integra y responsable, con habilidades para el uso de sistemas y
tecnologías de información, análisis de datos, indicadores de gestión.

1
DESIGN OF A MODEL OF ROUTING OF VEHICLES FOR THE SUPPLY OF FUEL IN A PUBLIC SERVICE
PROVIDING COMPANY IN THE MUNICIPALITY OF CALI

ABSTRACT

The work developed seeks to optimize the route that must make the vehicles of the company providing public
service in the urban area of Cali to supply fuel, Valle del Cauca, through a dynamic table model that
represents the main characteristics of current routes supply that the public service provider in the municipality
of Cali has, through the application of Api Google Maps, which seeks to obtain a solution in terms of
minimizing the total distance and the total time traveled during the fuel supply, comparing the results obtained
versus the results of the current system of the public service provider in the municipality of Cali, referring to
the total distance and total time traveled.
The study will have three main stages: In the first stage, a diagnosis will be made to the current fuel supply
system of the vehicles of the utility company, where a diagnosis of the main causes of the system will be
made using a dynamic table. Which shows how often the vehicles will be supplied and which are the service
stations most used by drivers. The second stage will be a design of the structure of the routing model of the
service provider company, which calculates each of the distances of the routes of the vehicles that starts from
its overnight point to the nearest service stations , evidencing that the operations are performed many times
until late at night and many of the streets are repeated in each of the routes, which will be done by Google
Maps. The third stage will consist of programming, where it is possible to apply the nearest k-neighbor
method to generate the possible routes according to the overnight point to the nearest station, then the
Google Maps API was applied to find which one the routes generated by the Application Program Interface
was the best. For the solution of the routes of each one of the routes of the urban area of the municipality of
Cali. Some conditions are that the driver always uses the same route that you assign to each overnight point
to the nearest service station.

Keywords: Operations research, logistics, transportation, model, distribution, optimization, heuristics,

metaheuristico, routing, Google Maps API, method, service stations, overnight...

2
 INTRODUCCIÓN explorar el espacio de soluciones, logrando
finalmente encontrar una solución razonablemente
Actualmente, el tema del abastecimiento de buena necesariamente óptima) en un tiempo
combustible en Colombia es muy disperso, si a esto mucho menor al empleado por los algoritmos
se le agregan aspectos como “infraestructura, exactos.
movilidad, clima, normatividad, orden público y HENAO, en su Pasantía institucional “Diseño de un
competencia del personal”,1 generan más dificultad modelo de ruteo de vehículos para la recolección
establecer un orden al proceso que no afecte de de residuos sólidos en el municipio de Zarzal Valle
manera directa el tema de suministro. del Cauca”, busca optimizar el recorrido que debe
Como se expresa en las obras públicas, en la realizar el vehículo recolector de residuos sólidos
mayoría de los casos, las rutas se diseñan de por el casco urbano del municipio de Zarzal, Valle
forma intuitiva de allí que los tiempos y gastos, del Cauca, mediante un modelo de grafos que
como por ejemplo, en combustible se incrementen. representa las principales características de las
El problema de ruteo de vehículos (VRP) y el rutas actuales de recolección, el cual mediante la
problema de la colonia de hormigas, buscan hallar aplicación del algoritmo del cartero chino se busca
el conjunto de rutas para la distribución o obtener una solución en términos de minimizar la
recolección de mercancías, estas rutas pueden distancia total recorrida durante la recolección de
estar representadas sobre los nodos en el caso del residuos sólidos, comparando los resultados
VRP o los arcos en el caso del problemas del obtenidos versus los resultados actuales de la
viajante (TSP: travelling selesmas problem), que empresa de ASEO PROACTIVA S.A., referente a la
tienen que cumplir con una serie de restricciones, distancia total recorrida.
un tiempo mínimo y una distancia mínima, en
donde los vehículos parten siempre de uno o varios
nodos de origen a los que se le denomina 2. PLANTEAMIENTO DEL PROBLEMA
depósitos. Estos problemas están directamente
relacionados con problemas de la realidad como el El Problema de Ruteo de Vehículos (Vehicle
abastecimiento de combustible de los vehículos. En Routing Problem o VRP, por sus siglas en inglés),
los cuales hallar la mejor ruta, que inicie en la consiste en determinar un conjunto de rutas “para
pernocta, abarque todos los nodos y regrese al una flota de vehículos que parten de uno o más
punto de partida, utilizando un costo o un tiempo depósitos o almacenes para satisfacer la demanda
mínimo. de varios clientes dispersos geográficamente. El
objetivo es entregar la demanda de dichos clientes
1. REVISIÓN DE LITERATURA minimizando la distancia total involucrada en las
rutas”.
Según MEDIORREAL, en su proyecto de grado No tener una planificación de rutas de los vehículos
“Modelo de ruteo de vehículos para la distribución crea un aumento en los tiempos de servicios y
de las empresas Laboratorios Veterland, distancias recorría que no permite a la empresa
Laboratorios Callbest y Cosméticos Marlioü París”. cumplir con lo pactado en el tiempo estimulado esto
Realizar un modelamiento matemático para el ruteo sería perjudicial para la imagen de la empresa.
de vehículos en las empresas Laboratorios La empresa prestada de servicio público en la
Veterland, Laboratorios Callbest y Cosméticos ciudad de Cali tiene una falla en la organización de
Marlioü París (quienes realizan la distribución de la ruta de abastecimiento de vehículos, lo que
sus productos de manera conjunta), con el fin de genera retrasos en la prestación del servicio a los
hacer más eficiente el proceso de distribución de clientes.
las empresas mencionadas, En este caso se va a Por esta razón la empresa prestadora de servicios
tratar el problema de ruteo de vehículos con públicos en la ciudad de Cali necesita establecer un
ventanas de tiempo. Al ser este un problema diseño modelo de rutas para el abastecimiento de
computacionalmente intratable en la práctica para combustible y así ofrecer un servicio de mejor
instancias medianas o grandes, deja como calidad.
alternativa la utilización de técnicas algorítmicas En esta investigación se estudia una variante del
que puedan encontrar soluciones aproximadas en Problema de Ruteo de Vehículos en la cual se
tiempo razonable se utiliza como método general consideran dos objetivos a optimizar: por un lado la
de búsqueda de soluciones una metaheurística minimización la distancia total y el tiempo total en el
basada en una Búsqueda Tabú, que permite recorrió.

3
 además mira cuales de los puntos están cerca sin
3. METODOLOGÍA la necesidad de una coincidencia exacta o un
patrón solo por intuición.
Siguiendo la concepción del tema de estudio dentro
de lo que se llama el ruteo de vehículos, se FIGURA 2. Plano cartesiano del método k-
vecino más cercano.
continúa el trabajo de investigación considerando la
situación como un problema m-TSP (problema de
m vendedores viajeros). Y de manera seguida, se
considera para la recolección dos elementos
importantes como son: distancia total y el tiempo
total. Replanteando el modelo como un problema
de ruteo de vehículos con capacidad, donde el
nodo origen o punto de partida es diferente al nodo
destino o punto de llegada A medida que se va
cambiando el modelo se replantean las técnicas de
optimización a utilizar (api de google Maps) para
obtener una buena solución. A continuación se puede observar las distancias
recorridas por cada uno del punto de pernocta a
FIGURA 1. Mapa de del api google: Red de una estación de servicio, por el método K-vecinos
interconexión de los puntos de pernocta y más cercanos. Posteriormente el beneficio
estaciones de servicio para el diseño de las representado por el ahorro en distancia obtenido.
rutas del Sistema de abastecimiento de En la tabla21 se presentan las distancias K-vecinos
combustible de la empresa prestadora de más cercanos de las operaciones de
servicio público en Cali. abastecimiento de combustible de los vehículos de
la empresa prestadora de servicio público del
municipio de Cali, dando como resultado una
distancia total de 52,40 kilómetros.

FIGURA 3. Resultado del método k- vecino

más cercano.

4. RESULTADOS DE LA INVESTIGACIÓN.
Como se menciona anteriormente en el documento
Para la definición del método k- vecino más la distancia total del método k- vecino más cercano
cercano en el municipio de Cali, se realizaron es de aproximadamente 52.40 Kilómetros teniendo
diferentes análisis, inicialmente por medio de a los puntos de pernocta: planta PTARC, planta
Google Maps se calculó la latitud y longitud del Puerto Mallarino y planta rio Cauca con las
centro de gravedad de cada uno de los punto de distancias más largas por recorrer para llegar a una
pernocta y estación de servicio obteniendo así las estación d servicio.
coordenadas geodésicas
Con estos datos de las coordenadas se insertaron
en un plano cartesiano que se aplicó mediante la
gráfica de Excel en donde se aplicó el método k-
vecino más cercano, el cual consiste en reconocer
los puntos de pernocta y las estaciones de servicio,

4
 el sistema propuesto En donde se aplicaron las
FIGURA 4.Resultado Api Google Maps en mismas metodologías antes mencionadas el
minutos método del K- vecino más cercano y método Api
Google. A continuación se presentan los resultados
obtenidos matriz y tabla.

FIGURA 6.Matriz el sistema actual de

abastecimiento de combustible de la empresa
prestadora de servicio

Como se menciona anteriormente en el documento

le tiempo total del método Api Google Maps es de
aproximadamente 146 minuto teniendo a los puntos
de pernocta: planta PTARC, Planta Puerto
Mallarino, Telefonía Colon, Almagrario TELEFONÍA
TEQUENDAMA y Planta Rio Cali con el tiempo más
largas por recorrer para llegar a una estación d Como se menciona anteriormente en el documento
servicio. la distancia total del sistema actual es de
A continuación se puede observar gráficamente las aproximadamente 6381.3 Kilómetros teniendo a los
distancias recorridas por cada uno del punto de puntos de estaciones de servicio: Autopista,
pernocta a una estación de servicio, en el método Cañaveralejo y Alcázares con mayor uso por los
de api de Google Maps. Posteriormente el beneficio
vehículos en la operación de abastecimiento de la
representado por el ahorro en distancia obtenido y
el ahorro en tiempo de recorrido.se presentan las empresa prestadora de servicio público en
distancias y tiempo de Api Google de las municipio de Cali.
operaciones de abastecimiento de combustible de
los vehículos de la empresa prestadora de servicio FIGURA 7. Tabla del sistema propuesto de
público del municipio de Cali, dando como abastecimiento de combustible de la empresa
resultado una distancia total de 52,40 kilómetro y prestadora de servicio
tiempo total 146 minutos.
FIGURA 5. Mapa de del api google final.

Como se menciona anteriormente en el documento

la distancia total del sistema propuesto es de
5. ANÁLISIS DE LA COMPARACIÓN DE LOS aproximadamente 2894.5 Kilómetros teniendo a los
SISTEMA ACTUAL VS SISTEMA puntos de pernocta: planta PTARC, planta puerto
PROPUESTO Mallarino y planta rio cauca con las distancias más
Este capítulo plantea realizar diversos escenarios
largas por recorrer para llegar a una estación de
con el propósito de inferir acerca del impacto que
servicio.
poseen las variaciones en la operación de
abastecimiento de los vehículos de la empresa Se realizó un análisis de comparativo respecto a la
prestadora de Cali analizando el sistema actual con variación en la distancia total, pudiéndose observar

5
los cambios entre el modelo actual, el propuesto y pernocta y las estaciones de servicio
el cambio mediante el análisis de sensibilidad. mediante el método de localización
geográfica.
 Con la comparación del modelos
1. COMPARACIÓN DE LOS SISTEMAS actual y la aplicación de la experiencia
obtenida; se identificaron los factores
que afectan el proceso de
abastecimiento de combustible en la
empresa prestadora de servicio
Al contrastarlos resultados del sistema actual y público en el municipio de Cali y el
ruteo de los vehículos como son:
sistema propuesto encontramos un ahorro del 45%
cantidad de vehículos, distancias de
en el nuevo sistema que esto equivale 3486.8 km, recorrida y tiempo recorrido, consumos
en la distancia recorrido en el momento de de combustible, restricciones legales.
realización el suministro de combustible de los A partir del análisis de estos factores
vehículos de la empresa prestadora de servicio se definió y diseño un modelo que
público en el municipio de Cali. permite la minimización en la distancia
aplicable al proceso y a la versatilidad
2. CONCLUSIONES de la demanda de la Empresa;
El análisis de los resultados sistema de ruteo contando con la flota necesaria en el
de vehículos empresa prestadora de servicio momento y ubicación estratégica,
público en el municipio de Cali propuesto obteniendo una reducción en la
Se logra desarrollar y moldear el método k distancia recorrida encontramos un
vecino más cercano para escoger la ruta ahorro del 45% km, respondiendo así
óptima desde un punto de origen (pernocta) con las necesidades del cliente para
hasta varios puntos de destinos (estaciones de prestar el servicio.
servicio).  El éxito del modelo radica en la
Al combinar los métodos de k-vecino más versatilidad y aplicación del modelo
cercano y el api de Google Maps logramos con la inestabilidad que presenta en la
identificar la ruta óptima y graficarla en un operación de suministro de
mapa de la ciudad de Cali. abastecimiento de los vehículo de la
 Se establece como variable critica la Empresa prestadora de servicio
distancia total recorrida sobre la público, se logra llevando en cuenta
variable tiempo, por facilidad del varios periodos, así como para el
control del sistema ruteo de vehículos diseño Api Google Maps y
para el abastecimiento de combustible contemplando las restricciones legales
en una empresa prestadora de servicio que existe para vehículos en la ciudad
públicos. de Cali.
 se pudo evidenciar en la investigación 3. BIBLIOGRAFÍA
realizada que implementar el sistema
bajo la variable crítica tiempo ocasiona  ARRANZ DE LA PEÑA, Jorge y PARRA,
8 alteraciones en las rutas óptimas Truyol, Antonio. Algoritmos genéticos.
desde los sitios de pernocta hasta las [Consultado 22 de septiembre de 2017].
estaciones de servicio, y se prevé Disponible en Internet:
mayores alteraciones, ya que esta http://www.it.uc3m.es/~jvillena/irc/practicas/
variable es dependiente a los sucesos 06-07/05.pdf
que ocurren en el día.  ALFONSO, Muñoz Guillermo y BELLO,
 Para lograr el correcto funcionamiento Suarez Magda Viviana. Mejoramiento del
del sistema ruteo de vehículos para el sistema de programación y ruteo de
abastecimiento de combustible en una vehículos de transporte de carga en el
empresa prestadora de servicio trayecto Bogotá - Yopal y municipios
públicos se necesita conocer con alternos caso empresa AUTOLLANOS S.A.
exactitud la ubicación de los sitios de [En línea]. Trabajo de grado Ingeniero

6
 Industrial. Bogotá, D.C: Universidad Libre,  CHACON. Introducción a la investigación
2016. 122 p. [Consultado 28 de septiembre de operaciones. mexico: Pearson
de 2017]. Disponible en Internet: Educación. 2005.
http://repository.unilibre.edu.co/bitstream/ha  87
ndle/10901/10348/PROYECTO%20DE  DANTZIG, G., RANZEL, F. & JOHNSON, S.
%20GRADO%20FINAL (1954). Solution of a large-scale travelling
%2010%20AGOSTO.pdf? salesman problem. Operations Research,
sequence=1&isAllowed=y 2, 393–410.
 BHATT. A model for the optimal allocation  DAZA, J., MONTOYA, J. y NARDUCCI.
of trucks for solid waste management. Resolución del problema de enrutamiento
Waste Management & Research, 14, 87 de vehículos con limitaciones de capacidad
-96. utilizando un procedimiento meta-heurístico
 BERMÚDEZ, Salcedo Diana Paola. de dos fases. Revista EIA, ISSN 1794-1237
Logística de Transporte de Combustible Número 12, p. 23-38. Diciembre 2009
(A.C.P.M.) en la ciudad de Bogotá. Escuela de Ingeniería de Antioquia,
Especialización en Gerencia de Logística Medellín (Colombia).
Integral. Universidad Militar Nueva  GÓMEZ, Toro, Jennifer Andrea; VANEGAS,
Granada. Bogotá D.C. 2014. Recuperado el Castellanos, Juan David y ZULUAGA,
03012018. Disponible en: Gómez, Natalia. Diseño e implementación
http://repository.unimilitar.edu.co/bitstream/ de un algoritmo para dar solución al
10654/13619/1/ARTICULO%20FINAL problema de asignación de salones
%20LOGISTICA.pdf (Timetabling) usando el método de colonia
 CASTAÑEDA Jiménez, Juliana y de hormigas. 2009. [Consultado 05 de
CARDONA, Arias Jaime Andrés. octubre de 2017]. Disponible en Internet:
Implementación del método del ahorro para http://repositorio.utp.edu.co/dspace/handle/
resolver el VRP aplicado al diseño de una 11059/1320
red de logística inversa para la recolección  GONZALEZ, Parra, Yair Fabio y TERAN,
de aceite vehicular usado generado en los Cantillo Luis Alberto. Diseño de un modelo
puntos de acopio ubicados en Pereira. [En para la asignación y ruteo de las bombas
línea]. Trabajo de grado Ingeniero estacionarias desde las plantas de concreto
Industrial. Pereira: Universidad Tecnológica de HOLCIM (Colombia) S.A, zona Bogotá.
de Pereira, Facultad de Ingeniería, 2014 . [En línea]. Monografía para optar el título
135 p. [Consultado 25 de septiembre de de Especialista en Gerencia en Logística
2017]. Disponible en Internet: Integral. Bogotá D.C: Universidad Militar
http://repositorio.utp.edu.co/dspace/bitstrea Nueva Granada, 2010.104 p. [Consultado
m/handle/11059/4395/6587882C346.pdf? 26 de septiembre de 2017]. Disponible en
sequence=1 Internet:
 CASTILLO, Patarroyo, Luis Carlos y http://repository.unimilitar.edu.co/bitstream/
CERQUERA, Bravo Nicolás. Diseño de 10654/482/2/GonzalezParraYair2010
sistema logístico de transporte para la
recolección de materiales reciclados en la
localidad de Engativá con la empresa
Compapeles Milenium. [En línea]. Trabajo
de grado Ingeniero Industrial. Bogotá, D.C:
Universidad Libre, 2012. 87 p. [Consultado
25 de septiembre de 2017]. Disponible en
Internet:
http://repository.unilibre.edu.co/bitstream/ha
ndle/10901/5909/CastilloPatarroyoLuisCarl
os2012.pdf;jsessionid=636A2C64A0786C6
4DD0DC2CF1CDC2EE5?sequence=1