Tesis de Transporte

ESCUELA SUPERIOR POLITÉCNICA DEL LITORAL
INSTITUTO DE CIENCIAS MATEMÁTICAS
“DISEÑO DE RUTAS DE TRANSPORTE DE PERSONAL

APLICANDO MODELIZACIÓN MATEMÁTICA PARA RESOLVER
EL PROBLEMA DE ENRUTAMIENTO VEHICULAR
CAPACITADO CON VENTANAS DE TIEMPO”
TESIS DE GRADO
Previa a la obtención del Título de:
INGENIERO EN LOGÍSTICA Y TRANSPORTE
AUTORES:
Lorena Marina Loor Vélez
Patricia Elizabeth Sánchez Villamar
GUAYAQUIL – ECUADOR
Año: 2012
AGRADECIMIENTOS
Antes que todo quiero agradecer en primer lugar a mi Dios por la salud,
sabiduría y por estar siempre conmigo en todo momento de mi vida, a mí
querida madre Nelly por sus consejos y gran amor en todo tiempo, a mis
abuelos y tíos quienes siempre nos han extendido sus manos, a mi novio
Gustavo por estar presente en los momentos que más lo necesité, a los
hermanos en Cristo, Gloria y Eloy por su noble ayuda, a mis amigas Patricia,
Gisella y Maritza por brindarme su cariño durante todo el tiempo que
estuvimos juntas.
Lorena Loor Vélez
A Dios por no dejarme sola, a mis padres Jenny y Daniel por su apoyo, mis
hermanos Andrea, Victor Aleja e Isaías y a mis amigos en especial a Carlos
Roberto, Marina e Iris por su apoyo incondicional en todo momento,
alentándome para seguir adelante
Patricia Sánchez Villamar

DEDICATORIAS
A ti mi amado Dios por brindarme la vida y regalarme una hermosa familia, a

mis queridos padres quienes han luchado muy duro por darme una carrera
para mi futuro, a mis hermanos Luis y Mónica por su gran cariño, los amo
mucho.
Lorena Loor Vélez
A Dios por todas las bendiciones que ha derramado sobre mí, a mis padres
por su constante apoyo incondicional demostrándome que los sueños son
posibles de cumplir. A mis hermanos, a todas las personas que han creído en
mí, a mi Amor Luo por ayudarme sin importar nada.
Patricia Sánchez Villamar

TRIBUNAL DE GRADUACIÓN
________________________
Ing. Víctor Vega Chica
DIRECTOR DE TESIS DE GRADO
________________________ ________________________
Ing. Erwin Delgado Ing. Xavier Cabezas
VOCAL PRINCIPAL PRESIDENTE
DECLARACIÓN EXPRESA
“La responsabilidad del contenido de esta
Tesis de Grado, me corresponden
exclusivamente; y el patrimonio intelectual de
la misma a la ESCUELA SUPERIOR
POLITÉCNICA DEL LITORAL”
(Reglamento de Graduación de la ESPOL)
Lorena Loor Vélez Patricia Sánchez Villamar

I
RESUMEN
En el presente trabajo se implementa un modelo de programación matemática
que tiene como objetivo principal el diseño de rutas, la misma que cumplan
con las restricciones de ventanas de tiempo, capacidad de los vehículos de una
empresa la cual realiza la función de transporte de personal a otras entidades.
La tesis está estructurada en tres capítulos. El primer capítulo consiste en un
estudio de la situación actual de la empresa, que involucra, paraderos, clientes,
vehículos y costos de las rutas definidos por la empresa. En la segunda etapa
se analiza el modelo matemático que mejor se ajuste a las condiciones reales.
En el último capítulo se entregan los resultados de la investigación, que como
se mencionó anteriormente es el diseño de rutas óptimas y además las
recomendaciones necesarias.
La elaboración de este trabajo pretende demostrar como la optimización de las
rutas ayudan a reducir los costos de transportación.

II
ABSTRACT
This article implements a mathematical programming model that has as main
objective the design of routes, the same that meets the constraints of time
windows, vehicle capacity of a company which performs the function
of transporting personnel to other entities. It is structured as follows: The first
part contains an introduction to the problem. The second section is a study of
the current business situation, involving, bus stops, customers, vehicles and
costs of the routes defined by the company. The third stage analyzes the
mathematical model that best fits the actual conditions. In the fourthphase the
results of the investigation are given, which as mentioned above is the design
of optimal routes and finally the conclusions, acknowledgments and necessary
recommendations are mentioned. The preparation of this paper aims
to demonstrate how route optimization helps reduce transportation costs.

III
ÍNDICE GENERAL
RESUMEN .................................................................................................. I
ABSTRACT ................................................................................................ II
ÍNDICE GENERAL .................................................................................... III
ÍNDICE DE FIGURAS ............................................................................. VII
ÍNDICE DE TABLAS............................................................................... VIII
CAPÍTULO 1
1. INTRODUCCIÓN ................................................................................ 1
1.1 Justificación e importancia ........................................................... 2
1.2 Objetivo General .......................................................................... 2
1.3 Objetivos específicos ................................................................... 3
CAPÍTULO 2
2. ANÁLISIS DE LA SITUACIÓN ACTUAL ............................................ 4
2.1 La problemática básica. ............................................................... 5
2.2 Clientes ........................................................................................ 6
2.3 Depósitos ..................................................................................... 8
2.4 Rutas ........................................................................................... 9

IV
2.5 Paraderos .................................................................................. 11
2.6 Vehículos ................................................................................... 18
2.7 Costos Fijos y Variables ............................................................ 21
2.7.1 Costos Fijos .................................................................... 21
2.7.2 Costos Variables ............................................................. 22
CAPÍTULO 3
3. EL PROBLEMA DE ENRUTAMIENTO VEHICULAR ........................ 24
3.1 Estado el Arte del CVRPTW .................................................... 24
3.2 El problema de ruteo capacitado con ventanas de tiempo
(CVRPTW)…………………………………………………. ......... 28
3.2.1 Capacitated Vehicle Routing Problem (CVRP) ............ 31
3.2.2 Times Windows Vehicle Routing Problem (TWVRP) ... 32
3.2.3 Vehicle Routing Problem with multiple depot (MDVRP)
..................................................................................... 33
3.2.4 Vehicle Routing Problem with multiple depot- Times ... 34
3.3 Definición formal del problema de ruteo capacitado con
ventanas de tiempo (CVRPTW) .............................................. 38
3.3.1 Parámetros e índices ................................................... 39
3.3.2 Variables ...................................................................... 40
3.3.2.1 Variables de decisión binaria ........................ 40
3.3.2.2 Variables de decisión real ............................. 40
3.3.2 Función Objetivo .......................................................... 41

V
3.3.2 Restricciones ................................................................ 41
3.4 Complejidad computacional .................................................... 43
CAPÍTULO 4
4. ANÁLISIS COMPUTACIONAL (APLICACIÓN DEL MODELO
MATEMÁTICO CVRPTW) ................................................................ 45
4.1 Herramienta tecnológicas ...................................................... 45
4.1.1 Google Maps............................................................... 46
4.1.2 Google Earth ............................................................... 47
4.1.2.1 Ubicación geográfica de los nodos ............... 48
4.1.2.2 Aplicación del método de barrido .................. 51
4.1.2.3 Cálculo de distancias y tiempos ..................... 57
4.1.3 GAMS .......................................................................... 58
4.2 Modelo Matemático para el diseño de rutas óptimas............... 59
4.2.1 Conjunto de Índices..................................................... 60
4.2.2 Vectores de Datos ...................................................... 61
4.2.3 Variables ..................................................................... 63
4.2.4 Restricciones .............................................................. 64
4.2.4.1 Función objetivo ............................................ 65
4.2.4.2 Visitas a las paradas ..................................... 66
4.2.4.3 Salida desde un mismo depósito .................. 66
4.2.4.4 Capacidad del vehículo ................................. 67

VI
4.2.4.5 Selección de vehículo por parada ................. 67
4.2.4.6 Cumplimiento del horario .............................. 67
4.2.4.7 Eliminación de subtours ................................. 68
4.3 Resultados Obtenidos ........................................................... 69
4.4 Post optimizaciòn .................................................................. 76
4.5 VRPCTW versus ANALISIS ACTUAL ................................... 78
4.6 Comparación con otras Heuristicas ....................................... 80
CAPÍTULO 5
5.CONCLUSIONES Y RECOMENDACIONES .......................................... 82
5.1 Conclusiones ......................................................................... 82
5.2 Recomendaciones ................................................................. 84
APÉNDICES ............................................................................................. 87
GLOSARIO ............................................................................................. 117
BIBLIOGRAFÍA....................................................................................... 118
VII
ÍNDICE DE FIGURAS
Figura 2.1. Ubicación espacial de los clientes de la empresa. Mapa del

centro de la ciudad de Guayaquil de Google Earth........... 14
Figura 2.2. Ubicación del depósito en Google Maps .......................... 15
Figura 2.3. Ruta 2 del departamento de Operaciones ........................ 17
Figura 2.4. Paraderos de la Ruta 3. Mapa del centro de la ciudad de
Guayaquil en Google Earth ................................................ 18
Figura 2.5. Fotos de los vehículos utilizados ...................................... 28
Figura 3.1. Ejemplo del Problema de Enrutamiento vehicular ............. 35
Figura 3.2. Ejemplo clásico del Agente Viajero (TSP) ......................... 38
Figura 3.3. Ejemplo del Problema de Enrutamiento vehicular con
Capacidad .......................................................................... 40
ventanas de tiempo............................................................ 41
múltiples depósitos ............................................................ 42
Figura 3.6. Ejemplo del Problema de Enrutamiento vehicular
capacitado con ventanas de tiempo ................................... 43
Figura 4.1. Aplicación del método de barrido....................................... 61

Figura 4.2. Cálculo de distancias por formula de Manhattan .............. 65
Figura 4.3. Resultados obtenidos en Gams ......................................... 67
Figura 4.4. Ruta pos optimizada .......................................................... 85
Figura 4.5. Comparación de costos por departamento ........................ 87
Figura 4.6. Resultados de la página VRP Web................................... 88
Figura 4.7. Resultados obtenidos con el modelo ................................ 89
VIII
ÍNDICE DE TABLAS
Tabla 2.1 Nombre-Dirección y Coordenadas Geográficas de algunos

Clientes .............................................................................. 15
Tabla 2.4 Penalización por retraso .................................................... 17
Tabla 2.5. Paraderos del departamento Operaciones ....................... 19
Tabla 2.6 Paraderos del departamento FACTURACIÓN ................... 22
Tabla 2.7 Paraderos del departamento ADMINISTRATIVO .............. 24
Tabla 2.8 Capacidad de los vehículos en las diferentes rutas ........... 26
Tabla 2.9 Costo fijo mensual por ruta ............................................... 29
Tabla 2.10 Costo Variable estimado de las rutas por día .................... 31
Tabla 4.1 Coordenadas geográficas del destino y depósito .............. 56
Tabla 4.2 Coordenadas geográficas de los paraderos de Operaciones
......................................................................................... 57
Tabla 4.3 Método de barrido de los paraderos del departamento de
Operaciones ...................................................................... 62
Tabla 4.4 Conjunto de índices ........................................................... 68
Tabla 4.5 Conjunto de Vectores de datos .......................................... 69
Tabla 4.6 Conjunto de variables decisión ......................................... 71
Tabla 4.7 Resultados obtenidos de las rutas del departamento de
OPERACIONES................................................................. 78
Tabla 4.8 Resultados obtenidos de las rutas del departamento
FACTURACIÓN ................................................................. 81
Tabla 4.9 Resultados obtenidos de las rutas del departamento de
ADMINISTRACIÓN ............................................................ 83
Tabla 4.10 Resultados obtenidos a las rutas que presentan cruces ... 86
Tabla 4.11 Comparación de los costos actuales con los anteriores .... 87
1
CAPÍTULO 1
1. INTRODUCCIÓN
El transporte es un medio muy usado por los seres humanos, por lo que se
convierte en una necesidad donde se encuentran presentes elementos tales
como infraestructura, vehículo y operador. Esta tesis presenta una alternativa
técnica desarrollada por la investigación de operaciones, con el objetivo de
crear rutas basados en un depósito para transportar a los empleados desde
cierto paradero hasta su lugar de trabajo, el cual consiste en aplicar una
programación matemática y a través de ella encontrar una solución para el
problema de enrutamiento vehicular con restricción de capacidad y ventanas de
tiempo, que permita minimizar el costo de la ruta.
Existen factores que son difíciles de parametrizar como son el tráfico,
accidentes de tránsito, huelgas, desastres naturales por lo que se opta la
aplicación de métodos muy prácticos en sus operaciones, lo cual no es una
buena planificación que influyen en altos costos e insatisfacción del cliente.

2
1.1 Justificación e importancia
Muchas empresas ofrecen servicios de personal, sin embargo la
mayoría no aprovechan sus recursos al cien por ciento. Para la
resolución de este tipo de problemas se debe tener en cuenta la
satisfacción del cliente, distancia entre paraderos, tiempo de viaje,
ventanas de tiempo, tiempo de servicio. Se propondrá un modelo
matemático para mejorar la situación actual.
Hay que considerar ciertos parámetros que son establecidos por la
empresa como los paraderos, con los cuales se procederá a diseñar
rutas óptimas para compararlas con las rutas actuales.
1.2 Objetivo General
Emplear un Modelo Matemático y a partir de ello, encontrar una
solución para el problema de enrutamiento vehicular capacitado con
restricciones horarias, con el fin de crear óptimas rutas que transportan
el personal de una compañía ubicada en las cercanías al puerto de la
ciudad de Guayaquil.
3
1.3 Objetivos específicos
 Minimizar los costos
 Mejorar la utilización de los vehículos
 Cumplir con las ventanas horarias establecidas
 Modelar el problema de enrutamiento vehicular con restricción de
capacidad y ventanas de tiempo para la trasportación de
personas.
 Recolectar los datos necesarios para la aplicación del modelo.
 Comparar la situación actual con la propuesta a presentar.
 Reestructurar las trayectorias de los vehículos.

4
CAPÍTULO 2
2. ANÁLISIS DE LA SITUACIÓN ACTUAL
Hoy en día las organizaciones se concentran en su CORE-ACTIVITY, para
tener pleno KNOW HOW y de esta manera incrementar el nivel de servicio
a realizar, es por esto que efectúan la acción de subcontratar a una
compañía externa con el fin de delegar funciones o procesos que no
generan ingresos pero que son importantes para la generación de los
mismos. Esta es la situación de una empresa ubicada en las cercanías al
puerto de la ciudad de Guayaquil y que su actividad principal es el manejo y
operaciones de containers y terminales multipropósito del Puerto Libertador
Simón Bolívar, pero que la transportación de su personal y el hecho de que
estén puntualmente en las instalaciones es de gran importancia. Para
cumplir con este propósito ellos proceden a realizar un Outsourcing con una
compañía de transporte de personal.
El eje de este estudio se centra en esta compañía subcontratada, que
actualmente se encuentra ubicada en el centro de la ciudad de Guayaquil y
que cuenta con un departamento de logística que cumple con la función de

5
planificación de las rutas de trasporte el cual consiste en la creación,
monitoreo, supervisión de las mismas y todo los elementos que se
encuentran inmersos.
2.1 La problemática básica.
Actualmente la empresa realiza la planificación de sus rutas de manera
tradicional, lo que significa que no existe optimización en sus procesos,
por lo que genera un alto costo al brindar un buen servicio para poder
cumplir con los requerimientos de sus clientes, ya que en algunas rutas
existe un exceso en la capacidad del vehículo y en otras existe carencia
de clientes, esto se debe a la mala distribución de los mismos en las
rutas.
Por otro lado se encuentra el tema de los horarios ya que todos los
clientes deben estar presentes en el destino antes de las 7h00, en el
caso del departamento de operaciones, 8h00 si es el caso del
departamento de Facturación, y el departamento de Administración
debe presentarse antes de las 8h25, sin importar los inconvenientes
que se presenten en el camino.

6
2.2 Clientes
Todos los clientes se encuentran dispersos geográficamente, los cuales
se dirigen a los paraderos ubicados cerca de sus hogares, ya que los
vehículos realizan el recorrido por paraderos y no puerta a puerta.
También estos deben de estar a tiempo en los diferentes paraderos
para ser recogidos, ya que los vehículos tienen un tiempo de pasada
por cada paradero.
Se dividen por departamento los cuales son: Operaciones, Facturación
y Administración.
Se establece la ubicación geográfica por medio de las direcciones de
cada cliente utilizando la herramienta de Google Earth para determinar
sus coordenadas geográficas. El sistema de coordenadas geográficas
es un sistema de referencia que utiliza las dos coordenadas angulares,
latitud (Norte y Sur) y longitud (Este y Oeste) y sirve para determinar los
ángulos laterales de la superficie terrestre. La latitud mide el ángulo
entre cualquier punto y el Ecuador. Las líneas de latitud se llaman
paralelos y son círculos paralelos al Ecuador en la superficie de la
Tierra. La latitud es el ángulo que existe entre un punto cualquiera y el
Ecuador, medida sobre el meridiano que pasa por dicho punto. La
longitud mide el ángulo a lo largo del Ecuador desde cualquier punto de
la Tierra. Combinando estos dos ángulos, se puede expresar la posición

7
de cualquier punto de la superficie de la Tierra1. Se ilustra algunos
clientes en la figura 2.1.
Figura 2.1: Ubicación espacial de los clientes de la empresa. Mapa del centro
de la ciudad de Guayaquil de Google Earth
A continuación se presenta la tabla 2.1 con la dirección domiciliaria y los
nombres de algunos trabajadores ubicados en la zona norte de la
ciudad de Guayaquil.
3
Coordenadas Geográficas según Wikipedia. http://es.wikipedia.org/wiki/Coordenadas_geogr%C3%A1ficas . Revisado
el 17 abril del 2012.
8
TABLA 2.1
NOMBRE-DIRECCIÓN Y COORDENADAS GEOGRÁFICAS DE
ALGUNOS CLIENTES
Nombre del Trabajador Domicilio Colonia Longitud Latitud

CHICAIZA JUNTA MARIO MAPASINGUE ESTE COOP 27 ENERO NORTE -79,551696 -2,91670
LEONARDO MZ 12 V. 28
MALDONADO ARMIJOS LOMAS DE FLORIDA, COOP, HENNER NORTE -79552700 -2, 8363
JOSE PATRICIO PARRALES MZ 910 SL. 10
MEJÍA OLIVARES COLINAS DE LA ALBORADA MZ 725 NORTE -79,542021 -2,94402
IGNACIO ALFREDO SL. 20
ROBELLY AGUILAR CDLA PEDRO MENENDEZ MZ 6 V 26 NORTE -79,524201 -2,10167
MARCOS CRISTOBAL
ROSALES BORBOR HORIZONTES DEL FORTÍN MZ 2 SL. 6 NORTE -79,572012 -2,72320
DANIEL ARMANDO
2.3 Depósitos
En este caso solo existe un depósito que se encuentra ubicado en la
Ciudadela Las Garzas Mz. 7 villa 8, tal como se ilustra en la figura 2.2,
en donde están inicialmente los vehículos que parten para cumplir las
diferentes rutas y posteriormente finalizar en dicho depósito. El depósito
no cuenta con una ventana de tiempo.
Figura 2.2: Ubicación del depósito en Google Map

9
2.4 Rutas
La compañía tiene establecidas 12 rutas, las cuales están distribuidas
en tres departamentos antes mencionados que son: Operaciones con 5
Rutas, Facturación con 3 Rutas y Administrativo con 4 Rutas.
Cada ruta tiene asociado un tiempo de recorrido y Km recorridos, a
demás de paraderos, un vehículo y por ende clientes asignados a dicha
ruta.
Las rutas del departamento de Operaciones deben llegar al puerto de
Guayaquil a las 06h20, y esto se debe a que los clientes tienen que
marcar tarjeta antes de las 07h00 para que no se genere un atraso y
posteriormente una multa, aunque lo más importante es que estén a
tiempo para comenzar sus labores. Con las rutas del departamento de
Facturación, deben de llegar antes de las 7h40, para empezar sus
labores a las 8h00, y las rutas del departamento de Administración,
deben de estar antes de las 8h25.
Un retraso en la hora de llegada representa una queja del cliente y esto
repercute en una penalización impuesta por la compañía a quien se le
brinda el servicio. En la tabla 2.2 se muestra el valor de la penalización
por ruta. Sin embargo existen excepciones como las situaciones
imprevistas por ejemplo: huelgas, desvíos de ruta y desastres naturales.

10
TABLA 2.2
PENALIZACIÓN POR RETRASO
Ruta Penalización
Ruta1 4,2926
Ruta2 2,9705
Ruta3 1,84015
Ruta 4 1,24085
Ruta 5 4,68975
En la figura 2.3 se puede apreciar una de las rutas, en donde tiene su
origen A en el depósito (Ciudadela Las Garzas), recorriendo todos los
paraderos una sola vez, y llegando a su destino L, en este caso el
puerto (Puerto Libertador Simón Bolívar).
Figura 2.3: Ruta 2 del departamento de Operaciones

11
2.5 Paraderos
La empresa ha establecido los diferentes paraderos teniendo como
base la ubicación de los clientes en latitud y longitud, como están
distribuidos en la ciudad por zona y parroquia. La Figura 2.4 se observa
los paraderos de la Ruta 4 en la ciudad de Guayaquil en Google Earth.
Figura 2.4: Paraderos de la Ruta 4. Mapa del centro de la ciudad de

Guayaquil en Google Earth
En cada paradero existe un tiempo límite de espera que el vehículo
debe cumplir, llamado ventana de tiempo, es decir que si el vehículo
pasa en un intervalo de 07:00-07:02, el cliente puede estar en el
paradero antes de las 07:00 hasta 07:02, si llega a las 07:03 el vehículo
no estará en dicho paradero. A continuación se muestra en la tabla 2.5

12
los paraderos del departamento de Operaciones con el tiempo estimado
de llegada. Así mismo en la tabla 2.3, tabla 2.4 y tabla 2.5 los paraderos
de los diferentes departamentos establecidas por la compañía.
TABLA 2.3
PARADEROS DEL DEPARTAMENTO DE OPERACIONES
RUTA 1 Tiempo estimado de llegada

TERPEL DE LA GARZOTA 04h21
FERIA DEL JEAN 04h27
DENSO 04h40
ACADEMIA NAVAL GUAYAQUIL 04h43
PARRILLADA EL DORADO 04h47
BLOQUES DE LA ARMADA 04h50
LA ESPAÑOLA 04h56
MI COMISARIATO 05h00
BRIZ SÁNCHEZ 05h04
LA ROTONDA 05h10
COCA COLA 05h15
MARTHA DE ROLDÓS 05h17
COLEGIO AMERICANO 05h21
FINAL VIADUCTO PROSPERINA 05h25
CEIBOS NORTE 05h29
38 Y PORTETE 05H41
CEMENTERIO DEL BATALLÓN 05h48
29 Y LA "Q" 05h52
PERIMETRAL 06h11
PUERTO MARÍTIMO 06h20
BIELA 05h22
TERMINAL DE VIVERES 05h29
HOSPITAL UNIVERSITARIO 05h32
ENTRADA DE LA "8" 05h35
LA FLORIDA 05h38
PROSPERINA 05h42
13
PRIMER PUENTE PERIMETRAL 06h00

SEGUNDO PUENTE PERIMETRAL 06h05
TIA PERIMETRAL 06h08
FERTISA 06h12
COLÓN -ISMAEL PEREZ PAZMIÑO 04h51
COLÓN Y LA 11 AVA 04h56
LA 11 AVA Y CUENCA 04h59
CUENCA Y LA 13 AVA. 05h02
CUENCA Y LA 17 AVA 05h06
CUENCA Y LA 29 AVA. 05h12
LA 29 AVA. Y ARGENTINA 05h15
17 AVA.Y PORTETE 05h20
LEONIDAS PLAZA – VENEZUELA 05h24
LEONIDAS PLAZA Y BOLIVIA 05h27
BOLÍVIA Y LA 11 AVA 05h31
11 AVA Y 4 DE NOVIEMBRE 05h34
29 AVA Y N.AUGUSTO GONZALES 05h39
29 AVA Y LA "G" 05h43
LA 25 Y LA G 05h46
25 Y FRANCISCO SEGURA 05h52
FRANCISCO SEGURA Y LA 11 05h57
LEONIDAS PLAZA Y LA A 06h01
LEONIDAS PLAZA Y PANCHO 06h04
SEGURA
FRANCISCO SEGURA Y ANTEPARA 06h11
UNIVERSIDAD ESTATAL 05h26
TUNGURAHUA Y 9 DE OCTUBRE 05h30
TUNGURAHUA Y CAP. NÁJERA 05h34
TUNGURAHUA Y PORTETE 05h38
TUNGURAHUA Y FCO SEGURA 05h42
FCO SEGURA Y ANTEPARA 05h48
DOMINGO COMÍN (MERCADO 05h54
CARAGUAY)
DOMINGO COMÍN (PRADERA) 05h58
14
ADOLFO H SIMONS (FLORESTA 2) 06h02

DOMINGO COMÍN (GUASMO 06h07
CENTRAL)
RAUL CLEMENTE HUERTA Y 06h12
DOMINGO COMÍN
MOBIL SAMANES 05h15
PRIMAS DE LOS ROSALES 05h33
HIPERMARKET 05h40
REDONDEL DE LAS ORQUIDEAS 05h43
VIA DAULE PECA 05h53
PEPSI COLA 05h00
LA FLORIDA 05h03
AGA 05h08
SUPER ÉXITO 05h17
CALLE 6TA MAPASINGUE OESTE 05h34
COLEGIO ALEMAN 05h39
MC DONALDS 05h48
POLICÍA JUDICIAL PORTETE 05h51
38 Y PORTETE 05h56
CEMENTERIO DEL BATALLÓN 05h59
29 Y LA "Q" 06h03
PERIMETRAL 06h06
15
TABLA 2.4
PARADEROS DEL DEPARTAMENTO FACTURACIÓN
FACTURACIÓN
VIA DAULE (FUERTE HUANCAVILVA) 05h55
VIA DAULE (PROPERINA) 06h00
VIA DAULE (SUPER ÉXITO) 06h08
TUNEL SAN EDUARDO 06h10
PUENTE PATRIA 06h17
GOMEZ RENDÓN Y LA 29 06h21
GOMEZ RENDÓN Y LA 17 06h28
VENEZUELA Y LA 17 06h36
VENEZUELA Y LA 11 06h44
LA 11 Y 4 DE NOVIEMBRE 06h50
NICOLÁS AUGUSTO GONZÁLEZ Y LA 29 06h58
CEMENTERIO DE BATALLÓN 07h05
LA Q Y SALIDA A LA PERIMETRAL 07h14
TÍA DE LA PERIMETRAL 07h24
REGISTRO CIVIL 07h28
EDIFICIO DE LA ADUANA 07h37
FRENTE A LA ESPAÑOLA 04h45
CNT GUAYACANES 04h55
TERPEL GUAYACANES (AV. ISIDRO 05h01
AYORA)
MOBIL DE SAMANES 05h08
GARITA CDLA. EL ALCANCE 05h14
RIOCENTRO NORTE – HYPERMARKET 05h31
BANCO BOLIVARIANO (AV. FCO. 05h39
ORELLANA
SUPERMAXI 05h45
1er. DISTRITO DE POLICÍA JUDICIAL 05h51
(GARZOTA)
TERPEL GARZOTA (CERCA MALL DEL SOL) 05h58
HILTON COLÓN 06h05
CC. SAN MARINO 06h11
CC. POLICENTRO 06h17
16
UNIVERSIDAD ESTATAL 06h26

TUNGURAHUA Y GOMEZ RENDÓN 06h35
GOMEZ RENDÓN Y ANTEPARA 06h45
ANTEPARA Y VICENTE TRUJILLO 06h53
LAS ACACIAS 06h59
MALL DE SUR 07h06
REGISTRO CIVIL 07h23
MACHALA Y MANUEL GALECIO 06h10
COLEGIO GUAYAQUIL 06h21
PANCHO SEGURA Y ANTEPARA 06h31
ANTEPARA Y VICENTE TRUJILLO 06h38
DOMINGO COMÍN (CARAGUAY) 06h46
DOMINGO COMÍN (PRADERA) 06h53
ADOLFO H SIMONS (FLORESTA 2) 07h04
DOMINGO COMIN (GUASMO CENTRAL) 07h11
RAUL CLEMENTE HUERTA Y DOMINGO 07h20
COMÍN
BASE NAVAL SUR 07h32
17
TABLA 2.5
PARADEROS DEL DEPARTAMENTO DE ADMINISTRACIÓN
RUTA 12 - NORTE Tiempo estimado de llegada

LA ROTONDA 07h10
LA ROTONDA DESPUÉS DE DOS 07h13
CUADRAS
BRIS SÁNCHEZ 07h19
RODOLFO BAQUERIZO BCO. 07h23
INTERNACIONAL
R. BAQUERIZO PLAZA QUIL 07h33
EL PORTÓN DE URDESA 07h39
LAS AGUAS 07h44
LAS AGUAS FACSO 07h48
PARADA METROVÍA FEDERACIÓN 07h54
MAC DONAL´S CEIBOS 07h58
CEIBOS NORTE 08h03
RUTA 13 - NORTE Tiempo estimado de llegada
MOBIL DE LOS SAMANES 07h10
PAI SAUCES VI 07h15
EL DORADO 07h22
IGLESIA MORMÓN SAUCES III 07h25
SAUCES II FRENTE A DENSO 07h31
SANTA ISABEL GARZOTA 07h37
MOBIL GARZOTA DISTRITO 07h42
FCO. DE ORALLANA TRES CERRITOS 07h47
FRENTE A MALL DEL SOL 07h51
JOSE DE ANTEPÁRA / FCO. SEGURA Y 08h13
ORIENTE
RUTA 14 - CENTRO SUR Tiempo estimado de llegada
JOSÉ DE ANTEPARA Y QUISQUÍS 07h35
CDLA. BELLAVISTA 07h46
TUNGURAHUA Y LETAMENDI 07h58
TUNGURAHUA Y VENEZUELA 08h02
BOLIVIA Y TUNGURAHUA 08h06
TRUJILLO Y LA 25 DE JULIO 08h11
18
CAE 08h18
RUTA 15 – SUR Tiempo estimado de llegada
20 Y FCO SEGURA 07h15
4 DE NOVIEMBRE Y LA 11 07h25
FCO SEGURA Y GUERRERO VALENZUELA 07h32
PERIMETRAL (POR TÍA) 07h44
PRADERA (REDONDEL) 07h51
PRADERA ( METROVÍA-D.COMÍN) 07h55
7 LAGOS ( D. COMÍN) 07h58
FLORESTA ( D. COMÍN) 08h02
AV. LAS EXCLUSAS Y D. COMÍN 08h07
JUAN PÉNDOLA Y DOMINGO COMÍN 08h11
AV. 25 DE JULIO ( CAE) 08h16
2.6 Vehículos
Los vehículos con los que cuenta la compañía son de diferente
capacidad, es decir una flota heterogénea (busetas y furgonetas) en
general, pero por departamento es homogénea como se expresan en
la tabla 2.6, ya que cada departamento tiene un número diferente de
personas que recoger y además los vehículos deben de cumplir con el
tiempo establecido en cada paradero, con el fin de llegar a tiempo a su
destino que en este caso es a las cercanías al puerto de Guayaquil.

19
TABLA 2.6
CAPACIDAD DE LOS VEHÍCULOS ASIGNADOS EN LAS
DIFERENTES RUTAS
Tipo Vehículo Capacidad Ruta

Buseta 35 1-Operaciones
Bus 45 2-Operaciones
Bus 35 5-Operaciones
Furgoneta 17 7-Facturación
Furgoneta 17 12-Administrativa
Uno de los objetivos que se persigue es reducir el número de vehículos
cumpliendo con todas las rutas y horarios establecidos.
También los vehículos no pueden sobrepasar el número de pasajeros
máximo que deben de trasladar, es decir que no deben de haber
personas paradas en los vehículos, ya que es incómodo y peligroso, así
como tampoco se puede enviar un vehículo de gran capacidad para
realizar un recorrido donde existe una cantidad pequeña de clientes.

20
Actualmente existe un vehículo para cada ruta, es decir que un vehículo
no puede recorrer más de una rutas y además los vehículos deberán
visitar cada paradero no más de una vez.
A cada vehículo se les asigna un conductor y esto depende de la
compañía, ya que se toma en cuenta el horario de trabajo. Esta
restricción de horario-chofer está muy ligada al vehículo.
Los costos fijos y variables dependen por lo general del vehículo, ya
que se requiere de mantenimiento, reparaciones de los mismos en
ciertos períodos y estos de acuerdo al tiempo de utilidad del vehículo
En la figura 2.5 se ilustra los modelos de vehículos que posee la
empresa.
Figura 2.5: Fotos de los vehículos de la empresa

21
2.7 Costos Fijos y Variables
Estos costos son proporcionados por la empresa y representan la parte
a optimizar, ya que nuestro objetivo será disminuir los mismos
cumpliendo con las restricciones del modelo.
2.7.1 Costos Fijos
Los costes fijos o costos fijos son aquellos costos que no son
sensibles a pequeños cambios en los niveles de actividad de una
empresa, sino que permanecen invariables ante esos cambios2.
La empresa considera como costos fijos por ejemplo la
depreciación del vehículo, Seguros, estos son fijos ya que se
realizan todos los meses. Se generan estos valores cada vez que
un vehículo entra a operar, en la tabla 2.7, se muestran los datos
de los costos mensualmente por ruta.
2
Costo Fijo según Wikipedia. http://es.wikipedia.org/wiki/Costo_variable.Revisado el 26 marzo del 2012.
22
TABLA 2.7
COSTO FIJO MENSUAL POR RUTA
Costo Fijo mensual

RUTA 1 296,69
RUTA 2 156,15
RUTA 3 312,30
RUTA 4 171,77
RUTA 5 265,46
RUTA 7 174,89
RUTA 8 218,61
RUTA 9 109,31
RUTA 12 109,31
RUTA 13 109,31
RUTA 14 76,51
RUTA 15 120,24
2.7.2 Costos Variables
Un costo variable o coste variable es aquel que se modifica de
acuerdo a variaciones del volumen de producción (o nivel de
actividad), se trate tanto de bienes como de servicios. Es decir, si
el nivel de actividad decrece, estos costos decrecen, mientras que
si el nivel de actividad aumenta, también lo hace esta clase de
costos3.
3
Costo Variable, Wikipedia, la enciclopedia libre. Disponible en http://es.wikipedia.org/wiki/Coste_fijo.
Revisado 14 marzo del 2012.
23
La empresa genera un costo variable estimado de $0,52*(Total
Kilómetros Recorridos por día de una ruta), estos son creados
por mantenimiento del vehículo, combustible, lubricantes,
líquidos, llantas, etc., según las operaciones efectuadas.
En la tabla 2.8 se enseñan los valores por cada ruta
TABLA 2.8
COSTO VARIABLE ESTIMADO DE CADA RUTA POR DÍA
Costo Variable diario

RUTA 1 $34,33
RUTA 2 $23,77
RUTA 3 $15,64
RUTA 4 $9,89
RUTA 5 $37,52
RUTA 7 $30,83
RUTA 8 $26,29
RUTA 9 $28,50
RUTA 12 $28,91
RUTA 13 $28,66
RUTA 14 $13,62
RUTA 15 $22,68
24
CAPÍTULO 3
3. EL PROBLEMA DE ENRUTAMIENTO VEHICULAR
3.1 Estado el Arte del CVRPTW
En 1987 Solomon publicó 56 problemas, entre ellos instancias con las
cuales ha sido probado el CVRPTW. Entre las decisiones esta el
escogimiento de un vehículo con cierta capacidad, el primer problema
se llamo Vehicle selection o vehicle dispatching problem enunciado por
Egbelu y Tanchoco en 1984, posteriormente aparece Task selection
problem propuesto por Taghaboni y Tanchoco en 1995 además en ese
mismo año Rochat Taillard revoluciones con su concepto de memoria
adaptiva en el algoritmo de búsqueda tabú consiguió un desempeño
notable para la programación vehicular.
En 1996 Akturk y Yilmaz proponen un algoritmo para la secuenciación
de vehículos y tareas basadas en un modelo de programación entera

25
mixta cuyo nombre es MOSA (micro-opportunistic scheduling algorithm)
combina las tareas y los vehículos simultáneamente.
Este problema se define como Time Constrained Vehicle Routing
Problem, su objetivo es la minimización de las ventanas de tiempo. Pero
MOSA solo es aplicable con pocas variables debido a que incrementa el
tamaño de los parámetros además requiere un gran número de
recursos para presentar una solución.
Qiu y Hsu definen al Scheduling o planeación en el transporte como la
asignación de vehículos en una secuencia y en un tiempo determinado,
su objetivo es completar una serie de tareas, reduciendo el uso de
vehículos inclusive el tiempo más corto sujeto a restricciones en 1999.
A finales de la década de los 90 los autores ellos presentan un
esquema de tipo bidireccional para el enrutamiento y la planeación del
transporte combinando dos funciones, la eficiencia de este algoritmo
está restringida por la cantidad de variables
Otra aportación importante es la de Galic y Garic entre el 2006 -2007
con el Coeficiente Heurístico de peso y tiempo ponderado (the
Coeficiente Weighted Distance Time Heuristics) el cual busca
simultáneamente las paradas con una distancia mínima además del
depósito parte un solo vehículo por ruta cuando ya se completa la

26
capacidad del vehículo este regresa al depósito inicial. Cuando todas
las paradas son atendidas el algoritmo se detiene.
Las técnicas de solución disponibles se clasifican en heurísticas, meta-
heurísticas, optimización basadas en heurísticas y algoritmos de
optimización detallada por Cordeau en 2002.
Un ejemplo de una heurística de tipo clúster la dio Christofides en 1978
con su método 2fases, también existen las heurísticas tipo router en
las cuales una ruta es construida incluyendo la posición del los clientes
luego es particionada en pequeñas rutas asignando vehículos, ejemplo
de este tipo es heurística de la partición óptima (Beasley, 1983), y el
algoritmo de eliminación (Gillett y Miller, 1974). Las heurísticas de
inserción como la de Clarke and Wright desarrollada en 1964.
Entre las meta-heurísticas tenemos Tabu search creado por Carlton,
1995, y Potvin uso búsqueda tabú para resolver el CVRPTW en 1996.
Chiang and Russell describió como el método la metaheuristica
simulated annealing puede resolver el problema en 1996. Gambardella
en 1999 usa la técnica de optimización Colonia de hormiga para
solucionar CVRPTW.
Los métodos de aproximación como branch-and-bound la eliminación
de ramas en directrices heurísticas acelera el proceso de decisión y
puede proporcionar soluciones completamente buenas, Fisher [9] y

27
Jaikumar usan un modelo mixto entero en 1981, heurística creada para
CVRPTW.
Branch and Bound descrito por Fisher en 1974, Método dual lagrange
dado por Kallehauge (2001) y Branch and Price descrito por Desrochers
(1972) son métodos de optimización que garantizan una óptima
solución pero pueden requerir un gran tiempo computacional.
Un ejemplo sencillo que explica el Problema de enrutamiento vehicular,
es el que se ilustra en la Figura 3.1.
Figura 3.1: Ejemplo del Problema de Enrutamiento Vehicular

28
3.2 El problema de ruteo capacitado con ventanas de tiempo
(CVRPTW).
El origen del problema de ruteo vehicular se muestra en el año de 1959
con la aparición de Dantzig y Ramser [8] quienes realizaron un estudio
para la planificación de la distribución de combustible a través de
camiones, donde por primera vez manejan la programación matemática.
El problema de enrutamiento vehicular ha sido estudiado
exhaustivamente, Bodin [2] realizó una profunda revisión del VRP y sus
variaciones. Una de sus variaciones más estudiadas es el Problema de
Enrutamiento Vehicular con Ventanas de tiempo, este es un problema
extremadamente práctico usado en industrias como distribución,
recolección de pasajeros, servicio postal, etc.
Un eficiente ruteo con horario puede ayudar a la industria y al gobierno
millones de dólares al año. Solomon [8], realizó una distinción entre una
ventana de tiempo flexible y dura. Una ventana de tiempo es dura si el
vehículo llega muy tarde donde el cliente, este ha tenido que esperar.
Además, a un vehículo no se le permitirá dar el servicio si llega tarde
donde el cliente. En una ventana de tiempo dura, la restricción de
tiempo puede ser violada pero es penalizada con un costo.

29
En 1985, Savelsberg [11] mostró que un VRPTW es NP-hard, ahí su
investigación con el VRPTW implicó el desarrollo de heurísticas que
daban como un buen resultado cercano al óptimo
De manera general los problemas de optimización tratan de modelar la
realidad resolviendo problemas del tipo
Max o Min:
Donde Xi representa la variable decisión, sujetas a restricciones que
influyen en las soluciones factibles. Las restricciones pueden ser
desigualdades o igualdades, son limitaciones de la realidad; en cambio
los parámetros son datos tomados de la realidad.
Para poder modelar un problema debemos primero identificar las
variables, generalmente son de carácter cuantitativo representando
costos o ganancias, después debemos de reconocer las limitaciones del
problemas y por último debemos identificar nuestra función objetivo que
involucra costos o ganancias.
El objetivo es brindar un excelente servicio al cliente reduciendo los
costos, por eso los problemas que involucran ventanas de tiempo y

30
enrutamiento están siendo analizados, ya que la mayoría de las
empresas se involucran con reparto, transporte de materiales, etc.
El VRP es una evolución del problema básico del agente viajero
(Traveling Salesman Problem o TSP), el cual consiste en visitar un
conjunto de clientes una sola vez, partiendo de un depósito y
retornando al mismo, sin restricción de tiempo y capacidad a un mínimo
costo. Este es uno de los problemas más estudiados en el campo de la
optimización.
La Figura 3.2 muestra un ejemplo del TSP.
C5
C6
C4
C3
C2
C10
C7
C1
Deposito C8
C9
Figura 3.2: Ejemplo clásico del Agente Viajero (TSP)

31
Lo que pretende el VRP es descubrir la ruta óptima, asignando el
vehículo para poder cumplir con los requerimientos del cliente y la
minimización de los costos de transporte.
Muchas investigaciones han tratado de amoldar los problemas de la
realidad mediante la programación matemática, esto ha llevado a
variantes del VRP.
A continuación se menciona algunas variantes que se ajustan más a la
realidad en los negocios:
3.2.1 Capacitated Vehicle Routing Problem (CVRP)
Su característica principal es crear rutas asignando una capacidad
C, y esta no debe exceder la capacidad del vehículo que efectúa
dicha ruta . En la Figura 3.3 se expone una muestra del Problema
de Enrutamiento vehicular con capacidad.

32
Figura 3.3: Ejemplo del Problema de Enrutamiento vehicular con

capacidad
3.2.2 Vehicle Routing Problem with Times Windows (VRPTW)
Posee una restricción adicional denominada ventana de tiempo, el
cual es un intervalo de tiempo dentro del cual un cliente debe ser
visitado [8]. Un ejemplo sencillo del Problema de Enrutamiento
vehicular con ventanas de tiempo es el que se presenta a
continuación en la Figura 3.4.

33

ventanas de tiempo
3.2.3 Vehicle Routing Problem with multiple depot (VRPMD)
En este tipo de problemas se encuentran presente más de un
depósito como se ilustra en la Figura 3.5, en donde se le asigna
un número de clientes que deben ser atendidos por los vehículos
establecidos para dicho depósito.

34

múltiples depósitos
3.2.4 Vehicle Routing Problem with multiple depot- Times
Windows Vehicle Routing Problem (CVRPTW – VRPTW)
Esta variante es una de las más importantes, ya que se amolda
mas a la realidad que día a día enfrentan las organizaciones. Este
consiste en utilizar vehículos con cierta capacidad y dentro de un
intervalo de tiempo establecido. En la siguiente Figura 3.6 se
encuentra una ilustración de a problema.

35
Figura 3.6: Ejemplo del Problema de Enrutamiento vehicular

capacitado con ventanas de tiempo
Dado el problema planteado en esta tesis, el cual es la
recolección del personal de una compañía, se puede observar
que el VRPCTW es la variante que más se relaciona a dicho caso,
debido a las restricciones de capacidad, el tiempo establecido en
el que se debe recoger al cliente, y en donde los vehículos salen y
llegan a un solo depósito.
Vale recalcar que existen ventanas de tiempo Suaves (VRPSTW),
en donde se puede incumplir con el intervalo de tiempo
establecido pero esto crea una penalización, por el contrario
existen ventanas de tiempo duras (VRPHTW), las cuales no se

36
permite el incumplimiento de las ventanas horarias, es decir el
vehículo no puede llegar después de la hora máxima estipulada, y
si llega antes de la hora mínima, esto significa que debe esperar
hasta que se cumpla la hora.
Para este caso se tomarán ventanas de tiempo suaves con
penalización por incumplimiento, y dicha penalización es colocada
en la función objetivo.
Existen métodos para poder resolver el problema de enrutamiento
vehicular: Métodos Exactos y Métodos Aproximados.
Los Métodos Exactos , son aplicables para problemas pequeños,
obteniendo resultados óptimos pero en un tiempo exponencial,
dependiendo del tamaño del mismo. Es por esto que se ha
denominado al problema de ruteo vehicular como un problema
NP-difícil por Rinnooy en 1981 [11], debido a su complejidad
computacional. Sin embargo este Método es muy importante para
este estudio ya que el número de clientes no es grande, y lo más
interesante es que da resultados óptimos y no aproximados como
las Heurísticas que muestran una buena solución, pero no la
óptima.
Existen dos puntos que son muy importantes de llevar a cabo, el
tipo de ejecución y que sea este le óptimo. Por lo que las

37
heurísticas no nos garantizan que estos objetivos se vallan a
cumplir, debido a que encuentra buenas soluciones y pueda que
en ciertos casos entregue soluciones erradas a pesar de
ejecutarse rápidamente.
Se han llevado a cabo diferentes formas para resolver métodos
exactos, Kallehauge [4], realiza un estudio de estos métodos
propuestos durante los últimos 30 años. Propone un algoritmo
exacto por medio de ramificación y acotamiento Branch y Bound
[11], suavizando este tipo de problemas.
Otras técnicas estudiadas es la Programación con restricciones y
la programación dinámica, que es un algoritmo que trata de relajar
el problema aligerando su procedimiento Zeimpekis, l. Minis, K.
Mamassis y G.M. Giaglis plantean el problema dinámico el cual
usa información en tiempo real para delimitar las rutas y
programar según el orden de visitas mientras se ejecuta la
distribución [16].
38
3.3 Definición formal del problema de ruteo capacitado con ventanas
de tiempo (CVRPTW)
A continuación se describe los elementos que intervienen en el
CVRPTW para luego formularlo matemáticamente:
1) Un conjunto de vehículos K con capacidad limitada Q, como se
tiene vehículos con capacidades diferentes .
2) Los vehículos salen de un depósito, recorren los paraderos dejan
a los pasajeros y retornan al depósito.
3) Existe una hora de salida y de llegada al depósito.
4) Cada parada tiene un intervalo de tiempo [a 0 ,b0], llamado
ventana de tiempo.
5) El tiempo de espera de cada parada es de dos minutos
6) En cada parada se suben al vehículos los pasajeros sin
sobrepasar la capacidad Q del vehículo k
7) Cada vehículo visita una sola vez cada parada
8) El vehículo sale del depósito, atiende un grupo de paradas
dispersas geográficamente y regresa al depósito.
Formulación matemática del problema:
Sea G = (V, A) un grafo dirigido, donde V= {vo,v1,…,vn, vn+1} es el
conjunto de vértices y A= {(vi, vj);vi,vj Є V, i≠j } se denomina conjunto

39
de arcos. Los depósitos son representados por v0 y vn+1 y cada vi
representa una parada i y tiene asociada una demanda de pasajeros.
Las paradas de visita sin considerar el depósito son expresadas por el
conjunto Vc= {v1,… ,vn}. Las rutas comienzan en v0 y terminan en vn+1.
Definimos a cij como el costo de viajar de la parada vi a la vj. Tanto las
paradas como el depósito tienen asociada una ventana horaria de
servicio [evi, lvi], la demanda y el tiempo del servicio del depósito es igual
a cero.
Se expresa al conjunto de nodos adyacentes e incidentes como ∆+(vi) y
∆-(vi) respectivamente al nodo vi V; es decir:
3.3.1 Parámetros e índices
Los parámetros que se utilizan son:
K flota de vehículos
Q capacidad del vehículo
cij costos relacionado al arcos (vi, vj) ϵ A
qi demanda de la parada i
fk costos fijos
pvi penalización por atraso por atender la parada vi
svi tiempo de servicio de la parada i
[evi, lvi ] ventana horaria de la parada i

40
3.3.2 Variables
Para este modelo se tiene una variable binaria y dos variables
reales, las variables relacionadas con el tiempo no pueden ser
negativas.
3.3.2.1 Variable de decisión binaria
Solo puede tomar dos valores 1 y 0
3.3.2.2 Variable de decisión real
Donde representa el tiempo de servicio, es decir
el tiempo en el que empieza a ser servido la parada
El representa el tiempo de atraso en atender la
próxima parada
41
3.3.3 Función objetivo
El objetivo del CVRPTW es construir un conjunto de rutas con un
costo mínimo que visiten todas las paradas en el horario
establecido respetando la capacidad de los vehículos.
Como se puede ver la ecuación (3.1) suma los costos asociados
con las visitas a las paradas , los costos fijos por el uso
cada uno de los vehículos , además de la suma de las
penalizaciones dadas por infringir el horario de visitas de los
paraderos.
3.3.4 Restricciones
 Todas las paradas deben ser visitadas una sola vez y
por un único vehículo , ecuación 3.2:

42
 Todos los vehículos parten del depósito al iniciar las rutas,
ecuación 3.3:
 La suma de las personas recogidas en los paraderos no puede
exceder la capacidad del vehículo , ecuación 3.4:
 Todas las paradas son visitadas una sola vez y solo por único
vehículo, es decir la parada es atendida por el vehículo ,
entonces las paradas sucesoras y antecesoras deben ser
servidas por el mismo vehículo, ecuación 3.5:
 El tiempo inicio del servicio de debe ser mayor o igual a la
cota inferior de la ventana de tiempo del paradero , pero
también se permiten atrasos, como lo expresa la ecuación 3.6:

43
 La siguiente ecuación plantea una continuidad en el tiempo,
además elimina los subtours, esto quiere decir si un vehículos
viaja de hasta lo debe hacer en el tiempo ,
ecuación 3.7:
Cuando , la restricción se vuelve redundante, caso
contrario , la ecuación 3.7, se reduce a
3.4 Complejidad computacional
El problema del CVRPTW es NP- completo esto ha sido mostrado por
Lenstra & Rinnooy Kan en 1981 [11], ellos concluyeron que todos los
problemas de enrutamiento vehicular y problemas de horario son de
clase NP-completo. Además Garey and Johnson en 1979 [6]
demostraron que un circuito hamiltoniano es un NP- completo; esto
quiere decir que son problemas fáciles de declarar pero difíciles de
solucionar. Estos algoritmos trabajan utilizando un tiempo exponencial
con respecto al tamaño de clientes, pero para entradas menores estos
algoritmos dan buenos resultados.

44
Un algoritmo se puede solucionar en tiempo polinómico O(nk), siendo n
el tamaño de la entrada y k una constante independiente. Se puede
diferenciar dos tipos de problemas: los problemas de decisión y los
problemas de optimización.
Los problemas de decisión involucran generalmente variables binarias,
es decir, solo entre dos valores cero y uno; los problemas de
optimización involucran minimización de costos o maximización de
utilidades.
Los problemas de decisión P son resueltos en tiempos polinómicos, en
cambio los problemas de decisión de clase NP son problemas resueltos
en un tiempo polinómico indeterminado, solo pueden ser resueltos
utilizando una máquina de Turing capaz de ejecutar en paralelo un
número ilimitado de ejecuciones.
Entonces decimos que un problema X es NP-completo, si X esta en NP,
y si encontramos que un problema NP- completo puede ejecutarse en
un tiempo polinómico, entonces todos los problema tipo NP podrían
resolverse en tiempo polinómico. No se puede afirmar que P=NP.
Identificamos a un problema NP-duro si cualquier problema tipo NP
puede reducirse en un tiempo polinomial, debido a la complejidad de los
problemas cualquier método de solución exacto será complejo de
resolver en un tiempo aceptable y no sujeto a los cambios de la realidad.

45
CAPÍTULO 4
4. ANÁLISIS COMPUTACIONAL (APLICACIÓN DEL
MODELO MATEMÁTICO CVRPTW)
4.1 Herramientas tecnológicas
En la actualidad la tecnología se ha vuelto una necesidad, que
permite al ser humano sentirse ayudado y de esta manera poder
cumplir con las metas que se ha propuesto. Para esto se ha
descubierto ciertas herramientas que en este caso son de gran
beneficio para el área del transporte. Lo cual facilita el trabajo
permitiendo el uso adecuado de los recursos en una organización.

46
4.1.1. Google Maps
Google Maps es el nombre de un servicio de Google. Es un
servidor de aplicaciones de mapas en la Web.
Ofrece imágenes de mapas desplazables, así como fotos
satelitales del mundo e incluso la ruta entre diferentes
ubicaciones o imágenes a pie en una calle4.
Esta herramienta sirve de ayuda para la ilustración de las rutas
y todo lo que esto implica (Clientes, paraderos, calles, etc.), lo
cual es aprovechado en el área de la logística. En el Apéndice
A se observan el recorrido de algunas de las rutas que se
realiza en los diferentes departamentos.
No solo sirve de ilustración, sino que por medio de Google
Maps podemos ver el sentido de la calle de la ciudad, cómo
llegar en auto, el tiempo y kilometros recorridos.
4
Definición de Google Maps según Wikipedia. http://es.wikipedia.org/wiki/Google_Maps. Revisado el 15 de
Abril del 2012
47
4.1.2 Google Earth
Google Earth es un programa informático similar a un Sistema
de Información Geográfica (SIG), creado por la empresa
Keyhole Inc., que permite visualizar imágenes en 3D del
planeta, combinando imágenes de satélite, mapas y el motor
de búsqueda de Google que permite ver imágenes a escala de
un lugar específico del planeta5.
Gracias a esta herramienta se puede obtener las coordenadas
geograficas del deposito y de los diferentes deparamentos
expresadas en UTM (Sistema de Coordenadas Universal
Transversal de Mercator). A diferencia del sistema de
coordenadas geográficas, expresadas en longitud y latitud, las
magnitudes en el sistema UTM se expresan en metros
únicamente al nivel del mar que es la base de la proyección del
elipsoide de referencia6.
5
Definición de Google Earth según Wikipedia. . http://es.wikipedia.org/wiki/Google_Earth. Revisado el 4
de Mayo del 2012
6
Definición de UTM según Wikipedia.
http://es.wikipedia.org/wiki/Sistema_de_Coordenadas_Universal_Transversal_de_Mercator. Revisado el 26 de
Marzo del 2012
48
4.1.2.1 Ubicación geográfica de los nodos
En las siguientes tablas 4.1 y 4.2 se presentan las
coordenadas geográficas enunciadas en
UTM,dadas por google earth del depósito destino y
de los paraderos correspondiente al departamento
de operaciones, ver anexo F.
TABLA 4.1
COORDENADAS GEOGRÁFICAS EN UTM DEL
DEPÓSITO Y DESTINO
Posición X Posición Y
Depósito (S) 622473.05 9760412.23
Destino (R) 621580.32 9748384.18
49
TABLA 4.2
COORDENADAS GEOGRÁFICAS DE LOS
PARADEROS DEL DEPARTAMENTO DE
OPERACIONES
RUTA 1
Paraderos Posición X Posición Y
v1 623103.04 9762199.13
v2 624098.15 9763012.40
v3 623968.03 9763769.79
v4 623638.89 9764173.77
v5 623796.25 9764772.94
v6 623153.03 9764910.35
v7 622646.40 9763244.64
v8 621981.42 9763181.98
v9 622319.54 9763736.85
v10 621421.90 9763428.75
v11 620474.17 9762916.97
v12 620015.42 9763109.48
v13 619086.66 9763421.92
v14 617348.86 9763434.25
v15 617171.81 9762252.59
v16 618646.68 9757068.55
v17 618097.62 9754757.03
v18 617467.54 9753835.29
v19 622740.34 9752257.61
RUTA 2
p1 617783.75 9770572.75
p2 616988.53 9768234.03
p3 617000.68 9767032.63
p4 616900.17 9765703.15
p5 616809.49 9764848.47
p6 617224.47 9762695.40
p7 617927.38 9753022.94
p8 620780.16 9752428.06
p9 621689.63 9752474.39
p10 621843.17 9751154.79
50
RUTA 3
m1 622167.67 9757557.13
m2 621429.00 9757718.71
m3 621274.10 9757137.59
m4 621115.81 9757174.61
m5 620758.98 9757263.70
m6 619641.62 9757558.42
m7 619490.47 9756979.79
m8 620492.81 9756604.13
m9 621573.93 9756223.06
m10 621488.11 9755946.90
m11 621041.15 9756180.44
m12 620958.27 9755699.84
m13 619257.57 9756067.40
m14 618213.48 9754905.45
m15 618522.29 9754567.28
m16 619352.33 9755662.55
m17 620857.17 9754744.92
m18 621336.14 9754684.10
m19 621391.38 9755163.55
m20 622340.33 9754773.55
RUTA 4
w1 622738.78 9758797.01
w2 622748.64 9758220.04
w3 622385.65 9757081.63
w4 622097.94 9756169.14
w5 621739.57 9755032.23
w6 622338.68 9754775.03
w7 623421.01 9753742.36
w8 623290.03 9752563.72
w9 623410.35 9751179.31
w10 624312.36 9751018.48
w11 623463.66 9750324.82
RUTA 5
x1 621690.67 9764763.96
x2 621708.10 9765694.76
x3 622297.21 9766708.53
x4 621422.05 9763429.93
x5 618790.39 9764857.55
x6 618870.65 9765334.47
x7 618202.95 9768942.89
x8 616805.58 9764846.16
51
x9 619050.67 9761485.41
x10 618149.95 9761440.80
x11 617337.04 9760488.77
x12 617807.65 9759791.78
x13 618029.53 9757460.62
x14 618644.37 9757067.23
x15 618091.95 9754755.15
x16 617471.71 9753838.37
x17 617668.12 9753093.72
4.1.2.2 Aplicación del método de barrido
Según Ballou [1] el método “de barrido”, es una
técnica fácil ya que se puede realizar
manualmente como programar obtenido buenos
resultados produciendo una tasa de error promedio
del 10%.
Tiene dos fases: primero, las paradas se asignan a
los vehículos y después se determina la
continuación de las paradas dentro de las rutas.
Ballou describe de la siguiente forma:
1. Se localiza las paradas y el depósito dentro de un
mapa o cuadrícula
2. Se traza una línea recta desde el depósito en
cualquier dirección, hasta que se intercepte una
parada. Hacer la pregunta ¿Excede la capacidad
del vehículo el volumen acumulado? Si la

52
respuesta es sí, se la excluye y se define la ruta.
Continuando el barrido empezando con esa
parada
3. Dentro de cada ruta se efectúa una sucesión de
las paradas para minimizar las distancias. Esto
puede lograrse aplicando cualquier método de
optimización.
Este método da buenos resultados cuándo: 1) cada
parada representa una pequeña fracción de la
capacidad; 2) los vehículos con el mismo volumen;3)
no hay restricciones de tiempo. En el apéndice I se
muestran los resultados dados por el programa
MATLAB para el departamento de Facturación.
En la figura 4.1, se muestra esta aplicación, es decir
las diferentes paradas, y la linea trasada colorfucsia
que gira hasta interceptar una parada, y asi
sucesivamente hasta completar la capacidad del
vehiculo.En el apendice G se encuentra su codigo en
matlab.
53
Figura 4.1: Aplicación del método de barrido a las
paradas establecidas.
En la tabla 4.3 se presentan las rutas que se formaron
aplicando el método de barrido en el departamento de
operaciones, además la capacidad acumulada, que va
sumando las personas que se encuentran en los nodos
barridos hasta completar la capacidad del vehículo.
Luego empieza a sumar los siguientes nodos
seleccionados, hasta completar otra ruta, acumulando
la capacidad de otro vehículo.

54
TABLA 4.3
MÉTODO DE BARRIDO DE LOS PARADEROS DEL
DEPARTAMENTO DE OPERACIONES
Ruta 1 Nomenclatura Capacidad Capacidad-

Acumulada
FERIA DEL JEAN (. ROLDÓS AGUILERA) v2 2 2
DENSO v3 3 5
TERPEL DE LA GARZOTA v1 4 9
ACADEMIA NAVAL GUAYAQUIL v4 3 12
PARRILLADA EL DORADO -SAUCES 3 v5 2 14
BLOQUES DE LA ARMADA-SAUCES 4 v6 1 15
LA ESPAÑOLA -AV ISIDRO AYORA v7 2 17
MOBIL SAMANES x3 3 20
BRIZ SANCHEZ(AV. BENJAMIN v9 2 22
CARRION )
PRIMAS DE LOS ROSALES x2 4 26
PERIMETRAL v8 2 28
HYPERMARKET x1 2 30
LA ROTONDA (AV. BENJAMIN v10 2 32
CARRION)
BIELA p1 3 35

Acumulada
AGA x6 1 1
HOSPITAL UNIVERSITARIO p2 2 3
PEPSI COLA x5 2 5
COCA COLA v11 3 8
TERMINAL DE VIVERES p3 3 11
VIA DAULE PECA x4 3 14
COLEGIO AMERICANO v13 1 15
ENTRADA DE LA "8" p4 2 17
55
MARTHA DE ROLDOS v12 2 19

LA FLORIDA x7 3 22
PROSPERINA p5 3 25
FINAL VIADUCTO PROSPERINA v14 2 27
CEIBOS NORTE v15 1

28
SUPEREXITO x8 3 31
CALLE 6TA MAPASINGUE OESTE x9 4 35
Acumulada
COLEGIO ALEMAN x10 3 3
MC DONALDS x11 3 6
POLICIA JUDICIAL PORTETE x12 2 8
38 Y PORTETE v16 2 10
CUENCA Y LA 29 AVA. m6 3 13
LA 29 AVA. Y ARGENTINA m7 2 15
PERIMETRAL x13 3 18
CEMENTERIO DEL BATALLON- v17 1 19
SUBURVIO
29 Y LA "Q" v18 1 20
29 AVA Y N.AUGUSTO GONZALES m13 1 21
LA 25 Y LA G m14 2 23
25 Y FRANCISCO SEGURA m15 3 26
PRIMER PUENTE PERIMETRAL p6 4 30
CUENCA Y LA 17 AVA m5 2 32
17 AVA.Y PORTETE m8 2 34
Acumulada
CUENCA Y LA 13 AVA. m4 4 4
COLON Y LA 11 AVA m2 2 6
LA 11 AVA Y CUENCA m3 4 10
BOLIVIA Y LA 11 AVA m11 1 11
11 AVA Y 4 DE NOVIEMBRE m12 3 14
FRANCISCO SEGURA Y LA 11 m16 2 16
LEONIDAS PLAZA Y BOLIVIA m10 3 19
LEONIDAS PLAZA – VENEZUELA m9 3 22
56
SEGUNDO PUENTE PERIMETRAL p7 2 24

LEONIDAS PLAZA Y PANCHO SEGURA m18 2 26
LEONIDAS PLAZA Y LA A m17 1 27
TUNGURAHUA Y FCO SEGURA w5 3 30
COLON -ISMAEL PEREZ PAZMIÑO m1 1 31
TIA PERIMETRAL p8 3 34
Acumulada
TUNGURAHUA Y PORTETE w4 6 6
FERTISA p9 1 7
TUNGURAHUA Y CAP NAJERA w3 3 10
FCO SEGURA Y ANTEPARA w6 4 14
PERIMETRAL(AV 25 DE JULIO) v19 2 16
RAUL CLEMENTE HUERTA Y DOMINGO w11 3 19
COMIN
DOMINGO COMIN (GUASMO w10 2 21
CENTRAL)
DOMINGO COMIN (PRADERA) w8 5 26
TUNGURAHUA Y 9 DE OCTUBRE w2 2 28
DOMINGO COMIN (MERCADO w7 3 31
CARAGUAY)
UNIVERSIDAD ESTATAL w1 2 33
ADOLFO H SIMONS (FLORESTA 2) w9 2 35
57
4.1.2.3 Cálculo de distancias y tiempos
Para el cálculo de las distancias se procedió
a utilizar la métrica de Manhathan7, esta saca la
distancia menor entre dos puntos en ciudad
paratiendo de que las manzanas de la misma son
rectángulos. Es decir con los puntos A(xm, ym) y
B(xn, yn), la distancia d(A,B) entre dichos puntos
esta dada por la ecuaciòn:
Figura 4.2: Cálculo de distancias por formula de

Manhattan
7
Definición de Métrica de Manhathan según Wikipedia.
http://es.wikipedia.org/wiki/Geometr%C3%ADa_taxicab
Revisado el 5 de Abril del 2012
58
En el apéndice G se muestran los resultados calculados por
la métrica de Manhattan de las distancias y los tiempos de la
ruta 1 del departamento de Operaciones.
4.1.3 Gams
Para llevar a efecto el diseño de las rutas, se recurrió a la
ayuda de un el software informático llamado GAMS [14]
(General Algebraic Modeling System) es un lenguaje de
programación que permite el modelado, análisis y resolución
de diversos problemas de optimización. Una de las
características más valiosas que posee esta herramienta, es
la capacidad para resolver problemas de gran dimensión
(miles de variables y restricciones), por lo que no habrá
problemas con el número de paradas establecidas en el
modelo.
El usuario de GAMS debe ser cuidadoso con las reglas
“gramaticales”. El incumplimiento de una sola de ellas puede
provocar muchos errores de compilación. En la siguiente
figura 4.3, se muestra el resultado óptimo de una
programación realizada en este software matemático. Entre la
bibliografía de este lenguaje de programación cabe destacar

59
el manual de GAMS [17], cuyo segundo capítulo ofrece un
resumen con las características principales para empezar a
programar en este lenguaje, y el artículo[16], que proporciona
un enfoque ingenieril de GAMS.
Figura 4.3: Resultados obtenidos en Gams
4.2 Modelo Matemático para el diseño de rutas óptimas
Para la elaboración del modelo matemático se debe tomar en
cuenta las siguientes observaciones:
 Se define el conjunto de índices.
 Se introducen los vectores de datos.

60
 Se declaran las variables de decisión.
 Se crean las restricciones del problema.
La utilización del modelo VRPCTW en la recolección de
pasajeros tiene como objetivo:
 Especificar una ruta óptima de recolección de pasajeros
de tal forma que sea un ahorro de tiempo. Reduciendo
costos mediante la reducción de kilómetros recorridos.
 Mejorar el tiempo de recorrido de la ruta, para así
realizar mayor cantidad de vueltas a diversos clientes.
 Aprovechar los recursos actuales.
4.2.1 Conjunto de Índices
La palabra Set o Sets se utiliza para declarar los índices
para describir a los componentes de un vector en GAMS.
En la tabla 4.4 tenemos el conjunto de índices:

61
TABLA 4.4
CONJUNTO DE ÍNDICES
Índice Descripción
I Conjunto de nodos que recorre

los orígenes
J Conjunto de nodos que recorre

los destinos
K Conjunto de Vehículos
paraderos(i) Conjunto de paradas sin origen

y destino
arcos(i,j,k) Conjunto de arcos incluyendo
los de origen y destino
arcoconexion(i,j,k) Conjunto de arcos excepto los

de origen y destino
El depósito de inicio es representado por s y el depósito
final es representado por r.
4.2.2 Vectores de Datos
Los vectores se expresan como parámetros, y el comando
que se usa en Gams es Parameter, el cual sirve para fijar
los datos de entrada, por lo que se establecen nueve
vectores de entrada como se muestra en la siguiente tabla
4.5.
62
TABLA 4.5
CONJUNTO DE VECTORES DE DATOS
Parámetro Descripción
Costo en recorrer un paradero a

costos(i,j,k)
otro con un determinado bus
Costo fijo por vehículo
Costo_fijo(k)
Número de personas ubicadas en

Capacidad(i)
los paraderos
Multa por incumplimiento del

Penalización(paraderos)
horario de visita a los paraderos
Capacidad de los vehículos (flota
Capacidad_Veh(k)
heterogénea)
Tiempo de servicio de cada
tiempo_serv(paraderos) cliente.
Tiempo que transcurre de un

tiempos(i,j,k) paradero a otro con un
determinado vehículo.
Tiempo de inicio de la ventana
liminf(paraderos) horaria de cada cliente.
63
4.2.3 Variables
Las variables de decisión que se declaran en la siguiente
tabla 4.6 son aquellas en donde se muestran los
resultados óptimos que arroja el modelo.
TABLA 4.6
CONJUNTO DE VARIABLES DE DECISIÓN
Variable Descripción Unidades
x(i,j,k) Variable Binaria
Z Costo total
Tiempo de atraso al atender la

r(i) Minutos
siguiente parada vi
Tiempo en que se recoge a los

t(i) Minutos
clientes en las paradas.
La variable x(i,j,k) se encuentra en la función objetivo, lo cual
representa (parada inicial, parada final, vehículo asignado),

64
esto significa que existe un camino entre la parada i,j utilizando
el vehículo k.
En la variable Z se encontrará el valor óptimo de la ruta,
representado como el costo total, para lo cual debe ser menor
que el de la actualidad.
La variable r(i) es el tiempo de retraso en atender la siguiente
parada i, expresada en minutos, esta variable sirve para
determinar el valor de penalización.
También se necesita conocer el tiempo exacto en el que los
vehículos deben estar en los diferentes paraderos, para que de
esta forma se evite llegar tarde y por ende se genere una
penalización que conlleve al incremento de los costos, y esta
variable está representada en Gams como t(i) en minutos.
4.2.4 Restricciones
Para explicar las restricciones en Gams se utiliza el
término Equation o Equations, las mismas que pueden
ser de igualdad o desigualdad según sea el caso.

65
Una de las restricciones es por ejemplo la capacidad
del vehículo presentada en la tabla 6, además de la
limitante del tiempo de servicio es decir solo 2 minutos
por parada, la restricción de ventanas de tiempo, etc.
Dentro de estas restricciones se declara la función
objetivo mencionado a continuación.
4.2.4.1 Función objetivo
Para el diseño de rutas óptimas, es
importante que los costos de trasporte
sean mínimos, por lo tanto este es el
objetivo principal.
La suma de los costos de viaje de cada
arco que forma parte de la solución, los
costos fijos más los costos de

66
penalización por atraso en la atención a
los clientes, debe ser la mínima posible.
4.2.4.2 Visitas a las paradas
Los vehículos deben visitar una sola vez a
todas las paradas establecidas por la
empresa.
4.2.4.3 Salida desde un mismo depósito
Al empezar el recorrido, todos los
vehículos parten de un único depósito “s”
a una de las diferentes paradas.

67
4.2.4.4 Capacidad del vehículo
Se le asigna a cada parada un único
vehículo, es decir que el mismo vehículo
que entra a dicho nodo, es el mismo que
debe salir
4.2.4.5 Selección de un vehículo por parada
El total de personas recogidas en los
diferentes paraderos, no debe exceder la
capacidad del vehículo que esta en uso.
4.2.4.6 Cumplimiento del horario
El vehículo debe respetar el intervalo de
tiempo establecido, por lo que el vehículo
debe llegar como mínimo igual al tiempo
de inicio de la ventana horaria, para que

68
no se genere una multa por atraso al
paradero.
4.2.4.7 Eliminación de subtours
La siguiente ecuación plantea una
continuidad en el tiempo, además elimina
los subtours, esto quiere decir que el
tiempo de la siguiente parada, es decir
debe ser un tiempo mayor o igual a
, esto
ocurre si el vehículos viaja de hasta
lo donde representa el tiempo en que
empieza el servicio en dicha parada
Si = 0 (Si el vehículos no pasa por el
arco que va desde la parada hasta )

69
Si = 1 (Si el vehículos pasa por el
arco que va desde la parada hasta )
4.3 Resultados Obtenidos
Al aplicar el modelo matemático con el software informático
Gams, este dará como resultado las variables de decisión (Costo
Total, Variable binaria, Tiempo en que pasa el bus por cada
parada, Tiempo de atraso).
En el apéndice c, se puede observar los resultados de las
Variables de decisión que adoptó el Software Matemático Gams.
En las siguiente tabla 4.7, se puede ver los resultados obtenidos
en el departamento de Operaciones, como en la tabla 4.8 los
resultados del departamento de Facturación, y en la tabla 4.9 los
que pertenecen al departamento de Administración.

70
TABLA 4.7
RESULTADOS OBTENIDOS DE LAS RUTAS DEL
RUTAS PARADEROS ATRASO EN TIEMPO DE

MINUTOS LLEGADA
RUTA 1 s 0 04h30
v8 0 04h36
v10 0 04h45
x1 0 04h49
x2 0 04h51
x3 0 04h55
p1 0 05h00
v6 0 05h19
v4 0 05h43
v5 0 05h47
v3 0 05h51
v2 0 05h55
v9 0 06h03
v7 0 06h07
v1 0 06h12
r 0 06h45
RUTA 2 s 0 04h55
x8 0 05H04
x9 0 05h08
v15 0 05h14
p5 5 05h17
v14 0 05h21
x7 0 05h27
p4 0 05h31
p3 0 05h36
p2 0 05h40
x6 0 05h46
71
x5 0 05h57
x4 0 06h00
v13 0 06h05
v12 0 06h09
v11 0 06h12
r 0 06h46
RUTA 3 s 0 04h46
x10 0 04h58
m6 0 05h06
x11 0 05h15
x12 0 05h22
m7 0 05h28
v16 0 05h32
x13 0 05h45
v18 0 05h50
p6 0 05h55
v17 0 06h01
m14 0 06h04
m15 0 06h10
m13 0 06h13
m5 0 06h20
m8 0 06h24
r 0 06h45
RUTA 4 S 0 06h10
m1 0 06h13
m2 0 06h15
m3 0 06h17
m4 0 06h19
m11 0 06h22
m9 0 06h24
m10 0 06h26
m12 0 06h28
m18 0 06h30
w5 0 06h32
m17 0 06h34
72
m16 0 06h36
p7 0 06h39
p8 0 06h41
r 0 06h45
RUTA 5 s 0 06h08
w1 0 06h11
w2 0 06h13
w3 0 06h16
w4 0 06h19
w6 0 06h22
w7 0 06h25
w8 0 06h28
v19 0 06h30
w9 0 06h33
w11 0 06h35
w10 0 06h38
p9 0 06h41
r 0 06h45
73
TABLA 4.8
DEPARTAMENTO FACTURACIÓN
RUTAS PARADEROS ATRASO TIEMPO DE

LLEGADA
RUTA 7 o9 0 06H01
o10 0 06H03
o8 0 06H07
o1 0 06H10
o2 0 06H14
o7 0 06H19
o6 0 06H23
o5 0 06H27
o3 0 06H30
o4 0 06H34
i1 0 06H43
i2 0 06H52
i3 0 06H59
i4 0 07H03
i5 0 07H12
i6 0 07H14
r 0 07h40
RUTA 8 o12 0 06h40
o13 0 06h41
u1 0 06h48
u2 0 06h55
o17 0 07h01
u5 0 07h08
u6 0 07h13
i15 0 07h17
u8 0 07h21
u7 0 07h27
74
u9 0 07h32
r 0 07h40
RUTA 9 o11 0 06h10
o16 0 06h26
o15 0 06h30
u3 0 06h36
i10 0 06h44
i8 0 06h47
i7 0 06h51
i9 0 06h55
i11 0 07h01
i12 0 07h08
i13 0 07h14
i14 0 07h23
i16 0 07h29
u10 0 07h38
r 0 07h40
75
TABLA 4.9
DEPARTAMENTO DE ADMINISTRACIÓN
RUTAS PARADEROS ATRASO TIEMPO DE

LLEGADA
RUTA 12 y3 0 06h53
y2 0 06h57
y1 0 07h00
y6 0 07h06
y7 0 07h11
y8 0 07h14
y11 0 07h23
y9 0 07h38
y5 0 07h43
k2 0 08h10
R 0 08h20
RUTA 13 t9 0 07h03
t7 0 07h06
t5 0 07h13
t3 0 07h17
t4 0 07h20
t6 0 07h24
t2 0 07h32
t1 0 07h38
y4 0 07h44
t8 0 07h50
R 0 08h20
RUTA 14 k1 0 07h38
k6 0 07h48
q5 0 07h57
q6 0 08h00
q7 0 08h03
76
q8 0 08h07
q9 0 08h10
q10 0 08h15
R 0 08h20
RUTA 15 k3 0 06h30
k4 0 06h33
k5 0 06h36
q2 18.12 06h40
q1 0 06h45
q3 0 06h53
t10 0 06h58
k7 0 07h08
q4 0 07h36
R 0 08h20
4.4. Post optimización
Algunas de las rutas presentan cruces entre las aristas, se utilizó el
algoritmo 2-opt para solucionar este inconveniente. Para cada
combinación de clientes asignada a un vehículo, el 2-opt cambia y
cruza las aristas para tratar de mejorar la calidad de la solución
considerando movimientos que no violen ninguna restricción,
tratando de disminuir la función objetivo. El 2-opt es un operador
denominado intra-ruta el cual reversa una sección de la ruta
delineadas por 2 arcos y remplazada con 2 arcos que reforman la
ruta. A continuación el algoritmo:

77
1.- Solución inicial dada por CVRPTW en gams
2.- Para cada combinación de clientes se busca una solución mejor,
mediante los cuatro operadores heurísticos 2-opt, traslado, cambio,
cruces sin violar las restricciones
3.- Si no se puede mejorar la solución pasar al paso 5
4.- Ir al paso 2
5.-Poner la solución anterior
En la figura 4.4 se muestra un cruce en una de las rutas y luego se
muestra su resultado aplicando el algoritmo.
Figura 4.4 Ruta pos optimizada

78
TABLA 4.10
RESULTADOS OBTENIDOS A LAS RUTAS QUE PRESENTAN
CRUCES
RUTA RESULTADO POST OPTIMIZACIÓN
2-Operaciones 1-4-9-7-3-6-10-8-16-2- 1-4-9-7-3-6-16-2-5-8-
5-12-11-13-14-17 10-12-11-13-14-17
3-Operaciones 1-16-5-2-3-4-14-15-6- 1-5-16-2-3-4-14-15-6-
10-12-11-8-9-7-13-17 10-12-11-8-9-7-13-17
5-Operaciones 1-11-9-3-13-4-10-8-5-6- 1-11-9-3-13-4-10-8-5-
12-7-2-14 12-7-6-2-14
15-Administración 1-3-4-5-7-8-6-2-10-9-11 1-3-4-5-7-8-6-2-10-9-11
4.5 VRPCTW versus ANÁLISIS ACTUAL
Aplicando el método de barrido se asigno los vehículos a las paradas
y con el cálculo de las distancias mediante la métrica de Mahathan
finalmente se procedió a programar en GAMS las diferentes rutas
para luego obtener una post optimización las cuales presentaban
cruces, obteniendo una reducción en los costos por lo que se
puede llegar a la siguiente comparación mostrada en la tabla 4.11

79
TABLA 4.11
COMPARACIÓN DE LOS COSTOS ACTUALES ANTERIORES
Departamento Nuevo Actual
Operaciones 126,70 158,52

Facturación 74,21 144,27
Administración 75,73 117,3
Total 281,57 420,09
Figura 4.5 Comparación de costos por departamento
En el Figura 4.5 se puede comparar las dos situaciones, por lo que
se observa que en la propuesta existe un ahorro del 33 % para la
empresa mensualmente. El costo actual mensual de todas las rutas

80
es de $ 420,09 con la nueva propuesta el costo sería de $ 281,57,
dando como resultado un ahorro de $138,52, esto representa un
33% de ahorro.
4.6 Comparación con otras heurísticas
Se comparó el método utilizado los datos del problema de
Solomon RC202 con 25 clientes. Primero se procedió a utilizar el
método del barrido dando como resultado tres rutas a las cuales se
les aplicó el modelo matemático como no presentaron cruces entre
aristas no se uso la tercera fase la post optimización. En la página
VRP WEB se presentan los resultados. A continuación se presentan
las resoluciones obtenidas:
Figura 4.6 Resultados de la página VRP Web

81
4.7 Resultados obtenidos con el modelo

82
CAPÍTULO 5
5. Conclusiones y Recomendaciones
5.1 Conclusiones
 Este trabajo propone una mejor alternativa para las rutas
actuales a una empresa que ofrece servicios de transporte de
personas mediante el VRPCTW, para ello se uso la
programación matemática adaptándolo a la realidad. El
objetivo principal del programa era encontrar una solución
óptima con los recursos presentes. Para lo cual se encontraron
nuevas opciones de rutas que cumplan con las restricciones,
obteniendo así una reducción en los costos de manera
significativa.
 La programación matemática presenta la mejor solución, aun
siendo un poco inflexible a problemas con muchas variables,

83
pero a problemas medianos como éste, genera muy buenos
resultados. También existen otras alternativas como las
heurísticas y metaheurísticas, con éstas solo se obtiene una
buena solución sin llegar al óptimo; son un poco mas elásticos
con problemas mayores.
 Este algoritmo puede ser implementado en otro tipo de
problemas como distribución de productos con capacidad
vehicular, recolección de personal, mensajería. También se
puede analizar otras opciones de VRP, las cuales son muy
utilizadas en todos los campos.
 Se aplicó el algoritmo considerando un tiempo de servicio en
cada parada de 2 minutos, esto se determinó al tomar el
tiempo físico en cada paradero y sacar un promedio.
 Los costos de transporte que genera la empresa estudiada,
son muy altos con relación a las ganancias, por lo que al
presentar una reducción de los mismos, esto aumentará la
utilidad, obteniendo un gran beneficio con el uso de estas
herramientas.
84
 Gracias a Google Maps se pudo llegar a visualizar las rutas y
todo lo que conlleva esto (paradas, arcos, depósito), además al
cálculo de las distancias entre paradas y la distancia total de
cada ruta, tanto la actual como la propuesta, permitiendo ver
los resultados, de una forma gráfica.
 Al aplicar nuevas opciones de arcos, que permiten la aparición
de nuevas rutas, la herramienta matemática Gams, se encargo
de mostrar la mejor opción de ruta, es decir la óptima con un
equilibrio entre la distancia y el tiempo.
 La aplicación de un algoritmo post optimización nos ayuda a
corregir ciertos errores del programa obteniendo una mejora
global en la respuesta final.
5.2 Recomendaciones
 Debido al poco desarrollo de la investigación de operaciones en
nuestro país, muchas veces se toman decisiones de forma
empírica este caso nos demuestra que se puede llegar a un

85
ahorro significativo cuando se tienen las herramientas
adecuadas.
 Nuestro mercado es cada día más competitivo, estas
herramientas se traducen en ventajas competitivas. Muchas
veces el poco interés de los empresarios en la capacitación de
los empleados produce un retraso en el desarrollo. Además de
la reducción de costos que se obtiene se debe considerar la
percepción para con el servicio ofrecido.
 Se debería de reconsiderar la ubicación de paraderos, no
deberían de estar demasiados seguidos en algunos casos, se
recomienda incluir las rutas con paraderos parecidos en una
solo.
 También se recomienda cambiar la ubicación del depósito,
efectuando un análisis, para llegar a un sitio más adecuado, ya
que se da el caso de que en algunas paradas, en donde se
empieza la ruta, se deben recorrer una distancia significativa
para empezar el camino. Podría darse el caso de tener más de
un depósito, para evitar la realización de dichas distancias.

86
 Para problemas muchos más grandes, es decir con mayor
número de clientes y de paraderos, que incremente las
variables y restricciones, se recomienda realizar heurísticas,
por la complejidad computacional.

87
APÉNDICES
88
APÉNDICE A
ILUSTRACIÓN EN GOOGLE MAPS DE LAS RUTAS QUE REALIZA LA
EMPRESA DE TRANSPORTE EN LA ACTUALIDAD
RUTA 1
Esta ruta tiene una distancia total de 63.6 Kilómetros con un tiempo de 1
hora 24 minutos.
89
RUTA 2
En la ruta 1-Pascuales, se tiene una distancia total de 50.3 Kilómetros con
un tiempo de 56 minutos.
RUTA 3
Para la ruta 2-4, se tiene una distancia total de 30. Kilómetros con un tiempo
de 1 hora 5 minutos.
90
RUTA 4
En la ruta 3, se tiene una distancia total de 13.5 Kilómetros con un tiempo de
25 minutos.
RUTA 5
Dentro de esta ruta, se tiene una distancia total de 69.3 Kilómetros con un
tiempo de 1 hora 22 minuto

91
APÉNDICE B
ILUSTRACIÓN DE ALGUNOS PARADEROS ESTABLECIDOS POR LA
EMPRESA DE TRANSPORTE EN GOOGLE EARTH
PARADEROS DE LA RUTA 2 DEL DEPARTAMENTO DE OPERACIONES
PARADEROS DE LA RUTA 8 DEL DEPARTAMENTO DE FACTURACIÓN

92
APÉNDICE C
RESULTADOS EN GAMS DE LOS DIFERENTES
DEPARTAMENTOS
93
94
DEPARTAMENTO DE FACTURACIÓN
95
96
APÉNDICE D
MODELO MATEMÁTICO EN GAMS
SETS
paraderos(i) PARADEROS
/y1,y2,y3,y5,y6,y7,y8,y9,y10,y11,k2,t1,t2,t3,t4,t5,t6,t7,t8,t9,y4,k1,q5,q6,q7,q8,q9,q10,k6,t10,k
3,k4,k5,q1,q2,q3,q4,k7/
SETS
nodo_sal(i) NODO DE INICIO /s/
nodo_lleg(i) NODO DE LLEGADA /r/;
SETS
k depositos/a,b,c,d/
SETS
arcos(i,j,k)
todos/s.y1.a,s.y2.a,s.y3.a,s.y5.a,s.y6.a,s.y7.a,s.y8.a,s.y9.a,s.y10.a,s.y11.a,s.k2.a,
y1.y2.a,y1.y3.a,y1.y5.a,y1.y6.a,y1.y7.a,y1.y8.a,y1.y9.a,y1.y10.a,y1.y11.a,y1.k2.a,
arcoconexion(i,j,k) conexion/
y9.y1.a,y9.y2.a,y9.y3.a,y9.y5.a,y9.y6.a,y9.y7.a,y9.y8.a,y9.y10.a,y9.y11.a,y9.k2.a
parameters
costos(i,j,k) costos por viajes vacios
/
s.y1.a 2.16
s.y2.a 2.13
s.y3.a 2.08
s.y5.a 1.24
s.y6.a 1.45
s.y7.a 1.89
s.y8.a 2.25
s.y9.a 1.42
97
s.y10.a 2.66
s.y11.a 3.73
s.k2.a 5.13
y1.y2.a 0.18
y1.y3.a 0.64
y1.y5.a 1.37
Capacidad(i) Número de personas ubicadas en los paraderos
/
y1 2
y2 3
y3 1
y5 1
y6 2
y7 1
y8 1
y9 2
y10 2
y11 1
Penalizacion(i) Multa porno cumplir con
/
y1 0.39
y2 0.39
y3 0.39
k2 0.43
y5 0.39
y6 0.39
y7 0.39
y8 0.39
y9 0.39
y10 0.39
y11 0.39
tiempo_serv(i) Tiempo que trascurre el bus en el paradero
/
y1 2
y2 2
y3 2
k2 2
y5 2
y6 2
y7 2
y8 2
y9 2
y10 2
y11 2
tiempos(i,j,k)
/
s.y1.a 8
s.y2.a 8
s.y3.a 8
s.y5.a 5
s.y6.a 6
s.y7.a 7
s.y8.a 9
98
s.y9.a 5
s.y10.a 10
s.y11.a 14
s.k2.a 20
liminf(i)
/
y1 8
y2 8
y3 8
y5 5
y6 6
y7 7
y8 9
y9 5
y10 10
y11 14
limsup(i)
/
y1 80
y2 80
y3 80
k2 80
y5 80
y6 80
y7 80
y8 80
y9 80
y10 80
y11 80
Capacidad_Veh(k)
/a 17
b 17
c 17
d 17
Costo_fijo(k)
/a 0.52
b 0.52
c 0.52
d 0.52
/
variables
z Costo total de la ruta
x(i,j,k) Binaria (si la ruta pasa del nodo i al nodo j en el bus k)
Positive variable
r(i) Tiempo de atraso al atender la siguiente parada i
t(i) Tiempo en el que se recoge a los clientes en cada parada i;
Binary Variable x;
99
equation
obj funcion objetivo
res1 todos los paraderos deben ser visitados una sola vez
res2 cada ruta debe ser realizada por un solo vehiculo k
res3 cada uno de los vehiculos k parte solo del deposito s al iniciar la ruta
res4 la suma total de las personas ubicadas en los paraderos visitados por el vehiculo k no
debe superar su capacidad
res5 la ventana de tiempo superior mas el tiempo de atraso debe exceder al tiempo en el
que se recoge al cliente en el paradero i
res6 la ventana de tiempo inferior debe ser menor o igual al tiempo en el que el vehiculo
pasa por el paradero i
res7 asegura que el tiempo de visita a las paradas esten de acuerdo con los arcos
seleccionados (continuidad del tiempo)
res8 cada vehiculo k llega una sola vez al destino r;
obj.. z=e=sum((i,j,k)$(arcos(i,j,k)),costos(i,j,k)*x(i,j,k));
res1(paraderos).. sum((i,k)$(arcos(i,paraderos,k)),x(i,paraderos,k))=e=1;
res2(paraderos,k).. sum(i$(arcos(i,paraderos,k)),x(i,paraderos,k))=e=
sum(i$(arcos(paraderos,i,k)),x(paraderos,i,k));
res3(k).. sum(paraderos$(arcos('s',paraderos,k)),x('s',paraderos,k))=e=1;
res4(k).. sum((i,j)$(arcos(i,j,k)),x(i,j,k)*Capacidad(i))=l=Capacidad_Veh(k);
res5(paraderos).. t(paraderos)=l=limsup(paraderos);
res6(paraderos).. t(paraderos)=g=liminf(paraderos);
res7(paraderos,j,k)$(arcoconexion(paraderos,j,k)).. t(paraderos)+tiempos(paraderos,j,k)-
t(j)+tiempo_serv(paraderos)=l=(1-x(paraderos,j,k))*100000;
res8(k).. sum(paraderos$(arcos(paraderos,'r',k)),x(paraderos,'r',k))=l= 1;
MODEL CVRPTW /all/;

SOLVE CVRPTW USING MIP MINIMIZING Z;
DISPLAY X.L,T.L,Z.L;
FILE SOLUCION /D:\MODELO MATEMATICO.TXT/;

PUT SOLUCION;
PUT "TESIS SOBRE LA PROGRAMACION MATEMATICA PARA TRANSPORTE DE

PERSONAL"//;
PUT "REALIZADO POR: LORENA LOOR Y PATRICIA SANCHEZ"//;
PUT "FECHA:" PUT SYSTEM.DATE//
PUT "HORA:" PUT SYSTEM.TIME//;
PUT "EL COSTO TOTAL DE LAS RUTAS ES DE [$]:" Z.L:10 //;

100
APÉNDICE E
ILUSTRACIÓN DE LA NUEVA PROPUESTA DE RUTAS POR
DEPARTAMENTO
OPERACIONES
RUTA 1 RUTA 2
Con cruce Sin cruce

101
RUTA 3 RUTA 4 RUTA 5
Con cruce Sin cruce Con cruce Sin cruce

102
FACTURACIÓN
RUTA 7 RUTA 8 RUTA 9

103
ADMINISTRACIÓN
RUTA 12 RUTA 13
104
RUTA 14 RUTA 15
Con cruce Sin cruce

105
APÉNDICE F
TABLA DE COORDENADAS DE FACTURACIÓN Y ADMINISTRACIÓN
RUTAS DE FACTURACIÓN
RUTA 7
i1 618,63684 9766,63472
i2 618,54042 9763,32167
i3 619,02224 9761,47666
i4 619,3081 9760,65302
i5 618,8312 9757,60857
i6 619,60121 9757,41156
i7 620,69239 9757,1376
i8 620,48167 9756,52654
i9 620,8275 9756,43709
i10 620,73129 9756,07482
i11 619,19683 9756,10588
i12 618,14027 9754,84868
i13 617,80381 9753,125
i14 621,68917 9752,46357
i15 622,82422 9751,39219
i16 622,824 9751,392
RUTA 8
o1 622,66452 9763,24284
o2 622,84315 9764,07803
o3 622,30956 9765,49958
o4 622,29074 9766,7234
o5 621,71682 9765,41801
o6 621,60583 9764,7619
o7 621,52201 9763,75839
o8 622,85998 9762,87144
o9 622,681 9760,23713
o10 623,11806 9762,2115
106
o11 623,12506 9761,54133

o12 622,55094 9760,13608
o13 622,40331 9759,91331
o14 622,74625 9758,78886
o15 622,27374 9756,72276
o16 622,90198 9756,56354
o17 622,35601 9754,74105
o18 622,29888 9753,94837
o19 622,54642 9753,56043
o20 622,824 9751,392
RUTA 9
u1 623,57766 9758,43271
u2 622,90509 9756,55757
u3 622,33512 9754,76472
u4 622,35601 9754,74105
u5 623,46288 9753,29662
u6 623,34779 9751,94367
u7 624,64789 9750,11946
u8 623,83466 9751,16776
u9 623,4634 9750,3185
u10 621,8032 9748,68752
o11 623,12506 9761,54133
o12 622,55094 9760,13608
107
RUTAS DE ADMINISTRACIÓN
RUTA 12
y1 621,42575 9763,42706
y2 621,62609 9763,5758
y3 622,11709 9763,96763
y4 622,28405 9763,84177
y5 620,9868 9761,22283
y6 620,87789 9761,50382
y7 619,91546 9761,39284
y8 619,6352 9761,80435
y9 619,9144 9760,48056
y10 617,85218 9759,80933
y11 617,22846 9762,24618
RUTA 13
t1 622,29035 9766,7228
t2 622,30028 9764,96263
t3 623,78848 9764,7618
t4 623,76336 9764,46852
t5 623,95714 9763,75952
t6 623,62981 9763,27863
t7 623,10584 9762,20721
t8 622,67945 9762,20187
t9 623,06447 9761,5657
t10 622,33268 9754,76473
RUTA 14
k1 623,40044 9758,16227
k2 623,30572 9751,29251
k3 622,175 9756,428
k4 622,071 9756,085
k5 621,97463 9755,79439
k6 622,57706 9754,9865
k7 622,824 9751,392
RUTA 15
q1 619,43896 9755,59628
108
q2 620,96174 9755,7049
q3 621,11123 9754,7009
q4 623,20372 9749,94295
q5 623,3189 9752,45331
q6 623,3552 9751,75129
q7 623,305 9751,292
q8 623,10199 9750,57871
q9 623,47902 9750,31728
q10 622,958 9749,515
q11 622,824 9751,392
109
APÉNDICE G
RUTAS DESPUÉS DE APLICAR EL MÉTODO DE BARRIDO
Ruta 7 Nomenclatura Capacidad Acumulado Angulo

Vía daule (fuerte huancavilca) i1 1 1 355,27
Vía daule (prosperina) i2 2 3 346,98
Vía daule (super éxito) i3 1 4 346,51
Tunel san eduardo i4 1 5 339,66
Puente patria i5 1 6 339,5
Gómez Rendón y la 29 i6 1 7 328,3
Frente a la española o1 1 8 211,37
Cnt guayacanes o2 1 9 194,34
Terpel guayacanes (av. Isidro o3 1 10 192,09
ayora)
Mobil de samanes o4 1 11 188,74
Garita cdla el alcance o5 1 12 188,37
Riocentro norte – hypermarket o6 1 13 186,48
Banco bolivariano, av. Fco. o7 1 14 186,06
Orellana
Supermaxi o8 1 15 182,49
Terpel Garzota (cerca mall del o9 1 16 181,25
sol)
Hilton Colón o10 1 17 179,66
110

Registro civil i15 2 2 179,03
Universidad estatal o12 1 3 178,79
Tungurahua y Gómez Rendón o13 1 4 177,7
Mall de sur o17 1 5 176,73
Machala y Manuel Galecio u1 3 8 176,31
Colegio Guayaquil u2 1 9 175,13
Domingo Comín (caraguay) u5 2 11 162,84
Domingo Comín (pradera) u6 1 12 158,27
Domingo Comín (Guasmo central) u7 1 13 158,15
Adolfo h Simons (floresta 2) u8 2 15 153,71
Raúl clemente huerta y domingo u9 2 17 152,54
Comín

Gómez Rendón y la 17 i7 1 1 147,9
Venezuela y la 17 i8 1 2 144,09
Venezuela y la 11 i9 1 3 142,72
La 11 y 4 de noviembre i10 1 4 137,04
Nicolás González y la 29 i11 1 5 128,07
Cementerio de batallón i12 1 6 85,67
La q y salida a la i13 1 7 72,6

perimetral
Tía de la perimetral i14 1 8 52,86
Edificio de la aduana i16 1 9 31,18
CNT Guayacanes o11 1 10 15,05
Antepara y Vicente Trujillo o15 4 14 8,7
Las acacias o16 1 15 7,69

Pancho segura y Antepara u3 1 16 1,37
Base naval sur u10 1 17 1,2
111

La rotonda y1 2 2 19.12
La rotonda después dos cuadras y2 3 5 14.12
Bris Sánchez y3 1 6 12.14
R. Baquerizo plaza Quil y5 1 7 60.58
El portón de Urdesa y6 2 9 52,58
Las aguas y7 1 10 66.95
Las aguas Facso y8 1 11 63.34
Parada metrovía federación y9 2 13 72.53
Mc Donal´s ceibos y10 2 15 96.75
Ceibos norte y11 1 16 69.84
Cdla. Bellavista k2 1 17 90.89

Mobil de los samanes t1 2 2 2.55
Pai sauces vi t2 1 3 3.8
El dorado t3 1 4 11.74
Iglesia Mormos sauces iii t4 2 6 20.47
Sauces II Frente a Denso t5 2 8 22.20
Santa Isabel Garzota t6 2 10 19.80
Mobil garzota distrito t7 1 11 17.03
Fco. De Orellana tres cerritos t8 3 14 5.66
Frente a Mall del Sol t9 2 16 25.09
Rodolfo Baquerizo bco. y4 1 17
Internacional
112

José de Antepara y Quisquis k1 3 3 190.81
Pradera (redondel) q5 2 5 185.81
Pradera ( metrovia-D. Comín) q6 1 6 189.90
7 lagos ( D. Comín) q7 2 8 185.02
Floresta ( D. Comín) q8 2 10 188.13
Av. Las Exclusas Y D. Comín q9 1 11 185.54
Juan Péndola y Domingo Comín q10 2 13 182.46
Trujillo y la 25 de julio k6 4 17 180.56

José Antepara Fco.Segura y t10 1 1
Oriente 178.46
Tungurahua y Letamendi k3 1 2 175.07
Tungurahua y Venezuela k4 3 5 174.26
Bolivia y Tungurahua k5 2 7 173.28
20 y Fco segura q1 2 9 147.19
4 de noviembre y la 11 q2 1 10 157.01
Fco segura y guerrero Valenzuela q3 1 11 166.09
Perimetral (por Tía) q4 2 13 174.24
CAE k7 4 17 175.76
113
APÉNDICE H
ALGORITMO DE BARRIDO EN MATLAB
function patty=patty0(matriz)
%columna uno angulo
%columna dos distancia
%columna tres capacidad
tamanomatriz=size(matriz);
lista=tamanomatriz(1);
d=0;
deposito=[d d d];
%vehiculos capacidad
k=17;
matrizB(lista,3)=0;
vehiculos(1,lista)=0;
n=0;
w=max(matriz);
w=w(1);
n=0;
m=w;
q=0;
for i=1:lista
m=w;
for j=1:lista
if(n<matriz(j,1) && matriz(j,1)<m)
c=matriz(j,3);
m=matriz(j,1);
q=0;
else
if(matriz(j,1)==w)
%matrizB(lista,3)=matriz(j,3)
q=1;
z=j;
end
end
end
matrizB(i,1)=m;
matrizB(i,3)=c;
n=m;
if(q==1)
matrizB(lista,3)=matriz(z,3);
end
end
z=0; n=1; m=1; q=0;
114
matrizB
matrizB(lista+1,1)=0;
captotal=18;
for i=1:lista+1
if(z<captotal)
z=z+matrizB(i,3);
vectorsuma(n,m)=z;
vector(n,m)=matrizB(i,3);
vectorlargo(i)=matrizB(i,3);
m=m+1;
q=q+1;
if(z>=captotal)
z=matrizB(i,3);
n=n+1;
m=1;
end
end
end
%vectorsuma
n=size(vectorsuma);
for i=1:n(1)
for j=1:n(2)
if(vectorsuma(i,j)>captotal && j>1)
vectorsuma(i,j)=0;
end
if(vectorsuma(i,j)>=captotal && j==1)
vectorsuma(i,j)=vectorlargo(i);
end
end
end
%vector
vectorsuma
%vectorlargo
numeroscarros=n(1)
115
APÉNDICE I
RESULTADO DEL ALGORITMO DE BARRIDO EN
MATLAB-FACTURACIÓN
matrizB =
4.7300 0 1.0000
13.0200 0 1.0000
13.4900 0 1.0000
20.3400 0 1.0000
20.5000 0 1.0000
31.7000 0 1.0000
148.6300 0 3.0000
165.6600 0 1.0000
167.9100 0 1.0000
171.2600 0 2.0000
171.6300 0 2.0000
173.5200 0 1.0000
173.9400 0 1.0000
177.5100 0 2.0000
178.7500 0 1.0000
180.3400 0 1.0000
180.9700 0 1.0000
181.2100 0 4.0000
182.3000 0 1.0000
183.2700 0 1.0000
183.6900 0 1.0000
184.8700 0 1.0000
197.1700 0 1.0000
201.7300 0 1.0000
201.8500 0 1.0000
206.2900 0 1.0000
207.4600 0 1.0000
212.1000 0 1.0000
215.9100 0 1.0000
217.2800 0 1.0000
222.9600 0 1.0000
231.9300 0 1.0000
274.3300 0 1.0000
116
287.4000 0 1.0000
307.1400 0 2.0000
328.8200 0 1.0000
344.9500 0 1.0000
351.3000 0 1.0000
352.3100 0 1.0000
358.6300 0 1.0000
358.8000 0 1.0000
vectorsuma =
1 2 3 4 5 6 9 10 11 13 15 16 17 0 0
3 4 5 9 10 11 12 13 14 15 16 17 0 0 0
2 3 4 5 6 7 8 10 11 12 13 14 15 16 16
numeroscarros =
3
117
GLOSARIO
 Algoritmo: conjunto prescrito de instrucciones o reglas bien definidas,

ordenadas y finitas que permite realizar una actividad mediante pasos
sucesivos que no generen dudas a quien deba realizar dicha actividad.
 Arco: es cualquier curva continua que une dos puntos.
 Arista: uniones entre nodos o vértices.
 Complejidad: cualidad de lo que está compuesto de diversos elementos.

En términos generales, la complejidad tiende a ser utilizada para
caracterizar algo con muchas partes que forman un conjunto intrincado.
 Containers: recipiente de carga para el transporte aéreo, marítimo o

fluvial, transporte terrestre y transporte multimodal.
 Continuidad: aquella para la cual, intuitivamente, para puntos cercanos

del dominio se producen pequeñas variaciones en los valores de la
función.
 Core-Activity: actividad central que realiza una organización.
 Depósito: lugar en el cual se guarda alguna cosa o se mantiene
 Enrutamiento: función de buscar un camino entre todos los posibles en

una red de paquetes cuyas topologías poseen una gran conectividad.
 Grafo: conjunto de objetos llamados vértices o nodos unidos por enlaces

llamados aristas o arcos, que permiten representar relaciones binarias
entre elementos de un conjunto.
 Gams: lenguaje de modelización, más que un programa para resolver

problemas de optimización.
 Heurísticas: capacidad de un sistema para realizar de forma inmediata

innovaciones positivas para sus fines.
118
BIBLIOGRAFÍA
[1] Ballou, Ronald H., (2004)”Logística: Administration de la cadena de

suministro,” Pearson Educación vol. 5, pp. 235-245.
[2] Bodin, L.,Golden, B., Assad, A. and Ball, M. (1983)”Routing and

Scheduling of Vehicles and Crews: The State of the Art,” Comput .Opns. Res
vol. 10, pp. 62-212.
[3] B. Kallehauge, “Formulations and exact algorithms for the vehicle routing
problem with time windows” Computers & Operations Research Vol. 35
(2008) pp. 2307 – 2330
[4] F. Li, B. Golden, E. Wasil: "Very large-scale vehicle routing: new test
problems, algorithms, and results". Computers & Operations Research, 32
(5), pp. 1165-1179. 2005.
[5] Garey, M.R. & D. Johnson (1979). “Computers and intractability: A guide
to the theory of np-completeness”. Freeman.
[6] G. B. Dantzing and J. H. Ramser, “The Truck Dispatching Problem”

Management Science, Vol. 6, No. 1 (Oct., 1959), pp. 80-91.
[7] James tomala, Johnny Pincay, “Diseño de un Sistema de Soporte de

decisiones para resolver el Problema de Ruteo en un servicio de Courier”,
Escuela Superior Politécnica del Litoral, Guayaquil – Ecuador, 2010.
[8] M. M. Solomon. "Algorithms for the Vehicle Routing Problem with Time
Windows". Transportation Science, 29(2), pp. 156-166. 1995.
[9] M. L. Fisher, "Optimal Solution of Vehicle Routing Problems Using

Minimum K trees", Operations Research 42, 626-642, 1994.
[10] Nemhauser, G., Wolsey, L.: “Integer and Combinatorial Optimization”.

John Wiley & Sons (1988)
119
[11] Lenstra, J.K. & A. Rinnooy Kan (1981). “Complexity of vehicle routing
and scheduling problems”. Networks, 11, 221-227.
[12] Paolo Toth y Daniele Vigo, “The vehicle routing problem”, Universidad de
Bologna, Italia, 2002.
[13]Pedregal Pablo , Ricardo García, Enrique Castillo, Antonio J. Conejo y

Natalia Alguacil (2002)” Formulación y Resolución de Modelos de
Programación Matemática en Ingeniería y Ciencia.” pp.1-574
[14] Starkweather. T., McDaniel S.,Mathias K., Whitley D. and Whitley C.

(1991) “A Comparison of Genetic Sequencing Operators”. Proceedings of the
Fourth International Conference on Genetic Algorithms. Morgan
Kaufmann Pub
[15] Solomon, M.M. and Desrosiers, J: (1988) ”Time Window Constrained

Routing and Scheduling Problems: A Survey”. Transportation Science vol. 22
(1), pp. 1-11
[16] Zeimpekis, V., Minis, I., Mamassis, K., and Giaglis, G. M. (2007a).
“Dynamic management of a delayed delivery vehicle in a city logistics
environment “. In Zeimpekis, V., Tarantilis, C. D., Giaglis, G. M., and Minis,
L., editors, Dynamic Fleet Management , volume 38 of Operations
Research/Computer Science Interfaces Series, charper 9, pages 197-217.
Springer US.
[17] www.gams.com
[18] www.neos-server.org

Tesis de Transporte

Cargado por

Copyright:

Formatos disponibles

Tesis de Transporte

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Tesis de Transporte

Cargado por

Copyright:

Formatos disponibles

ESCUELA SUPERIOR POLITÉCNICA DEL LITORAL

INSTITUTO DE CIENCIAS MATEMÁTICAS

“DISEÑO DE RUTAS DE TRANSPORTE DE PERSONAL

Previa a la obtención del Título de:

INGENIERO EN LOGÍSTICA Y TRANSPORTE

Lorena Marina Loor Vélez

Patricia Elizabeth Sánchez Villamar

Lorena Loor Vélez

Patricia Sánchez Villamar

A ti mi amado Dios por brindarme la vida y regalarme una hermosa familia, a

Lorena Loor Vélez

Patricia Sánchez Villamar

“La responsabilidad del contenido de esta

Tesis de Grado, me corresponden

exclusivamente; y el patrimonio intelectual de

la misma a la ESCUELA SUPERIOR

POLITÉCNICA DEL LITORAL”

(Reglamento de Graduación de la ESPOL)

Lorena Loor Vélez Patricia Sánchez Villamar

En el presente trabajo se implementa un modelo de programación matemática

con las restricciones de ventanas de tiempo, capacidad de los vehículos de una

empresa la cual realiza la función de transporte de personal a otras entidades.

La tesis está estructurada en tres capítulos. El primer capítulo consiste en un

estudio de la situación actual de la empresa, que involucra, paraderos, clientes,

vehículos y costos de las rutas definidos por la empresa. En la segunda etapa

se analiza el modelo matemático que mejor se ajuste a las condiciones reales.

En el último capítulo se entregan los resultados de la investigación, que como

se mencionó anteriormente es el diseño de rutas óptimas y además las

La elaboración de este trabajo pretende demostrar como la optimización de las

rutas ayudan a reducir los costos de transportación.

This article implements a mathematical programming model that has as main

windows, vehicle capacity of a company which performs the function

of transporting personnel to other entities. It is structured as follows: The first

part contains an introduction to the problem. The second section is a study of

of optimal routes and finally the conclusions, acknowledgments and necessary

recommendations are mentioned. The preparation of this paper aims

to demonstrate how route optimization helps reduce transportation costs.

ÍNDICE GENERAL .................................................................................... III

ÍNDICE DE FIGURAS ............................................................................. VII

ÍNDICE DE TABLAS............................................................................... VIII

1.1 Justificación e importancia ........................................................... 2

1.2 Objetivo General .......................................................................... 2

1.3 Objetivos específicos ................................................................... 3

2. ANÁLISIS DE LA SITUACIÓN ACTUAL ............................................ 4

2.1 La problemática básica. ............................................................... 5

2.2 Clientes ........................................................................................ 6

2.3 Depósitos ..................................................................................... 8

2.4 Rutas ........................................................................................... 9

2.5 Paraderos .................................................................................. 11

2.6 Vehículos ................................................................................... 18

2.7 Costos Fijos y Variables ............................................................ 21

2.7.1 Costos Fijos .................................................................... 21

2.7.2 Costos Variables ............................................................. 22

3. EL PROBLEMA DE ENRUTAMIENTO VEHICULAR ........................ 24

3.1 Estado el Arte del CVRPTW .................................................... 24

3.2 El problema de ruteo capacitado con ventanas de tiempo

3.2.1 Capacitated Vehicle Routing Problem (CVRP) ............ 31

3.2.2 Times Windows Vehicle Routing Problem (TWVRP) ... 32