ISSN 0718-3291 Versión Impresa

ISSN 0718-3305 Versión en línea

  • SciELO Analytics
  • Traducción automática
  • Indicadores

    Links relacionados

    • En proceso de indezaciónCitado por Google
    • No hay articulos similaresSimilares en SciELO
    • En proceso de indezaciónSimilares en Google

    Compartir


    Ingeniare. Revista chilena de ingeniería

    versión On-line ISSN 0718-3305

    Ingeniare. Rev. chil. ing. vol.29 no.3 Arica set. 2021

    http://dx.doi.org/10.4067/S0718-33052021000300435 

    Artículos

    Problema de ruteo de vehículos multi-objetivo con entregas y recogidas simultáneas y minimización de emisiones

    A multi-objective vehicle routing problem with simultaneous pick-up and delivery and minimization of emissions

    José Ruiz-Meza1  2  * 

    1 Universidad Nacional Abierta y a Distancia. Escuela de Ciencias Básicas, Tecnologías e Ingenierías. Corozal, Colombia. E-mail: jose.ruiz@unad.edu.co

    2 Universidad de La Sabana. Facultad de Ingeniería. Chía, Cundinamarca, Colombia. E-mail: joserume@unisabana.edu.co

    RESUMEN

    En las cadenas de suministro, el transporte se considera como uno de los procesos más importantes y críticos debido a los costos que se derivan de este, además del substancial aporte que genera a la contaminación ambiental. Por lo cual, los modelos de ruteo de vehículos representan una herramienta eficaz que pueden articular un gran número de variables acordes a los contextos reales para la toma de decisiones y organizar un ruteo que permita la obtención de soluciones eficientes y sustentables en la asignación del transporte. En este artículo se presenta un modelo de VRP multi-objetivo que considera entregas y recogidas simultáneas, flota heterogénea, capacitado, ventanas de tiempo y multi-depósito, para la disminución de los costos del proceso en términos de uso del vehículo, costos asociados a las violaciones de tiempo y costos de las emisiones de CO2 equivalentes. Se realizaron estudios computacionales con instancias reales, construidas y adaptadas de la literatura especializada, obteniendo resultados que evidencian las reducciones en los costos totales de hasta un 18,12% con respecto al escenario actual.

    Palabras clave: Optimización; ruteo; recogidas y entregas simultáneas

    ABSTRACT

    In supply chains, transport is considered one of the most important and critical processes because of the costs derived from it, in addition to the substantial contribution it generates to environmental pollution. Therefore, vehicle routing models represent an effective tool that can articulate many variables according to real contexts for decision making and organize routing to obtain efficient and sustainable solutions in the allocation of transport. This article presents a multi-objective VRP model that considers simultaneous pickups and deliveries, heterogeneous fleet, capacitated, time windows and multi-depot, which aims to reduce process costs in terms of vehicle use, costs associated with time violations and costs of equivalent CO2 emissions. Computational studies were conducted with real instances, constructed, and adapted from the specialized literature, obtaining results that evidenced reductions in total costs of up to 18.12% with respect to the current scenario.

    Keywords: Optimization; routing; pickup and delivery

    INTRODUCCIÓN

    El proceso de ruteo en el transporte, considerado como uno de los problemas más habituales en las cadenas de suministro, se traduce en un reto cada vez más grande que obliga a las empresas a ser más innovadoras a la hora de organizar el movimiento y traslado de sus productos. En este proceso se deben considerar diversas variables como el estado de rutas, tiempos de viaje, distancias a recorrer, disponibilidad de vehículos, tiempos de entrega, gestión del personal, los costos elevados que se derivan del proceso, entre otras, para maximizar así la calidad del servicio 1,2.

    Con el desarrollo de los modelos de ruteo de vehículos (VRP) originados en 1959 como problemas de optimización combinatoria solucionados en primera instancia a través de la programación lineal 3,4 y que cada vez se ajustan más a los problemas reales, se obtienen ruteos eficientes que inciden directamente en la minimización de costos y que adicionalmente pueden considerar las minimizaciones de emisiones de CO2 para la protección del ambiente 5. Es así, que el VRP supone una gran cantidad de variantes que contextualizan diversas condiciones de los problemas de ruteo del mundo real (6). Una de estas variantes son las entregas y recogidas simultáneas (VRPSPD), la cual se ha aplicado a diferentes sistemas de logística inversa que manejan un flujo de bienes en ambas direcciones 7. Con esta variante se modela un sistema que permite que los clientes puedan recibir un producto y devolver bienes al mismo tiempo 8. Este enfoque genera una red inversa para asegurar la recolección de productos que pueden ser reutilizables, reciclados, reprocesados, y/o mejorar su disposición final 9.

    Generalmente los modelos matemáticos de VRP presentan una función objetivo lineal que pretende la minimización de distancias recorridas, el costo de viaje y/o tiempos de recorrido 10. Sin embargo, dadas las implicaciones ambientales que genera el transporte, se hace necesario considerar variantes asociadas a la logística verde para medir el consumo de energía y las contaminaciones emitidas al ambiente (suelo, aire y agua). Todo ello, con el objetivo de minimizar el impacto negativo (9) de las emisiones de gases de efecto invernadero (GEI) que afectan directamente e indirectamente a la salud personas por el daño producido a la capa de ozono (10).

    Por otra parte, los modelos de VRP pueden pretender la optimización de un objetivo a la vez o de un conjunto de ellos. Lo cual, puede generar combinaciones de minimización y/o maximización en una misma función objetivo; cuando se formula un modelo con una sola función objetivo, se denomina mono-objetivo, sin embargo, cuando hay más de un objetivo en un mismo problema, se denomina multi-objetivo 11. En este trabajo se considera un modelo multi-objetivo, cuya finalidad es la reducción de los costos por emisiones de CO2, la minimización de costos por violación de ventanas de tiempo y el costo fijo y variable por distancia recorrida de los vehículos. Adicionalmente, presenta una combinación de las siguientes variantes: flota heterogénea capacitada, entregas y recogidas simultáneas, ventanas de tiempos suaves y múltiples depósitos, lo que robustece el modelo propuesto categorizándolo como Np-hard. Por último, para medir el combustible, nosotros consideramos el consumo del vehículo en la aceleración inicial, en movimiento y detenido realizando el servicio en los nodos (tiempo en ralentí).

    BREVE REVISIÓN DE LITERATURA

    Los problemas de VRP cuyo objetivo es la asignación de rutas a vehículos para cumplir la demanda de clientes en un área determinada partiendo de un depósito y retornado a él al final del recorrido 12, han aumentado su complejidad durante la última década, combinando diversas variantes para poder modelar los sistemas reales y obtener resultados eficientes 13. Figura 1.

    Figura 1 Principales autores de trabajos con variantes comunes del VRP. 

    Ahora bien, dadas las implicaciones ambientales que generan las actividades del trasporte, se inició el desarrollo de una línea de modelos con variantes verdes introducido por 15 el cual calculó las emisiones de Dióxido de Carbono en el trayecto y tiempo de recorrido del vehículo. A este nuevo enfoque, se suma el trabajo de Energy Minimizing Vehicle Routing Problem (EMVRP) de 16 que mediante una nueva función de costos que considera la distancia y la carga del vehículo, pretende la minimización de la energía que se genera en el trabajo total de los vehículos.

    Sin duda alguna, uno de los trabajos más importantes en esta área fue el de (10) con el Pollution Routing Problem (PRP), en donde se establece una función objetivo que considera todos los costos implicados por distancia de viaje, cantidad de emisiones de gases de efecto invernadero, consumo de combustible y tiempos de viaje.

    VRP Pickup and Delivery (VRPPD)

    Las variantes de los modelos de VRP pretenden asemejar la realidad para poder solucionar los problemas contextualizados; uno de los sistemas que se están empleando a lo largo de las cadenas de suministros es la logística inversa, en donde el VRP modela un sistema que permite al vehículo recoger productos (Pickup) y hacer entregas (Delivery) en la misma ruta (17. Bajo este enfoque, se satisface conjunto de solicitudes de transporte en una o diversas rutas de viaje que se definen por puntos de recogidas y/o entregas, además de una demanda u oferta que debe ser transportada 18.

    Uno de los primeros aportes a esta variante direccionada a los sistemas dial-a-ride (transporte de personas) fue realizada por 19 quienes modelaron un sistema de ruta de autobuses teniendo en cuenta el origen y destino de los pasajeros. Ahora bien, en los años 80 y 90, esta variante toma mayor importancia gracias a los trabajos de 20,21,22 quienes presentaron nuevos algoritmos de solución para problemas de pickup and delivery; para esta época 23 establecen las características que distinguen al VRPPD de otras variantes de VRP.

    Otros autores como 24 desarrollaron heurísticas para solucionar un Traveling Salesman Problem (TSP) pickup and Delivery (TSPPD). Posteriormente 25 desarrolló un modelo de VRPPD, que combinaba variantes de ventanas de tiempo duras y multi-depósito. Un importante aporte fue el de (8) quienes dividen los problemas de VRPPD en tres categorías: Pickups and Deliveries simultáneos, Pickups and Deliveries Mixtos y Pickups después de los Deliveries (Delivery-first, pickup-second).

    VRP Simultaneous Pickup and Delivery (VRPSPD)

    Esta sub-variante del VRPPD establece que se puede recolectar bienes y transportarlos en la dirección inversa, al mismo tiempo en que se entreguen otros bienes al mismo cliente 17. El primer autor del VRPSPD fue 26 quien modeló el problema de una biblioteca y lo solucionó agrupando los nodos y resolviéndolos cada grupo como un TSP (7, 8). Posteriormente 27 aplicó una heurística de inserción para resolver un VRPSPD de la vida real que considera distancias de viajes y capacidad residual.

    Además de los aportes de la heurística de (8) que buscaba minimizar las infactibilidades, 28 fueron los primeros que propusieron una metaheurística de algoritmo híbrido basada en búsqueda tabú (TS) y búsqueda de vecindarios más cercanos (VNS) para solucionar un VRPSPD (29. Por otra parte, 30 emplean la metaheurística de optimización de Colonia de Hormigas (ACS) para mejorar las soluciones iniciales obtenidas con la heurística del vecino más cercano.

    Otros autores empezaron a combinar otras variantes de VRP con el VRPSPD, tales como (31 quienes desarrollan un VRPSPD con ventanas de tiempos teniendo en cuenta la importancia del tiempo en la toma de decisiones gerenciales. Asimismo, 32 combina variantes de flota de vehículos heterogénea (HVRPSPD) el cual fue solucionado mediante un algoritmo híbrido compuesto por recocido simulado y búsqueda local. En (7) también desarrollaron un modelo de VRPSPD con flota heterogénea y resuelto con un algoritmo híbrido basado en búsqueda local y búsqueda tabú. Por otra parte, (33) combinan variantes de múltiples depósitos tratando de contextualizar los problemas reales. El modelo fue resuelto mediante un algoritmo híbrido entre búsquela local y heurística de barrido.

    Los modelos de VRPSPD, están enmarcados mayormente en la logística inversa para contribuir a la minimización de impactos ambientales (9) y esta línea es reforzada por los objetivos de minimización de energía, CO2 y consumos de combustibles que se han venido trabajando desde el aporte de (15).

    Sin duda, uno de los más grandes aportes a esta variante "verde" del VRP fue el PRP" introducido por (10), cuya función objetivo se planteó en términos de emisiones de CO2 por el consumo de combustible y la distancia recorrida.

    Para el caso del VRPSPD 34 desarrollaron un modelo pickup and delivery simultaneo verde (g-VRPSPD) para una flota homogénea en donde se minimizaban los costos por emisiones de CO2. Asimismo, 35 proponen un nuevo modelo de programación lineal entera mixta (MILP) bajo incertidumbre para un problema de VRPSPD con ventanas de tiempo (TWPDPRP) con minimización de consumo de combustibles y emisiones.

    FORMULACIÓN DEL MODELO MATEMÁTICO

    Para los sistemas que implican la recolección y descargue de bienes de manera simultánea en un mismo cliente, los modelos de VRPSPD representan una eficiente herramienta de modelación (7) que puede ser resuelta a través de métodos exactos o aproximados según su complejidad 36. El modelo propuesto se representa mediante un grafo dirigido G = (N, V), donde N es el conjunto de vértices dividido en dos subconjuntos: N u = {n 1 , n 2 , n 3 ,…n n } es el conjunto de nodos en los cuales se realizarán cargas p j y descargas d j simultáneas dentro de una ventana de tiempo{a i , b i }. El subconjunto N d = {n n+1 , n n+2 , n n+3 ,.., n n+d } representa los depósitos y, por último, N = N u U N d es el conjunto de arcos. Figura 2. Se consideran diferentes tipos de vehículos que integran la flota de transporte V = {k1, k2, k 3 ,..., k n ,}y su capacidad de carga es limitada Q k .

    Figura 2 Representación del MDVRPSPD. 

    Consumo de energía en el arco y en ralentí

    Se considera el consumo de energía y emisiones de CO2 a partir de 37, similar a (16). El trabajo W es la multiplicación de la fuerza F por la distancia C, obteniendo W = F × C. Sin embargo, en el movimiento de un vehículo actúan cuatro fuerzas (Fuerza aerodinámica f 1, Fuerza de rodamiento f 2, Fuerza por pendiente f 3 y Fuerza por inercia f 4) 38, por lo cual tenemos que W = f 1+f2+f3+ f4) × C. Estas fuerzas se calculan a partir de las siguientes ecuaciones f 1 = jC w R 0SV2, f 3 = wsenθ y 38. Donde j, u y n son constantes.

    Tenemos que Cw es el coeficiente de arrastre, R0 la densidad del aire, S el área frontal del vehículo y V velocidad del vehículo. Asimismo, C r es el coeficiente de resistencia al rodamiento, w peso del vehículo, q ángulo de la pendiente, a aceleración del vehículo, m masa y rt 2 es la relación de paso de la transmisión; se considera que w = (m × g) donde g es la gravedad, por lo que obtenemos:

    (1)

    Similar a esta ecuación, (10) establecen P ij = α ij siendo P ij el consumo de combustible por el trabajo del vehículo en términos de energía, a ij es una constante específica del arco (ij) que se calcula mediante a ij = a + g sin θ ij + gC r cos y β otra constante específica para el vehículo calculada a través de β = 0,5CdAp. Donde M es la tara (peso del vehículo vacío), f ij es la carga del vehículo en el arco (ij), d ij es la distancia, V ij 2 es la velocidad del vehículo, C d corresponde al coeficiente de arrastre, A es la superficie frontal del vehículo en m 2 y p es la densidad del aire en kg/m 3 .

    A partir de esto, se pueden agrupar las fuerzas f 2 , f 3 y f 4 que dependen del peso del vehículo tanto lleno, como vacío. Por lo cual, se establecen las siguientes dos ecuaciones:

    (2)

    (3)

    Donde C ij es la distancia que recorre el vehículo en un arco (ij), M k la tara, y la carga del vehículo es la sumatoria de la cantidad de producto descargados Z ijk más la cantidad de productos recogidos Y ijk en el mismo arco. Por otra parte, la aceleración es ac k , el coeficiente de resistencia al rodamiento es C r y r tk es la relación de paso de la transmisión.

    La operación , ahora será expresada por d ijk . Adicional a ello, la fuerza f 1 como dependiente del vehículo, queda dada por:

    (4)

    El coeficiente de arrastre es C w , el área frontal del vehículo es AS k , la densidad del aire es R 0 y la velocidad del vehículo es V ij . Para calcular la velocidad del vehículo, se considera la aceleración inicial dividiendo la velocidad en dos tramos: en el primer tramo la a1 ≠ 0 y la velocidad se calcula mediante V1 = a1 * t 2. Para el segundo tramo, se calcula a través de , asumiendo la velocidad como constante y convirtiendo a 2 = 0. Figura 3.

    Figura 3 Velocidad del vehículo en los dos tramos para el arco (ij). 

    Para , se obtiene a través de x = x 0 +, , sin embargo, V0 = 0 al partir de reposo y como se da una distancia C ij establecida para un arco (ij), se considera a x 0 = 0. Para el segundo tramo, como V2 inicia desde d 2, se calcula que . Y tenemos:

    (5)

    No podemos solo promediar las dos velocidades que se dan en cada tramo , por

    tanto, si se asume que C ij equivale al 100% de la distancia podemos calcular un índice de porcentaje mediante , obteniendo una nueva ecuación:

    (6)

    Consecuente a esto, la operación para calcular ∂ ijk queda dada por:

    (7)

    Adicional al consumo de combustible en cada arco, se genera un consumo en ralentí (motor encendido sin acelerar con o sin embrague, manteniendo un mínimo de revoluciones por minuto) que se presenta en el tiempo de servicio S i y que consume el 17% de la energía del combustible 38, generando una ecuación de consumo dada por el factor R de consumo del vehículo y .

    Notación

    El modelo matemático considera los aportes de 10,12,35,7.

    Índices y conjuntos:

    i, j, h: Índice de clientes o depósitos.

    k: Índice de vehículos.

    N: Conjunto de depósitos {1, 2, 3... u}.

    N d : Conjunto de clientes {1, 2, 3... d}.

    N: Conjunto clientes y depósitos N = N u ∪ N d .

    K: Flota de Vehículos {1, 2, 3.. .k}.

    Parámetros:

    Q k : Capacidad del vehículo kK.

    F k : Costo fijo por uso del vehículo kK.

    V k : Costo variable por uso del vehículo kK.

    C ij : Distancia entre nodos iN, jN.

    P i : Oferta del producto a recoger en clientes iN u .

    d i : Demanda a descargar en clientes iN u .

    TTij: Tiempo de viaje del vehículo k entre los nodos iN, jN.

    a i : Horario más temprano de llegada al cliente i Nu.

    b i : Horario más tarde de llegada al cliente iN u .

    Tmax k : Tiempo máximo de ruta del vehículo k ∈ K.

    S i : Tiempo de servicio del cliente i ∈ N u .

    m i : Costo unitario de multa por violación de ventana de tiempo en el cliente i ∈ N u .

    W k : Peso del vehículo vacío k ∈ k.

    ac k : Aceleración del vehículo k ∈ k.

    Qm j: Capacidad mínima que debe recibir el depósito j ∈ N d .

    Qmx j : Capacidad máxima que puede recibir el depósito j ∈ N d .

    rt k : Relación del paso de la transmisión del vehículo k ∈ k.

    ASk: Área de la superficie del vehículo k ∈ K.

    ijk : Valor específico para el arco (ij) a partir de las fuerzas de rodamiento, por pendiente y fuerza por inercia i ∈ N, j ∈ N, k ∈ K.

    Escalares:

    M: Número muy grande definido como 1,125 veces el tiempo máximo de trabajo del vehículo. c f : Costo del combustible.

    ce: Costo emisiones de CO2.

    Cr: Coeficiente de rodamiento en kg/Ton.

    C w : Coeficiente de arrastre.

    R 0 : Densidad del aire en kg/m 3 .

    g: Gravedad m/s2.

    t2: Tiempo de aceleración inicial en min.

    ts: Tiempo máximo de servicio en que se debe dejar el motor en ralentí en min.

    R: Consumo en ralentí del vehículo en Lt/hr

    Variables:

    X jjk : Variable binaria que es = 1 si se asigna el vehículo k al arco (ij) y 0 de lo contrario.

    Y ijk : Carga recogida en el cliente por el vehículo k mientras recorre el arco (ij).

    Z ijk : Carga descargada en el cliente por el vehículo k mientras recorre el arco (ij).

    T i : Momento de tiempo en que el vehículo llega al cliente i.

    TR k : Tiempo de ruta para el vehículo k.

    Va i : Violación de restricción de la ventana de tiempo por llegada antes al cliente i.

    Vb i : Violación de restricción de la ventana de tiempo por llegada después al cliente i.

    λ i : Variable de tiempo del vehículo en ralentí en el nodo i.

    FORMULACIÓN DE PROGRAMACIÓN ENTERA MIXTA MULTI-OBJETIVO

    Este modelo presenta una función multi-objetivo compuesta por:

    i. Minimización de los costos fijos y variables en términos de la distancia recorrida por el vehículo.

    ii. Minimización de las violaciones a las ventanas de tiempo.

    iii. Minimización de emisiones de CO2 en términos de movimiento del vehículo y ralentí.

    Función multi-objetivo:

    (8)

    (9)

    (10)

    Sujeto a:

    (11)

    (12)

    (13)

    (14)

    (15)

    (16)

    (17)

    (18)

    (19)

    (20)

    (21)

    (22)

    (23)

    (24)

    (25)

    (26)

    (27)

    (28)

    (29)

    (30)

    (31)

    (32)

    La función multi-objetivo de este modelo está conformada por los objetivos (8, 9 y 10), en donde se da la minimización de los costos por uso del vehículo, minimización costos de las violaciones de ventanas de tiempo y minimización de emisiones de CO2 respectivamente. La restricción (11) asegura que un cliente es visitado exactamente una vez por un solo vehículo. La restricción (12) asegura el flujo en la red. La restricción (13) garantiza que cada vehículo debe salir máximo de un depósito. Restricciones (14 y 15) son las ecuaciones de cargue y descargue respectivamente. Para el origen las cargas se hacen cero al igual que las descargas al iniciar la ruta empleando las ecuaciones (16 y 17). Las ecuaciones (18 y 19) garantiza que si un arco es realizado por un vehículo entonces una cantidad deberá cargada y descargada. La capacidad del vehículo está dada en (20). Las restricciones (21 y 22) establecen las cantidades máximas y mínimas que deben llegar a los depósitos. El tiempo de llegada al primer cliente está dado por (23). La restricción (24) establece el tiempo de visita a los clientes. Si los clientes no pertenecen a la misma ruta, se introduce M como un valor muy grande que multiplica a la variable binaria para no considerar el cliente. La restricción (25) asegura el tiempo de ruta total del vehículo considerando el trayecto de retorno desde el último nodo al depósito. La restricción (26) limita el tiempo de ruta total. Las llegadas tempranas y tardías a los clientes se obtienen

    con las restricciones (27 y 28) respectivamente. La restricción (29) asegura el menor tiempo de servicio en para un cliente, y la las restricciones (30, 31 y 32) definen la naturaleza de las variables.

    MÉTODO DE SOLUCIÓN

    Se consideraron inicialmente once nodos con dos depósitos y dos vehículos de prueba. El área frontal de los vehículos, osciló entre los 4 y 3 mt2 y la relación del paso de la transmisión se tomó en 1,5 y 1,34, como lo expresa (37). Se calcula el costo de emisiones de CO2 (ce), multiplicando el costo de emisiones de una tonelada de CO2 emitidas en cada arco, por el consumo de combustible e. Aplicamos el método sectorial para calcular la cantidad de emisiones 39.

    (33)

    El combustible gastado en la ruta se multiplica por el factor de emisión f e y la fracción oxidada del combustible, cuyo valor es de 0,99 para para petróleos y derivados 40. Obtenemos:

    (34)

    El factor de emisión f e equivale a 2,28 kg de CO2 por cada litro de combustible dando un costo total de $8,28 por litro de combustible consumido 41.

    Frontera de Pareto aplicada al modelo

    Similar a (6,31,33 el modelo multiobjetivo se resuelve a través del método de suma ponderada, considerado el segundo mayor utilizado en la literatura (42). Se asignan unos pesos α, β y γ para cada objetivo y se construye una función lineal mono-objetivo.

    El modelo fue programado en GAMS y resuelto óptimamente mediante el solver CPLEX. Se utilizó un computador con 4 GB de memoria RAM, procesador Intel Core i7-5500 CPU@ 2.40 GHz, un TB de DD y sistema operativo de 64 bits. Se emplearon treinta y dos variaciones de pesos obteniendo un conjunto de cinco resultados extremos eficientes, diferenciados por las variaciones en los tiempos computacionales. Tabla 1.

    Tabla 1 Conjuntos de resultados con variaciones de pesos ponderados. 

    Posteriormente, se verificaron los resultados de cada objetivo comparando uno con otro para establecer la frontera de Pareto y así, identificar la mejor solución no dominada bajo el concepto de la dominancia de Pareto (11). Figura 4. Seleccionamos el conjunto de resultados cuyo costo fue $77.977,449 y de las variaciones de pesos, optamos por la que generaba respuesta en el menor tiempo computacional α = 0,9, β = 0,05 y γ = 0,05.

    Figura 4 Comparación de objetivos y dominancia de Pareto. 

    Ejecución del modelo y comparación con instancias reales

    Se evaluaron las instancias de cuatro rutas diferentes usando los pesos de la Tabla 1. Comparando los costos reales con los costos que arroja en modelo. Tabla 2. La instancia g-MHSPD_01 presentó un conjunto de ocho soluciones. La mejor solución fue obtenida con pesos de α = 0,6, β = 0,1 y γ = 0,3 con una distancia recorrida 193,589 km, litros de combustible consumidos: 68,83 Lt, tiempo de ruta: 439,44 min con 8,19 min de violación de ventanas de tiempo. Ejecutando la instancia g-MHSPD_02 se obtuvo un conjunto de 28 soluciones acotando solo las que presentaron un GAP menor al 5% (26 conjuntos de soluciones). La mejor solución de este subconjunto se obtuvo con pesos de α = 0,1, β = 0,8 y γ = 0,1 con una distancia recorrida 182,12 km, litros de combustible consumidos: 40,48 Lt, tiempo de ruta: 610,1 min sin violación de ventanas de tiempo.

    Tabla 2 Comparación de resultados en instancias actuales. 

    Nota: los costos fueron calculados por día.

    Las instancias g-MHSPD_03 y g-MHSPD_04 presentaron la particularidad de un solo depósito y vehículo. Con g-MHSPD_03 se obtuvo cuatro conjuntos de soluciones, de las cuales se seleccionó α = 0,2, β = 0,5 y γ = 0,6 arrojando una distancia recorrida 31,6 km, litros de combustible consumidos: 13,04 Lt, tiempo de ruta: 128,9 min sin violación de ventanas de tiempo. Los experimentos realizados con la instancia g-MHSPD_04 arrojaron 15 conjuntos de soluciones del cual se seleccionó el resultado con pesos a = 0,8, b = 0,1 y g = 0,1. El GAP de esta solución fue del 2,07% y el mayor GAP global fue de 16,9%. Los valores de distancia fueron 134,238 km recorridos, 61,644 Lt de combustible consumidos y 241,04 min de tiempo de viaje con 31,37 min de penalización por las violaciones de las ventanas de tiempos.

    Considerando las distancias y tiempos en las matrices correspondientes según la posición geográfica de las instancias para todas las rutas, el rango de tiempo necesario para obtener soluciones de la instancia g-MHSPD_01 fue de 13 a 731 min y el porcentaje de reducción fue del 13,75%. Figuras 5 y 6. Para la instancia g-MHSPD_02 fue de 69 a 1540 min y el porcentaje de reducción fue del 18,12%. Esta instancia presentó un GAP global máximo de 9,23%. Figuras 7 y 8. Para la instancia g-MHSPD_03 fue de 0,18 a 0,25 min y el porcentaje de reducción fue del 7,8%. Figura 9. En la última instancia g-MHSPD_04 se tardó entre 211 a 777 min para obtener resultados, y el porcentaje de reducción fue del 8,35% considerando un GAP global máximo de 16,9. Figuras 10 y 11.

    Figura 5 Ruta actual para la instancia g-MHSPD_01. 

    Figura 6 Ruta obtenida minimizando el costo de la energía minimizando para la instancia g-MHSPD_01. 

    Figura 7 Ruta actual para la instancia g-MHSPD_02. 

    Figura 8 Ruta obtenida minimizando el costo de la energía minimizando para la instancia g-MHSPD_02. 

    Figura 9 Comparación de la ruta actual y la ruta obtenida minimizando el costo de la energía minimizando para la instancia g-MHSPD_03. 

    Figura 10 Ruta actual para la instancia g-MHSPD_04. 

    Figura 11 Ruta obtenida minimizando el costo de la energía minimizando para la instancia g-MHSPD_04. 

    CONCLUSIONES

    Se desarrolló un modelo multi-objetivo que contribuye a la minimización de los costos en términos de: (i) costo fijo y costos variables por distancia recorrida, (ii) costos por multas de violaciones de tiempo y (iii) costo de las emisiones de CO2. Se incluye la variante "verde" debido al aumento considerable de las emisiones y los problemas de efecto invernadero que generan en gran participación los sistemas de transporte. Este tipo de problema deben ser tratados en las cadenas de suministros sostenibles. En este trabajo se consideraron los consumos de combustible por movimiento del vehículo, carga en cada arco, aceleración inicial, además del consumo del vehículo en ralentí al realizar los servicios de cargue y descargue. Los resultados computacionales obtenidos con las instancias de prueba y reales generan las siguientes conclusiones:

    Se obtuvieron soluciones óptimas no dominadas con un método de agregación para resolver problemas multi-objetivos. Se empleó el método de pesos ponderados, segundo de mayor uso en la literatura especializada (42 y aplicado a modelos de VRPSPD. Se obtuvo una función mono-objetivo mediante la asignación de pesos ponderados cuya variación permitió la obtención de respuestas eficientes para construir la frontera óptima de Pareto.

    La aplicación de este modelo genera reducciones en los costos diarios de las rutas estudiadas desde 7,8% a 18,12%. Sin embargo, los tiempos computacionales para obtener algunas soluciones fueron altos si se considera la organización diaria de un ruteo.

    El ruteo se trabajó de manera clusterizada, debido a la complejidad computacional del modelo al ser Np-Hard. Se Agruparon los datos por cada zona obteniendo así un ruteo particular y reducciones de costos en cada una. Para abordar las zonas de manera holística, es necesario considerar la construcción de algoritmos aproximados.

    Los modelos de pickup and delivery se caracterizan por ser de tipo Np-hard, por lo cual se pueden desarrollar y aplicar diferentes métodos aproximados. Generalmente se desarrollan algoritmos híbridos para obtener soluciones computacionalmente buenas. La implementación de un algoritmo de dos fases es recomendada: en la primera fase puede considerarse la aplicación de métodos exactos o heurísticas, tales como el algoritmo de Clarke and Wright (C&W) para generar soluciones factibles iniciales. Posteriormente, la segunda fase buscaría mejorar las soluciones iniciales a través de algoritmos como búsqueda tabú o genéticos (AG), el NSGA II o una adaptación del VEGA. Por otra parte, para el desarrollo de investigaciones futuras que permiten aumentar el conjunto de variantes y similitud con los contextos reales, proponemos la inclusión de variantes de entregas fraccionadas y multiproducto, según la naturaleza del problema o el aporte que se quiera realizar a la literatura.

    REFERENCIAS

    [1] H. Castillo, J. Bermeo and S. Serrano. "Propuesta de sistemas Inteligentes para la Implementación de un modelo de gestión triple a en la cadena de suministro de centros de acopio de leche cruda en la provincia del Azuay". J. Exp. Psychol. Gen. Vol. 136 N° 1, pp. 23-42. 2013. [ Links ]

    [2] J.C. Quintero. "Propuesta metodológica para la recolección de leche en Colombia caso de estudio: Provincia de Sugamuxi (Boyacá)", pp. 96. 2013. [ Links ]

    [3] S. Aref and I. Kazemian.'A green perspective on capacitated time-dependent vehicle routing problem with time windows", pp. 1-15, 2015. [ Links ]

    [4] G.B. Dantzig and J. Ramser. "The truck dispatching problem". Manage. Sci. Vol. 6 N° 1, pp. 1-13. 1959. [ Links ]

    [5] H. Lamos Diaz, S.A. Galván Nuñez, L.J. Gonzalez Villamizar and C. Cruz Jimenez. "PSO-Hybrid algorithm for solving the vehicle routing problem with simultaneous pickup and delivery". Fac. Ing. Vol. 22 N° 35, pp. 75-90. 2013. [ Links ]

    [6] P. Sombuntham and V. Kachitvichyanukul. "Multi-depot vehicle routing problem with pickup and delivery requests". AIP Conf. Proc. Vol. 1285, pp. 71-85. 2010. [ Links ]

    [7] M. Avci and S. Topaloglu. "A hybrid metaheuristic algorithm for heterogeneous vehicle routing problem with simultaneous pickup and delivery". Expert Syst. Appl. Vol. 53 N°2, pp. 160-171. 2016. [ Links ]

    [8] G. Nagy and S. Salhi. "Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries". Eur. J. Oper. Res. Vol. 162 N° 1, pp. 126-141, 2005. [ Links ]

    [9] V. Reyes, D. Zavala and J. Gálvez. "A review of reverse logistics process and its relation with green logistics" Rev. Ing. Ind. ISSN-e 0717-9103. Vol. 7 N° 2. 2008. [ Links ]

    [10] T. Bektaş and G. Laporte. "The Pollution-Routing Problem". Transp. Res. Part B. Vol. 45, pp. 1232-1250. 2011. [ Links ]

    [11] F. Mendoza. "Diseño multiobjetivo y multietapa de sistemas de distribución de energía aplicando algoritmos evolutivos". Universidad de Zaragoza-2010. [ Links ]

    [12] N. Herazo-Padilla. "Modelación matemática del problema de ruteo de vehículos con restricciones de múltiples depósitos, flota heterogénea de vehículos y ventanas de tiempos", pp. 151. 2012. [ Links ]

    [13] J.L. Ruiz-Meza. "Diseño de un modelo multiobjetivo de VRP pick-up and delivery simultáneo (VRPSPD) para el aprovisionamiento de la leche en la cadena de suministros lácteos". 2018. [ Links ]

    [14] J.R. Montoya-Torres, J. López Franco, S. Nieto Isaza, H. Felizzola Jiménez and N. Herazo-Padilla. "A literature review on the vehicle routing problem with multiple depots". Comput. Ind. Eng. Vol. 79, pp. 115-129. 2015. [ Links ]

    [15] A. Palmer. "The developement of an integrated routing and carbon dioxide emissions model for goods vehicle". Sch. manag., vol. Doctor of, pp. 151, 2007. [ Links ]

    [16] I. Kara, B. Karap and M. Yetis. Energy Minimizing Vehicle Routing Problem. 2007. [ Links ]

    [17] J. Ruiz-Meza, A. Torregroza-Espinoza, D. Mejía-Ayala and G. Mendoza-Ortega. "Vehicle routing problem with simultaneous pickup and delivery for milk collection in Galeras , Sucre". Engineering, integration, and alliances for a sustainable development. hemispheric cooperation for competitiveness and prosperity on a knowledge-based economy: Proceedings of the 18th laccei international multi-conference for engineering, education and technology, pp. 1-8. 2020. Boca Ratón, Florida, US. [ Links ]

    [18] G. Desaulniers, J. Desrosiers, A. Erdmann, M.M. Solomon and F. Soumis. "VRP with pickup and delivery". Veh. Routing Probl., pp. 225-242. 2002. [ Links ]

    [19] N.H.M. Wilson, J.M. Sussman, H.K. Wong and T. Higonnet. "Scheduling algorithms for a dial-a-ride system". Massachusetts Institute of Technology. Urban Systems Laboratory. 1971. [ Links ]

    [20] J. Desrosiers, Y. Dumas and F. Soumis. "A dynamic programming solution of the large-scale single-vehicle dial-a-ride problem with time windows". Am. J. Math. Manag. Sci. Vol. 6 N° 3-4, pp. 301-325. 1986. [ Links ]

    [21] J. Desrosiers, Y. Dumas, M.M. Solomon and F. Soumis. "Chapter 2 time constrained routing and scheduling". Handbooks Oper. Res. Manag. Sci. Vol. 8, pp. 35-139.1995. [ Links ]

    [22] D. Desrosiers, J. Dumas, Y. Soumis, F. Taillefer and S. Villeneuve. "An algorithm for mini-clustering in handicapped transport". Les Cah. du GERAD. N° January, pp. G-91-02. 1991. [ Links ]

    [23] M.W.P. Savelsbergh and M. Sol. "The general pickup and delivery problem". Transp. Sci. Vol. 29 N° 1, pp. 17-29. 2008. [ Links ]

    [24] M. Gendreau, G. Laporte and D. Vigo. "Heuristics for the traveling salesman problem with pickup and delivery". Comput. Oper. Res. Vol. 26 N° 7, pp. 699-714. 1999. [ Links ]

    [25] S. Irnich. "A multi-depot pickup and delivery problem with a single hub and heterogeneous vehicles". Eur. J. Oper. Res. Vol. 122 N° 2, pp. 310-328. 2000. [ Links ]

    [26] H. Min. "The multiple vehicle routing problem with simultaneous delivery and pick-up points". Transp. Res. Part a Gen. Vol. 23 N° 5, pp. 377-386. 1989. [ Links ]

    [27] J. Dethloff. "Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up". OR Spektrum. Vol. 23 N° 1, pp. 79-96. 2001. [ Links ]

    [28] J. Crispim and J. Brandão. "Metaheuristics applied to mixed and simultaneous extensions of vehicle routing problems with backhauls". J. Oper. Res. Soc. Vol. 56 N° 11, pp. 1296-1302. 2005. [ Links ]

    [29] P. Aravind, D.E. Babu and B. Paul. "A Review of Vehicle Routing Problem with Simultaneous Pickup and Delivery". Vol. 15 N° 4, pp. 203-205. 2014. [ Links ]

    [30] Y. Gajpal and P.L. Abad. "An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup". Comput. Oper. Res. Vol. 36, pp. 3215-3223. 2009. [ Links ]

    [31] H.F. Wang and Y.Y. Chen. "A genetic algorithm for the simultaneous delivery and pickup problems with time window". Comput. Ind. Eng. Vol. 62 N° 1, pp. 84-95. 2012. [ Links ]

    [32] B. Kececi, F. Altiparmak and I. Kara. "The heterogeneous vehicle routing problem with simultaneous pickup and delivery: A hybrid heuristic approach based on simulated annealing". Proceedings book of CIE44 & IMSS'14, pp. 412-423. 2014. Istanbul, Turkey. [ Links ]

    [33] J. Li, P.M. Pardalos, H. Sun, J. Pei and Y. Zhang. "Iterated local search embedded adaptive neighborhood selection approach for the multi-depot vehicle routing problem with simultaneous deliveries and pickups". Expert Syst. Appl. Vol. 42 N° 7, pp. 3551-3561. 2015. [ Links ]

    [34] Y. Huang, C. Shi, L. Zhao and T. Van Woensel. "A study on carbon reduction in the vehicle routing problem with simultaneous pickups and deliveries". Proc. 2012 IEEE Int. Conf. Serv. Oper. Logist. Informatics, SOLI 2012, pp. 302-307. 2012. [ Links ]

    [35] N. Tajik, R. Tavakkoli-Moghaddam, B. Vahdani and S. Meysam Mousavi. "A robust optimization approach for pollution routing problem with pickup and delivery under uncertainty". J. Manuf. Syst. Vol. 33 N° 2, pp. 277-286. 2014. [ Links ]

    [36] A. Lüer, M. Benavente, J. Bustos and B. Venegas. "El problema de rutas de vehículos: Extensiones y métodos de resolución estado del arte". CEUR Workshop Proc. Vol. 558. 2009. [ Links ]

    [37] M. Yolanda, R. Morales and A.H. Guzmán. "Manual de conducción técnica de vehículos automotores diesel: Segunda edición". 2012. [ Links ]

    [38] R. Baxter, N. Hastings, A. Law and E.J. Glass. "Manual de conduccione eficiente para vehículos turismo". Anim. Genet.Vol. 39 N° 5, pp. 561-563. 2008. [ Links ]

    [39] INECC and PNUD. "Actualización del inventario nacional de emisiones de gases de efecto invernadero 1990-2010, para las categorías de energía y procesos industriales". 2012. [ Links ]

    [40] IPCC. "IPCC Guidelines for National Greenhouse Gas Inventories". 2006. [ Links ]

    [41] J. Mosquera, S. Fernandez and J. Mosquera. "Análisis de emisiones de CO2 para diferentes combustibles en la poblacion de taxis en Pereira y Dosquebradas". N° 45, pp. 141-146. 2010. [ Links ]

    [42] J.A. Aranda Pinilla and J.A. Orjuela Castro. "Optimización multiobjetivo en la gestión de cadenas de suministro de biocombustibles. Una revisión de la literatura". Ingeniería. Vol. 20 N° 1, pp. 21-47. 2015. [ Links ]

    Recibido: 19 de Julio de 2019; Aprobado: 21 de Agosto de 2020

    * Autor de correspondencia: jose.ruiz@unad.edu.co

    Creative Commons License Este es un artículo publicado en acceso abierto bajo una licencia Creative Commons

     

    Artículos Relacionados

    Volumen 29 N° 3, Julio - Septiembre 2021

    pdf Índice

    Problema de ruteo de vehículos multi-objetivo con entregas y recogidas simultáneas y minimización de emisiones

    Ver en SciELO
    Problema de ruteo de vehículos multi-objetivo con entregas y recogidas simultáneas y minimización de emisiones

    SciELO - Scientific Electronic Library Online

     
    vol.29 número3¿Cuál es el rol de la identidad de marca en la creación de valor del sector eléctrico? Un análisis dinámico basado en modelosIncidencia del capital intelectual en el desempeño financiero de las universidades chilenas para el período 2014 al 2018 índice de autoresíndice de materiabúsqueda de artículos
    Home Pagelista alfabética de revistas  

    Servicios Personalizados

    Revista

    Articulo

    Como citar este artículo
    # Título Ver
    1
    Reconfiguración de redes eléctricas de media tensión basada en el algoritmo de Prim (2007)
    Angely Cárcamo-Gallardo, Luis García Santander, Jorge E. Pezoa
    HTML | PDF
    2
    Modelos de programación entera para un problema de programación de horarios para universidades (2007)
    Andrés Saldaña Crovo, Cristian Oliva San Martín, Lorena Pradenas Rojas
    HTML | PDF
    3
    Modelo ACO para la recolección de residuos por contenedores (2009)
    Eduardo Salazar Hornig, Nelson Ruiz Fuentealba
    HTML | PDF
    4
    Algoritmos evolutivos multiobjetivo aplicados a los proyectos de antenas microstrip (2009)
    Juliano Rodrigues Brianeze, Carlos Henrique da Silva-Santos, Hugo Enrique Hernández-Figueroa
    HTML | PDF
    5
    Tetraheurística sistémica (THS) para el TSP (2010)
    Jorge Iván Pérez Rave, Gloria Patricia Jaramillo Álvarez, Carlos Mario Parra Mesa, Luis Fernando Moreno Velásquez
    HTML | PDF
    6
    Un algoritmo genético para el problema de Job Shop Flexible (2011)
    Rosa Medina Durán, Lorena Pradenas Rojas, Víctor Parada Daza
    HTML | PDF
    7
    Localización de paraderos de detención y diseño óptimo de rutas en el transporte de personal (2011)
    Víctor M. Albornoz, Edward H. Johns
    HTML | PDF
    8
    Heurístico de simulación-optimización para la configuración de un sistema de estantería selectiva simple (2012)
    Mario C. Vélez Gallego, Diego A. Valencia Ramírez, Carlos A. Castro Zuluaga
    HTML | PDF
    9
    Modelación de los efectos de la compensación de potencia reactiva en sistemas de suministro eléctrico (2012)
    Davel Borges Vasconcellos, Ignacio Pérez Abril, Vicente León Martínez
    HTML | PDF
    10
    Un procedimiento para evaluar el riesgo de la innovación en la gestión del mantenimiento industrial (2012)
    Fernando F. Espinosa, Acires Dias, Gonzalo E. Salinas
    HTML | PDF
    11
    Compensación de potencia reactiva en sistemas desbalanceados utilizando algoritmos genéticos (2012)
    Davel Borges Vasconcellos, Ignacio Pérez Abril, Vicente León Martínez
    HTML | PDF
    12
    Producción de biohidrógeno a partir de residuos mediante fermentación oscura: una revisión crítica (1993-2011) (2012)
    Sergio Andrés Blanco Londoño, Tatiana Rodríguez Chaparro
    HTML | PDF
    13
    Planeamiento de expansión de la transmisión considerando múltiples escenarios de generación e incertidumbre en la demanda (2014)
    Carlos Adrián Correa, Ricardo Bolaños, Antonio Escobar
    HTML | PDF
    14
    Aplicación del método de composición musical al problema de asignación de unidades de enseñanza y aprendizaje (2014)
    Rafaela Blanca Silva López, Rosa Elena Cruz Miguel, Eric Alfredo Rincón García, Roman Anselmo Mora Gutiérrez, Antonin Ponsich
    HTML | PDF
    15
    Optimización topológica bidireccional con esquema de penalización de material y restricciones de desplazamiento (2015)
    Patricio Uarac P., Patricio Cendoya H., Juan Pablo Sanhueza O.
    HTML | PDF
    16
    Simulación y optimización para dimensionar la flota de vehículos en operaciones logísticas de abastecimiento-distribución (2015)
    Yasel José Costa Salas, Néstor Jaime Castaño Pérez
    HTML | PDF
    17
    Optimización de sistemas simulados a través de técnicas de superficie de respuesta (2015)
    Oscar Oviedo-Trespalacios, Rita Patricia Peñabaena
    HTML | PDF
    18
    Evaluación del desempeño del método de elementos de contorno multipolar rápido para procedimiento de optimización topológica (2015)
    Carla T. M. Anflor, Luciana M. Braga, Eder L. de Albuquerque
    HTML | PDF
    19
    Nuevo enfoque para la localización óptima de reconectadores en sistemas de distribución considerando la calidad del servicio y los costos de inversión (2016)
    Oscar D. Montoya G., Ricardo A. Hincapié I., Mauricio Granada E.
    HTML | PDF
    20
    Modelos de optimización para el diseño sostenible de cadenas de suministros de reciclaje de múltiples productos (2016)
    Michael Feitó Cespón, Roberto Cespón Castro, Manuel Alejandro Rubio Rodrí­guez
    HTML | PDF
    21
    Algoritmo basado en generación de columnas para resolver problemas combinados de ruteo e inventarios (2016)
    Carlos Franco-Franco, Juan Carlos Figueroa-García
    HTML | PDF
    22
    Optimo despliegue y enrutamiento de UDAP para infraestructura de medición avanzada basada en el algoritmo MST (2017)
    Cristian Ganán, Esteban Inga, Roberto Hincapié
    PDF
    23
    Nuevo enfoque para resolver el problema de planeamiento de sistemas de distribución considerando reconectadores automáticos (2017)
    Oscar D. Montoya G., Alejandro Grajales O., Ricardo A. Hincapié I., Mauricio Granada E.
    PDF
    24
    Diseño de una red de distribución a través de un modelo de optimización considerando agotados (2017)
    Harol Mauricio Gámez-Albán, Christopher Mejía-Argueta, Ricardo Arturo León Espinosa de los Monteros
    PDF
    25
    Localización óptima y confiable de instalaciones en una cadena de suministro (2017)
    Fernando González-Solano, Juan Escorcia-Caballero, Luis Patiño-Toledo
    PDF
    26
    Selección óptima de conductores en sistemas de distribución empleando el algoritmo búsqueda tabú (2018)
    O.D. Montoya G., A. Grajales, R.A. Hincapié I.
    PDF
    27
    Márgenes de contribución óptimos en servicios de alimentación usando control de inventarios con dependencia estadística (2019)
    Fernando Rojas
    HTML | PDF
    28
    Optimización de costos de producción agregada en empresas del sector textil (2020)
    Emiro Antonio Campo, Jose Alejandro Cano, Rodrigo Andrés Gómez-Montoya
    PDF
    29
    Slotting y picking: una revisión de metodologías y tendencias (2020)
    Juan Camilo Duque Jaramillo, Manuela Cuellar Molina, Juan Miguel Cogollo Flórez
    PDF
    30
    Operaciones portuarias de petróleo crudo: Una revisión bibliográfica sobre simulación e investigación operativa (2021)
    Ignacio de la Peña Zarzuelo, María Jesús Freire Seoane, Beatriz López Bermúdez
    PDF
    31
    Modelo de optimización LFSR basado en método de coeficientes adaptativos para sistemas reconfigurables de ERNC (2021)
    Cecilia Sandoval-Ruiz
    PDF


    Otros Artículos

    # Título Ver
    1
    Los movimientos de fondo representados por fronteras inmersas: experimentos numéricos usando las simulaciones de gran escala (2012)
    José Eduardo Alamy Filho, Harry Edmar Schulz, André Luiz Andrade Simões
    HTML | PDF
    2
    Efecto de la disminución de la velocidad vehicular en la durabilidad de una capa asfáltica (2013)
    Hugo Alexander Rondón Quintana, Fredy Alberto Reyes Lizcano, Carlos Felipe Urazán Bonells
    HTML | PDF
    3
    Modelo predictivo del espesor de la capa de óxido y microdureza en aluminio Al3003-B14 y Al6063-T6 anodizado usando análisis multifactorial (2011)
    Leonardo Eladio Vergara Guillén, Luis Manuel Nerey Carvajal, Víctor Manuel Guedez Torcates
    HTML | PDF

    Desarrollado por: Cristian Díaz Fonseca - informatica@cristianfonseca.cl