T abajo de Fin de Más e
Op imización de anspo es de epa ables en el
sec o ae onáu ico
Au o : An onio Blanch Rod íguez
Tu o : An onio Ja ie Gallego Len
Escuela Técnica Supe io de Ingenie ía
Uni e sidad de Se illa
Se illa, 2023
T abajo de Fin de Más e
Más e en Ingenie ía Indus ial
Op imización de anspo es de epa ables en el
sec o ae onáu ico
Au o :
An onio Blanch Rod íguez
Tu o : An onio Ja ie Gallego Len
Escuela Técnica Supe io de Ingenie ía
Uni e sidad de Se illa
Se illa, 2023
A mi amilia y a mi pa eja,
po hace lo odo an ácil

i
Resumen
En el p esen e abajo se analiza el lujo de ma e iales y equipos epa ables de una Emp esa Ae onáu ica desde
un almacén cen al si uado en España hacia di e en es cen os epa ado es en Ingla e a, y ice e sa. El
obje i o es educi el iempo de ánsi o o al de es os equipos an o en su ayec o a epa a como en el e o no
una ez epa ado, in en ando no inc emen a el cos e. Pa a ello, se esuel en los p oblemas de ubicación
óp ima de un cen o de dis ibución eniendo en cuen a la ubicación geog á ica y demanda de los cen os
epa ado es, y pos e io men e un p oblema de u ado de ehículos. Pa a es e segundo p oblema, se lle a a
cabo un ex enso es udio del es ado del a e y se de ine el p oblema como un VRPPD, que se esuel e median e
mé odos heu ís icos. Pa a e alua la bondad de la solución p opues a, se lle a a cabo un análisis exhaus i o de
los iempos de ánsi o y cos es log ados con es a solución, simulando las u as que se deben lle a a cabo
du an e un año.
iii
Abs ac
This p ojec analyses he low o epai pa s o an Ae onau ical Company om a cen al wa ehouse loca ed in
Spain o di e en epai cen es in England, and back. The objec i e is o educe he o al lead ime o his
ma e ials bo h on i s jou ney o epai and on i s e u n once epai ed, ying no o inc ease he cos . To
achie e his, he p oblems o op imal loca ion o a dis ibu ion cen e, aking in o accoun he geog aphical
loca ion and demand o he epai cen es, and hen a p oblem o ehicle ou ing a e sol ed. Fo his second
p oblem, an ex ensi e s a e-o - he-a s udy is ca ied ou and he p oblem is de ined as a VRPPD, which is
sol ed using heu is ic me hods. To e alua e he goodness o he p oposed solu ion, an exhaus i e analysis o
he lead imes and cos s achie ed wi h his solu ion is made, simula ing he ou es o be ca ied ou du ing a
yea .

xi
Ac ónimos y ab e iaciones
3PL
Thi d Pa y Logis ics
4PL
Fou h Pa y Logis ics
ADR
Acco d eu opéen ela i au anspo des ma chandises Dange euses pa Rou e
AOG
Ai c a On G ound
AWB
Ai Waybill
BL
Bill o Landing
BR
Business Rule
CEDI
CEn o de DIs ibución
CMR
Con en ion ela i e au con a de anspo in e na ional de Ma chandises pa Rou e
CVRP
Capaci ed VRP
DUA
Documen o Único Adminis a i o
DVRP
Dis ance VRP
EAR
Expo Adminis a ion Regula ions
HazMa
Haza dous Ma e ial
InCoTe ms
In e na ional Comme cial Te ms
ITAR
In e na ional T a ic in A ms Regula ions
Loc-ID
Loca ion ID
LT
Lead Time
MDVRP
Mul iple Depo VRP
PL
P o eedo Logís ico
PN
Pa Numbe
PVRP
Pe iodic VRP
RN
Repai No i ica ion
RTN
Rou ine
SDVRP
Spli Deli e y VRP
SVRP
S ochas ic VRP
TR
T anspo Reques
TSP
T a eling Salesman P oblem
UE
Unión Eu opea
VBA
Visual Basic o Applica ions
VRP
Vehicle Rou ing P oblem
VRPB
VRP wi h Backhauls
VRPPD
VRP wi h Pickup and Deli e y
VRPSF
VRP wi h Sa elli e Facili ies
VRPTW
VRP wi h Time Windows
1
1 INTRODUCCIÓN
1.1 Obje i os
El p incipal obje i o del p esen e abajo es analiza y diseña una solución pa a el anspo e de ma e iales y
equipos epa ables de una Emp esa Ae onáu ica desde un almacén cen al si uado en España hacia di e en es
cen os epa ado es en Ingla e a, y ice e sa.
Pa a ello, se a a analiza el es ado ac ual de es e lujo de anspo es, an o en el ámbi o económico como a
ni el de iempos de ánsi o (Lead Times). Una ez lle ado a cabo es e análisis, se p opond án di e en es
soluciones, diseñando un algo i mo heu ís ico que ayude a la óp ima ges ión de la ed de anspo e. Además,
se de ini án en base a da os de cos es y iempos de en ega, pa áme os como el amaño de la lo a, la
ecuencia o el ipo de anspo e.
Figu a 1.1. Modelos mili a es a) Ai bus A400M y b) Boeing C-17
1.2 Alcance
La Emp esa Ae onáu ica a es udio desea mejo a los iempos de sus se icios pos en a, aspi ando a educi los
un 20%. Den o de odo el lujo del ma e ial, el anspo e iene un al o impac o en es os iempos, po lo que se
p opone educi el Lead Time de anspo e en un 30%. Es e p oyec o se cen a á en la educción del Lead
Time de anspo e de elemen os epa ables y epa ados, más conc e amen e aquellos que ayan o uel an de
cen os epa ado es si uados en Reino Unido, ya que son ac ualmen e los más al os en elación con la dis ancia
al almacén cen al.
El esul ado del p oyec o debe se una solución de comp omiso en e el ex a cos e que la emp esa debe
asumi y los iempos de ánsi o ob enidos, pe o en cualquie caso se debe supe a el 30% de educción de LT
sin inc emen a más del 5% el cos e de anspo e.
In oducción
2
1.3 P incipales S akeholde s del P oyec o
Al se un p oyec o en el que se in oluc an mul i ud de pa es in e esadas ( ambién llamadas s akeholde s), los
in e eses de cada uno de ellos y el papel que juegan de ca a a alcanza el obje i o deben se enidos en cuen a,
y po ello es impo an e iden i ica los. Los p incipales s akeholde s del p oyec o son:
 El equipo logís ico de la Emp esa Ae onáu ica
 El equipo de inanzas de la Emp esa Ae onáu ica
 El ope ado logís ico del 4PL
 Los ope ado es logís icos de los di e en es 3PLs
 El almacén cen al de la Emp esa Ae onáu ica
 Los di e en es Cen os Repa ado es que abajan pa a la Emp esa Ae onáu ica
1.4 Es uc u a del T abajo
El abajo es á es uc u ado en 8 g andes capí ulos, o ien ados a log a los obje i os desc i os p e iamen e a la
ez que se exponen g adualmen e los concep os y mé odos u ilizados.
En p ime luga , se lle a á a cabo una b e e in oducción al en o no ae onáu ico, cen ado en la ges ión de
ma e iales y más conc e amen e en los lujos de anspo e pa a se icios pos en a.
Pos e io men e, se expone el p oblema conc e o que debemos esol e , compa ando la si uación p e ia al
es udio (AS-IS) y las posibles al e na i as que pueden ayuda nos a log a un escena io que cumpla los
obje i os ma cados (TO-BE).
Una ez de inido el p oblema y expues as las posibles soluciones, di idimos la esolución del mismo en dos
ases. La p ime a a a de encon a la ubicación óp ima pa a la colocación de un cen o de dis ibución,
usando mé odos numé icos y eniendo en cuen a ac o es ambien ales y económicos. En la segunda ase, y una
ez de inido el pun o del que pa i án los ehículos, se a a de esol e un p oblema de u ado de ehículos.
En es e capí ulo se lle a a cabo una explo ación del con ex o his ó ico y del es ado del a e an o de los ipos de
p oblemas de u ado de ehículo, pa a encon a el que más se ajus e a la solución que que emos implan a ,
como de los mé odos de esolución. Una ez modelado el p oblema y elegido los mé odos de esolución, se
p ocede a diseña una aplicación en VBA pa a esol e el mismo.
Pa a e alua la idoneidad de la solución y la apo ación del p oyec o a mejo a el desempeño an o económico
como en elación a los iempos de la Emp esa Ae onáu ica, se lle a a cabo un análisis compa ando los da os
del AS-IS y del TO-BE.
Po úl imo, se esumen los p incipales log os del p oyec o y se exponen las conclusiones del mismo, poniendo
ambién el oco en posibles abajos u u os elacionados que pudie an mejo a la solución ob enida.
3
3
Op imización de anspo es de epa ables en el sec o ae onáu ico
2 CONTEXTO
En es e capí ulo se desc ibi án los di e en es lujos de ma e iales que se lle an a cabo en una Emp esa
Ae onáu ica. Hay que dis ingui los lujos de P oducción de aquellos de Se icios, que son los que nos a ec an
en es e abajo. Los lujos de P oducción son odos aquellos mo imien os de ma e ial ( anspo es) que son
necesa ios pa a asegu a el abas ecimien o de ma e iales y equipos pa a la p oducción de a iones de se ie. Sin
emba go, los lujos de Se icios son aquellos que abas ecen de ma e iales y equipos a los a iones una ez son
en egados a clien e, es deci , son anspo es de ma e iales pa a se icios pos - en a.
La ges ión de ambos lujos es independien e y es lle ada a cabo po depa amen os di e en es, aunque es
posible busca sine gias en soluciones de anspo e en e ambos. En los dos casos, el se icio de anspo e
es á subcon a ado, y no es la Emp esa Ae onáu ica la que lle a a cabo los mo imien os de ma e ial po sus
p opios medios, como se explica á con de alle en la sección 2.2 (Es uc u a de los P o eedo es Logís icos).
Con la ges ión del anspo e subcon a ada de es a o ma, cuando se quie a solici a un anspo e de
me cancía, se á necesa io c ea un eque imien o de anspo e (TR, po las siglas de T anspo Reques en
inglés) que se á el iden i icado único del mismo, independien emen e del anspo is a que lo lle e a cabo.
Es a e e encia se e ie e al en ío, no solo al ma e ial. En o as palab as, un ma e ial que deba se en iado
desde el clien e al almacén cen al de la Emp esa Ae onáu ica, y de es e almacén cen al al cen o epa ado ,
end á dos TRs, uno po cada anspo e, a pesa de se el mismo ma e ial. Po o a pa e, un TR pod á
con ene a ios ma e iales, siemp e que el o igen y el des ino sea el mismo. Es a p ác ica es conocida como
consolidación, y lle a consigo mul i ud de en ajas en e a ene un TR po cada ma e ial, como puede se la
meno ges ión que es necesa ia, la mejo azabilidad o la posibilidad de op imiza los cos es de anspo e.
En es e capí ulo se a a á de desc ibi el p oceso comple o de anspo e pa a cualquie o igen, des ino y ipo
de ma e ial, desde la c eación del TR en o igen has a la ecepción del ma e ial en des ino, incluyendo odos los
p ocesos adminis a i os y logís icos que puedan se necesa ios en e medias.
2.1 Flujo de ma e iales
El lujo de ma e iales y equipos pa a Se icios (aquellos que dan sopo e al clien e una ez el a ión ha salido
de la ac o ía y ha sido en egado) puede di idi se en e Repues os y Repa ables. A con inuación se desc iben
las ca ac e ís icas de cada uno de ellos:
2.1.1 Repues os
Los Repues os o Spa e Pa s son ma e iales nue os que son en iados al clien e pa a eemplaza a o o que es
de ec uoso. En es e caso, el ma e ial de ec uoso no es epa ado, sino que se cambia po o o que nunca ha sido
epa ado ni ensamblado en ningún o o a ión.
El lujo de ma e iales, en es e caso, suele se el siguien e: la Emp esa Ae onáu ica comp a di e en es Pa

Con ex o
4
Numbe s (P/N) nue os a di e en es p o eedo es o supplie s y los almacena en su Almacén Cen al. Es e
anspo e desde p o eedo al almacén puede lle a se a cabo median e los medios del supplie o median e los
medios de la Emp esa Ae onáu ica (aunque subcon a e es e se icio), dependiendo del Inco e m aco dado en
el con a o ( e sección 2.3). Cuando un clien e equie a de ese P/N, es e se le en ia á di ec amen e desde el
Almacén Cen al, lo que educe los iempos logís icos y hace posible una mejo ges ión. Además, el paso po
almacén asegu a un con ol de calidad que no se lle a ía a cabo en caso de que uese el supplie el que en iase
di ec amen e al clien e.
Figu a 2.1. Flujo de Spa es
Además de pa a eemplaza equipos o pa es de ec uosas, un clien e puede comp a Spa e Pa s pa a
ac ualiza la e sión de su a ión o pa a hace se con su p opio s ock de epues os, y así dispone de los
ma e iales al momen o en que los equie a.
2.1.2 Repa ables
A di e encia de los Spa e Pa s, las Repa ables son ma e iales que sí han sido p e iamen e mon ados en el
a ión. Pa a lle a a cabo epa aciones, mejo as o eajus es, es os ma e iales o equipos se desensamblan del
a ión y son en iados con una Repai No i ica ion (RN) al almacén cen al de la Emp esa Ae onáu ica, donde
se e alúan los daños y se edi eccionan al Cen o Repa ado más adecuado. Es e anspo e es el obje o de
es udio en es e abajo, así como el anspo e de uel a desde Cen o Repa ado has a el Almacén Cen al una
ez el equipo ha sido epa ado. Una ez allí, el equipo de Calidad del almacén se enca ga de e i ica que el
ma e ial cumple los es ánda es de calidad an o ísica como documen almen e, y se en ía de nue o al clien e
pa a que pueda ol e a mon a lo en su a ión.
Figu a 2.2. Flujo de Repai s
5
5
Op imización de anspo es de epa ables en el sec o ae onáu ico
O a posibilidad pa a lle a a cabo es e lujo comple o es e i a el paso in e medio po el almacén cen al y que
el clien e le en íe el ma e ial di ec amen e al Cen o Repa ado y es e ambién se lo de uel a di ec amen e.
Es e ipo de lujo lle a consigo algunas en ajas, pe o ambién algunos incon enien es, po lo que solo se debe
lle a a cabo en casuís icas pa icula es donde las en ajas supe en a los incon enien es. La p incipal en aja
de es a p ác ica, llamada Di ec Shipmen , es la educción de iempos logís icos al pasa de 4 a 2 anspo es.
Sin emba go, algunos incon enien es que pueden su gi son los siguien es:
 Imposibilidad de e i ica la calidad, po lo que sólo se á posible pa a clien es en los que exis a un
equipo de la Emp esa Ae onáu ica en sus ins alaciones.
 Meno posibilidad de consolidación, ya que hab á muchas más combinaciones de o ígenes-des inos.
 P oblemas aduane os, ya que los ma e iales del clien e son impo ados y eexpo ados po la Emp esa
Ae onáu ica en el p oceso no mal, y en es e caso end ían que se impo ados y eexpo ados po los
Cen os Repa ado es, asumiendo las asas y a anceles co espondien es.
 Meno con ol de la documen ación y ac u as.
2.2 Es uc u a de los P o eedo es Logís icos
En es a sección se desc ibi á la es uc u a de los di e en es Ope ado es Logís icos que in e ienen en el
p oceso de anspo e. Es a es uc u a se di ide en di e en es P o eedo es Logís icos (PL), que se clasi ican
según los se icios que desempeñen los di e en es ope ado es logís icos y su g ado de ex e nalización. En la
siguien e igu a se pueden iden i ica los cua o ni eles de P o eedo es Logís icos de es a es uc u a:
Figu a 2.3. Es uc u a de P o eedo es Logís icos
 1PL:
Es el eslabón más bajo de la pi ámide y hace e e encia a la compañía (o pe sona indi idual) que iene
su p opio ehículo o lo a de ehículos y es capaz de anspo a ma e ial de un luga a o o. Los
p o eedo es logís icos de es e ni el suelen se agencias de anspo e que son subcon a adas po o as
emp esas (gene almen e 2PL), de mane a que ellos se enca gan de la comp a y manu ención de la
lo a, así como de la ges ión de los conduc o es, pe o no se hacen ca go de almacenajes ni o as
Con ex o
6
ope aciones logís icas de mayo ni el. Pa a los p opósi os de es e ex o, la Emp esa Ae onáu ica no
end á con ac o con es os p o eedo es logís icos, dejando que los PL de mayo ni el puedan
subcon a a los se icios que ean necesa ios.
 2PL:
Es e ni el engloba el anspo e de ma e ial desde un á ea geog á ica a o a, ya sea po ca e e a, ma ,
ai e, e c. Es e eslabón puede se , po ejemplo, una pequeña emp esa de mensaje ía, una compañía
e o ia ia, una ae olínea o cualquie o a compañía de anspo e en un segmen o especí ico de la
cadena logís ica.
La p incipal di e encia con espec o a los 1PL es que el 2PL abaja en un ámbi o más amplio y se
enca ga de coo dina la lo a y las ope aciones de anspo e, aunque los se icios que o ezca sean
simila es. Es muy habi ual que los 3PL subcon a en a dis in os 2PL en unción de la zona geog á ica,
el ipo de anspo e, la disponibilidad y o os ac o es.
Al igual que en el caso an e io , la Emp esa Ae onáu ica no con a a á di ec amen e a los 2PL, sino
que deja á es a ges ión al 3PL, aunque la solución p opues a implique una coo dinación en e ambos.
 3PL:
En es e ni el se incluyen las p incipales emp esas de anspo e y logís ica, ya sea con su p opia lo a
o median e subcon a ación a un 2PL, y con espacio de almacenaje. La capacidad de almacenaje les
pe mi e dispone de los ma e iales más ce ca del clien e inal y, po an o, en ega en meno iempo.
También les pe mi e usa sus almacenes como c oss-dock (muelle c uzado) y hace uso de di e en es
2PLs o di e en es edes del mismo.
Es e ni el ambién incluye soluciones de so wa e in o má ico logís ico y se icios de análisis, pa a
segui y as ea el es ado de en ega de los dis in os en íos. Es a logís ica de e ce os p opo ciona
odos los se icios mencionados y ambién ges iona cualquie obs áculo o incon enien e que su ja
du an e el p oceso, libe ando a los 2PL de es os p ocesos.
Los 3PL, al se ope ado es de más al o ni el, o ecen soluciones pe sonalizadas según las necesidades
de la emp esa con a an e, de sus clien es y del ipo de negocio que lle an a cabo. Como es os
acue dos suelen se a la go plazo, el ope ado logís ico puede i ap endiendo de la logís ica de su
clien e e i adap ando y op imizando sus p ocesos. Es e suele se un abajo conjun o y el análisis que
se a a lle a a cabo en es e abajo es un ejemplo del mismo.
 4PL:
A di e encia de los 3PL, el 4PL no lle a a cabo el anspo e ísico, sino que ac úa como ges o y
supe iso de las ope aciones logís icas. En algunas ocasiones, la p opia emp esa con a an e puede
ac ua como 4PL, pe o en emp esas g andes como es es e caso, se suele subcon a a es e se icio a un
ope ado logís ico ex e no que se enca gue de asigna cada TR que c ea el almacén al 3PL más
adecuado eniendo en cuen a las necesidades del clien e, la p io idad del en ío, el ipo de anspo e y
7
7
Op imización de anspo es de epa ables en el sec o ae onáu ico
eniendo en cuen a cie as es icciones como la documen ación y el ipo de ma e ial a anspo a .
2.3 Inco e ms
Los Inco e ms son los é minos y condiciones de una ansacción in e nacional de comp a en a y es ipulan
cuándo y dónde se p oduce la ans e encia del iesgo y la obligación del cos e, quién es esponsable en cada
pun o del anspo e y o os ac o es elacionados con dichas ansacciones. El é mino Inco e m es la
ab e ia u a de "In e na ional Comme cial Te ms".
Los Inco e ms ue on c eados po la ICC (In e na ional Chambe o Comme ce) en 1936 y son e isados
no malmen e cada 10 años pa a ac ualiza los, eno a los y sus i ui é minos que hoy en día ya no se u ilicen.
Ac ualmen e, los más ac ualizados son los de 2020, y pa a di e encia las dis in as e siones es os é minos
an acompañados de un núme o que indica la ac ualización de ese é mino en conc e o.
Los Inco e ms ienen de e minados po :
 Dónde y cuándo se p oduce la ans e encia de iesgo y esponsabilidad del endedo al comp ado .
 Luga de en ega
 Responsabilidad de con a a y paga el anspo e y el segu o
 Ges ión de la documen ación po cada pa e
Según los é minos del Inco e m, se iden i ican es g upos:
 F/E: Recogida en el país de o igen
 C: Responsabilidad compa ida, llega al país de des ino (ae opue o/pue o ma í imo)
 D: En ega al clien e
La Figu a 2.4 mues a los dis in os Inco e ms en su e sión más ac ualizada. Pa a cada Inco e m y en cada
pun o, se di e encia la esponsabilidad en é minos de cos e y en é minos de iesgo, ya que puede no se la
misma pa a algunos casos.
A con inuación se desc iben los Inco e ms más usados en es e negocio, pa a un en ío desde el almacén cen al
a un Cen o Repa ado o Clien e:
 FCA: En es e caso, la única esponsabilidad de la Emp esa Ae onáu ica se ía despacha el ma e ial en
el almacén y p epa a lo pa a el anspo e (embalaje, incaje y co ec a iden i icación). Además, si el
en ío es ex acomuni a io debe enca ga se de la gene ación de la documen ación de expo ación.
 DAP: Además de lo expues o en el ejemplo del en ío con Inco e m FCA, aho a es esponsabilidad de
la Emp esa Ae onáu ica el anspo e. Pod ía hace lo po sus p opios medios, pe o en es e caso se
subcon a a a un 3PL pa a que lle e a cabo el anspo e hacia des ino. Una ez en las aduanas
aco dadas con el clien e o cen o epa ado , es esponsabilidad del consigna a io hace el despacho
aduane o, aunque el anspo e desde las aduanas has a el pun o de en ega uel e a lle a lo a cabo el
Con ex o
14
in o mación esencial sob e la ca ga.
 Requisi os de Segu idad: Es ablece medidas especí icas pa a la manipulación, ca ga y desca ga de
ma e iales pelig osos, incluyendo capaci ación y equipo de p o ección pe sonal pa a el pe sonal
in oluc ado.
Los ma e iales pelig osos se di iden en nue e clases p incipales, y cada una debe i iden i icada con al menos
una de las e ique as de la Figu a 2.7.
Figu a 2.7. Clases de ma e iales pelig osos según su clase
 Explosi os (Clase 1)
 Gases (Clase 2)
 Líquidos In lamables (Clase 3)
 Sólidos In lamables (Clase 4)
 Sus ancias Combu en es (Clase 5)
 Sus ancias Tóxicas e In ecciosas (Clase 6)
 Ma e iales Radioac i os (Clase 7)
 Co osi os (Clase 8)
 Sus ancias Pelig osas Di e sas (Clase 9)
2.9 Bussiness Rules
Cuando se gene a una pe ición de anspo e (TR), es a se debe asigna a un 3PL en e odos los que engan
elación con ac ual con la Emp esa Ae onáu ica. Es a asignación se basa an o en el cos e del en ío como en
el iempo de ánsi o o ecido, cumpliendo siemp e los eque imien os del ipo de en ío seleccionado. Ya que
muchos de los lujos son ecu en es pa a la mayo ía de emp esas, las p incipales u as de anspo e ya han

15
15
Op imización de anspo es de epa ables en el sec o ae onáu ico
sido analizadas con an e io idad pa a elegi con an elación la opción más en ajosa, de mane a que cuando se
gene a un TR ya se puede sabe qué 3PL debe asigna lo. Las eglas y lógicas que dic an es a elección son
denominadas Business Rules y son diseñadas en conjun o en e el 4PL y el clien e pa a op imiza sus cos es y
su pe o mance. Los c i e ios de es as eglas se basan en los siguien es inpu s:
 O igen
 Des ino
 Peso
 Volumen
 P io idad
 Clasi icación Mili a
Pa a ealiza cada una de es as eglas es posible ag upa las di e en es di ecciones p e-es ablecidas. De es a
mane a, po ejemplo, podemos deci que odos los en íos que salgan cualquie ubicación en Mad id y que
ayan a F ancia pa a unos c i e ios de peso, olumen, p io idad y clasi icación de e minados, se asignen a un
3PL de e minado.
Si no se hiciese uso de es e ipo de ag upaciones que dan luga a egiones, el núme o de eglas se ía
excesi amen e al o, ya que exis i ían n2 combinaciones posibles, siendo n el núme o de ubicaciones exis en es,
que se mul iplica ían po odas las combinaciones de peso, olumen, p io idad y clasi icación mili a . Po
ejemplo, suponiendo que exis en 2000 ubicaciones di e en es y que el TR puede se RTN o AOG, Ci il o
Mili a y el peso meno o mayo de 300 kg, se debe ían de ini 32 millones de business ules, algo o almen e
inmanejable.
Como se comen aba an e io men e, po ejemplo, odas las ubicaciones de Mad id pod ían ag upa se en una
egión y odos los LOC-ID de F ancia en o a. Sin emba go, se pueden c ea egiones más pequeñas pa a
de ini BRs, po ejemplo, pa a el no e y pa a el su de F ancia, o incluso se pueden c ea egiones que
incluyan LOC-IDs de di e en es luga es pe o que engan ca ac e ís icas comunes (po ejemplo, los almacenes
o plan as que pa icipan en P og amas comunes, o los cen os de epa ación de una de e minada zona, dejando
en o a egión ubicaciones con p oximidad geog á ica pe o a los que se aplican di e en es BRs).
2.10 Visual Basic o Applica ions (VBA)
Visual Basic o Applica ions es un lenguaje de p og amación diseñado po Mic oso y disponible pa a su uso
con el paque e Mic oso O ice, aunque suele se especialmen e ú il cuando se u iliza adjun o a Excel. Es e
lenguaje de p og amación apa eció po p ime a ez en la e sión Excel 97 y se con i ió en un en o no pa a el
desa ollo de so wa e po en e, uncional y lexible.
Los p og amas c eados en es e lenguaje se denominan Mac os (del g iego μακρο, que signi ica g ande), que es
una ab e ia u a de mac oins ucción, y consis e en una secuencia o denada de ins ucciones que se ejecu an
cuando el usua io lo decide o cuando se p oduce un e en o du an e el uso de Excel. Suele usa se pa a lle a a
Con ex o
16
cabo la au oma ización de a eas epe i i as, sin emba go, al se un lenguaje de p og amación muy comple o e
inco po a muchas unciones que o man pa e de los lenguajes de p og amación es ánda , ambién es posible
diseña p og amas o módulos complejos que in e ac úen con una hoja de Excel.
Figu a 2.8. Logo ipo VBA
En es e p oyec o se u iliza á VBA como lenguaje de p og amación pa a odos los algo i mos que se diseñen,
ya que nos apo a las siguien es en ajas:
 Fácil in e acción con Mic oso Excel, donde se encuen a la base de da os con la que amos a abaja
y donde amos a ep esen a los esul ados.
 Accesible a la mayo ía de emp esas y abajado es, ya que o ma pa e del paque e O ice.
 Con capacidad su icien e pa a p ocesa los algo i mos que se analizan en es e p oyec o en iempos
acep ables.
17
17
Op imización de anspo es de epa ables en el sec o ae onáu ico
3 DESCRIPCIÓN DEL PROBLEMA
3.1 Análisis del AS-IS
Den o de los lujos de ma e iales desc i os en el apa ado an e io , en es e p oyec o nos cen a emos en los
epa ables que se en ían desde el Almacén Cen al a cen os epa ado es ubicados en Ingla e a. Es e lujo es
especialmen e in e esan e pa a su es udio ya que en el me cado no exis en muchas al e na i as ápidas y
económicas que puedan da una solución óp ima al p oblema.
Siguiendo las al e na i as de anspo e desc i as en el Capí ulo 2.6, se analiza án los p os y los con as de cada
una de las opciones posibles:
 Vehículo dedicado: es a es la opción que se usa pa a anspo es en AOG, ya que son los más ápidos
pe o a la ez los más cos osos. La ope a i a en es e caso es simple, ya que la documen ación de
expo ación se hace eniendo en cuen a la ma ícula del ehículo dedicado y la ecogida iene luga en
cuan o el DUA es á lis o. Se suelen usa u gone as o u gones que puedan ci cula sin es icciones
pa a llega lo an es posible a des ino.
 Ru a: es la al e na i a pa a lujos donde el olumen es al o, la u gencia es media/baja y los des inos
son siemp e los mismos. Como e emos a con inuación, la Emp esa Ae onáu ica hace uso de una
g an can idad de cen os epa ado es di e en es (cada uno especializado en unas piezas en pa icula ) y
si analizamos el olumen semanal, e emos un olumen al o en gene al pe o bajo pa a cada cen o
epa ado en pa icula . Es o hace que la u a como al no sea una opción iable ya que el iempo que
a da ía en hace odas las pa adas se ía incluso supe io al de llega desde España a Ingla e a.
 G upaje: es a opción es la que se usa ac ualmen e pa a en íos u ina ios, ya que el cos e es
ela i amen e bajo. Sin emba go, los Lead Times que o ecen los di e en es 3PL son excesi amen e
al os pa a los iempos que se ían acep ables po clien e, po lo que el obje i o del p oyec o se ía deja
de usa es a opción inc emen ando el cos e lo mínimo. Además, exis e la di icul ad añadida de que si
se quie e hace la p e-impo ación au omá ica se debe conoce la ma ícula dos días an es de la salida
pa a pode inclui la en el DUA. Hay que ene en cuen a que en es e ipo de anspo es, los ma e iales
an cambiando de ehículo y que la ma ícula que debe igu a en el DUA es la del que c uza la
on e a, que en algunas ocasiones es imposible de conoce . Es o alen iza aún más el Lead Time o al.
 C oss-docking: es a opción es in e esan e pa a es e ipo de lujo ya que nos pe mi i ía ap o echa las
en ajas de la u a (bajo cos e y ánsi o bajo, solo sumando iempos de espe a al día de salida) y las de
anspo e semi-dedicados pa a lle a a cabo lo conocido como “úl ima milla”. Además, si se
consigue usa siemp e el mismo o los mismos ehículos, nos pe mi i ía usa siemp e la misma
ma ícula y po lo an o se pod ía hace la p e-impo ación con es a.
En la ac ualidad, los lujos an o de ida como de uel a a los cen os epa ado es se ges ionan de la siguien e
mane a:
Desc ipción del P oblema
18
 Flujo de Almacén Cen al a Cen o Repa ado : los AOG se ges ionan con ehículos dedicados y los
RTN se ges ionan median e g upaje. Pa a pode hace la p e-impo ación, se iene un acue do con un
3PL que asegu a la misma ma ícula pa a el paso po la on e a si los en íos salen siemp e el mismo
día. Es deci , además de los al os LT del g upaje, hay que suma que solo salen del Almacén Cen al
una ez a la semana. De es a mane a, en el peo de los casos que es que un TR es é lis o jus o el día
después del día de salida, el Lead Time se á: 2 días de gene ación de DUA, 6 días de espe a a la salida
y 8 días de ánsi o, lo que suma ía 16 días.
Ciudad
La i ud
Longi d
ISLE OF WIGHT
50,67
-1,33
WIMBORNE
51,54
-0,21
SOUTHEND-ON-SEA
51,54
0,71
OXFORDSHIRE
51,83
-1,25
GLOUCESTER
51,87
-2,25
BRISTOL
51,46
-2,6
COVENTRY
52,41
-1,51
CRAWLEY
51,11
-0,18
WOLVERHAMPTON
52,58
-2,13
BRIDPORT
50,73
-2,76
LONDON
51,51
-0,13
POOLE
50,74
-1,95
HEREFORD
52,06
-2,72
MARLOW
51,57
-0,78
LUTON
51,88
-0,42
TITCHFIELD
50,85
-1,24
PORTSMOUTH
50,8
-1,08
ESSEX
51,77
0,46
WATERHEAD
53,55
-2,07
YEOVIL
50,94
-2,63
REDDITCH
52,31
-1,94
LEIGHTON
BUZZARD
51,92
-0,66
WEST SUSSEX
50,94
-0,53
VERWOOD, DORSET
50,87
-1,87
CHELTENHAM
51,9
-2,07
HANFORTH
53,35
-2,22
MARSTON
58,
-2,49
BLACKPOOL
53,82
-3,06
SUSSEX
50,94
-0,06
BASILDON, ESSEX
51,57
0,45
CORNWALL
50,42
-4,75
CHRISTCHURCH
50,74
-1,78
FAREHAM-
HAMPHIRE
50,85
-1,18
SOUTHALL
51,51
-0,38
Tabla 3.1. Ubicación de los cen os epa ado es (en g ados decimales)
19
19
Op imización de anspo es de epa ables en el sec o ae onáu ico
 Flujo de Cen o Repa ado a Almacén Cen al: en es e caso la ges ión es p ác icamen e igual, aunque
al no ene que hace p e-impo ación a la uel a hace que las ecogidas de g upaje puedan ealiza se
en cuan o el ma e ial y su documen ación es é lis a. De es a mane a, los AOG end án un LT de 2 días
en ehículo dedicado al igual que en la ida, y los RTN end án un LT de 10 días.
Los cen os epa ado es con los que abaja es a Emp esa Ae onáu ica se mues an en la Tabla 3.1, y en la
siguien e igu a se mues a la ubicación en el mapa Ingla e a de cada uno de es os pun os
Figu a 3.1. Rep esen ación g á ica de las ubicaciones de los cen os epa ado es
3.2 Posibles soluciones pa a el TO-BE
Aunque los cos es de anspo e pa a la opción elegida en el AS-IS son económicos y siemp e exis e la
posibilidad de paga más po un anspo e u gen e, los Lead Times de los TRs en RTN son excesi os y
p o ocan penalizaciones y quejas de clien es y p o eedo es. A con inuación se plan ea la al e na i a que
es udia emos en adelan e en es e p oyec o y, si bien los cos es se inc emen a án, puede se la opción más
óp ima que equilib e cos e y Lead Time si se diseña de mane a co ec a.
La solución p opues a consis e en es ablece una ecuencia de salida de un ehículo dedicado desde el
Almacén Cen al hacia un pun o de e minado en Ingla e a. Es e pun o, que se de e mina á en el Capí ulo 4 de
acue do con la ubicación de odos los cen os epa ado es pa a calcula su ubicación óp ima, se á el cen o de
consolidación y a él llega án odos los ma e iales epa ables desde el Almacén Cen al, desde donde se
lle a án a epa o po medio de un núme o de e minado de camione as con una ecuencia ambién
de e minada que se calcula á en el Capí ulo 6 según la demanda. El lujo de ma e iales epa ados se á el
mismo pe o al con a io, pudiendo ap o echa las u gone as que se usan pa a epa i a des ino inal (haciendo
la “úl ima milla”) y la uel a del ehículo que salió de España de uel a.
Po lo an o, las a iables a de e mina en es e p oblema se án las siguien es:
 La ubicación óp ima del cen o de dis ibución en unción de la ubicación de los cen os epa ado es
 La ecuencia de la u a del almacén cen al al cen o de dis ibución y ice e sa
 La ecuencia de salida a epa o inal
 La can idad de ehículos usados pa a lle a a cabo el epa o inal

Desc ipción del P oblema
20
21
21
Op imización de anspo es de epa ables en el sec o ae onáu ico
4 UBICACIÓN DEL CENTRO DE DISTRIBUCIÓN
4.1 Me odología
Pa a de e mina cuál es la ubicación óp ima del cen o de dis ibución, end emos en cuen a la Tabla 3.1 con
las coo denadas de cada cen o epa ado . Además, ambién end emos en cuen a la demanda de cada uno de
los cen os, de mane a que aunque un cen o es é muy alejado del cen o de dis ibución, si la ecuencia con la
que hay que i es baja, el o al de kilóme os que se eco e án a la go plazo se á meno . En la li e a u a
podemos encon a di e en es modelos pa a de e mina es a ubicación óp ima, si bien a ándose de un
p oblema con una al a a iabilidad y dis ancias co as, podemos usa la ubicación ob enida po el algo i mo
como una ap oximación o un ango de á ea más a o able. Pa a es e caso, los modelos de localización
con inua (conocidos ambién como modelos en el plano) pueden se i nos pa a es a p ime a ap oximación.
Es os modelos se ca ac e izan po dos a ibu os p incipales:
 El espacio de solución es con inuo, de mane a que cualquie pun o del plano es una solución
po encial. Al busca un pun o de pa ida, es o no ep esen a un p oblema ya que podemos de e mina
la ubicación del cen o de dis ibución en un luga ce cano al ob enido.
 La dis ancia se mide como la ayec o ia lineal o euclidiana, asumiendo que el e o debido al azado
de las ca e e as no es al o. Como la mayo ía de cen os epa ado es se encuen an a las a ue as de las
ciudades, podemos oma es a hipó esis como álida ya que e i a emos los azados i egula es de
calles u banas y el á ico.
Los modelos de localización con inua o planos u ilizan las coo denadas de los cen os epa ado es pa a halla
una localización (x,y) óp ima que gene e la mínima suma de las dis ancias en e las ins alaciones y los pun os
de demanda (cen os epa ado es). Es os mé odos son ma emá icos y sencillos de modela , ya que analizan la
demanda y la ubicación de las ins alaciones ya exis en es en el á ea geog á ica.
Pa a calcula las dis ancias, el cálculo más adecuado se ía usando el mé odo de Ha e sine o semi e seno, que
iene en cuen a la cu a u a de la ie a. Es a dis ancia es é ica se calcula median e las siguien es ó mulas:
𝑎=sin2(∆𝜑
2)+cos⁡(𝜑1)∙cos⁡(𝜑2)∙𝑠𝑒𝑛2(∆𝛿
2)
(4.1)
𝑐 =2∙a an2(√𝑎,√1−𝑎)
(4.2)
𝑑ℎ=𝑅∙𝑐
(4.3)
Donde φ es la la i ud, δ la longi ud, R el adio e es e y d la dis ancia es é ica.
Sin emba go, como las dis ancias a calcula son pequeñas, asumi emos un pequeño e o calculando odas las
dis ancias como lineales o euclidianas, median e la siguien e ó mula:
Ubicación del Cen o de Dis ibución
22
𝑑𝑒=√∆𝜑2+∆𝛿2
(4.4)
Siendo ∆φ es la di e encia de la i ud, ∆δ la di e encia de longi ud, y d la dis ancia euclidiana.
Pa a lle a a cabo la búsqueda del pun o más óp imo, u iliza emos el Mé odo del Cen o de G a edad.
U ilizando es e mé odo, asumimos que la mejo ubicación del cen o de dis ibución se ía ce ca del cen o de
g a edad de un cue po imagina io en el que cada pun o o igen-des ino u ie a como densidad es e p oduc o.
Las coo denadas se ob end án median e las siguien es ecuaciones:
𝑥𝑘=∑𝑙𝑖𝑥𝑖
𝑛
𝑖=1
∑𝑙𝑖
𝑛
𝑖=1
(4.5)
𝑦𝑘=∑𝑙𝑖𝑦𝑖
𝑛
𝑖=1
∑𝑙𝑖
𝑛
𝑖=1
(4.6)
𝑑𝑖=√(𝑥𝑖−𝑥𝑘)2+(𝑦𝑖−𝑦𝑘)2
(4.7)
Donde xi e yi son las coo denadas de cada cen o epa ado , li es el olumen de la demanda y di es la dis ancia
del cen o epa ado i al cen o de dis ibución xk,yk.
Exis e o o mé odo, llamado Mé odo de Webbe cuyo obje i o es encon a un pun o que minimice los cos es
de anspo e (la dis ancia) desde el nue o cen o de dis ibución has a los ya exis en es median e i e aciones.
El obje i o de es e o o mé odo es de e mina la ubicación (x,y) del cen o de dis ibución minimizando la
suma del p oduc o de cada la dis ancia y olumen de demanda. Median e i e aciones, se busca el mínimo de la
siguien e unción obje i o:
𝑚𝑖𝑛⁡𝐹 =∑𝑙𝑖𝑑𝑖(𝑥,𝑦)
𝑛
𝐼=1
(4.8)
Siendo y di es la dis ancia del cen o epa ado i al cen o de dis ibución, calculada según la exp esión (4.7).
4.2 Algo i mo
A con inuación se lle a á a cabo el cálculo del pun o óp imo pa a la ubicación del cen o de dis ibución. Las
coo denadas de cada cen o epa ado se oman de la Tabla 3.1, y las demandas semanales se oma án de la
siguien e abla:
23
23
Op imización de anspo es de epa ables en el sec o ae onáu ico
Ciudad
Nº de TRs
ida
Nº de TRs
uel a
To al
ISLE OF WIGHT
1,3
1,2
2,5
WIMBORNE
1,8
1,5
3,2
SOUTHEND-ON-SEA
1,2
0,6
1,8
OXFORDSHIRE
0,7
0,0
0,8
GLOUCESTER
3,8
0,5
4,3
BRISTOL
1,3
1,3
2,5
COVENTRY
2,2
0,7
2,9
CRAWLEY
1,4
0,6
2,0
WOLVERHAMPTON
1,3
0,6
1,9
BRIDPORT
1,0
0,6
1,5
LONDON
0,9
0,6
1,5
POOLE
0,6
0,1
0,7
HEREFORD
1,6
0,1
1,6
MARLOW
1,3
0,6
1,9
LUTON
0,6
0,6
1,3
TITCHFIELD
0,5
0,6
1,1
PORTSMOUTH
1,5
0,7
2,2
ESSEX
0,7
0,5
1,2
WATERHEAD
1,1
0,5
1,6
YEOVIL
1,1
0,5
1,7
REDDITCH
0,6
0,5
1,1
LEIGHTON BUZZARD
0,8
0,5
1,3
WEST SUSSEX
0,9
0,1
0,9
VERWOOD, DORSET
2,5
2,5
5,1
CHELTENHAM
1,0
0,6
1,6
HANFORTH
0,9
1,4
2,3
MARSTON
1,0
0,1
1,1
BLACKPOOL
0,5
0,0
0,6
SUSSEX
1,5
0,0
1,5
BASILDON, ESSEX
1,2
0,0
1,3
CORNWALL
1,4
0,6
1,9
CHRISTCHURCH
0,7
0,3
1,0
FAREHAM-HAMPHIRE
1,3
1,0
2,3
SOUTHALL
1,4
0,6
2,0
Tabla 4.1. Volúmenes de demanda de los cen os epa ado es
Puede llama la a ención que la “demanda” la y “o e a”, en endidas como el núme o de TRs que el cen o
epa ado ecibe ( epa ables) y que el cen o epa ado expide ( epa ados), espec i amen e, no sean iguales.
Lo lógica dic a que odos los equipos y piezas que se eciben luego son en iados de uel a epa ados con o o
TR, sin emba go, hay un pa de ac o es que hacen que es os olúmenes no sean iguales:
 En algunos casos, an o en el Almacén Cen al como en el cen o epa ado se pueden en ia a ios
ma e iales jun os que en el lujo in e so puedan iaja de mane a sepa ada (con TRs di e en es). Po
ejemplo, desde el Almacén Cen al se en ían 3 equipos di e en es bajo un mismo TR, sin emba go el
iempo de epa ación de cada uno de ellos es di e en e po lo que el cen o epa ado i á en iando
cada uno según los aya epa ando, haciendo que lo que a la ida e a un TR a la uel a sean 3.
Ubicación del Cen o de Dis ibución
30
ecnológico o el de la logís ica, po lo que la disponibilidad de suelo indus ial es muy al a. Con 4
pun os alo amos a Swindon ya que, a pesa de se una ciudad con meno ex ensión y población, ha
sido siemp e conocida po su sólida base indus ial y su his o ia en la ab icación, aunque ha
expe imen ado una ans o mación en su economía en las úl imas décadas, alejándose de la
manu ac u a pesada hacia sec o es más lige os y la ecnología. Con 2 pun os alo a emos a Newbu y
y Ando e , que aunque cuen an con pequeños pa ques emp esa iales, la o e a no es demasiado al a.
Pa a pun ua la dis ancia media en kilóme os de odos los cen os epa ado es, asigna emos el alo 1
al mayo (Swindon), el alo 5 al meno (Newbu y) y se ponde a á la no a de los o os dos (3,32≈3
pa a Reading y 2,42≈2 pa a Ando e .
 P ecio del suelo indus ial:
El p ecio del suelo indus ial a ía en unción de ac o es como la ubicación, la zoni icación (es deci ,
si ya ienen pe misos pa a uso indus ial), la in aes uc u a, se icios y la demanda y o e a del
mismo. Basándonos en es os ac o es, además de in o mación cuan i a i a ob enida de di e en es
webs y agencias inmobilia ias, asignamos los alo es de 4 a Swindon, Newbu y y Ando e , y 3 a
Reading.
 Accesibilidad y p oximidad a la ed p incipal de ca e e as:
O o pun o impo an e a ene en cuen a además de la ubicación es la accesibilidad y disponibilidad de
in aes uc u as de anspo e, en es e caso ca e e as p incipales. Teniendo en cuen a que el cen o de
dis ibución se ubica ía en algún polígono indus ial a las a ue as de la ciudad, an o Reading como
Swindon es a ía muy bien conec adas, ya que po ambas pasa la Au opis a M4, una de las más
ansi adas. Po Swindon ambién pasa la A419 y la A420 a Ox o d, lo que hace que se le asigne una
pun uación de 5 en e a los 4 de Reading. Ce ca de Newbu y ambién pasa la au opis a M4, po lo
que se le asignan 3 pun os. 2 pun os end ía Ando e , la peo ubicada en es e sen ido.
Figu a 4.5. P incipales ca e e as y au opis as de Sou h Wes England

31
31
Op imización de anspo es de epa ables en el sec o ae onáu ico
A con inuación, se mues a la ma iz de decisión con las pun uaciones asignadas pa a cada c i e io:
Reading
Swindon
Newbu y
Ando e
Disponibilidad de suelo indus ial
5
4
2
2
Dis ancia media a los cen os epa ado es
3
1
5
2
P ecio de suelo indus ial
3
4
4
4
P oximidad a ed de ca e e as
4
5
3
2
15
14
14
10
Tabla 4.5. Ma iz de Decisión
Podemos obse a que la ciudad que mayo pun uación ha ob enido es Reading, po lo que se oma la decisión
de ubica el cen o de dis ibución en es e luga . Aunque las ciudades e an ce canas y las ca ac e ís icas
simila es pa a algunas de ellas, u iliza es e ipo de he amien as pa a la oma de decisiones puede se muy ú il
en p oblemas más complejos en los que el hecho de oma una decisión u o a enga un al o impac o en el
esul ado inal.
Figu a 4.6. Ubicación g á ica del cen o de dis ibución as e alua las opciones median e el mé odo de la ma iz de decisión
Ubicación del Cen o de Dis ibución
32
33
33
Op imización de anspo es de epa ables en el sec o ae onáu ico
5 PROBLEMA DE RUTADO DE VEHÍCULOS
En es e capí ulo se in oduci á el p oblema de u ado de ehículos, desc ibiendo ma emá icamen e el
p oblema, sus elemen os y p incipales ca ac e ís icas, así como su con ex o his ó ico y es ado del a e.
Pos e io men e, y una ez desc i o el p oblema y obje i o a alcanza , se p esen a án algunos algo i mos que
hagan posible su esolución y se diseña á un algo i mo pa a ello.
5.1 In oducción y Es ado del A e
Los p oblemas de esolución de u as son unos de los p oblemas de op imización combina o ia más
es udiados. Es os p oblemas a an de esol e el diseño óp imo de u as que debe hace un ehículo o una
lo a de ehículos pa a sa is ace la demanda de una se ie de clien es ubicados en di e en es pun os del plano,
suje o a de e minadas es icciones. Den o de los p oblemas de u ado, podemos di e encia según el luga
donde se p oduce la demanda (u o e a), ya sea en los nodos de la ed o en los a cos.
En los p oblemas en los que la demanda se p oduce en los a cos la a ea implica que los ehículos deben cub i
la o alidad o una pa e de las conexiones en e los nodos de un g a o, es deci , odas o un núme o de e minado
de las a is as deben se eco idas. Un ejemplo de es e ipo de p oblemas es el P oblema del Ca e o Chino
(CPP, del inglés Chinese Pos man P oblem), en el que un ca e o debe eco e un ci cui o que aba ca odas las
calles de un á ea de e minada de la ciudad. El ca e o debe epa i el co eo de mane a e icien e, minimizando
la dis ancia o al eco ida. Es e p oblema es conside ado écnicamen e esuel o, lo que signi ica que exis e un
algo i mo capaz de encon a una solución óp ima en un iempo azonable, lo que nos pe mi e esol e
p oblemas CPP de g an en e gadu a en pocos segundos u ilizando una compu ado a mode na. Si ex endemos
es a idea a si uaciones que in oluc an a múl iples ehículos, ob enemos lo que se conoce como P oblema de
En u amien o de A cos Capaci ados (CARP), en el que los ehículos deben eco e ci cui os que con ienen
conexiones que ya han sido a endidas po o o ehículo.
Po o a pa e, los P oblemas de Vé ices son aquellos en los que la demanda se p oduce en los nodos de la ed,
debiendo el ehículo o ehículos isi a a es os clien es eco iendo la meno dis ancia o al posible. Un
ejemplo de es e p oblema es el TSP (T a eling Salesman P oblem o P oblema del Viajan e). En él, la can idad
de combinaciones es an al a que pa a esol e un p oblema con 100 nodos se necesi a ían años usando una
compu ado a ac ual, ya que el núme o de soluciones posibles es del o den de 10157. Es e núme o de soluciones
aumen a conside ablemen e si aho a a amos de esol e la ed de 50 nodos conside ando un p oblema VRP
(Vehicle Rou ing P oblem), en el cual la demanda o al equie e de más de un ehículo y po lo an o es
necesa io di idi el conjun o de nodos clien e pa a que su demanda sea a endida po cada ehículo y
pos e io men e esol e un TSP con cada ehículo.
P oblema de Ru ado de Vehículos
34
Figu a 5.1. Rep esen ación g á ica de los p oblemas a) TSP y b) VRP
Pa a hace en e a es e núme o an al o de posibles combinaciones, se hace uso de di e en es algo i mos, ya
sean median e écnicas de p og amación ma emá ica, algo i mos heu ís icos y algo i mos me aheu ís icos.
Es os mecanismos se analiza án más en p o undidad en la sección 5.3.
5.1.1 Con ex o His ó ico
Desde que el p oblema de u ado de ehículos uese inicialmen e p opues o po Flood en 1956, mul i ud de
au o es han a ado de busca soluciones óp imas o sub-óp imas a es e p oblema o sus a ian es median e
di e en es algo i mos que lo hiciesen compu acionalmen e iable. De la o mulación del p oblema
inicialmen e p opues a po Flood nacen a ian es como la Dan zig y Ramse en The T uck Dispa ching
P oblem en 1959, en el que p oponen un TSP gene alizado en el que una se ie de camiones- anque de gasolina
deben su i a un núme o de e minado de es aciones de se icio, pasando una sola ez po cada una de ellas.
Conside ando es e p oblema como un TSP, es deci , con ando solo con un ehículo pa a sa is ace la
demanda, y asumiendo que cada pa de nodos es á conec ado po un a co ansi able, el núme o o al de u as
di e en es pa a dicha ed iene de inido po :
𝑁 =1
2𝑛!
(5.1)
siendo n el núme o de nodos.
Pa a e alua la complejidad de es e ipo de p oblemas, Lens a y Rinnooy Kan (1981) lle a on a cabo un
análisis de la di icul ad del p oblema de en u amien o de ehículos y llega on a la conclusión de que
p ác icamen e odos los p oblemas de en u amien o de ehículos son NP-complejos, incluido el p oblema
TSP, ya que no se esuel en en iempo polinómico.
35
35
Op imización de anspo es de epa ables en el sec o ae onáu ico
Figu a 5.2. Núme o de soluciones posibles del p oblema TSP según el núme o de nodos de la ed (escala loga í mica)
La p ime a e e encia al TSP múl iple o m-TSP en el cual se iene un almacén cen al y m ehículos apa ece
en 1960 con Mille , Tucke y Zemlin. Es e p oblema oma el nomb e de VRP y a pa i de él apa ece el PTSP
en 1969 a pa i del abajo de Tillman. El p opósi o de es e p oblema consis e en de e mina el cos o mínimo
espe ado de desplazamien o a a és de un g upo de nodos en los cuales hay p obabilidades elacionadas con
la p esencia o ausencia de consumido es que necesi an a ención.
En cuan o a las a ian es de los p oblemas TSP y VRP, de acue do con Solomon y Des osie s (1988), el
p oblema de en u amien o de ehículos con en anas de iempo (VRPTW) ambién es NP-comlejo debido a
que es una ex ensión del VRP. También lo es el p oblema de en u amien o de ehículos con en egas
es ocás icas (VRPSD) aun ep esen ando una simpli icación del VRP (D o y T udeau, 1990; A che i e al.,
2005). Po lo an o, cualquie combinación de los an e io es, como el VRPTWSD, es ambién NP-complejo, lo
que espalda la aplicación de heu ís icas y me aheu ís icas pa a esol e el p oblema.
5.1.2 Tipos de VRP
En secciones an e io es se ha desc i o el p oblema del T a eling Salesman (TSP) y su gene alización al VRP,
así como su e olución y con ex o his ó ico. A con inuación, se p esen an las di e en es a ian es del p oblema,
según se modi iquen los di e en es eque imien os logís icos. Pa a en ende mejo cómo es os eque imien os
a ec an al ipo de p oblema, se p esen an los di e en es elemen os que in e ienen en un p oblema VRP:
 Depósi o (cen o de dis ibución): La me cancía a epa i se suele ubica inicialmen e en un
almacén cen al o depósi o. De es a mane a, los ehículos de cada u a deben ene ambién inicio (y
gene almen e inal) ambién en es e mismo depósi o u o o. Si se plan ea un p oblema con múl iples
depósi os, se debe de ini si es os ienen una capacidad máxima (que puede se di e en e en cada uno),
si cada uno iene asignada una lo a asignada o incluso de ini unas en anas empo ales.
 Clien es/p o eedo es (cen os epa ado es): Los clien es juegan el papel de gene ado es de la
demanda en es e ipo de p oblemas. La demanda puede se en endida como un p oduc o que debe
anspo a se y que, po an o, ocupa un olumen de e minado en un ehículo, o como un se icio que
la emp esa debe ealiza y po lo an o ocupa un cie o espacio de iempo en el cual el ehículo se
encuen a inmo ilizado.

P oblema de Ru ado de Vehículos
36
Como en el caso an e io , exis en nume osas a ian es del p oblema, en las cuales, po ejemplo, la
demanda pueda se sa is echa po más de un ehículo di e en e o que cie os ma e iales a se
en egados no es én inicialmen e en el depósi o y po lo an o sea necesa io isi a a un p o eedo
p e iamen e (se es ablece una es icción en el o den de la u a). Al igual que con los cen os de
dis ibución, los nodos clien e pueden ene de inidas unas en anas empo ales, pueden ene una
capacidad máxima de ca ga/desca ga o deban se isi ados po un ehículo en pa icula .
 Red de anspo e: Se en iende la ed de anspo e como el g a o en el que los nodos son los clien es
y depósi os y los a cos las ías de conexión en e ellos. Es os úl imos pueden se di igidos o no
(dependiendo de si se pe mi e el anspo e en un sen ido o en ambos) y puede o no exis i conexión
en e odos los nodos. A cada a co se le asocia un cos e que gene almen e suele se unción de la
dis ancia espacial en e nodos o el iempo que el ehículo a da en eco e lo.
 Flo a de ehículos: Son el conjun o de agen es de anspo e que o man pa e de la ed, es deci ,
de inen el núme o máximo de u as solución pa a el VRP. En gene al se asume que un ehículo,
du an e el pe íodo plani icado, solo ealiza á una u a, pe o exis en a ian es del p oblema en las que
el mismo ehículo puede pa icipa en más de una u a, po lo que el núme o máximo de u as
solución ya no se ía igual al amaño de la lo a.
Los ehículos suelen ene una capacidad olumé ica o de peso máxima, que puede se común pa a
odos los ehículos ( lo a homogénea) o di e en es pa a cada uno ( lo a he e ogénea). En cuan o al
cos e, además del asociado a cada a co ecogido, puede exis i un ijo po ehículo que depende á de
si es u ilizado o no.
 Ru a o u as solución: El obje i o de es e ipo de p oblemas es de e mina la u a a lle a a cabo po
cada uno de los ehículos de la lo a, cumpliendo con las es icciones p e iamen e desc i as y
asegu ando que se sa is ace la demanda. Se denomina u a o u as solución a aquellas que cumplen
con es o.
Una ez de inidos los elemen os p incipales del p oblema, se desc iben algunas de las a ian es más conocidas
y sus p incipales ca ac e ís icas:
5.1.2.1 P oblema VRP con es icciones de capacidad: CVRP
In oducido po Ralphs, Ha man y Gala i en 2001, el p oblema CVRP (Capaci ed VRP) es una a ian e en la
cual los ehículos ienen una capacidad máxima de e minada y cons an e. Conociéndose la demanda de los
clien es, el obje i o es halla las u as óp imas (meno cos e de anspo e) asegu ando que la demanda se
cumple y que, a la ez, se usa el meno núme o de ehículos posible eniendo en cuen a su capacidad.
5.1.2.2 P oblema VRP con es icciones de dis ancia: DVRP
To h y Vigo in oduje on en 2002 una a ian e del CVRP en un VRP con es icciones de dis ancia (DVRP).
En es e p oblema, a di e encia del CVRP p e iamen e desc i o, la es icción es de dis ancia (o iempo) en ez
de capacidad y la suma de la longi ud de los a cos no puede excede la máxima longi ud de la u a.
37
37
Op imización de anspo es de epa ables en el sec o ae onáu ico
Si se combina la es icción an o en la capacidad del ehículo como de dis ancia máxima o iempo máximo, el
p oblema se con ie e en una combinación del CVRP y DVRP, llamada DCVRP.
5.1.2.3 P oblema VRP con en anas empo ales: VRPTW
El p oblema VPRTW (VRP wi h Time Windows), in oducido po Co done & Cal o en 2001, añade al VRP
clásico la es icción de cumpli una en ana empo al en el que cada clien e debe se a endido. De la misma
mane a, el depósi o o cen o de dis ibución ambién cuen a con una en ana empo al de la o ma [ei,li]. El
ehículo debe a ende al clien e i en un ins an e de iempo an e io a li y pos e io a ei, ya que ue a de es e
in e alo sus ins alaciones es a án ce adas. En ealidad es posible llega an es del ins an e ei,⁡pe o⁡en⁡es e⁡
caso⁡el ehículo debe á espe a has a que se alcance dicho ins an e pa a comenza el se icio (incu iendo en
cos es de pa alización añadidos al hecho de no es a a endiendo a o o clien e en ese in e alo de iempo). En
gene al, es e p oblema ambién inco po a la es icción de capacidad pa a la lo a de ehículos, como en el
CVRP.
5.1.2.4 P oblema VRP con múl iples depósi os: MDVRP
Es e p oblema ue in oducido po Hjo ing en 1995 y debe su nomb e a las siglas en inglés de Mul iple Depo
VRP. En es e caso el núme o de depósi os es mayo que 1 y, al igual que en los casos an e io es, el obje i o es
minimiza el núme o de ehículos a u iliza y la dis ancia eco ida po es os.
Pod ía pensa se que es e p oblema no es más que el conjun o de a ios VRP a la ez, sin emba go, en es e
p oblema no se asigna inicialmen e cada clien e a un depósi o en conc e o, sino que odos los depósi os pueden
sa is ace la demanda de odos los clien es. Es po ello que el p ime paso de la esolución del p oblema debe
se asigna cada clien e a un depósi o pa a pos e io men e de ini la u a de cada uno de los ehículos
asociados al depósi o en cues ión.
5.1.2.5 P oblema VRP con en egas y de oluciones: VRPPD
In oducido po Righini en 2000, en el p oblema VRPPD (VRP wi h Pickup and Deli e y) exis e la
posibilidad de que un clien e que ya haya sido se ido necesi e que se le ecoja me cancía. En es e p oblema
hay que ene en cuen a que la ca ga del ehículo no a a se es ic amen e dec ecien e (si cumple con la
es icción de espacio a la salida del depósi o la cumpli á siemp e), sino que es a puede i a iando a medida
que los clien es an in oduciendo o sacando me cancía. Se supone que los clien es no pueden in e cambia
me cancía, es deci , la me cancía empieza o acaba siemp e en el depósi o.
5.1.2.6 P oblema VRP con iajes de eg eso: VRPB
El VRPB (VRP wi h Backhauls), in oducido en 1992 po Jacobs-Blecha y Goe schalckx, es una a ian e del
VRP en el que los nodos pueden se se idos (clien es) o deben en ega me cancía (p o eedo es). Puede
en ende se como una modi icación del VRPPD en el que los clien es se di iden en dos g upos (los que ienen
demanda y los que ienen o e a) y las de oluciones ienen luga una ez se ha en egado oda la me cancía.
Pa a que la solución sea ac ible se equie e que la capacidad de los ehículos no sea excedida en ningún pun o
P oblema de Ru ado de Vehículos
38
de la u a y que cada clien e sea isi ado po una sola u a.
5.1.2.7 P oblema VRP con en egas pa ciales: SDVRP
El p oblema SDVRP (Spli Deli e y VRP), in oducido po D o , Lapo e y T udeau en 1994, es una a ian e
del algo i mo VRP en que es á pe mi ido que un clien e sea se ido po más de un ehículo. Es e
plan eamien o esuel e el p oblema de que un clien e enga una demanda an al a que la capacidad de un
ehículo no sea capaz de sa is ace . De es a mane a, la solución óp ima se á aquella en la que el núme o de
ehículos usados y la dis ancia eco ida o iempo de anspo e sea mínimo, independien emen e del núme o
de isi as a cada clien e.
5.1.2.8 P oblema VRP con a iables es ocás icas: SVRP
In oducido po S ewa y Golden, 1983, el SVRP (S ochas ic VRP) es un p oblema VRP en el que una o
a ias a iables del mismo (núme o de clien es, demanda, iempo de se icios, e c.) son alea o ios. Pa a su
esolución, se lle a a cabo una p ime a e apa en la cual se de e mina la solución an es de conoce el alo de
las a iables, pa a pos e io men e lle a a cabo una co ección de la solución una ez conocidos los alo es
es ocás icos.
En unción de la a iable que sea alea o ia, exis en las siguien es a ian es:
 Clien es es ocás icos (SVRP-SN, Jaille , 1985): cada clien e iene una p obabilidad p de es a p esen e
y una p obabilidad (1- p) de encon ase ausen e.
 Demandas es ocás icas (VRPUD, Lapo e y Lou eaux, 1987): la demanda de cada clien e es un una
a iable alea o ia.
 Tiempos es ocás icos (VRPSTT, Lapo e, Lou eaux y Me cu e, 1992): los iempos de anspo e y
los iempos de se icio son a iables alea o ias
5.1.2.9 P oblema VRP pe iódico VRP: PVRP
A di e encia del VRP clásico, el PVRP (Pe iodic VRP), in oducido po Bap is a, Oli ei a y Zúque e en 2002,
ex iende su plani icación a n días. Pa a que la u a solución sea ac ible, además de cumpli se las es icciones
del p oblema, se debe isi a a cada clien e al menos una ez y no es necesa io que los ehículos uel an al
depósi o en el mismo día que salie on, sino que ienen opción de ol e has a el día n.
5.1.2.10 P oblema VRP con ins alaciones sa éli es: VRPSF
El VRPSF (VRP wi h Sa elli e Facili ies) es la a ian e del VRP en el que se pe mi e el eabas ecimien o de
los ehículos sin necesidad de que uel an al depósi o. In oducido po Ba d en 1997, en es e p oblema se
asume que se dispone de ins alaciones sa éli es donde los ehículos pueden epone su ca ga y con inua con
las en egas has a el inal de su u no sin necesidad de ol e al depósi o inicial. A di e encia del MDVRP,
aquí cada ehículo no es á asociado a un solo pun o de ca ga, sino que puede i abas eciéndose a lo la go del
camino, lo que pe mi e halla soluciones con u as más la gas.
39
39
Op imización de anspo es de epa ables en el sec o ae onáu ico
5.2 Algo i mos de esolución
Una ez conocidos y desa ollados los p oblemas TSP y VRP, así como sus ipos y a ian es, en esa sección se
expond án los di e en es mé odos de esolución del p oblema. Es os mé odos se pueden di idi , según la clase
de algo i mo que se emplee pa a su esolución, en es g andes g upos: exac os, heu ís icos y me aheu ís icos.
Figu a 5.3. Taxonomía de los mé odos de esolución de p oblemas VRP según la clase algo i mo
5.2.1 Mé odos Exac os
Se denomina mé odo exac o a aquel que busca odas las soluciones posibles has a encon a la óp ima,
pa iendo de un modelo de p og amación lineal, en e a, cuad á ica, e c., y haciendo uso de algo i mos de
aco amien o (Lüe , Bena en e, Bus os, & Venegas, 2009). Es os mé odos o ecen unos iempos
compu acionales acep ables pa a p oblemas con menos de 50 depósi os, ya que po encima de es e núme o,
aunque se consiga halla la solución óp ima, el iempo que end íamos que emplea en da con ella lo ha ía
o almen e ine icien e. Cabe eco da la exp esión (5.1) que es ablece el núme o de posibles combinaciones
según el núme o de depósi os.
Den o de los mé odos exac os, es os se pueden di idi en es di e en es g upos:
 Mé odos de búsqueda di ec a de á bol:
La búsqueda de la solución óp ima se ealiza sob e odos los nodos de un á bol de acue do a los
c i e ios especí icos de cada mé odo. Algunos de los mé odos más conocidos son:
o Asignación de co a in e io (Lapo e, Me cu e y Nobe , 1986): es e algo i mo asigna una
co a in e io que pe mi e disminui el núme o de ehículos eque idos pa a isi a odos los
é ices, p opo cionando una co a supe io pa a el núme o de ehículos y ans o mándolo
en un p oblema TSP.
o Algo i mo de ami icación y aco amien o o poda (Li le, Mu y, Sweeney y Ka el, 1968):
en es e caso, se eco e cada nodo del á bol desde el ni el supe io has a el in e io ,
ob eniéndose un conjun o de soluciones de sub-p oblemas que luego se op imizan de mane a
independien e pa a de e mina qué nodos pueden elimina se. Un nodo (jun o con sus
P oblema de Ru ado de Vehículos
46
P oblem wi h Pickup and Deli e y). Como se explicó p e iamen e, en es e p oblema los nodos pueden se a la
ez demandan es de o e a y demanda, como es el caso obse ando los da os de la Tabla 4.1. Es a es la
p incipal di e encia con el p oblema VRP con iajes de eg eso (VRPB), y hace que sea más complejo ya que
la capacidad del ehículo a luc uando en unción de la demanda de cada se icio. A con inuación, se
desc ibe ma emá icamen e el p oblema VRPPD.
5.3.2 Modelado Ma emá ico
En el p oblema a modela , se ienen en cuen a N nodos nume ados de 0 a n, donde 0 es el cen o de
dis ibución y el es o de nodos son los nodos clien e. Así mismo, cada clien e i iene asociada una demanda de
en ega Ei y una demanda de ecogida Ri que debe se sa is echa po una lo a de ehículos Q. Los p incipales
pa áme os que in e ienen en el p oblema son, de es a o ma:
 Ni: Nodo i de la ed de anspo e
 Ei: Demanda de en ega en el clien e i
 Ri: Demanda de ecogida en el clien e i
 dij: Dis ancia eco ida en e los nodos i y j
 Cq: Cos e del kilóme o eco ido po el ehículo q
 Qq: Capacidad del ehículo q
Po o a pa e, se p esen an las siguien es a iables de decisión del p oblema:
 𝑋𝑖𝑗𝑘 ={1⁡si⁡el⁡ ehículo⁡𝑞⁡ eco e⁡el⁡a co⁡(𝑖,𝑗)
0⁡en⁡caso⁡con a io
 𝑌𝑞={1⁡si⁡se⁡asigna⁡un⁡ ehículo
0⁡en⁡caso⁡con a io
 Lqi: olumen anspo ado po el ehículo q al iaja en un nodo i
La unción obje i o, aquella que debe se minimizada pa a encon a la solución óp ima del p oblema, calcula
el cos e o al asociado a la ecogida y en ega eniendo en cuen a la dis ancia eco ida po cada uno de los
ehículos de la lo a y iene es a o ma:
min𝐹𝑂 = ∑∑∑𝑋𝑖𝑗𝑞𝑑𝑖𝑗𝐶𝑞
𝑗∈𝑁𝑖∈𝑁𝑞∈𝑄
(5.1)
A con inuación, se p esen an las di e en es es icciones a las que es á suje o el modelo:
 Cada clien e i debe se isi ado po un y solo un ehículo q:

47
47
Op imización de anspo es de epa ables en el sec o ae onáu ico
∑∑𝑋𝑖𝑗𝑞 =1;⁡⁡∀𝑗 ∈𝑁
𝑖∈𝑁𝑞∈𝑄
(5.2)
 Todos los ehículos deben comenza y e mina su u a siemp e en el cen o de dis ibución (nodo 0):
∑𝑋𝑖𝑗𝑞 =𝑌𝑞
𝑖∈𝑁 ;⁡⁡∀𝑗 ∈𝑁;⁡∀𝑞 ∈ 𝑄
(5.3)
∑𝑋𝑖𝑗𝑞 =𝑌𝑞
𝑗∈𝑁 ;⁡⁡∀𝑖 ∈ 𝑁;⁡∀𝑞 ∈𝑄
(5.4)
 Res icción de capacidad del ehículo q:
𝐿𝑞𝑖 −𝐿𝑞𝑖 +𝑅𝑗−𝐸𝐽≤(1−𝑋𝑖𝑗)𝑄𝑞;⁡⁡∀𝑖 ∈ 𝑁;⁡∀𝑗 ∈𝑁;⁡∀𝑞 ∈𝑄
(5.5)
 Res icción de capacidad de ehículo q cuando sale del cen o de dis ibución:
𝐿𝑞0 ≤𝑄𝑞𝑌𝑞;⁡⁡∀𝑞 ∈ 𝑄
(5.6)
 Res icción pa a es ablece lujo en el modelo:
∑𝑋𝑖𝑗𝑞 −∑𝑋𝑗𝑖𝑞 =0
𝑖∈𝑁𝑖∈𝑁 ;⁡⁡∀𝑗 ∈𝑁;⁡∀𝑞 ∈ 𝑄
(5.7)
5.3.3 Resolución
El algo i mo diseñado se i á al ope ado logís ico pa a diseña la u a óp ima cada ez que eciba me cancías
en el cen o de dis ibución. En es e abajo, y pa a e alua la bondad de la solución p opues a, se u iliza án
unos da os de demanda de ecogida y en ega basados en el p omedio semanal, edondeando al alza a en e os
an o el núme o de ecogidas como de en egas. Es e se á uno de los peo es casos de es udio, ya que lo habi ual
es que haya algunos cen os epa ado es que no engan que se isi ados en alguna u a en pa icula , lo que
nos pe mi i á dimensiona la lo a en exceso pa a ene siemp e disponibilidad de la misma y e i a deja algún
TR sin en ega . Los da os de demanda po clien e del ejemplo a esol e se mues an en la Tabla 5.1.
P oblema de Ru ado de Vehículos
48
Ciudad
Núme o de
TRs a
en ega
Nº de TRs
a ecoge
To al
ISLE OF WIGHT
2
2
4
WIMBORNE
2
2
4
SOUTHEND-ON-SEA
2
1
3
OXFORDSHIRE
1
0
1
GLOUCESTER
4
1
5
BRISTOL
2
2
4
COVENTRY
3
1
4
CRAWLEY
2
1
3
WOLVERHAMPTON
2
1
3
BRIDPORT
1
1
2
LONDON
1
1
2
POOLE
1
1
2
HEREFORD
2
1
3
MARLOW
2
1
3
LUTON
1
1
2
TITCHFIELD
1
1
2
PORTSMOUTH
2
1
3
ESSEX
1
1
2
WATERHEAD
2
1
3
YEOVIL
2
1
3
REDDITCH
1
1
2
LEIGHTON BUZZARD
1
1
2
WEST SUSSEX
1
1
2
VERWOOD, DORSET
3
3
6
CHELTENHAM
1
1
2
HANFORTH
1
2
3
MARSTON
1
1
2
BLACKPOOL
1
0
1
SUSSEX
2
0
2
BASILDON, ESSEX
2
0
2
CORNWALL
2
1
3
CHRISTCHURCH
1
1
2
FAREHAM-HAMPHIRE
2
1
3
SOUTHALL
2
1
3
TOTAL
57
36
93
Tabla 5.1. Valo es de demanda de ecogidas y en egas pa a el ejemplo a esol e
Pa a esol e el p oblema, u iliza emos dos algo i mos que se basan en la me aheu ís ica: el algo i mo de
pé alos, que nos da á una buena ap oximación inicial ya que p e iamen e hemos diseñado el cen o de
dis ibución (o CEDI) en el pun o cen al que minimiza la dis ancia o al eco ida, y pos e io men e un
algo i mo de mejo a basado en la me aheu ís ica del ecino más ce cano. Con es e algo i mo, consegui emos
mejo a la solución ob enida p e iamen e in e cambiando nodos ecinos en busca de una dis ancia o al
eco ida meno .
49
49
Op imización de anspo es de epa ables en el sec o ae onáu ico
5.3.3.1 Algo i mo de Ba ido
El p incipio undamen al de es e algo i mo es á basado la obse ación de que en muchos p oblemas de u ado
de ehículos, las u as óp imas p esen an una es uc u a lobulada o casi lobulada (Fos e y B yan, 1976).
Basándose en el mé odo de ba ido in oducido po Gille y Mille en 1974, en es e algo i mo se a eco iendo
el plano median e una semi ec a que a gi ando e inco po ando nodos a la u a, has a que el ehículo se llena
o se alcanza alguna es icción adicional.
Pa a que es e algo i mo sea e icien e, es necesa io que los nodos clien e (cen os epa ado es) se si úen en un
sec o geog á ico cen ado en el cen o de dis ibución. Pa a ello, amos a cambia el sis ema de e e encia y
amos a ubica el cen o de dis ibución en el pun o (0,0). Una ez cen ado, amos a calcula la ubicación
ela i a de cada nodo lo amos a ubica en el plano. De es a o ma, ob enemos la siguien e dis ibución sob e
el sis ema de e e encia:
Figu a 5.5. Ubicación g á ica de los nodos clien e en un sis ema de e e encia cen ado en el CEDI
Una ez colocados odos los nodos en el nue o sis ema de e e encia, amos a cambia a coo denadas pola es
pa a acili a el eco ido de la semi ec a. Pa a ello, u iliza emos las siguien es exp esiones básicas:
𝑟=√𝑋2+𝑌2
(5.8)
𝜃 =𝑎𝑡𝑔(𝑌
𝑋)
(5.9)
Una ez con e idas odas las coo denadas de los nodos a pola es, p ocedemos a o dena las en o den c ecien e
según θ. De es a o ma es a emos ba iendo el espacio al como se necesi a en el algo i mo y es a íamos
p epa ados pa a empeza a asigna nodos a cada u a. Si se a ase de un p oblema TSP en el que no se u iese
lími e supe io en la dis ancia eco ida, el esul ado de aplica el algo i mo de ba ido a nues a ed se ía la que
se mues a en la Figu a 5.6.
P oblema de Ru ado de Vehículos
50
Figu a 5.6. Resul ado de aplica el algo i mo de ba ido sob e la ed comple a
En la Tabla 5.2 se mues a la nume ación de los nodos (de meno a mayo ángulo, asumiendo que el cen o de
dis ibución es siemp e el nodo 0) así como la con e sión a coo denadas ela i as y pos e io men e a
coo denadas pola es.
Una ez adap ados nues os da os ya es amos p epa ados pa a diseña el algo i mo de ba ido eniendo en
cuen a las demandas de en egas y ecogidas. El p oceso es simple y se basa en un p ocedimien o i e a i o que
a eco iendo cada uno de los nodos e i icando que la capacidad del ehículo no se exceda ni que ampoco
se acíe po comple o. En es e pun o, enemos que ene en cuen a la Hipó esis 6, ya que la condición de que el
ehículo se acíe debe di e encia en e ma e iales ecogidos y ma e iales a en ega . De es a o ma, las
condiciones deben se :
 El ehículo debe ol e al CEDI si, ecogiendo odo el ma e ial epa ado disponible en el siguien e
nodo, la capacidad excede ía el máximo pe mi ido (en es e caso 10).
 El ehículo debe ol e al CEDI una ez ha en egado odos los ma e iales epa ables ca gados en el
CEDI, independien emen e del espacio disponible. Solo hab á una excepción, que se á cuando en el
siguien e nodo a isi a solo exis a demanda de ecogida, y no de en ega.
 Se supone que el ehículo siemp e pa e del cen o de dis ibución ca gado con la máxima ca ga
posible (10 cajas). Sin emba go, se ha añadido una p ime a e aluación en la cual se comp ueba si en
el p ime nodo la demanda de ecogida supe a a la demanda de en ega. Si es o es así, el ehículo sale
con la can idad máxima de cajas que le pe mi a ecoge odo el ma e ial epa ado disponible en el
p ime nodo, pa a e i a que nunca se pueda inicia una u a.
La lógica del algo i mo p og amado se ep esen a en el diag ama de la Figu a 5.7
51
51
Op imización de anspo es de epa ables en el sec o ae onáu ico
Ca esianas
Ca esianas
ela i as
Pola es
n
Ciudad
x
y
X
Y
(km)
he a
(deg)
0
READING
5712,06
-107,67
0
0
0
0
1
LEIGHTON BUZZARD
5763,12
-73,26
51,06
34,41
61,57
33,98
2
LUTON
5758,68
-46,62
46,62
61,05
76,81
52,63
3
MARLOW
5724,27
-86,58
12,21
21,09
24,37
59,93
4
ESSEX
5746,47
51,06
34,41
158,73
162,42
77,77
5
WIMBORNE
5720,94
-23,31
8,88
84,36
84,83
83,99
6
SOUTHALL
5717,61
-42,18
5,55
65,49
65,72
85,16
7
BASILDON, ESSEX
5724,27
49,95
12,21
157,62
158,09
85,57
8
LONDON
5717,61
-14,43
5,55
93,24
93,41
86,59
9
SOUTHEND-ON-SEA
5720,94
78,81
8,88
186,48
186,69
87,27
10
CRAWLEY
5673,21
-19,98
-38,85
87,69
95,91
113,90
11
SUSSEX
5654,34
-6,66
-57,72
101,01
116,34
119,74
12
WEST SUSSEX
5654,34
-58,83
-57,72
48,84
75,61
139,76
13
PORTSMOUTH
5638,8
-119,88
-73,26
-12,21
74,27
189,46
14
FAREHAM-HAMPHIRE
5644,35
-130,98
-67,71
-23,31
71,61
199,00
15
TITCHFIELD
5644,35
-137,64
-67,71
-29,97
74,05
203,88
16
ISLE OF WIGHT
5624,37
-147,63
-87,69
-39,96
96,37
204,50
17
CHRISTCHURCH
5632,14
-197,58
-79,92
-89,91
120,30
228,37
18
POOLE
5632,14
-216,45
-79,92
-108,78
134,98
233,70
19
VERWOOD, DORSET
5646,57
-207,57
-65,49
-99,9
119,45
236,75
20
BRIDPORT
5631,03
-306,36
-81,03
-198,69
214,58
247,81
21
YEOVIL
5654,34
-291,93
-57,72
-184,26
193,09
252,61
22
CORNWALL
5596,62
-527,25
-115,44
-419,58
435,17
254,62
23
BRISTOL
5712,06
-288,6
0,001
-180,93
180,93
270,00
24
GLOUCESTER
5757,57
-249,75
45,51
-142,08
149,19
287,76
25
HEREFORD
5778,66
-301,92
66,6
-194,25
205,35
288,92
26
CHELTENHAM
5760,9
-229,77
48,84
-122,1
131,51
291,80
27
REDDITCH
5806,41
-215,34
94,35
-107,67
143,16
311,23
28
WOLVERHAMPTON
5836,38
-236,43
124,32
-128,76
178,98
313,99
29
BLACKPOOL
5974,02
-339,66
261,96
-231,99
349,92
318,47
30
MARSTON
5912,97
-276,39
200,91
-168,72
262,36
319,98
31
OXFORDSHIRE
5753,13
-138,75
41,07
-31,08
51,50
322,88
32
HANFORTH
5921,85
-246,42
209,79
-138,75
251,52
326,52
33
COVENTRY
5817,51
-167,61
105,45
-59,94
121,30
330,39
34
WATERHEAD
5944,05
-229,77
231,99
-122,1
262,16
332,24
0
READING2
5712,06
-107,67
0
0
0
0
Tabla 5.2. Nodos o denados según el ángulo y sus co espondien es coo denadas ela i as

P oblema de Ru ado de Vehículos
52
Figu a 5.7. Diag ama de lujo del Algo i mo de Ba ido
T as aplica el algo i mo desc i o sob e el p oblema-ejemplo, ob enemos que la ed puede se eco ida y la
demanda sa is echa po seis ehículos, o mando las u as en o ma de pé alos de la Figu a 5.8.
Figu a 5.8. Solución del p oblema p opues o median e el Algo i mo de Ba ido
53
53
Op imización de anspo es de epa ables en el sec o ae onáu ico
Median e es a disposición, la lo a de ehículos ha conseguido lle a a cabo las 57 en egas y 36 ecogidas
solici adas. Podemos calcula la dis ancia eco ida po cada ehículo sumando la dis ancia en e cada uno de
los nodos que es isi ado en cada u a. Pa a ello, p ime o debemos calcula una ma iz de dis ancias en e odas
las combinaciones de nodos, que se mues a en el Anexo I. Es as dis ancias es án calculadas median e la
exp esión (4.7) y con los da os de la Tabla 5.2.
Los esul ados ob enidos se mues an en la siguien e abla:
Ru a
Nodos
En egas
Recogidas
km
eco idos
Ru a 1
0
1
2
3
4
5
6
0
9
7
444,25
Ru a 2
0
7
8
9
10
11
12
0
10
4
576,71
Ru a 3
0
13
14
15
16
17
18
0
9
7
320,08
Ru a 4
0
19
20
21
22
23
0
10
8
935,20
Ru a 5
0
24
25
26
27
28
0
10
5
543,14
Ru a 6
0
29
30
31
32
33
34
0
9
5
1382,82
To al
57
36
4202,21
Tabla 5.3. Resul ados del p oblema p opues o median e el Algo i mo de Ba ido
5.3.3.2 Algo i mo de mejo a median e la heu ís ica del ecino más ce cano
Como se puede obse a a simple is a si mi amos la Figu a 5.8, la solución hallada median e el algo i mo de
ba ido es una solución ac ible pe o no óp ima. El ejemplo más cla o se puede e en la Ru a 6, que cuen a
con dos nodos ce canos al cen o de dis ibución y el es o más alejado. Si se a eco iendo en el sen ido
ho a io de las agujas del eloj, se isi a án de mane a al e na nodos ce canos y lejanos al cen o de
dis ibución, haciendo o almen e ine icien e el eco ido p opues o.
Pa a ello, se p opone un algo i mo de mejo a que se basa en la heu ís ica del ecino más ce cano
(Rosenk an z, S ea ns y Lewis, 1977). Median e es e algo i mo, se a a de cons ui un ciclo Hamil oniano
( u a sin é ices epe idos que eco e odos los é ices del g a o) que se basa en desplaza se al nodo o é ice
más ce cano al ac ual, es deci , omando la a is a de meno cos e. Aunque mejo a los esul ados del algo i mo
de ba ido ya que minimiza la dis ancia en e nodos, es a heu ís ica es “miope”, ya que en cada i e ación solo
iene en cuen a la siguien e elección disponible, de mane a que oma la mejo opción disponible pa a la
i e ación ac ual puede obliga le a oma malas decisiones más adelan e. De es a o ma, eco e á a is as de bajo
cos e al p incipio pe o al inal queda án é ices cuya conexión sea de al o cos e.
En es e p oblema, al se ela i amen e sencillo debido al bajo núme o de nodos po u a, es a heu ís ica puede
mejo a conside ablemen e el esul ado ob enido an e io men e y además iene un bajo cos e compu acional,
po lo que se p og ama el algo i mo siguiendo la lógica ep esen ada en el diag ama de la Figu a 5.9.
P oblema de Ru ado de Vehículos
54
Figu a 5.9. Diag ama de lujo de la heu ís ica del ecino más ce cano
Aunque en el diag ama de lujo se simpli ica el p oceso, es necesa io con a con una ma iz de isi a cuyos
elemen os algan 1 cuando un nodo ha sido isi ado y 0 cuando no. De es a mane a, el ehículo no se di igi á
a un nodo ya isi ado aunque sea el de meno dis ancia. Po o a pa e, ambién se á necesa io impone que el
ehículo debe ol e al nodo 0 una ez e mine de eco e el es o (el algo i mo debe se gene al pa a n nodos
ya que cada u a puede ene un núme o di e en e de pa adas).
Tomando como pun o de pa ida las u as que hemos ob enido de aplica el algo i mo de ba ido de la Tabla
5.3, y aplicando la heu ís ica explicada, ob enemos los siguien es esul ados:
Ru a
Nodos
En egas
Recogidas
km
eco idos
Ru a 1
0
3
1
2
6
5
4
0
9
7
393,96
Ru a 2
0
12
10
11
8
7
9
0
10
4
486,11
Ru a 3
0
14
15
13
16
17
18
0
9
7
332,56
Ru a 4
0
19
21
20
23
22
0
10
8
1014,81
Ru a 5
0
26
24
25
28
27
0
10
5
475,14
Ru a 6
0
31
33
32
34
30
29
0
9
5
774,44
To al
57
36
3477,02
Tabla 5.4. Resul ados del p oblema p opues o median e el Algo i mo de mejo a basado en Heu ís ica del Vecino más Ce cano
55
55
Op imización de anspo es de epa ables en el sec o ae onáu ico
Compa ando los esul ados con los an e io es, podemos obse a que se ha mejo ado el cos e o al del
conjun o de u as en 725,19. Sin emba go, al como habíamos p edicho, en algunas u as el esul ado de aplica
es e algo i mo “ciego” puede habe empeo ado lige amen e los esul ados iniciales, como ha ocu ido con las
u as 3 y 4.
Figu a 5.10. Solución del p oblema p opues o median e el Algo i mo de mejo a basado en Heu ís ica del Vecino más Ce cano
Pa a ilus a es e empeo amien o de los esul ados, amos a analiza un ejemplo. Si mi amos la Ru a 4,
podemos obse a como, as isi a el nodo 20 (el e ce o de es a u a), el algo i mo debe decidi si i al nodo
23 (el más ce cano) o al nodo 22 (más lejano). Según la heu ís ica del ecino más ce cano, el nodo a isi a
debe se el 23 ya que es el que se encuen a a meno dis ancia (83 km s 223,6 km). Sin emba go, es o le
obliga a que deba e mina la u a eco iendo las a is as 23-22 (265,1 km) y 22-0 (435,1 km). En cambio, si
hubiese elegido i hacia el nodo 22, aunque en el momen o hubiese eco ido 140,6 km más, las a is as que
end ía que eco e luego se ían la 22-23 (265,1 km) y la 23-0 (180,9 km). Se mues a así que es a heu ís ica
ealiza mejo as locales pe o en cie os casos puede empeo a la solución global.
Figu a 5.11. Ejemplo de decisión según la Heu ís ica del Vecino más Ce cano
P oblema de Ru ado de Vehículos
62
En cualquie caso, pa a oma el mejo esul ado oma emos, pa a cada u a, la que meno dis ancia haya
eco ido. De es a o ma, aunque algún algo i mo empeo e alguna de los u as, siemp e nos queda emos con la
mejo ya que puede habe con igu aciones iniciales que se esuel an mejo po un mé odo o po o o.
En la siguien e abla se mues an los iempos de ejecución de cada uno de los algo i mos:
Algo i mo
Tiempo de ejecución (seg)
Algo i mo de ba ido
0,016
Heu ís ica de ecino más ce cano
0,086
Búsqueda local (nodos adyacen es)
0,094
Búsqueda local (nodos no isi ados)
0,102
To al
0,297
Tabla 5.10. Tiempos de ejecución del código VBA

63
63
Op imización de anspo es de epa ables en el sec o ae onáu ico
6 ANÁLISIS DE LA SOLUCIÓN PROPUESTA
En el capí ulo an e io se esol ió un p oblema cuyos da os es aban basados en alo es p omedios de las
demandas de ecogida y en ega, de ca a a e alua la bondad de los mé odos de op imización escogidos. Una
ez diseñado el algo i mo, en es e capí ulo simula emos los da os pa a un año comple o y aplica emos el
algo i mo an e io a cada una de las 52 semanas, pa a e alua el núme o de ehículos p omedio que ha án al a
y los kilóme os es imados a eco e . Con esos esul ados, analiza emos el impac o an o en cos es como en
Lead Time de la solución p opues a.
Se simulan los da os pa a cada una de las semanas del año de mane a alea o ia pe o asegu ando que el
p omedio de en íos y ecogidas cumpla con los da os de la Tabla 4.1. Es os da os se mues an en el Anexo II.
Aplicando los algo i mos de ba ido, de ecino más ce cano y de búsqueda local basado en pe mu a de nodos
no isi ados, ob enemos pa a cada semana los siguien es esul ados:
Semana
Núme o
de u as
( ehículos)
Dis ancia
eco ida
(km)
Semana
Núme o
de u as
( ehículos)
Dis ancia
eco ida
(km)
1
7
3018,7
27
6
2512,0
2
11
4592,7
28
4
1577,3
3
7
2903,0
29
5
2493,7
4
6
2723,4
30
8
3206,0
5
8
3742,2
31
6
2829,4
6
5
1914,9
32
5
2514,4
7
6
2706,8
33
5
2698,5
8
6
3337,9
34
7
2874,6
9
7
3275,0
35
6
2618,3
10
7
2881,1
36
7
3186,7
11
5
2539,6
37
5
2083,2
12
4
2392,3
38
8
3358,6
13
8
3195,9
39
6
2387,4
14
6
2629,7
40
6
2615,1
15
6
2393,2
41
5
2380,4
16
7
3108,2
42
6
2703,6
17
4
2070,4
43
6
1750,6
18
7
2995,1
44
7
2890,3
19
6
2707,9
45
6
2714,9
20
5
2542,2
46
8
2914,8
21
6
1987,4
47
4
2109,1
22
6
2811,5
48
7
2864,0
23
7
2800,9
49
5
1962,5
24
9
3338,1
50
5
2734,4
25
8
3632,4
51
5
2437,7
26
6
2750,8
52
6
2482,8
Tabla 6.1. Resul ados de aplica los algo i mos de op imización semanalmen e du an e un año comple o
Análisis de la Solución P opues a
64
Vamos a ep esen a el núme o de ehículos necesa ios pa a sa is ace la demanda semanal en un his og ama,
de ca a a pode es ima el núme o necesa io de ehículos que se deben con a a :
Figu a 6.1. His og ama del núme o de ehículos necesa ios po semana
Podemos obse a que el núme o más epe ido es el 6, que coincide con la mediana de la mues a. Si
calculamos la des iación es ánda , ob enemos que es a iene un alo de 1,34. Podemos deduci que, si
con a amos 6 ehículos, cub i emos el se icio el 63% de las ocasiones. Si con a ásemos 7 ehículos, el
se icio queda ía cubie o el 85% de las ocasiones y si uesen 8 los ehículos con a ados, se cub i ía el 96%.
Es a decisión se oma á más adelan e cuando se analice el cos e de ese a un ehículo así como posibles
cos es de cancelación.
En cuan o a los kilóme os eco idos, el p omedio es de 447 po u a, lo que hace un o al de 142.978
kilóme os. Si no hubiésemos aplicado algo i mos de op imización, el o al de kilóme os eco idos hubie a
sido 173.634, más de 30.000 km po encima del esul ado inal. En la Figu a 6.2. se mues a el o al de
dis ancia eco ida en caso de habe u ilizado cada mé odo de op imización, donde se puede obse a que
aplica la heu ís ica del ecino más ce cano aho a un 14,2% de dis ancia, el algo i mo de búsqueda local con
pe mu a de nodos adyacen es aho a un 16,1% de dis ancia, y el basado en pe mu a de nodos no isi ados
pe mi e aho a un 17,7% de dis ancia o al.
Figu a 6.2. Compa ación de dis ancia anual eco ida po algo i mo de op imización
65
65
Op imización de anspo es de epa ables en el sec o ae onáu ico
La Figu a 6.3 mues a es os mismos da os semanalmen e, donde se puede no a que el algo i mo de búsqueda
local con pe mu a de nodos no isi ados es siemp e el que mejo es esul ados ob iene, y el de ba ido siemp e
el que peo .
Figu a 6.3. Dis ancia eco ida semanalmen e po algo i mo de op imización
6.1 Análisis de Lead Times
A con inuación se a a es udia la mejo a en cuan o a iempos de ánsi o que se espe a consegui con la
solución p opues a. Reco damos que los lujos son los siguien es:
 Flujo de Almacén Cen al a Cen o Repa ado : G upaje saliendo una ez en semana del almacén
cen al. El LT se á de 8 días de ánsi o sumado a la espe a al día de salida de la u a, que podemos
es ima como 3 días de media. El Lead Time de ida a cen o epa ado (sin con a ámi es aduane os)
es de 11 días.
 Flujo de Cen o Repa ado a Almacén Cen al: G upaje saliendo cada ez que haya una expedición
lis a en un cen o epa ado . El LT es de 8 días de ánsi o más 2 días ap oximadamen e pa a o ganiza
la ecogida.
Vamos aho a a analiza los iempos es imados pa a la solución p opues a, que consis e en hace una u a
semanal con un áile al cen o de dis ibución y pos e io men e en ega y ecoge odo de los cen os
epa ado es median e las u as es udiadas en el capí ulo an e io . El iempo de ánsi o desde el Almacén
Cen al has a el cen o de dis ibución son dos días. A es o hab á que suma le el iempo de espe a de la u a,
que inicialmen e suponemos semanal, po lo que el p omedio es de 3 días al igual que en la solución an e io .
Es deci , el ma e ial llega ía al cen o de dis ibución el quin o día y se lle a ía a epa o el sex o, po lo que el
p omedio de LT de es e lujo de ida se hab á educido de 11 a 6 días, es deci , 5 días. Aho a, el iempo
máximo de ánsi o se á de 9 días y el mínimo de 3 días, sin con a ámi es aduane os, que se es ima en 2 días.
Pa a el lujo de uel a, el iempo de espe a pa a que un ma e ial sea ecogido es igual que en el caso con a io,
ya que la misma u a que en ega es la que ecoge po lo que la ecuencia debe se la misma. El ánsi o es
ambién de 2 días po lo que el LT desde cen o epa ado a Almacén Cen al se ía ambién de 6 días de
p omedio, es deci , se consigue una educción de 4 días.
Todo lo expues o p e iamen e aplica únicamen e a en íos con p io idad u ina ia (RTN). Los en íos en AOG
Análisis de la Solución P opues a
66
se con inua án en iando median e ehículo dedicado a menos que el TR se gene e el mismo día que sale la
u a, ap o echando que el iempo de ánsi o es simila .
En el siguien e esquema se mues a la plani icación semanal de la solución p opues a, que iene un ho izon e
empo al de una semana:
Figu a 6.4. Plani icación semanal de la solución p opues a
Aho a debemos escoge el día de la semana que debe comenza es a plani icación:
 Lunes: comenzando es e día, la en ega se ía el jue es y los ma e iales epa ados llega ían al almacén
cen al el domingo, po lo que hab ía que suma un día más al LT del lujo de uel a.
 Ma es: si el áile sale del almacén cen al el ma es, el epa o se end ía que lle a a cabo el ie nes.
Teniendo en cuen a que muchos cen os epa ado es ienen ho a io educido los ie nes, es una
opción a iesgada ya que si no da iempo a hace odas las en egas hab ía que suma dos más más al
LT has a el lunes que uel an a ab i , además de ene que con a a más ehículos pa a hace las
en egas es an es.
 Mié coles: saliendo es e día, el epa o y ecogida end ía que hace se el lunes, añadiendo dos días de
LT al lujo de epa ables (ida). El áile llega ía el ma es al almacén cen al (no se añade LT al lujo
de uel a).
 Jue es: caso simila al an e io , pe o solo se añadi ía un día de LT al lujo de ida.
 Vie nes: con la salida un ie nes, la llegada al cen o de dis ibución se ía el domingo. Es o implica
que el áile debe queda se inmo ilizado du an e un día, lo que además de suma LT añade un
sob ecos e que es p e e ible no asumi .
 Sábado: el almacén cen al ab e los sábados en ho a io de mañana, po lo que es iable la salida en
es e día. La llegada al almacén cen al se ía el lunes a p ime a ho a y el epa o el ma es, saliendo el
áile de uel a el mié coles y llegando al Almacén Cen al el ie nes.
 Domingo: no es posible sali es e día al es a el Almacén Cen al ce ado.
Viendo las di e en es opciones, la mejo opción pa ece se sali los sábados po la mañana, ya que es la única
opción que no gene a días de espe a ni gene a iesgos de no ene su icien e iempo pa a comple a los
se icios.
Pod íamos consegui iempos aún más bajos si aumen amos la ecuencia de la u a, eniendo siemp e en
cuen a que el mínimo iempo de ánsi o siemp e se á de 3 días. Si aumen amos la ecuencia de la u a a dos
po semana, end íamos dos opciones iables: que la segunda salida se lle e a cabo el ma es o el mié coles. Se
67
67
Op imización de anspo es de epa ables en el sec o ae onáu ico
desca an el es o de días ya que es a ían demasiado ce ca de la o a salida. La opción del ma es eco damos
que enía el p oblema de que se ha ía el epa o el ie nes, pe o si educimos el núme o de TRs a la mi ad (se
epa en en e dos u as) se pod ía consegui en ega an es del cie e de los mismos. La opción del mié coles
no educi ía an o el LT de epa ables ya que hay que con a con un iempo de espe a pa a el epa o, aunque sí
educi ía a la mi ad el de epa ados.
6.2 Análisis Económico
En es a sección se a a hace una es imación de cos es en unción de los esul ados del capí ulo an e io . Pa a
comenza , se de allan los cos es kilomé icos de cada ipo de ehículo, ob enidos del in o me de Julio de 2023
del “Obse a o io de cos es de anspo e de me cancías po ca e e a” del Minis e io de Fomen o:
Tipo de ehículo
Cos e po km
Cos e po h
Vehículo a iculado de ca ga gene al
1,48 €
98,67 €
Vehículo a iculado de ca ga gene al en anspo e in e nacional
1,59 €
119,46 €
T en de ca e e a
1,46 €
97,06 €
Vehículo ígido de 3 ejes
1,36 €
71,92 €
Vehículo ígido de 2 ejes
1,34 €
66,87 €
Fu gone a
1,45 €
40,23 €
Tabla 6.2. Cos es kilomé icos y ho a ios de anspo e de me cancía po ca e e a
Además de es os cos es kilomé icos y ho a ios, exis en los siguien es cos es ijos que debemos ene en cuen a
a la ho a de calcula el cos e global de la solución p opues a:
 Cos e ijo po ese a de ehículo a iculado: 80 €
 Cos e ijo po ese a de u gone a: 40 €
 Cos es de cancelación de ehículo a iculado: 120 €
 Cos e de cancelación de u gone a: 60 €
 Cos e ijo pa a u gone a adicional: 80 €
 Cos e ho a io de pa alización de ehículo a iculado: 5 €
 Cos e ho a io de pa alización de u gone a: 5 €
Pa a calcula el cos e anual de es a solución, debemos ene en cuen a que hab á u a odas las semanas del
año, y se han de ene en cuen a los siguien es concep os:
 T ayec o de Se illa-Reading y ice e sa:
Es e ayec o se ha á en un ehículo a iculado de ca ga gene al. La dis ancia ( eal, ob enida de la
aplicación Google Maps) es de 2080 km, y se a da ían al ededo de 24 ho as de conducción e ec i a
en es e ipo de ehículo. El cos e de cada ayec o se ía:

Análisis de la Solución P opues a
68
𝐶𝑡𝑟𝑎𝑦,𝑆𝐸𝑉−𝑅𝐸𝐴 =𝐶ℎ∙𝑡+𝐶𝑑∙𝑑 =119,46∙24+1,59∙2080=⁡6.174,24⁡€
(6.1)
Además, hab ía que suma un día comple o de pa alización del ehículo en el que es e es á espe ando
a que las u as de epa o y ecogida e minen sus ayec os. Es o nos supone un cos e de:
𝐶𝑝𝑎𝑟𝑎𝑙𝑖𝑧 =𝐶ℎ∙𝑡𝑝𝑎𝑟𝑎𝑙𝑖𝑧 =5∙24=⁡120⁡€
(6.3)
Pa a calcula el cos e o al anual end íamos que mul iplica po el núme o de semanas del año la
suma del cos e de dos ayec os en e Se illa y Reading, los cos es de pa alización y el cos e de
ese a del ehículo que se calcula semanalmen e:
𝐶𝑡,𝑇𝑅𝐴𝐼𝐿𝐸𝑅 =52(2𝐶𝑡𝑟𝑎𝑦,𝑆𝐸𝑉−𝑅𝐸𝐴 +⁡𝐶𝑝𝑎𝑟𝑎𝑙𝑖𝑧 +𝐶𝑟𝑒𝑠𝑒𝑟𝑣𝑎)=⁡⁡⁡652.520,96⁡€⁡
(6.3)
Figu a 6.5. Vehículo a iculado de ca ga gene al
 Ru as de epa o y ecogida en cen os epa ado es:
Pa a es as u as elegi emos po su apidez y acilidad pa a hace a eas de epa o un ehículo de ipo
u gone a. Pa a calcula el cos e de anspo e enemos que ene en cuen a es ac o es: el cos e po
kilóme o, el cos e po ho a y el cos e ijo po u a.
Pa a calcula el cos e de ayec o pu o (kilomé ico y ho a io), usa emos los da os ob enidos en el
capí ulo an e io (Tabla 6.1 y Figu a 6.2). Con es os da os ob end emos que la dis ancia o al eco ida
es de 142.978,41 kilóme os, que podemos mul iplica po el cos e ho a io pa a ob ene el anual. Pa a
calcula el cos e ho a io, asumimos que la elocidad media del eco ido es de 50 km/h (con ando con
las pa adas pa a ca ga y desca ga), po lo que emplea emos un o al de 2.860 ho as pa a lle a a cabo
odas las u as.
𝐶𝑡𝑟𝑎𝑦,𝑈𝐾 =𝐶ℎ∙𝑑
𝑣 +𝐶𝑑∙𝑑 =40,23∙2860+1,45∙142.978,41=⁡322.376,49⁡€⁡
(6.4)
Aho a debemos calcula los cos es ijos de ese a de los ehículos, así como las posibles
69
69
Op imización de anspo es de epa ables en el sec o ae onáu ico
cancelaciones. Basándonos en los da os simulados pa a odo el año, amos a calcula el cos e anual
que se end ía en los casos en que se ese en di e en e núme o de u gone as, sumándole los cos es
de u gone a ex a en caso de se necesa ia alguna más o es ándole los cos es de cancelación en caso
de sob a alguna. Los esul ados se mues an en la siguien e igu a:
Figu a 6.6. Cos es ijos po can idad de ehículos con a ada a lo la go de un año
Es e cálculo con i ma que la mejo opción es con a a 6 ehículos (la media) y paga cos es de
cancelación cuando se necesi en menos y cos es de ehículo ex a cuando sea necesa io. Se deduce
po la o ma de la g á ica que es p e e ible queda se co o que la go, ya que aunque los cos es de
cancelación son meno es que los de ehículo ex a, cuando se cancela un ehículo además se pie de el
ijo que se pagó inicialmen e, po lo que se ía un doble cos e.
Los cos es ijos se calcula ían de la siguien e mane a:
𝐶𝑓𝑖𝑗𝑜,𝑈𝐾 =𝑁𝑣,𝑐𝑜𝑛𝑡𝑟𝑎𝑡𝑎𝑑𝑜 ∙𝐶𝑓𝑖𝑗𝑜 +𝑁𝑣,𝑐𝑎𝑛𝑐 ∙𝐶𝑐𝑎𝑛𝑐 +𝑁𝑣,𝑒𝑥𝑡𝑟𝑎 ∙𝐶𝑒𝑥𝑡𝑟𝑎 =⁡15.860,00⁡€⁡
(6.5)
Los cos es o ales de las u as en u gone a en Ingla e a queda ían de la siguien e mane a:
𝐶𝑡,𝐹𝑈𝑅𝐺𝑂𝑁𝐸𝑇𝐴 =𝐶𝑡𝑟𝑎𝑦,𝑈𝐾 +𝐶𝑓𝑖𝑗𝑜,𝑈𝐾 =⁡⁡338.236,49⁡€⁡
(6.6)
Figu a 6.7. Fu gone a
Análisis de la Solución P opues a
70
 Cos es logís icos del cen o de dis ibución:
El cen o de dis ibución ecibe una media de 40 TRs a la semana, si se dimensiona del lado de la
segu idad con un 50% de espacio sob an e y se quie e apila como máximo en dos al u as, se
necesi a ían al ededo de 45 m2, que incluyendo pasillos se ían unos 50 m2. Según el po al en línea de
es adís icas S a is a, du an e el p ime imes e de 2023 el p ecio medio anual de alquile del m2 de
suelo indus ial (más conc e amen e, almacenes), ue de 300 €, po lo que podemos es ima un cos e
ijo de 15.000 € anuales en concep o de alquile del cen o de dis ibución.
Además, es necesa ia mano de ob a pa a la ca ga y desca ga de ma e iales, aunque es a es pun ual
(ap oximadamen e una ho a) dos eces a la semana. El cos e medio ho a io de la mano de ob a en
Ingla e a es de 25 €/h, po lo que semanalmen e se gas a ían 50 € y suponiendo que hay u a las 52
semanas del año, el cos e o al de la mano de ob a en el cen o de dis ibución se ía de 2600 €. Cabe
des aca que el cen o de dis ibución ealmen e solo es a ía ocupado du an e dos días a la semana, po
lo que se ía posible busca al e na i as más económicas que pe mi iesen compa i un almacén de
mane a coo dinada, pe o queda ue a del alcance de es e abajo académico.
El cos e anual del CEDI se ía, po an o:
𝐶𝐶𝐸𝐷𝐼 =𝐶𝑚𝑎𝑛𝑜⁡𝑑𝑒⁡𝑜𝑏𝑟𝑎 +𝐶𝑎𝑙𝑞𝑢𝑖𝑙𝑒𝑟 =⁡⁡⁡17.200⁡€⁡
(6.7)
Calculamos aho a el cos e o al:
𝐶𝑎𝑛𝑢𝑎𝑙 =𝐶𝑡,𝑇𝑅𝐴𝐼𝐿𝐸𝑅 +𝐶𝑡,𝐹𝑈𝑅𝐺𝑂𝑁𝐸𝑇𝐴 +𝐶𝐶𝐸𝐷𝐼 =⁡𝟏.𝟎𝟎𝟕.𝟗𝟓𝟕,𝟒𝟓⁡€⁡
(6.8)
Pa a pode compa a es a opción con el AS-IS que se enía, se oman los da os del úl imo año de g upaje y se
calcula el cos e medio po anspo e. En es e ipo de anspo es, el cos e a ía poco en e unas localizaciones
u o as, po lo que se puede conside a el cos e homogéneo y de 325 € po TR. Conside ando el núme o de
en egas en 2116 y el núme o de ecogidas en 1060 (al igual que en el caso an e io ), el cos e o al esul a á de
mul iplica 3176 TRs po 350 €/TR:
𝐶𝑎𝑛𝑢𝑎𝑙,𝑔𝑟𝑢𝑝𝑎𝑗𝑒 =𝑛𝑇𝑅 ∙𝐶𝑇𝑅 =⁡⁡𝟏.𝟎𝟑𝟐.𝟐𝟎𝟎,𝟎𝟎⁡€⁡⁡
(6.9)
De es a o ma, hab emos conseguido no solo educi el Lead Time, sino además educi sensiblemen e el
cos e. El aho o económico de es a solución se ci a en 24.242,55 €, que ep esen a una educción del 2,35%.
71
71
Op imización de anspo es de epa ables en el sec o ae onáu ico
Figu a 6.8. Compa a i a de cos es de AS-IS s TO-BE
En es e pun o, cabe des aca que si no se hubiesen u ilizado algo i mos de op imización, simplemen e con el
algo i mo de ba ido el cos e de anspo e pu o de las u as de epa o hab ía sido de 391.475,78 €, casi
70.000 € más, lo que hab ía hecho el business case nega i o. En la siguien e abla se mues an cómo hab ían
sido los cos es o ales en caso de u iliza cada algo i mo de op imización, así como el aho o ob enido:
Cos e o al
Sa ing (€)
Sa ing (%)
G upaje
1.032.200,00 €
Algo i mo de ba ido
1.077.056,74 €
- 44.856,74 €
-4,35%
Heu ís ica del ecino más ce cano
1.021.299,58 €
10.900,42 €
1,06%
Búsqueda local con pe mu a de nodos adyacen es
1.014.136,34 €
18.063,66 €
1,75%
Búsqueda local con pe mu a de nodos no isi ados
1.007.957,45 €
24.242,55 €
2,35%
Tabla 6.3. Compa a i a de cos es de AS-IS con TO-BE pa a cada algo i mo de op imización
Aunque el aumen o de cos es que se hubiese p oducido u ilizando únicamen e el algo i mo de ba ido hubiese
cumplido con los eque imien os del p oyec o, que e a aumen a cos es menos de un 5% ( éase el Capí ulo
1.2), habe hecho uso de mé odos heu ís icos nos ha aho ado más de 65 k€.
Figu a 6.9. Rep esen ación g á ica de la ompa a i a de cos es pa a cada algo i mo de op imización
Re e encias
78
Za agoza.
[17]
To h, P. y Vigo, D. (2022). The Vehicle Rou ing P oblem. Socie y o Indus ial and Applied Ma hema ics
(SIAM) monog aphs on disc e e ma hema ics and applica ions.
[18]
Klapi a, V. y Š eco á, Z. (2010). Logis ics cen e s loca ion. T anspo , 21(1), 48-52.
[19]
Lüe , A., Bena en e, M., Bus os, J., y Venegas, B. (2009). El p oblema de u as de ehículos:
Ex ensiones y mé odos de esolución, es ado del a e. WORKSHOP INTERNATIONAL. Temuco.
[20]
González, D. y Gómez, D. (2019). Solución al p oblema de u eo de ehículos con en egas y ecogidas
aplicando el algo i mo de pé alos y la heu ís ica del ecino más ce cano. P oyec o Cu icula Ingenie ía
de P oducción. Uni e sidad Dis i al F ancisco José De Caldas.
[21]
Ryan, D. M., Hjo ing, C., & Glo e , F. (1993). Ex ensions o he pe al me hod o ehicle ou eing.
Jou nal o he Ope a ional Resea ch Socie y, 44(3), 289-296.
[22]
Sen hil Kuma , V. V. y Jayachi a R. (2016). Linea Sweep Algo i hm o Vehicle Rou ing P oblem wi h
Simul aneous Pickup and Deli e y be ween Two Depo s wi h Se e al Nodes. Global Jou nal o Pu e and
Applied Ma hema ics.ISSN 0973-1768 Volume 12, Numbe 1 (2016), 897-908.
[23]
B. A. Fos e y D. M. Ryan (1976). An in ege p og amming app oach o he ehicle scheduling p oblem.
Opl Res. Q. 27, 367-284.
[24]
G. Lapo e y Y. Nobe (1987). Exac algo i hms o he ehicle ou ing p oblem. Ann Disc e e Ma h, 31,
147-184.
[25]
Rosenk an z, D. J., S ea ns, R. E., y Lewis, P. (1977). An analysis o se e al heu is ics o he a eling
salesman p oblem. SIAM Jou nal on Compu ing, 6(3), 563-581.
[26]
S a is a. (2023). Indus ial and Logis ics Real es a e en pe squa e me e in Eu ope 2023, by ma ke .
h ps://www.s a is a.com/s a is ics/858110/a e age-annual-indus ial- en -cos -pe -squa e-me e -by-
eu opean-coun y
[27]
Minis e io de Fomen o de España (2023) Obse a o io de cos es del anspo e de me cancía po
ca e e a. Julio 2023. Cos es del T anspo e de Me cancía po Ca e e a, 2, 6-50.

79
79
Op imización de anspo es de epa ables en el sec o ae onáu ico
ANEXOS
Anexo I: Ma iz de dis ancias
n 0 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
00,0 61,6 76,8 24,4 162,4 84,8 65,7 158,1 93,4 186,7 95,9 116,3 75,6 74,3 71,6 74,0 96,4 120,3 135,0 119,5 214,6 193,1 435,2 180,9 149,2 205,4 131,5 143,2 179,0 349,9 262,4 51,5 251,5 121,3 262,2
161,6 0,0 27,0 41,1 125,4 65,4 55,1 129,2 74,4 157,8 104,5 127,5 109,7 132,8 132,1 135,1 157,4 180,6 194,1 177,8 267,9 244,2 483,6 221,3 176,6 229,2 156,5 148,5 178,9 339,8 252,4 66,2 234,9 108,9 239,2
276,8 27,0 0,0 52,7 98,4 44,4 41,3 102,5 52,2 131,0 89,5 111,7 105,1 140,5 142,1 146,1 168,1 197,0 211,8 196,1 289,4 266,6 507,2 246,4 203,1 256,1 183,2 175,3 205,1 363,7 276,8 92,3 258,0 134,5 260,6
324,4 41,1 52,7 0,0 139,4 63,4 44,9 136,5 72,5 165,4 83,9 106,2 75,2 91,7 91,4 94,8 117,1 144,3 159,2 143,8 238,7 216,9 458,8 202,4 166,5 222,1 147,8 152,7 187,1 355,6 267,6 59,6 254,1 123,5 262,3
4162,4 125,4 98,4 139,4 0,0 78,6 97,6 22,2 71,6 37,7 102,0 108,7 143,4 202,0 208,7 214,6 233,2 273,7 290,9 277,3 375,6 355,1 597,4 341,4 301,0 354,4 281,2 273,1 301,2 452,2 367,3 189,9 345,3 229,9 343,4
584,8 65,4 44,4 63,4 78,6 0,0 19,2 73,3 9,5 102,1 47,8 68,6 75,5 126,8 132,1 137,6 157,4 195,6 212,6 198,7 297,0 276,8 519,0 265,4 229,4 284,5 210,3 210,2 242,4 405,1 317,7 119,8 300,2 173,6 304,0
665,7 55,1 41,3 44,9 97,6 19,2 0,0 92,4 27,8 121,0 49,6 72,6 65,4 110,7 115,1 120,3 140,8 177,4 194,1 180,0 278,0 257,6 499,9 246,5 211,4 266,8 192,5 194,6 227,7 392,7 305,0 102,9 288,8 160,4 294,0
7158,1 129,2 102,5 136,5 22,2 73,3 92,4 0,0 64,7 29,1 86,6 90,0 129,3 190,1 197,8 203,9 221,4 264,1 281,9 269,0 368,3 349,0 591,1 338,8 301,5 356,0 282,1 277,7 307,5 462,8 377,0 190,9 356,2 236,7 355,7
893,4 74,4 52,2 72,5 71,6 9,5 27,8 64,7 0,0 93,3 44,7 63,7 77,3 131,6 137,7 143,3 162,6 202,1 219,4 205,8 304,5 284,6 526,9 274,2 238,7 293,9 219,6 219,7 251,8 414,2 326,8 129,3 309,1 182,9 312,5
9186,7 157,8 131,0 165,4 37,7 102,1 121,0 29,1 93,3 0,0 109,7 108,4 152,9 215,0 223,3 229,6 246,2 290,3 308,3 295,9 395,5 376,7 618,7 367,5 330,6 385,1 311,2 306,3 335,7 489,0 403,8 219,9 382,3 264,7 380,8
10 95,9 104,5 89,5 83,9 102,0 47,8 49,6 86,6 44,7 109,7 0,0 23,1 43,2 105,7 114,7 121,1 136,7 182,3 200,7 189,5 289,5 272,6 513,0 271,4 244,8 301,0 227,4 236,4 271,1 439,0 351,0 143,2 336,3 206,4 342,6
11 116,3 127,5 111,7 106,2 108,7 68,6 72,6 90,0 63,7 108,4 23,1 0,0 52,2 114,3 124,7 131,4 144,1 192,2 211,0 201,1 300,6 285,3 523,8 287,8 264,1 320,4 247,3 258,2 293,1 461,6 373,7 164,9 359,2 229,2 365,7
12 75,6 109,7 105,1 75,2 143,4 75,5 65,4 129,3 77,3 152,9 43,2 52,2 0,0 63,0 72,8 79,4 93,7 140,5 159,2 148,9 248,6 233,1 472,0 236,9 217,0 273,0 201,4 218,2 254,3 425,5 338,0 127,1 326,7 196,1 336,4
13 74,3 132,8 140,5 91,7 202,0 126,8 110,7 190,1 131,6 215,0 105,7 114,3 63,0 0,0 12,4 18,6 31,3 78,0 96,8 88,0 186,6 172,8 409,5 183,9 176,0 229,6 164,3 192,9 229,4 400,8 315,7 115,9 310,0 185,0 324,4
14 71,6 132,1 142,1 91,4 208,7 132,1 115,1 197,8 137,7 223,3 114,7 124,7 72,8 12,4 0,0 6,7 26,0 67,7 86,3 76,6 175,9 161,3 399,1 171,5 164,1 217,4 152,8 182,7 219,1 390,2 305,5 109,1 300,6 177,0 315,6
15 74,0 135,1 146,1 94,8 214,6 137,6 120,3 203,9 143,3 229,6 121,1 131,4 79,4 18,6 6,7 0,0 22,3 61,2 79,8 70,0 169,2 154,6 392,5 165,4 159,3 212,2 148,6 179,7 216,0 386,6 302,3 108,8 298,1 175,7 313,5
16 96,4 157,4 168,1 117,1 233,2 157,4 140,8 221,4 162,6 246,2 136,7 144,1 93,7 31,3 26,0 22,3 0,0 50,6 69,3 63,9 158,9 147,4 380,6 166,0 167,8 218,2 159,3 194,2 229,9 398,9 316,0 129,1 313,5 194,2 330,1
17 120,3 180,6 197,0 144,3 273,7 195,6 177,4 264,1 202,1 290,3 182,3 192,2 140,5 78,0 67,7 61,2 50,6 0,0 18,9 17,6 108,8 96,9 331,6 121,1 135,8 179,9 132,7 175,2 207,9 370,2 291,7 134,5 293,8 187,8 313,6
18 135,0 194,1 211,8 159,2 290,9 212,6 194,1 281,9 219,4 308,3 200,7 211,0 159,2 96,8 86,3 79,8 69,3 18,9 0,0 16,9 89,9 78,7 312,8 107,7 129,8 169,6 129,4 174,3 205,2 363,4 287,2 143,8 291,3 191,7 312,2
19 119,5 177,8 196,1 143,8 277,3 198,7 180,0 269,0 205,8 295,9 189,5 201,1 148,9 88,0 76,6 70,0 63,9 17,6 16,9 0,0 100,0 84,7 323,6 104,2 118,7 162,3 116,5 160,0 192,0 353,1 275,1 126,9 278,0 175,5 298,3
20 214,6 267,9 289,4 238,7 375,6 297,0 278,0 368,3 304,5 395,5 289,5 300,6 248,6 186,6 175,9 169,2 158,9 108,8 89,9 100,0 0,0 27,4 223,6 83,0 138,6 147,7 150,8 197,6 216,9 344,6 283,5 207,4 296,9 232,4 322,3
21 193,1 244,2 266,6 216,9 355,1 276,8 257,6 349,0 284,6 376,7 272,6 285,3 233,1 172,8 161,3 154,6 147,4 96,9 78,7 84,7 27,4 0,0 242,3 57,8 111,5 124,7 123,4 170,3 190,3 323,2 259,1 182,3 271,4 205,1 296,3
22 435,2 483,6 507,2 458,8 597,4 519,0 499,9 591,1 526,9 618,7 513,0 523,8 472,0 409,5 399,1 392,5 380,6 331,6 312,8 323,6 223,6 242,3 0,0 265,1 320,8 289,7 339,8 375,9 376,9 421,5 403,7 418,8 429,7 422,1 457,4
23 180,9 221,3 246,4 202,4 341,4 265,4 246,5 338,8 274,2 367,5 271,4 287,8 236,9 183,9 171,5 165,4 166,0 121,1 107,7 104,2 83,0 57,8 265,1 0,0 59,8 67,9 76,5 119,5 134,8 266,9 201,3 155,4 214,0 160,5 239,3
24 149,2 176,6 203,1 166,5 301,0 229,4 211,4 301,5 238,7 330,6 244,8 264,1 217,0 176,0 164,1 159,3 167,8 135,8 129,8 118,7 138,6 111,5 320,8 59,8 0,0 56,3 20,3 59,7 79,9 234,4 157,7 111,1 164,3 101,7 187,5
25 205,4 229,2 256,1 222,1 354,4 284,5 266,8 356,0 293,9 385,1 301,0 320,4 273,0 229,6 217,4 212,2 218,2 179,9 169,6 162,3 147,7 124,7 289,7 67,9 56,3 0,0 74,3 90,9 87,3 199,0 136,7 165,2 153,6 139,8 180,4
26 131,5 156,5 183,2 147,8 281,2 210,3 192,5 282,1 219,6 311,2 227,4 247,3 201,4 164,3 152,8 148,6 159,3 132,7 129,4 116,5 150,8 123,4 339,8 76,5 20,3 74,3 0,0 47,7 75,8 239,8 159,1 91,4 161,8 84,1 183,2
27 143,2 148,5 175,3 152,7 273,1 210,2 194,6 277,7 219,7 306,3 236,4 258,2 218,2 192,9 182,7 179,7 194,2 175,2 174,3 160,0 197,6 170,3 375,9 119,5 59,7 90,9 47,7 0,0 36,6 208,7 122,8 93,3 119,6 49,0 138,4
28 179,0 178,9 205,1 187,1 301,2 242,4 227,7 307,5 251,8 335,7 271,1 293,1 254,3 229,4 219,1 216,0 229,9 207,9 205,2 192,0 216,9 190,3 376,9 134,8 79,9 87,3 75,8 36,6 0,0 172,1 86,4 128,3 86,1 71,4 107,9
29 349,9 339,8 363,7 355,6 452,2 405,1 392,7 462,8 414,2 489,0 439,0 461,6 425,5 400,8 390,2 386,6 398,9 370,2 363,4 353,1 344,6 323,2 421,5 266,9 234,4 199,0 239,8 208,7 172,1 0,0 87,9 298,6 106,8 232,6 113,9
30 262,4 252,4 276,8 267,6 367,3 317,7 305,0 377,0 326,8 403,8 351,0 373,7 338,0 315,7 305,5 302,3 316,0 291,7 287,2 275,1 283,5 259,1 403,7 201,3 157,7 136,7 159,1 122,8 86,4 87,9 0,0 210,9 31,3 144,7 56,0
31 51,5 66,2 92,3 59,6 189,9 119,8 102,9 190,9 129,3 219,9 143,2 164,9 127,1 115,9 109,1 108,8 129,1 134,5 143,8 126,9 207,4 182,3 418,8 155,4 111,1 165,2 91,4 93,3 128,3 298,6 210,9 0,0 200,1 70,6 211,5
32 251,5 234,9 258,0 254,1 345,3 300,2 288,8 356,2 309,1 382,3 336,3 359,2 326,7 310,0 300,6 298,1 313,5 293,8 291,3 278,0 296,9 271,4 429,7 214,0 164,3 153,6 161,8 119,6 86,1 106,8 31,3 200,1 0,0 130,8 27,7
33 121,3 108,9 134,5 123,5 229,9 173,6 160,4 236,7 182,9 264,7 206,4 229,2 196,1 185,0 177,0 175,7 194,2 187,8 191,7 175,5 232,4 205,1 422,1 160,5 101,7 139,8 84,1 49,0 71,4 232,6 144,7 70,6 130,8 0,0 141,0
34 262,2 239,2 260,6 262,3 343,4 304,0 294,0 355,7 312,5 380,8 342,6 365,7 336,4 324,4 315,6 313,5 330,1 313,6 312,2 298,3 322,3 296,3 457,4 239,3 187,5 180,4 183,2 138,4 107,9 113,9 56,0 211,5 27,7 141,0 0,0
Anexos
80
Anexo II: Demandas de ecogidas y en egas simuladas pa a un año comple o
Ciudad
Núme o de
TRs a
en ega
o al
CW01 CW02 CW03 CW04 CW05 CW06 CW07 CW08 CW09 CW10 CW11 CW12 CW13 CW14 CW15 CW16 CW17 CW18 CW19 CW20 CW21 CW22 CW23 CW24 CW25 CW26 CW27 CW28 CW29 CW30 CW31 CW32 CW33 CW34 CW35 CW36 CW37 CW38 CW39 CW40 CW41 CW42 CW43 CW44 CW45 CW46 CW47 CW48 CW49 CW50 CW51 CW52
ISLE OF WIGHT 63 3013310203112022113103021000000030300300003033300303
WIMBORNE 91 3243114310242032000304431201104430012400330214220020
SOUTHEND-ON-SEA 56 5 5 1 1 2 0 1 2 2 2 2 2 2 1 0 2 0 0 0 0 0 1 1 0 1 1 2 0 1 5 1 1 0 0 0 0 0 1 1 1 0 2 2 1 0 0 0 0 0 2 2 0
OXFORDSHIRE 35 0121010112111021100200001111011101020010000111200100
GLOUCESTER 193 6754407457040716064360658603344620482530500756680001
BRISTOL 66 3100111211022202222000000102223020030332012221021232
COVENTRY 112 2267002450307004313000016310050010016340600575302004
CRAWLEY 72 1801001202100011032312202221323310322133002010201020
WOLVERHAMPTON 66 2002333002010020121020200023232033033203201011101310
BRIDPORT 53 0410221121211111112111001121120112111020100120101011
LONDON 49 0021102012010020121212232101100011010102010110021312
POOLE 31 1012000100011001010010110100110110111211110111001010
HEREFORD 80 0022300130100134440002400030033400512000202002443134
MARLOW 67 1022122130113342103204040230110000000232223002000002
LUTON 30 1201010012100001022220000011200000010021200000100100
TITCHFIELD 27 0111000110110100001010001111011001100101111000101110
PORTSMOUTH 80 2520423103202040130013333000140230002304103000210322
ESSEX 36 1101110000012000010221100221100000112121011110100110
WATERHEAD 52 0000102301320000022100002200020321222120220220120111
YEOVIL 59 1010202310323011213200031321121001211230010002031000
REDDITCH 29 1210001111010110010001121000000011000101111110011001
LEIGHTON BUZZARD 39 1 0 1 0 0 0 1 1 2 2 2 0 2 2 1 0 0 2 0 0 1 1 0 1 0 1 2 2 0 0 1 1 2 0 0 2 0 1 1 0 1 0 0 1 0 1 0 0 0 1 2 0
WEST SUSSEX 43 1212101120100001100010111100110112221002110021020211
VERWOOD, DORSET 130 2 3 6 3 3 1 5 4 4 0 0 0 0 0 6 7 0 0 0 2 0 5 5 2 0 1 2 4 4 5 3 5 0 1 1 4 5 0 6 5 3 1 1 0 4 5 0 5 4 0 1 2
CHELTENHAM 48 2210100300000022112220101110222100120011010102220021
HANFORTH 43 2100101012100001102202111200122201112000001022002002
MARSTON 53 1022101102200102202002022212122110012000220202100211
BLACKPOOL 28 0500000000550000000000000000003001220000000500000000
SUSSEX 76 2600211140103432010300020030302120300014032033032320
BASILDON, ESSEX 63 1 3 0 2 0 2 1 0 0 0 3 0 3 1 1 0 3 0 3 2 0 2 1 3 2 0 0 0 3 0 2 0 0 1 2 3 3 1 0 2 2 0 2 0 2 0 1 2 0 1 1 2
CORNWALL 73 3002330122213122123201201200232122302303001212101010
CHRISTCHURCH 34 2100010220011011010000001111102011210201200000101011
FAREHAM-HAMPHIRE 67 2 7 2 2 2 1 0 3 3 1 0 2 0 2 1 2 0 3 0 2 0 0 3 1 2 2 0 3 0 0 1 0 2 2 3 2 0 0 3 1 0 0 0 1 0 1 0 0 2 2 0 1
SOUTHALL 72 1140132002212123133001220000000340303021042233010220
81
81
Op imización de anspo es de epa ables en el sec o ae onáu ico
Ciudad
Nº de TRs a
ecoge o al
CW01 CW02 CW03 CW04 CW05 CW06 CW07 CW08 CW09 CW10 CW11 CW12 CW13 CW14 CW15 CW16 CW17 CW18 CW19 CW20 CW21 CW22 CW23 CW24 CW25 CW26 CW27 CW28 CW29 CW30 CW31 CW32 CW33 CW34 CW35 CW36 CW37 CW38 CW39 CW40 CW41 CW42 CW43 CW44 CW45 CW46 CW47 CW48 CW49 CW50 CW51 CW52
ISLE OF WIGHT 62 2 2 0 2 0 0 1 3 0 2 0 1 0 0 1 1 1 0 0 1 2 0 0 1 2 2 1 0 0 1 1 3 2 2 3 3 0 2 2 2 1 0 2 2 2 2 0 2 2 2 0 1
WIMBORNE 76 0113000203322031013213012310122323112021020232202002
SOUTHEND-ON-SEA 33 0 3 1 1 0 0 0 1 0 2 0 1 1 1 2 1 1 1 1 1 0 1 0 0 1 0 1 0 0 0 1 0 1 1 0 1 0 0 0 1 0 1 1 1 0 0 1 0 0 0 0 1
OXFORDSHIRE 2 0000000000000000000000000000000000000000000000000000
GLOUCESTER 26 1111001101010011010011101110110000110000101110001100
BRISTOL 65 0572121110000602001110502123002011200201021013120001
COVENTRY 38 1020111001102100001001221101101201010000110110110211
CRAWLEY 29 1110011000101001000101110011110010010011101010110101
WOLVERHAMPTON 29 0 5 1 1 1 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 1 1 1 0 0 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 1
BRIDPORT 29 1101200100100010000011010110010112100010010001111100
LONDON 29 0101101111100001100010010100010110100001110100110110
POOLE 4 0100000000000000000000000000000000000000000000000000
HEREFORD 4 0000000000000000000000000000000000000000000000000000
MARLOW 31 0201000110001100011021001001011011010101010111002110
LUTON 32 1110110000110100011011011000100011111100010111010111
TITCHFIELD 29 0011100111101111000111101110100111010011011010101000
PORTSMOUTH 36 0500001111003200100111010111111001000101111001100010
ESSEX 28 0011011010011001101101000110101000111101110000000111
WATERHEAD 28 0500001101100000100100111107000001000010000101010011
YEOVIL 26 0000101000000010011011110000001010010101101100111111
REDDITCH 27 0011101111001010110101010000110101011001111000001101
LEIGHTON BUZZARD 27 0 1 1 0 1 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 1 1 1 0 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 1 1 1 1 0 1 0 1 1 0
WEST SUSSEX 3 0200000000000000000000000000000000000000000000000000
VERWOOD, DORSET 131 4 5 5 3 3 5 0 0 3 4 0 2 4 6 5 3 0 4 0 5 3 3 5 4 6 5 0 0 3 0 5 2 0 0 0 1 2 5 5 0 2 4 1 6 0 0 0 1 0 6 0 0
CHELTENHAM 31 0400201110001110110010001000022001100211001010010001
HANFORTH 74 3130113112310301020200302010002201332303042322313002
MARSTON 4 0000000000000000000000000000000000000000000000000000
BLACKPOOL 1 0000000000000000000000000000000000000000000000000000
SUSSEX 0 0000000000000000000000000000000000000000000000000000
BASILDON, ESSEX 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
CORNWALL 28 1000010001000110000102120100111002001002111102110001
CHRISTCHURCH 15 0 0 0 0 1 0 0 0 0 0 1 1 1 0 1 0 1 1 1 0 0 1 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
FAREHAM-HAMPHIRE 52 0 0 0 1 0 0 0 2 3 2 0 0 2 0 0 3 2 1 1 1 3 1 0 3 2 2 0 0 0 3 3 0 1 0 1 2 1 1 3 0 1 1 0 0 0 1 1 3 1 2 0 0
SOUTHALL 29 1001101111110110000100111000010101100000101101101011
Anexos
82
Anexo III: Código de p og amación en Visual Basic
- Decla ación de a iables globales y mac o p incipal:
Public n_nodes
Public id
Public ci y
Public x
Public y
Public
Public he a
Public deli e ies
Public collec ions
'Pa áme os del p oblema
Public Cons max_TR As In ege = 10 ' Capacidad máxima del ehículo
Public Cons max_ ehicles As In ege = 15 ' Núme o máximo de ehículos de la lo a
Sub main()
Applica ion.Sc eenUpda ing = False
Call impo _da a ' Mac o que impo a los da os en a iables globales
Call e ase_ esul s ' Mac o que bo a los esul ados del p oblema an e io
Call pe als ' Mac o que de ine los pé alos de las u as
Call neighbo _heu is ic ' Mac o que op imiza cada pé alo median e hau ís ica del ecino más ce cano
Call local_sea ch ' Mac o que op imiza cada pé alo median e búsqueda local
Call local_sea ch__bis ' Mac o que op imiza cada pé alo median e búsqueda local con el es o de nodos de la
u a
End Sub
- Mac o que impo a los da os del p oblema:
Sub impo _da a()
Shee s("Da a").Selec
n_nodes = Range("A2").End(xlDown).Row - 3 ' Núme o de nodos (sin con a el CEDI)
ReDim id(n_nodes) ' ID del nodo (el CEDI es el nodo 0)
ReDim ci y(n_nodes) ' Nomb e de la ciudad del nodo
ReDim x(n_nodes) ' Coo denada x del nodo
ReDim y(n_nodes) ' Coo denada y del nodo
ReDim (n_nodes) ' Coo denada pola del nodo
ReDim he a(n_nodes) ' Coo denada pola he a del nodo
ReDim deli e ies(n_nodes) ' Núme o de TRs a en ega en el nodo
ReDim collec ions(n_nodes) ' Núme o de TRs a ecoge en el nodo
Fo i = 0 To n_nodes
id(i) = Range("A2").O se (i + 1, 0).Value
ci y(i) = Range("B2").O se (i + 1, 0).Value
deli e ies(i) = Range("C2").O se (i + 1, 0).Value
collec ions(i) = Range("D2").O se (i + 1, 0).Value
x(i) = Range("H2").O se (i + 1, 0).Value
y(i) = Range("I2").O se (i + 1, 0).Value
(i) = Range("J2").O se (i + 1, 0).Value
he a(i) = Range("K2").O se (i + 1, 0).Value
Nex
End Sub
- Mac o que bo a los da os del p oblema an e io :
Sub e ase_ esul s()
Shee s("Resul ado").Selec
Range("C2:L16").Clea Con en s
Shee s("Resul ado_2").Selec
Range("C2:L16").Clea Con en s
Shee s("Resul ado_3").Selec
Range("C2:L16").Clea Con en s
Shee s("Resul ado_4").Selec
Range("C2:L16").Clea Con en s
83
83
Op imización de anspo es de epa ables en el sec o ae onáu ico
End Sub
- Mac o que o ma los pé alos con el Algo i mo de Ba ido:
Sub pe als()
Dim ehicle(max_ ehicles) As In ege ' Núme o de ehículo ( u a)
Dim cus ome As In ege ' Núme o de nodo eco ido
Dim n_collec ed As In ege ' Núme o de TRs eco idos du an e la u a
Dim n_ o_deli e As In ege ' Núme o de TRs pendien es de en ega du an e la u a
Dim n_ esul (max_ ehicles) As In ege ' Nodos que alcanza cada u a
Dim j As In ege ' Va iable auxilia pa a imp imi los nodos- u a en la hoja de esul ados
Shee s("Resul ado").Selec
Range("C2:L16").Clea Con en s ' Bo amos el esul ado de la u a an e io
cus ome = 1 ' Comienzo con el p ime clien e, sal ándome el CEDI
Fo n_ ou e = 1 To max_ ehicles ' I e o pa a cada u a
j = 0
ehicle(n_ ou e) = max_TR ' De ino la ca ga del ehículo como la máxima posible
While max_TR - ehicle(n_ ou e) < collec ions(cus ome ) - deli e ies(cus ome )
ehicle(n_ ou e) = ehicle(n_ ou e) - 1 ' Si en el p ime nodo la demanda de ecogida es la mayo
que la demanda de en ega, ca go un TR menos pa a hace hueco a la ecogida y pode comenza la u a
Wend
n_ o_deli e = ehicle(n_ ou e) ' De ino la can idad de TRs en en ega
n_collec ed = 0 ' Al inicio de la u a, no hab é ecogido ningún TR
While ( ehicle(n_ ou e) + collec ions(cus ome ) - deli e ies(cus ome )) <= max_TR And n_ o_deli e >=
deli e ies(cus ome ) ' Aho a i e o has a que se llene el camión o se acaben las en egas pendien es
ehicle(n_ ou e) = ehicle(n_ ou e) + collec ions(cus ome ) - deli e ies(cus ome )
n_collec ed = n_collec ed + collec ions(cus ome ) ' Su suman los TRs ecogidos a la cuen a de
ecogidas
n_ o_deli e = n_ o_deli e - deli e ies(cus ome ) ' Su es an los TRs en egados a la cuen a de
en egas pendien es
j = j + 1
Shee s("Resul ado").Range("A1").O se (n_ ou e, j + 1).Value = cus ome
cus ome = cus ome + 1 ' Voy al siguien e nodo
I cus ome = n_nodes + 1 Then ' Cuando llego al úl imo clien e, salgo del bucle
GoTo inished
End I
Wend
n_ esul (n_ ou e) = cus ome - 1 ' La a iable n_ esul oma el ID del úl imo nodo isi ado po cada
ehículo
Nex
inished:
n_ esul (n_ ou e) = cus ome - 1
End Sub
- Mac o que aplica la heu ís ica del ecino más ce cano:
Sub neighbo _heu is ic()
Dim m_dis (34, 34) ' Ma iz de dis ancias
Dim m_ es(15, 11) ' Ma iz esul ado del algo i mo de pé alos
Dim m_ ou es(15, 11) ' Ma iz de u as
Dim isi (15, 11) As Boolean ' Vec o de isi a
Dim ac _node ' Nodo ac ual
Dim min_dis As Double ' Va iable auxilia pa a dis ancia mínima
Dim neighbo As In ege ' Vecino más ce cano
Dim nex _node As In ege ' Va iabla auxilia pa a conoce la ID del siguien e nodo
' Ca ga de la ma iz de dis ancias
Shee s("ma iz_dis ancias").Selec
Fo a = 0 To 34
Fo b = 0 To 34
m_dis (a, b) = Range("B2").O se (a, b).Value
Nex
Nex
' Ca ga del esul ado del algo i mo de pé alos
Shee s("Resul ado").Selec

Anexos
84
Fo m = 1 To max_ ehicles
Fo n = 0 To max_TR
m_ es(m, n) = Range("B2").O se (m - 1, n).Value
Nex
Nex
'Algo i mo de mejo a
Fo i = 1 To max_ ehicles ' En o en cada u a
' Comienzo en el nodo 0
ac _node = 0
m_ ou es(i, 0) = 0
isi (i, 0) = T ue
Fo j = 1 To max_TR
min_dis = -1
neighbo = -1
Fo k = 1 To max_TR
I No isi (i, k) And m_ es(i, k) <> "" Then
I min_dis = -1 O m_dis (ac _node, m_ es(i, k)) < min_dis Then
min_dis = m_dis (ac _node, m_ es(i, k))
neighbo = k
End I
End I
Nex
I neighbo <> -1 Then
isi (i, neighbo ) = T ue
m_ ou es(i, j) = m_ es(i, neighbo )
ac _node = m_ es(i, neighbo )
Else
m_ ou es(i, j) = ""
End I
Nex
Nex
Shee s("Resul ado_2").Selec
Fo i_aux = 1 To max_ ehicles
Fo j_aux = 1 To max_TR
Shee s("Resul ado_2").Range("A1").O se (i_aux, j_aux + 1).Value = m_ ou es(i_aux, j_aux)
Nex
Nex
End Sub
- Mac o que aplica el algo i mo de búsqueda local con pe mu a de nodos adyacen es:
Sub local_sea ch()
Dim m_dis (34, 34) ' Ma iz de dis ancias
Dim m_ es(15, 11) ' Ma iz esul ado del algo i mo de pé alos con heu ís ica de ecindad
Dim m_ ou es(15, 11) ' Ma iz de u as
Dim bes _d As Double
Dim aux As In ege ' Va iable auxilia pa a hace el in e cambio de nodos
' Ca ga de la ma iz de dis ancias
Shee s("ma iz_dis ancias").Selec
Fo a = 0 To 34
Fo b = 0 To 34
m_dis (a, b) = Range("B2").O se (a, b).Value
Nex
Nex
' Ca ga del esul ado del algo i mo de pé alos con heu ís ica de ecindad
Shee s("Resul ado_2").Selec
Fo m = 1 To max_ ehicles
Fo n = 0 To max_TR
m_ es(m, n) = Range("B2").O se (m - 1, n).Value
Nex
Nex
85
85
Op imización de anspo es de epa ables en el sec o ae onáu ico
Fo i = 1 To max_ ehicles
pe mu a = 1
While pe mu a = 1
pe mu a = 0
' Calculo dis ancia o al inicial
d = 0
Fo k = 0 To max_TR ' Calculo la dis ancia o al eco ida
I m_ es(i, k + 1) <> "" Then
d = d + m_dis (m_ es(i, k), m_ es(i, k + 1))
ElseI m_ es(i, k) <> "" Then
d = d + m_dis (m_ es(i, k), 0)
End I
Nex
bes _d = d
Fo j = 1 To max_TR
I m_ es(i, j + 1) <> "" Then
' In e cambio el nodo
aux = m_ es(i, j)
m_ es(i, j) = m_ es(i, j + 1)
m_ es(i, j + 1) = aux
' Calculo dis ancia o al
d = 0
Fo k = 0 To max_TR ' Calculo la dis ancia o al eco ida
I m_ es(i, k + 1) <> "" Then
d = d + m_dis (m_ es(i, k), m_ es(i, k + 1))
ElseI m_ es(i, k) <> "" Then
d = d + m_dis (m_ es(i, k), 0)
End I
Nex
I d < bes _d Then ' Si mejo a, me quedo con la dis ancia mínima
bes _d = d
pe mu a = 1
Else
aux = m_ es(i, j) ' Si no mejo a, deshago el cambio
m_ es(i, j) = m_ es(i, j + 1)
m_ es(i, j + 1) = aux
End I
End I
Nex
Wend
Nex
Shee s("Resul ado").Selec
Fo i_aux = 1 To max_ ehicles
Fo j_aux = 1 To max_TR
Shee s("Resul ado_3").Range("A1").O se (i_aux, j_aux + 1).Value = m_ es(i_aux, j_aux)
Nex
Nex
End Sub
- Mac o que aplica el algo i mo de búsqueda local con pe mu a de nodos no isi ados:
Sub local_sea ch_bis()
Dim m_dis (34, 34) ' Ma iz de dis ancias
Dim m_ es(15, 11) ' Ma iz esul ado del algo i mo de pé alos con heu ís ica de ecindad
Dim m_ ou es(15, 11) ' Ma iz de u as
Dim bes _d As Double
Dim aux As In ege ' Va iable auxilia pa a hace el in e cambio de nodos
' Ca ga de la ma iz de dis ancias
Shee s("ma iz_dis ancias").Selec
Fo a = 0 To 34
Anexos
86
Fo b = 0 To 34
m_dis (a, b) = Range("B2").O se (a, b).Value
Nex
Nex
' Ca ga del esul ado del algo i mo de pé alos con heu ís ica de ecindad
Shee s("Resul ado_3").Selec
Fo m = 1 To max_ ehicles
Fo n = 0 To max_TR
m_ es(m, n) = Range("B2").O se (m - 1, n).Value
Nex
Nex
Fo i = 1 To max_ ehicles
pe mu a = 1
While pe mu a = 1
pe mu a = 0
' Calculo dis ancia o al inicial
d = 0
Fo k = 0 To max_TR ' Calculo la dis ancia o al eco ida
I m_ es(i, k + 1) <> "" Then
d = d + m_dis (m_ es(i, k), m_ es(i, k + 1))
ElseI m_ es(i, k) <> "" Then
d = d + m_dis (m_ es(i, k), 0)
End I
Nex
bes _d = d
Fo j = 1 To max_TR
Fo p = j + 1 To max_TR
I m_ es(i, p) <> "" Then
' In e cambio el nodo
aux = m_ es(i, j)
m_ es(i, j) = m_ es(i, p)
m_ es(i, p) = aux
' Calculo dis ancia o al
d = 0
Fo k = 0 To max_TR ' Calculo la dis ancia o al eco ida
I m_ es(i, k + 1) <> "" Then
d = d + m_dis (m_ es(i, k), m_ es(i, k + 1))
ElseI m_ es(i, k) <> "" Then
d = d + m_dis (m_ es(i, k), 0)
End I
Nex
I d < bes _d Then ' Si mejo a, me quedo con la dis ancia mínima
bes _d = d
pe mu a = 1
Else
aux = m_ es(i, j) ' Si no mejo a, deshago el cambio
m_ es(i, j) = m_ es(i, p)
m_ es(i, p) = aux
End I
End I
Nex
Nex
Wend
Nex
Shee s("Resul ado_4").Selec
Fo i_aux = 1 To max_ ehicles
Fo j_aux = 1 To max_TR
Shee s("Resul ado_4").Range("A1").O se (i_aux, j_aux + 1).Value = m_ es(i_aux, j_aux)
Nex
Nex
End Sub