UNIVERSIDAD NACIONAL DE INGENIERIA

PROGRAMA ACADEMICO DE INGENIERIA INDUSTRIAL Y DE SISTEMAS

Anlisis e Implementacin de Procedimientos para

Solucin de Problemas de Distribucin y Localizacin
de Centros de Suministros

TE5I5 PRESENTADA PARA OPTAR EL TITULO DE INGENIERO INDUSTRIAL

ALFREDO JOS CELI PALOMINO

LIMA PER

1973
 INDICE

INTRODUCCION
LOCALIZACIN DEL DEPSITO SIMPLE DE UN CONJUNTO DE
CAPITULO I LOCALIDADE3 CON DEMANDAS DETERMINSTICAS

1.1 MODELO DEL PROBLEMA.

1.2 METODOS DE SOLUCION,
1.2.1 METODO DEL CENTRO DE GRAVEDAD.
1.2.2 ANALOGIA MECNICA.
1.2.3 MTODO NUMRICO ANALITICO.
1.3 DIAGRAMA EN GRANDES BLOQUES DEL PROGRAMA
FORTRAN APLICANDO AMBOS MTODOS.
1.4 EQUIVALENCIAS DE VARIABLES DEL PROGRAMA CON
VARIABLES DE LA FORMULACIN.
1.5 IDENTIFICACION DE VARIABLES DEL PROGRAMA.
1.6 PROGRAMA PRINCIPAL.
1.6.1 LECTURA DE DATOS.
1.6.2 PUBLICACIN DE REPORTES.
CAPITULO II
PROGRAMACION DE VEHICULOS.- REVISION DE LA
LITERATURA.
2.1 INTRODUCCION.
2.2 CLASIFICACION DEL PROBLEMA Y DEFINICION.
2.2.1 TERMINAL SIMPLE.
2.2.1.a PROBLEMA DEL AGENTE VIAJERO.
2.2.1.b RUTA SIMPLE DEL PRDBLEMA DE
REPARTO. PROBLEMADE
TRANSPORTISTAS
2.2.1 .c FLOTA HETEROGENEA
2.2.1 .d PORTADOR COMUN
2.2.2 TERMINAL MULTIPLE.
2.2.3 PROBLEMA GENERALIZADO DE
TRANSPORTISTAS.
CAPITULO III
FORMULACION DEL PBOBLEMA DE PROGRAMACIN DE
VEHICULOS (TRANSPORTISTAS).

EL PROBLBA DE TRANSPORTISTAS.
3.1 PROGRAMACION DINAMICA.
3.2 ALGORITMO BASADO EN LOS METODOS DE SOLUCION DEL
FROBLEMA DEL AGENTE VIAJERO
3.2.1 EJEMPLO NNUMRICO
3.3 ENFOQUE DE RAMIFICACION Y ACOTACION (BRANCH
AID BOUND).
3.3.1 EJEMPIO NUMRICO.
3.4 MTODO R-OPTIMO.
 3.5 ALGORITMOS BASADOS EN AHORROS.
3.5.1 ALGORITMO DE CLARKE Y WRIGHT.
EJEMPLO NUMERICO.
3.5.3 ALGORITMO DE TILLMAN Y COCHRANE.
EJEMPLO NUMERICO.
3.6 ALGORITMO DE GASKELL.
3.6.1 EJEMPLO NUMERICO.
3.7 UN METODO DE BUSQUEDA EN ARBOL BASADO EN LOS
AHORROS.
3.7.1 EJEMPLO NUMERICO.
3.8 ALGORITMO DE BAYES.

3.9 RESULTADOS COMPUTACIONALES Y CONCLUSIONES

CAPITULO IV : AGORITMO DE CLARKE Y WRIGHT.

4.1 FORMULACION
4.2 ASPECTO TEORICO DEL PROBLEMA.
4.3 PROCESO COMPUTACIONAL.
4.4 EJEMPLO NUMERICO.
4.5 EJEMPLO NUMERICO.

CAPITULO V : ALGORITMO DE TILLMAN Y COCHRANE.

5.1 FORMULACIN DEL ALGORITMO.
CAPITULO VI: RESUMBN DEL PROGRAMA FORTRAN VERSION D.0.S. PARA USO EN
LA COMPUTADORA IBM 380-40 DEL ALGORITMO DE TILLMAN.

6.1 DIA GRAMA DE FLUJO EN GRANDES BLOQUES.

6.2 LECTURA DE DATOS.- FORMATOS CORRESPONDIENTES.
6.3 PUBLICACION DE REPORTES.

CAPITULO VII APLICACION PRACTICA DEL ALGORITMO DE TTLLMAN A UNA

CADENA DE SUPERMERCADOS ( EPSA).

7.1 ENUNCIADO DEL PROBLEMA.

7.2 DATOS NECESARIOS.
7.3 COMPARACION DE RESULTADOS.

BIBLIOGRAFIA
 INTRODUCCION

Considerando la variedad de aplicaciones que en la actualidad se hacen con las computadoras y

teniendo en cuenta la necesidad de contar con programas que resuelvan determinados problemas

tericos y/ o prcticos cuyas soluciones ayuden a un mejor comprensin de los temas tratados, este

trabajo trata de investigar e implementar Algoritmos Heursticos aplicados & la solucin de

problemas de localizacin y distribucin de centros de suministros se presentan en el caso del

problemas de reparto, para el problema de transportistas.

En lo que respecta a localizacin de centros de suministros, se tiene varias localidades o clientes

que requieran ser abastecidos da algn producto (alimentos, combustibles, personal, etc.) para lo

cual debe determinarse la ubicacin del depsito o almacn desde donde sern satisfechas las

demandas de modo que se minimice una funcin objetivo que puede ser distancias, costos, etc.

o una combinacin de estas.

En lo referente e distribucin (clsico problema de transportistas) se conoce las demandas de los

clientes, las distancias desde ellos al centro da abastecimiento (depsito) y las distancias entre los

clientes. Se trata de encontrar las rutas que debe seguir una flota de vehculos para satisfacer la

demanda de todos los clientes y que cumpliendo con las restricciones que tenga el problema

minimice distancias, costos o una combinacin de ambas optimizando en consecuencia el nmero

de vehculos a usar.

La finalidad de este trabajo es presentar un resumen de la informacin encontrada que formara

parte de lo que sera el paquete de Sistemas de anlisis de Redes (SAR), que puede facilitar a los

alumnos que de
desarrollan el punto respectivo en los cursos de Investigacin de Operaciones a una mejor

comprensin de lo tratado.

El trmino EURSTICO no es ms que la aplicacin de sentido comn a 1a tcnica de

programacin pare orientar mejor la solucin de los problemas y permite en cierto modo

la optimizacin del tiempo de computadora y memoria de la misma, simplificando el

proceso de clculo y sacrificando algunas veces el valor ptimo por la reduccin de costos

de la solucin.

Tambin con este trabajo se trata de incentivar a los alumnos que lleven cursos orientados

al campo computacional como por ejemplo: Sistemas de Procesamiento de Informacin

(Cobol ). Control de Inventarios en lo que respecta a lotes econmicos, puntos de

reordenamientos, etc. Planeamiento y Control de la produccin en lo referente a

predicciones de demanda; Mtodos Estadsticos para calcular ajustes de curvas;

Investigacin de Operaciones en simulacin, transporte, etc.; para que desarrollen o

implementen programas que permitan formar una "biblioteca" que facilite la funcin

didctica de la Universidad entre otras cosas.

El contenido de esta tesis en forma general es el siguiente:

E1 captulo 1 trata de la localizacin del depsito simple de un conjunto de localidades con

demandas determinsticas. Se tiene (como se mencion antes) una serie de localidades

con demandas conocidas y la ubicacin de las localidades respecto do un origen de

coordenadas dando como base de medidas. Se trata de ubicar la localizacin del depsito

simple desde donde la distribucin de productos optimice la funcin costos distancias.

Incluyo en este captulo un programa versin explicado detalladamente que resuelve estos

problemas empleando los mtodos que tambin se describen.

E1 segundo captulo contiene la clasificacin del problema de programa

cin de Vehculos o problema do Reparto, con explicaciones sucintas de cada

subdivisin, donde una de ellas es el problema de transportistas ( rea que

comprende esta tesis ).

En el tercer captulo presento el problema de transportistas y varios

algoritmos conocidos que resuelvan este problema. He desarrollado un ejemplo

numrico en casi todos los algoritmos programados para indicar la forma de

resolver los problemas.

En el cuarto captulo explico detalladamente el Algoritmo de Clarke y Wright

que resuelve el problema de transportistas y con ejemplos numricos indico el

procedimiento de solucin.

En el quinto captulo presento el Algoritmo de Tillman y Cochrane que

tambin resuelve el problema de transportistas y con un ejemplo numrico voy

explicando la forma en que ste algoritmo enfoca y resuelve los problemas.

En el captulo VI muestro el diagrama en grandes bloques del programa

Fortran versin DOS que be diseado para aplicar el algoritmo de Tillman y

Cochrane. Tambin indico la forma que tienen que darse los datos y el

significado de los repartos que se publican. Las soluciones encontradas para

varios problemas corridos en la computadora de la Universidad se presentan

como anexos de esta tesis.

Teniendo en cuenta la necesidad e importancia de la aplicacin del ritmo de

Tillman a un caso prctico, he recurrido e IPSM (Empresa pblica de servicios

Agropecuarios) que es la entidad encargada de la administracin,

comercializacin y distribucin de productos alimenticios radiante la cadena

de supermercados Super-Epsa, para desarrollar en el ltimo captulo da sta

tesis el problema de distribucin de dicha empresa. En este captulo planteo el

problema y muestro los resultados los resultados obtenidos usando el

programa del algoritmo antes mencionado.

 CAPTULO I

LOCALIZACIN DEL DEPSITO SIMPLE DE UN CONJUNTO DE LOCALIDADES

CON DEMANDAS DETERMINISTICAS

Existe una gran variedad de problemas en donde se conoce les posibles localizaciones

de ciertos puntos de distribucin o consumo dadas por condiciones de mercado,

precios, etc.; cuyos requerimientos deben satisfacerse desde un terminal simple0 La

principal dificultad radica en donde debe estar ubicado este terminal simple de

modo que pueda ser minimizada ya sea la distancia total recorrida durante el reparto,

el costo total de transporte o finalmente une combinacin de costos y distancias.

Hay tambin situaciones por las que un punto que ha sido elegido ceno centro de

abastecimientos, debido entre otras cosas a:

- variaciones sustanciales de demanda en favor de ciertos clientes,

- en el caso de ser alquilado el local, piden su desocupacin o aumentan el

alquiler en forma inconveniente a los intereses de la empresa,

- los costos de transporte sufren alteraciones, etc.;

crean le necesidad de cambiar la ubicacin del depsito a fin de conseguir siempre

la minimizacin de factores costos, distancias, tiempos, etc.

1.1 Modelo del problema

E1 modelo consta de un depsito cuya localizacin en coordenadas cartesianas

se define como X1Y1. Este depsito debe suministrar algn producto a clientes

cuyas coordenadas referidas a un origen determinado cualquiera son XiYi ,

donde i = 1,2,..n.

Denominando al costo de transporte Cj los productos desde el depsito al

cliente j; el costo total de distribucin es:

 2

_lj_
( 1.1 )

considerando un juego de ,osibls Vf 102.es C t los cueles poder.io5

j
detemineir e lgun;; s i 1 terne. tives del de1)6sito desde donde deben

ser servidoG, li.. soluci6n r.ils ,:dccd; !JUede obten3rse de 1z. eve-

lUE ci6n do 1:. ocl.U) oi<1n ( le 1) perc c.:dc: loet lizec i6no

Si el coGto dol tr:nSl)orto depende en fon:i1i. linet 1 del l)GGo, d0

los productos y de L dietnci recorridc _ entonces t

c j .;.% wj a ( lr2 )
lj j

donde:

. >'.. costo pol:' unid.:.d de pi)so y pol' unif,d d3 dietLJncic. desde

1j
el deplto ... 1 cliente jo

W. peso tr,ns:part;:.do , cliente j des.ti el cl-spsito ( peGo

J
dal clien.to ) e

d dist;o.ncie dosde el cliente j ... 1 depsi to 11

j

Si la distancia en l!n.c;. recta ( l.wr.1adc:, dist.:.nc2 l"dil ) os 12

que usamos en lc:1 a oluci6n o.e p:rob1Q:,1c:: s., st.:: ser( :

( .L:-3 )

SiO( depende c6lo del clicmte que debe ssi' servido y no de 12

lj
ubieco15n del de_psito, teiemos ;

( lo4 )

resultndo 1E: funci6n costos

( lo5 )

TaL1bin en ost.:. acuc..ci6n, lo.s pc:r6ntroe pueden no ser line:lei:; y

en ese ci-.ao estor! . n ra:pror.;cnti<.1do:; por sdgun. E: f\U.lcion13s cont!nu3

 cuc:ndo ls velocidad de entregct de productos tiene groan significan-

cia, exist0 une f'unci6n que r.el"'ciona lB cntidad er,1,ndada po

cu-=.lqui er cli.ent0 j, dop0nc1iend.o del tiempo de cntrego 0 Eata fun -

cn os :

w v,Y.
j j

dono.e ..
wj centide. d ordentdo por el cliente j C\.l$ ndo o l tiempo de en-

trega es t o
j

v,Y.. ec.ntidad ordena.da con tiempo de e ntregB t
j
O

t tian.po de entreg de algn competid.or o

j
a factor de proporcionalidEld par-0 esp ecificer rea de den-

da y :productoo

Hay otros casos donde el tiGID.po dG entr ega al cliente j es propor

cion.:il el logaritmo do la distan cia de ese clienta 6 en f'orl'ile m6s

e,em::rel, cualquier f\mci6n convcnients puede usarse en un coso p..:,!_

ticulc:\r, sujeta lo eondici6n do que la. fun cin es cont!nua o

por simplicidad debe considerase que lu funci6n dG costo total es

lineal y se eqlcul, so6n L,i ecuacin (l c 5) o

ln2 M:ETODOS D$0IDQJ..QJ!o-

Si consideramos quo teuomoc slo dos clientoo, ol dcp6sito debe o

tfr ubict.do on la. linea recta que una e 6stoa clientes y cm un p

to proporcioral .a los pesos,,

Si las dcmendas do los clientes son igu,es y .(j pra todos ellos

es tnubin iguc.l, el probl01r.a trate!\ do minimizar la SUl"l(\ de :las

di stE1 ncia a radit} le s o

Tanando a.llore u n ejemplo con tres clientca; si loa pU!ltos formon

un tr1ngulo cuyos nguloo son menores que 120 , entonces la ubiCc":

 4

cin ptiraa del dep6sito e.8 aquell.;i desde donde se pusd1rJn trszt.r

rcct1:1s los vrtices dol tril.ngulo y q_u forr.l.d.n ,ngulos de 120

( Figc lo l )- Si el trfogulo r<Hmlta nte d$ unir con rectns los

clientes ti<ne un ingulo oayor que 120 , la ubici6n do 1 depsi-

o deber6 nr o]. vrtice q_:Jc tiene ste it.igulo ( '.Fig., lc:-2 ) ..

En ol caso do cuatro oli<mtes, el punto quo proporciol'lll lu mnina

suma de las distancias rE:idittleo os la 1ntorsocoin do ls.s diagone-

les del cdriltero for.1A1do como se nmostre en l figure. { lo3) y

si JD distribuci6n do los clientes no p:ir;:tlto la formecin do un

cu'ldril.storo convexo, 1,.) posici6n. optima del dr:.rptsito coincide con

el oliente interno ( punto 2 do }q Fig 10 4 ),

~
'
"~sl ' l,
...1/'
.Jit
;
,,,"),to

,
,. / Fi~ "k~
.,
4
f i.~c l cS

evidoncia de estos resulte.des se b.,sa G3n simples reltloiones ge:!.

.mtrica.so Si en los ]'ig(\ 1.,3 y 4 ae t QJI.. cut\lquier ubicin di-

.foronto a lb mostroda :por.a. al depsito puede fmostr.:irss gecae-tri

C1S1'lente que 16 distancia tote l da asta nuevC:\ ub ics cin es f.ltlyor

quo la sur;, do w distancias most:rades co:no ejemplo .-

Qbvia.mi:mte; p.:.rc1 probler:1,. con un r;rn nil:;ro da clionton con dG-

n:ndf:ls d1forcntos, lt.\ ooluci6n os mucho r.is conplejo. y es naces

rio recurri-c otros mtodoo"

]!oto n6tod.o w ha USf.ldCi por algn tieinpo; su eplic<lcin os

muy simple :pueo conc ide e 1 centro d8 gravada d de los

cl1Emtoo caao ol lugpr donde debe estar ubicado el dop6si

to do d iotribuc i6ne

II!Jr, c ooordena&s del centro de gvedl:lc1 se encuentrln ,m':

X:-----
z_. X;
Z v.lj
( le )
-
y -
2.W;fr
--J-
1 'vJ
" .J

un at oao ltel'nr.tiYo que tnro.bin so ha us41do er.1plee el

acto al e.ro to da transpart e. Eote n'todo onsa._y) dit'aren -

tos por canta jeo de trwispo;;:1; o Q diversos lientes, sioudo

:Pera 6so coso los e oordo ne d,s dol de:p6ai to t

-
x1:; - -----L
l 11, V\I- X- y
-. ':f 'n1
y .... -------
"''1 Y1
1 n.; w
t. w'
donde n oo ol acoto por unidad do roso ( S cntifd )e
j
Esto mtodo US{;l :frceuontomcnto nj como un valor fijo df>bi,

do llt'incil)alment0 a la oim:pleza d0c ctlculro quo roqioro ll

vargin y Rogora han oor.iostrado que ol centro do g?.",""vodod

no mcos.:'trirunc,mte oo Jt soJuci6n 6Dtima de . funei6n ces-

too moG'troda en JA ecua cin { lo5 ) Si racG:lOZ la deriva

li.i j).:1rciill da lo ecueci6n ( 1.,5 ) reG:ect o u la coorderodll

dol dep6sito x1 iguol a coro ;rcnolviondo 63ta dori'vado

tondre:ics i
 6

.; zo,,:i v.1:r x, /d; ( lo? )

y"]_
. 'i:--;;,J /-
dond0 x{ os el v.:.lor hP jorcdo pti.r<"i. lr,s coordenr:1s del do

:p6s ito ve .rg in y Ror5ers 1:.uestra n CJ!.t '3 cua ndo los p9D os re -

Q.ucridos pOl" tod los c.liontr.z 0n ig.ualcs ( '\V! ) la

ocu.;;:: ci6n ( 47 ) pd:; s:l.r,.-:plif.ic...rso i

xr = L MjXj
do';)~{? Ji

M j -::.
b 1t: Cf :
dK )f { ff
siendo d ll:l distancia dol do316si to a 1 cliente k ( k 2.,3
k
... ,n ) y //dk e 1 reducto do los d
k
Si cons idaraooc ahor!I g.oo

2.. M =: 1 ( lc,8 )

ontoncoo X oG ol promedio pondor.-:do do todDa 1:s coordo -

J'! 2. j

nadas X o Tc:mbin p.1ro el c.1100 espociel que

1 pal"l'l todo j
M :: ;-;- ( lo9 )
j

ontoncoo ( 1(' 10 )

Existe um diforonci entro la ubiCl ci5n 6ptin del dor,6 -

aito y lA roopuostl IJUD rooul t dol mtoa.o del contra do

e:invedudo Itl d<nost10 ci6n do ~o~ di1'0ronci~1 oo aprociu en,

el oiguient e ej$m,plo ;

conaicl.aramos que dos clientes p y p tienen dei."tlndf.:s w y

2 3 2
w ros_poctivniento y Ja cl:ito.11cie entr clloG es D ( F.i.Go
3
L,5 )

Fi ~o ~5
 7

si loc..,lizanos el oo:psi to e ure di stancis X medida a _pol'-

tir de p el m0:1ento del sistar.1e con resrecto al depai...

2
to os :

H-=-W:f ... w (D-X)

3
6: H = (W - W,z)X <'i" W,JJ ( loll)
2
DH'crencianlo con roo-pecto a X:

df!_:. (W - 1,7 )
) X. 2 3
Si cisumir.1os que w > w3; entonces, X debe ser lo mls rieque-
2
o :poaiblc :ier r:iinir..za.r u. 6 sec. X-.: o, por lo cpc sl do-

, "
si w
2
<w3 ,
el deposito 110cb:1a cstfor onp y si r -:w ,
3 2 3
clquior punto ent\e mbos cllenteD &r!<i el mismo reiml,..

tedoo

caloulJ:lndo el centro de gravec1.ad del sisterM, ste serie :

aqu!, las medidbs X son hochs d0ade p ::::: Oo y esim.ismo x

2 2
El ooiwnt o
l resultl3 de reemplazvr X por Xi de la ecua -
ci6n ( L,ll )o

li- -:; (Vl - w ) !~ -

X 2 3 (Wz ~ W3)
- 2W2W;/) ( lo12 )
Wz -t- W3

para mostrar quo ol cntro de VfJ ded. no nocesarimente

es le mejor ubicac:t on :pc1rs e 1 dep6si to loo siguientes

tres casos son examimdQs para clcult.ir ()n ecd6 uno al o -

rror involuc1"6 doo

O.ASO l .i W > W
2
cano se ha expresado. la i\.mci6n de crntos se minimiza

cu.r.i.ndo al dep6sito se en::uentro 0n p y el mnto del aia

2
 8

tem: s

( lol3 )

c.:cu.hmo 1" :rel.Dci6n entr-e el ucn:nto de inerci"' IDl sis

sito osw on P
2

1
;,:.___..?__ ( lol4 )
W2 _.' W-;)

v-.. lor que oQyor gs l f;

e.ASO 2 ; VT ::. w
2 3
ceo
n Ge dijo onteriOI'I!Snte, euelgp.ier punto entre p y P,,.
2 ()
ninirze la funcin costoso Dividiendo (lo.11.) entN {lc:,1)

H ..- 2IT
.. ~Jfl-~- 2 :.1
Hl W2 + V/3

Entonces, cuando w2::. w3, el cGntro clo g_row<};;d carres:pon

do al m!nimo valar de lo funci 6n objotivo"

CASO 3 \\ < rt
3
En fornI1 sir.lilr l ceso 1, e 1 re sult-.:ido obtenido es

-.: - --- .......~..:/

p:n:; ilustrar el errar involucredo en la seleccin del cen

tro do .$levedad ect:o ubic.<.icin dol dep6sito taneimos l .si

guiente ejooiplo : 1'1 ::.4 y 'fl,,_-= 2. Rcm_p.1DZ6..odo cfotos volares

2 1)

on lo ecuaci6n ( 1.14) obtenemos : H / H ::: s/ 6; por tanto,

1
X1
oi se elige ea:no ubicacin del cap6sito el ent:ro de grev
 9

l ..2a2 .ciGIA_}iEC.u WICJ, o-

El :pt' oblam.:. do ubic..ci6n del clo.?fui to t.:rr.1bi6n. m sido l:'C -

en lit ub1cc:.!ci6n qu-'.) corrospo.ur.<.G ~ los clionto:Je SO ps.ein.

\Ul;l :pites ,;roo nostionen _pcson pr0porcione.los n lb.s d::?i:'J:n-

des do loa clicntoi:; y on el otro oxtremo oo unon t.i ura. :ie-

quea ergolle ., 51 la argolla se lle"lfa a un ledo y oo sual-

ta, los poaoo ( CT)J.0 rGrcasentan s dendos de los clien-

tes ') heoon que l argolla aa estbilice en al :punto dando

la crors!a potenci 1 dol Gist011Y", seA m!nir.:lFl y pOJ:> la anl.2,_

ga considorodl:i 1 iste punto reprt,HJenta la J.)OOici6n en quo

los coato::; do tran.Cl)orto minimize.:n. f'unci6n objetivo, 6

sac:, $1gnificar ubicnci6n clsl do:i;,ooito del sistemo e Es

te m6todo ea S:inP.lC y prlctieo y su rincipcl viantaje { co

mo dijo S en cu on:foulo ) os que 11J.a amlogf ticno un

L':lx1cto viottz.1 que perrtc a. le gei1te ver y entender lo

que o.::it sucediendo; os to oo u i.n;-plc );)aJ:'t, 3,)tisfacer loo

" "
pro:poGi tos del r;,ode le a.e di::rtl' J.buci en. con wdioc QUO le.
.
 lO

r,o las idens q_ue tengn n 6 qua -po<h.!n ocurr rsele.o y rrl.s
,;
ilc.port?nta, qua eo un excelente rnetodo pr.ra des:pertcir ol

inteJ.:tfo da le gent{)rt a

El d:itodc tiene tambin sus desvontl\j.r,.:; r entre l-;a m1:1s

aeiltant8a podemos citar :

- debido a l!l fricci6n entre lrls pit..:':tJ3 y los egujros

l)OSici6n fiool de l .)rgollft puede cer indet8I"minid.

c1rnndo l nttr.iero de clisntes se!'l del'JJ siado e,.r21nds c

ligro de '-UbOl)tim\lid..)c 1'lnedc se:r ir..cy pt'onuncit:doo

- con.o lo indicaron Bt:,.rsh.J. y ot.l:oa, lo mlogfo no dis -

tin;-u.:-: entre >U.;blos :pnfoan I Qt e so;_., no considero. \

j
ds J..1 acut>c16n (J.o2) 1de,m6$-, si Ji.is relJ'l,ciones ds cmtre

f!f, a(;pondan sJ,o de J ubicacin ce los. clientes ceno se e

fJtipara. X. en le ecu6oi5n (1.5), los pesos uselt'ios puo

J
f..c:n a.iirntarso a ro:pressntar o w y no Wf
j j
el n6todo no ov11a 113 funci6u costos y esto l:i.zs re ...

presento cu IJaYor desvontja

lo2o3 MEI'ODO lUtERICO 11 N.:!LtTICO-

El m0todo nut:lbrico Pnal!Uco es el eQ,uivale:nte r.1:,temt1co

de la ant1log!e meclnicc10 i,dems, sta mltodo l)Uede usBrse

con fun-ciones costos y parmit incorport,r difert-:ntes par'ce

tajes de trn.s_part e p.a:r8 cli0ntes individu<'lles en a 1 caso

(Jlto fuer1:1. necesarioc

Tanando pm convenifincic, lEt ecu,,:,ci6n (1. ;; 5) :

 ll

ri vdas n . cero

off ..-.
y -:::2_O< .W ., (Y - Y >! d O
d>1 J .J 1 j j

Esta::, ecu?.ciones pueden resolverse con respecto a Xi e Y

1
obteniendo s oluc icneG qte pueden estiro.ar la probvb le ubica

ci.6n del dep.Si to Estoo soluaiolles son:

( lcl6 )

ff A(
usaruo loe valo:i.~s ne j o,."E.lcbo I:i_ e Y , l ac di,~t~n; iH3 dj
1
a

da clienta son :recolculd.:is y el mtodo contin hl!l[;ta

que no s ne jo(;o puedan h'l cers eo

1&2o3ol Oo-

El algoritmo colJJ,ista de lo:J ei.guieutao pso'.:

1) suponer uw ubict1c i6n inicie 1 pf..rc. el dep6sito

2) oalcluar los <.o oto;:; e.e o.cuerdo a le ect-ec16n

(lo5).,
3)+ l)3terr.,iMr l.,:; f'nnc1n costeo usenao ltio cooTde

d.ao mjorqd(lo da lb locolicin del dep6ai-

too Si p1<Xluce beneficio respecto el ooto

nnteriar, ae va al ps,so 4; sino concluye el

prob1-aner..

4) con 1.-:is ecU'lc ione::i { lc;,15 ) y ( l o l6 ) , deteJ..._

miMr 1', ru.ev'1 po;:;ib)g UbiCin del clepOOi to

 12

1 tv'7. P.!liGRlJi ;.f 1!N GR1NQEf3 .BIOW:!PS DEL OGR:J:it FOO'JR.',N .liJ?IICi,IDO AMBOS
1

tfEl'ODOSo-

.lirvi>,,1n,i-' rh.7.'os
---.._ X; Y, ?, A l.. :.

---

l -7m;nir~
~~~~~~- --~~~

lt- coor.(~n,.:1d',.c1r
-f:..-le! "").>0~1 ..t o~ ,tJ(!o

\ J r1,; ,,ry 4 /;\" ,:t<: .
I Y~CIO,),r;/

'---:--
1-
'
_,. . l . "
," \
' ~;-t:>? 1
\. /
' ' - ,.,.,.,,
 13

lo4 E9,m;y~IE.l:lf 2IAS DE Vl.RIJIBLES DZL PRWRt,!,;!. CON VARI iiB~ DE Lli F(!L

r.1JIIIUIO lib.....,.

Vtriflble e.o }.c. : vs,r:;:,ble "el ne.ccripcion

]'o llmll-':c i 611
. . -
p!'Cgt'l'.!_'11'.l
---
R FUnci6_ objetivo
--------
oosro
--4-1--- 1

1
i tIF (I} \ co::.to por unidc'.. de peso
por tt:1.id..:-.d a. d.1atanci <1
cle:::d.o el dop6:::.it o tll el io
--
1
te j
Xi 1 i1rr .:lbcist'. del. c.lie.ll; o i

Y(I) coor(-:.onl':' a.a. e.el cl:nto

Y1

P(l} denc:e del cliente i

wi

D(I) dictnncie rt:ic.hl aocae el

di
ar :Lgon et.l client0 i
-
1 XX 11 Obcioo da le rruevo pocicit'l.

1
Xo
dol 6.ep6si to
.
1

l
1

yo 1 17Y coor<lenoc 20 l,1 nuov0 po

1
\ cici<Sn c,c C.-epooito
L--------...._---------------------
1.5 -----
IDENTIFIC!CION DE Vl,RliiB!ES DEL .PRCX:lli.AMAc-

Z V<'lri t:b lo p.3r~ i- ."

n})l ao l.O;n

lVE(I} vect;ar blanc ex;

IVJro { I) vctor llano con r.-1ya e ( - ) :p,ara imp:re::;16n

COS varieblo qoo J;>Cn'"lito la cor:rpu1.ci6n d0 la :f."t.J.j...

ci6n objetivo p:ro etel'ninor si bay 6 no inojo

on 1.l'l 3 oluci6.Ilc

llar la solucin
 sw
swx
SWY {
scn-:-:ix <\l'ilfl'i'3bleo (luo peniton c,;Jnr..o:mr di:tos do
stf'.iY l Btml.e! to:ri & s
Str.iiiD)
COS.l

- ta pr:il:Pra rjet., do datos inf:ica el 11nero de puntos

i !READ(T,l) N

,.
J.l FOR:1IAT (I3}

-1.A sogundn, tercera, CU:}rta y quinta tsirjets, llOV<)ll

ollrote y cOiiclanteo ele poso por E}iGt81'1.cia c. cc1(1

Clit>n.t o.

IIREaD (T, 2) (X( I), L--1, ~

ll~D(Tt2) (Y(I) ,~1,NJ'.
j~FAD(T ,2} (.i.tF(I)' ,ll, N)
2FOBAJ.iT(l6F5.2} .
! FJ..D (T,4) (P(I},I~ l, N).
4\ FO}Jt.AT (l6F5 ..0)
1

Ejo~plo:

X, Y,-Ar..F : rJ5fot2!0f_J fITo15f5f .,ot211 ;tlt:

p : r]it5!0fot r 6)ofo, s 1 fst5t,rT:F::;TfJ /r1c

lo2 !'lJBLICACIOH DE REPORTESo- LOO reportes que publ icD 0sto

progr,r.m , son;

n) 1Jn, tnolo con los datos del probl <na

---eli~nte
l"~o

l 0.20 5060
 J.5

Il

;--1-:
i

1 2o78 Oca 130 lo

--3-,.._..,-i--4-.....030......__,._,.,- o,-:5__,._j

_.._ ____________...:.----
.._.__.._4__-+---+---+-.,
7olO 7o90
1

1 !
l
!
4o !
10

b) IPs coor<,::mdOs del r.epaito hD.llsdas _por el r.itodo

d.el centro de grvede

LA UBICJ.CION DEL DEPOSUD POR EL MET(l)()

l>EL CENI'RO DE GB.4VED.i.D ES&

X ::: 5060
y ... 4,51

e) I.lla coordoHl&s del c1ep6sito holleiaas par el 1-oorodo

nunSri CO Ul$ll J.!ii

~j<J?W-0
LA UBIClJCION DEL DEFOOITO POR EL MffiDO
mm:mrco AN.ALlT 1cr m,

d) El oosto totfll a.e entregD. ( valor do t, func16n obj!.

tivo) y el trona-ro c1e itar,.:ciones reelizodao tf'.ro llJ_

ger a osto vnlor.,

EL OCETO DE El ES 100p35
EL NUMERO DE ITFnllCIONES HA SIIX> 15

lo7 SUBM-

ta ruii cr:1 subrut imi que t ie re esto prcgron,, s o .D.o-n DIST',1'! que

os usac1a p,n.,a C1Jlcul.ar los coorderodaD c:lol f.epei 1o por ol nt.2,

o cal centro ce gr-,:1.vedl:.cl, siendo su 1it1S!'J.n do tl.u.J :. :

 J.6

(:ueOuT:;-;,.,,,..,"' (>.1, ?,x, Y )(;1i:1jYHG

,_ ,

,k'{ 5Vtft't'(-t ?fJ:) '{(J:l{

J w11,w= sfc.?;,all
-
)
!..)
[)(M :: 5UH6)C 1,JfftS.P
-

JYHEP :SIIH6 Y f,vP'Q,P }

--
',....____.,,,
/

El proe,Tana Fortran (vorsi5n W6t:t'or-) y V6rios probJ.(uls resueitoa

con ste pr cgror:n oe a1cuentn en los eno2,eo c1o est1 ts::.so

 l?

I'lUI.O ll

fil!RtSION DE U UTS'R..\'lU- PROOR.MhCION DE VEHICOLCS

2,1 INr'ROIXJ'CCIOl),1- El probla:n.1 c'l.e progran::tci6n de ,ohculos, fuo -

origin'3lnente i)nteaa.o par nantsig y Raoser y se :puede fcrnu -

lar cc..:io s:igue; un grupo de e liellt eG, co1.$ u110 con su ubic.sci6n

conocidB y los e.xigoncitls de ciertos (requari:-jmtoo) pro:luctos,

debsn se:r sun!n1stradon &ssde un terniul'il D h"!p:W por 1::adio c10 ,a -

hcul.os do capocic1Dc. ccnocifu:i. El proole-1e ea el d diser

iaa rutea dsnds este punto, aujetas Q loo ai.gui.Gntec; rsstriccio-

A) S,e debe satisfacer los requarinientos do t ocbs los cllenteGo

B} tio ae debe viol!lr lo ce:, cidt,c. de los veh!culoo, eG cec:tr, 1D

oar,-a tot.::i 1 asigr);}de u cae.o U...'10, .no '.ebe &ceder ou copac1diXl

roprsoanta sl peno, vol'1rlen, etoo ?:isponible 011 el vab.culo II

El t iaapo total (alt nui-tivlsnente :la c1 iJ;tanci11) debe clculi:E_

se ;pow Mdci vehculo o i'in de que c<npleta su ruta y no debe

oxcec\or ol!n Vlrlar prcdeterni1uico; esto eG uDE\ e owlici6n de

controto, nomolnenteo

l>) H:Y un ti.enpo a tenprano y rjs 1Mrd!o dentro e.el cufll un

cliente acel)ta un smini.stro y no se puede viol ,ro

El objetivo de unti soluci6n se puer,c ootQblecer en tinon gen

ralas ceno oquel ele nini.'":lizr>r el cooto tot;,l c'te :Ws entregas, an

docir, lD 3\101 de lo s costos aooci..;dos con el to:-1a_fi@ de lo. flotF.,

y el costo c1e lr:10 rutfls de entreg,J. se puede fl.s! fat'rmler vi:doo

problenas e.a ocie.e.os o

( 1) Si Jz, 1'lot6 consiste te un vah!culo sinple que tiem un1

capeoiclE.ld auficienternta gr0 nc1e (\e te nero que se pu

 18

den ignor 1&1'3 restricciones y si an adicin se 1gn0l."6n

los restricciones ( e) y ( d) emcu1fotrase la rut.i rLs corte

pare visitar e to<los los clienta" El _problerJEl sa reduce

al clr.sico n.oblene del ag011t o vi jero

(ii) si se ignoren las restricc:i.ones (e) y (a), e:n.cuntse el

nmero s pequeo de veh!culos qu<. se re cesitardno Este

prob.:i.er: del ter:JAo de :h:1 flott>. sa osej mucho &1 probl2_

r:ta a.e 11:l nochi:Ia.-,

(iii) J?<1,ro un lll.lr.JSro lado a.e -veh1culos con1)(ltible con lns res -

tricciones, clise<l1' l'1 rut de veh!culo dG tal n:lnti qe

1 d:Lstt:incia tol de s rut&s soo r:d.ni.mizadao Este ea el

pt"Oblena nol'rll ltiente conocidb cono al p:;i.oblrut as Trlna:po

tist.?.G y la royor!a de Lite.tui'(l que existe sobre o-

r.{:lci6u e.e veh!culoa, t ta d6 f/Stuc1i :r profundr:1<1.m:te ste

problena y as 1 qua nos dadirer.:iosa

(iv) si 1 ubicaciln ele todoo los clientes y sus axigencios oon

co.nocila s t digonoa p,3ra to'!oa lo s da s de le. 0!1&na y sul'

niendo que en lE, se:r.l.Qn 13U.Cesivlil se presente lo. :rniSl!S for-

na de 0.ar.i.anaa; encuentr.e el tl!Jr.1ao relstivo de le flotcl y

el tao ne la flota que debe ser elquilade fletada de

I:!odo que se tlihimi-ca l.os castos de entre.

LOS probler::es de plH1oor lea jorredas de entregt:1 son rmy

cor;mnas c Tol6 s las operaciones de en.tregs de p.ohtctos F.Jj

6 de loa clientes ca:uprenden stos pl'Oble-.1s !fil colee -

cin del correo de l1a casillas!:, de o:e.reciln a.e les sG_t

vicioa de &nnibus escoJ.a1.--eo, aon ej{t'.lploa fanilie1"ea a.e

,
entregs en .rewrsoj acl6rnas, a).e,unos problenas de pt'og:l:'8-

yaci6n de t bajo en r.quim s tienen ecta;:1ente l nisr.:a

estruetL:.r& ::.~tanltice y _puso.en ser er. ccnaecue.uc1A tl"fl t Q-

das ae la misr.:a fornao

 19

2o2 CI.ASI1Ic.ACION
.......... DEL PROBll1f
----_,,,, ------ .. - _____
Y DEF
,...,.. CION-
....... .... ......
El pi."O blema de enti"S ge pu.eae ser trctedo gtmarellra.ite col7lo uno

de detennirsci5n de ruta ru.t11s de um f'lot& ele veh!culoa par

que u funciCn Objetivo ( l."ecorrido totG1 1 costo tol, etc ,;, )

sEti OJ;>tir:1iZaM sujete 4 les restricciones rutos 6 camiones )

g:J.e J?resent e el sist em:lo

ta Fig c 20 1 muestra la clasificaci6n ganer&l del proble d r&-

1>9rto en tres distintos pl'.'oble.,:ias tipo i el proble &a rsperto

del te:rro.:i.nfi:l sim;ple, el problema. de reparto roulti,...tenninal y el

problE!ll.<'l generalizado de transportista El problena de re:pa!'to

d.Ell temnal siniJ)le puede , su vez ser clasificado en cuat ro ti-

poo de :probls , el problem del agente viajar-o, el J;)roblema

de tute. sim.:pla de re:perto 6 }1L'oblEl:lla da tran.spc:irtistea t el pro -

blo.l".la de flota hetarogenM y el l)l'oblema r..el l)<J.t'tsdor comun ce-

, ,
d.& probleJ.nS tipo descritv antorioroente se. define a continuacin.,

ffiOBIEifli DE Et-1Tllli"'OA j
-----...

o REP.ARI'O
G:ENE1Rt1 LIZADO j
TEre4l:l1
L-.- " 1 1.. DE TlaNSPOR j
__ -

GENTE POR--0-R-l
---!
L'iJERO
,\j I._,lf.ETEROGEN.Fli
.... _,,____.... ... .I COMUN J
1

. Y------- I

2t-2ol _.,.......
TERMINAL SIMPU:o-
____
Este oblana c onsiste en que algunos ttpoa de Sl.lt:linistros

son horn.e,-neoe y deben embarcarse a su,s cuentas cuyas d

nentles se asuraen conocides y los suministros s e entregan

en vah!culos de .reparto da caiscidad conocids o El probl&-

 20

L1! es detenninar :i. rut1 6 rutes desdo el ten:ni:11 simple

que n:J.n:imice el costo total 6 distll!ncia total sujeto a lts
restricciones del sistema.

Este, es el 1"s sir.J.ple probler:'l&\ de reparto y el

,r:i.J:rero en.s&y&do e n Inve stif,"&ci6n de Operaciones
:parij enc o!'ltrt,r ulllt soluci6n 6ptimae
El cllsico :probleIDQ deJ. gente viajer o es aquel

en qua un distribuidor de suminis tros sale de su

puesto be se, visita todos l os puntos destino
( do nde tiene que repertir al.111 p?"oducto ) so
ment:e ullQ VEtzi y retorl'J! a su puesto blseo El pr
bl<na consiste en determ.iner el oraen de lita vi-
sitas pera que io distancia total sea m!niml Si
u.ns restriccin adicional fuero que el distribu-
idor de a.tnnilstr os debe retorn&r a su base en -
tes de que t (t <n) ciuddes hayen ido visita -
das ( n es el nro toAl de puntos destino ) ,
el probl sufre wricones ue pueden ser trJ.
ttdes en sl aiguie11te problen tipo.,

2o2olob :fil}" JMfIE DEL PROBUI. DE :R!EAlrP..9.!.:.11!.@...

M TRitm...@TI?r....#..-
.t.ctualr.Jente, es um raotl1fic16n del clfsico pro -
blemft de 1 egente vi& jeroo En este pro'l;)leme, lA
solncifu consiste d.e un ciclo d.e rutas bech$.s por
un o 5 s c6nions de la misma 6 diferente c&J?C' -
cidld, que deben sltiatecer lis demandes ds un
mero var1$do de puntea diS'persos geogrefiotmente
El :prop6s1 to de ,sta scluci611 es cpt:unizar 1A fu

ci6n objetivo \ sea csr&J total, cistanci& totl,

et ce> ) su j ete cuc lq_ui0r :re str ice in que presan-

te el sistE!l'l8 0 I,6 ruta sL11ple originiar3.. puede ser

un vije simpl e 6 un nro e viajes cuelquie,

dependiendo de si Y restricciones de enlazar:iie!!

tos por l!li1itaci6n capeicidades de niiones o

Loa ejemplos de este tipo de :;robleI!l8s son nu.nErE_

sos: reparto de leche s tiendt1s minoristes, re1)6!_

to do @solioo a las earociones do servicio, re -

rto de diarios, ropsrto de paseado, ateo

:Muchas vs1iaciones de este oblame son posible1:1

de:pendiando de las oerocterfu tiooa ( cono iciones )

que pue tener (:Jl sistema, tttl cor,10, tianpo nu -

erto debido e p:>redes oblgadae, etc"

:en este CA so, los oar.iionos tien e11 c1iferentss ctie

cid.odas y ce:racte:r!sticas opecior11J.0s y hay un

n&nero ce oer.'liones de oaa. tipo a:provocbebloo

Ten&moo E; :puntos da:n.2nds ( 1\, ,. : .",P ) Y

n
q oentided de rceder:!t) s de:mandaoos ..,
1
El problel'll& consiate en programar 1,as d0Jll$ndas

ra ra SQ'r repartidas desde el terminsl. e cada I>UE.

to dem1lnda de modo que se rainimice el costo de

ti-e ns porte J se&n sat is feches todas las re str ic -

ciones del sistema. !Jl operoci6n se .;.suma que se

e:x:tie:nde P.l J.l'l. par!ooo de tieilI)?o tal qua Q repz:.

18
nt11 la dei:nda total de cada uno da loo puntos

)?al'.' este perorlo de tian.po o

 22

des dem!ndaa s a le <xtpacidnd as los 01nu.ion0s

se tal, que ss Mceaitlln muchos envos :p11r que

2o2o d Rm.T,iDOJLQQ.9-

En ,ste problel!W. ooy UlfJ 6 Lll1a restriciones de C!.

mionas coi. lmite de :ro de entrag&a que pue -

den ser ches en un vi!tjo siro-;J.s ll que, Uilil SE.

luc16n posible paro el probltJ@ debe especificar

algunoo vitijea paro <*da veh!culo desde el tenni-

ml oentr.al pe lfttiscer la denand.a o

npuntoa dendD { P,
Eicisten - ,P
QQ
n)
q cantiea d dE>rrSndada en ceda punto y se
1
,Sl.!I;'le conocida o

Los camiones d:Lsponibles pueden tener l&s mismaa

6 diferent&s a1p:1cicledos J;)ro JA aU!llil de las n,..

....
tideclas dQrrjl ndla..s de los n puntos, es rrls gNnde

que Ja capi)ciw d ae oualquior CJ:1r.1i5n de moa:i que

:r equieNm algunas vm jee pata satis fi:lce:.c .l,s

de11nnoo so Cada punto da.tian as visitado s610 ul:ll

vez-; sin eoba:rgo, no pueda apttracer was <1Ue en u...

na. rutao El objetivo nuavernente es, detanllir las

rutes tales que le tunciSn objetivo reeseutendo

costol:l a.istanci..as totales a.e opti.1'\l1za sujeta a

1-es restricciones de camiones y rut1s im:puestea

l)Ol' al sistans o

Eete probler:m puec.e considerarse oano una generalizc16n del

 Jll'Oblama de :rorto del l)Qt'i,idor cOlilll.o r.a diferencia es

que &.r.J.ON existan doo 6 .ru4s termin':iloa desde donde se as -

tisf fJCO Ja dn.da q

It\B oeraoter!aticas dei probma ( restricciones dG Ol.tlli,.2.

nes, rutas, demande ) oon las m1snits que las del partidor

conino .Ahore el llJ:'Oblt,ma consiste en da-ia:nnin11r Ja ruta q

con Mspecto ti ls tuncifu objetivo ( costos, rutas, 041mi .2_

z:es, atce} parJa EiuI>leer loe umi.zlbs {\:propdoa de modo.

de S!ltiaf&cer toda la dEl'Il&nda consilen.do J.,s restr1cc

nea inlpuestils :pat" el sistEIIfl,

2,2$3 PROB:tma GENERAJPiA.l!.Q. P.l.. .!_.-

Este :robleme es UJJa extnsin t nerel17.o16n del proble

ns d~ terminal. ~tiple. El irobl.&Inia ci:ln~iate oo ,_,

n tmi~ 1.1.

lt)sdonde <2d& uno tisna un nmu"O dado de (.ll.miow.a con<!.

l)!Cid&des conocidaao

Cada termiial es u.n receptor .lb vez que un deeolltdor

pera cea, uno a.e los crtroa te:i.inimlea, Bntoncea i loa term1

Illi les manoi0nedot.i 4iJqU ,son diferentes loa definidos pera

to:rroi.Jjl lea snplea y nilti:ples

El problema consiste en dt;t'itJrminr B rui.s de entrega,

tales que a diatancias tot&les reoorrtdGs Bean m!n.1nas

, ,
y el llUIOOro de oamionea u$doa tembian, p;,ra satiacer J.Q

oo:mo restricciones podemos tener J..e m1'x1.ma cUstinoi& que
:pUOde recorrer un cenun en um ro.t aaa.a; illmbi,n se
l:ilG que un bar(lUG :;u,:1rla sor t:r&n-spo:i:'-bado allo :por un c1 -

m16n de un solo iti&ja

1.R f'at"mula ci gn e.mpl$eda paM &s te 11L' obleIOlii .11uode na <!er ee

en pr-ocin lineal 0-l..

 24

QJ..?l..'fil!9-1!.
.- ------------.. --..---,---- ----------
li'01JAOIJ1CION
.....
MATEMTICA D.EL PROB.IJM.4
... DE PROG!Wt1ACION DE VEBICU:WS
S
( TBb N.>PORTITilS )

_,____
EL l'ROBIEMA
"""""' -"'--- --
DE TRHBPCRTISI'AS,,
.. ... En 1::: forme p:i:>asentad0 anteriomsnte

6 en una fO:r u.e. ,P.OCo modificada ht.i sido estudiada y fOll':IUlada como

l)rogrOJilacin 0-1 pi:,r :MlinsJr.i y Q.uandt y por a&rvin, Granda-11, Joh.n

y SI>ellman, pero los dos grupos de autores dan soluciones y fOJ.'mUJ.aci.2.

nes completamnte dife rentes0

El problema con.siderodo par BSlinsld y Q,uemdt 1ncJ.U3Te a6lo las restri.!

ciones del tipo (a) y {b) del tem {2ol) e

]Jllos definen una ect1v1dad 1 ( 1 :t 1.2. o-:-o m ) , cano una ruta _poten

oill sobre l.& que tiene qua operar un vehculo, siendo el ni1lmro to

tal de rutns simples poaibleso En.cunt;reae uoo matriz rl.e nfunoro

ij
detmnimndo si t i
no el cl ente j ast e n la actividad y dependiendo

de d d 1j -::.l ( en cuyo caso el cliente j est4 incluid o en ls activi -

dad i ) 6 dij o ( cuando no estl ) Si el costo de cede actividad se

conoce ( digamos c1 ) entonces su farmulbci6n se convierte en :

z = - xc
1 1
( 3ol )
(;. t

donde\"' 1, CUllndo la actividad ha sido e scogida y x :.O cuJ)ro.o no,

1
joto e:
.. { d ijx1:: 1 pare todo j 1,2.oa, n ( 3o2 )

I,a restr1cci6n (3c2) oxpress el hecho da que un cl.iont est<1 siendo su

ministrado por un veh!culoo Este formulaci6n tiene un mkero de limita

oiones l'e&leso En primer lugJI, el nmnero do rutas simples c tibles

en un probleraa puede ser un nilinero ruuy e;rendec si por ejemplo, el .:

ro irOl!l.Odio de clientes servidos por un veh{cu.lo e imple es el e-

ro dij veriabloo eera dsl orden de t

l'9prasentando to. s las 8gt>Upaciones p0eibles de..!! cliso.tes en_ 1,2,

eteo o. En segundo luger, el clculo de todt1s l.es rutfls posibles no ea

un J,1robl !'cil si se van e resolv-ar por enumaracin de toa.es las

oom:wsiciones pcsibles d.e rutas simples ctiblas pal.'6 un n.'lll9ro asa.o

de clientaso Si n es el nlxi.mo nimlm-o de clientes q.u :puede servil un

veh!oulo; en toncas I el n&nero de com:posiciones de rutas que se puoden

om.mrar a fin a.e celcu1or todas las rutes si.ut:ples posibles> estar'

dado par ,
..,, I

?, ( i)
un m.fme ro que _pueda ser rJUcho t:.-1m.or ( ye, que n! l- h ) ca eJ. r11M-ro
1

dado por :!a scuac16n (3 c :3)Q Siheubtlrgo, el oolculo del costo do w.a

eotivi.clad 1-equier la soluci6n de un paqumo problad de agente vis j,2

ro pera los clientes inc)u!dos

. 0n Ges ectividado

UI tomulacin e.e aarvin, G!'andall, john y sl.ln:llln, es 113 aiguiento,

\ ; clel'!t.lnd.a del cliente k

Q : cepacidad del veh!culo

c . costos 6 distancias de i s j
1j
o
yi : oentid8d barcnda ele i F.I j deetimda pal'a k ( el subl.ndico)....
"
jk
indica el alrzacn. )

uno tiene- entonceo las siguientc;s :restricciones

;._ ijk = jrk

<(' y ,v w:. todc J'. !:: J. .J. k ,, ( 3... 4 )
, , ...

donde E. as un cliente .iilrbitre:rio 0

lft .restricci6n (3o4) e:.q;iresa el rocho de qu.s no btly acumulfJcin de as-

 26

tertal en l destin:ldo pal'Q cualquier otro cliente ko Tambifu

:. k :pere todo k 3o5 )

f-YT
<:::'-
'- 2- Yk
1
= L
K.
qk { 30 6 )

!JlS restricciones (3.,5) y (306) dicen resptlctimente que lo que se na

aournUlado en el :pun.to ,!s. es igual a 1A d.em3 no.a :le .!. y lo que le dol a];

mec,n es ig1ml a 1 den13 ndm total,,

sea unei V81:'ia1ble x

1
f:::; 1 6 o de;penaiendo cte, si un vehcUlo visita al

clfonta .J. desie _! 6 noo Entonces :

.,(
x1j -:: Z y"
x:jr -; 1
a1"f.l todo j { 3o7 )

es d.ocir, sol611enta un vehculo ont:re 6 sale de _;t ; y

( 508 )

es decir, la oopecidad de los veh.culos no debe ser violcda ()

El Objetivo oa entonces minimizer el costo () la. disWnci1.1 tot&l viaj9...

da, 5 sea i

llfi.nim1za r R
_
Z, r o ,x
1 J ij

gte. fociSn x-equi&re n{n--l) y n.{1rl.) variables o-l, asi como

2n ..- l restricciones siendo e ato l1l turahnante im.tir6tico ra un :Pl,"obl!

que tenga a6lo 12 clientes 6 algo tsrecido o

IftB div6l'S:t t1 torm.ulac1ones pora resolver- el problema del trnsportis

ta s muestro a corttinuaci6n.o

3ol ffl..QI.9lt.J?J.Q!o-

r,. fonnulaci6n de pl'.'O.mci6n din.4nca dada p:ira l problemo del

agente viajero, se puros genfft'EJ liZB.r f'Sc ilm.ente ;t :re aplicars<l al

problano de TraneJ.)ortist.ss corao sigue : sea O (S) el costo d-a lt;

 27

, t1ro.a
ru op . "
a t!'svs de :os ct mt ss del. e cnjunto 8 Ci ue e.mpieze

y finali<;a (3).1 el towinalc Si S desig:a.1:; a todos los clientes que

se van a e te roer t snt oxc es lo q_ue se requiere es e 1 rn!n:uno de la

carttidad

( 3,.,10 )

sobre to::ls las prticiones fctil:>les S.(J'l,2, .. o..-nP) del con -

J
junto se)
sea i, (t_,1) ig,t>.el al rosto m!4imo que se logra usando k ve -

h.!culo.s y suministnando a Ul'.l subconjunto u del conjuntos da

clientes,.

1 (U)=. r/
1<
C::0)
1111

1 '"'--
{j_
- (/. 1
)i
(U u'*)+ C, (U 'J

)
l ( 3.ll)

IJi ecuocin ( 3 o 11) ,Plantee .siJQplem,4tnte gi.ie la me jOt' fo!!!Yi d

sumiuist.r e un sub-conjunto U da l.os clie.nt es u8a1'li o k velcu-

los, es le m(;s ba:NlUI de bs roe jore s f 6nnulas de SJIDllinist:rer a

un sub-conjunto m pequE:ijo U-U w- de c1ien tes con k-1 veh!culos y

surninlstrando .a los :re,stante u*cJ.enva m n otro vehculo; lo

ms ba:roto t'J.U sig;n.i.f'ica lo que coosta meinos de tcil&a :Ws foJ.tc-

mas posibles en cr.1e se pue::len eacoger los u *"clientea pare formar

lo:1 r\.t\;8 e:x:tre 0

r.e lista c1e sub-con.junto 1)&-<t1 optim.iz..aru*enle ecU5cin ( 5,,11)

 28

se ubicado en l p61rtici6n 6:pti.zl'e de s1, s200 .,.,,.s (es o.ecir de

:P
los clientes o ele JJls ruhs l 2u:<P) Q'Ul'3 rni.r.d.miza h de la ecua-

una cctnpare.ci6n de la so luci6n de .i. pr rci5n dtukiica con el

todo 0-1 pr Q:s:rmlde pQl'.' Bt,alin.ski y Q;uan.dt, nos muestl"a gr ndes

simili tudesc En efE!cto robos mtocbs requiel'9n el c&lculo da to-

dta lA.s ruU.s factibles y ev,ul51' s.i s costos"

El.loe di'ieren so.1MJ.entEl en el m$todo de determinar g.u valorea e..2,

tartfn en. le so luc i6n f1 n.slo ne esta modo, las objecci 011:3s practi

daa presentadas con respeeto & lGl f<rmuJ.e.oi6n de Belinski y

QUlndt son igua,Jm,,,...nte a:plie&blea l.t fonnulaci6n de pl'ogrcnwci6n

dinomics
;
rs. este it d:>lc l't;.

---- -
DE OOWG!ON DEL PROBIEMA... DEL AG]:llr
BASADO EN !DS 'MEI'IDOS -...
3o2 .AIGORl'IMO ....... ----
-
.

TE .
n clian:tes y el terminal de un problan. de pro
.._... VJA.TERO..-. Si los .....

gra:m&oion de veh!culos se conside cO(no un. :problema del .tgerte

viajero con ( n+l ) loe&lidbdes. la solucin es una rute que :psS8

t tras de to.ios loo clientes yeltenninel (visitando e ceda

clianta solBrnen te una 'VZ)o En el problmn del transportista, si

1aa rut,1s indi vidu&les de loa vehculos se combil'.l.(ln en une ntta

simple, esta ruta visiteN el terminal tantas veces cano rUU!a ha ..

ybe El pro b.lama del tren.aportte, on con..,ecuencia, se put!de fol.'-

mulr cano un problema dela ge Ite vi&jero eliminando el terminal -

real y reemplazln.dolo por termi.n.ces ertific ieles, todos ubic -

dos an la. rnisma l)Oa-ici6n, donde n es el nm:'o a.e vehculos en lo

flota e>
El-viji,r de un termin.al. llrtifici.&l a otro, est prdtibido, ponien -
do laist1:'l:PCi en.tre ellos igull1 1#.i:.lit:>, cmo se 11JUe;tt'e an

la matri.Z de Ceto " la 1':i.@ri\ ( 3,,1) y as btll3ca entM1ce ahora

la ooluci6n a est!l mtriz de co to, sujeto a las :restri:!cioties de

capacidaf. de lo.s ah!culbs <1

El nmero ,:le terminales 81."tif'iciales E. aiJ igu.l 1 rurr.s:ro de veh!c!

los mpleaoos en la soluc:i6n f ir/ -y e puad.e escer e va:dns

fonna1:: ., En- m;io:quiax- taso, n ti9ne su lmite in;llHioI' dete:i:min.ado

..,,.
pm: la cl:"pac id~d de vehicUlo Q a ~bel"
ll
N~ _ 9t/t;
( ,. 1
( 3ol.Z)

dome qi os la .exnallda del cli6nte .!. y Q ss 1m. caci-&d del 11e -

hCuloe

El problana e puBdei resol-vai4 ahora pa1a Virlr.ios ,,alo:res de y so

oacoge :U mejor soluc1n.:. UsU11lmentc no Be raqu.iere mis da N va

lar-es )?ii:ta 1.:;i aolu.ci6n fn&.1 enq;ie?.:.eno._o r,crr al ifa.lor m,e. bajo J?OSl

ble dete:nninado J?O:' la ecuac!n ( 3ol2 ) y auwntlndolo 1 ceda vez

' #<:-i.nF dI'

1odo; /cf ' c/.,1<;?! ; o:..,J
/,,t11e,1r>
"
"
di' fj,} f't.}/'
r j'v le J
'
-.:> 1
~~--~....L.--~------~------~~
 3 ()

sea e 22 to11o la ea:pacid;ld de CMliones {e:xi ste un numero

,
infinito de istos ., )

1:fl mtriz de distancias y las demandas se mi.wstran a cor.rti -

nuaciCn., No existe ninguna restriccin adicionc

I _ 1/- 7
-
ql. to,m.J>1d
1
-c,i1 /5
,' '
f /0 I:!:, / /{::,
IS c,,Q - 1,, )4 20 11' .2. 1 l &(1.) 10

":/_IJ,; /2.
1

13 /1 .20 lff Q(3).;

IJ /'! 13 o,CI t/<J, IS /1

-Q, (<1) .:

J,.1 .20 1/ /tJ ,,_/ /.2 \.2 (($).:

//,, / .20 IS 12 a,,O (.[-ti' &2{'11:. 7
9
1
? g,1 -15 /1 12 lo o<:>
6.<{'7 ); q
- ~

Solucl6n....,

Lo primen.-o gi e tsner11os que hacer es reduch lll IJStriZ de

distancias para lo a:m.al, buscamos el mencr ele.lilenio de ca-

da fila { aif1Ulpra 'y m.. ndo sea mayor que cero), (l!..10 debe ser

restsdo de los amils elementos de lt'I misma fila pera conse -

guir que :por lo nenas exista un cero :por fll& o !llego de .r&-

ducid.as les filas, hacemos lo mismo con lAS olumnes

I .2 3 . ...2- '
2

(;o
? 5 o ? J,,
,.
o 1 ? 12
1
<=>O J>
3 2 e.O ,3 / /CJ 5 /O

<.
3 q 3 -e> o I-;- 1 le

J - .t. Jf tJ R ,.:>O /O o z
~
'.
b
.
}{ /O s- .. '
l 2.
<?O o ;

? ' 7 '1 lt' 1.3 qj o g :>Oi

<
.sr
 31

- ~ ~ r,
----__......
1 11 "
1 _.o
2 o ..
_,.
. 3 o 2

' ;
? 2 e:-
o- o
.

--

_
J <>" I / 5
el o 1
2
3 -a
1

3 .2
o-
~

,__r; /6 q b 5"--=--- '

/CJ .3 z ..o o
z
b i
? 7 ti l
13 7 0 3 3 '

une vez que tan.anos le llfltriz reducida, elegimo$ U! oeld&

qua tenga el mayor recMzoo S9 llama recba:2to crl valor reeu,!

tante de toma cUli.\lqui0r oeld coh ve lor caro; buscar los

menoroo valores de la :f'il.8 y columna que contienen el cero

y s\mler t oa valores ( en el ejE111plo los rech,E\zos estn c.9.

locadas en la parte superior derech:1 de ceda celda .)o

El ms::ror rechazo as 5 correspondiente &1 en:J.ace (5,?) qua

rigina la ruta P1 - p5 - P7 - P con une ct1pac1aed de 15

1
tono ,Anulamos la ti.la 5 y lG columna '? y m cemos lil calda

(7,5) igual (1 infinito j}l.1l evitar formar a!..@'ln n1oop11

'
o 3'
!
-

'[
1 c:P -"51,2 3
o o
- --
2 3 00 ?2
o o .,.::) / / __,
.;:-

o
-
'"' o
.;J 2 3 O""?

l 6 G JO 3 2 -
2

., '

/& 1 13 ? ,;;;,D.
3 3

R: e;.
 32

cada vez que se borran tu.a y colwn dol m;ayor reclwz-o, se

tiene que reducir la IllEltriZ restante si es que se pueda; si

no, se continua buscando los rechazos pera d.etermir el

o.
'
.,
:::,O
z 3 6 ]
2. -
1

o,z
1
2,
o o<:) f zI1
--
3 o o oU I
3 .:..
I 51
o z
3 .2 ::z
......
.-1
o o
..<'.:)

(,, 4 4 f I o' oO

q o0 o .
'
'"'
-

'r l 4 /e)
i /:, l

El nayor rechazo do esta m,1 tr:LZ es 4 correspondiente 1:11 on-

lace (7 ;6), siendo ahor la ruta P - P ... P - P - P con

1 5 7 5 1
ure oaacidad de 22 "tono o Co.no no puedo enviaraa n&da nas

on aste mion al haberse satisfecho su ca i:ecidad., so ha E:

con.trado 1a pr:l.mera ru.ta c,

cuando ae satiateca la capi3cid.ad del camin en estudio 6 les

demandes restentea no :par:miten e.er ningunfl otra demanda

en la ruta generada: se anulan les filas y coluro.nes de loe

puntos que conto:anan la ruta y con los puntea restantes se

e:r.'lm ot:re mat1

..iz tomando en ,sta las di atanoiaa de la ll1El -

triz original y so resuelve como si se tta:ra de un nuevo

p:roblewto

proce:19.Uos con la mntriZ restan.te a reducir files y columnas

teniendo en cuenti::i quo los recht-e.>s que aa Gl:i.gen, deben

ser de enlaces que no estn uni.dos al or!ge Por este moti

vo ea que tomamoa el rechaZo 1 del enl.ece ( 2 - 4) 0

 ' .z 'a (.{

- 1ci 10
15
------
/2. 14 (>O
1
'7 /Q

3 !O 1z l / .J

4 /3 1 /4
---------,...----
I J
,;,,O 13

J 2 3 q

trt
<. 3
t

5l o 3
c-.;O
-
3
-- o -
2 (?<:;)

3 o 2 -- -
c:,l:.) 3 3
1
0 I ""' /~
() / o e<) </ 0 1o' , 01...0.
1
1 ....._-+-~-------,
I < :- (./~ 1

En el caso que hi':lyan vElrio s rechazo s igul:)lea ( los raayores)

p.xede seguirse V'9rios crite:t'ios para romper el emt.e; uno

de ellos es el de tomar el primer enlace que ancontromos

comenzando por las filas q

ta ruta for:meda al co11side.rar el enJ.Ace (24) es , Pl - p
2
- P ... P con u.na c1p;cidad de 18 ton.ce Puest.o que el hnto
4 1
quo fclta sor asigne:do {P ) tiene una dnas de 12 to11 cpe
3
I? " ..
de f.lgregca"sa e la ruta sobrepasarla la oopociaaa. del ca:mion (,

IP segunda rutf.J. queda con:fo:ma como se preso entes <> .A

"
- .
Ion.do los puntos. de esta ruta, queda solo el enJ.aca (l,3) que

generan la tercera ruta P - p3- l? con una ce P'.'l c.idad de 12

1 1
ton.,

'
I

3ih?!t
f::,
-
j / l /a
lo I

3
-:rc,o
oLJ
I _.

-..!
 34

El l,"eE!lmen da rut,1s y cargas, se llllestr\ e continuc ci6n

--- -- -,----
I e "'::!.,1
,_....-...- ..
r;.)
Ro1 fI /,;J .... ,-: 1.-,ne,' Tl
IJ

0, -
t 2-.:-?, - 11. - -
,;'
3G. :z

2 - 7.., _
?. ;> lf
? - - -- --- - - - -4
)
I

,-, f1 2() I <.

' 1

, - ?,!; -
J
,-.., - - - + - --
............. _
j J)i 5fue/ 7:,t I: q
,_ 1

3e3 !f'lFUE DE JY,MIFICACION Y ACCJ.r.AC J,91! (BRANOH ANp B

Un o.lgoriAli.O de ramlfiClci6n y aootac16n para le aoluni6n del pt,:;>-

bla:ne del gente vi aj aro, fue descrito pat' 1,i ttle y et :ro s y nuee

trt discusin se restrinel:) e les mod :i.f'icticiones ce son. te G0S2\rlas

para acomodar las varias restricciones del pid:JJ.em.si del tratl3por -

t:1.ata,:i,

nespooa de que ceda paso haci e adeJ.Dnte dal ir.bol de bsqueda qua

ae ha realido se deba chequear que no s0 ha violad.o nil'.l:,'UM do -

las restricci one Si 1:t!>daa laa restr'ico iones pr.esentlil(l!S en let

introouccin da esta parte existan, el oraen en el cool se cm

que&n para factibiliza1; es muy impcrcante; oste orden dependo de

quG reetricci6n es 1e ml..s restrictivao Si se viola tgune de liS

roatricciones, debe trao un paao at:r6s y so rt'l.mif' ice hacia un -

nuevo nudoo

En CF.lda );)Mo h&cia adelante os inlpartante verificar que no soJAmen -

to el anl.eee de en.treM no viola las restr1ociones Jll'.>rO tembitin

qu la otra parte dal problema no se vuelirt er.emanto int4ct1blee

par ejemplo si dos en.ll:lcea escidos priro.ei..o enleztn un clie.nte

con dos terminales ertificiaJ.es carrendo os! una ruta con e :me
 35

tG un cli<mto ,_,tendido , los siguioxrto,s v"'hculos no :oclr{n sUC1ini.!!

trar a loa eiguien-te.s clie!'.ltes debido e l insuficieuci3 de c.:.:pqc_i_

dad, pero &sto no se puade dasoubrir haEtJJG gua se ha tomdo un Illil

xo grande d0 a.os na cid adelante, entonces se evita um grn can,..

tid da bl'.lsqueda inneeaS'iria si le :;arte no :resuelta del probleJll.8

se chequea por 'act:1.bilid.ad. Esta prueba puede ser n.iy di:f'Cil da

incrOOlentar en ce.da J>SJ'30 hacia a de.la nte pe ro se puede diseffar al

prooedimien.to simple qu-e pemit datermimr si lo a vehculos r astan

tea pueden atender .,.1 los cllm.tes raeu.ltndo todo esto en un aho

rro austaucia.l en al tiempo y astuerzo de clculo. Ot:N complicec16n

que baca qua este m9todo sec menea ei.ciente en le aoluoin dal

:probml!'m del ;lgsnte vic.:ja:ro se debe 02 1.c, s raglQ]I henr'stis que

dtermina hsta qua nudo a rniif icar la :pr6xima vez. En el :p:ro"!.ll.B

ma del .:,g3n:te v:W jero ralliiicamos haciQ el nudo con la penalidad

yor y esto tiene IJ.Ucho ,x1 to en Umit&r. el tanao d9l rbol. que se

necesi'ta buscar,. En el :problema de _progren.ci6n da veh!cuJ.os 6 tr~n~

:portiste a lo que parece s&:c un an.16.c(j dessable puede que viole um

reatrlcci6n y nos haga seguir con J:'Glnii"icaci .. .mesinnecesarias.:- En. -

tonces Otl1i fol!la da aac<>ge.r el prox.imo ll.UdO 1)0 heCOJ."' las ram.ifi-

oaoiones y que ea hace necesario, nos :puede causar mucha dificultad

en le s.:;:tisf'accin d$ las restriccionasc Js:. eficiencie computcio -

.nal de. algoriitmO ae :ramifioaei6n y acotcin par res:,lvs:r el ro-

blena de t.ranaportistGa se muestra en la tbla (32)"

sea C-=22 tone- la cqacidad. de camiones ( exista un nmsro

1nfini"to da esto a )
 36

ci6n ( no hay l'G'triooionea odicionoles ) e

--1 2 3 s , -
?
!)<zmJYJr.J.cl
I .__..; 15 /O 13 ' /t, q (() (Ton-)

-- - /2 /1/ 20 lf 20
lb- o<:1
/o 12
--W'
~

&>O /3 !/ 20 / ["
{!l)

(!l(J)
&(2.)-:.
i:)(3)-; !
/O

'{ r
I .t,. 13 c:,O /O /.t JI (1<1) /J!(lf):. f?
f
z
-
.Jt1 /! /Ci oD IZ (2) :;( '5):. 0
1 /{. /( 20 IS /2 r,C>- }O (/<.J) cQ(,) r;
9 20 15 /! 2 /O -=:::> (2) 6< O)::: Cj
()) (S) (2)

..... .
sol.uci.6)1.,-
..........
oanenzamos l.a solooitn del problama f roducianck:> la matriz de

clistanc:Uls 5 oostos seg soo el msoo

U2 idee consiste en eleg:ir el enlce que ric oporc ione el tneyo:r

:i:,ec.bezo y re car la fica c16n de lo poai ble rute cp. e e ont

ga eil enlace descrito 6 que no lo contangao Cndo la ruta

en Gstdio no pueda &tisfE1cer Illi()s puntos dan.11m& par las reG-t

ti-1.cciomo iie.1 ob:1$1.la, qu.e confcr Ul'.la rute.....,- <:.on los

punt os no eonsid.edoa, se. forM otJ.a matriz m(s J_)equ que

11 origh:iar!.&. la (;!l;) se resuelve como si se tratara de un p

blen:e noovo ro tom.o laa aeto5 atigiu-;;les de J.@ Jlil),triz do

dio tl)ncif3 :l.niciA;.iJ.o

N,1. 4rbol f'ormedo inici.ilmente e

 3'?

puast:> que la triz reducid<>, slegimoa al m')yor rechlazo que

es 5 y que co:rras_pond& f.t (5, 7)o F.l nudo ciue tiene UJ:&l 1'tyi,...

t6 enc:i.ma del onlaca, re:Present al conjunto do las soluc io-

nas en doIXle no a.e considera el enle1oe (5,7) y le dere-

ch {la qu.a no ti ew .illr\gUna raye encim'.:l) as el e o:a.junto de

soluciones en dohd& interviene el enYtce m, roiort;1 do0

Los 1mi tes d0 l&s re1ms 12cp1 arfl5 del ,rbol se fcn,nan sgr2._

ndo 4)1 J.1.mite d0J. enlace 5 ra nterior, el yor de los

rechazos cmoontNdos (a ca@ celda qua t ia:ig valor cero so

lo encuentran loo valorc,s :m!n1moa de l'l fila y oo l\lllll:la roa -

);X:)Ctivc1 y se suman, encontr1nl09e as: los r0cha2:oa) o r.os 1!-

mitos de 1as N1nas que a:p&recen e la dorocba, se encuan:tren

de le aiguiente manera, uns vez eleg ido e 1 J.r..imo rechazo de

,
la celd$- que pemi.te asta recl:azo y se ve la posibilidfid do

roduci1" Ja na:triz que qu.da; el v.:1.l0r rasv.'lt.rmte de reducir

esa m':itriz ( pueoe sr cero en al ceso qoo .J6 mtriz fong

:por lo r.t1'nos un oor0 en toa.i.s les fiUis y col ) , se .a

grag. l l!m:t.te ds Ja rar1e an:teriClt' y se obtiene de asta InE,

do el lfuit a del conjunto de soluciones que contianan al en

lace seloccion&loo
 38

I iG 3 4 6" ' rJ
/ e>O z 5 o t'
1

7 / 1
z 3 a,,<)
o oc:7 6 .?
3 o 2 -o 3 / /tJ 5
o
' 18 '<
4
._,/ 4 3 ,;;,e::, /

5 ? .:,;O /O o
l,. >? /rf 6 2 -o o
7 12 !3 f.} o g -o -
- 'fj
(2) ('l) (5') R5

~-
I
I 6" 2 3 () 3
1
z .J t./
' & ')
l
2 E, oC) o o' g I
2
'--
f
3 () '!J 0 2 c,lJ / I 5 6

3 2 .. 3 ,,o ) o' /
(, /{, '1 b oO 5 o
b fo: /!) 3 2 {)t.
7 13 7 03 3
/{?
":;;. {3l

Hay que recordar que 1-& 1"mliticeci6n se b&co e pa:rtir del

nudo qua tenga el menor lin.tte.

En el ejElllplo que se es d'.3.sarrollando, como dl!llboa l!mite.s

son igualaa; alimos eu.lquiera de ellos digil,mo s la

derecaa ruta tonwti:va es J?1- l? - .P - :P con c&pac!

5 1
Jj\ \,l..llll
':"

d de 18 tono

Enaegu:i.d!i; .anulamos s t'i.as y columras 5 y 7 raspectiv$ -

mento y hacamos la disnci& (5,7) igual di1 cero pere. evrlltar

conaidenar otra ruta qua tenga sentido inverso a las que se

van obteniendo., vemos si podamos o no rao.ucir le mat.rlz re-

 3S

sult;)n:ta y buscamos JA celdlll con 01 m0Yor recmzoo Este -

valar BS 4 correspondiente e ( v1; ) : form6m.ose la ru -oo

P1 - ?6 - P7 - P5 - P que tiene u:rti9 c:pacid de 22 tone,
1
S6l.:i ;, le cpeciC,,d de loB oamior.es y esta ruto queda est!

blecia.a corro se ha exp:resado Gnteriarmenteo

LOS :,."()mifica.ciones hbidas b.tsta el man.ent;o en que se lw. -

ene entrado u:ti) ruta salud 6n se mP.estr.a a e ontillll$c16no

;
I Z 3 4 5 '
5 2 3
1
I e<:) 3
< 3 ,:;,tt() 0
2
olg 2
3 () 3 o-<
. o I / s
o {)
'
(./
3 ..:--Z 3 ,o ()

4 (( J'
1
I 0

'7 t/ /3 /O q .,,O
{)4
-
cuando se ha encontrado una ruts, se &nulan las filas y co-

l'lllllWB de los punt os que la confor.man y se corre in resol..-.

vi endo el probitena pero tomando Jas distencias dG la metr:lz

inicial. de distanc1&s 0

2.

3
g-
/O /2
/5 !O /3
o.o /2 /4
-D
/3
(1c)

(lz)

(to)
!

3
..,;:,

3
o
5 cj .3
c,,O

.2
o
..__... ! 2
-'?
"-

3
o ef
~ ,-.....
a;
13 /4 13 c;:;,,Q
(1'3) q I 1
.....::>

(1) (2) i:4-1

I .2 3 t.

/
1
oD
4 o
1
'
. 3 -o

IJ o'
3 o' I, ...o I
o" o (J -o -

R"=qg 1

oonsidel'8nd o qw tenemos N dop6s itoo .ert :iflciales ( P ) -

1
el siguiente yor rechazo debe ser Cc(llculdo sin tene r en

cua:rta aquellos en&'.) nde p&-tiipe el ar!gen 6 dep$itoo Es

por esa :ra6n que esc oga:nos el enlace (2;4); aunqua hubi,

moa podid o tansr el {42) ya qua tienen el misno rechazoo

. . .
Esta ruta se conforn CdmlO p - p - P - p que time U:ti3
1 2 4 1
ca::ecido.d de 18 tono y cuyo ir'bol se muestra a cont1nuaci6n
 41

':?..J.ei.;;;o (pe al punto :resten ta p t ien.E: une demnd& de 15 -

3
tono qua de 1ncl:ulrse en la r-.tt:, sobr,,rposar!e la capoi -

ai.a a.e los oomionos; la seg uma ruta quoda def i.n:lde cerno
se most antes y J.s tercera ru..ta
se:r!a P - 1>3 -
l'1
1
]..\ :i:esu.mm do rutas, d:i.stsncis rae Cll'.Tidiia y c.erges sa da.--

talla en el siguiente cu&droc

l
' z V .,,. A 5
< -
~
'bs1-"' c.J
- '.i .. ? - ?s - ?, 3t. 22
1

!
?, - i - ;t - ?, 42. /8
?, - 1 - : 20 -j 12.
I )J7:::.. 1.11: 9R

El p,:incipio de o:pt:Ll'!d.lidad :a, conside:ranilQ el prohl!l'. del tl)I:,

tos da la t' :ig me t 3Ql), podemos 01llJ.un e en ul:1 1 ta alea t orla a

geno:rer una ruta 61)tiw -2, 6pt:IDIP -3 u 6ptintl re

.As, si se -va a p:i.odttcfr u1-m xuta ptima 3 a parti:::- de Ubll rute

por otro grupo de 3 enlaces que gcnen'l un oo,s to tol me uor(! En

el p.r oblana da transportistas Din erob!rgo, uno t iem qua .hace:r -

uP& ;prueba u.ltoriar en. c&<la eta-pa p.'\:t:a sGgut>:rsa que un nuevo

gru.po de on'.LJos no fol!1a rutas no factibles" As, eu el probl

roa de procin de -veh!culoe, uno puede emi:ieza1 con ull;l ruta

11icial qoo se nace de dos ruts fctibles y prqgi'asiv.:1m.ent:,e me

jorarla s-=;. que es ptimo 3 nant3nitlo Ji\ factibilid&d l tl'l3,-

v6s de todas loa tra.nsfo;maciones o

u ruita :factible inicial sG puErl.e obtarer en vriedad de for

una ruta es simplo etib1e, por eja:nplo, s0 hace da xutas

qu.a contl.l3l'len u.n. cl. tent.e cacle UD.ao ou-aa, ccn l&s citte uno :pued0
empezar al algoritmo pt:imo-3, puedo sfll:' obtenido por uno de loa

mtto dos aproximados qu se describan postericrmnte (tal e ano el

m6mdo da- c:.:Jro y wrjght de los iharros, 6 mt odo de HYes)

O<>n la matriz de costos mCE trtde en la figl) 3ol uno pcra obte..

nr uua ruta ptima ....S <:on et nsni, nrod.e vdl!culos de J.n ru

te inicial, Si, sin G1llbargc reemplazamos al b.Jt>qua de 3 esqui

m.pati or izquie rae N :t N un oonj unto in:f'inito Gn J.jl matriz de

costos por ct;ra ocmteniendo ceros, el mis.10 Jgo:t'l.-tmo m:>clu.ce

una ru-w 6ptilno-6 y el mismo t iElllI)O &u.tomlticem.S>.te rece el m

mero de rutas, de vebculoa y Gsto nos lle-va a un ahorro en t'l'- -

minos de la diatancl.e viejSclao .Ambas versiones del algo.ri 1rno

son lttUes en diferente& circunstancias de::.emienlo de los o'bjo,..

t!voso vale l.& pena melXli oner aqu que le sclucin del prcblms

de tr.n.sportistas qu.e rniilJJliZ$ 1$ d:istanc it3 to tal recorrida, no

necea<Jl'ia.D'Jnte use al m:fnimo nrns:o de velouJ.os reqt\eJ:idos l)Eira

 atend.e:i,- a los clienteso

como en el prcble!J):} del agente viajero, se ha. eneontrt\do q\le al

e:.q,lorar lfl rute 6pticlo-r, ea perteotamente satisfactorio conf\-

rnar l<Js considereciones pe;il';l la rute 6ptimo-3; l que rrioiuce r.!

eultGdoarimuy buenos en un tiempo l."'lZonQblanente car1x> (' JJt el

blema do trensportj;;Jtas sin ambergo se e rouentra que se obtienen

mejores l.'esuJ.todos y se pr<xluce :trimero un m1maro d erutaa 6pti.I:lo

-2, se escoge luego la mejor de ,stas y de aqu! sa a:r:ipiaza a bu

oar la mejor l.'U'W 8ptin,.3 U\ fig ,, 3o2 noa n:uostl.'tl Gl procedi -

mien'b:> pel.'6 datt'tJir ruta .timo,.r ,Qrt1 mdo d.o una ruta :L-

30 5 AIOORn'MOO BAIX>S BRO&-

Ell 1963 Qlarke y Wl'ight introdlljeron el conceo de Sh()"roa y

deade entonces se ho deEtirrol l.ad.o y nblicado eerie de inten..

tos pa resolver el probl de tr-ansportistaa ueendP toonioaa -

'beseas en asta conor.,pto.

considere un t<:n>minal que i-aquiere abastecer a n olientes. AdG -

m(s, eu:pol:lge que dispone de atfic :tente mEro de veh!culos do

..
sG

le o&P9cided aaecuda en el terminal, de nx,do que cad:l cliente

:puede aer atendido individualmente :pol' un veh!culo qua suministre

a 0se cli ante s dlementoo El cos to o diinc:la tatal recol"rid.c

_por talo a los vec.ulo s es e nt oncea:

-r,
2 ;r
:-.1
C11
don.de el sub-ndwe l representa al terminaJ. y O jl 0s el oo ato

da las jornao.ss del tenninal el c.Uenw j ., El n:Bro de veh!ou..-.

loo usaros en este caoo es SU:pongamos ijhora que loa clientes

.! y l se enlazan de forma rpe son ab.astecidoa pt:r un mismo tn

en la misn,J ruto o l!}St e en lace de clientes .!, y f e l:1millf; Ut.:l ruta

de vehculo. y tam'Qil.n reduce el costo :por UD;l cantiasd

te cantid (.:li se denomina el ahorro del enlace {1:j) y conviaie

j
temar loa ];X)Si tivos; obviemente ll el DB?j or ahorro s nos pormit e
ij
el enlace ml,;s deseable de clientes i,j) en un: 'l'UWo

Este algorl tno se puede describir :por el aigie nt e p. ocedi-

e) oelcular los ehonos s1j J1l tome los p;lres de clien -

tee 1,jo

b) ordewr los ahorros en forma descenlenta o

o) l+}'!l.paz:endo de le perto superior de J;i llS.ta de ahorros or

donados> becar lo siglU.ent

lo- Si el e nla ca ese og ido r('J$1 l ta en una ruta posible d 0

acuaroo e las res tricciones del problErJS, entorcas

agregue e este enlace a 1a solud.6n, sino, roohnce

el enlaoeo

20- J?ruebe el nuevo enl1:1ce de la liste y re:piitl el :teso

(1) hesta que Yl lista se haj(l extemedo 0

d) ps enlaces que han sido escogl.doo :t'oxrnan la soluei6n del

pt.' obl1!1E1 e

Obviament a 1 este algar itmo no p:roduc e le respuesta f;pt:tme y

baj o estas circuns tancias la respuestl :pueda dife-jr comp.

tamente de u n valor 6pti:Jlloo El )goritmo es nuy simple de

apli car y requiere paqueffo tiempo de oompurtalore >al.'ll aE.ll'

ejecu"ltldo; sineni>argo, aJ.8u!ll'.:4s :res triecioms son didciles

 46

de in0':>rpo1ar y lail ,equerimientos de :rreoacl.& en la oompttt

dore se vuelva e,::cesivoac

HttY elgu:nEls di ficul 'ladea de eate elgo1 itino que puan afee-

ter la cslid:ld de las r.espuestes qua produco o u vez que

se hacE1 un enJ.8oE) y.A no se quiebl.f3. es dec :ir, su desetiblli-

ded se comiderll! independient0 de los otroo enlecea que se

pueden 0scoger en formo individ'U:31, ya sea quo se p.i.edA

pt'Obibir la :t'utur. selec ci<5n de l11.l.0vos enleces cuyos aho -

rros san ligeramente menores qua el del enlace ascogido y

que al 'inal nos .Proporcionaran \lll!l mejor sol.uci6n el pr5!_

blet:fl o El aiguiento alga.' itmo es una 11gel'O mod1ficaci6n

del ;r;i6todc de Olerke y W,right y se aobrapona paroialmente

a esta dificultado

sea o:. 22 tone i. cacidad dG oelnionea (exi ste un

liro.aJ.<o infinito de &silos)

IP- Iltl triz da d1sten1as ea d6 a continuacin (no

hay raatrioo iones adicioJ;llles) o

 .....
47

-- -r--
solucin.,-

LO :p:t'i1naro e hay que oo lcular son los f.l h.or.roao :t!l<!.

to se hace aplicando la ec'J!3 ciSn (4o7) o sa e1rp1

ce con detall en el cap!tulo IVo

ps ahorros oolcula dos Bp:lrecen en el lado izcpiel'-

do da las celda a da la ma.triz de @istanciea y obo ...

l'TOso se e:pr0c1e que existen dos ahorros con valo -

res m6J.mos de 15 corraspondiGnces a los en.lacas

(7,5) y ('7,6), paro calculando les distancias tota-

les de ambas posibles rutes escogemos el enlace (7,

5), origin6ndose la ruta tentati F - P - P - P

1 5 ? 1
con una capl\cidad da 15 ton. o El siguienta meyor a-

lx>ITo .& considerarse es 15 que corresponde a (7,6)

p arm.1 ti ando conf'orroer lG ruta P - P - P - "f - P

1 5 7 6 1
cpe t iene una oapaoided de 22 ton soo la oap,ci

c}jld de un camitno como no puede enviarse mas car -

ge en esta ruta I se h. encentre do una de las rutes

soluo15n del problsna0

JO. siguiente ;aso consiste en em.1.ar las :f'il.ils y

ls da loa puntos que inter vian.en en le ruta y

con el resto -&retamos de encentrar oties rutas como

si se estubiera resolviendo un problema nusvo o I/!

matriz con le e :fili3 s y columnas amla das se Il'lllestre

en lA siguiente ilginan

El siguiente nayor horro de los que q.ieden es 14 ,

corresl,X)ndiente al enlace (4,2) que origil'J), le rute

P. - P - P - P con una cap.ciclad de 18 mn e FUeato

1 4 2
que p tiene um dantlnda de l2 ton (pe no roa01n0s
3
 48

anviar;I.a en esto ruta 1 segunll:l rutE\ roluci6n ea

[ Q

fy.
; 2.
_,..,...
10
I :;_
'Z
z
5
' Jj !?...
'? 9 'Z. is
---- .....L.--.
ft.1

7 ,. IQ
?t.
?~
.,
r..:r.
?:;;
?<..
?,,

si e.nuJ.amoa nuevente tilas y columnas de los IJUE..

tos da 1l rut1;1 notl.\IOOs qoo el nico ahorro posible

de oonsiderar es (3;1) por lo que necesitamos otra

ru qua es :e1- P - J? con um1 oa paoic1ad da 12 ton...

3 l
y mstriz 100:road.o dG :rutas se scttl')lize da acuerdo

a cor.:io ee fueron generando lee rutas (pedanclo de li

siguienb e Ill:I nel'6 s

 49

-
t -
~4--
1

?,
?2. ' (Q
!' ! 1 l

?J
,,....,
/2 i.
J
tl 1
--
( /.9 1 l

1
-

;1 ,
(5 2Z !

f '
!

?l

]1 1
-
1
i ' 1l 2 2 1l 1-
El resWlen de ru s distancias y carge s se mues -
trs a continuaci6n.,

R u / A s ');1.:, '> C(} Cai,o.;,

<

:- - .7;2 - } - ?
- . ~.
3e, 2Z.

7: - - ?z - ?, q. 2.. ;>
- - ?
.-- 20 /2
l v,1,=,,;?(;./ %7..I:
1

e,

3o5o2 Jt.LOORI'lMO DE TII.lMA:N Y COCHRANmc-

A ..,._, a ---- ....-- , ... .__...._,.,.,,_

Es1te algori irao difiarG del anteriormente most do stlo Gll

la form:i en que se aaloccionan los ahorros ,, En lugar da to-
:mar el an.l.acs :factible con el mayor ahono, en oo da etapa
so selecciona el en.laca que cundo hecho, nos :emite esco-
ger un segundo enJ.a ce da modo que 1 runB de loa dos aho -
rros sea lo rr..yorr.
El anterior c:r.itio de sAlecc16n que r-aquie:t> el efacto ae
m:i.ra r dos en1D e ::,s en secuencia 1 puede ser axt endidc a mirar
tres t5 ms, pm.-o los cllculos involucrados se vuelven muy
extenaoso
 nm-0010 inf'1nito de Gatos cio1113s y no b:1y rest:d.5:;_

cionas fldioionQ_,le3e.,

I.S triz de distau,:d.as s .e u oont:l.nc16n:- _pero

S<3 le ha &.grdo loa ahorros qua se loulon del

1.l" :i.sm :rovdo que aL algori-tro de clarke o

.,... ____
\:,
j , [),
-
,11
i
')
! ! Ia 2
"7
r3
l
,z z ' 1 J:J ,2-l -
1

8 2 13 f'J /<f /::,. 13

i-
1

g 3 I JI 1 !
-,
(o -_ O " }{

,..,
1

P, {. lC g L q N /f /2 / 21
-1 t
t?l ? 2 q /! Ir ir fo}
. .lO t./ /5 /1 l
--

I.nicielizamos la triz rcado de rutes coloe4ndo

2 en loa enlaces aJ. or!ge:n p:a:xe_ indicar que as1g1!_

moa un cll!nin a oa db punto

' ?t Q
.
?z ;1 Jo z. -
-7..> }"l. 2
?4 g- ;_
'?:;;- r
/,,, 2-
- - 1
?, r .- ( '

1,_?1 rr Pi 7-
r--- - - - l
1

1
 51

:euscamos al mayor ahorro teital de los p3ras de uni

nea resultantes do eleg.i:i.., 01 yor aho::rro totl y

el siguiente mayor ahorro que no contenga ninguno

de loa p..,.ntoe dsl pr-imer enlaoeo

r iJHOllllo'
1 AHORRO UIWOwZ. .6.l-loRt.:
(.)A}J()(J 1 7D'T/JL._
=-=-
-- /.... .. /y zq
- /5 3-?i /3 '2?
0- /5 - /Y 2 '7
2,- '2 /'f ,S- - l [ 1
21

COllX> my varios ahor.i:-os totales igualas, oacogemos

uno de ellos digll':loa el primero, qe g&U3ra dos po

siblee rutaa :.

P - P - E .,. p oap4' 15 ton

l 7 5 l
P - P,1.- P ... P1 Oc:.1:p 20 ton
1 ,.. 2
Ra oernos hoos ( 'l t 5) 'Y ( 4 2) iguales a cero paN .!:
vitt.lr genarer nuevamente laa miS11ae rutas -y volvanoa

"' cal culer otro ~ :.i. de uniollas con ntlyor ehol."ro to-

tal .

,4110.-10
t//()J
() 1 AJ/aRO llcrAJ2 MJR.Ro TOtI..
.
-h /.3
.

-
?, .. ?q 11; 2i' 1

1 #; - ' 1 /$' ~ ... ?z. 1 13 2l' 1

{.
??_ --
l{-
i-- ?i
J'I
/<
13
1f,- - 1
?11- f.,.
1
N
!(/

/f
"
Hl 1
Zt
21
2
 52

Pl,esto que t:,dos los ahol."l:'Oa totales son iguales -"!

cog6tlJOS c11qlquiera de ellos di@mos el J.)rinnroi:- 1....

ce-r los ahorro a ( 7 ,4) y ( 6,2) iguales a C:<31'0 y ve ..

moa la pos1bil14a d de 1.ncMmanta:r ta.c; :ruiil a, oo

unir dos rota.a xe formar. Ull;1 oolt, 6 de generer

nu1ves J."U.ta s &n el ca so qua loa puntos e.al enlace

en estudio no sean. ninguno de los puntos de las ru-

t as ya gen~~ Sc:

TOI!l;lndo como sG dicho, loa ahorros (? ,4) y (6,2)

las rutas aer!'en ah()m t

P - P - P - P. -
1 4 7 5
P.t 00Po 23 ton

P. - P - P - P - P oape 27 ton
l 4 2 6 1

como ambas mtas oobrepi ff! n le oa e ciaa d de los ca-

miones desechamos los ahorro s con41darados y buac!.

100s nue'IJ'8Illente otro 'Ifliyor ahorro total e

.
r)pl(J, /.JJ.IOlcO l/HIOI(} iJll,O
ANOlf.i,
70"Tl:)I.,.

S- ?c /.{" 8-r, 13 7?
;- ? l'ia-?y IY 21
_ ? IV 1-? y 2

- 7z /3 g_7( /J- --2f

como l'.ll,levemente los &hOl'l'os so,n iguales tomos el

i.ml"'O :> originaMoae las s-iguientas rutas tente -

tivas i

l? .... l? - P - P - P oa:p 22 t-on

l S 7 5 1

P - P .. P2 P - P Capo 30 ton
1 4 3 1
 5-'.3

I,a primera de l&s rutes mostrad.es satisface la ondi

ci6n da capacidad da ca..11i6n y como n.o puooe envia:L"t

se rrJe cargEa, hemos encontrado la primara ruta sol

ci6no Corno al enloe (3,2) origina q1e se viole la

restrico16n de capac idad; deja de lado o

:r.a
ruta P - p - P - p no :puede satisfacer ninguna
1
1 4 2
demanda mas pues su c apac idad es de 18 ton y el puE_

to p que fel'ta satisfacer Uena una dananda de 12

3
ton; luego, sta tin:8 ruta tarnb:t,n fonna rte de

la soluci6n. .Anulando filas y co.ll.lIJUJ3s de los pun -

toa que toman erte en la ruta antes mencionada, qe

da rara
ser satisfecho solamente el pi.nto P el que
3
se asigna en una ruta. de ide y vuelta

El res&nen da rutes, distancias recoITidas y acxoan-

da. se. tia.facha en cada ru.ta SQ muestran. me a a,den. -

te C(Jll.O tambi,n la triz marcado de rutas actual!-

zaa.a de acu,:-do a las rutas encontrada a como solu -

c16n .,

una e:xpliccin mucho nis detallada en cuanto a la

soluciSnmisna de 5ate algorittno se encuentra en el

cap!tulo V de ,ste trabajo o

7, cQ
7' i I
?) /2. '2.
7v /J' J /
?r 22 /
7 (. ZL I
?ry l< 11
I I ]
 54

1? (.) 7 .t.\ }):, 1na cr,;:.

73- - ?, - } - 3C. 2"2

--
?,-i?-?,
7:-0-
z
'20
/.?
12.
})1sll7ti.il 7o1:
. 9? - '

Es11:a m~todo tanibi~n difiere del de OlrJrk0 y ~"'i8ht s6lo en 18 for-

n:ta de med.:f r la deseabHidlild ele un enHleec

aaskell sugiere las siientas altar.nativas da E\horros :

{j = 5t1 (e+ /&,1-J 1-er}

: 77:J = 5<; - f,f
donde O es el 'Valor px-omedio de todos los O Y S Gntl"e los :pun,..
ll ij
toa i y j, mts que sobre el ah(Jj."'.t'O Sij discriminal:iio stos on :f.'a.

vor de loe enlaces qua son s o meno radiales, los que el m,todo

dal ahOrro :ravorace e aqu,lloa q.e son cil.'cun.te.rene1ales.

As!, el algoritmo de ClarkB y wright en lug-ar de ordamr los enl.a-

ces en fo lI!la descendente besados en s1j , el criterio re. ordana:t'

lo aqu! se besa ya seia sobre l, ' cS sobr e 77;'..] y tdos loa

otros pasOs del algoritno, son los mi_soos

e -..22 tono la capaciasd de camiones (e:d ate un n<imero -

infinito <le stoe y no b.By restricciones adic1onales) 0

!f). matriz de d'd.stancies se da e continuacin y ca&l celda

oontienet

B
o.. 1
 55

A: ahorro A<r / 17; 'r

B: ahorro S j (el mismo que usa orlc-3)
:;,

Or; distancil o oos to

?, Q
T l

?1. 10 2. j 2. )! -1
11- 7_\7.(/o -M: l'J: /2
' :

?3
e 2 : _ n -ry) 1c9
l

?4 20\10 fo J

?r- . )Zo
-

b 2 jLj
. :. i -i.r\3 -- -3} / t J.,;,
") ! 7 j 11
:

?, r 2 '. 2.j/l -/3 \!K -ll\ (. 1t) ;, \fr ;tr e,: ,t. ll
: - ;
1
t

?, e 2.. -i\q r((/'l ld .,, t :Ir -,\ ,, 11 l't1!J z '-7J-; /.r! /o I

: :
:
l

soluci6Il(o-

., Bnplaenilo los ehorroo, /

:,
, s,j (e-., e,, -t?1J/- fi:r )
valor da O se calcula de la s:!guie nte manci-as
- e, --c.
e.::---
,.,,, - '
1.r1-,o.1./jt, r+/{,f 7 7/

e /<,
En nuestro ejemplo, para un par de punto a que tomen un

enlace cualqutere como (z.2), tendJ:unos;

-"l 2 =- 13 (/ Z r //O- I / - I1 )

,l3.,.2 - 6,5
paro el enlace (4,2)

A,,? = /e (>2, /1!)-1 /- I )

A. i', 1. ;; - 5 y
re el enlftlce (6 1 4)

A,,r:: /<..f(12f-f,-1r/ .... 1r)

A,' q =- o
 56

vez enco:rrtradoa los ahorres respectivos al algoritmo

se cormina e ano el de clarkeo As1., el ro1y<ll:' ahorro 165

qua cor:i;'esponi.e a (7 ,5) C%t' iginando ull:1 pl' ft.1Sl."a rute l\ -

P - P - P con una c$pac1dsd da 15 ton

7 5 1
cano por esta ruta puede sat isfoc.ersa too.ave eJ.gn otro

:punto, buscarros al siguiente mayor ahor.ro qua nada neX

se :por P 6
7
5 o ]JBte en.lt1ce ea (1 t6) y chequeamos les

restlicoionea del probl >re ver si es f"otibla anex

lo e la rutao Yl nica restriooi6n q-.l.a t1.ene el probleme

es ln ca.pacided de camiones y cano la ruta t crnada P- p6

p - p - p satisface esta a,nQicin., le r iil:& re ruta hil

'/ 5 l
a ido em ontr-r:<<19

Anule!llOs l&a filas y colum.!as de loa puntos que pertic1 -

,en en lA rute y buscamos nuevamente el siguiente mayor

ahcn.To El enlce (4,3) tie:r el maycr al:lor.r'o () que

gan&"a Js ruta P1- P 4- P3'- P:i. con oopacid-d de 2,0 oono

CO.tilo no puede e n"V :far se mas por esta ru U1 dado q.i a P2 q_ue

es el miico pUnto al CJl e :f:lUt.a tisfecer t-ttne utl'!I demeu

<la- de 10 tono; U) sagundc1 ru-ta bEl sioo hal.)!) y l t-erce --

El resunen de rutas se muestra su:idemante
j

R u r 4 .::'.) [.2),,:57',.1 ne, c,c),-oaJ

?, - P, - ?,- - - - 3 (;. .22
11- ?y- 1J - 3, 2D
f, - lt - ?, 3-0 /o
IJsz,, 1t.l= /o
 5?

b) W-1plea11do loa ahorros : llj 5 <,r (?,'.j

u. ,nueroc rnetr1z ae aho:rro s

?t ;
? /c:.J 11 1... :IJ
n. 131 /?.
:
?3 /2 2. it !fo
. .
.,'- 1-z. )3
. .
i ->). ;on
:

?q o /f.( N
.
e 2i. "l.. f -1?\3 )lO ...
.
-
f/
: i //
. 7 !. _, ! lf [lri
?, 2. ,, o i/t
:

l -/1)11 -14[l ! ll) -f i,

. : lf /2

77 e (. \?. 7 -(1y)y (i t(f{ <. i1r! 11

.
;
1 ir
;
2 t//10
. '
. t

f>OT ejau:plo para el enlace (32) ten:,mcs

3f 2 : s, i
I - <: :
,, /3- ll
-:: 1
se aprecio qua loo enla cea ('1 ,4) y (7 :s) tienen loa m-

yores horroo y son :iguales. OUndo sa :presenta est

situacin se :puadG ::'Gsol ver ascogie IJ:lo equt1 enlaoe que

tea la mcmor distancia que en w.0stro caso ea (7,4)

gen:i].'ancb 1 ruta P1- P.,,- P4 P con 17 tono de c.apaci.

1
aaa ,,

Como al m6'.lor vlor de li?s dardas que falta sqtisfacer

as 6 tono corre51>oncli eJXt e a p5, que de agreg.arse a la

tti fonMda sobretsar!a la capeic1ded de camiones, la pri

me:.- :ruti1 se lm encontrad9 y deb-emos enu.hlr fi.JJ1s y co -

lurnnas res:Bctivai'3Q

El sjguie.nte maycr. ahorro os 1 corr0poroiente a (3,2)

qua origilll.l la :ni t J?- p3- r2- P]_ con 2.2 to da capa

cidad 1 que &ltisface lr, Dt!,paoi& d d.e oc:>mionaa y en cons

 G'\lanc:l. se genera otra ru 'la o

como .loa siguientes ahorros a coni:d d.er t:iena:1 valores na-

gti vos, auto sjgnifiei:i que no se c\het' na&:l si hacam.os dt

ch uni6n y lo 1rl's comrenimts es esigl':V'lr un camin a ceda

punto :cestante$

El reS\lm.en da rutila se muestr a cont:inucin

,K u -r A s /)15 c.\ne1..;..
.f. '\ . 1.'r:t:'. .
C- irfd

--/ - ?fJ - ?y - ?1 33 /7
l>t- ?3 - ?; - r, 3? 22
? - ?.r - )C., b
-p_'t_ 3.2 7
.vIJ('/ ---
"Jt,7.;/: /1cf

Este xrltodo usa los a lx>:z.oros cano un erl. ter o pera ramifi aar en un

trbQl da bl!squ.eda el qu& ,;rn. cada lil nos d.a posibiljdd el -

St'IOOr ya se-1 el :mejor o al m!a pr6ximo el mejor anJAce pos!blb oEl

m&todo (afondo um bsquade m rbol) es relacione.do en p.- inoipio

o la t&onico de ramificeci6n y acot.:lci6n descri-ro antarionnante,

uunque no ae calcule l!i.nit0s aqu y no se haca inmntoa 1>-ra 11.Iili -

'blr ol.. ta?nlflo del trbol su lugar a610 se exploro..una l)equeo

porte del trbol por lo que no se gaNnt :tze lf.l opM.ntt11da a de la so .....
lucin.a

El m&to do es el ajguie:nt0"3

conaidc,re la lista ds anl1:1cos en orden descendmta de <'Ahorros oomo

aigus; (Y, j).,. (kl), (m,n), (p,g),i ateo En. eJ. algo-.l"itmo de -

Olerke tmd wr"lY;.,. el enlace (i,j) se selecciomr1a ;primaro, lu0go

 59

al enlt\ce (k,l) si es tacti ble :, e.s sucesi VEtrnenteo li:tl el preoo_n.

te llgoritlllO sa .mioe Wl0 sslacciGn en 1E. pr'.t.lllat'S eta12 pa elegir
los enlaces (i j) 6 (k,1) eono s a muestra en li.l fign 30 30
si se hace el snlao (1,j), el pr&xiroo enlace qUe se tomara ee:..-d'
(k,l) 6 (m,riJ BU:ponioo.do naturalmente qua ellos oon f'actibles()
tf) p:ooeeao con:tinoo Msta qua no sean poeiblee m's ramificaciones
ouando se ha. cc.:-plead.o el 4rbol de b\1squed.a, ten.en.os un. .e'?O
(le rutas pcs5.olas y sus cos-ros para seleccio1mr la mejd'o
obsm-ve qu la ruta representada por la cacle:na de 18 mano dereoha
det nudos da le. tigul'Q 3e3, es en efecto le solifu de clarkeo
um veir. que se haoe WJa ramitioacn :se sigue por otws en serie
fcrnEndo una oadena h6'sta que, sa el.gs.u:za uns aolue16n y 8610 en ...
tonces, se el.."]?laran l.'llmificacionea al tarnati vaao
.1.st t at la bsq_uooa Sii' tarmil1D p:-ednta s.:s te aiguna ruta
oomplete d modo que ya se puede escogar uta. soluc16'n. Uno podDa
no-tar que e.un si se busOil el '*bol coleto, la s:>tucid'n no ea 6'{r
tima ya que solamente ee han observado dos aitmtivas en. cada eta -
pee se puede int.rooucir tr, C\llt1'0 o m!a eiterIJB tiB en ou.el ...
quier ektl pero la oant1d de '1ouJ.os se vuelve uillllame im
pl'lfotiaa y ml\Cho 1114.i SNnde tp.e la del todo de ftmit1ceot611 y a...
oo12en.
sea o 22 tono Ja oa:paci&ad de los camiones (.3zisie
' u:.i iin'3

ro nfin1t o da ,atoe y no hay restriccione::s a.di. cioes)

na ne t:r:tz da di ist:aneiaa ae .11"..uest a continuacin

..--- i

71 f)
? )O z i
r

r. '?_
' 12 2 /O /3 /2
?4 1 J7 '2 /j /'</,
...
11 /tJ f3
. ?-
tJ G 2 ! 3 )() '7 . lf /tJ ,,
- l ll 13 /t e 21' lt.f /J' t
-

? /l
?\") q 2 q %q /( ,,
. ff /( l.
-Is
f

s:>luo16n
~ Y&a-..
..-
1,os ahor11Ca q.ua aqu! s.e usen son loa misnos qua ellll11e& el

elgoriimo de C.li.ll;'kec

1Jtjl 'Vf:/Z. calculedos los -ahat'?os, e e oraa1.an a YO!:.' e me -

nor O<XO.o se apreei.- dee,"'s oon loa m.ayoes e.harrQS se

hace l.aa l)rlllG1'6S rwnitioaciones, o asa, (7,4} y (7,5)41 S.1

tCJll:mos le:1 (7 .,4), los siguientes onl.aces que podemos

ec,ns:!denir son (7,2) y (7,6) (lle ii emn qe deoocb.a,se pu.es

en a:mboe aasos se eobre~sa ltl 08:6cidad de lo a oamionaa-

t:P1- P2- P7- P4- P1 oon 27 ton. de oapaeidad r 1- p6- JJ,

p4.- P oon 24 to de capacidad)
1
Tall8 ul o en c:011secuoncill le otta rema d&l d'rbol (7,5), los

siguien:tee enlaces posibles son ('7.6) y ('7,4tj 0 Si tomamos

!A ru:lia 'P - P - p ... P4- 1'1' au oapacioad (25 ton) ooccoda a

1 5 7
la del oomi6n y esta i.em ea desCl!lrta. oomo las antar:lores.
 61

con el enl.Aca {7 ,6) se f'orma 1.a r1ta P - J.> - P - p - P ou..

J. 5 7 6 l -
ya oecicbd ea 22 ton "J sa-tisfau. l,i rostr'lc(fin de cQrga

Sign'i 911~ la bqueda del .l'boJ.. ten.ews q,u.e tacerlo a 1)3.:- ....

tir <i.e1 nudo (7 ,6) denominado l' e:.i el diag.i.,eua que se pro -

sente mis adelanteo ras siguientes ramificaciones que s.1'.r' -

,
jiln d3 e $"te nodo y que contengan 5, 6 o ? se descartan y
.

con 1os ot:ro.s enlaces se v la posib:Llidad de foxmar nuevas

ruta"
por la a eoMideraeiones antes expuest&EJ1 sl nodo N debe de}!

cartarae y el M origina lA procahl.a JUt& p - p - P .. P oon

l 4 2 l
lS ten o.e csaeidc oontinuano.o con le l.'fJ.mi1'icaci6n de M;

eneontl'6.nlos los enlaces (4.,:3) y (3,2) llSJnados R y sen. el

die.gre.ma, J.oe cueles tornan les l'Utas P. - P - p - P - P

1 2 4 :3 1
oon ZiO ton d0 capaoidad y p - J> - P .... P - p tambi,n con
1 4 2 3 1
30 ton de oaoidad o Qbviamter amtes rt::tas no son factibles

y como no piede Mearse me.a ramificaoione.s, la segunda ru -

ta se ha encontdo y es 1> ..- P - P2- P oon 18 ton de ca:;a

1 4 1
cidedc 1JJ. t61:'C :t"U.ta aei4 aquellq que s61o tisfaoe P
3
en 'Vin je de ia y "Vu.elta o

.41 i_guaJ. qt1e loa otros !Sjon::ploa q._u.ia ea han de~rrollado, el..

reeman de zautaat diste.nejas y ca:ti.s son most,e.das mas ad$-

J,li{l..t5<>

--
Ro I j

15' '7 ' -,s

- ' q
15 '7 '7 -
i lt '7 z
 .
3o8 .ALGORl'lMO
( --------
DE &YESo-
Este elgQ:ri tmc es conel)tuali!tente dierente de todo::: los e.lgorit -

1no.a definidos anterioente que inte11.ta utiliZar las mismas tc

ll;ls decisiones tomada.a po- un des:echado.r humano son tUbjethas

por naturelez y entonces son inlposibles de :reproducir exactamente;

aine:m1:i!rgo 0 se rugie:i:-0 el ai,"Uiente ocecHmiento como una aprorl-

IWci6n razomble :

a) :}?l'Cd.uci:t' un n.&ri0ro de puntos exteriores, es decir puntos loca\

zadoa &n la :periferia del lrf:Jil servida por el ta."'mina.l. El pri

mEmO de stos puntos se ascoje cauo ol cliente quG sst{ l!Ss ala ...
jado del tsnninlllo Escoja ol segundo da loo siguientes clientes

Illdo p.e se tnaxinee al producto ds su distancia el tst"lnil

con. su distencia al :p1"1Ill91 punto ( ste sera, un :punto diametr1

calmante opuesto 4\l :pri:m.ero )o Los puntos sucesivos se escoj&n

de modo de marlll11Za,r al :producto ele le distancie al term1Il61 y

.llJ distancia a todoa loa puntos prmat10nte ooleccionadoa.

b} sal.eccioreir mi ;punto 0:xteridr ::era empezar llffl rut<le

o) coloce.r un oontc1dor ra rede punto no colooedo como WJ:1 combi-

ttic16n lineal de lA s ai8Uientea recter!sticaa t

2"- mme:ro da otros clientes no colocados en su vecindad

3"- la dist2nci!1 entre el punt o:rlGtriat' y el t6"1D.ina1

4c- la dianeia del tEn"Jniml

5o- la dat&ncia el pr6ximo punto Gxteriar n'O C6loulado; y

e.- elemento al<::atorioo

pare. e caro.cte:dstiec.s l,4,5 y 6, cu.en.to lli\yol' os gnit\l.d

ds la caxacter!stic:e :tnayor es l.& adici6n del taIJ el;ldor,,. 1.,0 con,..

 64

trario ocurre para l.es caracter!stic@s 2 y 3 0

d) slecciol'J-;:r el _punto c on al ta.me:1do1mas a:Lto y Bf>ignarlo an

la -ruta bjo oonstruccin si as posibleo

e) recalcular. 1.os acores y rap,tir e cusnd.J se completa una ruta,

esooje::r o tj?d ruta aict::irior par \ 0l!lpezar uta nusvs y s si suces1-

va:mentso
V';lr1oa i-efinam:!.entos a este procedimiento Je sugirieron por Rays

inclu;rendo lf, soluc16n del asnte vio.jera :ai:'l:I cadlll 1'll.ta 0 El mtp...

do se :puede usa.r 1,1a. esolve.l.' lllUY l''1>idmn.en.te l)robleo1\ts c'b?ia -V!,,

ces oon d1far antes val ores del arreglo 1nea torio y finaJ.Jnente se

:ielocciona la rnejo,r da e11tes soluciones Junq:ue la alid.ad. d lae

:rutas p:oducidaS pueden no ser- tan bue.nas eonx, la de los otros

iodos descri toa autariOC'Jilenta; el algori 1r..10 es muy r(pido "f puede

.ser .1ticuJ.amante l'.tU como un elemento do entrada pare proveer

, ,
les rutas factibles al metodo dal a 1 gori t:no optimo-.3o

!fo. e.tieienoia oom.pitecional en los Ellgori tnos dascri toa se compare

por me:iio de la soluci5n de un cierto nmna:ro de problElllls. ptos

detos estn listados an la tabla 3 o l

11Del'O de
Problan1il
Nfuero de
clientes
r1 P.r obl Elil2
or.iginal

l 6 mi.tGI!
z '
13 nantz 1g y RcO:naer
3;4;5 2i;22',29 .
Gaskoll
6 50 Olarke y WC1ght
7 32 skell
8 f() Ohr1stot1des and Eilon
9 '75 tr

"
l'1

lC 100 ti
 65

LO resu.J.teos que se muost:i:iu1 en J.a tabla 5o2 expresa que el nHt

do ;ptimo-3 fu' el roojcr d.e los ex_plol.'E).dc:;,, l!!-1.. m"coo.o .e eiaifica-

ci6n y acotec16n so prob soJawnta J;):ra los probJ.emes 1 y 2 dob_:;.

do a qua el tianpo de comp\1,ttcin y los J'.'dquari.mientos de menioria

del oom,putado:c se tornaron p::::'ohibitivos piN los otros :p:'oblemas 1>

claramente la aticienci canputacional del Etlgori tino ramifica -

oic'Sn y acotac:n cuan.do se :plic.a al problam.a de transpotistea ,

es sustanc:lE! .1Jn,3ut e reducido si se comi;ei-a ccn la soluoi6n de un

pl'ObJ.ema quh'Blente de &gent via jaro,,

:in. e:xamen <la le tabla 3.,,2 nos mues'tl'.'fl que eJ.. m,todo 5ptimo-3 prod2_

ce, rutas qe son haate. 10% 10.enos en longitud (lUe lee l:'UW a produo,1

aes por al m,todo de los ahorros de clarke y wrighte

,Ademis, en tras de un total de 10 prblamas oonsidered os, el n6n<'

-ro de veh!cuJ.oa usados pare proveer a loa clientGa fll.l tembin me-
,
nor n lsa rutas produoi s :por el matodo optimo-3, que en las ru-
I

tas produo1dti.s _por los mtodoo de los !lhol'1'os.

se observa qua ninguno de los m5todoo propuestos por Gask:ell ea

co:naistent001E>nte mjor que el mtodo de c1arke y que la tcr.ce

'heurstica de 'bseda en el. l:rbol usado loo 6.horros , aunque :por

su naturaleza; proa.u.e& mej oreB 1ouJ..tados que al da Clarke, tam. -

bin requiere un Jll)yor tiempo de c-oznputaoi6n y :p.rod.Uc3 resuJ.tados

que _por lo ri1a11oa re les problemas ob,!ldos no a.s tan buono cano

loa r&sU.ltedos del m'to :p timc,...3 s:tnanbargo e mroida qua las

reatricci,ones dl proble se bacan inla y mta restricti<;ft'ls, uno de.

be eaP3ra11 qua el nietoda E se vuelve progvesivamente ms etioiante

y eJ. O progrssiv&Jp9nte menos e1'1oienta; entonces, 1a s conclusiones

anteriores sobre loa todos l)lanteaaoa no .se puedan conside:r de

 67

----------....-------.-- -- --
ALGORl'l'M:o DE cum.m y WRIGill'....
....

Este al.gor1 t:no t:rata de enoontrar rutaa &ptiJD;l a contando con una :flota

de c&Dlionas de ca:p'l o1dad oonocidU ( iguales G diferentes ) , los qe ae

un J1:11'6 entr:r. mro:ider!as ( slnllin113tr os ) des.le un dep6siio can -

t:rsl a un mfuero -..al'1.!:ldo d:1 :puntos de.nana.a.

Se desea distribuir l2!s daD6ndaa en loa oaroiones dG modo cpe toda la

mares dor!e sea s slsrada y la die taucia total recen-ida sea nlnim:l o

4,1 !9:RrolAOION

un %mero de oomiones X de capacidad o ( i = 1,2,,, ,n ) son dispo

-
. 1 1
nible'se IJJS denandes q deben ser re1JE1rtidas a los puntoe p (j = 2,
j j
3,,, ) desde un d ep6aito P .redas las distanoias d entre todos
1
y,z
loa pares de pintos, ae mcasiia minimizar la disuinc:ie total re -

corrida :por los camioneso

En este algoritmo se oonsid91'6 que las repacidades de los carnioms

son iguales, , r= o2-:. .... en y que inicialmente hay' di

, ,
nibles un ID.llllaro i.n:t'inito de estos cemionaso si las 0:1paoia3de.s

fuDran diferentes, se o:rdellin e.n toma descenaan.te ( e i-l< c 1 ,

1=1,2,ooo,n) y ae asume que:

<< J;.1 9:r

Cn 2\ L. a.1:r
'/
puesto que si en la aoluci6n note que e ntonces el
J,
:problenE se reoolve:rl! ce.a.o un pi-oblema de agente via jaro.

Si alguna de las den11ndas ea nayor que la ca.acida,1 <le loa camio -

nas t se asigna lo que @epa en un oami6n y el ,esto confoDnB el

J.ll'.'Oblana de aaig:nac16n dG &aa sobrante en algurae ele las rutas qm

se gena1'8l'ino
4o2 !L-!Q.J']!>,],I.,Q!JJ..R.Jg._,-QJ:3.o ,_
Qonsi&r01.n.oa una posible tiaigrocin de rute sil En todos los

sos qua se presen cooo punto den:tlnda p,.ede ser unido a o,.,

t:ro par de :puntoo aienck:> uno .S ambos el Ol'!gell(i Conside:rancb

los dos puntos antes II1ene1omaoe F Y P , .&,tos :,uadan unirse

y 2
e. p y p rG Gl)eotive.m0nte "! tambi,n :puede calc'.L'at'l el .!
y!l Z:].
:e
footo a.s 1.:r..l \" PY oon z tt.

Sr3 ast.--:n que p y p ae encuent:r--an e11 1:ul:.a aep:1:re.des que pll!_

y z
ten deJ. or!ge $1 ellos se enouelltran en lJ:1 miSJS rute, las

misnes cons1de3'.lciones ea apliosn excepto el ces, moat1'!1dD en

Ti i u t'c .i

7r_,
 69

.; ~

i-t1
1
;;,s c)(o 4 _;
JA f'ig 0 40 1 muestra la posicitn de P y :p de la e s:tgnaci6n faoti-
y z
blo o :r.as t1gs 4o2, 4o3, 4o4 Y 4o5 mues:bl'Eln las OU:\t:L'O posibles

deaoanposieiones a.e 6stas rutas resultantes a.e unir P con p o E&->

y z
tas descomposiciones consisten en las divbrsas fol'mH, en que B-3

pieden unir P P pP con las otre s forllil s en que sa pue -

y.-1 y y Y+l
dan u.nir p p 6 P p tas a1stancias ahorradas p:>r oaa.a um
z ...1 z Z Z+l
de estas d.ee-oOJlllX)siciones se muestre a continnaoion
, :

( 4ol )
dY, v1 - d 1, v1 + d2, ... 1 - d12+1
i I -dy
I

4o2 )
1-1,'f - d1.'1-i * di.it1 - d1,lf - dy,

d Y,Yd d11 Y+-i + di.+ 1 - d, -,

{
- d '(,i 4&3

dy,. , .v -d1.v-1 4 d1,1-1 - d1,i-1 - dy,i 4o4 )

estoa ouatro ahorros so1 calcuJ.adoa J9:re ca.a.a r a.e puntos.

LO mostmdo a.nterionn.en.te ee la uni>n de un punto oualql.el.'6 oon o

tros dos pUntos ta;mbi6 oualquiarao

considerElllOe ahora cpe UnQ asigiaoi6n ftlotible de p y p es &qt-o

Y z
 ?o

lla -en que los otros aoo ;ptUltoa que se uJ1an a ?Y aon el orgen y

lo mi-amo su:p')llGm.Os t12ira P , aen a mm stra on la fig 40 6 "

z

~ o ,?
.

l-?,-l ~
, ~
~~

distancia rotal recorrida en ambas rutas aar :

1)1 :a 21-ld 1 <4t 2ird.z, l { 4-5 )

Y:

Si unimos ahoi-a P oon P , tena:nos lo siguiente t

y z

F1gc 4.7

siendo la d,tanoia total reoori:ida pare este oaso

D2 -: ( 4.6 )

El ahorro producido al hacar la ulli6n l? con P seri. de e.cuerdo a

y z
1a s cio.nes (4.5') y ( 4o 5)

5 v "i. "# 1>1 -- v2

1J

-= t d't, t +'l. di.,.1 - J..1 - di d.,1

( '7 )
 '71

qw.J :uesul.te.n do mur dos puntos con 1 cnf.gen y S$ a:nplea tamb:n

tos datos que se neeaitan pa:re Qte problema son i

1dentific.a.oi6n de loa puntos dananda ( x 2,3,o" :n )

p t>rgen
l
Q. ~na.~ d~l pun.to 1. ( 1:: 2,5, ,e rn )
1
opaoid:l d de los camiones
1
dij distancia oosto entre P.1 '1 l'
j
t !nd.ioe qua indica la uni6n d los to P y en 'lllla ruta
y,z Y -
( otflndo 6sts vaiabla tim velar 1 signitioe qua los pun,_ -

toa se mn oonaotado; si tieno vsl.or o > significa qua no

lllY conexin y si t il e 2 , aignif'ioal:1 que ol pun

Y,l
to P se ha conectado oon 1 orgGll )
Y
31 los oamione tub1ere. 01.aaa diferente un buen criterio para

.llLl4r en orden descendeut

Bl proceso oonsiats en lo siguiente ,

_ _l .- Qe10Ular los ahorros ro todas las um.onas de d.o.s PU;!!.

tos. usando la acuaoitn ( 4" 7) tt

l>.A.SO 2 .- &signa-' un otam.io da la menor <ax:.eidad a oaaa :punto

"'(,__,_,_._

dEl!flndiil e inicielizar la. natriZ "lnAl."Gado de rutaaft t1.1 ( um eZ:-

p11oao1n s detallad.e se presenta @11 el oap"' V en el paso 3 del

;procedinrl. ento }o.

3
00 ,.,.,,__
"-- ci- se eaooge el enlace que proporciona el 'fJSSyor ehorro

eiem3}'e y cuando la s\U3 da le a aaJ;eoid.ad.es aa estos puntoe see

meno qua la cE.IJ&cidtl d dGL oanu.6n. Si oum.3?la cfum y a l)Osibles

 72

rastruoiones que puedan habe.rr 1.os pu:itos escogidos -tomaran :pa:i'

te da una :ru.ii!\ y se actualiza ia niatriz 1t.ineircado de :eutas" o

__ 4 o- Se. busce los enle o..

PAS'.>___,

4o8 )

qua pueden w.lli1ra1;; a l ru,ta inioi.81 sta Bltisfacar 1e mcee1 -

dad del cem.ic)n11 !Ps Qn1.&c.as que no cu.m.:plan con. cualq_uia-e. de la e

oondioionea del problmt1 qued.Q.n ma.rginados P,J:El usos f't:rtul'Qs.

Si ya no ea puede envit.u. m.!s oa el OQm.in se ha encont do

la primare ruta soluo16n. Se actualiza la lllatri.Z. mar<E ao de .rutas

y aaignaci6n e tlota ter.minando de asta me.D.Gl'a unl ital'8oi6no

Se regresa l P3 so 3 y sa repite este proceso hasta que no mas enl!.

o ae oum:plen con las restriooionas.

ouando ee llega a asta .vec..te en la soluc1tn del p:roblana, lotJ pun -

tos que no hayan intervellid en n1.l:lg'Um de las :rut.e s se oonaida?Bn

ra ew a&t:ls.f&Cbos en tol.'!lla 1naapt-nd1ente, os, se esig:oa un O!.

m16'n epa i,e y viene a cada punto entes mamionado, comJ eyendo as

Tananos como datos la matriz de crd.atanciea de tebla 4.1 y JJie ....

ce:t1:1cter!sticas de la i'lnta da la tabla 4,,

 73

'n
1
J
cQ
/JOo iq
l
?z
[ /700 rt
l. itI!
!
7-.
I!
/500 l 'l 4' lf
1
/f_ !,r ;

/<;oo 12. 2> ,,

1
2,t 20 11/.
f ""
?,
1
/1}00 l. 2l1.fo 21 f} ll.z 21 2."" I t
' 2.i1-5
1

ffloo -- 2 lo lJ -,sq ~
1
10 30 '.

-
/2.C>O ' z lf()
1
., ,26 1' !,O l[ .
!I .t.O o t1 ; ?f
vo t.o l'1 ro }/ [! t-o ?
:

/90r.? l.. 3,
1
l
3lJlO Y/ 'J4 ,J
' 1 1 1
i l ?o
1
//()()
2 31 IO ?, 16 3(,, 14 i/3 12.o .. 11 J;. [Q /; 16

" , ,, /fJ 'll ' 1,1

1

l
1
1
flll IIJ // .20 3'- 3(. 31
3', 'f'f 1.0 tt ?,1

l?oo 1 5o o
l
t,i1b ,e. ] 4l J4 ,; a [IJ V )2 JI. 7' A. !f g ti

' J, lbr2 /.i ?1 l

l
J

/,e,o .
/tJ 5111;.o I.Jb JJ i(t 19 YY 1(b
! l ;r'
1
272 ,, t 1

--
<APA9.,1.11
e 1.f:\
"' 500() 6CKJO
sit)Ml8IL M-4
i(G,44 oO 3 4
#ISN/,4..11.i) IZ o o

ie resolvEU" este p.,b1..saa, tenemos que calcular p:-ime1'lnlsm;e los

ahonos an.pleendo la acuaci11, (4.'i)o ]lstoa sa han colocado en el

lado izquierdo da lfs caailles de la nst:;:,iZ da distencias0

par ejam:l)l xe los puntos p y i el 'i!horoo estar{:) dado po:i.,

3 5
8s z di:: 1 d3 t 1 - 3
I V' j
 :.- 2Z + 14 - 17

y a.s sucasivsmento J.'6 lo de.da puntos.,

!J.:' natriz ril6.reqdo de rutae in1e1alnrinte rupone un. ce.mino a cada

lolid.ed en rutas de 1de y vu ta de !1111 e.l n6mero 2 que a:i;ia-

reo en la ce, J ele ,, en lP tabJ.e 4o3 :o,

1
Escogemos el (I-"-'i.ac PJZ que nos pro:porcionia el lll!.Yat.' ahoro
12

( ' 12 z:i y como Ja sooi de :tas de.i:.'l.8ns { .':

J..
y tl.2 es 2,800

cantidad que as ID.f..AOJ':' que la. ca:peciclad m:rll'na de oamiom a gua

6,000 'J. onGe, tenenos qie le primsre l"l.1.t estll' si.nindo oon:fOJ!lll&\

& ?,
/200 2 ?i
---2-
/IJCJO ?1
,....._, ----.... .
--,
/[04 2 ?q
?r- i
!-----11---+--t--t---l-- - -
1lfoo 2.
-r:)or:,
- -
/'IDO 2.
......;.___

l
()!
2

--
->--

---,...._ - -
1
1 - -1-+--
' 1
?, .....
?'}
?a
_
-- -- --
f....//O

- .,_2__
-Pw'I
1
- - - -- -
-~

-?.
1
i-, -
l8ou 7. .?,-
1
' 1

#Or;
l.
f'FXJ
.L

z. __,_.__,__J___ !_ __
\__,.____.
.l/QO
.
-

__ ?. j
-
-- -- -

1
-
~J+_
--

1 l.

1 !
 75

De -0cua1,ao e las ecu&c1oms {308) y (3 u 9) $ vemcs que h':\y dos enle-

ces que mm:ple n co.n. la 1est:d ccin d cajfal o:lila . y- cai10 sus ehorr:c ,]

son iguales iS 3 -=-84 y 8 -;; 84) escobemos de .stasft el par

1 , U 12, ll
, o E::
que tenga la menor distancio. {d
12 1 11
ilOO Y- a 13, J,;i. '#104}

p . ; s iend::, hol.10. la cargA total de 4, 400 galone-se-

12, U
OoJJo a la ?ttt/vz:;. inicial se ha Ogl!leglldo al pun m Wu te nemea.- ceno -

nuevt:1 ruia .} -$t - }? p, .... p y debemos bu::. aql.loe ahorros

1 13 ll 1
en donde intenenn F !3 Y)t u ya que, :]k .. ,\ ,ar ser un punto a w)

est ocnec"'..,!;ldo al orlgent no debe tatJlrse ,;,Jl cuent4 ,a evitar qJ.e

la ruta :pueda rompersee,

Siau!e.ndo con el a.wlisis de loa ilhoITos VEllloa que, s13 , 9

Y 81,(
9
son igualas rtimm el valor 72) y si tomamos el que tenga :t.enor

di.s tanoia (d .. 84) y agrega.moa 9 a la ca:r-ga total de lA 1'1!ca

ll , 9
{1,900 ...,.4,4006,300); notamos que se sobrepasa la 0!3pcidd del

oom.t.n en estudio (6;000 galones)., Siguiendo J.a bl!squeda de ao -

rros mnmoa qua a au vez satiafa.g;n la restricci6n de 0:11>8cilad ,

an.cont,;'1ltnos OJ mo enlace posible 8:J..i , lo q_ue nos :permite 1a 14\1

, 8

l\- P
15
- t>12- P -l9'8-11
11
coh una cerge de 5, 500 galones (1,.J-0)

_.. l,"lOO + l, <'00 .... 1,200) y una di atancie total de 1.12- unidades (52

-! 10 to 8 of. lO t 32)

Si 1e cid.ad dai (l@lm16n permi tiel.a ag:regQr al.gtin punto rris s ll

ruta, el siguiente i:ia ao ser12. nular filas y columna a 12 y ll y

bien al eho!"ro (13, aj a f1 n de eviter. t;ua los puntos qn.e confomtan

esta rute sean co nsiderad.-:s llU3 vanunte en l b''.aqua&:l

oomo por los va lores de las darnan&s no es posibl.e Sfltisfa-;<lr ningt{n

punto '!Jls (el maio1, valor ea -:- 1,200 y lo que le :f.tl1:ta la ruta
2
Q

prAle eo.111r l& oeidad dal C.'lmiln as 4tO geJ.oneitl lJs encontrado
 7t3

la prilare ruta ooluc16n del 1>roblo

4, donde loa aubindics A signifio&ll qua se t:reIa de la ,:cl.meJ..16.

rtrt.a 03. o, et s:4snif'i oarn :?As ruta a sucesivas qua se formt7':

()amo ya hanos encontmdo um ruta, el s:tgi:.:.eute ::aso consista c,n

anular til&s y oolu.mtlia da loa :puntea qU.e confoli'Oi.n esta ruta y

oon loa hor.ros ras~ttea se z,epita ~ pr oc e:.;io.

JE. 6horro ; ., -: 68 P3mi te inioi4 lizar ;"', NJ:'im6-"fi ruta ya qu.3 :

9

y sUDEn 3,7.00 g:loma que cuxm_,len ,,Jn Ja restrtcci6n de

,aoidad, t9llisndo antonce lEl ruta 11 -p ...

1 lo
1/g 1>1.. Sigteno:> la
bsquede. Vfln.OB e El eigu1ente b.Qrro l)Osibl,3 es a siendo
9, 7
ahOl.'i ruta !) - P. - 1! - i,, -1\ con o1(}a d tot6 l de 5, lO
1 7 9 lQ
galones y una 11. stancia -tntal de 80 unidades (en. la -tabla 4i 4 sta

mita. se enouentra marcada oon el aubnd1c(:) B)

C,Omo no i,uade aatist'acersa otra dnda segunda ruta queda con-

f<1'DSda can.o se ha expresado &es y deban.os anular Eiho.re los pun ,_

toa que 1: oo nfo:um.n.

De los ahorros rootantea vamos epa e5 4

nos JBnllit& anix3za:r con la
1

teroa1.1l ruta t, - "'$

1 4 -e5- p1)a e;ttlo la capaoic"tid tcta.l tg.101 a

2, galones.,. ReJ,it iaxdo e.l pro ceso s egui o con la e ruta a a nt et' io -
res, epreoiamos qu:e le ruta sa oxt1da a P oon
1 Fs--P4-: F0 1-:-:-
una oapacictad total de 4,500 s,1lones y aespu&e de co.ntinw.r la bfis-.

que&l llegamos a la :ruta P -

1
-e.,- l"3- P.4- p5- 1>1. con UJjl
Q
oa:pa cidad -

total de 5;ero galones y ci.r cltshacia 1intal de B4 uni<ll.des, que es

la teree1"6 rt aoluci6n {C en tabla 4.4)

Despooa da mm.l&r los ahori-os re.speoti'li'OS de la tl 4c1 a:pre.cia

mos qua s6lo M quadaao eJ_ ce (6.,1) ]POr lo qu.G, :?:i. _;;io.nto e do-
vax:l BE!r.' (E:J1gua49 en ruta de ida y vualt ?1- $.\3 1) con wa

oida d do l.,' ga loaoo y una di sta,nei (i ,4 ttnide (lee ( en la. ta1)'.i.a

4.4 e.,areee con el su'b-r..dice D)

Rabiehdo llegado el t,imino dQ la l!Oluc16n del problsna, las te".:-J,.s

<el1 y 4-6 mu.estmn e 1 1"'68'.llllen :t.' iall del piobla..

JQ 1i
%ro 1C rt l
-
,e. rs
1l. ?)
5 -
[if)O 1e
roo {!) ?,
5100 10 ?,
5iDC 1 fs
jo - 1i ?'
5/!YO 13 1E ?.\)
.- .1
r,---- :?,._
-
A
:-"
1
.
6'" 1A
,, l
l
.......
1A 11l
1

"'S&.Oe 1 !
'

<A?'t:IP. 1 5"tJOC '

,
{)P. Rt-4 c,,O 3 4
1-= Z7U../P<JN o o
2 t?/lMION o eJ 2
]! 1n:/l.6Q CtV o o 3
,1 fl(i/JC,,()V tJ

bla 4.5
 78

--. l? (,/ r A -
e:; 1 )._,- t
ViC I ) 1 e f"< ci
.T
/-?t,-1;'!; - r/2 - ?s-?. //2
!1
1 56C>V
?; - 0- 7q -7,0 - ?, to 1 S/oo 1

7;7t ? -,;, .. ? .. {),

'

. 5"4 5[300

1 4c/ 11100
?
?, .. fl- 17
2qo
'--

l 011no; 1o-l!: 1

be recordar que cuaro um ruta 0st.i conrorna. por 'lf'ls de dos

puncos, por ej an.J;llo: :,,1-11 -

2
tt3- p4 P1 (s'.n consilerer :por Su.p.18!_

to 1? qUG a.B al Oldgan) ,. el .siguiente punto qus &a amdo a la ru

1
ta, d fgamos '!' 8610 pus da ingreall' por '1?
2
.6
i\ '3 no par p , pues e.[
3
5
tar.a ffrQlI4.)ienao- ru. esta.b1oo1da9

4-5 ll[!WlP NOMi!ID:CJf:>?-

En esta ejs:qplo aa Uene <it!MDO datos .lli erlai.enda de un. ndmaro 1nfi

nito de oemioma de 8 ton. de oe,,eo1aaa; no a:xiste ninguna reitri<>-

ci8n de Ml y ni otro ti,po de :raatricci6n &di ciol. m
llt\triz de distanoias se muestra en. la tabla 4.7.

solue!Gn.-

Aralizando la tabla 4.7, notamos que e 1 enJ.l;loa que J)annite el meyor

,
ahorro ea 3 qua tiene un valor de '?Jl. sumamo :tas dEm:lnc}le da

los puntos eaoo gi<b.s da 7.2 ton. qua satice la rostriec1n de t'!.
;;scidad da remiones e inuluso hay Uh JDrgen da Oo,8 to11. que pueden

&9tis3ioet"se en sta 1.v.., Da .ltl s danandoe que tiensn valores que

como nlxim'J sea OeB tone, en.rosen d.oa tp y j que reducen el

9 ll

de b1wque<ll del na abo., El aie.nte Qhom>o a oons1dezaJ:t es

l' por lo 1ue ;tl ruta. a <ll:lora l? - p_ .." J? :P - P con u c:1pa-
9 ,3 l Ll 9 l
o:toad de 7.,f, vllc y dista nc:ta do { 1;:; ,r 3 + 23 + :tl 'l 50 kmo
OOrao n.o ms puntos iued\;)n satisfacerse hemos ancontrado lli prime1-a

ru.t &ol,uoi6n ae:i. :p:ooblsma o

ADllJ..arulo las 1:'ila.s y oolmm.:ias d los l)\Ultos pertici;antes ds la

primera ruta ::1.ucont:raoia, notemos ttu0 al. siguiente mayor a.horro as

l8 que oorr2.1po...a.a a.l enla 1e (10 i, ), pudlando lnicializsr ,ata sc.r

gunda ?'Uta LViJllO p - J:l "" }? ,- l> 0011 Ull?. H:p1 Oid de 4 tone
1 10 8 l
OOnsiclaran.do 1 crHe:ci.o de ir satiafaciando las amandaa s !

des, tenemos qua d.ecidh-noa por Q. cuyo valor es l-t.-3 to14,. y deba -
6
moa anali'Zal" los eho-os a .... y s para d9term.ir por qua
--:i.v, 6 8,6
extrano da lA ruta debe ane:xa:rss p tt I,uago del anlisis i-esi,eot1 -

vo nos aecidirucs por (8,6) siendo ahora J.@. ruta :e - P - :P -
- 10 8 6
:e,-
:e cuya capaoicla.d as ?c.7 to11qe l'Uesto que no se :puedo am;xar ttia
1
1>untos a :c\J:ta }' hemos encotttdo 1a segunde mta aolucin sien -

do la distancia recorricla en ,ata ruta 41 lmlo

t.uego . de en\llar rua s y ools :reeti'Vas, el siguiente llley"or

ahorro :posibl.a as (ll. 1 ?) ( ouyo vsior ea 5 ) Fed@do esta nua\18

ruta oomo P ... P - 1! - P. con 6.3 tono de oe cicla de El siguiente

1 ll '1 1
ahorro qu.e p.9r.mi:bo as S'i tiat"an la.a rest:rciones del pl'Obl$M ea

l?(7 ,4) y lcl nu :ruta es l' - P -.:e ... P - 1:1 y JA nueva oapaciOlild
l l.1 r/ 4 1
es 7.,3 ton.:, El ,'1nioo punto posible de eoneidat-a:r: es pn cuya de-
Q
..,
inanda es 0.6 ton y aij na:xa a la l'-1.te por '.'? ssg&. l.oe ahorros
4
1 oomo t6TC r11ta t ema"!\Os tit1'.J..men'te.. J? - i - :e - :i - p - p
1 ]J. 7 4 2 1
eon 7i>9 tollc> de cq,pacidl y { 6 1' e + 1 f 15 + 18 ) 46 lo:n.- de ats--

tanci~ :reclOITida.,

tP Jmtr:lz 'fizr~l ~2.~ca.ao d':l .ruta.S1' y Gl ras<ken de J.Ji:3 r\t"..a11 f:L;s-

l se muestran a oontiweci6l1et
 82

E.1e elgorit)no al igual qui, el d.a ,C,1-r.JY W'r1ght ,_ tzat.a de enco.ntJ:1aJ;

1aw l.'Utae pt1.nae que UbEt tic.ta de camiones tiene que :rocox-rer i:ara ni...

nj,Ji:lZar u.m func:l.tn. objetiw que J?U&d.e ser costos $ disten()ia.s, satis!!_

oilnlo le.a reatrioo:i.:rnee <pe tGnga el problem .,

ta ditarencla pr.:i.mo1.d5Al eutra oste al..goi tmo y ol. do Olarko iefJ.1,oa en

el or1tar1o de mirar hsoia adel&nteo Este crite:ric an el algoritmo de

TUlxnan e8t 1ntilwmente lie,.do a otro llamado 1tn.fuero de uniones .- que

1nd10fJ el DJxtmo n&nero de l)Untos dEII8nda que puoo. en ser eatie:rall.os

oon el oam16'n de mayor capacidad .fas{ por ejemplo t oi la oapacid

de oam.tones de t.u:ll tlota i'Uel."B da 10,000 Wlids.des y lAl s demu1da s

en den Qaoendente tuera P '!S"l,500, P 1,500 ,, P .s. 2,_ 500, p -.3,000,

2 3 4 5
P s,ooo, P ._ s,ooo 1.Url.dea; lo ili:dmo qua :IX>drEUnos satisface%' en u.-
6 7
D3. 1'\lta { de ()umplir add.s con lAa restriocionaa del roblem ) aarla
P - 1> - P - P qa req,tiim."en me dttnaD& de s,500 unidades. ]:llto a1gn.1
-
2 3 4: 5
tioa que 1,lOS hacer unionsa de baste. 4 pmtoa o eee,
tres ')I\lacea

y en la solno16n del p:roblena si tamamoa le dooiain da tra'til jat" con

los tJ& a enlaeea deb&lOOS bur to<'la.s laa :pos1b1li&ldalil dG abonos to,"t.!.

les con este ro <le enlaces ( Itiiyor explioaciGn de ahorro total

ea hace m1s adelana ).:sz. oo.w heoho d3 hacer los O.oUlos da ehorroa

totales ,a oa ruta reprosanta un ti&?npo oousidaraole en la oompu:te

do que :puedo ser redl\oido si oonsideramoa aolament a doe el n&iat"o de

uniones qu.e Vf:ln a ser estudiado&o ES naca3ll'1o tantbin manoio;i:, que

ouando al problema oreoe en.xmgnitud ( ante at nime:t"'<> d.o puntos de -

gin.da ) , el oitai:i.o de s()lo aoa unio :puede ser aumentado a tres,

o\at, ete, sein sean. lE:a neaesi&=idas del uauarioc,, Ob'i'iElm.ente un or_!.
 83

,et'io d.e sblo <'lo s union.ea _l'=l1."'e \lll :proble~ g!e );)de :poch'fu da ,:l'J)s ~a
fiG UJt3 ClJ>t i.1ll!ll il.ellt lila DO '.!;\o

s V'():rieble 001pleadas e la ,01.16u <is aS'W algori imo a sl. como

loa aos a sir ( &111.idos e. eje1>lo il'llat:rativo ) se mu.ea-

n s mfiueo (i.a pt:ntoa da114nd.a

F &- l)'Ull.told danat.a.a ( i,:: 2 ) 3,H,n)

& 02:ut:1.a.a.a rclCJ.rila en aJ. punto arua naa y

\
G , oa,paoidsd d1: loa oar.:ione.s

d. , distancia entre loa puntoe dermn<l:\ y,z

y,z
t i lldioe da matriz m;z,cado di:> rucas crie indica le WJ.itn
:v,z
de los puntos y.,:a

t ind.ica qu.e e1. p\ll'.lto ? ae ha onectf\do eon l tamimll l'

,.1 Y l
t #1 indice. que
los punto p y p se h&n oonecia do
y,_ z 4 Y z
t $-()a indica no conexin da los puntos
"! ,.z

oo:r c.eclmd a ceas p:mto o.Etn&ncm oomo 11arroal?Xlent$ no ll&y d1BBs1!_

dos oem1onse j;ilra ba ce,.- e, se ,Stllll3 que erlstan. ctunionas dioio

nalaa diSl)Onibls; &ato s oomionea adicionales son llatados "C&.nio -

n.es l)Oizoa 'Y sus apacioacles 11oapao1aades :postizas" q_u.e se ton

{ seg(ui_ se lJlEltlC:lO ntas ) como las dQ loe ct3J:lrl.ones de J:ilenor oe

o:f.<'13.do

;r ir
plica a continUf.(oio.n

=---- -
:EAOO 1,,... ]J$tc .IU"imel" naso conaiste e.ll .nacer identifioa,bles loci PJ.l.k-

to1;1 dwan.oa l:1 ( Y:::.. 2i> 9'Q,n )('; Ta:ml:lis!i. se {'!Sume qua al te.rm.11 es
 84

el punto J? pues an progltlD)l3.'l'Zi6n no se puede bs ja:r oon subfn.d.1-

1
ce cero que es como se la denomina al dep5ai1.lrJ ce nt:ral en la l:i.te.-

ratu a;d.stent

PAOO 2.- En e1. prooellO oompu.1ill c1ona1 consista en la asig ci6n de

<lllmiones pz,::a los puntos dt;JlBn4a. se asU.me qua ( oo:mo se mencion6

en el pred"mbu..1..o de este O!lptulo ) los Wloraa de las denan&a

requerida a son tales qua u:1)3 f:l sig oin fu.i uh ca.ndtn a ce da punto

es pos:tblSQ
Bi una iris dem:andaa ron 'f!s gl.t!ndes que la nif:x:1.ma oap11cidlad de

oemion&e tEllllbi,n sa puede hacer uir. aeignacn dividiendo este pe,-

80 mayor en dos 6 tas rtes que puedan ser t:raWJportll&ts :por los

oamionea de. mayQr capacidad y el resto en otro de mm.or <>epaoidad.

J?or consiguiente, todos los pGsos oonaia.eraaoa cm el. probl pue

den cumplir oon \ par,.:1 todo

x
y, siendo o
:x:
la et1:4oidad mi
de loa camioni:;iao

ditioultad obvia ocurra oUQndo no hay sut'ioientea oamion.es di&-

l)Oniblew p:ira esignar t.1n cemi5n a oeda punto, siendo rs:nediada es -

ta situaoitn oon la asunoi&n de los entes menoiomdoa noamionea I>O!.

t1Zost' y sus nea:eo1<\l.dee postizas".

otra d1f'1ou1ta d. tam'bi6n pued e ocurrir ouando tsnenos cmnionea en

exoeso pa2'6 ae usados en e asig:iiacitn inioial, pies fllgunoa oe -

mio.nea 1tgrendestt a lQ mejor han sido decidido s ra tranSl)Ortar pe

sos peuqeos. un mejor uso d.e ,stos aam.iorfJs ,9r!a camb1l:l3r pesoa

de IIB-yores oon mnorea cantidades pa,..e logl'er una -mjor M.etr1bu -

ci6n de lJl a dndas.

,A.d.s, loa oamionaa a eigD.Eldos inioitllmante aon rea siglfl doa despa

de ceda 1tert:ic16n, aien:ao ,complete.da Uill. iterecitn cuindo se enG:xa,

un punto a um ruta ya atlstonte 6 cuando se oonaidara u n enlace

 85

pal'fl f-oi1Jli3r w:a nuEJVe rute.,

(Jo.ua1derelll06 1 siguiB.nt;e ejau;pl() que llO SeJ:ViJ' dG iJ.ug!; Oi()ll.

r
1

fi .
I1
ry 2
.,-\,,
.......
,
' _, J 38
- - '

!
P3 :q 2 q r 3f
------,
-P4 8 2 lll]t :u 6J ,3'
:-.-
-
61lf.t Tff.g
.1
--..
l j--"I.:,
'{ e 22 7d/ 11
?6 6 Q 64 ,b'1 j 1/XJ 20 l)j
1

?r s
-

2 golf56 62 &'/ e -.,:, tf WI 2?

l
1
' 4f

/2
. '
[ ctf>i.\C! 1 'PA} j
1'#1?_ lti 11111. ! 18 Yon_
1
.01'5?()/Jt&t( t'M i) 2 I I
PIS?f;!.//t,./L. ( bA i) 1
A5JMi).M. :x) 1 I /
1
,/, )lAC!i).N
.Jll/'C./.A( 6 Q ()

W. :p:rooaao de aa1gieo1tn de camionaa es c:>omo sigue ;

a.,- ooloooi.- las oap;; cid.es de los camiones en fOt"m creciente.:-

be- oeda damandl es n:signida al cam.io.n da memr OOJ;Jacid.ad isi-e SR

t:t'na:portaaa.,. :ta rsasigntc16n da camiones ocurre an al :paso 9

y se canpleta uro itereci6n del aJ.goritmor.

----
PAOO 3.,- se oalcu.la la matw:tzde ahorros anpleando .la aouae16n
 86

el l8do iZq).lierdo de las casilla-a. Puesto que le lI1' triz. de distan

cias ea etl'ioa ae usa s$lo la mitad de l.a m.ia.n:la pa la aolu -

c16n d.al oblsnae Duxnn.ixendo UIJa celda cualquiera de 1s) matriz

p , aignificarl la d'S.&UlMie. tre P y .P en la tabla 5.l

1, j 1 j
Del ejemplo, pare los puntos P y , tmos lo siguiente i
2 3
d
o
Ah rro %.-3 7
d2,i- 3, 1- 3,2

38f 42--35

45

I,Os ehottos rasta::tes ae calculan de la misma :f'o1ma y es neoe -

rio tener en cuenta las restricciones qu.e existen IOJ.'e dee091'tar

los enlaces. que no las oumpl..Qn de 111.tuJ:aa cG.Dsideraoiones.

la tabla 5ol se ha agregado ooltl!IX8 oon los valol."118 ct1 ,_; .,2;
3"uouon; que son loa pesCX!J requ0ridoa pOr OS.da punto dEl!'.lan.dao

Considerendo el vectm- Q con ai a -val.ores i-espectivoa y ot:rs mQ. -

triz "Xlllrcedo da ruta oon celclia t a! que puede tanar valora<:1

i,
o, l y 2 seg se explic.6 e.ntGriom.ante, se inicializa ata cona.!_

de11ido en la asigl:son inicial de Oatlionaa oon loa -valores t "%

1,l
2 oomo se Illllestra en. la tabla 5o.3 o

1'l asignaoitn inioial.. de oamionaa disoutidA en el paao 2 ( lll08t

aa. en la table 5.a ) aignific,a m el. ejemplo- que b8' disponibles

inicialmento 4 ae.m.1one.a, si en.do 2 de ellos de 12- unida dea, uno de

15 y al otro de 1 se ll& haoho wa sigrs oi6n inicial da 6 oaraio

nsa ele 12 unidaa de <ia.l)EI oidad f aqu! es tWnde hl oemos uao de los

aamiones postios ) e,

4c..- puesto que ce da pt.mto a.ame nda s61o :puede ser unido e o -

tras dos puntos ( pudiendo a uno de allos al t _El"milill j, la si -

fiente rslaoin debe oumplirse :

 87

o aea ,. ei sumamos los i;Q lo:ree ie la fila le y los -t

t de la
krz Y' k
oo1'tltllla k, el rew.1:te do aiilllpr. ed L Oua.n,do los coefloientea dEt

la matriZ fiJlfl:t>oado de rutaa" 12.l'1ln '-";lljustando de acuardo e oc,..:

I progrese le rolucin ht p:roblQlla; los vclol!'S s de los t .u va.rf. - '7

y.,
axin y J,a e:r,p.--:oesi6n ante.ri llJ.'OpOO!olora un mModo de@ rooordar a&-

mo laa ru:ls oon gen.eiadaa ,al! al algori~

I>.bSO 5Q-" 80 haoe un enaeyo de l.oa pnntou cp:a tengE1n el mayo

ehon-oo I.A ij.pJ;'O:dna ci6n US'lda Ji>Ol!' Ol&l'ke y Wl"igh.t. ee pa aelaoci

nar el all.orro nas granda y ooneo:r &t:IOQ dos puntos. Til.l.t:Jln, ede

m!a da un primer en.laca tamb.16n vo la posib111da<l do buaoar un 83-

gundo, un toero etc. enlaces da acuerdo &l temafio del problema,

etev. Ar,:.t.es de decidir la un.it:n Q.e dos puntos, &l paso 6 debe oum-

plira

l!l odo uaa.do en este paao pare l.& ealec.ai6n de los puntoa. a unir

ee, ajetofl a 11:1 s c9Iidic1o.ues antes l!lencioDldaa ee

ao.... oop.eidax"e,r la ofiil&l QOn el 1"xwo ahorro ( tuot$.ble de unirse}

y oonaidsre.r- quo &ate ,a;;, da puntos se um ( an el ajfJil.)lo, .Sa

to Vl\lor as p :: l> ).

-
i,j 5;4
'b.,- l)t, las el&! a :restantes doa,u6s del p;t so a sin considarer las

uniones que contengan mb!ndices 1 j, eleg;tr al siguiente ma-

Y')r $horro que es flactib los ahorr-os de los caeos!. y

-
b.

OQ- seguimos eon al segundo .tlt:!yor eho:r.,ro y va?J1oa la posi.billc!a d de

haoe:r el enlaoa ( a am;,irnae qua se puede :pe~ o!'ectoa de ls ex ....

plioocitn )

a.- De los eho:i.ros q.e q_ued!:l,n aes.:i,u.6s del pa oo 0 1 busoornoe uno ua

 88

sea otible pudiendo s'9r un.o de los ho1oroa de los pasos e y be

@.lliln!los los ilho:rros e y 41.

ea- lll proceao se repite l61'6 &l. torcer mayor ahorro y e si suoesi-
wmente he.su. qu,e t.odo.s los poaible111 ahrros l:myan sido inva&-

tige.doao un buen oite:rio para evitar haoer l.os 'loUlos que

se mne.stx'iin sn la tabla 4 es el de :pa:rar oua ndo el segundo

enlaoa que oonf'o el prill:ter ehoio total e,9 primero en con-

f'orrua:r cualquier otro ahorro total pu0s es en los primeros e-

hor.ros totales donde se enentra el mayor.da todos.

-Pi Q
?2 r 2
l
"j)-i. 2 1

,
' .) 1

?4 8 4
l

7'5 r.
'?6 6
1
1
- .,

J
1
1
1 s i
1 '2 !

i

UNl()N 1 A#il6 {JA/1(),V ? .A. flt/i.R .Hr)R.l.

,()7.,6{.

i - /O 1 1 - (3 81 183
- 98 - (2_ '/2 /7
i- .?4
. 1
i. (3 8 /Oo 183
7' - ?j --
?9 i-2, '74 153
?r..,, - /'J'
?e;. - ?2
Pr _ i}
174
72
65 .-
-?3
'?($ - ')
i-?5
r79
oe
cg

./63
-
1
l. 1 (
 (6 -
?z 64 lt./. 17
\

ri} - (3 3
- V 477 f6 - f4 /o() F-1?
-r 45 - J l I O() 1415

Tabln 5.4 Ahor:cos 'totales pera la prmeN

1teroo1n

De estos aro1.Toa to-tales ae escoge el lltlyor y los enlaces corres -

pondientoo s 6ste a.ho. originan las l.os primeras rutas ftlot1'bl.ee

dal problema

n el paro 5 en el ejemplo tenErllOa i

- llJ. n1'xinio aborro posibl.e es 100 que reaute de p oon p

6 4
y si O'UX!lplen con las restricciones del problellli tonmrn le

rut& P. - P - p - p con uw d1stanoia total de 140 unidades 0

1 IS 4 l
be- E'L si8uienm mayor aho rro posible ein oonside.rar los enlaces

O".tt que prtiotpa.n los puntos p

6
y P
es 85 que re.au.lta de
.
un1:
4
p oon p , fol."m:uxlo de ser f'aot:tble ll!I 1'\l:ta P. - P - f - l? con
5 3 1 5 3 1
UJl!:\ distancia tot-al de J.2.7 unidades. Sllnenio &atoe dos abol.'ros

tenemos colllQ flhorro "'tol 185.

o.- Sin oon.aid l,.oe 61llaoea d.e los ahori:oa inioit;lles, aegw.xnoa

oon el siguion:to ne yor ahor.ro tau.e es 98 001".r&apona.iente e P5

oon l? , dando or!gen. a le. rute l> - 5 - P - P con 156 unides

6 1 e 1
de distancia.

d0- sigui ante ayo:r shor.r9 ( sin cnsierar , ni p ) ea 72 de

5 6
unir p
4
:r P2 , ol'i.g.Ln3.l:Uio si los unimos ( de ser raotible J?O

su.puesto ) la rute. P - P - P - P oon ll6 uni<\ld.aa de aisten.oie

l 4 2 l
y un ahor:ro total ele .l?o.

ao- Bepitiendo el proceso xnostrado para aa uno de loa ahorroa sJ...

 guiantes i los respectivos ahorros tota1es son obtenidos y moa-

--
ro
P.l... 61,V... JJ)a p\Uitos sal.eociomds a:re. ser unidos de acuerdo al

paso 51 aon analizados pare ver s1 las restricciones c:lnotadas ini -

oialmQnta aon tiaf'eollil S1. 61 _par da puntos oon P y P tena:noa

y z
l.o- si los '1i1.:llcres t ,, y t ;, son mayoree que. ce.ro loa puntos P
Y,1 z 1 y
y p se t111m al or:gan y ae dacide JA. uni6n entre ellos.,
1

z
a.- LPa un:os > y I> l e van a ane:lf.l:raa ' ruta e toDSr
y z
una nuev.a ) oual:ldo lJ:\ ruta cuanta oon n:iis de dos puntos, m d!_

ben ser loa e%trarnos ( sin ooneidana1 al or!gen ) :pElJ.tt preve -

nir un n1oop" o sea , ouando um ruta consta da varios puntos

sin llegar el or!genq

3 .,- se asume qu& las oa rge s son combillil aaa da aouel."do a loa pasos

11 y s. lf)s oamionee son entonces reasigmdos de acuerdo al p:tso

2 y las capacidades izequari<2s son chequeadas oon las oora

p:ira deiarmi.nar si la l."Ut" propuesta es posible.,

4.-TOs l.ee dan'a :osiblaa rastricoionoo del p:roblsra. den eer

ti afecha " 1Cl:l el ejan'.@lo moatredo, um :ra str iooiin adicion!l.l

&s que los oainion&s no pueden reoorrar mJ..s de leo millliso

B1 \lnl I<s do s restriooionea no sa oumplsn, se elimilll el

p:ir l)Untoa el& cualquier consid&racin posterior y se repite

el I1l ao 519
- el ejemplo., el xnlximo ahorro total a 185 ( ver -tabla 5.4 )

JP.. :primera aaigmcin correaponde e .P - P4 oon um carga da 14

6
unida.des y la aegunc. GB P - J? O'.>n 16 unidades da paoid.ad..
5 3
i._Aro .7 r- Si toca a la s condiciones menciona ellas en el paso 6 aon a&-

tisteob\ a, los puntos P y p elegidos en 01 :paso 5 ee unsi. y t

Y z Y,
se haoe igual a 1, haoiendo los reajustes ne<esarioa en la tgbJa 4o3
 91

En al ajE1D.plo, el enJ..ace qua transpmta mayar carga es P - :e

5 3
qu oa:ao se expliw en el so 10 rasilta ser :W. primara m ta en
,-

la aoluc1n dal problsna, luego, el reajuste de la Iilitriz nflr06.do

t 12= 1, t ,::. l t : l, ccano se muest" en Ja 12blll 5t- 5

5' v J 3,1 f 6,1

71\
,,
Q
72 z
?3 /6 .
74 g 2
1
-
vs
1

J6 l l
76 6 2 ! 1

r, 5 2 ~
1 !
Ta b 5. 5 triz me.roa do d,e rutes rafl jw ta da
segn prim&.""'6 ruta

Et.so .S.- Bl. vector Q, debe ear entruoes oorr(gido de dos :it>rsa
) oa&a 13 a::,rresJ)o.wt:fente 41 un tj f O, se haoe 1BUa1 a o..
,
b) (}l)da Qj oorraspondiaIIt e e los puntos dnda comotadoa &l cxr!

gon (de la ruta que se es.bt axiizendo), a e hace igUA!ll a la s'lr-

De da l.6a dEIIl&lldaa rle talos loa puntos de la ruta. BJto tem -

bin SG illlst en lJi table 511 5-

PAS:> Q.- IJ>s cemioms son reasi.gnaoos ie cubrir los psses de

las lltB vas 1'U'tGas. )Jrto oonst; te en renovar los CEnnioms asigJ:lild.os

cubrir 1as pumos lf\ y P J e.signando uno l ruta que incltr

z
ye los 1>untos antes maro lomlos.o ML proceso :pa1".l ree.sigll3r loa <'!.
miones sa diswta en e1 e.so 2, mostndosa an wbla s.e la re-

(leignaoi6n de lAl. primaffl ruta

Jh el so 5 s se u.nh5 los :puntos? Y lP si ando lJi
5
o.arsa d e::rta
3
ta. l6 un:1.<lad.es qua se asin al eami.n d.e 18 y los :puntos res

tu 4:1:011 esiguS.b a a owniorea de 2 unidad-as de ct\,jl.o:lciado

<D-lOit-
.........--...- prlmfll."6 itemo!on de ha ootado y 1eg:re...<1Q.ndo al ---
so 5, vos pb1lidad de baoor nuevas unioneS'11 Si esto es P.2.

sibl.a ,- loa <h s caa que arre5PO:rtdan e.1 lnixtnx> aho:iro tot da

1a nm "V1l tabl& genera.da (o,,>) son ehequaados oon lila rute.a i

ginadaa en la ita:oooiln Qnterlo1: pud:sndo ocurr:Lr 11ariaa alter,!.

tt) tino d.e 109 enlaces coneota dos xutaa antes. o r:lgidaa.

b) trn enleca ti ene un punto en. a>mfui con d13 las rutas.

e) !Pa dos en:tscea n.o pueden ci:maotarae con ningwe a. la.a N1aa -
orjg :1.Uidrls q

En al oaso 1 e$a conexi&n SS.tistaoe l.&s rest:r1oo1or,u;is de pe.so,

distancia, ooatos, ato. ia ruta o.rece al. mb~ee egr~d<> ~ aalfl~

~ ns y esta lle~ ruta 1 es la ce se o onsi.dexe e:ce f\rtu.te.s ~
baa,

31. al. so de sar totibla ea :post bil:latd, tenl.remos 1'tta

(lue ree1IU)laza a la$ dos rs unida.is.

Sn lo que reSJ>oote al cso 2) aatos aula Os foi,iiln nueva rotas lo

origim que el pr,obl,DJl tange nis pcsi. b1l1tllild613 da genet:a:t< ru

.a aoluoi4n y su to posteria: ser oomo el d& lea rutas or1gi-

na.lmen:te go:ne11tdaa..

En al csao do no Sat' posiblo que e:rlsmn otros enlaoes anal. so

5i o saQ ,. no pueden oonrse J.a puntos (f!e !Gti:'agan todas las

r-elftrioci.oma del problema, ae ha. llegado a la solucin f:u1.u. Jlls

:rutes ai.eon"bll:ldas aa asignan a los CGmione resptiws (da acu.&l"do

al criterio seguido tal ccmo asignar loo C4:\lllionea de llilyor capacidad

inioilllnlerrte)y los puntos que n.o est"1 en nillgUlla ruta, son a a:ignll-
dos en fol"Jl:tl i:ndepend1E1:1te, o sea, ooaa uno e un camin en :rutas -

de ida y vuel t\6,

En al ,amplo tao.mios que ningwi punto pu.ea.e &mirs a ouslqui

l.'EI d.e las rutas- orjg:I.Ialee puoa JAa aapaoidades de e.mlaa eon.14 y

16 to y da los puntos osiblea a coXU:lide.mr va.re ino.rm&ntar es

tGs rutas o eraar ll\letas, la mfn oidud s 5 ton. a si se

'iln a la ru:i.el de meno:r "1)aoilad sobrf.:U)Q.Efln!& la c1dad m:d.-

11'1 de oe.mion.38, qu. a as- 18 tono !)or esta xez6' J.a ru.t de me.yo:

o1dad, se t<Jll:l como det1n1 t1"1!l, o SGEl, '11 -11 -1! - oon -
l 5 3 l
l6 ton. de Gi.dad y una distancia de J8? Jrlllao.

Heo:ta aaigtllilon, ee amuan toro B los enlaoea que conw por

lo menos uno de lcs puntos de la ruta eon la f'1IDlit1B4 a ev11Br

que loa.punto.a qua ya han sido asig!:fldos, se tomn en oua,.ta en -

tut.u.11:ls contt da1'lc:1 ones

CAPAc,vA )
12 /5 15
(7oN. )
'; '?r>1.11Bll1lJb1)
ASUM 1 )A ex) 1 1
/ ,4516NAOW 4 l
o 1

' ()1.J I {)\} 11-A# 62 Rt) (JNlt)N 2 HRK H()/)

,tfrAL
-
i- -
-
loe'; - ..., -
--
......

- - -- - -
bla 5.,7 Nieva tabla de ahorroa totales

N!J2A, Oano no mis puntos eatfafaoen le.a restl:'1.oeionaa del roblQIIS

asta ttlblo que&:1 1nconclue&co

 94

aon l.os ahon-os q qu.a<l3.n, se vuelve al :w.so 5; se gena"an ds

!lllGVae ruffi.fl y se c0ntintla el J;!?'OO&so hriil qe todos loa punin

del'llan&., ban a1do ;t isfehoe.

Oontimxudo con la soluc.1..Sn dal. ojEi11ilo, l tabla 5 08, noa mU3 stra

la. natriz cado de -utaa en la solucitn gonat.1a.l. re. tab.ltl 509 ,

-
nru.eatm la B!gnao:J..6n final de camiom tJ y la tabla 5 ol0 praswt -

las rutas :fi.ualea

.
oon cargas y distancia.a totalee raecttT1das en to

71 Q
72. 7 2
?3 16 ,
?4 /4 ' -
75 11 16 ) l (

14
1

1 !
?17 1
e: 2
'

CA ?.t:\ C! 1)J.. !) I'> / '$

( 70N. ) /
JJts7/.//
l.
J-JeDJJ)
2 ! I
As16.Al4 C/{YII
,r./A/A( 7- J I
 ( v rA .5" Ip,s7.M;a4 \ .. C4 2.A l
= -
?.-~-3 - B 76 16
?- ;s4 ~- P (2') /~
?,-~-~ /C/() 1)
~~??-1 !6C; ' 5
l,,1)slc)no. k;JLf ~ 5a3
'

Ji.l. ~ l que an el. a.]sor i1mo de Ol8rko and Wrigbt, ea nooasario -

tenor en ouenta qua los punt> s no coi.e o ta dos ~ ~ n se descartan

de posiblss CCUlSideraoionas de rutas para evitel:' el rompimiento de

 98

F.ESlMEN _________
-- __ ___
DEL P'i10GRAMA FORI'RAN
.,.., ,_ , VERSION -
.. --,..---
Tui0o87 DEL ---- -
ALG<lH:.!MO DE
...___

l!ll resiSman del :progL'a,m tort:ren diaaft.ado para l"esolver el algoritmo de

Til.llm.n cam<il. la fL1Ima en que se asn los datos y el significado de loa

reportes qm se iublicen, se muest a continwnino

Bn. esta pa1'"ta se _p"6sente en una f'oma blasta:nte 3.mral el di.agua-

ma de flujo en grandes bloqu.ea

( r.oct de tos

cilculo de,
&hol;'L"Os

orden::m1ento de
ahorros
( nayor e menor )

impes16n da matiz
da distenoiaa, a-
her.ros, flota

T

 ro pal.11 dot al"Jlrl nlr ' \ - - - - - - - - i l ' - - , .
aho1.,.ros totales

tonar lll:lyor ahorro

total y chequear
rastricc!oms
o '

escoger sgte ; mayor

ahorro que no oonten
ga Sl\Wnd:ices i !> -f
da uni'n l.- ahaquear
- l2.lil....L..l.w.i!.....t!n2)
1-.:re

hall.ar ahoo total

Gsooger mayor abo

rro total
anu.J..ar horros q,uo con
tota1
 100

lJiS tajsta de <!atoa necesarie.s son les siguientes g.

JJj pr:lm tarjeta tienG oano in:t'ooi6n s

llRBlu>(Y, B)NNtir,!e,Disr.A.N
,rooBM&.T (4115)

N' : nfuna:ro de }'.llntoa den.6nda

iNN : n6toom de datos distancias 6 til)OS de la matriZ

respeotiva

'NO , tipos de cemion0e de d.1:teroIIto octftoida a.

msrAS ; :re.str1ooi6n de distancia ,$ tiempos

rt l f!f3f t I J7fef J f f !~f 1 f1f6Jot f '-

,... Ul segunda tarjeta de datos indio,, la demanda de los puntos.

- !Ji tercera tc:rjeta rouest J.11a distan.cias tiem:pos en :ronna de

'Vector.

oo ae,:r!a coxno into:t'llnci6'n ;

lo:f1'31i5-t:1,i 7j1,afi! 9 1!9!ij2l2t s! 2f 7f ,

 101

- YJ. ouart& terj indica las dif'erentes ccidadea de lo.9 oa -

jiRl.1!AD (Y, 4, (OA.P(I) , l ::.l, rXJ),

~ lft)m,w[' (l.Ol.S)

!<?.. 1 Si tenemos 4 tipoa de onea de 2000,3000,4000 y 5000

kgo sa ax:preaar1 *

t:f2tc[oft ~3fofo!o+ T4f6tofoj f5fotofof t

- ta quinta tarjets de datos contiene el nrunero de caznionas que

I mw>(t 5) (DT&ll{I) ,I:= 1,NO)

lrol!JAT ( 10!2)

l Si tubis do,; camiones de 0000, 3 de 3000, 4 do 4000

y 5 da 5000; eooribiremos :

I..oa reportea que publica al programa son I

a) trJZ de di.stanoiAl.s y ehorroa.- cuando e.l p:obl t1eno m

nos de 13 puntos ( oonsiderando al organ ) einroco una sola

mat:ri donde en el lado doo;-echo figuren loa ahorros y en el !!_

qu1erdo les d:f.,9tanc1as 6 ahorros,.. Ondo el problena ccn de

ms de 13 looalidides, e.iaracan imprea las mstricaa se:pere

di?ls aeg(n se nuast:re en el -siguiente ejamplo 9

Pare. manos dG 13 localidades

 104

lTULO VII

APLI<lWION FBA.OTICA DllL .AU-OORITMO DE T!IJl.iAN _. UNl <WJENh..-1!!_ &n?Bma

a&ms,( llPSl )

7.1 IADO DEL l'ROBmllo-

En la aetualidad lta distr1buoitn de :productos en EPSA se hace dQa

de un d0l)6sito central e oo da uno d loa 14 supexmrcados con que
ouenta 1a li)ll.presa. Esta distribuoi6n se realiza segi1n sean los re-

quel"imientos de 6sto.s. Existen 4 camiones prol)ios da la Emprase y

se &lquilen 13 cam1on$S ( l.os propios son d.e 8 ton. y loa segundos

de 13 ton. ) pe h.a oor el l.'Sp; rto., Las rut a que daban Slir los

camiones p;ira eatist.'S oer las dnda s de los a.ipGr li:3 a b:l dotal;".llli

m d.o el Jadminbt.rador del depaito oentr-,;.l ba$1do en amp].1 ex,.-

peri.enoi en ee-ta tipo da t bajos. Hay di'ij.da a o mtqs que son

as que ragulemant& se tmpl0an y ouando uno 6 m!s eu:penneaoa

de u-1:tl ruta no tienen pedidos aa trata a.a seguir la rute tidecueda

&in oonaid.e,:,er eqaolloe super y algu!lla veces cuando los :pedid.os

de cierto super aon grandes, ae improV'isS la rutiil de aoierdo tmn -

bi&i e ia 6lt]?Grianoia del 4dministredor quien ads da desigrer

el orden da visitas, eugiers l&s rutas misn:Es :pare lo oual he so&-

tenido eonvarseciones eon los ohoferas.

como le tendencia d.a El?Slt. eonsiate en contar con tiendi.s af'111adae

distribuis inicialmente on todo ( luego ebercm todo el

pe!e) y qe en un pzo oarcaoo pusdsn ller e sm." 100 6 :ioos; r2_

aulta materialmente 1mpoa1ble qua une :perEJOna l)Or ouoha ax:perian -

ci que tenga puede enoarj:lraa de diaefi.ar s ru:ta s El d.acua cu:s

que se les propuso ol algoritmo do T11.lman p:ire detenniMr las ru-

tas, los oamionaa ldecu{.dos y lea ec.r.ttidadee y Wriedadea de p:r:'O -

dutos a dist.ribuu-, esparoondo llegr a. oontrtbuir a d:l.aafer un

giateme de Distribuein a lQa aupemercados p:.l.'8 tanar lir.:iantoQ

dis>oniblas 61 lico an toaaa );::la tiendas L'HJnoioae

]Cl. problema noturalmants tl't.'\ta d ontr las rutas que perm1tijp.

satisf&oer las danande.s de los supEmD.srcados desde un del)6sito cen

.,._
tl Jllim.rni"Zn til)O!!I 1t'iD.C1J:)<lllD.&nte.

1JJ. metz-iz de da tos 1'$qUel."idfi pe.ra 1& soluoin del prol,lm!)a as la

de tiElllpOa 1'1'6 lo cual Be tomado un lll"Ont$d1o de los ti(.;illpos

que empln los oomiones de ir del dei:i&'$1to a OWllquie aupar

1ar1os que llel)in los ohoferas en loa qe anotan loe tampos da

corri<loa 'Y de dsrgs en cada su:par a.e la ruta.. Esta tr.-iZ da

tia:npos sa .lll\l.estrE. <i cont1:nwci6n junto aon Jt:s delll7Dde.s de los

sup,merodoa que se han oonsaguido da l&tiJ gu[c. tJ da pedidos que se

ta cilitaron. HUY que tr en ue.n-w q_u 103 :pedidos sen. e.<mplte.

xnente dif1a:1rent as d& un super a oto y d& un a.!a a.l siguiente por

10 a l.;;11 dnoo s :pt'eaeJit; cas corresponden a t1n d{r. cutilquiara

de tie.bajo,

corno resti-1ocion.a, dal prool&ma tenemos lus o.aJ.)aeidad-es de los eo

miones { ouadro gue tambi,n aJ&rece lu$go ) y edenJs, el tisnpo t

l l"ecorMdo en une ruta oualpiare. no deba axoeder S horas pues

d$ lo 0011t1ufo habr!e que pagr sobretisnpo tanto lo e camiono -

rois eamo a1 l)&rsonal da E!ESA que se encc::r!fl 6.e reoepe1ontir la :rnal'

eedti."J.'!e"
 107

7.3 OOMPJ.P.AClON DE RESJ~~-

~a rutl s Cl_UE> eotu,.ilmant0 oo emplea.a p,.,.tt.. ht.t car el rapc::rto ,_ los

eupeme.rcados en verdad son d.e.ric:i.onee de un;; sol.:'i ruta que me -

~ie nt a p~qu lo s CtUD.b 1.os s a tl':1 ns:f'o:.ana an lt.,s otl'\.; "'

Esti;i rut.:. que podamos ll,ama.r rut;:., be se es oomo s taueatra a oont1

14 -2 -lo -5 -6 -11 -7 -13 -9 -12 -4 --1 -5 occq ( 4)

-0omo se epreoia t es,e ruta tiene lllls o::rianteoi6n e UW:t del ee,,&nte

v1a jaro pues BG han oonsidertldo -todos loe supeimatoados y se .ha su

puesto que se euwa con un cem:in de c;;::pqoid.:,d tt,l que IJE,mite

t-!staoar todas les d(;IJl;1 I!laa"

1}:3 s otx,.:: es mte s qua a:x:ist&n son W s siguiente e i

2 -10 -5 -6 -11 _,, -13 -9 -12 -4 -8 -1 -5 -14 eeoc-<'c,C:'e,to ( B)

10- 3 -6 -ll -7 -13 -9 -12 -4 -8-1-514 -2 O ,

(!<'<'<'Ot'C ( o )
1 -s -4 -12 _g ....J.3 -? -u -e -3 -10 -2 -14 -5. 4" e oo r ...
1 ne-:- e (. D )

8 -4 -12 _g -13 -7 -ll -6 -3 -lO - -14 -5 -1 ,t,,.OC"l(,;'! t' ( E )

4 -12 -9 -13 -7 -11 ...e, ---3 -lo -a -14 -5 -1 -e eOCJ!'9Q-ll <?O<' ( F )

tas B y O han .sufrid.o le.s ri.,.ntes da oolooar el pi:niat' super el

final y a !i}rtir da 1e wt" D so ha heoho lo oontri t sea, al

ltimo super a. J...a ruta 4 s ho. oolooQdo i:il comienzo.

l,08 :rasoJ.tB.dos obtenidos al eplioer el :prog;l'l;Ul]A tortn diseado

par! r&soler el algoritmo de Tillman $Oll los dgufontas 1

 108

.-
- :: - ---=r-
! P1 -J?9 - P5 - P13 - :P10 -P.l
----....-....,__ ..... _ .......-,.. .__ _____,__._____....,
76 8,700

-P - P11 - p2 - pl 8,320
pl
57

--------- --- .
?
_,...., -- ..
,.
_,,,, __. ... _._
p l -P 3 - pl4 - p8 -P1 55
__
8,185

+----------__,. ------ "'-

F - l?.15 - ,6 -P
l l
53 5;320

--1.-
4---
p - p - p - :e 5390
,..____ .... !" --- -

l l2 4 l
63

-------
'l'Il\mlQ 'ID.l'_.L 304
---
oomo loe super se laa he aumentdo UlJI::( unid pe.r:l tener oano d

peito el p1>.nto P en lc::s slicl:i e del progr.o(;llll3, las rutes .pe se

1
emplearon _pare; el a.!a q e se tomaron los da tos f'usmn a siguien.-

taa 1

--------"'___ ----
---...................._. _________ __
76 8,700
..,
l? - P -P - P -P 'l ,.040
,. ,

1 l.4 8 12 1
63

ti -- - - _
l 7 4 ll l
P -P - P -P - .P 7490

----------- __:
__.__._ ----.- .. ... .....,..._. --.
--....------ -
3 =._
r:1'.:__"" 5.1:__ 9:.15 ...
P
15

40 3,.340
.__. ,___l
I
pl - ?2 - ?l
---- ----- . --" -- -
TI.llh'.il?O TorJ.L : 327
-- ----.
.AlizE.ndo le rutiss que se ffin ancont?-ado 0011 las que se USCl"On

aqul de ,oon el algoritmo de TUlinsn se logre una reduvoi& da

#
tJ&m;:o de 23 ll31mztos4' !.a asign.seion de liliones con Tillmen recpi !.

re 5 de lo ton.. ( puel.&n ser 3 de lo t-on., y 2 de 8 ton. haciendo

un pequafio cambio ao. Gl. l)l"Ogram), mien.t-re:s qu.9 en eaigci6n

de le Em).ress se uSBron 2 cam1onoa & 10 ton. y 5 do e ton., Es -

to que a.xentexnehte otcriga cie:rta :ventt:jc. el m6todo actu&l(lles

@ la comparaci6n de cosl;oa obvic:iIDente <tl usar c6Unionae de 10 to

implica un m:yo:r f!ft. sto que &stos oanonas son t.lqu11-:.dos) uo ea

real debido prin.eilm-3nte a qua no existe un pln rt.eion2,l da re-

parto y en cllgu.nss oct.sionas se usen allo C.imionee ele lO ton

}>aN a:icpl1Ckir asto quiero Jn;.n.ifestsi que los pedidos .se meen ... o -

actuc:.l:lllenta en cuE.lqu:Ls:r lllomEn m desda cu<lquisr supn,nercado Y

ali-lnoa da toe pueden. b.car 2 t pedidos diario lo q.>.& or1g1:t-,

q_ue eontor.na hayan podidos ae ,ayan eaignando xuta&J Hay aituao10-

nea en que los pedidos aoti urgentes y en ese so se bsigna un ca

min p.N s:ttistaoe,: aolemente li dauand; de los super solieitn-

tas.
 B I B L I G R A F A

An algoritmo for the vehicle-dispetching problem

N. Christofidas and S. Eilon

The delivery problem

Robert W. Haring

* The truck dispatching problem

C.B. Dentzig and Ramser

A heuristic approach for solving the delivery problem

Tilman and Cochrane

B Distribution MANAGEMENT

Ne Christofidas and Eilon