Esteban López Milán II

Vista previa del material en texto

1 
 
MODELO DE SIMULACIÓN MATEMÁTICA PARA VEHÍCULOS DE REPARTO Y SU 
SOLUCIÓN MEDIANTE EL MICROSOFT EXCEL. 
 
MATHEMATICAL MODEL SIMULATION TO ROUTING VEHICLES. SOLUTION 
THROUGH MICROSOFT EXCEL. 
 
Dr. C. Esteban López Milán, elopez@uho.edu.cu, Departamento de Ingeniería Mecánica, 
Universidad de Holguín. 
 M. Cs. José García Reyes, garcia@mayari.emcomed.cu, EMCOMED Mayarí. 
 
Resumen. 
Esta investigación partió del objetivo de elaborar un modelo matemático para proveer de 
adecuadas rutas a vehículos de reparto, la solución se implementó a través de la 
herramienta Solver de Microsoft Excel. La función objetivo del modelo minimiza la suma 
de las distancias a recorrer en un ciclo cerrado, pasando una única vez por cada nodo. 
Se escogió el proceso de distribución de medicamentos en EMCOMED Mayarí para 
validar el modelo, como parte de un convenio de colaboración existente entre la 
Universidad de Holguín y la Empresa Provincial de Distribución de Medicamentos. Al 
comparar la solución obtenida por esta vía, con la que aportan otros métodos, se 
demostró que el método de simulación matemática aporta la mejor solución. Como 
resultado, se ha dotado a dicha empresa en su misión de la distribución de 
medicamentos, con una eficaz herramienta que le permite elaborar rutas ágiles y al menor 
costo posible. El modelo matemático, único de su tipo en Cuba, es aplicable en cualquier 
tipo de transportación en la que se necesite elaborar una ruta óptima de reparto. 
Palabras clave: Modelo de reparto, Ruteo de vehículos. 
 
Summary 
This research stat on the objective to create one mathematical model to offer adequate 
routes to routing vehicles, the solution was found by Solver tool of Microsoft Excel. The 
objective function of the model minimizes the addition of cover distances in a closed cycle, 
crossing once time by each node. It chose the distribution process of medicines in 
ENCOMED Mayarí to validate the model, supported in a collaborating agreement among 
University of Holguín and Distributing Provincial Enterprise of Medicines. Comparing the 
solution obtained by this way with solutions offered by other methods, it was demonstrated 
that the mathematical simulation is the best. As result, this enterprise has an effective tool 
to elaborate agilest routes and lowest cost, to distribute medicines. The mathematical 
model, who is unique in its type, is applicable in any kind of transportation that needs to 
elaborate optimal distribution routes. 
Keywords: routing model, routing vehicles. 
 
Introducción. 
Entre los numerosos convenios de colaboración que la Universidad de Holguín tiene con 
empresas del territorio, está el vigente con la Droguería Holguín, subordinada a la Unidad 
UEB Empresa Comercializadora y Distribuidora de Medicamentos (EMCOMED). Este 
convenio ha permitido que numerosos estudiantes de pregrado y posgrado se vinculen a 
esta entidad y desarrollen allí sus trabajos de diploma, proyectos de curso y tesis de 
mailto:elopez@uho.edu.cu
mailto:garcia@mayari.emcomed.cu
2 
 
maestrías, con los cuales dan una respuesta adecuada a los problemas existentes. 
Así lo demuestra la investigación desarrollada por García (2018) en su tesis de maestría, 
la cual abordó la solución a un importante problema de EMCOMED Mayarí, lugar donde 
se desempeña como profesional. EMCOMED Mayarí es una de las empresas cubanas 
donde el problema de crear rutas óptimas, había estado esperando por una propuesta de 
solución. En función de la necesidad planteada, esta investigación se propuso como 
objetivo modelar el proceso de distribución de medicamentos en EMCOMED Mayarí, para 
proveer a la distribución de rutas ágiles y al menor costo posible. 
Similar problema es una de las grandes preocupaciones de las empresas de transporte, 
cuando tratan de establecer una red de distribución que sea lo más eficiente posible para 
atender de forma eficaz a sus clientes y al mismo tiempo, que los costos generados por 
la distribución sean los más bajos posibles. 
Este problema se conoce genéricamente como ruteo de vehículos, y la solución debe 
satisfacer la necesidad de optimizar los recorridos (expresados en kilómetros recorridos 
o litros de combustible consumidos en la transportación), con la condición de que se salga 
de un punto “base” (por ejemplo: un almacén) y al final del recorrido se retorne a este 
mismo punto, habiendo pasado por cada nodo (punto de entrega o recepción de carga) 
una única vez. 
Cuando se trata de decidir rutas en las que la cantidad de nodos es pequeña, 
frecuentemente se opta por el “Método de la fuerza bruta”, que en estas condiciones 
puede aportar buenas soluciones con bajo nivel de cómputo. Cuando el problema supera 
los siete nodos, este método ya no es factible y se puede recurrir al “Método del vecino 
más cercano”, el cual no siempre brinda buenas soluciones y, en ocasiones, distantes del 
valor óptimo. 
El método de modelación matemática con enteros binarios, es la mejor variante para 
encontrar rutas óptimas de distribución. Su principal inconveniente está en que los 
directivos que deben tomar las decisiones, frecuentemente no son especialistas que 
sepan trabajar con modelos matemáticos. Este inconveniente provoca la necesidad de 
crear un software a la medida, mediante los cuales se procese la información y se provea 
de forma transparente al usuario del sistema, con una propuesta óptima para la 
transportación. 
En las fuentes consultadas no se encontraron modelos con similar modo de abordar el 
problema del reparto de medicamentos y forma de procesar, razón por la cual este que 
se abordará puede ser considerado como único de su tipo en Cuba 
 
DESARROLLO 
Varios fueron los inconvenientes iniciales que se presentaron como el hecho de que, 
frecuentemente, las personas que deciden las rutas de distribución de medicamentos no 
están familiarizadas con el uso de softwares profesionales, para procesar modelos 
matemáticos. Esto condicionó la necesidad de elaborar una sencilla interfaz que, de 
forma transparente al usuario, procesara el modelo y mostrara los resultados de forma 
sencilla. 
El tener a mano en el Excel su herramienta Solver, facilitó el proceso de modelación y 
solución sin el inconveniente que representa diseñar un software a la medida. Sin 
embargo, la solución se podría implementar con la condición de que los nodos no 
sobrepasen la cantidad de 12, lo cual la convierte en una buena opción para la mayoría 
de los problemas de reparto a los que se enfrentan las organizaciones. 
3 
 
Otro de los problemas de gran significación fue la inexistencia de una eficiente tabla de 
distancias que permitiera establecer las distancias entre cualquiera fueran dos puntos de 
origen y destino, y en ambos sentidos de circulación. Esto obligó a la confección de una 
base de datos que implicó la consulta 1 640 distancias; para determinar estas longitudes 
se empleó la aplicación de Internet Google Maps (www.maps.google.com), un ejemplo 
de ello se aprecia en la figura 1. 
 
Fig. 1. Distancia, según Google Maps, desde las 
Farmacias Bitiry y Hospital Mayarí (García, 2018). 
1. Modelo del ruteo para la distribución de los medicamentos (López, 2020) 
En el sistema de distribución de EMCOMED Mayarí se tienen varias rutas 
preestablecidas, cada una con no más de 12 clientes que reciben el servicio; sin embargo, 
la posible combinación de orígenes y destinos se eleva a la impresionante cifra de (12-
1)! = 39 916 800. En tal sentido, el “Método de la fuerza bruta” que analiza 
exhaustivamente cada una de las posibles variantes de transportación, queda 
definitivamente descartado. 
El “Método del vecino más cercano” y su variante del “Best first” son, a esta escala, 
variantes de solución válidas. El vecino más cercano ha demostrado que en algunos 
casos conduce a malas soluciones; por su parte la variante “Best first” mucho más 
laboriosa, puede aportar mejores soluciones, pero no se puede asegurar si la solución 
que aporta, estaría dentro de las variantes óptimasde transportación. 
Esta fue la razón por la que se decidió buscar la solución por el método de programación 
lineal con enteros binarios, que generalmente permite encontrar buenas soluciones para 
satisfacer un objetivo, a través de la satisfacción de una serie de restricciones planteadas 
como ecuaciones lineales. 
El objetivo en este caso sería el de minimizar la sumatoria de las distancias a recorrer 
entre nodos, teniendo en cuenta que hay que hacer un ciclo cerrado que implica salir de 
un punto y retornar a ese mismo punto, pasando (entrar y salir) por cada uno de los nodos 
una única vez. 
Para formular el problema se ha utilizado la variable Xij, donde los subíndices j e i son los 
nodos de la matriz (las farmacias a visitar). Para el ejemplo de 12 nodos, los valores que 
toman estos subíndices van desde A hasta L. 
 
Función objetivo. 
Esta función establece minimizar las distancias a recorrer. En este caso, los coeficientes 
http://www.maps.google.com/
4 
 
Cij son las distancias entre los nodos i y los nodos j. 
Min Z  
 
L
Ai
L
Aj
ijijXC (1) 
Las restricciones. 
Se han establecido seis grupos de restricciones, más la condición de no negatividad tal 
como sigue: 
 Primer grupo (12 restricciones). Establece que el valor de la variable en la diagonal 
principal es cero: 
0ijX , ( j = i) (2) 
 Segundo grupo (66 restricciones). Establece que cuando se salga de un nodo no se 
puede regresar a ese mismo nodo: 
1 jiij XX , ( i = A…L ,  j = 1…n,  i ≠ j) (3) 
 Tercer grupo (12 restricciones). Establece que desde un nodo se puede visitar como 
máximo a un único nodo: 
1

L
Ai
ijX , ( j = A…L) (4) 
 Cuarto grupo (12 restricciones). Establece que un nodo destino puede tener como 
máximo un nodo origen: 
1

L
Aj
ijX , ( i = A…L) (5) 
 Condición de variable binaria (144 restricciones). Establece que la variable tomará 
únicamente valores de cero y uno (Xij = 0, si la variable no entra en el conjunto de 
soluciones; caso contrario Xij = 1, si la variable entra en el conjunto de soluciones): 
 1;0ijX , ( i = A…L,  j = A…L,  i ≠ j) (6) 
 Condición de heurística (una en cada caso si se requieriera). El planteamiento de las 
restricciones anteriores no garantiza por sí solo que se creen sub-rutas, de modo que 
en algún momento habría que “impedir” que desde un determinado nodo se retorne al 
origen y/o establecer que desde un determinado nodo se devuelva al origen: 
0ijX , ( j = A, i = {B, C, …, K o L}) (7) 
1ijX , ( j = A, i = {B, C, …, K o L}) (8) 
 Condición de no negatividad: 
0ijX (9) 
En resumen, el problema planteado para los 12 nodos está compuesto por 144 variables 
binarias, una función objetivo y 246 restricciones. Entre las restricciones mencionadas, 
no se incluyen las restricciones heurística y de no negatividad. 
 
2. Solución del modelo con el Solver del Excel (García, 2018) 
El Solver del Excel está limitado modelar problemas que no incluyan más de 220 celdas 
cambiantes. Esta limitante fue la que determinó no trabajar más de 12 nodos (A, …, L), 
que implican 144 variables (144 celdas cambiantes) más otras 66 celdas cambiantes que 
se deducen del segundo grupo de restricciones, para un total de 210 celdas cambiantes. 
Este inconveniente, no obstante, no constituye un problema para el caso de EMCOMED 
5 
 
Mayarí, por cuanto las rutas de distribución de medicamentos en esta empresa agrupan 
a no más de 11 clientes. Para problemas de mayor complejidad hay que buscar otra vía, 
que puede ser la de confeccionar un software a la medida. La figura 2 muestra una vista 
general de la plantilla de Excel empleada en la determinación de las rutas, según la 
demanda de los clientes. La plantilla cuenta con otra hoja que contiene la tabla de 
distancias, la cual se ha ocultado para evitar daños accidentales y que el usuario tenga 
la menor interacción posible con la plantilla. Por esta misma razón aparecen ocultas 
varias columnas y filas en la hoja principal. 
 
Fig. 2. Vista general de la hoja de cálculo de Excel. 
La hoja contiene un marco en el cual aparece un grupo de controles del tipo checkbox 
que proporciona el Visual Basic para Office. Un checkbox marcado significa que la 
farmacia en cuestión está dentro de la programación de la ruta, mientras que un checkbox 
no chequeado indica que la farmacia correspondiente no se tendrá en cuenta para el 
cálculo de las rutas; por defecto, todos los checkbox aparecen marcados. De esta forma, 
el trabajo con la plantilla resulta tan simple como el proceder a marcar o desmarcar las 
casillas de las farmacias a serviciar y proceder con la corrida del Solver. 
En la matriz “Tabla de solución”, tanto en la columna como en la fila que encabeza los 
orígenes (A,…, L) y destinos (A,…, L), se han insertado comentarios que develan el 
nombre del nodo, al pasar el cursor del Excel sobre cada una de las casillas. 
Esta matriz tiene inicializada en cero cada una de sus 144 celdas; luego de haber corrido 
el Solver y resuelto el problema, aparecerán algunas casillas (en un máximo de 12) 
establecidas en valor “1” y el resto en ceros. Cada casilla establecida en “1” indica realizar 
la transportación desde el nodo del encabezamiento, hasta el nodo que está a la izquierda 
de la casilla. 
El chequeo de los checkbox es lo primero que ha de hacerse, por cuanto a partir de aquí 
es que se crea una nueva tabla de distancias si es preciso, para no tener en cuenta 
aquellos nodos que no estarán presentes en la distribución. 
Existe otra cantidad de celdas cambiantes en un número de 66 (ver figura 3.) que son 
para satisfacer el segundo grupo de restricciones. Estas celdas están establecidas 
originalmente con valor de cero; luego de encontrada la solución, algunas de ellas (12 
celdas como máximo) toman el valor de “1”. 
6 
 
 
Fig. 3. Celdas cambiantes generadas por 
el segundo grupo de restricciones. 
Estableciendo la Función Objetivo. 
Una vez que se tienen la matriz de distancias y la matriz de solución, se establece una 
casilla en la cual se mostrará el valor de la función objetivo. Este valor se calcula mediante 
la función “SUMAPRODUCTO(Matriz1;Matriz2)” del Excel, donde “Matriz1” es la tabla de 
distancias y “Matriz2” es la matriz de la solución. 
Programando las restricciones. 
Para programar cada una de las restricciones del modelo, se utiliza la ventana de entrada 
del Solver (ver figura 4). A esta ventana se accede desde la pestaña “Datos” en la cinta 
de opciones, haciendo clic en “Solver”. 
 
Fig. 4 Ventana de entrada de parámetros del Solver. 
A B C D E F G H I J K L
A 1 0 0 0 0 0 1 0 0 0 0
B 1 0 0 0 0 0 0 0 0 0
C 0 0 0 0 0 1 0 0 0
D 0 1 0 0 1 0 0 0
E 1 1 0 0 0 0 0
F 0 0 0 0 0 0
G 0 0 0 0 1
H 0 1 0 0
I 0 0 0
J 1 0
K 1
L
7 
 
Lo primero que se hizo fue establecer la casilla de la función objetivo, que se calcula con 
la función SUMAPRODUCTO antes explicada y decir si se trata de un problema de 
“maximizar” o “minimizar”; en este caso se trata de minimizar la sumatoria de las 
distancias a recorrer. 
A continuación, se estableció el rango de celdas donde aparecerán los valores de las 
variables de decisión, esto se refleja en el cuadro de texto que sucede a la etiqueta 
“Cambiando las celdas de variables:”. 
Solución encontrada. 
En la plantilla, todas las posibles restricciones ya están agregadas, de modo que tan solo 
hay solicitar la solución del problema; para hacerlo basta hacer clic en el botón “Resolver”. 
La figura 5 muestra el resultado de esta solución; el valor encontrado para la Función 
Objetivo para el problema planteado, es de 86,32 km. 
 
Fig. 5. Matriz de solución para el problema 
planteado con el Solver. 
Como se aprecia, la solución del problema es: A → B → C → I → D → F → E → G → L 
→ K → J → H → A; es decir: Almacén EMCOMED Mayarí → Farmacia de Urgencia → 
Hospital Mayarí → Policlínico Mayarí → Farmacia Bitiry → Farmacia Principal Mayarí → 
Farmacia Cocal → FarmaciaChavaleta → Farmacia Levisa → Farmacia Felton → 
Farmacia Guatemala → Farmacia Naranjal → Almacén EMCOMED Mayarí. La solución 
establece que se pase una única vez por cada nodo y que se retorne al final al mismo 
punto origen de partida. Lf Figura 6 muestra la tabla de distancias donde se han resaltado 
los valores de la solución encontrada, la sumatoria de estos valores es de 86,32 km. 
 
Fig. 6. Tabla de distancias, con resalte en los 
valores según la Solución del Solver. 
A B C D E F G H I J K L
A 0 0,74 0,89 1,30 3,40 2,10 3,60 3,20 1,50 13,60 22,00 18,00
B 0,37 0 0,15 0,61 2,60 1,40 2,90 2,50 0,80 13,80 21,00 18,57
C 0,88 0,15 0 1,50 2,70 1,40 2,90 2,50 0,82 14,10 21,10 18,72
D 1,50 0,61 0,63 0 2,00 0,75 2,30 1,90 0,21 13,90 22,20 17,00
E 3,70 3,00 3,00 2,00 0 1,80 3,30 3,10 2,40 15,10 24,20 21,20
F 1,90 1,20 1,20 0,75 3,20 0 1,50 1,30 0,67 13,40 20,00 16,00
G 3,40 2,70 2,70 2,30 3,30 1,50 0 1,30 2,20 13,40 18,00 15,00
H 3,00 2,30 2,30 1,90 3,10 1,30 1,30 0 1,80 12,00 19,00 16,00
I 1,20 0,52 0,54 0,41 2,40 1,20 2,70 2,30 0 14,30 21,00 17,00
J 14,00 14,80 14,90 15,20 17,30 17,00 13,40 12,00 13,90 0 30,00 27,00
K 22,00 21,00 21,00 20,00 21,00 20,00 18,00 19,00 20,00 30,00 0 19,00
L 18,00 17,00 17,00 16,50 18,00 16,00 15,00 17,00 17,00 27,00 19,00 0
8 
 
3. Análisis de los resultados 
El mismo problema de ruta, del tipo “Agente Viajero”, se resolvió por otras cinco vías. La 
mejor de las soluciones se alcanzó en tiempo récord por el método de programación lineal 
(86,32 km), con un valor muy cercano al que se obtuvo por el laborioso método Best First 
(87,36 km). En orden le sigue la solución EMCOMED Mayarí (88,96 km) que dista en tan 
solo 2,64 km de la mejor solución encontrada. En la Tabla 1 se resumen los resultados 
obtenidos en cada solución: 
Tabla 1. Resumen de las soluciones para el problema de la ruta 
óptima para la distribución de medicamentos. 
Método de solución Valor de la F.O. 
1. Vecino más cercano 93,22 km 
2. Directa 92,35 km 
3. Directa inversa 92,09 km 
4. EMCOMED Mayarí 88,96 km 
5. Mejor primero (Best First) 87,36 km 
6. Programación lineal con enteros binarios 86,32 km 
La solución que se puede encontrar por los métodos del vecino más cercano, Best First 
y por programación lineal, siempre va devolver un valor no cambiante puesto que se 
obtienen a partir de un determinado algoritmo de cálculo. 
Como se ha demostrado, es muy conveniente simular el método de programación lineal 
en una interfaz como es el Excel, siempre que el tamaño del problema lo permita. En 
estos momentos quien debe tomar las decisiones de programar las rutas de abasto de 
medicamentos, marcando o desmarcando nodos en función de la demanda, lo puede 
hacer en tiempo récord y con la certeza de que ofrecer una ruta que estaría dentro del 
conjunto de soluciones óptimas. 
 
Conclusiones. 
La vinculación de las empresas con la Universidad y viceversa, es una excelente vía para 
abordar y solucionar problemas que tributan tanto a la economía del país, como a la 
formación del futuro profesional. Muchas de estas soluciones pasan por la materialización 
de ideas audaces y a la vez sencillas. La solución al problema abordado, con el empleo 
de la herramienta Solver del Excel, es una muestra de que soluciones sencillas de aportar 
están al alcance de la mano, sin necesidad de recurrir al diseño de algún software a la 
medida. 
Esta investigación demostró la conveniencia del empleo de los modelos de programación 
lineal con enteros binarios, para el aseguramiento de rutas óptimas. La implementación 
del modelo para el reparto de medicamentos en EMCOMED Mayarí, muestra que es 
factible obtener de manera rápida las rutas de distribución y al menor costo posible, en 
función de las necesidades cambiantes de los clientes. 
En lo adelante esta investigación se encamina a la solución de problemas mucho más 
complejos por dos posibles vías, la primera es recurrir al Open Solver que se instala como 
un plugin de Excel y, se usaría este tabulador como interfaz de usuario. La otra, sería 
utilizar el potente sistema profesional IBM ILOG-Cplex, que supondría la creación 
adicional de una interfaz fácil de manipular por los especialistas o personal administrativo, 
encargados en la confección de rutas. 
9 
 
 
Bibliografía. 
García Reyes, J. M. (2018). Optimización de las rutas de distribución a las farmacias 
EMCOMED Mayarí. Tesis presentada en opción al título de Máster en Eficiencia 
Energética. Universidad de Holguín. 
López Milán, E., Plà Aragonés, L. M., Rigol Cardona, B. R., Reyes Gómez, E. y Miquel 
Fernández, S. (2020). Contribuciones al perfeccionamiento del transporte terrestre 
en Cuba. Revista Anales de la Academia de Ciencias de Cuba, Volumen 10, Número 
3, septiembre-diciembre de 2020.