El presente trabajo tiene como objetivo construir una red que permita calcular las distancias existentes entre los 30 muncipios del departamento de cordoba con la finalidad de minizar la distancia total.
para esto inplementamos un mapa en rstudio utilizando la libreria leaflet como se puede observar a continuacion:
#cargar librerias library(igraph)
Attaching package: 'igraph'
The following objects are masked from 'package:stats':
decompose, spectrum
The following object is masked from 'package:base':
union
para llegar a este mapa lo que se hizo fue que se creo un dataframe donde se guardaron los vectores
municipio: contien el nombre de los municipios
latitud: contiene las coordenadas de latitud de los municipios
longitud: contiene las cordenadas de longitud de los municipios
luego se crea el objeto mapa interactivo llamado “map” de la libreria leaflet, luego se crean las capas, se establece la vista del mapa con las cordenadas de longitud y latitud del punto central del mapa, y el nivel de zoom inicial para finalmente agregar los marcadores al mapa los cueles seran nuestros municipios
Calculo de distancia euclidina
para esto se utliza una funcion personalizada que calcula la distancia euclidiana entre dos puntos en un espacio bidimensional. Los parámetros de entrada son lat1, lon1, lat2, y lon2, que representan las coordenadas de dos puntos en latitud y longitud. L a formula para calcular la distancia euclidiana es:
$$\sqrt{\sum_{i=1}^n(A_i-B_i)^2}$$
Cálculo de las distancias entre todas las ubicaciones
Se crea una matriz llamada “distancias” inicializada con valores NA y dimensionada según la cantidad de municipios. Luego, se utiliza un bucle “For” para calcular las distancias entre todas las ubicaciones mediante la función “d_eu” que evalúa las coordenadas de latitud y longitud de cada par de municipios y almacena los resultados en la matriz “distancias”
luego se visualiza la matrix como podemos observar acontinuacion
# Función para calcular la distancia euclidianad_eu <-function(lat1, lon1, lat2, lon2) { dist <-sqrt((lat1 - lat2)^2+ (lon1 - lon2)^2)return(dist)}# Calcular las distancias entre todas las ubicacionesdistancias <-matrix(NA, nrow =nrow(dat), ncol =nrow(dat))rownames(distancias) <- dat$Municipiocolnames(distancias) <- dat$Municipiofor (i in1:nrow(dat)) {for (j in1:nrow(dat)) { distancias[i, j] <-d_eu(dat$Latitud[i], dat$Longitud[i], dat$Latitud[j], dat$Longitud[j]) }}# Ver la matriz de distanciasprint(distancias)
Ayapel Buenavista Canalete Cereté Chimá
Ayapel 0.0000000 0.3536350 1.1896496 0.87054705 0.96762386
Buenavista 0.3536350 0.0000000 0.9368649 0.73285189 0.93718446
Canalete 1.1896496 0.9368649 0.0000000 0.44806438 0.70670633
Cereté 0.8705471 0.7328519 0.4480644 0.00000000 0.31301848
Chimá 0.9676239 0.9371845 0.7067063 0.31301848 0.00000000
Chinú 0.8389750 0.8847808 0.8777668 0.43943609 0.21608059
Ciénaga de Oro 0.7384020 0.6657137 0.6195040 0.17673636 0.27462037
Cotorra 0.9718748 0.8707957 0.5142660 0.15417179 0.19296239
La Apartada 0.3301650 0.2262726 1.1579762 0.95382327 1.13769974
Los Córdobas 1.3458404 1.1006562 0.1645975 0.55708815 0.76848666
Momil 1.0754309 1.0417438 0.7266618 0.38241300 0.10825190
Montelíbano 0.4272712 0.2438237 1.1392514 0.97389470 1.17978096
Montería 0.8655964 0.6681402 0.3509277 0.15396084 0.46694059
Moñitos 1.3587870 1.2100264 0.4748491 0.49021868 0.50915600
Planeta Rica 0.4558056 0.2140380 0.7471876 0.51936516 0.73954341
Pueblo Nuevo 0.4054995 0.2773045 0.7857341 0.48606161 0.66151287
Puerto Escondido 1.2643002 1.0601602 0.2233424 0.41965767 0.58895895
Puerto Libertador 0.6805734 0.3872158 1.0629281 1.01006187 1.26621818
Purísima 0.9649903 1.0108594 0.9176165 0.50315361 0.21245159
Sahagún 0.7321397 0.7233067 0.7423683 0.29434146 0.23548617
San Andrés de Sotavento 1.0362834 0.9622450 0.5963425 0.26248456 0.13056693
San Antero 1.2278755 1.1837170 0.7577338 0.49055774 0.26025330
San Bernardo del Viento 1.3194991 1.2241308 0.6355753 0.49351782 0.38309599
San Carlos 0.7386341 0.6124914 0.5336828 0.13196843 0.36023813
San José de Uré 0.6604954 0.4432784 1.2206556 1.13311151 1.36925813
San Pelayo 0.9649510 0.8299003 0.4249059 0.09780026 0.28670656
Tierralta 0.5955363 0.2419417 0.8035621 0.72240992 0.98591821
Tuchín 0.9664909 0.9660843 0.7892777 0.38668347 0.08276037
Valencia 0.9942783 0.6527644 0.5256006 0.70357778 1.01607657
Santa Cruz de Lorica 1.1417743 1.0639174 0.6128262 0.34859158 0.20647991
Chinú Ciénaga de Oro Cotorra La Apartada
Ayapel 0.8389750 0.7384020 0.97187476 0.3301650
Buenavista 0.8847808 0.6657137 0.87079570 0.2262726
Canalete 0.8777668 0.6195040 0.51426603 1.1579762
Cereté 0.4394361 0.1767364 0.15417179 0.9538233
Chimá 0.2160806 0.2746204 0.19296239 1.1376997
Chinú 0.0000000 0.3081006 0.37618385 1.0595607
Ciénaga de Oro 0.3081006 0.0000000 0.23409282 0.8724919
Cotorra 0.3761838 0.2340928 0.00000000 1.0870893
La Apartada 1.0595607 0.8724919 1.08708933 0.0000000
Los Córdobas 0.9604151 0.7337059 0.58479385 1.3223038
Momil 0.2935398 0.3765671 0.23697656 1.2444424
Montelíbano 1.1173900 0.9092146 1.11387807 0.1000270
Montería 0.5819553 0.2875664 0.29731912 0.8942185
Moñitos 0.7252299 0.6294053 0.39931277 1.4347248
Planeta Rica 0.7151733 0.4651048 0.65979595 0.4383783
Pueblo Nuevo 0.6113913 0.3932748 0.61047662 0.4793533
Puerto Escondido 0.7891096 0.5931924 0.41379052 1.2861889
Puerto Libertador 1.2477529 0.9922305 1.16176371 0.3690640
Purísima 0.1283877 0.4043933 0.40338976 1.1877775
Sahagún 0.1842440 0.1325559 0.29319058 0.9132359
San Andrés de Sotavento 0.3444319 0.3037946 0.10952686 1.1739671
San Antero 0.4349156 0.5185445 0.33640645 1.3904569
San Bernardo del Viento 0.5901932 0.5827922 0.35535335 1.4419894
San Carlos 0.4195346 0.1116174 0.25833458 0.8298691
San José de Uré 1.3277931 1.0949143 1.28126873 0.3303345
San Pelayo 0.4549547 0.2476701 0.09563195 1.0513819
Tierralta 0.9855552 0.7140112 0.87465757 0.3975995
Tuchín 0.1600061 0.3189975 0.27520161 1.1581077
Valencia 1.1029445 0.7948918 0.84590370 0.8250130
Santa Cruz de Lorica 0.4200571 0.4089880 0.19645954 1.2773906
Los Córdobas Momil Montelíbano Montería Moñitos
Ayapel 1.3458404 1.0754309 0.4272712 0.8655964 1.3587870
Buenavista 1.1006562 1.0417438 0.2438237 0.6681402 1.2100264
Canalete 0.1645975 0.7266618 1.1392514 0.3509277 0.4748491
Cereté 0.5570882 0.3824130 0.9738947 0.1539608 0.4902187
Chimá 0.7684867 0.1082519 1.1797810 0.4669406 0.5091560
Chinú 0.9604151 0.2935398 1.1173900 0.5819553 0.7252299
Ciénaga de Oro 0.7337059 0.3765671 0.9092146 0.2875664 0.6294053
Cotorra 0.5847938 0.2369766 1.1138781 0.2973191 0.3993128
La Apartada 1.3223038 1.2444424 0.1000270 0.8942185 1.4347248
Los Córdobas 0.0000000 0.7656423 1.3038062 0.4903468 0.4173880
Momil 0.7656423 0.0000000 1.2848659 0.5324375 0.4543011
Montelíbano 1.3038062 1.2848659 0.0000000 0.8995023 1.4451276
Montería 0.4903468 0.5324375 0.8995023 0.0000000 0.5467102
Moñitos 0.4173880 0.4543011 1.4451276 0.5467102 0.0000000
Planeta Rica 0.9083502 0.8411995 0.4547216 0.4571540 0.9964399
Pueblo Nuevo 0.9406155 0.7671305 0.5184359 0.4615141 0.9753769
Puerto Escondido 0.1889993 0.5789463 1.2819850 0.4007884 0.2525554
Puerto Libertador 1.2226658 1.3638775 0.2714316 0.9004897 1.4387628
Purísima 0.9805310 0.2410163 1.2448107 0.6544695 0.6950242
Sahagún 0.8464793 0.3433730 0.9622150 0.4190681 0.6882714
San Andrés de Sotavento 0.6451319 0.1330959 1.2060200 0.4066459 0.3829557
San Antero 0.7638051 0.1527759 1.4274275 0.6289625 0.3908310
San Bernardo del Viento 0.6092052 0.2980776 1.4663705 0.5998329 0.2058515
San Carlos 0.6616990 0.4521137 0.8555505 0.1874776 0.6218059
San José de Uré 1.3819885 1.4709240 0.2359529 1.0354469 1.5795701
San Pelayo 0.5088326 0.3309091 1.0703283 0.2120831 0.3940995
Tierralta 0.9670780 1.0810195 0.3494478 0.6133892 1.1548284
Tuchín 0.8505573 0.1336659 1.2062434 0.5402825 0.5765505
Valencia 0.6655670 1.0823523 0.7686087 0.5505363 0.9791518
Santa Cruz de Lorica 0.6343120 0.1437989 1.3074854 0.4800586 0.3114773
Planeta Rica Pueblo Nuevo Puerto Escondido
Ayapel 0.4558056 0.4054995 1.2643002
Buenavista 0.2140380 0.2773045 1.0601602
Canalete 0.7471876 0.7857341 0.2233424
Cereté 0.5193652 0.4860616 0.4196577
Chimá 0.7395434 0.6615129 0.5889590
Chinú 0.7151733 0.6113913 0.7891096
Ciénaga de Oro 0.4651048 0.3932748 0.5931924
Cotorra 0.6597959 0.6104766 0.4137905
La Apartada 0.4383783 0.4793533 1.2861889
Los Córdobas 0.9083502 0.9406155 0.1889993
Momil 0.8411995 0.7671305 0.5789463
Montelíbano 0.4547216 0.5184359 1.2819850
Montería 0.4571540 0.4615141 0.4007884
Moñitos 0.9964399 0.9753769 0.2525554
Planeta Rica 0.0000000 0.1234604 0.8536904
Pueblo Nuevo 0.1234604 0.0000000 0.8617800
Puerto Escondido 0.8536904 0.8617800 0.0000000
Puerto Libertador 0.5336565 0.6389115 1.2404394
Purísima 0.8362614 0.7360285 0.7994681
Sahagún 0.5408773 0.4461862 0.6928343
San Andrés de Sotavento 0.7543726 0.6947927 0.4623101
San Antero 0.9789847 0.9116387 0.5753256
San Bernardo del Viento 1.0116592 0.9658275 0.4278571
San Carlos 0.4017151 0.3567467 0.5412893
San José de Uré 0.6298169 0.7177590 1.3907199
San Pelayo 0.6161529 0.5836000 0.3511306
Tierralta 0.2770137 0.3974645 0.9657644
Tuchín 0.7765680 0.6887978 0.6699072
Valencia 0.5663216 0.6745206 0.7397381
Santa Cruz de Lorica 0.8543950 0.7986100 0.4456717
Puerto Libertador Purísima Sahagún
Ayapel 0.6805734 0.9649903 0.7321397
Buenavista 0.3872158 1.0108594 0.7233067
Canalete 1.0629281 0.9176165 0.7423683
Cereté 1.0100619 0.5031536 0.2943415
Chimá 1.2662182 0.2124516 0.2354862
Chinú 1.2477529 0.1283877 0.1842440
Ciénaga de Oro 0.9922305 0.4043933 0.1325559
Cotorra 1.1617637 0.4033898 0.2931906
La Apartada 0.3690640 1.1877775 0.9132359
Los Córdobas 1.2226658 0.9805310 0.8464793
Momil 1.3638775 0.2410163 0.3433730
Montelíbano 0.2714316 1.2448107 0.9622150
Montería 0.9004897 0.6544695 0.4190681
Moñitos 1.4387628 0.6950242 0.6882714
Planeta Rica 0.5336565 0.8362614 0.5408773
Pueblo Nuevo 0.6389115 0.7360285 0.4461862
Puerto Escondido 1.2404394 0.7994681 0.6928343
Puerto Libertador 0.0000000 1.3697831 1.0745141
Purísima 1.3697831 0.0000000 0.2966603
Sahagún 1.0745141 0.2966603 0.0000000
San Andrés de Sotavento 1.2647939 0.3373573 0.3194242
San Antero 1.4936305 0.3548677 0.4957358
San Bernardo del Viento 1.4974565 0.5328963 0.6022084
San Carlos 0.9130475 0.5118755 0.2428283
San José de Uré 0.1673801 1.4534236 1.1633524
San Pelayo 1.0990426 0.4943631 0.3418695
Tierralta 0.2880724 1.1031055 0.8064469
Tuchín 1.3081466 0.1299860 0.2448718
Valencia 0.6036404 1.1927850 0.9224098
Santa Cruz de Lorica 1.3580096 0.3837000 0.4210907
San Andrés de Sotavento San Antero
Ayapel 1.0362834 1.2278755
Buenavista 0.9622450 1.1837170
Canalete 0.5963425 0.7577338
Cereté 0.2624846 0.4905577
Chimá 0.1305669 0.2602533
Chinú 0.3444319 0.4349156
Ciénaga de Oro 0.3037946 0.5185445
Cotorra 0.1095269 0.3364064
La Apartada 1.1739671 1.3904569
Los Córdobas 0.6451319 0.7638051
Momil 0.1330959 0.1527759
Montelíbano 1.2060200 1.4274275
Montería 0.4066459 0.6289625
Moñitos 0.3829557 0.3908310
Planeta Rica 0.7543726 0.9789847
Pueblo Nuevo 0.6947927 0.9116387
Puerto Escondido 0.4623101 0.5753256
Puerto Libertador 1.2647939 1.4936305
Purísima 0.3373573 0.3548677
Sahagún 0.3194242 0.4957358
San Andrés de Sotavento 0.0000000 0.2293500
San Antero 0.2293500 0.0000000
San Bernardo del Viento 0.2845118 0.1946446
San Carlos 0.3540059 0.5813766
San José de Uré 1.3803617 1.6070577
San Pelayo 0.1997309 0.4171664
Tierralta 0.9786478 1.2078273
Tuchín 0.2084288 0.2771971
Valencia 0.9541428 1.1685948
Santa Cruz de Lorica 0.1056528 0.1525898
San Bernardo del Viento San Carlos San José de Uré
Ayapel 1.3194991 0.7386341 0.6604954
Buenavista 1.2241308 0.6124914 0.4432784
Canalete 0.6355753 0.5336828 1.2206556
Cereté 0.4935178 0.1319684 1.1331115
Chimá 0.3830960 0.3602381 1.3692581
Chinú 0.5901932 0.4195346 1.3277931
Ciénaga de Oro 0.5827922 0.1116174 1.0949143
Cotorra 0.3553534 0.2583346 1.2812687
La Apartada 1.4419894 0.8298691 0.3303345
Los Córdobas 0.6092052 0.6616990 1.3819885
Momil 0.2980776 0.4521137 1.4709240
Montelíbano 1.4663705 0.8555505 0.2359529
Montería 0.5998329 0.1874776 1.0354469
Moñitos 0.2058515 0.6218059 1.5795701
Planeta Rica 1.0116592 0.4017151 0.6298169
Pueblo Nuevo 0.9658275 0.3567467 0.7177590
Puerto Escondido 0.4278571 0.5412893 1.3907199
Puerto Libertador 1.4974565 0.9130475 0.1673801
Purísima 0.5328963 0.5118755 1.4534236
Sahagún 0.6022084 0.2428283 1.1633524
San Andrés de Sotavento 0.2845118 0.3540059 1.3803617
San Antero 0.1946446 0.5813766 1.6070577
San Bernardo del Viento 0.0000000 0.6122365 1.6253529
San Carlos 0.6122365 0.0000000 1.0263602
San José de Uré 1.6253529 1.0263602 0.0000000
San Pelayo 0.3996519 0.2279890 1.2257018
Tierralta 1.2094378 0.6290143 0.4258075
Tuchín 0.4312255 0.4167894 1.4037882
Valencia 1.1012037 0.6837733 0.7708800
Santa Cruz de Lorica 0.1811521 0.4527509 1.4775507
San Pelayo Tierralta Tuchín Valencia
Ayapel 0.96495098 0.5955363 0.96649093 0.9942783
Buenavista 0.82990034 0.2419417 0.96608426 0.6527644
Canalete 0.42490587 0.8035621 0.78927771 0.5256006
Cereté 0.09780026 0.7224099 0.38668347 0.7035778
Chimá 0.28670656 0.9859182 0.08276037 1.0160766
Chinú 0.45495473 0.9855552 0.16000608 1.1029445
Ciénaga de Oro 0.24767011 0.7140112 0.31899749 0.7948918
Cotorra 0.09563195 0.8746576 0.27520161 0.8459037
La Apartada 1.05138188 0.3975995 1.15810772 0.8250130
Los Córdobas 0.50883264 0.9670780 0.85055734 0.6655670
Momil 0.33090910 1.0810195 0.13366593 1.0823523
Montelíbano 1.07032826 0.3494478 1.20624338 0.7686087
Montería 0.21208312 0.6133892 0.54028249 0.5505363
Moñitos 0.39409945 1.1548284 0.57655049 0.9791518
Planeta Rica 0.61615287 0.2770137 0.77656800 0.5663216
Pueblo Nuevo 0.58360003 0.3974645 0.68879779 0.6745206
Puerto Escondido 0.35113056 0.9657644 0.66990723 0.7397381
Puerto Libertador 1.09904262 0.2880724 1.30814662 0.6036404
Purísima 0.49436312 1.1031055 0.12998596 1.1927850
Sahagún 0.34186945 0.8064469 0.24487179 0.9224098
San Andrés de Sotavento 0.19973095 0.9786478 0.20842881 0.9541428
San Antero 0.41716639 1.2078273 0.27719708 1.1685948
San Bernardo del Viento 0.39965190 1.2094378 0.43122554 1.1012037
San Carlos 0.22798902 0.6290143 0.41678938 0.6837733
San José de Uré 1.22570184 0.4258075 1.40378820 0.7708800
San Pelayo 0.00000000 0.8109803 0.36799092 0.7550424
Tierralta 0.81098027 0.0000000 1.03245169 0.4278504
Tuchín 0.36799092 1.0324517 0.00000000 1.0863228
Valencia 0.75504238 0.4278504 1.08632276 0.0000000
Santa Cruz de Lorica 0.26803918 1.0706802 0.26633936 1.0163720
Santa Cruz de Lorica
Ayapel 1.1417743
Buenavista 1.0639174
Canalete 0.6128262
Cereté 0.3485916
Chimá 0.2064799
Chinú 0.4200571
Ciénaga de Oro 0.4089880
Cotorra 0.1964595
La Apartada 1.2773906
Los Córdobas 0.6343120
Momil 0.1437989
Montelíbano 1.3074854
Montería 0.4800586
Moñitos 0.3114773
Planeta Rica 0.8543950
Pueblo Nuevo 0.7986100
Puerto Escondido 0.4456717
Puerto Libertador 1.3580096
Purísima 0.3837000
Sahagún 0.4210907
San Andrés de Sotavento 0.1056528
San Antero 0.1525898
San Bernardo del Viento 0.1811521
San Carlos 0.4527509
San José de Uré 1.4775507
San Pelayo 0.2680392
Tierralta 1.0706802
Tuchín 0.2663394
Valencia 1.0163720
Santa Cruz de Lorica 0.0000000
Grafo
A continuation se construye el grafo que representa el problema utilizando la libreria igraph donde las distancias se utilizan como pesos de las aristas
#red en igrap# grafo ponderado utilizando las distancias como pesos de las aristasgrafo <-graph.adjacency(as.matrix(distancias), weighted =TRUE, mode ="undirected")plot(grafo)
Árbol de expansión
Para terminar se encuentra el arbol de expansion minimo mediante el algoritmo de Prim com se observa en el siguiente codigo
MTS:es un subconjunto del grafo original que conecta todos los municipios de la manera más eficiente posible en términos de distancia total.
# Encontrar el MST utilizando el algoritmo de PrimMst_prim <-minimum.spanning.tree(grafo, algorithm ="prim")plot(Mst_prim, layout=layout.auto)
