Determinación de ruta más corta desde la Sede Principal

hasta la Sede Doctor Angélico de la Universidad Santo

Tomás por medio del Algoritmo de Djikstra y
planteamiento del modelo matemático

Natalia Marcela Martínez Olarte1, Laura Camila Navarrete Cárdenas 2, Oscar Mauricio Gelves Alarcón3

Resumen

El algoritmo de la ruta más corta permite optimizar distancias entre puntos con el fin de reducir
costos y tiempos de movilización, de tal forma que el desplazamiento se vuelva más eficiente.
La Universidad Santo Tomás de Bogotá tiene cuatro sedes, tres de ellas ubicadas en Chapinero
y la otra en el norte de la ciudad, por tal motivo gran parte de la población académica debe
desplazarse entre sedes para realizar sus actividades, siendo principales los recorridos que se
realizan entre las sedes de Chapinero ya que debido a su cercanía permite que el recorrido se
realice caminando. El objetivo de esta investigación fue encontrar la ruta más corta desde la
Sede Principal de la Universidad Santo Tomás, ubicada en la Carrera 9 #51-11, hasta el Edificio
Doctor Angélico, ubicado en la Carrera 9 #72-90, teniendo en cuenta que la salida de la Sede
Principal está ubicada sobre la carrera 13. Para la solución de la ruta se utilizó el Algoritmo de
Dijkstra, y se planteó el modelo matemático. Finalmente se comparó la distancia obtenida con
la distancia que arroja Google Maps y se determinó que la distancia se aproxima de forma
significativa.

Palabras Claves

Djikstra, Programación lineal, Ruta más corta,

TÍTULO DEL ARTÍCULO EN INGLÉS

Calculation of the shortest route from the Headquarters to the Angelic

Doctor Headquarters of the Santo Tomás University through the
Dijkstra Algorithm and approach to the Linear Programming model

ABSTRACT

The algorithm of the shortest route allows to optimize distances between points in order to reduce costs and
mobilization times, so that the displacement becomes more efficient. The Santo Tomás University of Bogotá
has four locations, three of them located in Chapinero and the other in the north of the city, for this reason a
large part of the academic population must travel between venues to carry out their activities, the main routes
being They take place between the offices of Chapinero since, due to its proximity, it allows the route to be
made on foot. The objective of this research was to find the shortest route from the Main Headquarters of the
Santo Tomás University, located in Carrera 9 # 51-11, to the Doctor Angélico Building, located in Carrera 9 #
72-90, taking into account that the exit of the Main Headquarters is located on carrera 13. For the solution of
the route the Dijkstra Algorithm was used, and the mathematical model was raised. Finally, the distance
obtained was compared with the distance that Google Maps throws and it was determined that the distance
is significantly approximated.

Keywords: Djikstra, Linear Programming, Shortest Route

Introducción

El traslado de un punto a otro en una ciudad como Bogotá es importante para realizar análisis
e investigaciones, ya que es una ciudad en la cual la mayoría de las calles no cuenta con
distancias estándar, y hay muchos caminos posibles de un origen a un destino. Encontrar la ruta
más corta de un punto a otro puede generar una disminución de tiempos e incluso de costos
importantes para una persona y/o empresa. En el caso de la universidad Santo Tomás Sede
Bogotá, muchos de los estudiantes y profesores se tienen que trasladar entre las cuatro sedes,
principalmente a través de las tres que están en la localidad de Chapinero. Uno de las
herramientas para determinar la ruta más corta entre dos puntos es el Algoritmo de Dijkstra,
esta herramienta permitió determinar la mínima distancia que se debe recorrer entre la Sede
Principal y el Edificio Doctor Angélico caminando. También se hace el planteamiento del
modelo matemático para la programación lineal del problema.

Marco teórico

Teoría de Redes

Las redes están expresadas gráficamente, está compuestas por una cantidad específica de nodos
unidos por arcos ya sean en una dirección, o bidireccionales. La red busca representar un flujo
entre nodos, que pasa por entre los arcos. En este caso también es utilizado el concepto de nodo
origen o nodo fuente que, se refiere a el nodo donde empiezan a salir los ramales, su orientación
siempre es hacia fuera, por otra aparte está el nodo destino al cual llegan todos lo ramales, es
decir todos los arcos van hacia él, por otra parte, hay nodos de transición los cuales tiene
entradas y salidas de flujo. [1]

Algoritmo de la ruta más corta

Es un modelo mediante el cual se genera una red que permite establecer rutas posibles y
determinar aquella que represente menor distancia desde un nodo origen hasta un nodo destino.
En este algoritmo solo un nodo está denominado como el origen, y otro diferente denominado
como el destino, y en medio de estos hay distintos nodos de transición que permiten establecer
la ruta óptima para el recorrido. [2]
1
Universidad Santo Tomás, Sede Bogotá. Contacto: nataliamartinezo@[Link].
2
Universidad Santo Tomás, Sede Bogotá. Contacto: lauranavarrete@[Link]
Algoritmo de Dijkstra

“[…] es un modelo que se clasifica dentro de los algoritmos de búsqueda. Su objetivo, es

determinar la ruta más corta, desde el nodo origen, hasta cualquier nodo de la red. Su
metodología se basa en iteraciones, de manera tal que en la práctica, su desarrollo se dificulta
a medida que el tamaño de la red aumenta, dejándolo en clara desventaja, frente a métodos de
optimización basados en programación matemática.” [3]

Algunas características de este algoritmo es que trabaja por etapas, es decir que a medida que
avanza la red va ofreciendo resultados óptimos sin tener en cuenta que pasará a futuro, por ello
es posible que la mejor solución esté cambiando constantemente a medida que se avanza en el
desarrollo del algoritmo. [4]

Programación Lineal

“La programación lineal es un conjunto de técnicas racionales de análisis y de resolución de

problemas que tiene por objeto ayudar a los responsables en las decisiones sobre asuntos en los
que interviene un gran número de variables.” [5] El objetivo de la programación lineal es
resolver problemas, logrando minimizar o maximizar un resultado encontrando soluciones
viables de acuerdo a restricciones dadas.

Programación lineal ruta más corta

Xij =
1 Tomar el arco desde el origen i=1, 2, 3…m al destino j=2,3,4…n
0
Dij= distancia del arco i=1…m hasta j=1…n

𝑛
MinZ = ∑𝑚
𝑖=1 ∑𝑗=1 𝑑𝑖𝑗𝑋𝑖𝑗

S.a
𝑛

∑ 𝑋𝑖𝑗 = 1
𝑗=1
𝑚

∑ 𝑋𝑛𝑗 = 1
𝑖=𝑛

Equilibrio

Total Flujo de entrada del =Total flujo de salida del nodo

Xij es 1 ó 0

3
Metodología

Inicialmente se dibujó la red de grafos del recorrido, tomando cada esquina como nodo, y cada
calle o carrera que une las esquinas como arcos. Se tuvo en cuenta que la salida de la sede
principal está ubicada sobre la carrera 13, por tanto, se limitó la red entre la Calle 51 y la Calle
73, y entre la Carrera 7 y la Carrera 13. Con base en ello, se toman arcos sobre la carrrera 13
hasta que llega a la calle 67, ya que en este punto la carrera se une a la Avenida Caracas,
saliéndose de tal forma de los límites establecidos, en este punto se tuvieron en cuenta otras
carreras que estaban dentro de los límites para continuar con el recorrido. Finalizada la red con
nodos y arcos, se tomaron las distancias con la información proporcionada en Google Maps.

En el Anexo 1 se encuentra la red con distancias.

Imagen 1. Red entre las dos sedes (Ver en Anexo 1).

Seguido a esto se aplicó el modelo de Dijkstra sobre la red, y se determinó la ruta más corta
entre las sedes.

4
En el Anexo 1 se encuentra la red con la aplicación del Algoritmo Dijkstra.

Imagen 2. Aplicación de algoritmo de Dijkstra (Ver en Anexo 1)

Resultados

Algoritmo de Dijkstra

Por medio del algoritmo de Dijkstra se determinó que la ruta más corta entre la sede Principal
y el Edificio Doctor Angélico tiene una distancia de 2445 metros, alcanzando dicha distancia
en la iteración número 26 de la red. La ruta está dada de la siguiente forma: nodo 1 ubicado en
la carrera 13 con calle 51 (Sede Principal), nodo 2 ubicado en la carrera 13 con calle 52, nodo
5 ubicado en la carrera 13 con calle 52ª, nodo 7 ubicado en la carrera 13 con calle 53, nodo 11
ubicado en la carrera 13 con calle 54, nodo 15 ubicado en la carrera 13 con calle 55, nodo 24
ubicado en la carrera 13 con calle 57, nodo 28 ubicado en la carrera 13 con calle 58 Bis, nodo
30 ubicado en la carrera 13 con calle 59, nodo 36 ubicado en la carrera 13 con calle 60, nodo
37 ubicado en la calle 60 con carrera 9ª, nodo 42 ubicado en la carrera 9ª con calle 61, nodo 47
ubicado en la 9ª con calle 62, nodo 54 ubicado en la carrera 9ª con calle 63, nodo 64 ubicado
en la carrera 9ª con calle 64, nodo 70 ubicado en la carrera 9 con calle 65, nodo 77 ubicado en
la carrera 9 con calle 66, nodo 86 ubicado en la carrera 9 con calle 67, nodo 90 ubicado en la
carrera 9 con calle 67ª, nodo 94 ubicado en la carrera 9 con calle 69, nodo 100 ubicado en la

5
carrera 9 con calle 69ª, nodo 103 ubicado en la carrera 9 con calle 69ª bis, nodo 107 ubicado
en la carrera 9 con calle 70, nodo 115 ubicado en la carrera 9 con calle 70ª, nodo 118 ubicado
en la carrera 9 con calle 71, nodo 121 ubicado en la carrera 9 con calle 72, y finalmente el nodo
126 que está ubicado en la carrera 9 con calle 72 – 90 (Edificio Doctor Angélico).

En total el recorrido tiene un total de 26 iteraciones, recorriendo en total una distancia de 2445
metros.

Programación lineal – Modelo matemático

Xij  1 Es escoger arco origen i= 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41,
42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64,
65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87,
88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107,
108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124,
125 al destino j= 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45,
46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68,
69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91,
92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110,
111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126.
0

Ecuación objetivo

MinZ = 100X12 + 140X11.5 + 87X1.51.8 + 90X1.53 + 87X1.81.5 + 83X1.84+ 55X25 + 160X23 +

160X32 + 50X36 + 87X34 + 90X31.5 + 87X43 + 130X410 + 83X41.8 + 55X52 + 160X56 + 57X57 +
50X63 +160X65 + 63X69 + 57X75 + 110X78 + 74X711 + 110X87 + 70X89 + 61X812 + 63X96 +
70X98 + 75X910 + 61X913 + 130X104 + 75X109 + 53X1014 + 74X117 + 120X1112 + 150X1115 +
61X128 + 120X1211 + 72X1213 + 70X1216 + 61X139 + 72X1312 + 66X1314 + 53X1410 + 66X1413 +
160X1421 + 150X1511 + 120X1518 + 200X1524 + 70X1612 + 56X1617 + 83X1618 + 56X1716 + 78X1720
+ 83X1816 + 120X1815 + 35X1819 + 35X1918 + 62X1920 + 72X1922 + 78X2017 + 62X2019 + 81X2021
+ 160X2114 + 81X2120 + 78X2123 + 72X2219 + 83X2223 + 130X2226 + 78X2321 + 83X2322 +130X2327
+ 200X2415 + 98X2425 + 110X2428 + 98X2524 + 110X2526 + 100X2529 + 110X2625 + 130X2622 +
87X2627 + 130X2723 + 87X2726 + 120X2733 + 110X2824 + 140X2829 + 110X2830 + 100X2925 +
140X2928 + 71X2931 + 110X3028 + 170X3031 + 96X3036 + 71X3129 + 170X3130 + 100X3132 + 58X3134
+ 100X3231 + 52X3233 + 61X3235 + 120X3327 + 52X3332 + 120X3339 + 58X3431 + 110X3435 +
55X3438 + 61X3532 + 1103534 + 96X3630 + 100X3637 + 120X3640 + 100X3736 + 110X3738 + 110X3742
+ 55X3834 + 110X3837 + 110X3839 + 110X3843 + 120X3933 + 110X3938 + 110X3944 + 120X4036 +
85X4041 + 89X4045 + 85X4140 + 54X4142 + 130X4146 + 110X4237 + 54X4241 + 120X4243 + 120X4247
+ 110X4338 + 120X4342 + 120X4344 + 130X4350 + 110X4439 + 120X4443 + 87X4451 + 89X4540 +
100X4546 + 83X4552 + 130X4641 + 100X4645 + 77X4647 + 120X4742 + 77X4746 + 78X4748 + 91X4754
+ 78X4847+ 36X4849 + 81X4855 + 36X4948 + 52X4950 + 70X4955 + 130X5043 + 52X5049 + 120X5051

6
+ 99X5056 + 87X5144 + 120X5150 + 130X5157 + 83X5245 + 60X5258 + 72X5253 + 72X5352 + 150X5354
+ 59X5359 + 91X5447 + 150X5453 + 82X5455 + 61X5464 + 81X5548 + 70X5549 + 82X5554 + 43X5556
+ 49X5560 + 99X5650 + 43X5655 + 100X5657 + 75X5660 + 130X5751 + 100X5756 + 77X5766 + 60X5852
+ 79X5859 + 91X5861 + 59X5953 + 79X5958 + 120X5963 + 56X5962 + 49X6055 + 75X6056 + 31X6065
+ 91X6158 + 97X6162 + 97X6167 + 56X6259 + 97X6261 + 100X6263 + 100X6268 + 120X6359 +
100X6362 + 87X6364 + 96X6369 + 61X6454 + 87X6463 + 57X6465 + 91X6470 + 31X6560 + 57X6564 +
130X6566 + 89X6571 + 77X6657 + 130X6665 + 100X6672 + 97X6761 + 120X6768 + 110X6773 +
100X6862 + 120X6867 + 110X6869 + 99X6874 + 96X6963 + 110X6968 + 99X6970 + 120X6975 + 91X7064
+ 99X7069 + 67X7071 + 130X7077 + 89X7165 + 67X7170 + 120X7172 + 75X7179 + 100X7266 +
120X7271 + 70X7280 + 110X7367 + 150X7374 + 110X7381 + 99X7468 + 150X7473 + 110X7475 +
93X7482 + 120X7569 + 110X7574 + 51X7576 + 80X7584 + 51X7675 + 50X7677 + 78X7685 + 130X7770
+ 50X7776 + 80X7778 + 74X7786 + 80X7877 + 53X7879 + 67X7887 + 75X7971 + 53X7978 + 120X7980
+ 70X8072 + 120X8079 + 120X8088 + 110X8173 + 180X8182 + 93X8274 + 180X8281 + 75X8283 +
160X8291 + 75X8382 + 41X8384 + 120X8392 + 80X8475 + 41X8483 + 50X8485 + 62X8489 + 78X8576
+ 50X8584 + 58X8586 + 74X8677 + 58X8685 + 76X8687 + 68X8690 + 67X8778 + 76X8786 + 120X8788
+ 120X8880 + 120X8887 + 110X8897 + 62X8984 + 110X8990 + 67X8993 + 68X9086 + 110X9089 +
53X9094 + 160X9182 + 71X9192 + 110X91104 + 120X9283 + 71X9291 + 54X9293 + 62X9298 + 67X9389
+ 54X9392 + 110X9394 + 53X9490 + 110X9493 + 75X9495 + 73X94100 + 75X9594 + 73X9596 +
180X95108 + 73X9695 + 83X9697 + 180X96109 + 110X9788 + 83X9796 + 190X97110 + 62X9892 +
47X98101 + 59X98105 + 110X99100 + 11X99101 + 73X10094 + 110X10099 + 26X100103 + 11X10199 +
47X10198 + 12X101102 + 12X102101 + 110X102103 + 26X103100 + 110X103102 + 67X103107 + 110X10491
+ 81X104105 + 33X104111 + 59X10598 + 81X105104 + 8X105106 + 8X106105 + 160X106107 + 12X106112
+ 67X107103 + 160X107106 + 76X107108 + 96X107115 + 180X10895 + 73X108109 + 76X108107 +
180X10996 + 73X109108 + 86X109110 + 190X11097 + 86X110109 + 100X110116 + 33X111104 + 85X111112
+ 70X111113 + 12X112106 + 85X112111 + 71X112114 + 70X113111 + 83X113114 + 83X113117 + 71X114112
+ 83X114113 + 150X114115 + 96X115107 + 150X115114 + 240X115116 + 74X115118 + 100X116110 +
240X116115 + 190116122 + 83X117113 + 240X117118 + 120X117119 + 74X118115 + 240X118117 +
99X118121 + 120X119117 + 150X119120 + 150X119123 + 150X120119 + 110X120121 + 150X120124 +
99X121118 + 110X121120 + 200X121122 + 160X121126 + 190X122116 + 200X122121 + 150X122125 +
150X123119 + 140X123124 + 150X124120 + 140X124123 + 100X124126 + 150X125122 + 180X125126.

Sujeto a:

Restricciones de origen y destino

1. X11.5 + X12 = 1
2. X121-126 + X124-126 + X125-126 = 1

Restricción binaria

3. Xij es 1 o 0

7
Restricciones de nodos de transición

4. Nodo 1.5= X11.5+X31.5+X1.81.5=X1.53+X1.51.8

5. Nodo 1.8= X1.51.8+X41.8=X1.81.5+X1.84
6. Nodo 2= X12 + X32 + X52 = X25 + X23
7. Nodo 3= X23+X63+X43=X32+X36+X34
8. Nodo 4= X34+X104=X43+X410
9. Nodo 5= X25+X75+X65=X52+X56+X57
10. Nodo 6= X36+X56+X96=X63+X65+X69
11. Nodo 7= X57+X87+X117=X75+X78+X711
12. Nodo 8= X78+X98+X128=X87+X89+X812
13. Nodo 9= X89+X69+X109+X139=X98+X96+X910+X913
14. Nodo 10= X410+X910+X1410=X104+X109+X1014
15. Nodo 11= X711+X1211+X1511=X117+X1112+X1115
16. Nodo 12= X812+X1112+X1312+X1612=X128+X1211+X1213+X1216
17. Nodo 13= X1213+X913+X1413=X1312+X139+X1314
18. Nodo 14= X1014+X1314+X2114=X1410+X1413+X1421
19. Nodo 15= X1115+X1815+X2415=X1511+X1518+X1524
20. Nodo 16= X1216+X1716+X1816=X1612+X1617+X1618
21. Nodo 17= X1617+X2017=X1716+X1720
22. Nodo 18= X1518+X1618+X1918=X1815+X1816+X1819
23. Nodo 19= X1819+X2019+X2219=X1918+X1920+X1922
24. Nodo 20= X1720+X1920+X2120=X2017+X2019+X2021
25. Nodo 21= X2021+X1421+X2321=X2114+X2120+X2123
26. Nodo 22= X1922+X2322+X2622=X2219+X2223+X2226
27. Nodo 23= X2123+X2223+X2723=X2321+X2322+X2327
28. Nodo 24= X1524+X2524+X2824=X2415+X2425+X2428
29. Nodo 25= X2425+X2925+X2625=X2524+X2529+X2526
30. Nodo 26= X2526+X2226+X2726=X2625+X2622+X2627
31. Nodo 27= X2627+X2327+X3327=X2726+X2723+X2733
32. Nodo 28= X2428+X2928+X3028=X2824+X2829+X2830
33. Nodo 29= X2529+X2829+X3129=X2925+X2928+X2931
34. Nodo 30= X2830+X3130+X3630=X3028+X3031+X3036
35. Nodo 31= X2931+X3031+X3431+X3231=X3129+X3130+X3134+X3132
36. Nodo 32= X3132+X3332+X3532=X3231+X3233+X3235
37. Nodo 33= X2733+X3233+X3933=X3327+X3332+X3339
38. Nodo 34= X3134+X3534+X3834=X3431+X3435+X3438
39. Nodo 35= X3435+X3235=X3534+X3532
40. Nodo 36= X3036+X4036+X3736=X3630+X3640+X3637
41. Nodo 37= X3637+X4237+X3837=X3736+X3742+X3738
42. Nodo 38= X3438+X3738+X4338+X3938=X3834+X3837+X3843+X3839
43. Nodo 39= X3339+X3839+X4439=X3933+X3938+X3944
44. Nodo 40= X3640+X4140+X4540=X4036+X4041+X4045
45. Nodo 41= X4041+X4641+X4241=X4140+X4146+X4142

8
46. Nodo 42= X4142+X4742+X4342=X4241+X4247+X4243
47. Nodo 43= X4243+X5043+X4443=X4342+X4350+X4344
48. Nodo 44= X4344+X5144=X4443+X4451
49. Nodo 45= X4045+X4645+X5245=X4540+X4546+X4552
50. Nodo 46= X4546+X4146+X4746=X4645+X4641+X4647
51. Nodo 47= X4247+X4647+X4847+X5447=X4742+X4746+X4748+X4754
52. Nodo 48= X4748+X4948+X5548=X4847+X4849+X4855
53. Nodo 49= X4849+X5549+X5049=X4948+X4955+X4950
54. Nodo 50= X4950+X4350+X5150+X5650=X5049+X5043+X5051+X5056
55. Nodo 51= X4451+X5051+X5751=X5144+X5150+X5157
56. Nodo 52= X4552+X5352+X5852=X5245+X5253+X5258
57. Nodo 53= X5253+X5953+X5453=X5352+X5359+X5354
58. Nodo 54= X5354+X4754+X6454+X5554=X5453+X5447+X5464+X5455
59. Nodo 55= X4855+X4955+X5455+ X5655 + X6055=X5548+X5549+X5554+X5556+ X5560
60. Nodo 56= X5056+X5556+X6056+X5756=X5650+X5655+X5660+X5657
61. Nodo 57= X5157+X5657+X6657=X5751+X5756+X5766
62. Nodo 58= X5258+X5958+X6158=X5852+X5859+X5861
63. Nodo 59= X5359+X5859+X6259+X6359=X5953+X5958+X5962+X5963
64. Nodo 60= X5560+X6560+X5660=X6055+X6065+X6056
65. Nodo 61= X5861+X6261+X6761=X6158+X6162+X6167
66. Nodo 62= X5962+X6162+X6362+X6862=X6259+X6261+X6263+X6268
67. Nodo 63= X5963+X6263+X6963+X6463=X6359+X6362+X6369+X6364
68. Nodo 64= X6364+X5464+X6564+X7064=X6463+X6454+X6465+X6470
69. Nodo 65= X6065+X6465+X6665+X7165=X6560+X6564+X6566+X6571
70. Nodo 66= X5766+X6566+X7266=X6657+X6665+X6672
71. Nodo 67= X6167+X6867+X7367=X6761+X6768+X6773
72. Nodo 68= X6268+X6768+X6968+X7468=X6862+X6867+X6869+X6874
73. Nodo 69= X6369+X6869+X7569+X7069=X6963+X6968+X6975+X6970
74. Nodo 70= X6470+X6970+X7170+X7770=X7064+X7069+X7071+X7077
75. Nodo 71= X6571+X7071+X7271+X7971=X7165+X7170+X7172+X7179
76. Nodo 72= X6672+X7172+X8072=X7266+X7271+X7280
77. Nodo 73= X6773+X7473+X8173=X7367+X7374+X7381
78. Nodo 74= X6874+X7374+X7574+X8274=X7468+X7473+X7475+X7482
79. Nodo 75= X6975+X7475+X8475+X7675=X7569+X7574+X7584+X7576
80. Nodo 76= X7576+X7776+X8576=X7675+X7677+X7685
81. Nodo 77= X7677+X7077+X8677+X7877=X7776+X7770+X7786+X7778
82. Nodo 78= X7978+X7778+X8778=X7879+X7877+X7887
83. Nodo 79= X7179+X7879+X8079=X7971+X7978+X7980
84. Nodo 80= X7280+X7980+X8880=X8072+X8079+X8088
85. Nodo 81= X7381+X8281=X8173+X8182
86. Nodo 82= X7482+X8182+X9182+X8382=X8274+X8281+X8291+X8283
87. Nodo 83= X8283+X9283+X8483=X8382+X8392+X8384
88. Nodo 84= X8384+X7584+X8584+X8984=X8483+X8475+X8485+X8489
89. Nodo 85= X8485+X7685+X8685=X8584+X8576+X8586

9
90. Nodo 86= X8586+X7786+X8786+X9086=X8685+X8677+X8687+X8690
91. Nodo 87= X7887+X8687+X8887=X8778+X8786+X8788
92. Nodo 88= X8088+X8788+X9788=X8880+X8887+X8897
93. Nodo 89= X8489+X9089+X9389=X8984+X8990+X8993
94. Nodo 90= X8690+X8990+X9490=X9086+X9089+X9094
95. Nodo 91= X8291+X9291+X10491=X9182+X9192+X91104
96. Nodo 92= X9192+X8392+X9892+X9392=X9291+X9283+X9298+X9293
97. Nodo 93= X8993+X9293+X9493=X9389+X9392+X9394
98. Nodo 94= X9094+X9394+X10094+X9594=X9490+X9493+X94100+X9495
99. Nodo 95= X9495+X9695+X10895=X9594+X9596+X95108
100. Nodo 96= X9596+X9796+X10996=X9695+X9697+X96109
101. Nodo 97= X8897+X9697+X11097=X9788+X9796+X97110
102. Nodo 98= X9298+X10198+X10598=X9892+X98101+X98105
103. Nodo 99= X10199+X10099=X99100+X99101
104. Nodo 100= X94100+X99100+X103100=X10094+X10099+X100103
105. Nodo 101= X99101+X98101+X102101=X10199+X10198+X101102
106. Nodo 102= X101102+X103102=X102101+X102103
107. Nodo 103= X100103+X102103+X107103=X103100+X103102+X103107
108. Nodo 104= X91104 +X105104 + X111104 = X10491 + X104105 + X104111
109. Nodo 105= X98105 + X104105 + X106105 = X10598+ X105104 + X105106
110. Nodo 106= X105106 + X107106 + X112106 = X106105+ X106107 + X106112
111. Nodo 107= X103107 + X106107 + X108107 + X115107 = X107103 + X107106 + X107108 +
X107115
112. Nodo 108= X95108 + X107108 + X109108 = X10895 + X108107+ X108109
113. Nodo 109= X96109 + X108109 + X110109 = X10996 + X109108 + X109110
114. Nodo 110= X97110 + X109110 + X116110 = X11097 + X110109 + X110116
115. Nodo 111= X104111 + X112111 + X113111 = X111104 + X111112 + X111113
116. Nodo 112= X106112 + X111112 + X114112 = X112106 + X112111 + X112114
117. Nodo 113= X111113 + X114113 + X117113 = X113111 + X113114 + X113117
118. Nodo 114= X112114 + X113114 + X115114 = X114112 + X114113 + X114115
119. Nodo 115= X107115 + X114115 + X116115 +X118115 = X115107 + X115114 + X115116 +
X115118
120. Nodo 116= X110116 + X115116 + X122116 = X116110 + X116115 + X116122
121. Nodo 117= X113117 + X118117 + X119117 = X117113 + X117118 + X117119
122. Nodo 118= X115118 + X117118 + X121118 = X118115 + X118117 + X118121
123. Nodo 119= X117119 + X120119 + X123119 = X119117 + X119120 + X119123
124. Nodo 120= X119120 + X121120 + X124120 = X120119 + X120121 + X120124
125. Nodo 121= X118121 + X120121 + X122121 = X121118 + X12120 + X121122 + X121126
126. Nodo 122= X116122 + X121122 + X125122 = X122116 + X122121 + X122125
127. Nodo 123= X119123 + X124123 = X123119 + X123124
128. Nodo 124= X120124 + X123124 = X124120 + X124123 + X124126
129. Nodo 125= X122125 = X125122 + X125126

10
Análisis de resultados

El algoritmo de Dijkstra fue la herramienta utilizada para determinar la distancia mínima que
se recorre en la ruta más corta, que en este caso se obtuvo de 2445 metros. Por otra parte, no
se pudo realizar la aplicación de la programación lineal en solver debido a la capacidad del
sistema, ya que el modelo consta de 403 variables y 129 restricciones.
Utilizando la herramienta Google Maps, se hizo la comparación de la ruta más corta y de la
distancia obtenida:

Imagen 3. Ruta propuesta por Google Maps.

11
 Imagen 4. Parte 1 de ruta propuesta por Google Maps.

Imagen 5. Parte 2 de la ruta propuesta por Google Maps.

12
Como se puede observar en las imágenes la ruta propuesta por Google Maps, la ruta es la
misma que se determinó con el algoritmo de Dijkstra, consistiendo en tomar la carrera 13
desde la calle 51 hasta la calle 60, en este punto girar y tomar la carrera 9ª, continuar por esta
carrera desde la calle 60 hasta la calle 64, y desde este punto continuar por la carrera 9 hasta
llegar al destino.

Imagen 6. Distancia por Google Maps.

La distancia que muestra la plataforma de Google Maps para el recorrido es de 2.5 km, en el
algoritmo desarrollado se determinó que la distancia es de 2.445 km, es decir que se presenta
un error porcentual de 2.2%, la distancia determinada por medio del algoritmo es 2.2%
menos que la distancia que determina Google Maps.

13
Conclusiones

 Se determinó que la ruta más corta entre la Sede Principal y el Edificio Doctor Angélico
de la Universidad Santo Tomás (Bogotá) recorre una distancia total de 2.445 km, siendo
similar en un 97.8% a la distancia que se obtiene de Google Maps.
 La ruta que se debe recorrer para utilizar la ruta más corta entre las dos sedes está dada
por la siguiente consecución de nodos: 1-2-5-7-11-15-24-28-30-36-37-42-47-54-64-
70-77-86-90-94-100-103-107-115-118-121-126, estableciendo así un total de 26
iteraciones.
 El error porcentual entre la distancia obtenida por medio del Algoritmo de Dijkstra y la
distancia de Google Maps es del 2.2%, es decir 55 metros, por ello se concluye que la
aplicación del algoritmo se acerca en gran proporción al resultado guía, dicho error
puede deberse a la calibración que hace el sistema de Google Maps para aproximar
distancias, y/o al error del factor humano al ajustar las distancias sobre la red.
 El modelo matemático se planteó con base en 403 variables representadas por los arcos
y nodos, y con 129 restricciones, debido a la limitación de programas disponibles para
resolver la programación lineal teniendo en cuenta la capacidad necesaria, en esta
investigación no fue posible resolver el modelo para comparar con el resultado del
algoritmo de Dijkstra, se establece como punto de partida para futuras investigaciones.

14
Referencias Bibliográficas

[1] INGENIERÍA INDUSTRIAL ONLINE, «INGENIERÍA INDUSTRIAL ONLINE,»

TEORÍA DE REDES, [En línea]. Available:
[Link]
industrial/investigaci%C3%B3n-de-operaciones/teor%C3%ADa-de-redes/. [Último
acceso: 19 Octubre 2019].
[2] [Link],
«[Link],» [En línea]. Available:
[Link]
industrial/investigacion-de-operaciones/algoritmo-de-la-ruta-mas-corta/. [Último acceso:
19 10 2019].
[3] [Link],
«[Link],» [En línea]. Available:
[Link]
industrial/investigacion-de-operaciones/algoritmo-de-dijkstra/. [Último acceso: 19 10
2019].
[4] EcuRed, «EcuRed,» [En línea]. Available: [Link]
[Último acceso: 19 10 2019].
[5] M. Z. Cesar, «Gestiopolis,» Programación lineal en la investigación de operaciones, 29
Octubre 2013. [En línea]. Available: [Link]
en-la-investigacion-de-operaciones/. [Último acceso: 19 Octubre 2019].

15