Circuitos eulerianos óptimos en grafos mixtosel problema del cartero mixto

  1. Campos Aucejo, Vicente
unter der Leitung von:
  1. Marco A. López Cerdá Doktorvater/Doktormutter

Universität der Verteidigung: Universitat de València

Jahr der Verteidigung: 1982

Gericht:
  1. Marco A. López Cerdá Präsident/in
  2. Rafael Romero Villafranca Sekretär/in
  3. Segundo Gutiérrez Cabria Vocal
  4. Miguel Sánchez García Vocal
  5. Ramiro Melendreras Gimeno Vocal

Art: Dissertation

Teseo: 7172 DIALNET

Zusammenfassung

PARTIENDO DEL ANALISIS DE LA FUERTE CONECTIVIDAD DE UN GRAFO MIXTO CON COSTES ASOCIADOS A SUS ARCOS Y ARISTAS SE ELABORA UN ALGORITMO EXACTO DE OBTENCION DEL CIRCUITO EULERIANO DE MINIMO COSTE SOBRE DICHO GRAFO, PARA ELLO SE UTILIZAN TECNICAS DE RELAJACION LAGRANGIANA QUE PROPORCIONA COTAS INFERIORES EN LOS NUDOS DEL ARBOL DE BRANCH AND BOUND ASOCIADO AL ALGORITMO. POR OTRA PARTE SE ELABORA UN NUEVO PROCEDIMIENTO PARA ENCONTRAR SOLUCIONES POSIBLES (NO NECESARIAMENTE OPTIMAS) QUE EN LA PRACTICA COMPUTACIONAL HA DADO BUENOS RESULTADOS. FINALMENTE LA OPERATIVIDAD DEL ALGORITMO SE HA TESTADO EN UNA COLECCION DE PROBLEMAS GENERADOS ALEATORIAMENTE CON LA AYUDA DE UN ORDENADOR UNIVAC 1100/60 TANTO LAS CARACTERISTICAS MAS IMPORTANTES DE LOS PROBLEMAS COMO LOS RESULTADOS COMPUTACIONALES CON DESCRITOS EN LA MEMORIA