DESARROLLO DE UN PLANIFICADOR DE RUTAS PARA EL RECOJO DE

DESECHOS SÓLIDOS EN EL DISTRITO DE PILLCO MARCA - HUÁNUCO

Ángel Pozo Estrada, usuario@[Link]

Baldwin Vara Moreno, baldwinvm49@[Link]

Trabajo de Grado presentado para optar al título de Ingeniero de Sistemas

Asesor: Adam Francisco Paredes, Seleccione título académico más alto del asesor en Ejemplo
Gerencia de la Innovación.

Universidad Nacional Hermilio Valdizán

Facultad de Ingeniería Industrial y de Sistemas
Ingeniería de Sistemas
Huánuco, Perú
2019
 Citar/How to cite [1]

Referencia/Reference [1] A.J. Pozo Estrada, B. Vara Moreno, y E. Vela Lastra, “Desarrollo de un
planificador de rutas para el recojo de desechos sólidos en el distrito de Pillco
Marca - Huánuco”, Tesis Ingeniería de Sistemas, Universidad Nacional Hermilio
Estilo/Style: Valdizán, Facultad de Ingeniería Industrial y Sistemas, 2019.
IEEE (2014)
 Dedicatoria

A nuestros padres, por el apoyo constante y desinteresado que nos brindan, de la misma forma a
nuestros docentes, por guiarnos en nuestro desarrollo académico y profesional.
Tabla de contenido
I. PLANTEAMIENTO DEL PROBLEMA ............................................................................... 10

A. Antecedentes y fundamentación del problema................................................................... 10

B. Formulación del problema ................................................................................................. 10

1. Problema General ............................................................................................................ 10

2. Problemas Específicos ..................................................................................................... 10

C. Objetivos ............................................................................................................................ 11

1. General............................................................................................................................. 11

2. Específicos ....................................................................................................................... 11

D. Justificación e importancia ................................................................................................. 11

E. Limitaciones ....................................................................................................................... 11

II. MARCO TEÓRICO ........................................................................................................... 12

A. Revisión de estudios realizados.......................................................................................... 12

1. [2]..................................................................................................................................... 12

2. [3]..................................................................................................................................... 12

3. [4]..................................................................................................................................... 13

4. [5]..................................................................................................................................... 15

5. [6]..................................................................................................................................... 17

6. [7]..................................................................................................................................... 18

B. Conceptos Fundamentales .................................................................................................. 19

1. Problema del camino más corto....................................................................................... 19

2. Algoritmo de Dijkstra ...................................................................................................... 19

3. Algoritmo de Bellman-Ford ............................................................................................ 20

4. Algoritmo de búsqueda A* .............................................................................................. 21

C. Definición de términos básicos .......................................................................................... 22

 1. Algoritmo: ....................................................................................................................... 22

2. Base de datos: .................................................................................................................. 22

3. Sistema de posicionamiento global (GPS): ..................................................................... 22

III. Referencias ......................................................................................................................... 25

 LISTA DE TABLAS

TABLA I. RESULTADOS DEL TEST ........................................ Error! Bookmark not defined.

 LISTA DE FIGURAS

Fig. 1. Imagen corporativa Institute of Electrical and Electronics Engineers (IEEE). .......... Error!
Bookmark not defined.
Fig. 2. Logo Biblioteca Digital (Repositorio) Universidad de San Buenaventura. ................ Error!
Bookmark not defined.
 RESUMEN

La presente tesis tiene como objetivo desarrollar un planificador de rutas óptimas mediante la
aplicación de un algoritmo de caminos cortos para el recojo de desechos sólidos en el distrito de
Pillco Marca con el fin de mejorar la rentabilidad.
En el marco teórico se analizan los algoritmos de caminos cortos de manera teórica, basado en
antecedentes nacionales e internacionales.
Se plantean también la hipótesis general y las específicas, así como el marco metodológico de la
investigación. Seguidamente se plantea la población, la muestra y las técnicas de recolección y
tratamiento de datos.
 ABSTRACT

The objective of this thesis is to develop an optimal route planner by applying a short path algorithm
for the collection of solid waste in the district of Pillco Marca in order to improve profitability.
In the theoretical framework, short path algorithms are analyzed theoretically, based on national
and international antecedents.
The general hypothesis and the specific hypothesis are also presented, as well as the
methodological framework of the research. Next, the population, the sample and the data collection
and treatment techniques are considered.
 I. PLANTEAMIENTO DEL PROBLEMA
A. Antecedentes y fundamentación del problema
A nivel mundial, especialmente en las grandes ciudades de los países de América Latina y el
Caribe, el manejo de los residuos sólidos ha representado un problema debido, entre otras cosas, a
los altos volúmenes de residuos sólidos generados por los ciudadanos; cuando el manejo de éstos
no esel adecuado, puede afectar la salud de los ciudadanos y al medio ambiente.
En el Perú, la generación de los residuos sólidos municipales a experimentado en los últimos
años un incremento significativo, asociado al crecimiento económico, la generación per cápita de
residuos sólidos municipales ha pasado de 0.711 hg/hab/día en el 2001 a 1.08 kg/hab/día el 2007.
Para disminuir el aumento de residuos sólidos, en estos tiempos con el desarrollo tecnológico se
busca automatizar la tarea de planificación de las rutas de recojo. El concepto de automatizar no es
uno nuevo, se puede decir que en la antigüedad ya se trataba de automatizar procesos; como
ejemplo de ello, los egipcios inventaron y utilizaron muchas máquinas básicas, como la rampa y la
palanca, como ayuda en las construcciones.
[1], dijo: “Creo que quizá el concepto básico de automatización sea un medio para organizar o
controlar los procesos de producción para lograr el uso óptimo de todos los recursos”
En el distrito de Pillco Marca la aglomeración de los residuos sólidos aumenta y con ello la
incomodidad de los vecinos, también se observa que los vehículos de recolección no pasan por
todas las cuadras del distrito, por ello se propone desarrollar un planificador de rutas óptimas
mediante la aplicación de algoritmos de caminos cortos, apoyando la planificación para el recojo
de desechos sólidos en el distrito.
B. Formulación del problema
Frente al problema planteado, formulamos las siguientes interrogantes:
1. Problema General
¿Cuál es el sistema que nos permite planificar de manera óptima el recojo de los desechos
sólidos en el distrito de Pillco Marca?
2. Problemas Específicos
 ¿Cuál es el modelo de la base de datos y de la interfaz gráfica de la web que cumple
con los requerimientos del sistema?
 ¿Cuál es el algoritmo adecuado para calcular de manera óptima la ruta más corta?
  ¿Cuál es la herramienta adecuada para desarrollar el mapa del distrito y administrar
los datos geográficos?
C. Objetivos
1. General
 Desarrollar un sistema planificador de rutas óptimas para el recojo de desechos sólidos
mediante la aplicación de un algoritmo de caminos cortos en el distrito de Pillco Marca.
2. Específicos
 Identificar cuáles son los requerimientos del sistema para realizar el modelo de la base
de datos y la interfaz gráfica del sistema
 Analizar e identificar que algoritmo es el adecuado para calcular de manera óptima la
ruta más corta
 Seleccionar una herramienta para desarrollar el mapa del distrito y administrar los datos
geográficos
D. Justificación e importancia
La realización de esta investigación responde a la necesidad de optimizar la planificación de
rutas para el recojo de desechos sólidos en el distrito de Pillco Marca, Huánuco; minimizando
costos y aumentando la productividad.
También responde a la necesidad de la sociedad por mantener limpias las vías públicas.
E. Limitaciones
El proyecto se limita geográficamente al distrito de Pillco Marca, Huánuco.
 II. MARCO TEÓRICO
A. Revisión de estudios realizados
1. [2]
[2] en su tesis de grado: “Optimización de rutas en una empresa de recojo de residuos
sólidos en el distrito de los Olivos” llegó a las siguientes conclusiones:
 La optimización de rutas para una empresa de recolección de residuos sólidos se
basa en gran parte en un modelo teórico, pero es fundamental tomar en cuenta el
factor empírico para ajustar a la realidad el modelo con mayor exactitud.
 La sectorización de rutas brinda un ahorro para que las empresas puedan evitar
alquiler de vehículos o utilizarlos para motivos adicional. En el caso de la empresa,
este es el principal beneficio que obtiene, por no utilizar la capacidad máxima de
sus vehículos. Brindan un beneficio como mínimo de S/. 200,000 al año.
 La implementación del modelo implica un valor presente neto de S/. 2’404,990 al
año cero. Tomando en cuenta la inversión inicial de S/. 695,980, significa una
ganancia de más del 145% respecto a la inversión inicial. Esto genera un atractivo
grande para cualquier inversionista, y también se encuentra alineado a los resultados
de las variables financieras halladas.
 El periodo de 1.43 años es un fuerte atractivo, pues significa que a partir del segundo
año genera beneficios netos, que pueden servir para inversiones adicionales.
 Una de las razones externas a la optimización de rutas que explica las diferencias
entre tiempo de recorrido de rutas entre el modelo propuesto y el tiempo real, es que
el modelo propuesto se basa en supuestos, los cuales generan una desviación
respecto al tiempo real pues no se aplican como lo indica el modelo, sino que se
ajusta y varía en el tiempo.
2. [3]
[3] en su tesis de grado: “MODELO DE OPTIMIZACIÓN DEL SISTEMA DE RECOJO
DE RESIDUOS SÓLIDOSEN EL DISTRITO DE REQUE PARA MEJORAR LA
EFICIENCIA DE OPERACIONES” llegaron a las siguientes conclusiones:
 La Municipalidad Distrital de Reque no cuenta con la información necesaria sobre
el recojo de residuos sólidos, lo cual dificulto procesar datos y analizar la situación
actual acerca del problema, y aun cuando cuentan con recurso humano asignado a
 estas tareas, no se realiza el trabajo que se debe hacer. Para la Sectorización de rutas
se realizó con la ayuda de un plano que nos brindaron, que aunque no está
actualizado, ha servido para establecer una base sobre el recojo de basura aplicando
otras técnicas.
 Se construyó el modelo de programación lineal, debiéndose plantear y resolver para
cada ruta, donde el número de variables de decisión superan los cien y el número de
restricciones los 20. EL modelo empleado es el del agente viajero con programación
entera (binario (ceros y unos)), aquel modelo que genera rutas óptimas;
minimizando distancia como función objetivo y dado que el camión recorre todos
los sectores en un día alcanzando la cobertura total de recolección.
 Para simular el modelo de programación lineal se ha utilizado el software GRAFOS
para realizar los cálculos con más rapidez. En este caso se ha utilizado el programa
GRAFOS, con la extensión de Solver, una herramienta accesible y además porque
es fácil de utilizar y los resultados se obtienen muy rápido.
 Al Diseñar y Evaluar el Modelo de optimización se tomó como medida las distancia
optimizada de recorrido y el combustible que se emplea, lo que se refleja en la
reducción de costos. Es decir para sector reque centro se reduce a 42% las
distancias; para 28 de julio se reduce a38%; para sector esperanza se reduce a13%
y para el sector Villa el sol se reduce a 31%.
 El Modelo de Optimización del Recojo de Residuos Sólidos Municipales tiene un
incremento Optimo del 100% en la eficiencia del servicio en el Distrito de Reque.
3. [4]
[1] en su tesis de grado: “Desarrollo de un sistema de localización de rutas óptimas entre
dos puntos geográficos” llegó a las siguientes conclusiones:
 Existen un sinnúmero de herramientas que permiten el desarrollo de
aplicaciones que contenga información geográfica, por lo tanto, es necesario
realizar un estudio sobre las ventajas y desventajas que proveen cada una de
éstas herramientas de acuerdo a las necesidades del problema. En este trabajo se
ha realizado una comparación entre las herramientas de mayor uso sobre este
tema.
 Es también necesario investigar sobre los algoritmos existentes, puesto que
muchos de estos algoritmos ya han sido optimizados para diversos propósitos.
En éste proyecto se necesitaba un algoritmo que determinara la ruta óptima y se
encontraron cuatro algoritmos importantes. No se puede decir que ninguno era
mejor que otro, sin embargo sí se puede decir que un algoritmo es más
conveniente que otro para determinados aspectos. Para el proyecto, el algoritmo
de Dijkstra parecía ser el más equilibrado de acuerdo a los requerimientos
planteados.
 Un inconveniente durante el desarrollo de éste proyecto fue que se tenía que
esperar mucho tiempo hasta obtener resultados durante las primeras versiones
del algoritmo del cálculo de la ruta óptima. Por lo tanto se recomienda utilizar
un computador con mucha capacidad de memoria y procesamiento para la base
de datos para éste tipo de análisis.
Es importante realizar un análisis profundo sobre la implementación de
algoritmos que necesiten ser ejecutados en el menor tiempo posible, de manera
que puedan ser optimizados al máximo. También es necesario revisar la
configuración del motor de la base de datos para destinar más recursos en caso
de ser necesario. Además, es recomendable que estos algoritmos estén
estrechamente integrados con la base de datos.
 PHP puede ser un lenguaje de Scripting que ayude en incrementar la velocidad
de desarrollo de las aplicaciones web, sin embargo tiende a volverse difícil de
mantener en el largo plazo. Esto se debe a que a medida que se incluyen nuevas
características en la interfaz gráfica, es más difícil diferenciar la lógica de la
aplicación de la codificación de la interfaz gráfica.
 La codificación de gran número de funciones como parte de la base de datos
permitirá que la aplicación pueda ser fácilmente codificada en otro ambiente
distinto a PHP, como por ejemplo a través de un servidor de aplicaciones
compatible con J2EE.
 El trabajo presentado en éste documento es un inicio a un problema que puede
ampliarse para poder ser utilizado con dispositivos de localización geográfica
que permitan a los usuarios determinar las rutas mientras están en sus vehículos.
  También se podría proveer una característica adicional que permita especificar
que una vía esté cerrada periódicamente a determinadas horas o determinados
días como un túnel por ejemplo. Sin embargo, esto se puede emular poniendo
un costo en tiempo demasiado alto de tal manera que no sean tomadas en cuenta
por el algoritmo, pero en tal caso la base de datos sería inconsistente.
 Se recomienda también implementar una función que permita determinar la
consistencia de la base de datos en el sentido de que existe al menos una ruta (no
necesariamente óptima) entre cada par de nodos de la base de datos.
 También se podría analizar la posibilidad de incluir no sólo el promedio del
costo en tiempo para cada ruta a cada hora de cada día sino también información
sobre una distribución de probabilidad sobre cada tramo para proporcionar al
usuario información sobre el tiempo mínimo y el tiempo máximo que le tomaría
recorrer la ruta óptima entre dos nodos.
 Recientemente motores de base datos como Microsoft SQL Server y MySQL
han provisto de soporte para manejo de información geográfica por lo cual se
recomienda un estudio sobre la eficiencia entre los distintos motores de base de
datos y su conectividad con Mapserver y otros paquetes de software.
4. [5]
[2] en su proyecto de titulación: “Estudio comparativo de algoritmos basados en
metaheurísticas aplicados a la solución del problema de ruteo de vehículos con capacidad
limitada”, llegó a las siguientes conclusiones:
Los resultados obtenidos al resolver los casos de prueba por las heurísticas y
metaheurísticas permiten declarar las siguientes conclusiones:
 Tanto las heurísticas como las metaheurísticas generan soluciones de mejor calidad
al resolver casos donde los clientes se encuentren de forma agrupada.
 Las heurísticas y metaheurísticas tuvieron su peor resultado en el grupo de clientes
con posición agrupada y aleatoria dado que estos tenían n grandes con referencia a
los otros grupos de clientes.
 La heurística de Clarke and Wright generó resultados de mejor calidad que la
heurística de barrido, teniendo una gran diferencia en los gaps máximos de cada uno
para cada grupo de clientes.
  Se comparó los números de vehículos obtenidos en las soluciones de ambas
heurísticas con la solución óptima y la heurística de barrido tuvo más soluciones en
la cual alcanzó el óptimo. Esto es una acotación muy importante, dado que la
heurística de Clarke and Wright obtiene soluciones con distancias más cortas que la
heurística de barrido, pero esta obtiene mayores distancias con menos unidades de
vehículos. Para algunas empresas será más importante reducir las unidades a
comprar que la distancia recorrida.
 La metaheurística de GRASP generó resultados de mejor calidad que la
metaheurística de recocido simulado, con diferencias mínimas de gap promedio para
cada grupo de clientes.
 Ambas metaheurísticas obtuvieron mayores mejoras con respecto a las soluciones
iniciales de la heurística de Clarke and Wright en los casos de prueba de los clientes
con posición aleatoria.
 La metaheurística de GRASP con el caso B-n34-k5 de clientes con posición
agrupados alcanzó la solución óptima, siendo el único caso de prueba de los treinta
que se realizaron.
Los resultados obtenidos al resolver los casos de prueba por las heurísticas y
metaheurísticas permiten declarar las siguientes conclusiones:
 Se resolvió el caso real por la heurística de Clarke and Wright se obtuvo una mejor
solución a la que la empresa realizó, con una disminución en promedio de 15
kilómetros.
 El caso real también fue resuelto por la metaheurística de GRASP, pero se obtuvo
la misma solución que con la heurística de Clarke and Wright debido a la poca
complejidad de las ubicaciones de los clientes.
 La empresa posee dos vehículos que pueden realizar hasta tres vueltas cada uno, la
respuesta obtenida por la heurística de Clarke and Wright proporciona cinco rutas.
Las mismas que se considera que se usaron dos vehículos uno haciendo tres rutas y
el otro vehículo haciendo dos rutas, con eso se descarta que la empresa podría
requerir más vehículos para completar las rutas.
5. [6]
[3] en su tesis de pre-grado “Análisis comparativo entre el algoritmo cuántico de GROVER
y un algoritmo GRASP, aplicados a la búsqueda de individuos óptimos en la población
inicial de un algoritmo genético”, llegó a las siguientes conclusiones:
 El algoritmo de Grover, y en general todo algoritmo cuántico, puede ser simulado
en un entorno clásico gracias a la representación matricial que cada uno posee por
naturaleza. Sin embargo, esto conlleva a un decremento considerable en su
eficiencia real. Siendo, entonces, fácilmente superables por algún algoritmo clásico.
Esto a raíz que las operaciones entre matrices son altamente costosas
computacionalmente hablando.
 El algoritmo cuántico de Grover es más eficaz y más eficiente que el algoritmo
GRASP. Sin embargo, también es el más complejo de implementar de los dos.
 Existe un intervalo del valor de N (cantidad de genes por cromosoma) en el cual el
algoritmo cuántico de Grover es mejor que el algoritmo GRASP en la aplicación
planteada. Para valores mayores fuera de este intervalo el algoritmo de Grover no
se puede explicar pues las necesidades computacionales se vuelven demasiado altas.
En esta tesis se utilizó el valor de N=10 (1024 elementos en el Universo) y el
algoritmo de Grover funcionó, sin embargo, de usar valores cada vez más grandes
como 15 o 20, se necesitaría una computadora con mayor capacidad de memoria.
Para valores como N=30 (más de mil millones de elementos) la cantidad de memoria
necesaria por el algoritmo de Grover (en su versión clásica planteada aquí) excede
las capacidades actuales de una computadora promedio.
 Para que el algoritmo cuántico de Grover funcione en una búsqueda es necesario
poder formular correctamente la función oráculo del elemento que se desea buscar.
Esto resulta altamente deseable cuando se busca un elemento conocido en un
universo grande. Sin embargo se vuelve un poderoso inconveniente cuando no se
puede identificar el elemento deseado. Un claro caso de esto fue detectado durante
el desarrollo de la tesis, pues no hay forma de saber si hemos encontrado el mejor
individuo (o uno de los mejores) sin antes compararlo con cada uno de los elementos
de la población. La solución a este problema es realizar varias ejecuciones del
 algoritmo de Grover como se puede comprobar en el diseño e implementación de la
búsqueda cuántica.
 El algoritmo cuántico de Grover es una opción altamente recomendable para la
realización de búsquedas siempre y cuando en el futuro pueda contarse con una
computadora cuántica completamente operacional. Esto a raíz de que el algoritmo
cuántico de Grover puede realizar búsquedas en todo el universo y no en un sub-
conjunto de este universo, como hace el algoritmo GRASP.
 La implementación del algoritmo de Grover usando matrices y vectores como
alternativa a la simulación de un entorno cuántico, restringe notablemente el campo
de aplicaciones que podrían dársele al algoritmo en un entorno clásico. Si el tamaño
del universo de posibles soluciones crece, ésta implementación clásica del algoritmo
de Grover requiere cada vez una mayor cantidad de memoria.
En la ejecución del experimento principal se trabajó con el valor de N igual a 10, lo
cual significaba que cada cromosoma tuviera en total 10 genes. Ello también
significaba que el algoritmo de Grover necesitaba usar matrices de 1024 elementos
por 1024 elementos durante cada ejecución. Si se tratara de trabajar con un valor de
N=20, el algoritmo de Grover necesitaría utilizar matrices de más de un millón de
elementos por más de un millón de elementos, una labor computacionalmente muy
costosa. Un problema real podría tener un universo de billones de posibles
soluciones, lo cual descarta de inmediato la posibilidad de usar la implementación
clásica del algoritmo de Grover.
6. [7]
[4] en su tesis de grado “Optimización de rutas de distribución de una empresa productora
de jugos”, llegó a las siguientes conclusiones:
El uso de tecnologías inteligentes de transporte como los sistemas de información
geográfica y los modelos de optimización espacial son la mejor herramienta para el diseño
de redes de distribución ya que nos proporcionan las siguientes ventajas:
 Se reducen los tiempos de diseño e implementación en por lo menos un 50 %, de 6
meses de reestructura (Supervisores, Gerente y Analista) vs 3 meses de reestructura
(Presente proyecto.)
  Los resultados obtenidos en los ahorros de la distribución e incremento de servicio
comprobaron la hipótesis.
 Nos permite tener las bases de los clientes georeferenciadas y actualizadas en todo
momento.
 Nos da una visión actual de la situación de un proceso de distribución, así como
también nos permite poder simular escenarios futuros.
El diseño de la nueva configuración de las rutas del Centro de Distribución llamado de La
Villa le permitió a la empresa procesadora de jugos obtener los siguientes beneficios:
 Tener rutas compactas, con un territorio definido y libres de traslapes con otras.
 Reducir sus costos de distribución en por lo menos un 10 %.
 Incrementar su participación de mercado en por lo menos un 10 % al tener 6 rutas
adicionales.
 Reducir sus tiempos de traslado en por lo menos un 10 %.
 Colocar sus productos en por lo menos el 70 % de sus clientes objetivo específicos.
B. Conceptos Fundamentales
1. Problema del camino más corto
En la teoría de grafos, el problema del camino más corto es el problema que consiste en
encontrar un camino entre dos vértices (o nodos) de tal manera que la suma de los pesos de
las aristas que lo constituyen es mínima. Un ejemplo de esto es encontrar el camino más
rápido para ir de una ciudad a otra en un mapa. En este caso, los vértices representarían las
ciudades y las aristas las carreteras que las unen, cuya ponderación viene dada por el tiempo
que se emplea en atravesarlas.
2. Algoritmo de Dijkstra
El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo
para la determinación del camino más corto, dado un vértice origen, hacia el resto de los
vértices en un grafo que tiene pesos en cada arista. Su nombre alude a Edsger Dijkstra,
científico de la computación de los Países Bajos que lo describió por primera vez en 1959.
La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos
que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el
camino más corto desde el vértice origen hasta el resto de los vértices que componen el
grafo, el algoritmo se detiene. Se trata de una especialización de la búsqueda de costo
 uniforme y, como tal, no funciona en grafos con aristas de coste negativo (al elegir siempre
el nodo con distancia menor, pueden quedar excluidos de la búsqueda nodos que en
próximas iteraciones bajarían el costo general del camino al pasar por una arista con costo
negativo).
Una de sus aplicaciones más importantes reside en el campo de la telemática. Gracias a él,
es posible resolver grafos con muchos nodos, lo que sería muy complicado resolver sin
dicho algoritmo, encontrando así las rutas más cortas entre un origen y todos los destinos
en una red.
Teniendo un grafo dirigido ponderado de N nodos no aislados, sea x el nodo inicial. Un
vector D de tamaño N guardará al final del algoritmo las distancias desde x hasta el resto
de los nodos.
 Inicializar todas las distancias en D con un valor infinito relativo, ya que son
desconocidas al principio, exceptuando la de x, que se debe colocar en 0, debido a
que la distancia de x a x sería 0.
 Sea a = x (Se toma a como nodo actual.)
 Se recorren todos los nodos adyacentes de a, excepto los nodos marcados. Se les
llamará nodos no marcados vi.
 Para el nodo actual, se calcula la distancia tentativa desde dicho nodo hasta sus
vecinos con la siguiente fórmula: dt(vi) = Da + d(a,vi). Es decir, la distancia
tentativa del nodo ‘vi’ es la distancia que actualmente tiene el nodo en el vector D
más la distancia desde dicho nodo ‘a’ (el actual) hasta el nodo vi. Si la distancia
tentativa es menor que la distancia almacenada en el vector, entonces se actualiza
el vector con esta distancia tentativa. Es decir, si dt(vi) < Dvi → Dvi = dt(vi)
 Se marca como completo el nodo a.
 Se toma como próximo nodo actual el de menor valor en D (puede hacerse
almacenando los valores en una cola de prioridad) y se regresa al paso 3, mientras
existan nodos no marcados.
Una vez terminado al algoritmo, D estará completamente lleno.
3. Algoritmo de Bellman-Ford
El algoritmo de Bellman-Ford (algoritmo de Bell-End-Ford) genera el camino más corto en
un grafo dirigido ponderado (en el que el peso de alguna de las aristas puede ser negativo).
 El algoritmo de Dijkstra resuelve este mismo problema en un tiempo menor, pero requiere
que los pesos de las aristas no sean negativos, salvo que el grafo sea dirigido y sin ciclos.
Por lo que el Algoritmo Bellman-Ford normalmente se utiliza cuando hay aristas con peso
negativo. Este algoritmo fue desarrollado por Richard Bellman, Samuel End y Lester Ford.
Según Robert Sedgewick, “Los pesos negativos no son simplemente una curiosidad
matemática; […] surgen de una forma natural en la reducción a problemas de caminos más
cortos”, y son un ejemplo de una reducción del problema del camino hamiltoniano que es
NP-completo hasta el problema de caminos más cortos con pesos generales. Si un grafo
contiene un ciclo de coste total negativo entonces este grafo no tiene solución. El algoritmo
es capaz de detectar este caso.
Si el grafo contiene un ciclo de coste negativo, el algoritmo lo detectará, pero no encontrará
el camino más corto que no repite ningún vértice. La complejidad de este problema es al
menos la del problema del camino más largo de complejidad NP-Completo.
El Algoritmo de Bellman-Ford es, en su estructura básica, muy parecido al algoritmo de
Dijkstra, pero en vez de seleccionar vorazmente el nodo de peso mínimo aun sin procesar
para relajarlo, simplemente relaja todas las aristas, y lo hace |V|-1 veces, siendo |V| el
número de vértices en el grafo. Las repeticiones permiten a las distancias mínimas recorrer
el árbol, ya que en la ausencia de ciclos negativos, el camino más corto solo visita cada
vértice una vez. A diferencia de la solución voraz, la cual depende de la suposición de que
los pesos sean positivos, esta solución se aproxima más al caso general.
Existen dos versiones:
 Versión no optimizada para grafos con ciclos negativos, cuyo coste de tiempo es
O(VE).
 Versión optimizada para grafos con aristas de peso negativo, pero en el grafo no
existen ciclos de coste negativo, cuyo coste de tiempo, es también O(VE).
4. Algoritmo de búsqueda A*
El algoritmo de búsqueda A* (pronunciado "A asterisco", "A estrella" o "Astar" en inglés)
se clasifica dentro de los algoritmos de búsqueda en grafos. Presentado por primera vez en
1968 por Peter E. Hart, Nils J. Nilsson y Bertram Raphael, el algoritmo A* encuentra,
siempre y cuando se cumplan unas determinadas condiciones, el camino de menor coste
entre un nodo origen y uno objetivo.
 Propiedades:
Como todo algoritmo de búsqueda en amplitud, A* es un algoritmo completo: en caso de
existir una solución, siempre dará con ella.
Si para todo nodo n del grafo se cumple g (n) = 0, nos encontramos ante una búsqueda
voraz.
Si para todo nodo n del grafo se cumple h (n) = 0, A* pasa a ser una búsqueda de coste
uniforme no informada.
Para garantizar la optimización del algoritmo, la función h (n) debe ser heurística admisible,
esto es, que no sobrestime el coste real de alcanzar el nodo objetivo.
De no cumplirse dicha condición, el algoritmo pasa a denominarse simplemente A, y a pesar
de seguir siendo completo, no se asegura que el resultado obtenido sea el camino de coste
mínimo. Asimismo, si garantizamos que h (n) es consistente (o monótona), es decir, que
para cualquier nodo n y cualquiera de sus sucesores, el coste estimado de alcanzar el
objetivo desde n no es mayor que el de alcanzar el sucesor más el coste de alcanzar el
objetivo desde el sucesor.
C. Definición de términos básicos
1. Algoritmo:
[8] Conjunto de reglas que, aplicada sistemáticamente a unos datos de entrada apropiados,
resuelven un problema en un número finito de pasos elementales. Los algoritmos tienen una
entrada (Input) y una salida (Output), entre ambas están las instrucciones.
2. Base de datos:
[9] Define como colección de datos relacionados, organizados, estructurados y
almacenados de manera persistente. La persistencia es la característica de los datos que nos
permite recuperarlos en el futuro, es decir que un dato es persistente si lo podemos
almacenar a través del tiempo.
3. Sistema de posicionamiento global (GPS):
[10] Es un sistema de navegación global basada en 29 satélites, 24 activos y 5 de backup.
Originalmente fue desarrollado sólo con fines militares y con el correr de los años se
extendió su uso hacia aplicaciones civiles.
 [Link] de términos básicos
Nodo: Punto geográfico con coordenadas específicas que se almacena en la base de datos.
Ruta o camino: Subconjunto de nodos y tramos de un grafo en el que cada nodo pertenece a
exactamente dos tramos excepto dos nodos, los nodos de inicio y fin que pertenecen a un tramo.
Ruta óptima: Ruta o camino que toma el menor tiempo para trasladarse de un punto a otro.
Algoritmo: un algoritmo es un conjunto prescrito de instrucciones o reglas bien definidas,
ordenadas y finitas que permiten llevar a cabo una actividad mediante pasos sucesivos que no
generen dudas a quien deba hacer dicha actividad.
[Link] METODOLOGICO
5.1 NIVEL DE INVESTIGACION
explicativo
5.2 TIPO DE INVESTIGACION
explicativo
5.3 DISEÑO DE LA INVESTIGACION
Aplicada tecnológica
 III. Referencias

[1] F. Diebold, The Journal of Business, 1989.

[2] J. A. Taquía Valdivia, «Optimización de rutas en una empresa de recojo de residuos sólidos,»
LIma, 2013.
[3] I. J. Ruiz Liza y W. M. Vidal Urdiales, «MODELO DE OPTIMIZACIÓN DEL SISTEMA
DE RECOJO DE RESIDUOS SÓLIDOS EN EL DISTRITO DE REQUE PARA MEJORAR
LA EFICIENCIA DE OPERACIONES,» Chiclayo, 2016.
[4] E. M. Aguayo Moreno, «Desarrollo de un sistema de localización de rutas óptimas entre dos
puntos geográficos,» Quito, 2008.
[5] F. Y. Sanabria Quiñonez, «Estudio comparativo de algoritmos basados en metaheurísticas
aplicados a la solución del problema de ruteo de vehículos con capacidad limitada,»
Guayaquil, 2018.
[6] J. E. Rivera Alejo, «Análisis comparativo entre el algoritmo cuántico de GROVER y un
algoritmo GRASP, aplicados a la búsqueda de individuos óptimos en la población inicial de
un algoritmo genético,» Lima, 2010.
[7] J. A. Reza Vargas, «Optimización de rutas de distribución de una empresa productora de
jugos,» Atizapán de Zaragoza, 2016.
[8] S. C. Fanjul, «En realidad, ¿qué es exactamente un algoritmo?,» Retina el país, 22 03 2018.
[9] M. C. F. M. Cruz, «Bases de Datos,» Mexico, 2019.
[10] J. M. V. Castaño, «Fundamentos del Sistema GPS,» La Revista Negocios de Seguridad, nº
100-104, p. 2.
ANEXOS