Cartero Rural (RPP)
El problema del cartero rural es un problema de:
Teoría de grafos
Qué significa ARP en español?
Problemas de Ruteo de Arco.
En qué se aplica el Problema del Cartero Rural No Dirigido (URPP)?
Se aplica a grafos no dirigidos.
Qué es el circuito Euleriano?
Un recorrido cerrado que atraviesa cada arista del grafo exactamente una vez
Una de las técnicas más utilizadas para resolver el PCRD?
Relajación del problema
En qué consiste el Problema del Cartero Rural???
Encontrar el camino cerrado o circuito más corto que visita cada arista en un grafo no dirigido, conectado y no euleriano.
De qué trata el Street Sweeping Problem?
Busca encontrar la ruta más eficiente para que un vehículo de barrido limpie todas las calles de un área determinada. El objetivo es minimizar la distancia total recorrida por el vehículo, asegurando que cada calle sea limpiada al menos una vez.
En qué situaciones surge el URPP?
Surge en situaciones donde no hay direcciones específicas o restricciones unidireccionales en las aristas.
Qué algoritmos de emparejamiento estándar mencionamos:
Algoritmo Húngaro o el algoritmo Blossom.
El PCRND es una versión más general del...
PCRD
Qué tipo de recorrido tiene que hacer el RPP?
Debe visitar cada casa una vez y regresar al punto de partida
Con qué tipo de restricciones debe cumplir el vehículo en The Street Sweeping Problem?
Calles de sentido único, ventanas de tiempo y zonas prohibidas.
El URPP se utiliza a menudo en qué aplicaciones prácticas?
Mantenimiento de carreteras, inspecciones de servicios públicos y planificación turística.
Qué características tienen las aristas del Problema del Cartero Rural Dirigido (PCRD)?
Las aristas del grafo tienen una dirección.
Las soluciones óptimas del PCRND también son soluciones óptimas del PCRD.
Verdadero o Falso?
Verdadero.
Cómo se representa matematicamente?
Cuáles son las caracteristicas únicas del Problema de Remoción de Nieve? (Snow plowing problem)
Acumulación de nieve, la variación de la densidad de nieve y la necesidad de priorizar ciertas carreteras según el volumen de tráfico y su importancia.
Algoritmos y heurísticas que se han desarrollado para abordar el URPP?
Algoritmo de Christofides, algoritmos genéticos y optimización de colonias de hormigas.
Objetivo del PCRD?
Encontrar un circuito que recorra cada arista del grafo dirigido al menos una vez, comenzando y terminando en un vértice dado, y minimizando el costo total del recorrido.
A qué se refiere el problema de Stacker Crane Problem ?
Se refiere a la tarea de mover una pila de bloques de una ubicación a otra utilizando una grúa apiladora.
Qué algoritmos se pueden utilizar para resolver el RPP? (2)
Algoritmo del Cartero Chino o el Algoritmo de Christofides.
Cómo se representan las direcciones en el Problema de Entrega de Correo?
Como nodos en una red.
Ahorros de costos, una mejor asignación de recursos y una mejor entrega de servicios en áreas rurales.
El PCRD es un problema de tipo...
NP-completo.
(No se conoce un algoritmo eficiente para resolverlo de manera exacta en tiempo polinómico)
Objetivo del Stacker Crane Problem?
El objetivo es determinar el número mínimo de movimientos necesarios para trasladar la pila desde su ubicación inicial a su ubicación final.