LA TESIS FINAL REVISADA

ESCUELA SUPERIOR POLITÉCNICA DEL LITORAL

INSTITUTO DE CIENCIAS MATEMÁTICAS
ESCUELA DE GRADUADOS
PROYECTO DE GRADUACIÓN
PREVIO A LA OBTENCIÓN DEL TÍTULO DE:
“MAGÍSTER EN CONTROL DE OPERACIONES Y GESTIÓN LOGÍSTICA”
TEMA
DISEÑO DE UN SISTEMA DE SOPORTE DE DECISIONES PARA

RESOLVER EL PROBLEMA DE RUTEO EN UN
SERVICIO DE COURIER
AUTORES
JAMES TOMALÁ ROBLES
JOHNNY PINCAY VILLA

Guayaquil -EcuadorAÑO
2010


Dedicatorias
A la evolución inmediata de mi algoritmo genético: Gisela, mi compañera elegida y complemento vital; Ester, fruto del amor y lo mejor de los dos, engendrada y nacida en esta etapa de estudios; y Kevin, la extensión ya creada y evolucionada en nuestro hogar.
James Tomalá Robles
A quienes mientras vivieron me dieron felicidad, lecciones y ahora cuidan de mí desde su morada:mi abuela Felícita, pilar y amor vivo de la familia; mi primo Hernán, habrías aprendido esto y mucho más; mi hermana María, tus ojos brillaron pocas horas y nuestro amor para siempre.
Johnny Pincay Villa



Agradecimientos
Gracias a mi esposa por el apoyo que siempre encuentro en ella, incondicional y amoroso, pero sobre todo sabio e inspirado en Dios, que hace superar cada obstáculo denuestras vidas.
James Tomalá Robles
Necesitaría otra vida para demostrar lo agradecido que me siento con todos quienes entregaron su tiempo, paciencia, conocimientos y aliento... ¡gracias! Leofer, Lucy, Ámbar y Gloria, su confianza en mí marcó la diferencia.
Johnny Pincay Villa




Declaración Expresa
La responsabilidad por los hechos y doctrinas expuestas en este Proyecto de Graduación, así comoel Patrimonio Intelectual del mismo, corresponde exclusivamente al ICM (Instituto de Ciencias Matemáticas) de la Escuela Superior Politécnica del Litoral.
Ing. James Tomalá Robles Ing. Johnny Pincay Villa


Tribunal de Graduación
M. Sc. Fernando Sandoya Sánchez Ph. D. Walter Vaca Arellano
PRESIDENTE DIRECTOR DE TÉSIS
M. Sc. Pedro Echeverría Briones
VOCAL


Autores del proyecto degraduación
Ing. James Tomalá Robles Ing. Johnny Pincay Villa




Tabla de contenido

Capítulo 1.......................................................................................................................... 1

1. Introducción al problema de ruteo de vehículos....................................................1

1.1 Introducción....................................................................................................... 1

1.2 El problema de ruteo capacitado con ventanas de tiempo (CVRPTW).............3

1.2.1 Definición del CVRPTW. ......................................................................................3

1.2.2 Métodos de solución para los problemas de ruteo de vehículos. ...........................5

1.2.3 Complejidad algorítmica........................................................................................6

1.3 Definición del problema..................................................................................... 7

1.4 Formulación matemática del problema..............................................................9

1.4.1 Condiciones del sistema a modelar ................................................................ 9

1.4.2Formulación de programación matemática del CVRPSTW ................................10
Capítulo 2........................................................................................................................ 14

2. Desarrollo de una Heurística basada en Algoritmos Genéticos para el problema de ruteo con ventanas detiempo..................................................................................... 14
2.1 Introducción ..................................................................................................... 14

2.2 Revisión teórica de los Algoritmos Genéticos ................................................. 15

2.2.1 Algoritmos Evolutivos (AE) ................................................................................15

2.2.2 Algoritmos Genéticos (AG)...