APLICACION DE CARTERO CHINO

2014 - I

DEDICATORIA:

A nuestra facultad por todo lo que dedicación, paciencia, esmero y profesionalismo nos dirigió durante todo este trayecto, con el objetivo de enseñarnos e instruirnos para nuestro futuro.

atc

INDICE

INTRODUCCION

OBJETIVOS

OBJETIVO GENERAL

OBETIVOS ESPECIFICOS

CAPITULO I: TEORIA DEL PROBLEMA DEL CARTERO CHINO

CONCEPTOS PARA LA SOLUCIÓN DEL PROBLEMA DEL CARTERO CHINO

GRAFO CONEXO

GRAFO EULERIANO

ALGORITMO DE FLEURY

ALGORITMO DE DIJSKTRA

ALGORITMO DE EMPAREJAMIENTO DE EDMONDS

DIAGRAMA PARA SOLUCIÓN DEL CARTERO CHINO

CAPITULO II: APLICACIÓN DEL PROBLEMA DEL CARTERO CHINO

DESCRIPCION DEL PROBLEMA

DESCRIPCION DEL SERVICIO

SECTORIZACION Y RECOPILACION DE DATOS

DESCRIPCIÓN DEL SISTEMA DE ENTREGA

DISTRIBUCION DE ENTREGA

REQUERIMIENTOS Y LOGÍSTICA PARA LA IMPLEMENTACIÓN

COSTOS PARA LA IMPLEMENTACIÓN DEL SISTEMA “PANES CALIENTES”

CONCLUSIONES Y RECOMENDACIONES

BIBLIOGRAFIA

INTRODUCCION

El problema del cartero chino (CPP) consiste en encontrar un circuito de coste mínimo, en un grafo no dirigido, que atraviesa cada arista al menos una vez. Este problema fue propuesto por Mei-Ko en 1962 y resuelto eficientemente por Edmonds y Johnson en 1973.

En el presente trabajo se presenta una breve explicación concisa de las diferentes soluciones para el problema del cartero chino, el cual tiene una aplicación en el Capítulo II para la solución de un problema real el cual nos indica brevemente sobre los aspectos a tomar para la selección de una ruta óptima para la distribución de panes a un cierto sector.

OBJETIVOS

OBJETIVO PRINCIPAL

Plantear una nueva propuesta para la entrega de panes a domicilio teniendo como base los conceptos de la solución del problema del cartero chino.

ONJETIVOS ESPECIFICOS

 Analizar los costos de implementación de una propuesta de delivery de panes.

 Crear nuevas oportunidades laborales de medio tiempo y al mismo tiempo ayudar a las familias a tener más tiempo por las mañana de hacer sus actividades.

CAPITULO I

TEORÍA DEL PROBLEMA DEL CARTERO CHINO

CONCEPTOS PARA LA SOLUCIÓN DEL PROBLEMA DEL CARTERO CHINO

GRAFO CONEXO

Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b.

Un grafo es doblemente conexo si cada par de vértices está conectado por al menos dos caminos disjuntos; es decir, es conexo y no existe un vértice tal que al sacarlo el grafo resultante sea disconexo.

Es posible determinar si un grafo es conexo usando un algoritmo Búsqueda en anchura (BFS) o Búsqueda en profundidad (DFS).

En términos matemáticos la propiedad de un grafo de ser (fuertemente) conexo permite establecer con base en él una relación de equivalencia para sus vértices, la cual lleva a una partición de éstos en "componentes (fuertemente) conexas", es decir, porciones del grafo, que son (fuertemente) conexas cuando se consideran como grafos aislados. Esta propiedad es importante para muchas demostraciones en teoría de grafos.

GRAFO EULERIANO

Cubre todas las líneas de un grafo, comenzando y terminando en un mismo vértice, recorriendo sin repetición y en forma continua todas las líneas de un grafo G cualquiera. Cuando tal recorrido existe, se denomina euleriano y un grafo que se puede trazar mediante un recorrido euleriano se llama grafo euleriano.

En la fig. 3.11, G1 es obviamente un grafo euleriano; G2 no lo es, a pesar de que se puede trazar continuamente, ya que el recorrido comienza y termina en vértices distintos; finalmente, G3 no es un grafo euleriano, porque no se puede trazar continuamente.

TEOREMA 1.- Existencia de trayectorias de Euler.

1. Si un grafo tiene más de dos vértices de grado impar, entonces no puede tener una trayectoria de Euler.

2. Si un grafo conexo tiene exactamente dos vértices de grado impar, entonces tiene por lo menos una trayectoria de Euler. Cualquier trayectoria de Euler debe iniciar en uno de los vértices de grado impar y terminar en el otro.

ALGORITMO DE FLEURY

Este algoritmo permite determinar un circuito de Euler, y un circuito de Euler es aquel que recorre todas las aristas de un grafo pasando solo una vez.

Los pasos a seguir en el algoritmo de Fleury para encontrar una trayectoria de Euler son:

1. Verificar que el grafo cumpla con los criterios de grafos Euleriano (todos los vértices deben tener grado par, salvo dos como mucho).

2. Escoger un vértice de grado impar. En caso de que no exista, se puede escoger cualquier vértice.

3. En cada paso, recorre cualquier arista disponible, eligiendo un puente solo cuando no haya alternativa. Al recorrer la arista borrarla y continuar el proceso hasta que todos los vértices tengan grado cero.

PSEUDOCODIGO DEL ALGORITMO DE FLEURY

Bondy en “Graph Theory”, donde da sobre programación del Algoritmo de Fleury.

1: nodo = SeleccionarNodo (ConjuntoNodos) (La función “Seleccionar Nodo” elegirá un nodo de grado impar si es posible)

2: WHILE (Conjunto Nodos ≠ VACÍO) DO

arista = Seleccionar Arista Adyacente Nodo (nodo) (La función “Seleccionar Arista Adyacente Nodo” elegirá una arista puente solamente como último recurso)

3: ConjuntoAristas = ConjuntoAristas – arista

ConjuntoNodos = Quitar VérticesdecardinalCero (Conjunto Nodos)

IF Conjunto Nodos ≠ VACÍO THEN

nodo = SeleccionarNodoAdyacenteArista (arista, ConjuntoNodos)

END IF

END WHILE

4: FIN DEL ALGORITMO.

ALGORITMO DE DIJSKTRA

También llamado algoritmo

...