1158070 Optimización en redes
1151032 Temas selectos de Ingeniería en Computación I
Trimestre 2013 Invierno
Evaluación del Tema 6: Problemas de ruteo
Fecha de entrega: 8 de abril de 2013 a las 10:00
Los alumnos de posgrado deberán hacer toda la evaluación. Los de
licenciatura deberán resolver una parte de cada sección de la
evaluación. Manden su tarea a mi correo (franz) en un pdf.
Sección I: Lectura de un capítulo de libro o de un artículo (6
puntos)
- Lea y haga un resumen de una cuartilla del artículo Routing
problems: A historical perspective.
- Lea y haga un resumen de una cuartilla del artículo The
vehicle routing problem: An overview of exact and approximate
algorithms.
Sección II: Solución de problemas prácticos (6 puntos)
Considere la gráfica no dirigida que tiene un vértice por cada
capital de cada estado del país, una arista entre cada dos
capitales si sus estados tienen una frontera común con costo igual
a la distancia en kilómetros entre las capitales.
- Resuelva el problema del cartero para esta gráfica.
- Resuelva el problema del cartero rural para esta gráfica
cuando las aristas requeridas son aquellas que unen capitales
cuyos nombres empiezan con consonante.
Sección III: Problemas teóricos (8 puntos)
- Demuestre que el problema del cartero es un caso especial del
problema del cartero rural.
- Demuestre que el problema del cartero con viento es un caso
especial del problema del cartero para gráficas mixtas.