Equa ion Chap e 1 Sec ion 1
T abajo Fin de Más e
Más e en Ingenie ía Indus ial
Diseño y op imización de una dis ibución
coo dinada de suminis os en colegios públicos de
Se illa
Au o : Miguel No oa Con e as
Tu o : Luis Miguel Rome o Pé ez
Dp o. Ingenie ía y Ciencia de los Ma e iales
y del T anspo e
Escuela Técnica Supe io de Ingenie ía
Uni e sidad de Se illa
Se illa, 2018
iii
T abajo Fin de Más e
Más e en Ingenie ía Indus ial
Diseño y op imización de una dis ibución
coo dinada de suminis os en colegios públicos de
Se illa
Au o :
Miguel No oa Con e as
Tu o :
Luis Miguel Rome o Pé ez
Á ea de conocimien o: Ingenie ía e In aes uc u a de los T anspo es
Escuela Técnica Supe io de Ingenie ía
Uni e sidad de Se illa
Se illa, 2018
T abajo Fin de Más e : Diseño y op imización de una dis ibución coo dinada de suminis os en
colegios públicos de Se illa
Au o :
Miguel No oa Con e as
Tu o :
Luis Miguel Rome o Pé ez
El ibunal nomb ado pa a juzga el P oyec o a iba indicado, compues o po los siguien es miemb os:
P esiden e:
Vocales:
Sec e a io:
Acue dan o o ga le la cali icación de:
Se illa, 2018
El Sec e a io del T ibunal

ii
A mi amilia po su apoyo.
A mi u o Luis Miguel Rome o
po su colabo ación.
ix
Resumen
Es an amplio el abanico de posibilidades, de si uaciones logís icas y de dis ibución de me cancías, y
cada una de es as posibilidades an dis in as en e sí, que los p oblemas de op imización de u a como el del
p oblema del iajan e, son muy impo an es en la ac ualidad. Es al el aho o y la e iciencia que se pueden
alcanza con es os mé odos, que con apenas in e sión se puede consegui unos ni eles de compe i i idad muy
al os, algo que es muy impo an e en es e sec o .
Es e p oyec o a a de diseña y op imiza la u a de epa o de ma e ial escola a odos los cen os
educa i os localizados en la ciudad de Se illa. Como se explica á du an e el p oyec o, la idea es que desde un
mismo cen o de dis ibución se epa a odo el ma e ial necesa io pa a los cen os educa i os públicos de
Se illa. De es a mane a se disminui á los kilóme os eco idos y el núme o de anspo es que an a los cen os
educa i os, consiguiendo ambién un meno á ico y una mayo segu idad ce ca de los cen os educa i os. Pa a
ello, se ha in es igado y es udiado los p oblemas de op imización de u as, y cuales son la mejo o ma de
esolución.
A lo la go del p oyec o, se p esen a á una base eó ica sob e los p oblemas de op imización de u as y
posibles mé odos de esolución. Además, se aplica án algunos de los mé odos explicados, cuyos esul ados se án
analizados y compa ados. Se inaliza á con la explicación y el análisis de la mejo u a encon ada, y con posibles
mejo as que aplica .
Figu a 18. Relación mapa de calo con los g upos (“GoogleMaps,” n.d.). 65
Figu a 19. Localización de los cen os del g upo 1. (“GoogleMaps,” n.d.) 73
Figu a 20. Localización de los cen os del g upo 2. (“GoogleMaps,” n.d.) 76
Figu a 21. Localización de los cen os del g upo 3. (“GoogleMaps,” n.d.) 80
Figu a 22. Localización de los cen os del g upo 4. (“GoogleMaps,” n.d.) 83

x ii
No ación
TSP
ACO
VRP
ADN
APP
P oblema del agen e iaje o
Colonia de ho migas
P oblema de en u amien o de ehículos
Ácido desoxi ibonucleico
Aplicación
19
INTRODUCCIÓN
20
20
1 INTRODUCCIÓN
Obje i o del p oyec o
En el p esen e p oyec o se a a diseña y op imiza la dis ibución del ma e ial escola en odos los cen os
educa i os públicos de la ciudad de Se illa. Pa a lle a a cabo el diseño de la dis ibución, se an a implemen a
dis in os algo i mos en el p og ama Ma lab. Es os algo i mos p opo ciona án di e en es u as, las cuales
e leja án el o den de epa o en los cen os educa i os. Se implemen a án a ios algo i mos pa a pode compa a
sus soluciones, y analiza cuál de es as es la solución idónea a implan a en la dis ibución.
Es impo an e des aca que, en es a idea la dis ibución del ma e ial escola se lle a á a cabo po un
dis ibuido único, a di e encia de como se es á ealizando ac ualmen e con a ios dis ibuido es, como se
comen a á a lo la go del p oyec o.
An eceden es del p oyec o
Ac ualmen e, es e epa o de ma e ial es ealizado po di e en es emp esas, y cada una de es as emp esas
a di e en es cen os educa i os. Es a o ma de dis ibución del ma e ial escola es muy ine icien e y se ob ienen
muchas consecuencias nega i as. Al con a cada cen o educa i o con di e en es emp esas de
ap o isionamien o, y dependiendo del ma e ial necesa io la dis ibución la ealiza una emp esa u o a, se o igina
un excesi o á ico de me cancías al ededo de los cen os educa i os.
Es a o ma de dis ibución no solo o igina un excesi o á ico, sino que p o oca o as consecuencias nada
deseables. El cos e y el consumo de combus ible de oda la dis ibución ambién son muy ele ados, debido al
g an núme o de kilóme os que ienen que ealiza el conjun o de las emp esas pa a comple a el epa o de odo
el ma e ial escola a odos los cen os educa i os. También p o oca si uaciones mejo ables como en el ámbi o
de la segu idad ial y del medio ambien e, donde al exis i an o á ico de me cancías se p oducen un mayo
iesgo de acciden e y unas ele adas emisiones de CO2 en el en o no de los cen os educa i os.
Es impo an e disminui ese excesi o á ico que exis e con la dis ibución ac ual. El excesi o á ico de
me cancías es un ema muy no able y de mucho deba e en la ac ualidad. La dis ibución de me cancías es el
p incipal culpable de la conges ión u bana y po lo an o de los pe juicios de es a. Son nume osas las medidas
que se es án omando a ni el eu opeo y nacional pa a in en a educi es e á ico. De en e los aspec os nega i os
que iene el excesi o á ico de me cancías en la ciudad se pueden des aca :
- Ambien al: Con ibución al e ec o in e nade o y a la exis encia de una mala calidad del ai e. Así
como excesi as si uaciones de in enso uido y ib aciones.
21
- Segu idad: Al a asa de acciden es po el excesi o á ico, y la sensación de pelig o al ci cula
pea ones y pequeños ehículos jun o a g andes camiones pesados.
- Cos es de ope ación: Al habe una g an conges ión del á ico, el iempo y el cos e des inado a la
dis ibución se inc emen a, lo que al inal epe cu e en el cos e inal de los p oduc os.
- Ope aciones u banas: Exis e g an can idad de ehículos des inados al anspo e de me cancías que
ienen que ca ga y desca ga en la ía pública, lo que disminuye el espacio de ci culación pa a
pea ones y pa a el es o de ehículos. Además, es e espacio de ci culación se e educido cuando los
ehículos se es acionan ilegalmen e pa a su ca ga y desca ga. En es e sen ido des aca que el á ico
de me cancías supone el 75% de las ope aciones de ca ga y desca ga, mien as que el 25% es an e
es pa a uso domés ico o pa a el sec o se icios.
En Muñuzu i,2003, se puede amplia la in o mación sob e los impac os nega i os de la conges ión del
á ico an o pa a la logís ica u bana de me cancías como pa a la sociedad. Así como se pueden obse a algunas
soluciones a es e p oblema como el uso del ca il bus, epa os noc u nos o epa os conjun os desde un mismo
cen o de dis ibución.
Toda es a p oblemá ica adquie e un alo oda ía más impo an e, si es as si uaciones se dan en el en o no
de los cen os educa i os, donde se debe ene especial cuidado po la p esencia de un g an núme o de niños
pequeños.
Pa a e i a es as si uaciones, en es e p oyec o se es udia la posibilidad de que un mismo dis ibuido se
enca gue de odo el ap o isionamien o de ma e ial escola que necesi an los cen os educa i os, es o p o oca á
una disminución del núme o de kilóme os y de ehículos des inados a dicha causa.
Con es a p opues a se disminui á dicho á ico y se aumen a á la segu idad al ededo de los cen os
educa i os de la ciudad. Además, se disminui á un cos e y un núme o impo an e de kilóme os eco idos. O o
aspec o impo an e que se mejo a á, se á la disminución de las emisiones de CO2 en el en o no de los cen os
educa i os de la ciudad debido al meno á ico.
La idea gene al es la de ecibi odo el ma e ial escola en un pun o de la ciudad de Se illa, y desde ese
pun o dis ibui lo a odos los cen os educa i os. Pa a que esa dis ibución sea lo más óp ima posible se han
diseñado las posibles u as que se pueden segui . En el capí ulo de esul ados expe imen ales se p esen a án las
dis in as u as y las elegidas como mejo es u as a implan a . La siguien e imagen puede esumi el cambio que
se a a es udia en es e p oyec o de pasa de una dis ibución indi idual a una dis ibución coo dinada.
Figu a 1. Dis ibución indi idual a la izquie da y dis ibución coo dinada a la de echa. (Jun a de Andalucía. Conseje ía de
Educación.)

INTRODUCCIÓN
22
22
Como bien se ha comen ado, el obje i o p incipal es implemen a la u a óp ima desde un cen o de
dis ibución, que comple en el epa o a odos los cen os educa i os públicos, pa a así disminui el núme o de
kilóme os y el núme o de anspo es. Pa a es o es necesa io hace un in en a io de odos los des inos, es deci ,
de odos los cen os educa i os a los que se en egan los bienes.
Con es a p opues a se eliminan las en egas indi iduales, lo que ocasiona 4 p incipales bene icios que se
pueden esumi en:
- Medio ambien e: Se disminuye las emisiones de CO2 an o en la ciudad como en el en o no de los
cen os educa i os.
- Segu idad del á ico: Al disminui el á ico de camiones, se aumen a á la segu idad del á ico en la
ce canía de los cen os educa i os.
- Ambien e de abajo: Con el diseño de las u as se aho a iempos de en ega, lo que aumen a la
compe i i idad y mejo a el clima de abajo. Además, se pueden ija los mismos días y ho as pa a la
en ega de la me cancía.
- Coo dinación municipal: Se pod á ealiza con mayo acilidad un in en a io del ma e ial escola .
Con una dis ibución coo dinada se puede lle a un mayo con ol del ma e ial que se necesi a en los
cen os educa i os. Además, con es e mé odo se pod á sol en a de mane a más e icien e y e icaz
cualquie con a iempo que ocu a en el epa o del ma e ial.
Es a idea de dis ibución coo dinada se ha implan ado en algunas egiones de Suecia, donde los esul ados
ue on imp esionan emen e buenos. Los da os que se ob u ie on as la implan ación de es a idea en esas
egiones hablan de una mejo a impo an e, an o en kilóme os eco idos como en emisiones de CO2.
- Kilóme os eco idos: Se aho ó de media 2.800 kilóme os en el anspo e de me cancías.
- En íos: Se disminuye on los en íos en un 62%.
- Emisiones de CO2: Se p odujo una g an disminución de emisiones de CO2, educiéndose en un 73%
con espec o al modelo an e io de dis ibución.
Viendo los esul ados que se ob u ie on en es e p oyec o sueco, se puede pensa que es una muy buena
medida a implan a en el modelo de dis ibución de ma e ial escola en los cen os educa i os públicos de Se illa.
23
2 FUNDAMENTOS TEÓRICOS
P oblema del agen e iaje o
2.1.1 In oducción al p oblema del agen e iaje o
A lo la go de odo es e p oyec o, se a a acome e el es udio y el análisis de la u a que debe segui el
epa o de ma e ial escola a odos los cen os educa i os de la ciudad de Se illa. El obje i o p incipal es
consegui que el iempo que se necesi e pa a lle a a cabo dicha u a sea el meno posible. Es impo an e
comen a que en el epa o de ma e ial escola se deben isi a odos los cen os educa i os, y no epe i el paso
po ningún cen o, ya que es o aumen a ía el iempo del epa o.
La de inición del obje i o de es e p oyec o, es muy simila a la de uno de los g andes p oblemas de la
op imización combina o ia como es el p oblema del iajan e. Debido a es a g an simili ud, en es e p oyec o se
a a es udia odo lo elacionado con el p oblema del iajan e, como sus ca ac e ís icas, ipos de p oblemas,
algo i mos de esolución, e c. Po ello se p e ende que, a a és del p oblema del iajan e se dé solución al
p oblema del epa o de ma e ial escola an es explicado.
En p ime luga , y an es de in oduci que es el p oblema del iajan e, es necesa io sabe que ipos de
p oblemas de u as exis en en la ac ualidad. Exis en dos g andes g upos de p oblemas de u as, los p oblemas
po é ices y los p oblemas po a cos.
El p ime o de ellos iene como obje i o isi a los é ices, es deci , isi a los nodos de un g a o, es os
nodos pueden se isi ados po un ehículo, TSP, o po a ios ehículos, VRP (Vehicle Rou ing P oblem).
El segundo g upo de p oblemas se cen a en pasa po las a is as de un g a o, en es e g upo se puede
encon a un ipo de p oblemas pa ecido al TSP, y es el CPP (Chinese Pos man P oblem). En es e, en ez de
eco e odos los nodos, se ienen que eco e odas las a is as una sola ez.
Po p o undiza un poco más en el mundo de los p oblemas po é ices, como es el caso del p oblema
que se a a a a en es e abajo, se pueden da dis in os ipos de p oblemas como los p esen ados a con inuación:
1. Max-TSP → Su obje i o es con a io al caso es udiado, es deci , se busca la u a con cos e máximo.
2. TSP con cuello de bo ella → Busca una u a, de al o ma que se minimice el mayo cos e de las a is as
que pe enecen a dicha u a.
3. TSP → El p oblema a ado en es e abajo, busca el mínimo cos e de una u a que isi a una ez odos los
nodos.
4. TSP gene alizado → Los nodos es án ag upados y el obje i o de es e p oblema es la búsqueda de una u a
de cos e mínimo que isi e una sola ez un nodo de cada g upo.
Fundamen os eó icos
24
24
El p oblema del agen e iaje o, o p oblema del iajan e, es comúnmen e conocido bajo las siglas TSP
(T a elling Salesman P oblem). El obje i o de es e p oblema es encon a la u a óp ima que debe ealiza el
agen e, pa iendo desde el o igen, eco iendo odos los pun os y ol iendo a dicho o igen. Es a u a óp ima debe
se la de meno dis ancia o meno iempo. Es a u a que con iene odos los nodos es conocida como ciclo
hamil oniano, cuyo nomb e es en hono a William Rowan Hamil on.
A p io i, pa ece que el p oblema es sencillo, pe o si se iene en cuen a el núme o de nodos, las dis ancias
o los iempos en e ellos y demás es icciones que se pueden inco po a , el p oblema adquie e una di icul ad
ele ada. Es deci , se es á an e un p oblema que no es di ícil de modela , pe o sí lo es de esol e .
En la ac ualidad, se u ilizan algo i mos que p opo cionan una solución ap oximada en un iempo
azonable. Un algo i mo que p opo ciona la solución exac a, es comp oba odas las posibles soluciones del
p oblema, pe o es o es in iable debido al iempo compu acional eque ido, ya que, el iempo necesa io pa a
encon a la solución aumen a de mane a exponencial a medida que aumen a el amaño del p oblema. Es deci ,
pa a un p oblema con n nodos, donde los iempos son simé icos ( iempo de A-B es el mismo que el iempo de
B-A) exis en (𝑛−1!) 2
⁄ u as posibles. Po ello es e ipo de p oblemas se enma ca den o de los p oblemas
NP-HARD, como se explica en Be nal e al, 2015.
Es e ipo de p oblema iene muchas aplicaciones que se explica án pos e io men e, pe o una de las
aplicaciones más impo an es es la logís ica y el anspo e de me cancías, debido a la al a compe i i idad que
ienen las emp esas del sec o . Po ello, se u ilizan nue as he amien as de ges ión, pa a así op imiza los ecu sos
y pode ob ene mayo es má genes de bene icio.
Una de es as nue as he amien as es la esolución de los p oblemas de op imización combina o ia, en e
los que se incluye el TSP, median e algo i mos o heu ís icas. Pa a su esolución es habi ual la ejecución de a ios
algo i mos y es a egias, pa a alo a sus soluciones y e cuál es la mejo a implemen a . Es deci , dependiendo
del iempo compu acional, de la calidad de la solución, de la simplicidad o del cumplimien o de las es icciones.
Figu a 2. Ejemplo u a TSP (López e al, 2014)
25
2.1.2 Fundamen os his ó icos
En es a sección se a a de alla como se ha ido o mulando el p oblema del iajan e desde su o igen, el
cual no es á del odo cla o, has a la ac ualidad. Pa a p o undiza más en el siguien e eco ido his ó ico, sob e el
p oceso de de inición del p oblema del iajan e y de las di e en es me odologías pa a su esolución, se puede
isi a mul i ud de e e encias bibliog á icas, como po ejemplo K. Menge , 1931; Dan zig e al, 1954; Gomo y,
1958; en e o as muchas.
El p ime g an a ance en es e campo, se debe g acias a la apa ición de los ci cui os hamil onianos,
nomb ados an e io men e en es e abajo. Aunque, an es de conoce es os ci cui os con es e nomb e, Eule y
Vande monde in es iga on es os ci cui os pa a da solución al p oblema del juego del sal o del caballo, ambos
p esen a on una solución a dicho p oblema, la de Leonha d Eule , de 1735, es á ecogida en Núñez Valdés e
al,2004 y la de Alexand e-Théophile Vande monde, en su a ículo “Rema ques sû des p oblèmes de si ua ion”
publicado en 1771 po la Academia Real de las Ciencias de Pa ís.
(Vande monde, 1771)
Ambos in es igado es a a on de encon a un ci cui o, el cual iene que simula el eco ido de un
caballo, que debe pasa una sola ez po cada uno de los 64 cuad ados del able o de ajed ez. Aunque, como se
ha dicho al p incipio el p ime g an a ance no ue el de es os dos in es igado es, ue la apa ición de los ci cui os
hamil onianos. En 1857 William Donald Hamil on desa olló un juego cuyo obje i o e a ob ene un ci cui o que
pase po las a is as de un dodecaed o, de mane a que se isi e cada una de las 20 esquinas de es e polied o una
sola ez, y en el que el pun o de pa ida sea ambién el pun o inal del eco ido. El nomb e de es e eco ido se
da en hono a Hamil on, pe o 2 años an es, el ma emá ico b i ánico Thomas Penyng on Ki kman ya plan eó el
mismo p oblema en un documen o llamado “dado un g a o de un polied o, ¿exis e un ciclo que pase una ez po cada é ice?”.
(Ki kman, 1855)
Figu a 3. Juego Icosaéd ico. (A anda e al, 2007)
Fundamen os eó icos
32
32
Es os campos pueden se algunos de los más no edosos y donde más se es á abajando el p oblema del
iajan e, pe o exis en muchas más aplicaciones en el en o no eal como la op imización de u as pa a el á ico
aé eo, pa a p og ama unas acaciones con dis in os si ios a isi a , pa a los se icios de eme gencia, e c. Es
impo an e comen a que, a la ho a de oma la decisión de una u a no solo debe con a la in o mación que nos
p opo cione en el TSP. Po ejemplo, en el caso de los se icios de eme gencias, o as a iables son más
impo an es.
Algo i mos de esolución
En es a sección se a p esen a y explica los algo i mos de esolución del p oblema del iajan e, no se
nomb a án odos, ya que, exis e una g an di e sidad de algo i mos y heu ís icas. De los p esen ados en es a
sección se eligie on algunos pa a la implemen ación de un código que esol ie a el p oblema.
Se debe des aca que, como ya se ha comen ado en secciones an e io es, el p oblema es NP-HARD, po
lo que el iempo necesa io pa a llega a la solución óp ima puede llega a se muy ine icien e. Po ello, con los
algo i mos que se desc iben, se in en a llega a una solución los más ce cana posible al óp imo.
En p ime luga , se pueden di e encia dos g andes g upos de algo i mos, aquellos que buscan una
solución que, de no se la solución óp ima, se puede sabe cuán o di ie e del óp imo. Y o o g an g upo que, se
ca ac e iza po se e icien e en iempo polinomial, aunque no se sabe cuán o di ie e la solución ob enida de la
óp ima. La mayo ía de los algo i mos p esen ados en es e p oyec o pe enecen a es e g an g upo.
Hay una mane a de ob ene la solución exac a pa a es e p oblema, pe o su iempo de esolución no es
nada e icien e. Se ía ob ene odas las posibles u as y pa a cada una de ellas calcula el iempo o al, la u a con
meno iempo se á la óp ima. Pe o es a o ma de esolución es o almen e in iable, po ejemplo, pa a un pequeño
p oblema de 10 ciudades, exis en 362.880 u as posibles.
2.2.1 Algo i mo del ecino más p óximo
También denominado, algo i mo codicioso o algo i mo o az. Quizás, a p io i, el algo i mo más ácil de
implemen a , y que no malmen e no p opo ciona la solución óp ima. Hay eces que sí p opo ciona una muy
buena solución del p oblema, dependiendo de la localización de los nodos y del amaño del p oblema. Es e
algo i mo ealiza los siguien es pasos:
1. Se inicia buscando el nodo más ce cano al nodo de inicio, cuando se encuen e dicho nodo, se añade a la
u a, quedando dicha u a p ime o con el nodo inicio, seguido del nodo más ce cano a es e.

33
2. Pa a es e úl imo nodo inco po ado a la u a, se busca el nodo más ce cano, excep uando los que ya es án
añadidos a la u a.
3. El algo i mo inaliza cuando se inco po an odos los nodos a la u a, en ese caso, se inco po a á al inal de
la u a el nodo inicial, ya que, la u a debe sali y debe inaliza en dicho nodo.
Una ez ob enida la u a, se puede calcula el iempo o al in e ido, sumando cada uno de los iempos de
i de un nodo a o o, en el o den que nos diga la solución ob enida.
2.2.2 Algo i mo de Ch is o ides
Algo i mo diseñado, como bien indica su nomb e, po el ma emá ico chip io a Nicos Ch is o ides, en
1976. Es e algo i mo se basa en o o, llamado el minimum spanning ee o á bol de expansión mínima,
básicamen e el algo i mo a a de encon a un á bol mínimo, y, una ez encon ado, se duplican sus amas y
aplicando algunas écnicas se puede llega a una muy buena solución del p oblema. Además, ambién u iliza el
concep o de g a o eule iano, el cual se ca ac e iza po se un g a o conexo donde los nodos ienen g ado pa .
Pa a en ende un poco más el algo i mo se p esen an los siguien es pasos:
1. Llega a un á bol de expansión mínima, es o es, una colección de n-1 amas que unan los n nodos sin
o ma ciclo.
2. Una ez se ob iene dicho á bol, se aplica un ma ching o empa ejamien o mínimo pa a odos los nodos
de g ado impa , es deci , se unen en e sí aquellas pa ejas de nodos que sean de g ado impa , donde el
núme o de amas que salen y en an al nodo es impa , de es a mane a se con ie e el nodo en pa .
3. Una ez e minado dicho p oceso, se ob end á un g a o eule iano, al cual se le aplica á la écnica de
sho cu s, la cual consis e en eco e el g a o y cuando se llegue a un nodo sin amas de salida o cuyas
amas de salida ya han sido explo ados, uni lo con el siguien e nodo del g a o que no ha sido isi ado.
En Ch is o ides, 1976, se puede e odo lo explicado en es e apa ado y se puede indaga con mucho más
de alle sob e el Algo i mo de Ch is o ides.
Pa a en ende es e algo i mo y modo de ejemplo se p esen an la siguien e imagen, en la que se puede e
en p ime luga un á bol de expansión mínima, seguido de un g a o eule iano y llegando a la u a inal median e
la aplicación de sho cu s.
Fundamen os eó icos
34
34
Figu a 5. Ejemplo del Algo i mo de Ch is o ides
2.2.3 Mé odo de B anch and Bound
En cas ellano, mé odo de ami icación y aco ación, es una e olución del mé odo de los planos de co es,
que se diseñó en 1954, como se ha mencionado en los undamen os his ó icos de es e p oyec o.
En é minos gene ales, consis e en c ea un á bol de soluciones, el p opio algo i mo de ec a si una ama
ya no puede se óp ima y la co a, es deci , no busca á más soluciones en esa ama. La e iciencia de es os
algo i mos depende mucho del núme o de nodos que enga el p oblema.
El algo i mo se basa en una écnica, llamada back acking, simila a la que se u iliza en los á boles de
expansión mínima, consis e en ol e a un nodo an e io pa a examina sus posibles descendien es. Y o o
c i e io muy impo an e pa a la aplicación de dicho algo i mo es la de poda aquella ama cuyo cos e ya no
pe mi e que sea óp ima, pa a así no pe de iempo in es igando sus descendien es. Cada hoja se á un
subp oblema, donde se decidi á si una ciudad conc e a en a á en la u a en dicha posición o no.
Pa a asimila el p oblema un poco mejo se p esen an los siguien es pasos, donde se obse a de o ma
más in ui i a la mane a de abaja del algo i mo:
1. La p ime a hoja se á el nodo inicial del p oblema.
2. A cada ila de la ma iz de cos o o iginal se le es a el meno alo que apa ezca en su ila,
35
pos e io men e a cada columna de es a ma iz que se ob iene se le ealiza el p oceso simila . Es deci ,
es simplemen e aplica el eo ema de la ma iz educida a la ma iz de cos es o iginal.
3. El cos e o al de la u a se á la suma de los alo es que se han es ado en las ilas y en las columnas.
Es e cos e se i á inc emen ando según a ance el algo i mo.
4. Una ez se iene la nue a ma iz de cos es, se elige alea o iamen e una casilla que enga alo ce o, y
de aquí sald án dos subp oblemas, uno eligiendo esa casilla como óp ima (po lo que se elimina á su
ila y su columna de la ma iz de cos e modi icada) y o o eligiendo esa casilla como no óp ima (en
cuyo caso hab á que elegi o o ce o de la ma iz y epe i es e p oceso)
5. Pa a cada é ice que se alcanza ealiza el p oceso del pun o 4, cuando se llegue a un é ice cuyo cos e
sea mayo del cos e o al ac ualizado, co a su p og esión y hace un back acking al é ice an e io
que no haya sido explo ado. También se ealiza á el back acking si el é ice ya no puede ene más
ami icación.
6. La u a óp ima se á la del subp oblema que enga un meno cos e.
Aho a sí se puede en ende mejo la di icul ad que iene es e algo i mo pa a p oblemas del iajan e con
un núme o ele ado de nodos a isi a . En la siguien e imagen se puede obse a el á bol al que se llega ía pa a
un ejemplo de p oblema de solo 4 nodos. Se puede ap ecia que pa a an solo 4 nodos hay un g an núme o de
subp oblemas.
Figu a 6. Ejemplo á bol de soluciones (Al ed, John, & Je ey, 1987)
Fundamen os eó icos
36
36
2.2.4 Clus e ing
Es e mé odo de esolución del p oblema del iajan e se basa en la ag upación de los nodos que se ienen
que isi a en el p oblema. Básicamen e a a de busca el óp imo de cada clús e , pa a así llega al óp imo del
p oblema. Pa a más in o mación sob e es a he amien a isi a Lapo e, 2002.
Es a écnica po sí sola, no llega a ninguna solución, debe de es a acompañada de algún algo i mo ex a,
es deci , cuando se aplica clus e ing el esul ado es una ag upación de los pun os a isi a , según unas a iables,
como dis ancia, iempo, cos e, e c. A es os g upos hay que aplica le una heu ís ica pa a ob ene el óp imo de
cada uno de ellos. Una en aja de es o, es que pe mi e hace el p oblema escalable, ya que dependiendo del
núme o de g upos y del amaño del p oblema, se puede esol e muchos p oblemas de poco amaño, en ez de
un p oblema de g an amaño.
Los pasos a segui pa a llega a una co ec a ag upación de los nodos se ían los p esen ados a
con inuación:
1. Es ablece el núme o de g upos que se desean ob ene , puede es ablece se de mane a alea o ia o según
un c i e io. Al núme o de g upos se llama á k, po ejemplo.
2. Selecciona k nodos, uno po cada núme o de g upos, que se u iliza án como cen oides de cada g upo.
Es os deben es a lo más alejado posibles unos de o os.
3. Pa a el es o de nodos, calcula la dis ancia a los cen oides y asigna al clús e cuyo cen oide sea el
más ce cano.
4. Cuando se asigna un nodo a un clús e , se ecalcula su cen oide.
5. Una ez se ienen odos los g upos, aplica alguna heu ís ica de esolución a cada uno de ellos.
6. Cuando se ob iene la u a de cada clús e , uni los g upos, se calcula la dis ancia en e los g upos y se
unen los más ce canos en e sí, uniéndose nodo inal de un g upo, con el nodo inicial de o o.
7. Se llega a la u a inal.
Pa a e g á icamen e como se esuel e el p oblema del iajan e, empleando una he amien a de
clus e ing se p esen an a con inuación es a imagen.
37
Figu a 7. Ejemplo de clus e ing, Anaya e al. (2012)
2.2.5 K-op
Es a heu ís ica, desa ollada po Lin-Ke nighan, necesi a de la aplicación an e io de o a heu ís ica, es
deci , K-op pe enece al g upo de heu ís icas de mejo as. A pa i de la solución de o o algo i mo, u iliza dicha
u a ob enida pa a aplica le mejo as locales e in en a mejo a dicha u a. En es e p oyec o se ha u ilizado en
conc e o la heu ís ica 2-op que, ue p opues a y desa ollada po C oes en 1958.
Es un algo i mo en el que in e iene demasiado el aza , ya que se eligen k nodos alea o iamen e pa a
in e cambia los y comp oba si el iempo de la u a es meno . El algo i mo se puede comp ende mejo con las
siguien es ins ucciones:
1. Ob ene una solución ac ible median e o a heu ís ica. En el caso de que la solución sea óp ima,
el algo i mo de mejo a no p opo ciona á ninguna solución mejo .
2. Elegi alea o iamen e k nodos de la u a, po ejemplo, se elige 2 nodos al aza .
3. Se cambia la posición en la u a de un nodo po la del o o.
4. El amo de u a que hay en e los dos nodos se in ie e.
5. Se ob iene una nue a u a, se comp ueba el iempo que se a da ía en eco e es a nue a u a.

Fundamen os eó icos
38
38
6. Si es e iempo es meno que el ob enido al p incipio, es e se á el mejo iempo encon ado y su
u a la mejo .
7. Los pasos del 2 al 6 se pueden ealiza de mane a i e a i a, es ableciendo una condición de pa ada
o un núme o máximo de i e aciones.
Se puede conclui diciendo que, puede se una buena heu ís ica pa a mejo a la solución ob enida po o o
mé odo, pe o quizás es demasiado alea o ia, po lo que depende demasiado del núme o de i e aciones.
2.2.6 Colonia de ho migas
Como bien indica su nomb e, es e algo i mo e leja la ida de las ho migas: las ho migas, en la búsqueda
de un obje i o donde i , azan p ime o algunos eco idos alea o ios; las ho migas que eg esan an es se án las
que alcancen el camino más co o, el es o de ho migas segui á el as o de e omonas que han dejado las
ho migas que han ido po ese camino co o. Cuan as más ho migas pasen po es e camino, mayo se á la
concen ación de e omonas. Mien as que las e omonas de o as u as menos ansi adas se i án e apo ando.
El algo i mo p esen ado aquí es un mé odo heu ís ico, que se ca ac e iza po segui un p oceso simila .
Se c ean una se ie de caminos alea o ios; aquellos caminos más co os end án un mayo as o de e omonas,
es deci , una mayo p obabilidad de se elegido de nue o, mien as que los más la gos end án una p obabilidad
casi nula. Una explicación más de allada del algo i mo puede encon a se en Chu a e al, 2015.
Es e algo i mo ue desa ollado po Ma co Do igo en 1999 como se ecoge en Do igo e al, 2004; con
es e mé odo p e endían halla la u a más co a saliendo de su ciudad na al, di igiéndose a o as ciudades sin
epe i ninguna, y ol e de nue o a la ciudad na al.
El algo i mo es á basado en p oceso i e a i o, en el que, en cada i e ación, cada ho miga a i icial ealiza
un camino; en el p oceso de búsqueda del camino po pa e de cada ho miga, se llega á a una ciudad u o a según
dos a iables de decisión:
• Ma iz heu ís ica: Ma iz que no se modi ica de una i e ación a o a, siemp e es cons an e, y es á
elacionada con el cos e de i de un nodo a o o.
• Ma iz as o de e omonas: Es a in o mación se ac ualiza i e ación a i e ación, ya que depende de
la concen ación de e omonas que enga cada camino, es deci , si un camino es eco ido po más
ho migas end á una p obabilidad mayo de que las siguien es ho migas ambién lo u ilicen, como
se puede ap ecia en la siguien e imagen.
39
Figu a 8. Ejemplo as o de e omona (Robles Alga ín, 2010)
Pa a conclui la explicación de es e algo i mo, se a a esquema iza los pasos p incipales del mé odo,
desde la inicialización de los pa áme os has a la solución inal.
1. Inicialización de los pa áme os pa a la ma iz heu ís ica y el as o de e omonas, así como el núme o
de ho migas a c ea y el núme o de i e aciones.
2. Mien as no se llegue al núme o de i e aciones o no se cumple una condición de pa ada, ealiza el
siguien e p oceso i e a i o.
3. Se c ean las ho migas, y según la decisión de la ho miga, que depende de la ma iz heu ís ica y el as o
de e omonas, i de ciudad en ciudad, sin epe i ciudad, has a llega al inal.
4. Comp oba el esul ado de odas las ho migas, ac ualiza las e omonas, pa a que los caminos más
co os engas más p obabilidad de se elegidos po las ho migas de la siguien e i e ación.
5. Realiza an as i e aciones has a las es ablecidas o has a que se cumpla una condición de pa ada.
6. Cuando se e mine el bucle, se ob end á la solución del algo i mo.
Fundamen os eó icos
40
40
2.2.7 Algo i mo gené ico
Uno de los algo i mos más u ilizados pa a esol e es e ipo de p oblemas de op imización, se basan en
la e olución biológica de las especies. Fue ideado en 1975 po John Holland como un algo i mo inno ado y
e oluciona io en el ámbi o de la in eligencia a i icial. A con inuación, se p esen a una b e e explicación de la
me odología; más de alles pueden encon a se en Holland, 1992.
De o ma gene al, es e algo i mo se puede explica como la c eación de una población de indi iduos, es a
población e oluciona á, c eándose nue os indi iduos que mejo a án a los an e io es. Es a e olución se
ca ac e iza po la mu ación y el c uce de indi iduos, y po se una heu ís ica p obabilís ica, es deci , a la
capacidad de mu ación y a la de c uce, se le asigna án una p obabilidad.
Pa a en ende mejo el algo i mo es necesa io conoce unos concep os undamen ales:
• Población: Conjun o de indi iduos que se c ean pa a da solución al p oblema, puede se una
población alea o ia o p esen a ya alguna u a alcanzada po o o algo i mo.
• Indi iduo: Posible solución del p oblema, en el caso del p oblema del iajan e, se ía una posible u a.
• Descendien es: Son aquellos indi iduos que ganan en un o neo que se ealiza en e los p opios
indi iduos an e io es, es deci los que ienen mejo unción obje i o.
• C uce: También denominado ecombinación, como su p opio nomb e indica, c uza los descendien es
en e sí, es deci , coge los mejo es indi iduos y los c uza po si se c ea un indi iduo mejo .
• Mu ación: Pa a un indi iduo elegido al aza , se elige un pun o a bi a io de la u a y se in e cambian
sus nodos p edeceso es po los pos e io es.
• E olución: T as ealiza los p ocesos de c uce y mu ación, los indi iduos más ue es, es deci , los
mejo es, sob e i i án y segui án en el p oceso.
Conociendo es os é minos, se a a p ocede a de alla los pasos que sigue el algo i mo gené ico en el
p oceso de esolución del p oblema del iajan e:
1. C ea una población de indi iduos de mane a alea o ia.
41
2. Pa a cada indi iduo de la población, se calcula el iempo de sus u as.
3. Realiza el en en amien o en e los indi iduos, gene ando unos indi iduos ganado es, los de meno
iempo de u a.
4. Pa a es os ganado es, c ea nue os indi iduos, median e la ecombinación en e ellos.
5. Aplica la mu ación a un indi iduo y e si mejo a y puede e oluciona a o o mejo .
6. Ve los iempos de odos es os indi iduos que se han c eado en los pasos 4 y 5, y si algún indi iduo
iene un iempo de u a meno que el mínimo de odos los indi iduos an e io es, es ablece como mejo
iempo y mejo indi iduo.
7. Repe i los pasos del 2 al 6, has a llega a una condición de pa ada o al núme o de i e aciones máximo.
Figu a 9. Algo i mo gené ico (Bonelli & Beglia do, 2016)
Apa e de es os pasos, es impo an e es ablece una se ie de pa áme os an es de inicia el algo i mo, como
son la p obabilidad de mu ación, la p obabilidad de c uce, el amaño de la población, la condición de pa ada del
bucle o el núme o máximo de i e aciones.
Algunas des en ajas de es e algo i mo pod ía se la al a complejidad del mé odo, que puede depende
demasiado de los pa áme os elegidos y que pa a el diseño del algo i mo se necesi a conocimien o y expe iencia
en es e campo. O o pun o nega i o del algo i mo es que, pa a un núme o ele ado de nodos, el p oblema no
con e ge en un iempo e icien e, o con e ge a una solución lejana del óp imo, es o úl imo suele pasa al llega
a un óp imo local.
Los algo i mos y las heu ís icas que se han explicado en es a sección son algunos de los muchos mé odos
que exis en pa a esol e el p oblema del iajan e, exis en o os como búsqueda abú (Glo e & Laguna, 1997),
ecocido simulado (Ki kpa ick, Gela , & Vecchi, 1983), op imización po enjamb e de pa ículas (Kennedy &
Ebe ha , 1995), e c.
Caso de es udio
48
48
147
Ins i u o de Educación Secunda ia
Mu illo
148
Ins i u o de Educación Secunda ia
Ne ión
149
Ins i u o de Educación Secunda ia
Pablo Picasso
150
Ins i u o de Educación Secunda ia
Pino Mon ano
151
Ins i u o de Educación Secunda ia
Polígono Su
152
Ins i u o de Educación Secunda ia
Poli écnico
153
Ins i u o de Educación Secunda ia
Pun a del Ve de
154
Ins i u o de Educación Secunda ia
Ramón Ca ande
155
Ins i u o de Educación Secunda ia
Ramón del Valle Inclán
156
Ins i u o de Educación Secunda ia
Sal ado Tá o a
157
Ins i u o de Educación Secunda ia
San Isido o
158
Ins i u o de Educación Secunda ia
San Je ónimo
159
Ins i u o de Educación Secunda ia
San Pablo
160
Ins i u o de Educación Secunda ia
San a Au elia
161
Ins i u o de Educación Secunda ia
Se illa-Es e
162
Ins i u o de Educación Secunda ia
Siglo XXI
163
Ins i u o de Educación Secunda ia
To eblanca
164
Ins i u o de Educación Secunda ia
T iana
165
Ins i u o de Educación Secunda ia
V Cen ena io
166
Ins i u o de Educación Secunda ia
Velázquez
167
Ins i u o de Educación Secunda ia
Vicen e Aleixand e
Tabla 2. Cen os educa i os de Se illa. (Jun a de Andalucía. Conseje ía de Educación.)
Pa a en ende mejo la ubicación geog á ica de los cen os educa i os se p esen an las siguien es
imágenes, en la p ime a se obse a un conjun o de pun os ubicados en el mapa, cada pun o ep esen a un cen o
educa i o; en la segunda se obse a un mapa de calo de los cen os educa i os.
Figu a 11. Localización de los cen os educa i os. (“GoogleMaps,” n.d.).

49
Figu a 12. Mapa de calo de los cen os educa i os. (“GoogleMaps,” n.d.).
T a amien o de da os de pa ida
Pa a pode sabe cuáles son y donde se si úan, odas las gua de ías, colegios e ins i u os de la ciudad de
Se illa, se ealizó una búsqueda, llegando a una página web de la Jun a de Andalucía que p opo cionaba un
a chi o .cs con la di ección, nomb e, código pos al, si e a público o p i ado, elé ono, e c. En dicho a chi o se
con emplaba oda la p o incia de Se illa, po lo que a a és de un il ado se queda on solo los pe enecien es
a Se illa capi al, y que además ue an públicos. Es e a chi o .cs sepa ado po comas, se pasó a un iche o Excel
en p ime luga . Realizando dichos il os se queda on 167 cen os educa i os en e gua de ías, colegios e
ins i u os, odos ellos públicos, los cuales o ma án el núme o de nodos del p oblema a esol e .
Caso de es udio
50
50
En un p incipio se u ilizó una API de Google pa a consegui las la i udes y longi udes de cada cen o
educa i o, pa a pos e io men e, y a a és de la misma API, gene a los iempos en e los colegios. Pa a ello se
implemen ó en Ma lab dos códigos. Uno pa a consegui la la i ud y la longi ud, y o o pa a ob ene los iempos.
Pa a implemen a y pa a asegu a que los códigos es aban co ec os, se u ilizó una pa e pequeña del
lis ado de cen os educa i os, cuando se e i icó que odo es aba co ec o se aplicó a odo el lis ado.
En un p incipio los códigos pa a la API uncionaban co ec amen e, sal o que la aplicación enía un lími e
de pe iciones po minu o y po día, es e pequeño p oblema se sol en ó median e algunas ins ucciones en el
código que con olaban los e o es y ges ionaban una lis a de pe iciones pendien es.
De esa mane a, se ob u o odas las la i udes y longi udes de la lis a pequeña de los cen os educa i os, y
los iempos en e ellos. Es os iempos ue on u ilizados pa a ealiza los algo i mos de esolución, pa a así
acili a su implemen ación y asegu a que es os uncionaban co ec amen e.
Una ez se comp obó que ambos códigos uncionaban co ec amen e, se aplica on al o al de los cen os
educa i os, pe o al in en a ejecu a los no se podía, debido a un e o elacionado con la API de Google.
Buscando in o mación sob e el posible e o , se llegó a que pa a pode u iliza dicha API se necesi a una Key,
que se puede consegui acili ando una cuen a pa a ac u ación. Google p opo ciona un núme o de c édi os
g a ui os, po lo que se in uye que se ha supe ado dichos c édi os.
Po lo que as mucha in es igación sob e cómo consegui los iempos en e los cen os educa i os, se
implemen a on a iaciones en ambos códigos an e io es, se in oduje on algunas ins ucciones pa a que lanza a
pe iciones di ec amen e a Google Maps. La espues a a es as pe iciones es mucho más labo iosa de lee , y e a
más di ícil de encon a la in o mación que se buscaba. Aunque inalmen e, y as un iempo de implemen ación
del código se consiguió ob ene oda la in o mación necesa ia de odos los cen os educa i os.
La ma iz inal de iempos en e cen os educa i os, y las la i udes y longi udes de es os, se expo a on a
dos iche os Excel di e en es pa a su pos e io acceso du an e la ejecución de los algo i mos. Además, se
comp oba on a ios de es os da os ob enidos, in oduciéndolos alea o iamen e en Google Maps y ob eniendo el
esul ado espe ado. Es os códigos u ilizaban como da os de pa ida:
- Tipo de cen o educa i o: Colegio, gua de ía o ins i u o
- Nomb e del cen o educa i o
- Di ección del cen o educa i o
- Código Pos al del cen o educa i o
Es a in o mación si ió pos e io men e pa a calcula las soluciones a cada una de las heu ís icas que se
implemen a on en Ma lab. Se debe des aca que la idea de consegui las la i udes y longi udes, e a pa a que, a
pa i de es as, se ob u ie an los iempos. Aunque al inal, los iempos se ob u ie an median e la p opia di ección.
Pe o dichas la i udes y longi udes si ie on pos e io men e, pa a ealiza un clus e ing, y clasi ica los cen os
educa i os en 4 g upos, ya que, la u a comple a de odos los cen os educa i os no se podía ealiza po mo i os
que se explica án pos e io men e. El clus e ing se ealizó a a és de una aplicación de Ma lab que se basa en
edes neu onales.
51
En el anexo del p oyec o es án e lejados es os códigos, donde se en las ins ucciones, en o ma de
comen a ios, que se u iliza on pa a la API, y las que pos e io men e se u iliza on pa a Google Maps. Es os
códigos se denomina on la _lo _colegios.m y MATRIZ_OD_COLEGIOS.m.
esul ados expe imen ales
52
52
5 RESULTADOS EXPERIMENTALES
En es e capí ulo del p oyec o, se an a p esen a los esul ados ob enidos as aplica algunos de los
algo i mos explicados en el capí ulo 1, pa a cada heu ís ica se explica á b e emen e el código implemen ado,
los p oblemas que su gie on y los esul ados ob enidos.
Se a a p esen a el esul ado de cada heu ís ica, y el esul ado de es a as aplica le ambién o a heu ís ica
de mejo a, K-op .
Pa a mos a la solución de cada heu ís ica se p esen a una abla po solución, en dicha abla se mues a
el o den a segui en la u a. Los núme os que se obse an en las ablas co esponden al índice que se le asignó a
cada cen o educa i o en la ma iz de o igen y des ino. Toda u a debe comenza con el índice 1 y e mina con
el mismo índice, ya que se debe comenza y e mina en el mismo pun o. El o den de la u a se isualiza en las
ablas leyéndolas de izquie da a de echa comenzando po la p ime a ila.
Vecino más p óximo
Como se ha comen ado an e io men e, es la heu ís ica más sencilla y más ápida de implemen a en
Ma lab. Apenas hubo p oblemas pa a la ealización del código, ya que es e e a muy in ui i o.
Tiempo de la u a: 53.617 segundos, 893’62 minu os, 14’9 ho as.
1
85
118
27
139
99
79
142
83
87
113
34
18
103
75
61
94
144
122
148
66
37
40
156
160
138
65
127
62
67
6
53
54
26
52
151
119
101
135
154
63
45
126
25
19
5
92
88
44
105
106
91
60
159
116
14
97
81
108
80
136
12
74
143
35
10
95
149
20
51
161
165
155
32
84
11
33
125
47
146
53
7
28
82
57
22
120
3
9
15
134
141
71
104
112
21
114
8
23
130
153
46
58
128
48
123
39
16
98
132
43
73
140
164
76
38
42
77
89
124
131
4
117
167
111
68
121
110
70
13
133
64
31
56
137
109
93
24
100
158
102
69
55
150
41
145
30
166
49
29
157
129
96
17
162
115
59
86
163
90
72
2
78
107
147
36
50
152
1
Tabla 3. Ru a del ecino más p óximo
En la imagen an e io se ap ecia la u a a segui según la heu ís ica del ecino más p óximo, el iempo
o al se ía de 14,9 ho as. Se debe des aca que es e iempo co esponde al iempo de i de un pun o a o o, a es e
iempo hab á que añadi les o os iempos necesa ios pa a ealiza el epa o.
• Aplicándole la mejo a K-op : 53.252 segundos, 887’53 minu os, 14’80 ho as
El o den a segui es p ác icamen e el mismo, solo exis en pequeñas a iaciones de in e cambio en e dos
pun os. Es a solución ha mejo ado la an e io del ecino más p óximo en unos 6 minu os.
1
85
118
27
139
99
79
142
83
87
113
34
18
103
75
61
94
144
122
148
66
37
40
156
160
138
65
127
62
67
6
53
54
26
52
151
119
101
135
154
63
45
126
25
19
5
92
88
44
105
106
91
60
159
116
14
97
81
108
80
136
12
74
143
35
10
95
149
20
51
161
165
155
32
84
11
33
125
47
146
7
28
82
57
22
120
3
9
15
134

esul ados expe imen ales
54
54
141
71
104
21
112
114
8
23
130
132
43
153
46
58
128
48
123
39
16
98
73
140
164
76
38
4
131
124
89
77
42
117
167
111
68
121
110
70
13
133
64
31
56
137
109
93
24
100
158
102
69
55
150
41
145
30
166
49
29
157
129
96
17
162
115
59
86
163
90
72
2
78
107
147
36
50
152
1
Tabla 4. Ru a del ecino más p óximo op imizada
Colonia de ho migas
Algo i mo que depende de algunos pa áme os elegidos, como bien se explica en el ma co eó ico de es a
heu ís ica, el cual se puede e en el capí ulo 1 de es e p oyec o. A con inuación, se p esen an los alo es que se
han es ablecido pa a es os pa áme os, el mejo iempo ob enido y su u a.
- I e aciones: 400
- Núme o de ho migas: 300
- Coe icien e de e apo ación:0.1
- Impo ancia as o e omona: 1
- Impo ancia ma iz heu ís ica:1
- Impo ancia del as o del nue o mejo camino: 5
Todos es os pa áme os se han ido cambiando, ob eniéndose dis in as soluciones pa a es a heu ís ica. La
mejo solución ob enida se mues a a con inuación, la cual se alcanzó con los pa áme os p esen ados a iba.
55
Tiempo de la u a: 50.969 segundos, 849’49 minu os, 14’16 ho as.
1
85
118
109
93
24
100
158
129
150
137
31
56
121
139
99
79
142
83
87
113
34
103
75
111
131
4
124
89
77
42
164
76
38
140
73
117
167
157
29
3
120
159
60
116
94
144
122
148
147
14
71
104
44
105
106
91
21
112
114
126
25
5
92
135
154
63
45
160
138
65
127
62
67
6
53
54
26
52
151
88
78
72
17
162
115
59
146
7
28
82
97
81
74
108
80
136
143
35
10
95
149
20
51
165
155
32
84
11
33
125
47
96
161
86
163
90
2
58
153
46
16
98
132
43
128
48
123
39
107
8
141
61
166
49
68
55
69
12
22
57
41
64
102
27
110
70
13
133
9
15
134
30
145
18
23
50
36
19
119
101
66
37
40
156
130
152
1
Tabla 5. Ru a de la colonia de ho migas
Se ha de des aca que es un algo i mo que mejo a la solución del ecino más p óximo, el incon enien e
es que el iempo compu acional es algo ele ado, pe o es algo que se puede pasa po al o, debido a la buena
solución que ha p opo cionado. Es e iempo compu acional es al o debido al g an núme o de nodos que p esen a
el p oblema, al amaño de la población de ho migas que se ha elegido y al núme o de i e aciones es ablecido. Si
se disminuye es a población de ho migas y/o el núme o de i e aciones, el iempo compu acional disminuye.
Se hicie on a ias p uebas disminuyendo ambos pa áme os, y el iempo compu acional disminuyó algo,
pe o la solución empeo ó demasiado, ace cándose, e incluso sob epasando, el iempo del ecino más p óximo.
esul ados expe imen ales
56
56
• Aplicándole la mejo a K-op : 50.549 segundos, 842’48 minu os, 14’04 ho as.
1
85
118
158
100
24
93
109
129
150
137
31
56
121
139
99
79
142
83
87
113
34
103
75
111
4
131
124
89
42
77
164
76
38
140
73
117
167
157
29
3
120
159
60
116
94
144
122
148
147
14
71
104
112
21
91
106
105
44
114
126
25
5
92
135
154
63
45
160
138
65
127
62
67
6
53
54
26
52
151
88
78
72
17
162
115
59
146
7
28
82
81
97
74
108
80
136
143
35
10
95
149
20
51
165
155
32
84
11
33
125
47
96
161
86
163
90
2
46
153
58
16
98
132
43
39
123
48
128
107
8
141
61
166
49
68
55
69
12
22
57
41
64
102
27
110
70
13
133
9
15
134
30
145
18
23
50
36
19
119
101
66
37
40
156
130
152
1
Tabla 6. Ru a de la colonia de ho migas op imizada
T as la aplicación de la heu ís ica de mejo a K-op , se consiguió disminui el iempo en unos 7 minu os,
consiguiendo comple a se la u a en 14.04 ho as.
57
B anch and Bound
En es e caso, el código implemen ado no es exac amen e el mé odo de B anch and Bound, aunque sí es á
basado en él. La di e encia p incipal es que en el código no se u iliza la écnica de back acking, mien as que
en B anch and Bound es básico su uso. La explicación de po que no se ha u ilizado es po el iempo
compu acional, es deci , si se usa a dicha écnica el iempo de ejecución se ía muy ine icien e.
Como bien se explicó en el apa ado eó ico de es e algo i mo, B anch and Bound es un mé odo de
esolución exac o, pe o que depende demasiado del núme o de nodos. Pa a el ejemplo, que se io en la imagen
de esa sección, se esol ía un p oblema con 4 ciudades, y pa a esol e lo con es e mé odo se debía esol e 14
subp oblemas. En el caso de es udio son 167 pun os a eco e , po lo que el núme o de subp oblemas se hace
in iable en iempo de ejecución.
Po ello, se ha op ado mejo a el iempo compu acional a pesa de que la solución ob enida se e á
a ec ada nega i amen e. Pa a eso, se ha ob iado el back acking, po lo que el algo i mo implemen ado se basa
en la aplicación de la ma iz educida. Se aplica la ma iz educida a la ma iz de cos es, eliminando de la ma iz
de cos es cada posible casilla (o igen, des ino) en un p oceso i e a i o, se elige la casilla cuya ma iz modi icada
enga meno cos e. El nodo des ino de esa casilla se con ie e en o igen, y se uel e a ealiza el p oceso i e a i o.
Así, has a eco e odos los nodos. El o den de las casillas, se á la u a inal.
Al no hace el back acking, el á bol que queda es de an solo una ama, ya que solo se eco e un camino.
Explicado odo es o, se a a p esen a la u a ob enida y el iempo de dicha u a, así como la solución con
la heu ís ica de mejo a.
Tiempo de la u a: 55.186 segundos, 919’77 minu os, 15’33 ho as.
1
85
137
102
27
64
118
150
41
139
99
79
142
68
121
129
109
93
24
158
100
55
69
9
15
87
18
34
113
61
166
157
49
83
29
134
12
136
143
96
11
20
47
28
82
57
22
116
14
147
104
104
141
94
8
66
37
40
156
63
45
160
2
114
126
25
19
5
92
135
154
67
6
53
54
26
132
43
39
123
48
128
58
107
88
78
72
17
162
86
161
51
165
155
32
84
149
95
10
35
146
7
74
108
80
97
81
3
120
13
133
31
56
110
70
117
167
111
152
140
73
124
89
130
23
50
36
148
65
138
esul ados expe imen ales
64
64
Como se puede obse a en la imagen an e io , los cen os educa i os se di idie on en 4 g upos, 29 en el
g upo 1, 56 en el g upo 2, 58 en el g upo 3 y 24 en el g upo 4. Encon ándose el pun o de pa ida y de llegada
en el g upo 3, po lo que al g upo 1,2 y 4 hay que añadi un nodo más. Dicha imagen no ep esen a la ubicación
geog á ica de los g upos, solo el amaño de los g upos. Cabe des aca que se obse an dos g andes g upos y dos
g upos de meno amaño.
En la siguien e imagen sí que se puede di e encia donde es án los cen oides de cada g upo en unción
de la longi ud y la la i ud.
Figu a 16. Cen oides de los g upos
Una ez se consiguen es os g upos, se c ea on 4 subma ices de iempos o igen/des ino, cada una pa a un
g upo, pa a así hace más ácil las pequeñas modi icaciones de los algo i mos u ilizados. En la siguien e imagen,
se puede di e encia cla amen e los 4 g upos ep esen ados con un colo dis in o y la es ella se ía el o igen y el
des ino de cada una de las 4 u as que se lle a á a cabo en el epa o de ma e ial escola en los cen os educa i os
de Se illa. Se puede isualiza como los g upos ojo y ama illo son los de mayo amaño, y los g upos e de y
azul los de meno amaño.

65
Figu a 17. Localización de los cen os educa i os po g upo. (“GoogleMaps,” n.d.).
Se puede acep a es a ag upación ealizada po la aplicación de Ma lab, ya que la disposición de los g upos
coincide con el mapa de calo p esen ado en el capí ulo del caso de es udio. En la siguien e imagen se p esen a
una supe posición de ambos mapas. Y en ella se obse a como las mayo es concen aciones del mapa de calo
coincide con los dos g upos mayo i a ios de cen os educa i os.
Figu a 18. Relación mapa de calo con los g upos. (“GoogleMaps,” n.d.).
esul ados expe imen ales
66
66
Debido a la c eación de es as subma ices de iempos, y de la u ilización de es as en los algo i mos pa a
cada g upo, se pie de el índice que se le asignaba a cada cen o educa i o en la ma iz o iginal o igen/des ino.
Po ello se implemen ó un código, llamado RELACION_INDICE_COLEGIO.m, en es e código se elaciona la
posición de los nue os índices con los o iginales, pa a así sabe la posición de cada colegio en cada u a.
Una ez ya se iene los g upos, los iempos en e los nodos de cada g upo y la elación de los índices de
los cen os educa i os, se hicie on pequeñas modi icaciones en los algo i mos an es aplicados, elacionadas con
el amaño de los ec o es y ma ices u ilizadas, el uncionamien o de cada heu ís ica pe maneció cons an e.
T as odo es o, se p esen an los esul ados ob enidos pa a el ecino más p óximo, la colonia de ho migas
y el algo i mo gené ico. Al esul ado, de aquella heu ís ica que p opo cione la mejo solución, se le aplica á el
algo i mo K-op , pa a in en a op imiza un poco más dicho esul ado.
Vecino más p óximo pa a cada g upo
Como bien se ha comen ado, se a a aplica a cada g upo la heu ís ica del ecino más p óximo,
ob eniéndose 4 u as, una pa a cada g upo, y 4 iempos de u a.
Tiempo de la u a 1: 10.339 segundos, 172’32 minu os, 2’88 ho as.
1
143
35
10
95
149
20
51
161
165
155
32
11
33
125
47
146
7
28
160
17
162
115
59
86
163
90
96
72
78
1
Tabla 11. Ru a del g upo 1 con el ecino más p óximo
67
Tiempo de la u a 2: 19.311 segundos, 321’85 minu os, 5’37 ho as.
1
138
65
127
62
67
6
53
54
26
52
151
119
101
135
154
63
45
144
122
148
66
37
40
156
114
126
94
141
61
147
71
104
112
21
44
105
106
91
92
88
58
16
98
132
43
39
123
48
107
2
8
25
19
5
36
50
1
Tabla 12. Ru a del g upo 2 con el ecino más p óximo
Tiempo de la u a 3: 19.126 segundos, 318’77 minu os, 5’32 ho as.
1
85
118
27
139
99
79
142
83
87
113
34
18
3
120
159
60
116
14
97
81
108
80
136
12
74
57
22
55
69
9
15
134
70
110
121
56
31
137
109
93
24
100
158
64
102
133
13
68
150
41
82
129
145
30
29
49
84
1
Tabla 13. Ru a del g upo 3 con el ecino más p óximo
esul ados expe imen ales
68
68
Tiempo de la u a 4: 10.501 segundos, 175’02 minu os, 2’92 ho as.
1
117
73
140
164
76
38
42
77
89
124
130
23
103
75
111
131
4
152
167
157
166
153
46
128
1
Tabla 14. Ru a del g upo 4 con el ecino más p óximo
El iempo o al de odos los g upos se ía de: 59.277 segundos, 987’95 minu os, 16’47 ho as.
Colonia de ho migas pa a cada g upo
Es a heu ís ica p opo cionaba la mejo solución, pa a una u a po odos los cen os educa i os, aho a se
a aplica a cada g upo y se comp oba á si sigue siendo la mejo heu ís ica pa a es e p oblema. Los alo es de
los pa áme os u ilizados pa a los g upos ue on los mismos que pa a el conjun o o al de cen os educa i os,
es os pa áme os son:
- I e aciones: 400
- Núme o de ho migas: 300
- Coe icien e de e apo ación:0.1
- Impo ancia as o e omona: 1
- Impo ancia ma iz heu ís ica:1
- Impo ancia del as o de nue o mejo camino: 5
Tiempo de la u a 1: 9.031 segundos, 150’52 minu os, 2’51 ho as.
1
143
149
95
10
35
96
51
161
165
155
32
20
11
33
125
47
146
7
28
160
78
72
17
162
115
59
90
163
86
1
Tabla 15. Ru a del g upo 1 con la colonia de ho migas
69
Tiempo de la u a 2: 18.306 segundos, 305’10 minu os, 5’09 ho as.
1
44
105
106
91
71
104
21
112
114
126
94
141
61
8
156
40
37
66
144
122
148
147
25
101
119
135
154
63
45
2
138
65
127
62
67
6
53
54
132
43
39
123
48
58
16
98
5
92
52
151
26
36
50
19
107
88
1
Tabla 16. Ru a del g upo 2 con la colonia de ho miga
Tiempo de la u a 3: 17.209 segundos, 286’82 minu os, 4’78 ho as.
1
85
118
109
64
31
56
121
139
99
79
142
83
29
49
68
27
110
70
13
133
9
113
34
18
3
120
22
57
41
102
137
158
100
24
93
55
69
150
145
30
15
87
116
60
159
136
12
74
108
80
97
81
134
14
82
84
129
1
Tabla 17. Ru a del g upo 3 con la colonia de ho migas
Tiempo de la u a 4: 9.447 segundos, 157’45 minu os, 2’63 ho as.
1
157
166
103
75
111
4
131
124
89

esul ados expe imen ales
70
70
77
42
73
117
167
164
76
38
152
140
130
23
153
46
128
1
Tabla 18. Ru a del g upo 4 con la colonia de ho migas
El iempo o al de odos los g upos se ía de: 53.993 segundos, 899’89 minu os, 15 ho as. El amaño de
los 4 p oblemas del iajan e que se han esuel o es meno , y al conse a los mismos pa áme os se llegan a
mejo es soluciones que aplicando la heu ís ica al conjun o comple o.
Algo i mo gené ico pa a cada g upo
Es a heu ís ica ue de las que peo es esul ados p opo cionó al conjun o comple o de cen os educa i os,
como ya se explicó, debido al al o núme o de cen os. En es a ocasión se espe a que de uel a buenas soluciones,
debido a que el núme o de nodos disminuye, al di idi los cen os educa i os en 4 g upos. En es a ocasión, sí se
modi ica on algunos pa áme os que in luyen en el algo i mo, solo pe maneció cons an e el amaño de la
población de indi iduos. Con lo cual pa a cada g upo se u iliza on una p obabilidad de mu ación y de
ecombinación di e en es.
Es des acable señala , que an o pa a la colonia de ho migas como pa a el algo i mo gené ico se ealiza on
p uebas de calib ación con la misma semilla pa a es ablece los alo es de los di e en es pa áme os.
Tiempo de la u a 1: 9.007 segundos, 150’12 minu os, 2’51 ho as.
- Tamaño de la población: 5000
- P obabilidad de mu ación: 1
- P obabilidad de ecombinación: 1
1
143
149
95
10
35
96
11
20
51
161
32
155
165
33
125
47
146
7
28
160
78
72
17
59
115
162
90
163
86
1
71
Tabla 19. Ru a del g upo 1 con el algo i mo gené ico
Tiempo de la u a 2: 18.291 segundos, 304’85 minu os, 5’09 ho as.
- Tamaño de la población: 5000
- P obabilidad de mu ación: 0.35
- P obabilidad de ecombinación: 1
1
44
105
106
91
71
104
21
112
114
126
94
141
61
8
156
40
37
66
144
122
148
147
25
101
119
135
154
63
45
138
2
65
127
62
67
6
53
54
132
43
39
123
48
58
16
98
5
92
52
151
26
36
50
19
107
88
1
Tabla 20. Ru a del g upo 2 con el algo i mo gené ico
Tiempo de la u a 3: 17.123 segundos, 285’39 minu os, 4’76 ho as.
- Tamaño de la población: 5000
- P obabilidad de mu ación: 0.9
- P obabilidad de ecombinación: 1
1
85
118
109
64
31
56
121
139
99
79
142
83
29
49
68
27
110
70
13
133
9
113
34
18
3
120
22
57
41
102
137
158
100
24
93
55
69
150
145
30
15
87
116
60
159
136
12
74
108
esul ados expe imen ales
72
72
80
97
14
134
81
82
84
129
1
Tabla 21. Ru a del g upo 3 con el algo i mo gené ico
Tiempo de la u a 4: 9.325 segundos, 155’42 minu os, 2’60 ho as.
- Tamaño de la población: 5000
- P obabilidad de mu ación: 0.85
- P obabilidad de ecombinación: 1
1
22
24
12
8
13
2
18
20
5
10
14
25
23
9
4
19
7
15
11
17
3
21
6
16
1
Tabla 22. Ru a del g upo 4 con el algo i mo gené ico
El iempo o al de odos los g upos se ía de: 53.746 segundos, 895’77 minu os, 14’93 ho as. Es muy
des acable lo que ha mejo ado las soluciones ob enidas con es a heu ís ica al disminui el núme o de nodos. De
se una de las que peo es soluciones p opo cionaba pa a el conjun o comple o, a se la que mejo solución ha
p opo cionado a cada uno de los g upos.
Po ello, a las soluciones ob enidas po el algo i mo gené ico se les aplicó la heu ís ica de mejo a K-op ,
cuyas soluciones se p esen an en el siguien e apa ado.
Heu ís ica de mejo a pa a cada u a
T as la aplicación de es os algo i mos se obse a que las mejo es u as se han ob enido con el algo i mo
gené ico, a la solución de es e algo i mo se le a a aplica una heu ís ica de mejo a, k-op .
73
A con inuación, se p esen a los esul ados de la heu ís ica de mejo a K-op , aplicada a la solución ob enida
con el algo i mo gené ico:
Tiempo de la u a 1: 8.915 segundos, 148’59 minu os, 2’48 ho as.
1
160
78
72
17
59
115
162
90
163
86
161
20
32
155
165
51
96
11
33
125
47
95
149
10
35
143
146
7
28
1
Tabla 23. Ru a del g upo 1 con algo i mo gené ico op imizado.
En la siguien e imagen se obse a el o den a segui en la u a del g upo 1, los núme os ep esen an en que
o den se a a epa i el ma e ial en los cen os educa i os.
Figu a 19. Localización de los cen os del g upo 1. (“GoogleMaps,” n.d.)
esul ados expe imen ales
80
80
Figu a 21. Localización de los cen os del g upo 3. (“GoogleMaps,” n.d.)
ORDEN
TIPO DE CENTRO EDUCATIVO
NOMBRE DEL CENTRO
EDUCATIVO
ÍNDICE
EN LA
MATRIZ
DE
TIEMPOS
1
'Colegio de Educación In an il y P ima ia'
Ad iano
1
2
'Colegio de Educación In an il y P ima ia'
Teodosio
85
3
'Ins i u o de Educación Secunda ia'
Albe Eins ein
118
4
'Escuela In an il'
San Je ónimo
109
5
'Colegio de Educación In an il y P ima ia'
Pablo Ruiz Picasso
64

81
6
'Colegio de Educación In an il y P ima ia'
Ignacio Sánchez Mejías
31
7
'Colegio de Educación In an il y P ima ia'
Ma ía Zamb ano
56
8
'Ins i u o de Educación Secunda ia'
Azaha
121
9
'Ins i u o de Educación Secunda ia'
Llanes
139
10
'Escuela In an il'
A go e de Molina
99
11
'Colegio de Educación In an il y P ima ia'
San José Ob e o
79
12
'Ins i u o de Educación Secunda ia'
Maca ena
142
13
'Colegio de Educación In an il y P ima ia'
So Ángela de la C uz
83
14
'Colegio de Educación In an il y P ima ia'
Hue a de San a Ma ina
29
15
'Colegio de Educación In an il y P ima ia'
Maca ena
49
16
'Colegio de Educación In an il y P ima ia'
Ped o Ga ias
68
17
'Colegio de Educación In an il y P ima ia'
He manos Machado
27
18
'Escuela In an il'
San a Ca alina
110
19
'Colegio de Educación In an il y P ima ia'
Pío XII
70
20
'Colegio de Educación In an il y P ima ia'
Blas In an e
13
21
'Ins i u o de Educación Secunda ia'
Inmaculada Viei a
133
22
'Colegio de Educación In an il y P ima ia'
A ias Mon ano
9
23
'Escuela In an il'
San ísima T inidad
113
24
'Colegio de Educación In an il y P ima ia'
Ja dines del Valle
34
25
'Colegio de Educación In an il y P ima ia'
Ca men Bení ez
18
26
'Colegio de Educación In an il y P ima ia'
Al-Andalus
3
27
'Ins i u o de Educación Secunda ia'
An onio Machado
120
28
'Colegio de Educación In an il y P ima ia'
Esc i o Al onso G osso
22
29
'Colegio de Educación In an il y P ima ia'
Ma iana de Pineda
57
30
'Colegio de Educación In an il y P ima ia'
Juan de Mai ena
41
31
'Escuela In an il'
Julio Césa
102
32
'Ins i u o de Educación Secunda ia'
Julio Ve ne
137
33
'Ins i u o de Educación Secunda ia'
San Je ónimo
158
esul ados expe imen ales
82
82
34
'Escuela In an il'
Fe nando Villalón
100
35
'Colegio de Educación In an il y P ima ia'
Fede ico Ga cía Lo ca
24
36
'Colegio de Educación P ima ia'
Buena is a
93
37
'Colegio de Educación In an il y P ima ia'
Manuel Siu o
55
38
'Colegio de Educación In an il y P ima ia'
Pino Flo es
69
39
'Ins i u o de Educación Secunda ia'
Pino Mon ano
150
40
'Ins i u o de Educación Secunda ia'
Miguel de Ce an es
145
41
'Colegio de Educación In an il y P ima ia'
Hue a del Ca men
30
42
'Colegio de Educación In an il y P ima ia'
Cal o So elo
15
43
'Colegio de Educación In an il y P ima ia'
Valdés Leal
87
44
'Escuela In an il'
Vi gen de los Reyes
116
45
'Colegio de Educación In an il y P ima ia'
Miguel He nández
60
46
'Ins i u o de Educación Secunda ia'
San Pablo
159
47
'Ins i u o de Educación Secunda ia'
Joaquín Tu ina
136
48
'Colegio de Educación In an il y P ima ia'
Bal asa de Alcáza
12
49
'Colegio de Educación In an il y P ima ia'
San Ignacio de Loyola
74
50
'Escuela In an il'
Sag ada Familia
108
51
'Colegio de Educación In an il y P ima ia'
San Juan de Ribe a
80
52
'Escuela In an il'
Ángel de la Gua da
97
53
'Colegio de Educación In an il y P ima ia'
Bo bolla
14
54
'Ins i u o de Educación Secunda ia'
Isbilya
134
55
'Colegio de Educación In an il y P ima ia'
San Pablo
81
56
'Colegio de Educación In an il y P ima ia'
San a Cla a
82
57
'Colegio de Educación In an il y P ima ia'
Ta essos
84
58
'Ins i u o de Educación Secunda ia'
Félix Rod íguez de la Fuen e
129
1
'Colegio de Educación In an il y P ima ia'
Ad iano
1
Tabla 28. Ru a de los cen os educa i os del g upo 3
83
Tiempo de la u a 4: 9.325 segundos, 155’42 minu os, 2’59 ho as.
1
22
24
12
8
13
2
18
20
5
10
14
25
23
9
4
19
7
15
11
17
3
21
6
16
1
Tabla 29. Ru a del g upo 4 con algo i mo gené ico op imizado
Figu a 22. Localización de los cen os del g upo 4. (“GoogleMaps,” n.d.)
esul ados expe imen ales
84
84
ORDEN
TIPO DE CENTRO EDUCATIVO
NOMBRE DEL CENTRO
EDUCATIVO
ÍNDICE
EN LA
MATRIZ
DE
TIEMPOS
1
'Colegio de Educación In an il y P ima ia'
Ad iano
1
2
'Ins i u o de Educación Secunda ia'
San Isido o
157
3
'Ins i u o de Educación Secunda ia'
Velázquez
166
4
'Escuela In an il'
Ma ía Inmaculada
103
5
'Colegio de Educación In an il y P ima ia'
San Isido o
75
6
'Escuela In an il'
San a Luisa de Ma illac
111
7
'Colegio de Educación In an il y P ima ia'
Al a es
4
8
'Ins i u o de Educación Secunda ia'
Gus a o Adol o Bécque
131
9
'Ins i u o de Educación Secunda ia'
Poli écnico
152
10
'Colegio de Educación In an il y P ima ia'
Juan Ramón Jiménez
42
11
'Colegio de Educación In an il y P ima ia'
San José de Calasanz
77
12
'Escuela In an il'
De Se illa
117
13
'Ins i u o de Educación Secunda ia'
Vicen e Aleixand e
167
14
'Ins i u o de Educación Secunda ia'
T iana
164
15
'Colegio de Educación In an il y P ima ia'
San Jacin o
76
16
'Colegio de Educación In an il y P ima ia'
José Ma ía del Campo
38
17
'Ins i u o de Educación Secunda ia'
Los Vi e os
140
18
'Colegio de Educación In an il y P ima ia'
Rico Cejudo
73
19
'Ins i u o de Educación Secunda ia'
Ca los Haya
124
20
'Colegio de Educación In an il y P ima ia'
Va a del Rey
89
21
'Ins i u o de Educación Secunda ia'
Fe nando de He e a
130
22
'Colegio de Educación In an il y P ima ia'
España
23
23
'Ins i u o de Educación Secunda ia'
Pun a del Ve de
153
24
'Colegio de Educación In an il y P ima ia'
La Raza
46
85
25
'Ins i u o de Educación Secunda ia'
Fede ico Mayo Za agoza
128
1
'Colegio de Educación In an il y P ima ia'
Ad iano
1
Tabla 30. Ru a de los cen os educa i os del g upo 4
El iempo o al de odos los g upos se ía de: 53.598 segundos, 893’3 minu os, 14’89 ho as.
El uncionamien o del algo i mo gené ico ha mejo ado an o pa a pequeños g upos de nodos, que incluso
la heu ís ica de mejo a local no consigue op imiza las u as 3 y 4.
También es eseñable el buen compo amien o de la colonia de ho migas, cuya solución pa a cada g upo
es muy ce cana en iempo a la del algo i mo gené ico.
Es a úl ima solución es la que se adop a como mejo solución del caso es udiado, la cual se ca ac e iza
po ene 4 u as, una pa a cada día. Aunque a dicha solución se le aplica á algunas modi icaciones. En el
siguien e apa ado se p esen a án las conclusiones y algunos aspec os a ene en cuen a pa a es a solución.

Conclusiones
86
86
6 CONCLUSIONES
Tiempo y u a óp ima
Obse ando y analizando odos los esul ados ob enidos as la aplicación de odos los algo i mos, se ha
llegado a la conclusión de que, p ime o no se puede ealiza odo el epa o del ma e ial escola en una sola u a,
y segundo se ha llegado a una solución que op imiza el iempo y los ecu sos necesa ios pa a lle a a cabo el
epa o.
No se puede lle a a cabo odo el epa o en un mismo día, ya que el iempo mínimo que se ha ob enido
supe a las 8 ho as lími e. Po ello se ealizó la clasi icación de los cen os educa i os en 4 g upos, ealizándose
así una u a po día.
La mejo solución ob enida es la conseguida median e la aplicación del algo i mo gené ico a cada uno de
los 4 g upos de cen os educa i os, y la pos e io aplicación de la heu ís ica de mejo a, k-op . Dichas u as se
pueden obse an en las ablas 27, 28, 29 y 30 de es e p oyec o. Tan o los iempos de cada u a como el iempo
o al que apa ecen jun o a dichas ablas, son los iempos del eco ido, es deci , la suma de los iempos de i de
un pun o a o o.
- Ru a 1: 8.915 segundos, 148’59 minu os, 2’48 ho as
- Ru a 2: 18.235 segundos, 303’92 minu os, 5’07 ho as
- Ru a 3: 17.123 segundos, 285’39 minu os, 4’76 ho as
- Ru a 4: 9.325 segundos, 155’42 minu os, 2’59 ho as
A es os iempos hay que suma les los iempos de ca ga y de desca ga del ma e ial en cada uno de los
cen os educa i os. Es os iempos ue on de inidos al p incipio del capí ulo 3 y son los siguien es:
- Tiempo de ca ga: 60 minu os
- Tiempo de desca ga: 3 minu os po cen o educa i o
Al añadi es os iempos a cada una de las 4 u as, quedan los siguien es iempos:
- Ru a 1: 4’93 ho as
- Ru a 2: 8’87 ho as
- Ru a 3: 8’61 ho as
- Ru a 4: 4’79 ho as
87
Como se puede obse a en los iempos an e io es, en las u as 2 y 3 se sob epasa las 8 ho as de la jo nada
labo al, po lo que hab ía que busca una solución a ese p oblema. O a cues ión que se ía in e esan e mejo a ,
se ía equilib a un poco más los iempos que se dan en cada epa o dia io, debido a que hay dos días con un
iempo demasiado ele ado y dos días con apenas 5 ho as.
Po odo es o, se es u o pensando en cómo mejo a ambas cues iones, había a ías posibilidades, como
aumen a el núme o de g upos en los que clasi ica los cen os educa i os o lib a del iempo de ca ga a aquellos
días más ca gados y añadí selo a los días menos ca gados.
T as con empla ambas al e na i as, se decidió aplica la segunda, ya que con la p ime a disminui ía el
iempo de los días más ca gados, pe o aumen a ía el iempo ocioso de los días menos ca gados. Sin emba go,
con la segunda p opues a, el iempo de los días más ca gados se ía meno y se equilib a ía los iempos de odos
los días.
Al aplica es e c i e io, los 4 días de epa o queda on de la siguien e mane a:
- P ime día: Ca ga la u a 1, ealiza la u a 1 y ca ga la u a 2. Tiempo o al: 5’93 ho as.
- Segundo día: Realiza u a 2. Tiempo o al: 7’87 ho as.
- Te ce día: Ca ga u a 4, ealiza u a 4 y ca ga u a 3. Tiempo o al: 5’79 ho as.
- Cua o día: Realiza u a 3. Tiempo o al: 7’61 ho as.
Como se puede ap ecia , los iempos de cada día es án un poco más equilib ado y no se supe a las 8 ho as
dia ias. Al inal se consigue que la ca ga del abajado no enga picos de muchas ho as en un día y pocas ho as
en o o, que se puede comple a el epa o con el mínimo iempo posible y lo más impo an e, al disminui ese
iempo ambién se es án disminuyendo cos es pa a la emp esa. El cos e disminuye en e o as cosas po el aho o
de combus ible. También un aspec o impo an e que se consigue es aumen a la compe i i idad de la emp esa,
debido a que, si se emplea menos iempo en es e epa o, an es se comienza o os epa os, aspec o que los
clien es pueden ene muy en cuen a.
Obse aciones inales
T as habe llegado a la solución, que se acaba de de alla , se puede conclui , que la aplicación del
p oblema del iajan e, ha sido una buena mane a de llega a unas u as e icien es y que ayudan al aho o de
iempo, cos es y kilóme os.
Conclusiones
88
88
Du an e la in es igación han su gido algunas obse aciones que son in e esan es de comen a :
- La di icul ad exponencial que se da en la esolución de es os p oblemas cuando se aumen a el núme o
de pun os a eco e . Un cla o ejemplo, ha sido el algo i mo gené ico, el cual ha p opo cionado una
solución pésima pa a 167 pun os, pe o al aplica lo a los di e en es g upos de meno amaño sí ha
mejo ado mucho su solución con espec o a o os algo i mos.
- El iempo y dine o que se puede llega a aho a una emp esa, con muy poca in e sión, al aplica
es os algo i mos. Es deci , la di e encia en iempo en e ealiza una u a cualquie a y una u a
es udiada es muy g ande, y po ello quizás un cos e demasiado ele ado.
- La aplicación de di e en es algo i mos es necesa ia, ya que quizás con el empleo de un solo algo i mo
no se llega a una u a lo su icien emen e óp ima. Po ejemplo, si solo se hubie a empleado el algo i mo
gené ico a odo el conjun o, se es a ían despe diciando casi 3 ho as de abajo, y el cos e que
supond ía es as 3 ho as ex a, con espec o a la solución de la colonia de ho migas pa a odo el
conjun o.
- La dependencia de algunos algo i mos a cambios en cie os pa áme os. A lo la go del p oyec o, se
han p obado dis in os alo es pa a los pa áme os an o de la colonia de ho migas como del algo i mo
gené ico. Las soluciones a iaban mucho en unción del alo de los pa áme os y del amaño del
p oblema.
- La dis in a e icacia de las heu ís icas según el p oblema. Dependiendo del amaño del p oblema y de
la disposición de los pun os del p oblema hay eces que unciona mejo un algo i mo y o as eces
que unciona mejo o o. Es deci , no siemp e es mejo el mismo.
Como bien se ha comen ado exis e una g an di e encia de e icacia y e iciencia al aplica una heu ís ica u
o a, a con inuación, se de alla pa a cada heu ís ica las p incipales conclusiones que se han ob enido:
• Vecino más p óximo: Como bien se pensaba al p incipio del p oyec o, ha sido un algo i mo ealmen e ácil
de implemen a . También se con i mó la idea de que e a un algo i mo con un iempo compu acional bajo,
pe o la op imalidad de la solución no es an buena. De odos modos, ha p opo cionado esul ados mejo es
de los que se espe aba con ella. Combina es e algo i mo con alguna heu ís ica de búsqueda de óp imo
local, como se ha ealizado en es e p oyec o, p opo ciona una solución e icien e y de cie a calidad. Es o
úl imo coincide con lo que se dice en Pé ez, 2011, donde se analiza el compo amien o del ecino más
p óximo en el p oblema del iajan e.
• B anch and Bound: Du an e la p esen ación de los esul ados ob enidos po es e algo i mo se des acó que
el código no e a exac amen e el de es e algo i mo. En el código implemen ado se ejecu a la esolución po
co es basada en la ma iz educida al igual que en el algo i mo B anch and Bound, pe o no se ealiza el
back acking. No se u iliza es a écnica ya que se ía ine icien e en iempo, si se aplica a el algo i mo exac o
de B anch and Bound se ob end ía la solución exac a del p oblema, pe o eniendo en cuen a el amaño de
es e se ía imposible ob ene la en poco iempo. Po ello se puede conclui que es un algo i mo exac o de
esolución y es ecomendable pa a pequeños p oblemas, pa a p oblemas con amaños simila es al de es e
p oyec o no es ecomendable.
89
• Colonia de ho migas: P opo cionó la mejo solución pa a el conjun o comple o de cen os educa i os y
es u o muy ce ca de las mejo es soluciones pa a cada uno de los g upos. En gene al, se puede deci que es
una muy buena heu ís ica pa a aplica al p oblema del iajan e. Aunque, pa a que su uncionamien o sea
co ec o y se llega a una buena solución, es necesa io un buen calib ado del algo i mo pa a ajus a los
pa áme os. Además, si se compa a en iempo de ejecución con el algo i mo gené ico, el iempo que emplea
la colonia de ho migas es algo meno que el del algo i mo gené ico. Todo lo comen ado sob e la
impo ancia que ha enido en es e p oyec o el alo de los pa áme os y el amaño del p oblema, coincide
con lo que se p esen a en Robles, 2010.
• Algo i mo gené ico: Cuando se empezó a analiza las di e en es heu ís icas que se podían aplica en es e
p oyec o, se pensó que el algo i mo gené ico se ía de las mejo es, y así ha sido. Ha sido el algo i mo que
ha p opo cionado las mejo es soluciones pa a cada g upo, en cambio ha sido de las peo es pa a el conjun o
comple o de los cen os educa i os. Es o con i ma las sospechas sob e que depende demasiado del amaño
del p oblema a a a . Es e aspec o, jun o con su ele ado iempo compu acional son los dos únicos aspec os
nega i os que se le pueden encon a a es a heu ís ica. Ya que es uno de los mejo es y más po en es
algo i mos que exis en. Tal es así, que ha p opo cionado las mejo es soluciones pa a cada uno de los g upos.
Al igual que pa a la colonia de ho migas, es muy impo an e calib a el p oblema pa a los di e en es
conjun os de da os, ya que el alo de los pa áme os in lui á no ablemen e en su e iciencia y e icacia. La
impo ancia de es os pa áme os se puede obse a en Holland, 1992.
Po úl imo, des aca que, con la aplicación de es os esul ados en el modelo de dis ibución del ma e ial
escola , se ob end án los bene icios que se comen a on al p incipio del p oyec o en el aho o de cos e y
kilóme os, en las emisiones de CO2 y en la segu idad ial en el en o no de los cen os educa i os.
T abajos u u os
Una posible línea de abajo u u a pa a mejo a aún más es a p opues a, se ía la de inclui uno o a ios
cen os de dis ibución, de mane a que con la ayuda de es as u as se diseñen localizaciones es a égicas donde
emplaza dichos cen os. La inco po ación de es os cen os de dis ibución se ía necesa ia, ya que en es e
p oyec o se ha con emplado la hipó esis de que un cen o educa i o ecibe odo el ma e ial, y es desde dicho
cen o, desde donde se inician odas las u as.
En caso de exis i ya un cen o de dis ibución se pod ía e si dichas u as ob enidas pueden se aplicadas
pa a dicho cen o. Si los cos es y el iempo empleado aumen a an demasiado al uni dichas u as con el cen o
de dis ibución, se aplica ía los mismos algo i mos incluyendo el nue o cen o de dis ibución como pun o de
pa ida y de llegada.
ANEXO 2. Vecino más p óximo
96
96
ANEXO 2. VECINO MÁS PRÓXIMO
% ALGORITMO DEL VECINO MÁS PRÓXIMO
clea ;
clc;
% Impo he da a
% Impo he da a
% [~, ~, ma izODCOLEGIOS] =
xls ead('C: Use s mnc m Desk op MIKEL US TFM ma izOD_COLEGIOS.xlsx','Hoja1');
%
% ma izODCOLEGIOS = s ing(ma izODCOLEGIOS);
% ma izODCOLEGIOS(ismissing(ma izODCOLEGIOS)) = '';
%
% iempos=ma izODCOLEGIOS;
% iempos=s 2double( iempos);
[~, ~, ma izODCOLEGIOS] = xls ead('C: Use s mnc m Desk op MIKEL US TFM iempo4.xlsx','Hoja1');
ma izODCOLEGIOS = s ing(ma izODCOLEGIOS);
ma izODCOLEGIOS(ismissing(ma izODCOLEGIOS)) = '';
iempos=ma izODCOLEGIOS;
iempos=s 2double( iempos);
o i=1:25
o j=25
i i==j
iempos(i,j)= 0;
end
end
end
%inicio algo i mo
=0;
ecino=1;
u a=[1];
iempos_ ecino=[];
o i=1:24
o j=1:25
sal a = ind( u a==j);
sal a =isemp y(sal a );
i sal a ==1
iempos_ ecino=[ iempos_ ecino iempos( ecino,j)];
else
iempos_ ecino=[ iempos_ ecino 0];
j=j+1;
end
end

97
_0= iempos_ ecino( iempos_ ecino~=0);
_ ecino =min( _0);
ecino= ind( iempos_ ecino== _ ecino);
ecino= ecino(1);
u a=[ u a ecino];
= + _ ecino;
i=i+1;
iempos_ ecino=[];
end
u a
ANEXO 3. BRANCH AND BOUND
98
98
ANEXO 3. BRANCH AND BOUND
% b anch and bound
% clea ;
% clc;
% Impo he da a
% Impo he da a
[~, ~, ma izODCOLEGIOS] =
xls ead('C: Use s mnc m Desk op MIKEL US TFM ma izOD_COLEGIOS.xlsx','Hoja1');
ma izODCOLEGIOS = s ing(ma izODCOLEGIOS);
ma izODCOLEGIOS(ismissing(ma izODCOLEGIOS)) = '';
iempos=ma izODCOLEGIOS;
iempos=s 2double( iempos);
o i=1:167
o j=1:167
i i==j
iempos(i,j)= 0;
end
end
end
m_ iempos= iempos;
m_ iempos(m_ iempos==0)=in ;
ed_ il=min(m_ iempos,[],2);
ed_ il(isin ( ed_ il))=0;
m_ iempos_ ed_ il=m_ iempos- ed_ il;
ed_col=min(m_ iempos_ ed_ il);
m_ iempos_ ed=m_ iempos_ ed_ il- ed_col;
m_ iempos_ ed(isnan(m_ iempos_ ed))=in ;
1=sum( ed_col)+sum( ed_ il);
ec o =[1:167];
am=0;
i=1;
u a=[1];
while am<167 %n
ec o _ =ze os(1,167);
i_0=i;
o j=2:167
i ec o (j)~=in
educida=m_ iempos_ ed;
educida(i,:)=in ;
educida(:,j)=in ;
educida(j,i)=in ;
ed_ il=min( educida,[],2);
ed_ il(isin ( ed_ il))=0;
educida_ il= educida- ed_ il;
ed_col=min( educida_ il);
99
educida= educida_ il- ed_col;
educida(isnan( educida))=in ;
ed_ il( ed_ il==in )=0;
ed_col( ed_col==in )=0;
= 1+sum( ed_col)+sum( ed_ il)+m_ iempos_ ed(i,j);
iempos(i,j);
ec o _ (j)= ;
=0;
end
j=j+1;
end
ec o _ ( ec o _ ==0)=in ;
[cos e pos]=min( ec o _ );
i=pos;
i cos e~=in
1=cos e;
u a=[ u a i];
end
ec o (i)=in ;
aux= ind( ec o ==in );
[ ami amj]=size(aux);
am= amj;
educida=m_ iempos_ ed;
educida(i_0,:)=in ;
educida(:,i)=in ;
educida(i,i_0)=in ;
ed_ il=min( educida,[],2);
ed_ il(isin ( ed_ il))=0;
educida_ il= educida- ed_ il;
ed_col=min( educida_ il);
educida= educida_ il- ed_col;
educida(isnan( educida))=in ;
m_ iempos_ ed= educida;
end
1
u a=[ u a 1]
ANEXO 4. Algo i mo gené ico
100
100
ANEXO 4. ALGORITMO GENÉTICO
- Función p incipal
clea ;
clc;
% Impo he da a
[~, ~, ma izODCOLEGIOS] =
xls ead('C: Use s mnc m Desk op MIKEL US TFM iempo4.xlsx','Hoja1');
ma izODCOLEGIOS = s ing(ma izODCOLEGIOS);
ma izODCOLEGIOS(ismissing(ma izODCOLEGIOS)) = '';
iempos=ma izODCOLEGIOS;
iempos=s 2double( iempos);
am_poblacion=100; % Se ue cambiando según el amaño del p oblema
meno _ alo =30000;
% while meno _ alo >9600
[poblacion]=pob_inicial( am_poblacion);%c eación población inicial
o i e acion=1:15
p ob_ ecombinacion=0.2; %P obabilidad pa a la ecombinación
p ob_mu acion=0.9; %P obabilidad pa a la mu ación
i e =0;
pa a = alse;
=0;
[ un_obje i o]= unObje i o(poblacion, iempos, am_poblacion);%c eación de la unción
obje i o
%Aho a se ab e ciclo has a cumpli dos condiciones: que el meno alo no
%cambie en 2n gene aciones y que llegue a 1000 gene aciones
while pa a == alse
[num_descendien es]=sel_ o neo( un_obje i o, am_poblacion);%p oceso de selección
po o neo
[poblacion]= ecombinacion(num_descendien es,poblacion,p ob_ ecombinacion, am_poblacion
);%nue a población
[ un_obje i o]= unObje i o(poblacion, iempos, am_poblacion);%nue a .obj
101
[poblacion]=mu acion(poblacion,p ob_mu acion, am_poblacion);%mu ación
[ un_obje i o]= unObje i o(poblacion, iempos, am_poblacion);% .obj de la nue a
población si hay mu ación
[nue o_ alo posicion]=min( un_obje i o);
i meno _ alo > nue o_ alo
meno _ alo = nue o_ alo ;
x=poblacion(posicion,:);
end
% p ime a condición de pa ada del bucle while
i meno _ alo ==nue o_ alo ;
= +1;
i ==1000 %2n
pa a = ue;
end
end
%segunda condición de pa ada del bucle while
i i e ==1000
pa a = ue;
end
i e =i e +1;
end
iempo_ u a=meno _ alo
u a=x;
iempos_ u a(i e acion,1)= iempo_ u a;
u as(i e acion,:)= u a;
end
[ iempo_ u a pos_op imo]=min( iempos_ u a);
iempo_ u a
u a_op ima=[1 u as(pos_op imo,:) 1]
%end
- Población inicial
- unc ion [poblacion]=pob_inicial( am_poblacion, u a)
-
- %En es a unción se c ea las poblaciones iniciales a pa i de la cual
- % abaja , cada población end á una u a alea o ia
-
- %s= ng( andpe m(1000,1))%u iliza la misma semilla pa a comp oba cálculos del
algo i mo, es deci , mismos nume os alea o ios,
- poblacion=ze os( am_poblacion-1,24);% el n-1
- %s= ng(938)
-
-
- o i = 1: am_poblacion% ilas-->población
-
- ec o ( andpe m(24))=2:25; %% andpe m núme os alea o ios sin que se
epi an en una misma ila pa a que la ciudad solo se epi a una ez
- poblacion(i,:)= ec o ;
- i=i+1;

ANEXO 4. Algo i mo gené ico
102
102
- end
-
-
- end
- Función obje i o
unc ion[ un_obje i o]= unObje i o(poblacion, iempos, am_poblacion)
%En es a unción se a a e alua los iempos de cada uno de los caminos gene ados en
pob_inicial
un_obje i o=ze os( am_poblacion,1);% ec o columna que end á los iempos de cada
u a c eada an e io men e
p=[ones( am_poblacion,1) poblacion ones( am_poblacion,1)];%A las poblaciones c eadas
en pob_inical se le añade la ciudad de en ada y salida.
=0;
o i=1: am_poblacion
o j=1:25 % n
= + iempos(p(i,j),p(i,j+1));
j=j+1;
end
un_obje i o(i,1)= ;
=0;
i=i+1;
end
end
- Selección de o neo
unc ion [num_descendien es]=sel_ o neo( un_obje i o, am_poblacion)
% es a selección es a basada en ealiza o neos en e k indi iduos y
% escoge del de mejo .obje i o
% oy a escoge o neo en e dos indi iduos
k=2;
comp=ze os(k,2);
num_descendien es=ze os( am_poblacion,1);% ec o columna con el núme o de
descendien es
while sum(num_descendien es)< am_poblacion
i=1;
while i<=k
al= loo (( am_poblacion)* and+1);% se escoge un camino a bi a iamen e
i al ~= comp(:,2) %pa a que no compa e el mismo camino
comp(i,:)=[ un_obje i o(al,1) al]; % .obj y camino
i=i+1;
end
end
[min_comp pob]=min(comp(:,1)); %mínimo del o neo y su camino
103
num_descendien es(comp(pob,2),1)=num_descendien es(comp(pob,2),1)+1;
%cada camino o pad e end á unos descendien es, aquí se e cuan os
%descendien es iene cada camino
end
end
- Recombinación
unc ion
[poblacion]= ecombinacion(num_descendien es,poblacion,p ob_ ecombinacion, am_poblacion
)
%Se a a u iliza el mé odo de ecombinación de un pun o, pa a los caminos
%ganado es en la selección de o neo se an a combina , es deci , cada
%camino a a man ene sus p ime as u as y a pa i de cie o pun o end á
%las u as de o o camino.
caminos_op =ze os( am_poblacion,24);% ma iz que end á a los caminos más óp imos
ob enidos en la selección de o neo
i=1;
% aho a se gua da en esa ma iz an e io los caminos con sus u as
while max(num_descendien es)~= 0
[descendien es camino]=max(num_descendien es);
o aux=1:descendien es
caminos_op (i,:)=poblacion(camino,:);
i=i+1;
end
num_descendien es(camino,1)=0;
end
x=[];
i=0;
while size(caminos_op ,1)~=0 %has a eco e odos los caminos más óp imos
camino1=caminos_op (1,:); %p ime camino
al= loo ((size(caminos_op ,1)-1)* and+2); %pa a elegi o o camino
camino2=caminos_op (al,:);%segundo camino
caminos_op ([1 al],:)=[];%se bo an ambos caminos
i p ob_ ecombinacion>= and % si se ecombinan c ea o os caminos combinación de
ambos
pun o_ ecomb= loo ((3)* and+1);
c1=camino1;
c2=camino2;
o j=1:pun o_ ecomb
pa e1= ind(c2(1,:)==camino1(1,j));
i pa e1~=0
c2(pa e1)=[];
end
pa e2= ind(c1(1,:)==camino2(1,j));
i pa e2~=0
ANEXO 4. Algo i mo gené ico
104
104
c1(pa e2)=[];
end
end
i=i+1;
x(i,:)=[camino1(1,1:pun o_ ecomb) c2];
i=i+1;
x(i,:)=[camino2(1,1:pun o_ ecomb) c1];
else %si no se ecombinan deja los mismos caminos
i=i+1;
x(i,:)=camino1;
i=i+1;
x(i,:)=camino2;
end
end
poblacion=x;
end
- Mu ación
- unc ion [poblacion]=mu acion(poblacion,p ob_mu acion, am_poblacion);
-
- %en es e apa ado se a a cambia algún camino al aza pa a pod á alcanza
- %una mejo .obj que no se haya de ec ado en la ecombinación. Se le asigna
- %una p obabilidad de mu ación baja po lo que pocas eces se a a da una
- % ans o mación de un camino.
-
- %pa a un camino elegido al aza se in e cambian el o den de dos de sus
- %ciudades
- i p ob_mu acion>= and
- camino_mu a= loo (( am_poblacion)* and+1);
- ciudad1= loo (24* and+1);
- ciudad2=ciudad1;
- while ciudad1==ciudad2
- ciudad2= loo (24* and+1);
- end
- aux=poblacion(camino_mu a,ciudad1);
- poblacion(camino_mu a,ciudad1)=poblacion(camino_mu a,ciudad2);
- poblacion(camino_mu a,ciudad2)=aux;
- end
-
- end
% k-op
clc
105
clea
% Impo he da a
[~, ~, ma izODCOLEGIOS] =
xls ead('C: Use s mnc m Desk op MIKEL US TFM iempo4.xlsx','Hoja1');
ma izODCOLEGIOS = s ing(ma izODCOLEGIOS);
ma izODCOLEGIOS(ismissing(ma izODCOLEGIOS)) = '';
iempos=ma izODCOLEGIOS;
iempos=s 2double( iempos);
n=25;
i e aciones=5000;
_ac =0;
%el siguien e ec o es el óp imo del ecino más p óximo
%si pongo el ec o óp imo una ez aplicada el 2-op el iempo disminuye un
%poco 13141 el que menos iempo dio
u a_op =[1,22,24,12,8,13,2,18,15,11,10,5,7,14,25,23,9,4,20,19,17,3,21,6,16,1];
o i=1:n
_ac = _ac + iempos( u a_op (i), u a_op (i+1));
end
o i e =1:i e aciones
%nodos que se an a in e cambia , in i iendo así pa e del ec o
% u a
nodo_cambio1=2+(10-2)* and;
nodo_cambio1= loo (nodo_cambio1)
nodo_cambio2=7+(25-7)* and;
nodo_cambio2= loo (nodo_cambio2)
i nodo_cambio1>nodo_cambio2
a=nodo_cambio1;
nodo_cambio1=nodo_cambio2;
nodo_cambio2=a;
end
i nodo_cambio1~=nodo_cambio2
nue a= u a_op (nodo_cambio1:nodo_cambio2);%pa e del ec o u a que se a
in e i
aux=nodo_cambio2-nodo_cambio1+1;
nue a=nue a(aux:-1:1);% ec o in e ido
nue a_ u a=[ u a_op (1:nodo_cambio1-1) nue a u a_op (nodo_cambio2+1:n+1)];
1=0;
o i=1:n
1= 1+ iempos(nue a_ u a(i),nue a_ u a(i+1));
end
1
i 1<= _ac
_ac = 1;
u a_op =nue a_ u a;
ANEXO 7. RELACIÓN ÍNDICE-COLEGIO
112
112
ANEXO 7. RELACIÓN ÍNDICE-COLEGIO
clc
clea
%algo i mo pa a elaciona cada índice del clús e con el colegio
%co espondien e
g upo1=[1,7,10,11,17,20,28,32,33,35,47,51,59,72,78,86,90,95,96,115,125,143,146,149,155
,160,161,162,163,165]
g upo2=[1,2,5,6,8,16,19,21,25,26,36,37,39,40,43,44,45,48,50,52,53,54,58,61,62,63,65,66
,67,71,88,91,92,94,98,101,104,105,106,107,112,114,119,122,123,126,127,132,135,138,141,
144,147,148,151,154,156]
g upo3=[1,3,9,12,13,14,15,18,22,24,27,29,30,31,34,41,49,55,56,57,60,64,68,69,70,74,79,
80,81,82,83,84,85,87,93,97,99,100,102,108,109,110,113,116,118,120,121,129,133,134,136,
137,139,142,145,150,158,159]
g upo4=[1,4,23,38,42,46,73,75,76,77,89,103,111,117,124,128,130,131,140,152,153,157,164
,166,167]
[~, ~, ma izODCOLEGIOS] =
xls ead('C: Use s mnc m Desk op MIKEL US TFM ma izOD_COLEGIOS.xlsx','Hoja1');
ma izODCOLEGIOS = s ing(ma izODCOLEGIOS);
ma izODCOLEGIOS(ismissing(ma izODCOLEGIOS)) = '';
iempos=ma izODCOLEGIOS;
iempos=s 2double( iempos);
% amaño g upo 1 es 30
% amaño g upo 2 es 57
% amaño g upo 3 es 58
% amaño g upo 4 es 25
_ u a_1=0;
_ u a_2=0;
_ u a_3=0;
_ u a_4=0;
%in oduzco u a ob enida po cada algo i mo de esolución
u a1=[1,22,10,3,18,24,6,8,25,30,27,12,19,4,9,21,11,23,2,7,26,15,14,5,13,20,28,17,29,1
6];
u a2=[1,50,27,47,25,29,4,21,22,48,15,13,45,18,23,6,35,40,31,16,38,39,32,26,17,46,34,5
1,24,53,30,28,52,44,54,19,11,9,7,36,43,49,56,20,55,10,3,33,5,37,8,41,42,57,14,12,2];
u a3=[1,33,45,11,53,37,27,54,31,34,43,15,8,2,46,58,21,44,6,36,29,26,40,28,51,4,9,20,1
6,39,52,14,19,47,42,25,5,49,3,7,50,55,13,12,17,23,18,24,56,30,32,22,41,35,10,38,57,48]
;
u a4=[1,22,24,12,8,13,2,18,20,19,7,15,11,5,10,14,25,23,9,4,3,17,21,6,16];
%g upo1
o i=1:30
u a_op ima_clus e 1(i)=g upo1( u a1(i));
end
u a_op ima_clus e 1=[ u a_op ima_clus e 1 1];
o i=1:30
_ u a_1= _ u a_1+ iempos( u a_op ima_clus e 1(i), u a_op ima_clus e 1(i+1));

113
end
%g upo 2
o i=1:57
u a_op ima_clus e 2(i)=g upo2( u a2(i));
end
u a_op ima_clus e 2=[ u a_op ima_clus e 2 1];
o i=1:57
_ u a_2= _ u a_2+ iempos( u a_op ima_clus e 2(i), u a_op ima_clus e 2(i+1));
end
%g upo3
o i=1:58
u a_op ima_clus e 3(i)=g upo3( u a3(i));
end
u a_op ima_clus e 3=[ u a_op ima_clus e 3 1];
o i=1:58
_ u a_3= _ u a_3+ iempos( u a_op ima_clus e 3(i), u a_op ima_clus e 3(i+1));
end
%g upo 4
o i=1:25
u a_op ima_clus e 4(i)=g upo4( u a4(i));
end
u a_op ima_clus e 4=[ u a_op ima_clus e 4 1];
o i=1:25
_ u a_4= _ u a_4+ iempos( u a_op ima_clus e 4(i), u a_op ima_clus e 4(i+1));
end
_ u a_1
u a_op ima_clus e 1
_ u a_2
u a_op ima_clus e 2
_ u a_3
u a_op ima_clus e 3
_ u a_4
u a_op ima_clus e 4
ANEXO 8. MATRIZ DE TIEMPOS
114
114
ANEXO 8. MATRIZ DE TIEMPOS
% IMPORTAR EXCEL colegios, a a és de la opción IMPORT DATA/IMPORT
SELECTION/GENERATE SCRIPT
clea
clc
o ma long
% Se up he Impo Op ions
op s = sp eadshee Impo Op ions("NumVa iables", 13);
% Speci y shee and ange
op s.Shee = "colegios_se illa";
op s.Da aRange = "A2:M168";
% Speci y column names and ypes
op s.Va iableNames = ["Cdigo", "Denominacin", "Nomb e", "Dependencia", "Domicilio",
"Localidad", "Municipio", "P o incia", "CdPos al", "Tel ono", "Enseanzas",
"Se icios", "P og amas"];
op s.Va iableTypes = ["double", "ca ego ical", "s ing", "ca ego ical", "s ing",
"ca ego ical", "ca ego ical", "ca ego ical", "double", "double", "ca ego ical",
"ca ego ical", "ca ego ical"];
op s = se a op s(op s, [3, 5], "Whi espaceRule", "p ese e");
op s = se a op s(op s, [2, 3, 4, 5, 6, 7, 8, 11, 12, 13], "Emp yFieldRule", "au o");
% Impo he da a
lis adoCOLEGIOS =
ead able("C: Use s mnc m Desk op MIKEL US TFM lis ado_COLEGIOS.xlsx", op s,
"UseExcel", alse);
% SOLO COLUMNA DE CALLES
COLEGIOS= lis adoCOLEGIOS(:,2);
COLEGIOS = able2a ay(COLEGIOS);
NOMBRES= lis adoCOLEGIOS(:,3);
NOMBRES = able2a ay(NOMBRES);
CALLE= lis adoCOLEGIOS(:,9);
CALLE = able2a ay(CALLE);
%%PARA CADA CALLE HAGO LA DIRECCIÓN DE LA PETICIÓN A GOOGLE
o i=1:167
COLEGIOS(i)= s ep(COLEGIOS(i),' ','+');
% CALLE_COLEGIOS(i,)= s ep(CALLE_COLEGIOS(i),'C/','Calle');
COLEGIOS(i)= s ep(COLEGIOS(i),'ñ','n');
COLEGIOS(i)= s ep(COLEGIOS(i),'','o');
NOMBRES(i)= s ep(NOMBRES(i),' ','+');
NOMBRES(i)= s ep(NOMBRES(i),'ñ','n');
NOMBRES(i)= s ep(NOMBRES(i),'í','i');
115
NOMBRES(i)= s ep(NOMBRES(i),'á','a');
NOMBRES(i)= s ep(NOMBRES(i),'ó','o');
NOMBRES(i)= s ep(NOMBRES(i),'é','e');
NOMBRES(i)= s ep(NOMBRES(i),'ú','u');
CALLE(i)= s ep(CALLE(i),'ñ','n');
CALLE(i)= s ep(CALLE(i),'í','i');
CALLE(i)= s ep(CALLE(i),'á','a');
CALLE(i)= s ep(CALLE(i),'ó','o');
CALLE(i)= s ep(CALLE(i),'é','e');
CALLE(i)= s ep(CALLE(i),'ú','u');
i=i+1;
end
%cambio a colegio publico
o i=1:92
COLEGIOS(i)='Colegio Publico';
i=i+1;
end
%
o i=1:167
o j=1:167
i i~=j
%%QUITO LAS COMILLAS
A1=ca ego ical(COLEGIOS(i));
B1=ca ego ical(NOMBRES(i));
C1=ca ego ical(CALLE(i));
A2=ca ego ical(COLEGIOS(j));
B2=ca ego ical(NOMBRES(j));
C2=ca ego ical(CALLE(j));
A1=cells (A1);
B1=cells (B1);
C1=cells (C1);
A2=cells (A2);
B2=cells (B2);
C2=cells (C2);
% % PET={'h ps://maps.googleapis.com/maps/api/geocode/json?add ess='};
% API DE GOOGLE
pe _ iempo={'h ps://www.google.es/maps/di /'};
%%in oduzco se illa
se ={'Se illa#'};
pe _ iempo=s ca (pe _ iempo,A1,'+',B1,'+',C1,'+','SEVILLA','/',A2,'+',B2,'+',C2,'+','
SEVILLA','/');
% pe _ iempo={'h ps://www.google.es/maps/di /'};
%
pe _ iempo=s ca (pe _ iempo,DIRECCION_LAT(i),',',DIRECCION_LON(i),'/',DIRECC
ION_LAT(j),',',DIRECCION_LON(j),'/');
pe _ iempo=cha (pe _ iempo);
iempo=u l ead(pe _ iempo);
%API DE GOOGLE
%PARA EVITAR QUE SE QUEDE EN EL LIMITE DE PETICIONES
% l = s ind( iempo,'OVER_QUERY_LIMIT');
% while l>0
ANEXO 8. MATRIZ DE TIEMPOS
116
116
% iempo=u l ead(pe _ iempo)
% l = s ind( iempo,'OVER_QUERY_LIMIT');
[ iempo,ma ches] = s spli ( iempo,{'m '},'CollapseDelimi e s', ue);
iempo= iempo(6);
iempo=cha ( iempo);
% % % % %
[ iempo,ma ches] = s spli ( iempo,{' '},'CollapseDelimi e s', ue);
iempo= iempo(2);
iempo=cha ( iempo);
[ iempo,ma ches] = s spli ( iempo,{','},'CollapseDelimi e s', ue);
iempo= iempo(2);
% iempo=cha ( iempo);
ma izOD(i,j)= iempo;
end
j=j+1
end
i=i+1
end
xlsw i e('ma izOD_COLEGIOS.xlsx',ma izOD);
- Limpieza de de los iempos
op s = sp eadshee Impo Op ions("NumVa iables", 167);
% Speci y shee and ange
op s.Shee = "Hoja1";
op s.Da aRange = "A1:FK167";
% Speci y column names and ypes
op s.Va iableNames = ["Va Name1", "Va Name2", "Va Name3", "Va Name4",
"Va Name5", "Va Name6", "Va Name7", "Va Name8", "Va Name9", "Va Name10",
"Va Name11", "Va Name12", "Va Name13", "Va Name14", "Va Name15", "Va Name16",
"Va Name17", "Va Name18", "Va Name19", "Va Name20", "Va Name21", "Va Name22",
"Va Name23", "Va Name24", "Va Name25", "Va Name26", "Va Name27", "Va Name28",
"Va Name29", "Va Name30", "Va Name31", "Va Name32", "Va Name33", "Va Name34",
"Va Name35", "Va Name36", "Va Name37", "Va Name38", "Va Name39", "Va Name40",
"Va Name41", "Va Name42", "Va Name43", "Va Name44", "Va Name45", "Va Name46",
"Va Name47", "Va Name48", "Va Name49", "Va Name50", "Va Name51", "Va Name52",
"Va Name53", "Va Name54", "Va Name55", "Va Name56", "Va Name57", "Va Name58",
"Va Name59", "Va Name60", "Va Name61", "Va Name62", "Va Name63", "Va Name64",
"Va Name65", "Va Name66", "Va Name67", "Va Name68", "Va Name69", "Va Name70",
"Va Name71", "Va Name72", "Va Name73", "Va Name74", "Va Name75", "Va Name76",
"Va Name77", "Va Name78", "Va Name79", "Va Name80", "Va Name81", "Va Name82",
"Va Name83", "Va Name84", "Va Name85", "Va Name86", "Va Name87", "Va Name88",
"Va Name89", "Va Name90", "Va Name91", "Va Name92", "Va Name93", "Va Name94",
"Va Name95", "Va Name96", "Va Name97", "Va Name98", "Va Name99", "Va Name100",
"Va Name101", "Va Name102", "Va Name103", "Va Name104", "Va Name105",
"Va Name106", "Va Name107", "Va Name108", "Va Name109", "Va Name110",
"Va Name111", "Va Name112", "Va Name113", "Va Name114", "Va Name115",
"Va Name116", "Va Name117", "Va Name118", "Va Name119", "Va Name120",
"Va Name121", "Va Name122", "Va Name123", "Va Name124", "Va Name125",
117
"Va Name126", "Va Name127", "Va Name128", "Va Name129", "Va Name130",
"Va Name131", "Va Name132", "Va Name133", "Va Name134", "Va Name135",
"Va Name136", "Va Name137", "Va Name138", "Va Name139", "Va Name140",
"Va Name141", "Va Name142", "Va Name143", "Va Name144", "Va Name145",
"Va Name146", "Va Name147", "Va Name148", "Va Name149", "Va Name150",
"Va Name151", "Va Name152", "Va Name153", "Va Name154", "Va Name155",
"Va Name156", "Va Name157", "Va Name158", "Va Name159", "Va Name160",
"Va Name161", "Va Name162", "Va Name163", "Va Name164", "Va Name165",
"Va Name166", "Va Name167"];
op s.Va iableTypes = ["s ing", "s ing", "s ing", "s ing", "s ing", "s ing",
"s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing",
"s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing",
"s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing",
"s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing",
"s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing",
"s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing",
"s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing",
"s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing",
"s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing",
"s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing",
"s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing",
"s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing",
"s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing",
"s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing",
"s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing",
"s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing",
"s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing",
"s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing",
"s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing",
"s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing", "s ing",
"s ing"];
op s = se a op s(op s, [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, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135,
136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152,
153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167],
"Whi espaceRule", "p ese e");
op s = se a op s(op s, [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, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135,
136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152,
153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167],
"Emp yFieldRule", "au o");
% Impo he da a
ma izODCOLEGIOS1 =
ead able("C: Use s mnc m Desk op MIKEL US TFM ma izOD_COLEGIOS.xlsx", op s,
"UseExcel", alse);

ANEXO 8. MATRIZ DE TIEMPOS
118
118
b=[];
clea op s
o i=1:167
a=ma izODCOLEGIOS1(i,:);
a= able2a ay(a)
o j=1:167
i i~=j
a(j)= s ep(a(j),'[','');
end
j=j+1
end
b=[b;a];
i=i+1
end
o i=1:167
o j=1:167
b(i,j)= s ep(b(i,j),"'","");
end
end
op s = sp eadshee Impo Op ions("NumVa iables", 167);
% Speci y shee and ange
op s.Shee = "Hoja1";
op s.Da aRange = "A1:FK167";
% Speci y column names and ypes
op s.Va iableNames = ["NaN", "Va Name2", "Va Name3", "Va Name4", "Va Name5",
"Va Name6", "Va Name7", "Va Name8", "Va Name9", "Va Name10", "Va Name11",
"Va Name12", "Va Name13", "Va Name14", "Va Name15", "Va Name16", "Va Name17",
"Va Name18", "Va Name19", "Va Name20", "Va Name21", "Va Name22", "Va Name23",
"Va Name24", "Va Name25", "Va Name26", "Va Name27", "Va Name28", "Va Name29",
"Va Name30", "Va Name31", "Va Name32", "Va Name33", "Va Name34", "Va Name35",
"Va Name36", "Va Name37", "Va Name38", "Va Name39", "Va Name40", "Va Name41",
"Va Name42", "Va Name43", "Va Name44", "Va Name45", "Va Name46", "Va Name47",
"Va Name48", "Va Name49", "Va Name50", "Va Name51", "Va Name52", "Va Name53",
"Va Name54", "Va Name55", "Va Name56", "Va Name57", "Va Name58", "Va Name59",
"Va Name60", "Va Name61", "Va Name62", "Va Name63", "Va Name64", "Va Name65",
"Va Name66", "Va Name67", "Va Name68", "Va Name69", "Va Name70", "Va Name71",
"Va Name72", "Va Name73", "Va Name74", "Va Name75", "Va Name76", "Va Name77",
"Va Name78", "Va Name79", "Va Name80", "Va Name81", "Va Name82", "Va Name83",
"Va Name84", "Va Name85", "Va Name86", "Va Name87", "Va Name88", "Va Name89",
"Va Name90", "Va Name91", "Va Name92", "Va Name93", "Va Name94", "Va Name95",
"Va Name96", "Va Name97", "Va Name98", "Va Name99", "Va Name100",
"Va Name101", "Va Name102", "Va Name103", "Va Name104", "Va Name105",
"Va Name106", "Va Name107", "Va Name108", "Va Name109", "Va Name110",
"Va Name111", "Va Name112", "Va Name113", "Va Name114", "Va Name115",
"Va Name116", "Va Name117", "Va Name118", "Va Name119", "Va Name120",
"Va Name121", "Va Name122", "Va Name123", "Va Name124", "Va Name125",
"Va Name126", "Va Name127", "Va Name128", "Va Name129", "Va Name130",
119
"Va Name131", "Va Name132", "Va Name133", "Va Name134", "Va Name135",
"Va Name136", "Va Name137", "Va Name138", "Va Name139", "Va Name140",
"Va Name141", "Va Name142", "Va Name143", "Va Name144", "Va Name145",
"Va Name146", "Va Name147", "Va Name148", "Va Name149", "Va Name150",
"Va Name151", "Va Name152", "Va Name153", "Va Name154", "Va Name155",
"Va Name156", "Va Name157", "Va Name158", "Va Name159", "Va Name160",
"Va Name161", "Va Name162", "Va Name163", "Va Name164", "Va Name165",
"Va Name166", "Va Name167"];
op s.Va iableTypes = ["double", "double", "double", "double", "double", "double",
"double", "double", "double", "double", "double", "double", "double", "double",
"double", "double", "double", "double", "double", "double", "double", "double",
"double", "double", "double", "double", "double", "double", "double", "double",
"double", "double", "double", "double", "double", "double", "double", "double",
"double", "double", "double", "double", "double", "double", "double", "double",
"double", "double", "double", "double", "double", "double", "double", "double",
"double", "double", "double", "double", "double", "double", "double", "double",
"double", "double", "double", "double", "double", "double", "double", "double",
"double", "double", "double", "double", "double", "double", "double", "double",
"double", "double", "double", "double", "double", "double", "double", "double",
"double", "double", "double", "double", "double", "double", "double", "double",
"double", "double", "double", "double", "double", "double", "double", "double",
"double", "double", "double", "double", "double", "double", "double", "double",
"double", "double", "double", "double", "double", "double", "double", "double",
"double", "double", "double", "double", "double", "double", "double", "double",
"double", "double", "double", "double", "double", "double", "double", "double",
"double", "double", "double", "double", "double", "double", "double", "double",
"double", "double", "double", "double", "double", "double", "double", "double",
"double", "double", "double", "double", "double", "double", "double", "double",
"double", "double", "double", "double", "double", "double", "double", "double",
"double"];
% Impo he da a
ma izODCOLEGIOS =
ead able("C: Use s mnc m Desk op MIKEL US TFM ma izOD_COLEGIOS.xlsx", op s,
"UseExcel", alse);
ma izODCOLEGIOS = able2a ay(ma izODCOLEGIOS);
ab=ma izODCOLEGIOS;
clea op s
ANEXO 9. LATITUD-LONGITUD
120
120
ANEXO 9. LATITUD-LONGITUD
%%A pa i de la in o mación del excel con nomb e, calle y código pos al,
%%se ob u o la i ud y longi ud de cada cen o educa i o
clea
clc
o ma long
op s = sp eadshee Impo Op ions("NumVa iables", 13);
% Speci y shee and ange
op s.Shee = "colegios_se illa";
op s.Da aRange = "A2:M168";
% Speci y column names and ypes
op s.Va iableNames = ["Cdigo", "Denominacin", "Nomb e", "Dependencia",
"Domicilio", "Localidad", "Municipio", "P o incia", "CdPos al", "Tel ono",
"Enseanzas", "Se icios", "P og amas"];
op s.Va iableTypes = ["double", "ca ego ical", "s ing", "ca ego ical",
"s ing", "ca ego ical", "ca ego ical", "ca ego ical", "double", "double",
"ca ego ical", "ca ego ical", "ca ego ical"];
op s = se a op s(op s, [3, 5], "Whi espaceRule", "p ese e");
op s = se a op s(op s, [2, 3, 4, 5, 6, 7, 8, 11, 12, 13], "Emp yFieldRule",
"au o");
% Impo he da a
lis adoCOLEGIOS =
ead able("C: Use s mnc m Desk op MIKEL US TFM lis ado_COLEGIOS.xlsx", op s,
"UseExcel", alse);
COLEGIOS= lis adoCOLEGIOS(:,2);
COLEGIOS = able2a ay(COLEGIOS);
NOMBRES= lis adoCOLEGIOS(:,3);
NOMBRES = able2a ay(NOMBRES);
%%PARA CADA CALLE HAGO LA DIRECCIÓN DE LA PETICIÓN A GOOGLE
o i=1:167
%
COLEGIOS(i)= s ep(COLEGIOS(i),' ','+');
% CALLE_COLEGIOS(i,)= s ep(CALLE_COLEGIOS(i),'C/','Calle');
COLEGIOS(i)= s ep(COLEGIOS(i),'ñ','n');
NOMBRES(i)= s ep(NOMBRES(i),' ','+');
NOMBRES(i)= s ep(NOMBRES(i),'ñ','n');
i=i+1;
end
121
DIRECCION_LAT=s ings([167,1]);
DIRECCION_LON=s ings([167,1]);
%
o i=1:167
%%QUITO LAS COMILLAS
A=ca ego ical(COLEGIOS(i));
B=ca ego ical(NOMBRES(i));
A=cells (A);
B=cells (B);
% % PET={'h ps://maps.googleapis.com/maps/api/geocode/json?add ess='}
% es a e a una ins ucción pa a la API
%
PET={'h ps://maps.google.com/?q='};
%%in oduzco se illa
se ={'Se illa#'};
PET_GOOGLE= s ca (PET,A,B,se );
PET_GOOGLE= cha (PET_GOOGLE);
DIRECCION=u l ead(PET_GOOGLE);
% INSTRUCCIONES PARA LA API
% %PARA EVITAR QUE SE QUEDE EN EL LIMITE DE PETICIONES
% %
% % k = s ind(DIRECCION,'OVER_QUERY_LIMIT');
% % while k>0
% % DIRECCION=u l ead(PET_GOOGLE)
% % k = s ind(DIRECCION,'OVER_QUERY_LIMIT')
% % end
% [C,ma ches] = s spli (DIRECCION,{'"loca ion"
','"loca ion_ ype"'},'CollapseDelimi e s', ue);%%CON ESTE COMANDO SEPARO LA
CADENA EN TRES ME INTERESA LA DE EN MEDIO LAT LON
[C,ma ches] =
s spli (DIRECCION,{'window.APP_INITIALIZATION_STATE='},'CollapseDelimi e s', u
e);
C=C(2);
C=cha (C);
[C,ma ches] = s spli (C,{']'},'CollapseDelimi e s', ue);
C=C(1);
C=cha (C);
[C,ma ches] = s spli (C,{','},'CollapseDelimi e s', ue);
DIRECCION_LAT(i,1)=C(3);%%la i ud
DIRECCION_LON(i,1)=C(2);%%longi ud
end
%CAMBIOS MANUALES FACILES DE ENCONTRAR PQ SALE MI LAT Y LONG