Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 25 vistas

    PResentación ALNS

    Cargado por

    Jared Arturo Olmos Villagran
    Este documento describe el problema de ruteo de camiones y remolques con restricciones de capacidad y ventanas de tiempo. Explica la metaheurística ALNS y su pseudocódigo propuesto, incluyendo operadores de eliminación como aleatoria, del peor y de clústeres, e inserción voraz para encontrar soluciones óptimas.

    Copyright:

    © All Rights Reserved
    Descargue como PPTX, PDF, TXT o lea en línea desde Scribd

    PResentación ALNS

    Cargado por

    Jared Arturo Olmos Villagran
    25 vistas10 páginas
    Este documento describe el problema de ruteo de camiones y remolques con restricciones de capacidad y ventanas de tiempo. Explica la metaheurística ALNS y su pseudocódigo propuesto, incluyendo operadores de eliminación como aleatoria, del peor y de clústeres, e inserción voraz para encontrar soluciones óptimas.

    Título original

    PResentación ALNS.pptx

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    PPTX, PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Este documento describe el problema de ruteo de camiones y remolques con restricciones de capacidad y ventanas de tiempo. Explica la metaheurística ALNS y su pseudocódigo propuesto, incluyendo operadores de eliminación como aleatoria, del peor y de clústeres, e inserción voraz para encontrar soluciones óptimas.

    Copyright:

    © All Rights Reserved
    Descargue como PPTX, PDF, TXT o lea en línea desde Scribd
    Descargar como pptx, pdf o txt
    25 vistas10 páginas

    PResentación ALNS

    Cargado por

    Jared Arturo Olmos Villagran
    Este documento describe el problema de ruteo de camiones y remolques con restricciones de capacidad y ventanas de tiempo. Explica la metaheurística ALNS y su pseudocódigo propuesto, incluyendo operadores de eliminación como aleatoria, del peor y de clústeres, e inserción voraz para encontrar soluciones óptimas.

    Copyright:

    © All Rights Reserved
    Descargue como PPTX, PDF, TXT o lea en línea desde Scribd
    Descargar como pptx, pdf o txt
    de 10

    Algoritmo de extensión de

    ALNS (Búsqueda amplia de


    vecindarios adaptativa)
    Ing. Jared Arturo Olmos Villagrán
    Maestría en Cómputo Aplicado
    UACJ
    Contenido
    • Problema del ruteo del camión y su remolque con restricción de capacidad y
    ventanas de tiempo (CTTRPTW por sus siglas en ingles)
    • Introducción a la metaheuristica ALNS
    • Pseudocódigo de ALNS propuesto
    • Operadores de eliminación
    • -Eliminación aleatoria
    • -Eliminación del peor
    • -Eliminación de clústeres
    • Operadores de inserción
    • -Inserción voraz
    Problema del ruteo del camión y su remolque con restricción
    de capacidad y ventanas de tiempo (CTTRPTW)

    En el TTRP, un conjunto de rutas que


    consisten en rutas completas de vehículo
    o rutas puras de vehículo y un rutas
    puras de camión son construidas con el
    fin de que la distancia total recorrida por
    la flota sobre los tres tipos de rutas sea
    minimizada satisfaciendo todas las
    restricciones

    Semet F, Taillard E (1993). Solving real-life vehicle routing problems efficiently using tabu search. Ann Oper Res 41: 469–488
    I.-M. Chao, «A tabu search method for the truck and trailer routing problem,» Computers & Operations Research, vol. 29,
    pp. 33-51, 2002.
    Contenido
    • Problema del ruteo del camión y su remolque con restricción de capacidad y
    ventanas de tiempo (CTTRPTW por sus siglas en ingles)
    • Introducción a la metaheuristica ALNS
    • Pseudocódigo de ALNS propuesto
    • Operadores de eliminación
    • -Eliminación aleatoria
    • -Eliminación del peor
    • -Eliminación de clústeres
    • Operadores de inserción
    • -Inserción voraz
    Introducción a la metaheuristica ALNS
    • Metaheuristica de búsqueda amplia de vecindarios adaptativa
    utilizada para la optimización.
    • Se encarga de buscar a través de soluciones vecinas para encontrar
    una solución óptima.
    Introducción a la metaheuristica ALNS
    • Metaheuristica de búsqueda amplia
    Técnica dede vecindarios
    búsqueda adaptativa
    de soluciones que
    utilizada para la optimización. realizan exploraciones profundas pero
    limitadas en tiempos de cómputo
    • Se encarga de buscar a través de soluciones vecinas para encontrar
    razonables.
    una solución óptima.

    Orrego Cardoz, Juan Pablo; Ospina Toro, Daniela; Toro Ocampo, Eliana Mirledy Solución al Problema de Ruteo de Vehículos
    con Capacidad Limitada (CVRP) usando una técnica metaheurística Scientia Et Technica, vol. 21, núm. 3, septiembre, 2016,
    pp. 225-233
    Contenido
    • Problema del ruteo del camión y su remolque con restricción de capacidad y
    ventanas de tiempo (CTTRPTW por sus siglas en ingles)
    • Introducción a la metaheuristica ALNS
    • Pseudocódigo de ALNS propuesto
    • Operadores de eliminación
    • -Eliminación aleatoria
    • -Eliminación del peor
    • -Eliminación de clústeres
    • Operadores de inserción
    • -Inserción voraz
    Pseudocódigo de ALNS propuesto
    Dados:
    Una solución factible inicial
    Un número de clientes a eliminar por iteración de forma aleatoria entre
    Una probabilidad p de aceptación de una solución peor
    Una tasa de enfriamiento de la temperatura c
    Unas puntuaciones , en función de la calidad de la solución nueva obtenida
    Hacer:
    1. ,, 0, 0
    2. Repetir
    3. Escoger el par destrucción-reparación (d,r) cuyo peso sea
    4. esultado de aplicar (d,r) con a s,
    5. Si entonces , ,
    6. Sino si entonces
    7. Sino si entonces , no se incrementa
    8. , ,
    9. Hasta Criterio de Parada es alcanzado
    10. Devolver

    • Parragh SN, Cordeau JC (2017). Branch-and-price and adaptive large neighborhood search for the truck and trailer routing problem with time
    windows. COR 83: 28 – 44
    Contenido
    • Problema del ruteo del camión y su remolque con restricción de
    capacidad y ventanas de tiempo (CTTRPTW por sus siglas en ingles)
    • Introducción a la metaheuristica ALNS
    • Pseudocódigo de ALNS propuesto
    • Operadores de Eliminación e Inserción
    Operadores de Eliminación e Inserción
    • Eliminación relacional (Shaw, 1997)
    • Eliminación del peor (Ropke & Pisinger, 2006a)
    • Eliminación aleatoria (Ropke & Pisinger, 2006a)
    • Eliminación de clústeres (Ropke & Pisinger, 2006b)

    • Inserción voraz (Ropke & Pisinger, 2006a)

    • Ropke S, Pisinger D (2006a). An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Window. Trans Sci 40:
    455-472
    • Ropke S, Pisinger D (2006b). A unified heuristic for a large class of Vehicle Routing Problems with Backhauls. EJOR 171: 750 - 775

    También podría gustarte