Resumen
En las relaciones comerciales actuales
el transporte tiene una importancia extraordinaria permite que un cliente
reciba mercancías o productos sin importar la distancia al proveedor. En
principio las rutas que seguían estas mercancías fueron diseñadas
empíricamente, pero a medida que se incrementaron se fue complicando la
planificación y diseño rutas, hoy en día la logística se encarga de que las
rutas sean más eficientes, más cortas, duren menos tiempo en realizar el
transporte y por ende reducir el costo, que es una cantidad muy representativa
en el precio final de un producto o servicio. Para la resolución de estos
problemas del tipo VRP como el STP se cuentan con herramientas computacionales
que apoyan en la respuesta de los algoritmos empleados como el de Clarke y
Wright. El objetivo general de esta investigación es analizar los procesos de
diseño y planificación de rutas de transporte para mejorar los tiempos de entrega.
La metodología se basó en una investigación no experimental, documental y
descriptiva exploratoria. Los resultados que se determinaron fueron la
posibilidad del trazado de rutas con la presentación de estas de varias maneras
y obteniendo reducción del recorrido, en kilómetros en tiempo y en coste.
Palabras claves:
transporte; rutas; diseño; planificación; algoritmos.
Abstract
In today's business relationships,
transportation is of extraordinary importance, allowing a customer to receive
merchandise or products regardless of the distance to the supplier. In
principle, the routes that these goods followed were designed empirically, but
as they increased, the planning and design of routes became more complicated.
Today, logistics ensures that the routes are more efficient, shorter, take less
time to carry out the transport and therefore reduce the cost, which is a very
representative amount in the final price of a product or service. To solve
these problems of the VRP type, such as the STP, there are computational tools
that support the response of the algorithms used, such as that of Clarke and
Wright. The general objective of this research is to analyze the design and
planning processes of transport routes to improve delivery times. The
methodology was based on a non-experimental, exploratory documentary and
descriptive field research. The results that were determined were the possibility
of tracing routes with the presentation of these in various ways and obtaining
a reduction in the route, in kilometers in time and in cost.
Keywords:
transport; routes; design; planning; algorithms.
Resumo
Nas relações comerciais atuais, o
transporte é de extraordinária importância, permitindo que um cliente receba
mercadorias ou produtos independentemente da distância do fornecedor. Em
princípio, as rotas que essas mercadorias percorriam eram desenhadas
empiricamente, mas à medida que aumentavam, o planejamento e o desenho das
rotas se tornavam mais complicados. Hoje, a logística garante que as rotas
sejam mais eficientes, mais curtas e com menos tempo de execução. transporte e,
portanto, reduzir o custo, que é um valor bastante representativo no preço
final de um produto ou serviço. Para resolver esses problemas do tipo VRP, como
o STP, existem ferramentas computacionais que suportam a resposta dos
algoritmos utilizados, como o de Clarke e Wright. O objetivo geral desta
pesquisa é analisar os processos de projeto e planejamento de rotas de
transporte para melhorar os prazos de entrega. A metodologia baseou-se em
pesquisa descritiva não experimental, documental e exploratória. Os resultados
que se apuraram foram a possibilidade de traçar rotas com a apresentação destas
de várias formas e obter uma redução no percurso, em quilómetros em tempo e em
custo.
Palavras-chave:
transporte; rotas; Projeto; planejamento; algoritmos.
Introducción
En la actualidad, las relaciones
comerciales de la sociedad están marcadas por la inmediatez de las respuestas a
las expectativas del consumidor, sin importar si este consumidor es una
persona, una empresa o un país, el tiempo en el cual se recibe un producto o
servicio es cada vez menor, grandes empresas comerciales han basado su éxito en
reducir el tiempo que pasa desde que se hace un pedido hasta que es recibido en
la puerta de su casa o empresa. Las Tecnologías de la Información y
Comunicación (TIC) han tenido mucho que ver, pues la interconectividad mundial
hace posible que la distancia entre vendedor y cliente no sea un inconveniente.
En todas estas situaciones está presente el transporte como actividad
fundamental para lograr la satisfacción del cliente.
La logística en las empresas para
Julcapari (2018) es una actividad interdisciplinaria que incluye diferentes
departamentos de la organización, desde programar las compras hasta el servicio
postventa. Uno de los objetivos de la logística es determinar y coordinar de
forma correcta el traslado de productos hacia el cliente, considerando el
producto, cliente, lugar y tiempo correcto según Mora citado por Julcapari (2018)
Para Guillen y
Valdivieso citado por Garcia y Merino (2020) la correcta administración de las
operaciones logísticas tiene como objetivo entregar los productos o servicios
en el lugar deseado, la cantidad correcta, en el momento oportuno y en las
condiciones adecuadas, y todo esto se mide a través del nivel de satisfacción
al cliente, consiguiendo al mismo tiempo incrementar las utilidades de la
empresa.
García (2020)
menciona que, la logística es el arte de mover y almacenar, el movimiento
(transporte) es la parte de la actividad logística con mayor repercusión
económica e incluso social. Se puede decir que sin transporte no hay comercio y
sin comercio no hay actividad económica sostenible. Según Mendoza, Alfaro y
Paternina citados por Julcapari (2018) el transporte siempre ha sido primordial
económicamente en cada país, debido al fenómeno de la globalización actualmente
se ha convertido más relevante, ya que es una cualidad de suma importancia en
el desarrollo de los productos que la empresa pueda brindar.
Según Antón citado por Rodríguez (2020), la logística es una parte muy importante en todas las organizaciones
independientemente el objeto social, determina y gestiona los flujos internos y
externos en una empresa, así mismo implica todas y cada una de las operaciones
necesarias para mantener una actividad productiva Servicio postventa,
aprovisionamiento de materias primas, planificación, producción, almacenaje,
diseño, embalaje, etiquetaje, clasificación, distribución física.
La creciente tendencia hacia el
comercio digital, han generado cambios en las empresas dedicadas a la
logística, donde la alta competitividad les ha obligado a mejorar sus servicios
hacia los consumidores, done consultar o usar la información debe estar
disponible lo más pronto posible Hsiao y Chang (2019). Contar con sistemas de
información, permite que las empresas tomen decisiones más asertivas y así,
aumente la eficiencia en sus procesos Chupin et al. (2019).
El transporte es aquel que permite
el traslado de un producto o servicio, que va desde un lugar de origen hasta el
lugar o sitio donde es requerido; siendo una actividad fundamental dentro del
desarrollo de la empresa y de la humanidad Tutiven (2021)
Transporte es definido por Julio
citado por Tutiven (2021) “toda actividad encaminada a trasladar los productos
desde un punto de origen hasta un lugar de destino”, siendo el responsable de
dar movimiento a los recursos hacia las distintas empresas o clientes
distribuidos geográficamente, y agregando valor a los productos, en cuanto a su
entrega, calidad, y cantidad solicitada, satisfaciendo al cliente Barrera et
al. (2018). El transporte ocupa espacio público (carreteras, vías, puertos y
aeropuertos) y requiere inversiones públicas y privadas, generando una
actividad económica extraordinaria García (2020). Como se ha visto, hay varios
tipos de transporte el seleccionado dependerá de la ubicación geográfica del
tipo de producto o servicio a prestar y el tiempo de entrega. Cuando estas vías
no se encuentran en óptimas condiciones se producen perturbaciones que atrasan
y encarecen los despachos.
Hay ciertas situaciones que no
facilitan las actividades afines al transporte, la mayoría de las empresas
modernas que requieren del transporte terrestre al construir sus instalaciones
disponen de sitios adecuados para recibir y despachar suministros. Pero esto no
es el común de los casos, cuando el cliente está situado en ciudades que no
cuentan con vías que permiten la buena circulación, paradas o estacionamientos
adecuados, se está en presencia de obstáculos e inclusive, algunas ciudades
tienen regulaciones para la circulación del transporte de carga, o tiene un
horario para la descarga de mercancía en horario especial.
La seguridad es también muy
importante pata el transporte, hay vías que, por las características
geográficas, también se pueden catalogar como peligrosas porque atraviesan
zonas donde hay mucha delincuencia, en algunas vías marítimas hoy en día hay
actos de piratería que ponen en zozobra y encarecen al transporte.
El impacto que el transporte tiene
en el coste del producto tiene que ver con su volumen y/o con su peso, y es
evidente que tiene que ver también con las distancias y con las
infraestructuras tanto en origen como en destino, y que éstas van a definir el
tiempo de entrega e incluso la entrega a tiempo García (2020).
Desde el punto de vista de la distribución física, el transporte es todo un
arte, los avances tecnológicos han ayudado mucho y el sistema se ha vuelto más
sofisticado, y es necesario contar con vehículos necesarios y adecuados para
cada tipo de mercancía a transportar con el fin de entregar un producto a
tiempo y en las mejores condiciones. Estrella y Cuichan (2020).
Los costes de transporte son, en la
mayoría de las empresas, mayor que los costes de almacenaje. En Europa son el
45% de los costes logísticos llegando al 60% en USA García (2020),
las decisiones en el transporte se basan fundamentalmente en la velocidad y el
coste, pero también en la densidad del producto y la densidad de valor, la
seguridad del producto y de los lugares por donde pasan los productos y otros
productos que también se tengan que planificar.
El transporte terrestre
requiere infraestructuras (caminos o carreteras) sobre las que se mueven los
medios (carros, camiones) uniendo centros de producción y centros de consumo,
asimismo, los caminos y carreteras conforman una red donde los nodos
principales están unidos por vías principales y desde los nodos principales la
conexión a los nodos de menor nivel se realiza mediante vías de menor
capacidad. El transporte por carretera está regulado por legislaciones diversas
y variantes que limitan velocidades, cargas, tipos de carga, horarios García (2020).
El transporte ferroviario es
un tipo de transporte terrestre que exige una inversión en infraestructuras
superior pero que permite un desplazamiento de mercancías de menor coste, de
hecho, en muchas redes el transporte de mercancías convive con el transporte de
personas, y las velocidades promedio de desplazamiento son mucho menores. El
modo de mejorar esos tiempos de transporte es generando vías exclusivas para
mercancías o coordinando las operaciones de modo adecuado, lo que suele exigir
conexiones “punto a punto” muy estudiadas, y siempre dependientes de decisiones
políticas.
El transporte aéreo de
mercancías es el más costoso, aunque es evidentemente el más rápido. El uso de
helicópteros permite llevar el producto más cerca del punto de uso que un avión
que exige aeropuertos, el uso de dirigibles puede resurgir por su menor impacto
medioambiental, pero lo que parece un hecho es el uso de drones para el reparto
de paquetería resolviendo el problema de la última milla, esta opción es una
forma de transporte muy interesante para mercancías de alto valor, poco peso y
perecederas y es una respuesta ideal para envíos urgentes García (2020).
Cada modo de transporte tiene
ventajas e inconvenientes que los hacen más adecuados en función de los
clientes, sus demandas, sus plazos requeridos de entrega. Poder utilizar
adecuadamente diferentes modos en los diferentes tramos del transporte aporta
ventajas considerables, de igual manera la intermodalidad es la combinación de
diferentes tipos de transporte, esta exige resolver las transiciones de los
productos y de la información.
Al planificar el transporte las
empresas se enfrentan a una serie de restricciones, las cuales varían
constantemente, desde las físicas más básicas (dimensiones y peso), hasta la
peligrosidad del producto, restricciones horarias o la limitación del uso de determinados
equipos García (2020). Los
medios de transporte (cada tipo de camión, cada barco, cada avión) tienen una
capacidad en volumen y en peso diferente. La capacidad en volumen viene
limitada por las dimensiones del equipo de transporte utilizado.
Para López, Mendoza y Cuartas
citados por Sangay y Silva (2021) en cuanto a El problema del
agente viajero o TSP por sus siglas en inglés (Travelling Salesman Problem) ha
sido abordado por varias ramas de la ingeniería y por distintas razones, su
principal aplicación es la de diseñar rutas desde distintas perspectivas,
buscando la mejor ruta posible con criterios de economía en distancia o en
costo, proponiendo alternativas para el mejor uso de los recursos, su
origen se atribuye a Flood en 1956 y es quizá el problema de optimización
combinatoria más popular de todos en el área de investigación de operaciones Sangay
y Silva (2021)
El objetivo es encontrar un
recorrido completo que conecte todos los nodos de una red, visitándolos tan
solo una vez y volviendo al punto de partida, y que además minimice la
distancia total de la ruta. Este tipo de problemas tiene gran aplicación en el
ámbito de la logística y distribución, así como en la programación de curvas de
producción. Sangay
y Silva (2021).
El problema del agente viajero
tiene una variación importante, y esta depende de que las distancias entre un
nodo y otro sean simétricas o no, es decir, que la distancia entre A y B sea
igual a la distancia entre B y A, puesto que en la práctica es muy poco
probable que así sea Sangay y Silva (2021)
La cantidad de rutas posibles en
una red está determinada por la ecuación: (n-1)! Donde “n” es el número de
nodos, a medida que el número de nodos aumente la cantidad de rutas posibles
crece factorialmente.
Existen diferentes técnicas usadas
para resolver el problema del agente viajero, así como su complejidad
computacional y con cada uno de los métodos usados se pueden mostrar las
ventajas y desventajas al usarlos.
De esta manera, esta investigación
tiene como objetivo general analizar los
procesos de diseño y planificación de rutas de transporte para mejorar los
tiempos de entrega. La
metodología utilizada se basó en un diseño bibliográfico de tipo documental.
Metodología
Esta investigación se
realizó basándose en un diseño bibliográfico de tipo documental. El trabajo se
fundamenta en la revisión sistemática, rigurosa y profunda de material
documental de cualquier clase, donde se efectúa un proceso de abstracción
científica, generalizando sobre la base de lo fundamental, partiendo de forma
ordenada y con objetivos precisos Palella y
Martins (2010),
la investigación documental se concreta exclusivamente en la recopilación de
información de diversas fuentes, con el objeto de organizarla describirla e
interpretarla de acuerdo con ciertos procedimientos que garanticen
confiabilidad y objetividad en la presentación de los resultados, para lograr
este propósito se utilizaron herramientas como textos, documentos y artículos
científicos publicados disponibles en la web Palella y Martins (2010)
Los objetivos de esta
investigación se basaron en definir y mostrar la importancia del transporte
terrestre en las actividades comerciales, describir el ruteo resolviendo el
problema del agente viajero TSP (Travelling Salesman Problem) y sus variantes, describir el problema de
ruteo de vehículos VRP (Vehicle Routing Problem) y sus variantes, mostrar y clasificar
los diferentes tipos de algoritmos utilizados para resolver el VRP, describir
los procesos de diseño y planificación de rutas de transporte para reducir los
tiempos de entrega.
Resultados y discusión
Técnicas usadas para
resolver el problema del agente viajero
Problema de ruteo
(enrutamiento) de vehículos VRP
La planificación manual de rutas ha
sido empleada por compañías durante muchos años y, a pesar de la experiencia de
los planificadores de rutas, la complejidad siempre cambiante de la red de
transporte actual puede afectar la validez financiera de una ruta de un día a
otro (Murray, 2018).
Para Gallego, Pantrigo y Duarte
citados por Julcapari (2018) mencionan que, el problema de enrutamiento de
vehículo (VRP) consiste en obtener agrupaciones de rutas más cortas que se
pueda, usando una mínima cantidad de vehículos, iniciando desde un punto de
partida (almacén) y volviendo sucesivamente a él, se le suministran una
cantidad de clientes que se encuentran distribuidos geográficamente,
considerando que cada flota tiene una capacidad máxima propia y la cantidad de
producto demandada por los clientes es distinto.
Arboleda et al. Mencionados por
Cruz, Mesa, y Franco (2019) especifica que los componentes fundamentales del
VRP, son: la red de carreteras, los clientes, los depósitos, los vehículos y
los conductores.
Los
objetivos que busca este modelo VRP son la obtención de un menor costo asociado
a transporte, recorriendo la menor distancia, utilizando un menor tiempo de
distribución, entre otras diferentes variables, sujetas a los requerimientos de
las organizaciones o los casos objeto estudio Carabali
y Zapata (2019)
Los VRP también tienen en cuenta
para definir las rutas a los
clientes, los vehículos, los depósitos, las restricciones y los objetivos, en
donde el cliente cuenta con una demanda
establecida que necesita ser satisfecha por la flota de vehículos, la cual
parte y debe regresar al depósito.
Para Ascencio et al. (2018),
el VRP, busca la solución más óptima; este tipo de problemas de optimización es
de tipo combinatoria y por lo regular pertenece a la clase NP-Hard (Non
deterministic Polynomial-Hard), lo que significa que no es posible resolverlos
en tiempo polinomial.
Bravo et al. (2021)
Mencionan que, el problema de ruteo de vehículos o VRP, según sus siglas en
inglés, se puede dividir en dos categorías: homogéneo donde los nodos tienen
características en común, es decir que comparten recursos y los modelos
heterogéneos se dan en un contexto en que cada nodo tiene recursos diferentes.
En este sentido, Hernández (2018) menciona que, un VRP debe determinar un conjunto de rutas para llevar a cabo todas
las solicitudes de transporte (o algunas) dada una flota homogénea de
vehículos, a un mínimo costo. Que, para ser considerados como tal, debe
incluir una serie de elementos:
·
Flota de vehículos
·
Clientes y/o proveedores
·
Deposito central o centro de
distribución
·
Red de transporte
·
Servicio por atender (demanda o consumo)
·
Rutas de solución Hernández (2018)
Algoritmos Usados para
resolver VRP
Mancilla, Ebratt y Capacho citados
por Julcapari (2018) indicaron que, un algoritmo es un grupo reducido de
patrones establecidas correctamente en su lógica de control que permite la
solución de un problema en un menor tiempo. En este sentido, el algoritmo para
brindar solución al problema ejecuta una lista de pasos con las normas
establecidas, que puede ser realizado manualmente.
Entre los diferentes tipos de
algoritmo que se usan para resolver el VRP tenemos:
- Los Heurísticos:
Según Reeves citado por Bravo et al. (2021) define la
heurística como una técnica que, aunque no garantiza soluciones óptimas,
es capaz de encontrar buenas soluciones (subóptimas en la mayoría de los
casos) con un tiempo de cálculo factible.
Mientras que Díaz et al. Citados
por Julcapari (2018) afirman que los métodos heurísticos son un conjunto de
técnicas que solucionan multitud de problemas prácticos complejos que se
visualiza en distintas áreas, por el tipo de problemas que pueden abordar, su
mayor desarrollo se ha producido dentro del ámbito de la organización
empresarial y en particular en la dirección de operaciones.
- Metaheurísticos:
Según Reeves citado por Bravo et al. (2021) la metaheurística
se caracteriza por guiar un conjunto de heurísticas y ha sido
particularmente útil para resolver complejos problemas de optimización.
Este grupo es muy diverso, van desde los algoritmos genéticos hasta los
más recientes, esquemas auto adaptativos y algoritmos basados en
descomposición, entre otros como la búsqueda tabú, búsqueda dispersa,
entornos variables, meméticos entre otros.
- Exactos:
Tiene un uso extenso en escenarios de escala media, sin embargo, su uso de
tiempo alto para hallar las soluciones es inviable para la mayoría de los
procesos, a pesar de la exactitud de los resultados. Julián (citado por
Bravo et al. (2021)
- Matheuristics:
Esta es una solución híbrida con operadores exactos de programación
matemática que se mejoran con procesos metaheurísticos. Julián Sastre
(citado por Bravo et al. (2021)
- Aproximados:
dan una solución suficientemente óptima (no la óptima) en un tiempo de
ejecución razonable, logran solventar el problema de los elevados tiempos
de ejecución, con estos métodos no se tiene la garantía de obtener la
solución óptima, aunque sí una suficientemente buena.
En la figura 1 se muestran los
diferentes tipos de algoritmos aproximados.
Figura 1 Tipos de
algoritmos aproximados. Fuente: Ascencio et al. (2018)
Los algoritmos heurísticos CONSTRUCTIVOS,
son técnicas iterativas que gradualmente van creando una solución, donde en
cada paso se agrega un nuevo elemento que se evalúa y se deshecha cuando no es
mejor que otro.
Los algoritmos heurísticos de DOS
FASES que representan dos procesos: agrupación de vértices en rutas
factibles y construcción de la ruta, de tal manera que el problema se resuelve
de manera secuencial, un claro ejemplo es el método de Fisher y Jaikuman según
Ramalhinho y Serra mencionado por Ascencio et al. (2018)
Los algoritmos heurísticos de MEJORA,
realizan una serie de intercambios de vértices dentro de una misma ruta o entre
distintas rutas para buscar la mejor solución, está técnica consiste en
búsquedas locales que parten de una solución completa y usando el concepto de
vecindario recorren y evalúan parte del espacio para encontrar el óptimo local.
Un claro ejemplo es, el método Swap para Lum et al. Citados por Ascencio et al.
(2018)
Los algoritmos METAHEURISTICOS,
son la combinación de distintas técnicas heurísticas para realizar la
exploración del dominio de búsqueda de una manera más eficiente, se consideran
seis tipos de metaheuristicas: recosido simulado, genéticos, redes neuronales,
búsqueda tabú, colonia de hormigas y GRASP Ascencio et al. (2018)
En base a lo mencionado
anteriormente se puede identificar los siguientes métodos de programación y
diseño de rutas más usados, lo cuales dependen de restricciones prácticas tales
como la capacidad en peso y volumen de las diferentes unidades de transporte,
así como el tiempo máximo de conducción por ruta, distintas velocidades en
diferentes zonas, barreras para viajar y tiempos de descanso para el conductor.
La planificación manual de rutas ha
sido empleada por compañías durante muchos años y, a pesar de la experiencia de
los planificadores de rutas, la complejidad siempre cambiante de la red de
transporte actual puede afectar la validez financiera de una ruta de un día a
otro (Murray, 2018)
- Método de
barrido: Según Bellou, este método
tiene dos etapas, la primera consiste en la asignación de las paradas a
las unidades de transporte y la segunda determina la secuencia de las
paradas dentro de las rutas con el objetivo de minimizar la distancia
total recorrida; sin embargo, tiene la opción de dar resultados favorables
siempre y cuando esté sujeto a restricciones Bravo et al. (2021)
Algunas de las restricciones más
comunes para este tipo de modelo son:
- El volumen
de parada es una pequeña fracción de la capacidad de la unidad de
transporte.
- Todas las
unidades tienen la misma capacidad en peso y volumen.
- No existen
restricciones de tiempo en las rutas Bravo et al. (2021)
Este método consiste en realizar
los siguientes pasos:
- Localizar
las paradas, incluyendo el almacén o centro de distribución en el mapa.
- Trazar una
línea recta desde el almacén o centro de distribución en cualquier
dirección.
- Girar la
línea en sentido de las manecillas del reloj hasta que se intercepte una
parada Bravo et al. (2021)
- Método de
ahorro: Este método tiene como
finalidad reducir el número de unidades de transporte necesario para
atender todos los puntos de pedido, siendo capaz de presentar soluciones
óptimas combinado paradas dentro de una ruta de manera que se reduzcan el
desplazamiento total de las unidades y se maximice el uso de la capacidad
de estas Batista, Lao y Moreno (2019)
El Algoritmo de ahorros de Clarke y
Wright, es una de las técnicas más populares para resolver VRP a través de
heurísticas, consiste en el principio de combinar una solución de dos rutas
diferentes para formar una nueva ruta donde se validen los ahorros Ascencio et
al. (2018)
El modelo de ruteo de Clarke y
Wright, la utilizan algunas organizaciones que buscan que sus productos lleguen
a la mano del cliente y permita “la reducción en sus costos logísticos siendo
estos costos un componente con gran influencia en el costo por producto
entregado lo que a su vez significa una mejora de la competitividad” Tutiven
(2021)
En el año 1964 Clarke y Wright
dieron a conocer su algoritmo, conocido también como el método de los ahorros,
que:
Tratándose
de la heurística más significativa para llevar a cabo la resolución de
problemas de tipo VRP (Problemas de Rutas de Vehículos). Se trata de un
depósito central y un número de vehículos no limitado para atender la demanda
conocida de un número de n de clientes, siendo el objetivo el de encontrar las
rutas que deben realizar dichos vehículos de manera que los costes sean mínimos
y se satisfaga la demanda Sara (2017), p. 22 citado por Tutiven
(2021)
Este método se desarrolla partiendo
de una solución con dos rutas (0, a..,0) y (0, b..,0), las cuales pueden ser
combinadas generando así una sola ruta óptima (0, a,b,…0).
En la Figura 2 se presenta un
ejemplo del método del ahorro antes y después de ser unidas:
Figura
2
Método del ahorro Fuente: Ascencio et al. (2018)
El ahorro se calcula usando la
siguiente ecuación:
S (a,b) = d (a,0) + d (0,b) - d
(a,b) donde:
•
S(a,b): Ahorro que se percibe del nodo a
al nodo b.
•
d(a,0): Costo del nodo a al nodo de
origen.
•
d(0,b): Costo del nodo de origen al nodo
b.
•
d(a,b): Costo del nodo a al nodo b.
- Método de
inserción en paralelo: El algoritmo
propuesto por Christofides, Mingozzi y Toth está compuesto de dos etapas
que “determinan la cantidad de rutas a utilizar aplicando la primera fase
del algoritmo de Mole y Jameson para obtener rutas compactas y conservar
los clientes iniciales para luego crear las rutas e inserta el resto de
los clientes”. Rocha et al. Citados por Bravo et al. (2021)
La primera etapa consiste en
determinar la cantidad de rutas a usar con un cliente para iniciar cada una de
las rutas, sin prestar mucha atención a la ubicación de cada cliente en las
rutas.
En la segunda etapa se crean dichas
rutas y se incorpora el resto de los clientes con la ruta en la que el costo de
insertarlo es minimizado. Para decidir en qué orden se deben insertar los
clientes a las respectivas rutas se calcula la diferencia entre el costo de
realizar la incorporación en esa ruta y en la segunda mejor opción por cada
cliente, priorizando a aquellos con la mayor diferencia.
Para la implementación de
cualquiera de los métodos propuestos anteriormente en las diversas empresas u
organizaciones se lleva a cabo el desarrollo de tres fases, las cuales tendrán
como objetivo cumplir con los siguientes puntos, los cuales fueron tomados
Bravo et al. (2021) .
- Diagnóstico
del problema de la empresa u organización.
- Identificación
del modelo matemático óptimo para el problema identificado.
- Diseño de
un logaritmo con adecuado lenguaje de programación con los respectivos
resultados de la ejecución.
- Examinar y
evaluar todas las posibles restricciones del modelo de programación.
- Controlar y
evaluar los resultados con el objetivo de validar la mejor solución
obtenida Bravo et al. (2021)
Diseño y
planificación de rutas de transporte
Entre los métodos más
utilizados para el diseño, la panificación y mejora de rutas de transporte para
mejorar costos y tiempos de entregas tenemos el Problema del Agente Viajero TSP
y el Problema Ruteo de Vehículos VRP. El uso de cada uno dependerá de las
condiciones o restricciones que estén presentes. Por tanto en el departamento
de distribución es necesario elaborar un modelo matemático que permita
determinar la distribución óptima y resolverlo Garcia y Merino (2020), este modelo matemático es el primer paso en el diseño y planificación de la ruta
planteada.
Con la misma
información recopilada se diseña e ingresa el modelo matemático para el
problema del transporte, donde cada vehículo contaría con restricciones de
capacidad en depósitos y vehículos, cada ruta comienza y termina en el mismo
depósito, cada cliente debe ser visitado por una ruta exactamente una vez, la
suma de las demandas de los clientes visitados en una ruta no debe exceder la
capacidad del vehículo y la suma de las demandas de los clientes asignados a un
depósito no debe exceder su capacidad. Se tiene entonces, una aplicación
importante de la programación lineal, donde la problemática de transporte se puede
representar con un modelo matemático Garcia
y Merino (2020)
Se desea la
distribución de productos, y que lleguen en menor tiempo al cliente, con rutas
accesibles sin mucha demora, y con un costo logístico mínimo de transporte.
Como primer paso se
debe calcular la distancia que hay entre el almacén o fábrica de productos, a
cada uno de los puntos de entrega, además de la distancia que hay entre cada
punto de entrega o clientes. Para ello hay muchos métodos como los que usan
sistemas de posicionamiento global, entre otros. Un método sencillo y económico
es usar la fórmula de la distancia euclidiana y una hoja de cálculo y los datos
obtenidos se llaman matriz de distancia.
(1)
Donde (x1, y1)
y (x2, y2) son las coordenadas de los puntos geográficos
P1 y P2.
La fórmula de distancia
euclidiana viene dada de la “geometría, en la que calcula la distancia entre
dos puntos del plano, con una raíz que suma los cuadrados de los puntos, con la
diferencia entre los ejes” (Ronald, 2018). Se procede a
calcular la matriz de
Una vez calculado la
matriz de euclidiana, se procede a calcular la matriz del ahorro utilizando la
siguiente fórmula denominada Ahorro y el algoritmo de Clarke & Wright:
𝑆𝑖𝑗=𝐶𝑖0+𝐶0𝑗−𝐶𝑖𝑗 (2)
Donde:
Ci,0 = Distancia desde
el nodo i al origen (Origen se designa con 0).
C0, j = Distancia desde
el origen al nodo j (Origen se designa con 0).
Ci, j = Distancia desde
el nodo i al nodo j
Si, j = Ahorro desde el
nodo i al nodo j.
La matriz de ahorro nos
ayuda a encontrar el valor máximo entre dos nodos, y se lee de fila a columna Tutiven (2021)
Una vez obtenida la
matriz, se procede a ordenar los ahorros de manera descendente, para ello se
utiliza por ejemplo una fórmula de Excel llamada K ésimo mayor, esta fórmula
permite hallar el valor mayor de un conjunto de datos.
Se tendrán una cantidad
de iteraciones, se halla el valor mayor de todas las iteraciones A continuación,
se determina los pares de nodos, de las iteraciones encontradas, para ello se
ordena de manera descendente, Mediante los pares ordenados, se asignan nodos a
las rutas, teniendo como referencia las conexiones que existen entre los puntos
para minimizar el costo de transporte, la distancia y el tiempo empleado.
Se procede al trazado
de las rutas, ahora aquí es donde se utilizan varias maneras de realizar el
trazado las rutas.
Trazado de
rutas utilizando una aplicación Web
Una vez resuelto el algoritmo
del ahorro se necesita la interrelación de varios elementos que permitirá que
la elaboración de las rutas pueda obtenerse y mostrarse en una PC, Tablet o
Smartphone. Se denomina aplicación web a aquellas aplicaciones que los usuarios
pueden utilizar accediendo a un Servidor web a través de Internet o de una
intranet mediante un navegador.
Postgre SQL es un
poderoso sistema de base de datos relacional de objetos de código abierto, el lenguaje estructurado
de consultas (SQL) es un lenguaje de base de datos normalizado, utilizado por
la gran mayoría de los servidores de bases de datos que manejan bases de datos
relacionales u objeto-relacionales Ortiz, Ramos y Sullón (2020)
De la misma manera,
Sara citado por Ortiz, Ramos y Sullón (2020) mencionan que una base de Datos es:
Una colección de datos estructurados según un modelo que refleja
las relaciones y restricciones existentes en el mundo real. Los datos, son
compartidos por diferentes usuarios y aplicaciones. Deben mantenerse
independientemente en estas. Asimismo, los tratamientos que sufran estos datos
tendrán que conservar la integridad y seguridad
En el mismo orden de
ideas, API es la sigla de Application Programming Interface o, en español,
Interfaz de Programación de Aplicaciones, el cual, es básicamente un conjunto
de aplicaciones que permiten la construcción de una interfaz inteligente,
configurando un medio por el cual dos sistemas se comunican (Maplink, 2018).
Maps Permite a los
usuarios visualizar el mundo real, por medio de mapas estáticos o interactivos,
que pueden ser personalizados e incorporados a sitios o aplicaciones Maplink (2018)
Routes ayuda a los
usuarios a encontrar el mejor trayecto hasta su destino, con la sugerencia de
rutas y actualizaciones de tránsito en tiempo real, también permite crear
itinerarios hasta de 25 puntos de referencia, ideal para un planeamiento de
rutas de entrega más eficiente Maplink (2018). Places ayuda a los usuarios a
conocer y explorar el mundo a su alrededor. Posibilita encontrar locales
específicos, usando números de teléfono, direcciones o nombres de
establecimientos (Maplink, 2018)
Las herramientas de
diseño web son una asociación de aplicaciones web que facilitan la
comunicación, el diseño, el usuario y la colaboración con el WWW (World Wide
Web), además permite a los usuarios interactuar y colaborar con la creación de
contenidos, tanto los mismos usuarios como la información dada.
Con todos estos
elementos y las matrices se obtiene rutas, con la ventaja que estas pueden ser
cambiadas según varíen las restricciones en el VRP. La desventaja por así
decirlo es el costo para usar las herramientas de Google pues de manera
gratuita solo se puede usar un máximo de 25 nodos lo cual representa una
representación de empresa pequeña, en problemas reales se tienen muchos más
nodos que atender. Este método se engloba en los que utilizan un sistema de
información geográfica, donde hay los que no necesariamente se muestran en una
aplicación Web entre los cuales se encuentran MapInfo Profesional, OsmAnd,
ArcGis entre otros.
Referencias
1. Ascencio,
J., Bustos, A. J., Balbuena, J., & Zamora, A. (2018). Asistente
Automático para diseño de rutas de distribución. Instituto Mexicano de
Transporte. Ciudad de Mexico: IMT. Obtenido de
https://imt.mx/archivos/Publicaciones/PublicacionTecnica/pt538.pdf
2. Barrera,
H., Daza, D., Deluque, Y., Pulido, J., & Acero, W. (2018). Gestión de
Transportes y Distribución. UNAD, 1-5. Obtenido de Recuperado de
https://repository.unad.edu.co/handle/10596/18412
3. Batista,
R., Lao, Y., & Moreno, M. (agosto de 2019). Una mirada al ruteo de
vehículos: métodos, técnicas y análisis bibliométrico. , (3). Revista de investigación
Latinoamericana en Competitividad Organizacional(3), 6. Obtenido de
https://www.eumed.net/rev/rilco/03/ruteo-vehiculos.html
4. Bravo,
A., Yupanqui, C., Cribillero, C., Ocharan, D., & Patricio, V. (2021). Gestión
de rutas a través del uso de modelos basados en algoritmos. Universidad de
Lima, Facultad de Ingenieria y Arquitectura. Lima: Carrera de Ingenieria
Industrial. Obtenido de
https://repositorio.ulima.edu.pe/bitstream/handle/20.500.12724/13293/Bravo_Gestion-rutas-traves.pdf?sequence=1&isAllowed=y
5. Carabali,
H., & Zapata, U. (2019). Diseño de rutas con VRP solver 3.0: caso de una
empresa transportadora de mercancía. Universidad Santiago de Cali, Programa
de Ingenieria Industrial. Santiago de Cali: Facultad de Ingenieria. Obtenido de
https://repository.usc.edu.co/bitstream/handle/20.500.12421/116/DISE%c3%91O%20DE%20RUTAS.pdf?sequence=3&isAllowed=y
6. Chupin,
A., Yurchenko, O., Lemesheva, Z., Pak, A., & Khudzhatov, M. (2019).
Development of Logistical Technologies in Management of Intellectual Transport
Systems in the Russian Federation. Economía
Digital: Complejidad y Variedad vs. Racionalidad, 87,
778-787. doi:https://doi.org/10.1007/978-3-030-29586-8_89
7. Cruz,
E., Mesa, L., & Franco, O. (2019). Diseño de un sistema de rutas variable
de transportación basado en sistemas de información geográfica. Avances, 21(4),
497-515. Obtenido de
https://dialnet.unirioja.es/servlet/articulo?codigo=7090084
8. Estrella
R., E. A., & Cuichan T., J. E. (2020). Diseño de un modelo logístico
para la empresa RAPID SERVICE LTDA. del cantón Latacunga (Bachelor's thesis,
Ecuador: Latacunga: Universidad Técnica de Cotopaxi: Facultad de Ciencias
Administrativas. Universidad Técnica de Cotopaxi, Facultad de Ciencias
Administrativas. Latacunga: Trabajo especial de grado. Obtenido de
http://repositorio.utc.edu.ec/bitstream/27000/5928/1/T-001453.pdf
9. Garcia,
G., & Merino, J. (Mayo de 2020). Diseño de un modelo de optimización para
el problema de transporte en una piladora de arroz de la ciudad de Daule. Revista
Científica Aristas, 2(1), 1-75. Obtenido de
https://revistacientificaistjba.edu.ec/images/joomgallery/details/gallery_2/gallery_1_9/Edicion_Mayo_2020_COMPLETO-c.pdf#page=6
10. García,
J. (2020). Introducción Al transporte de Mercancías. Nota Técnica.
Repositorio Oficial UPV Riunet. Recuperado el 05 de Febrero de 2020, de
https://riunet.upv.es/handle/10251/138752
11. Hernández,
M. (2018). Diseño de un modelo matemático para la distribución eficiente de
mercancías en edificios comerciales. Doctoral Dissertation, Universidad
Andrés Bello, Santiago de Chile. Obtenido de
http://repositorio.unab.cl/xmlui/bitstream/handle/ria/10839/a127911_Hernandez_M_Diseno_de_un_modelo_matematico_2018_Tesis.pdf?sequence=1&isAllowed=y
12. Hsiao,
W., & Chang, T. (2019). Exploring the opportunity of digital voice assistants
in the logistics and transportation industry. Journal
of Enterprise Information Management 32(6).
13. Julcapari,
J. (2018). Sistema web para la gestión de rutas de transporte basado en el
algoritmo de Clarke and Wright en ICR PERÚ. Tesis , Universidad Cesar
Vallejo, Escuela Profesional de Ingennieria de Sistemas, Lima, Perú. Recuperado
el 05 de febrero de 2022
14. Maplink.
(18 de Julio de 2018). Apis de google. Obtenido de
https://maplink.global/es/blog/que-son-google-apis/
15. Murray,
M. (04 de Septiembre de 2018). Route Planning
for Logistics and Distribution Companies.
Recuperado
el 02 de 02 de 2022, de https://www.thebalancesmb.com/route-planning-2221322
16. Ortiz,
L., Ramos, M., & Sullón, G. (2020). Análisis, diseño y elaboración de un
prototipo para un sistema de administración y elección de rutas de transporte
público. Tesis, Universidad Nacional de Piura, Facultad de Ingenieria
Industrial, Piura. Obtenido de
https://repositorio.unp.edu.pe/handle/20.500.12676/2292
17. Palella,
S., & Martins, P. (2010). Metodología de la Investigación Cuantitativa. (2da
ed.). Caracas, Venezuela: FEDEUPEL.
18. Rodríguez.
(2020). Sistema de gestión de información logística basado en servicios web
para el transporte de mercancía de la Empresa Transportes Exprecar SAS.
Universidad Autonoma de Bucaramanga, Facultad de Ingenieria. Bucaramanga,
Colombia: Grupo de Investigacion en Tecnologias de la Informacion. Obtenido de
https://repository.unab.edu.co/handle/20.500.12749/15443
19. Ronald,
G. (2018). Diseño de ruteo vehicular con ventanas de tiempo aplicando el
algoritmo Clarke & Wright para una empresa que comercializa insumos y
dispositivos médicos. . Escuela Superior Politécnica del Litoral.
20. Sangay,
D., & Silva, K. (2021). Diseño de ruta de distribución para mejorar los
tiempos de entrega de la empresa Avesa Perú EIRL Cajamarca 2021. Tesis para
obtar al titulo Profesional de: Ingeniero Industrial, Universidad Privada del
Norte, Facultad de Ingenieria, Cajamarca. Obtenido de
https://repositorio.upn.edu.pe/handle/11537/27761
21. Tutiven,
S. (2021). Diseño de un modelo logístico para el diagnóstico de las diversas
rutas de transporte del proyecto Ciudad Industrial las Lomas, situada en el
cantón Lomas de Sargentillo. Tesis Doctoral, Universidad de Guayaquil,
Facultad de Ingenieria Industrial, Guayaquil. Obtenido de
http://repositorio.ug.edu.ec/bitstream/redug/56604/1/TUTIVEN%20MORAN%20STEEVEN%20MIGUEL.pdf
©2022 por los autores. Este artículo es
de acceso abierto y distribuido según los términos y condiciones de la licencia
Creative Commons Atribución-NoComercial-CompartirIgual 4.0 Internacional (CC
BY-NC-SA 4.0) (https://creativecommons.org/licenses/by-nc-sa/4.0/).
