-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathtesis.lyx
13173 lines (10141 loc) · 246 KB
/
tesis.lyx
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
#LyX 1.6.5 created this file. For more info see http://www.lyx.org/
\lyxformat 345
\begin_document
\begin_header
\textclass article
\use_default_options true
\language spanish
\inputencoding auto
\font_roman default
\font_sans default
\font_typewriter default
\font_default_family default
\font_sc false
\font_osf false
\font_sf_scale 100
\font_tt_scale 100
\graphics default
\paperfontsize default
\spacing single
\use_hyperref false
\papersize a4paper
\use_geometry false
\use_amsmath 1
\use_esint 1
\cite_engine basic
\use_bibtopic true
\paperorientation portrait
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\defskip medskip
\quotes_language english
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\author ""
\author ""
\end_header
\begin_body
\begin_layout Title
Un algoritmo distribuído de Ruin & Recreate para el problema de ruteo de
vehículos con ventanas de tiempo
\end_layout
\begin_layout Author
Martínez Quijano, Andrés \SpecialChar \nobreakdash-
LU: 32/98
\end_layout
\begin_layout Standard
\align center
Directora: Dra.
Irene Loiseau
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename uba.jpg
scale 50
\end_inset
\end_layout
\begin_layout Standard
\align center
Departamento de Computación
\end_layout
\begin_layout Standard
\align center
Facultad de Ciencias Exactas y Naturales
\end_layout
\begin_layout Standard
\align center
Universidad de Buenos Aires
\end_layout
\begin_layout Standard
\align center
Argentina
\end_layout
\begin_layout Verse
\begin_inset Newpage pagebreak
\end_inset
\end_layout
\begin_layout Abstract
En esta tesis se considera el problema de ruteo de vehículos con ventanas
de tiempo (Vehicle Routing Problem with Time Windows, VRPTW) y se propone
un algoritmo distribuído de la metaheurística Ruin and Recreate para el
mismo.
El problema de VRPTW es una variante del problema de ruteo de vehículos
(VRP) donde cada cliente tiene una ventana de tiempo asociada durante la
cual puede ser visitado por un vehículo.
El algoritmo y la implementación propuestas se ejecutan de forma paralela
y transparente en un número ilimitado de nodos computacionales.
Los resultados obtenidos mediante la aplicación paralela del algoritmo
son competitivos con las mejores soluciones obtenidas heurísticamente.
\begin_inset VSpace defskip
\end_inset
\end_layout
\begin_layout Abstract
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
selectlanguage{english}
\end_layout
\begin_layout Plain Layout
\backslash
begin{abstract}
\end_layout
\begin_layout Plain Layout
This thesis deals with the vehicle routing problem with time windows (VRPTW)
and it introduces a distributed algorithm based on the Ruin and Recreate
metaheuristic.
The VRPTW is a variant of the vehicle routing problem (VRP) where each
client has a time window of the time when it can be served by a vehicle.
The algorithm can be transparently executed in parallel in many cores across
many computers on a network.
The obtained results were found to be competetive with the best-known results.
\end_layout
\begin_layout Plain Layout
\backslash
end{abstract}
\end_layout
\begin_layout Plain Layout
\backslash
selectlanguage{spanish}
\end_layout
\end_inset
\end_layout
\begin_layout Verse
\begin_inset Newpage pagebreak
\end_inset
\end_layout
\begin_layout Standard
\begin_inset CommandInset toc
LatexCommand tableofcontents
\end_inset
\begin_inset Newpage pagebreak
\end_inset
\end_layout
\begin_layout Standard
\begin_inset FloatList algorithm
\end_inset
\begin_inset Newpage pagebreak
\end_inset
\end_layout
\begin_layout Standard
\begin_inset FloatList figure
\end_inset
\begin_inset Newpage pagebreak
\end_inset
\end_layout
\begin_layout Section
Descripción del problema
\end_layout
\begin_layout Subsection
Introducción
\end_layout
\begin_layout Standard
El ruteo de vehículos es un problema de logística muy presente en la vida
real.
Consiste en la optimización de asignación de rutas a vehículos en un orden
y tiempo determinados, de forma de minimizar la distancia total recorrida,
la cantidad de vehículos necesarios para cumplir los requisitos, o, en
general, ambas cosas.
En su instancia más simple, el VRP
\begin_inset Foot
status open
\begin_layout Plain Layout
del inglés
\emph on
Vehicle Routing Problem
\end_layout
\end_inset
, existe un número fijo de clientes con demandas de mercadería que debe
ser satisfecha con la visita de uno y sólo un vehículo (o camión).
Dado que los camiones tienen capacidad limitada, en general no es viable
que un sólo camión pueda visitar y satisfacer la demanda de todos los clientes,
por lo que es necesario que se agreguen camiones a la solución para que
ésta sea factible.
\end_layout
\begin_layout Standard
Una solución a una instancia de VRP consiste en un conjunto de rutas que
debe recorrer cada vehículo, partiendo y terminando en el
\emph on
depósito,
\emph default
de forma que todos los clientes sean visitados y sus demandas y restricciones
sean cumplidas.
El objetivo del VRP es encontrar la mejor solución, según el parámetro
de optimización deseado (cantidad de vehículos, distancia total recorrida,
tiempos de espera, etc.).
Existen diversas variantes al problema original: en VRPB
\begin_inset Foot
status open
\begin_layout Plain Layout
del inglés
\emph on
Vehicle Routing Problem with Backhauls
\end_layout
\end_inset
donde además del conjunto de clientes a quienes se les debe entregar mercadería
, existe otro conjunto de
\emph on
proveedores
\emph default
a quienes se debe ir en busca de mercadería para llevar de vuelta al depósito.
Además, todas las entregas deben hacerse antes que las recogidas, para
evitar reacomodar la carga del vehículo.
VRPPD
\begin_inset Foot
status open
\begin_layout Plain Layout
del inglés
\emph on
Vehicle Routing Problem with Pickup and Delivery
\end_layout
\end_inset
, donde no hay un depósito único de donde obtener la carga a repartir, sino
que está distribuída en distintos puntos, por lo que debe ser recogida
primero para poder ser entregada.
VRPSD
\begin_inset Foot
status open
\begin_layout Plain Layout
del inglés
\emph on
Vehicle Routing Problem with Split Delivery
\end_layout
\end_inset
permite que un cliente sea satisfecho por más de un vehículo, dando lugar
a entregas parciales.
\end_layout
\begin_layout Standard
En esta tesis se trata exclusivamente la variante VRPTW
\begin_inset Foot
status open
\begin_layout Plain Layout
del inglés
\emph on
Vehicle Routing Problem with Time Windows
\end_layout
\end_inset
donde cada cliente tiene asociada una ventana de tiempo que restringe el
momento en que puede ser visitada por un vehículo y un tiempo necesario
de servicio.
Si bien un camión puede arribar a un cliente antes de tiempo, deberá esperar
al inicio de su ventana de tiempo antes de poder iniciar la descarga, pero
nunca podrá arribar luego de cerrada la ventana.
El tiempo de servicio de cada cliente se impone como el tiempo que toma
la descarga de mercadería.
En el caso que plantea esta tesis, la ventana de tiempo aplica solamente
a la llegada del camión y no al tiempo de servicio, por lo que, por ejemplo,
se acepta que un camión llegue a una hora tal a un cliente de forma que
el servicio termine después de la ventana de tiempo haya cerrado.
Para una revisión más completa del problema de ruteo de vehículos, modelos,
algoritmos, variantes y formulaciones ver
\begin_inset CommandInset citation
LatexCommand cite
key "key-VRP"
\end_inset
.
\end_layout
\begin_layout Standard
En este trabajo se propone una solución metaheurística de tipo Ruin And
Recreate
\begin_inset CommandInset citation
LatexCommand cite
key "key-RR"
\end_inset
multiobjetivo, con implementación distribuída que permita utilizar varias
computadoras en red para resolver el problema.
\end_layout
\begin_layout Standard
En el resto de la sección 1 se introduce más detalladamente el VRPTW.
En la sección 2 se detalla la metaheurística
\emph on
Ruin & Recreate
\emph default
.
En la sección 3 se presenta en detalle la solución propuesta por esta tesis.
La sección 4 expone los resultados obtenidos al aplicar el algoritmo, y
finalmente en las secciones 5 y 6 se muestran las conclusiones y posible
trabajo futuro, respectivamente.
\end_layout
\begin_layout Subsection
Formulación de VRPTW
\end_layout
\begin_layout Standard
Sea
\begin_inset Formula $G=(V,A)$
\end_inset
un grafo completo donde
\begin_inset Formula $V=\{0,\ldots,n\}$
\end_inset
es el conjunto de vértices y
\begin_inset Formula $A$
\end_inset
el conjunto de ejes.
El nodo
\begin_inset Formula $0$
\end_inset
(también notado como nodo
\begin_inset Formula $n+1$
\end_inset
) corresponde al depósito de donde parten los vehículos y
\begin_inset Formula $i=1\ldots n$
\end_inset
son los clientes.
\begin_inset Formula $N=V\setminus\{0\}$
\end_inset
es el conjunto de clientes.
Además:
\end_layout
\begin_layout Standard
\begin_inset Formula $\Delta^{+}(i)=\{j/(i,j)\in A\}$
\end_inset
los nodos
\emph on
salientes
\emph default
del nodo
\begin_inset Formula $i$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $\Delta^{-}(i)=\{j/(j,i)\in A\}$
\end_inset
los nodos
\emph on
entrantes
\emph default
al nodo
\begin_inset Formula $i$
\end_inset
\begin_inset Foot
status open
\begin_layout Plain Layout
dado que en esta tesis se trabaja únicamente con grafos completos,
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\noun off
\color none
\lang english
\begin_inset Formula $\Delta^{+}(i)=\Delta^{-}(i)=V\setminus\{i\}$
\end_inset
\end_layout
\end_inset
\end_layout
\begin_layout Standard
Un costo no negativo
\begin_inset Formula $c_{ij}$
\end_inset
es asociado a cada eje
\begin_inset Formula $(i,j)\in A$
\end_inset
, representando el costo de viajar desde el nodo
\begin_inset Formula $i$
\end_inset
hasta el nodo
\begin_inset Formula $j$
\end_inset
.
En el caso que plantea esta tesis, se asume que el grafo no es dirigido,
o sea
\begin_inset Formula $c_{ij}=c_{ji\:}\forall i,j\in A,\: i\neq j$
\end_inset
.
\end_layout
\begin_layout Standard
Cada cliente tiene asociada una demanda no negativa
\begin_inset Formula $d_{i}$
\end_inset
(siendo
\begin_inset Formula $d_{0}=0$
\end_inset
) y una ventana de tiempo
\begin_inset Formula $[a_{i},b_{i}]$
\end_inset
con
\begin_inset Formula $a_{i}<b_{i}$
\end_inset
.
Los parámetros
\begin_inset Formula $E$
\end_inset
y
\begin_inset Formula $L$
\end_inset
indican el comienzo y fin, respectivamente, de la ventana de tiempo del
depósito:
\begin_inset Formula $[a_{0},b_{0}]=[E,L]$
\end_inset
, donde
\begin_inset Formula $a_{0}\leq a_{i}\:\forall i\in V$
\end_inset
y
\begin_inset Formula $b_{0}\geq b_{i}\:\forall i\in V$
\end_inset
.
También se asocia a cada cliente un valor no negativo
\begin_inset Formula $s_{i}$
\end_inset
indicando el tiempo de servicio, esto es, el tiempo mínimo que un vehículo
debe permanecer en el cliente cargando o descargando mercadería antes de
poder proseguir su ruta.
\end_layout
\begin_layout Standard
Se dispone de
\begin_inset Formula $K$
\end_inset
vehículos idénticos entre sí, cada uno con capacidad de carga
\begin_inset Formula $C$
\end_inset
\SpecialChar \@.
\end_layout
\begin_layout Standard
Se definen además las siguientes variables:
\end_layout
\begin_layout Standard
\begin_inset Formula $x_{ijk}=\begin{cases}
1 & \mbox{si \ensuremath{(i,j)\in A\mbox{ es usado por el vehículo \ensuremath{k}}\in K}}\\
0 & \mbox{si no}\end{cases}$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $w_{ik},i\in V,k\in K$
\end_inset
el comienzo del servicio en el nodo
\begin_inset Formula $i$
\end_inset
por el vehículo
\begin_inset Formula $k$
\end_inset
\end_layout
\begin_layout Standard
En el caso en que el objetivo sea minimizar el costo, el problema se puede
plantear como un problema de programación lineal entera, donde la solución
óptima consiste en hallar:
\end_layout
\begin_layout Standard
\begin_inset Formula \begin{equation}
\min\underset{k\in K}{\sum}\underset{(i,j)\in A}{\sum c_{ij}x_{ijk}}\label{eq:1}\end{equation}
\end_inset
\end_layout
\begin_layout Standard
sujeto a:
\end_layout
\begin_layout Standard
\begin_inset Formula \begin{equation}
\underset{k\in K}{\sum}\underset{j\in\Delta^{+}(i)}{\sum x_{ijk}}=1\qquad\forall i\in N\label{eq:2}\end{equation}
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula \begin{equation}
\underset{j\in\Delta^{+}(0)}{\sum x_{0jk}}=1\qquad\forall k\in K\label{eq:3}\end{equation}
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula \begin{equation}
\underset{i\in\Delta^{-}(j)}{\sum x_{ijk}}-\underset{i\in\Delta^{+}(j)}{\sum x_{jik}}=0\qquad\forall k\in K,j\in N\label{eq:4}\end{equation}
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula \begin{equation}
\underset{i\in\Delta^{-}(n+1)}{\sum x_{i,n+1,k}}=1\qquad\forall k\in K\label{eq:5}\end{equation}
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula \begin{equation}
x_{ijk}(w_{ik}+s_{i}+c_{ij}-w_{jk})\leq0\qquad\forall k\in K,(i,j)\in A\label{eq:6}\end{equation}
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula \begin{equation}
a_{i}\left(\underset{j\in\Delta^{+}(i)}{\sum x_{ijk}}\right)\leq w_{ik}\leq b_{i}\left(\underset{j\in\Delta^{+}(i)}{\sum x_{ijk}}\right)\qquad\forall k\in K,i\in N\label{eq:7}\end{equation}
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula \begin{equation}
E\leq w_{ik}\leq L\qquad\forall k\in K,i\in\{0,n+1\}\label{eq:8}\end{equation}
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula \begin{equation}
\underset{i\in N}{\sum}d_{i}\underset{j\in\Delta^{+}(i)}{\sum x_{ijk}}\leq C\qquad\forall k\in K\label{eq:9}\end{equation}
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula \begin{equation}
x_{ijk}\geq0\qquad\forall k\in K,(i,j)\in A\label{eq:10}\end{equation}
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula \begin{equation}
x_{ijk}\in\{0,1\}\qquad\forall k\in K,(i,j)\in A\label{eq:11}\end{equation}
\end_inset
\end_layout
\begin_layout Standard
la condición
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:11"
\end_inset
permite que la restricción
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:6"
\end_inset
sea linealizable como
\end_layout
\begin_layout Standard
\align center
\begin_inset Formula \begin{equation}
w_{ik}+s_{i}+c_{ij}-w_{jk}\leq(1-x_{ijk})M_{ij}\qquad\forall k\in K,(i,j)\in A\label{eq:7a}\end{equation}
\end_inset
\end_layout
\begin_layout Standard
donde
\begin_inset Formula $M_{ij}$
\end_inset
son constantes grandes
\end_layout
\begin_layout Standard
\begin_inset CommandInset ref
LatexCommand eqref
reference "eq:2"
\end_inset
restringe las visitas a sólo un vehículo por cliente
\end_layout
\begin_layout Standard
\begin_inset CommandInset ref
LatexCommand eqref
reference "eq:3"
\end_inset
\begin_inset CommandInset ref
LatexCommand eqref
reference "eq:4"
\end_inset
\begin_inset CommandInset ref
LatexCommand eqref
reference "eq:5"
\end_inset
modelan el tipo de recorridos que un vehículo puede hacer (salir del depósito,
visitar clientes y volver al depósito)
\end_layout
\begin_layout Standard
\begin_inset CommandInset ref
LatexCommand eqref
reference "eq:6"
\end_inset
\begin_inset CommandInset ref
LatexCommand eqref
reference "eq:7"
\end_inset
\begin_inset CommandInset ref
LatexCommand eqref
reference "eq:8"
\end_inset
\begin_inset CommandInset ref
LatexCommand eqref
reference "eq:9"
\end_inset
aseguran factibilidad en cuanto a ventanas de tiempo y capacidad de vehículos
\end_layout
\begin_layout Standard
\begin_inset CommandInset ref
LatexCommand eqref
reference "eq:7"
\end_inset
además obliga que
\begin_inset Formula $w_{ik}=0$
\end_inset
si el vehículo
\begin_inset Formula $k$
\end_inset
no visita al cliente
\begin_inset Formula $i$
\end_inset
\end_layout
\begin_layout Standard
En esta tesis se trabaja con un problema multiobjetivo, donde se prioriza
la reducción de la cantidad de vehículos de la solución, y en segunda instancia
la distancia total recorrida.
\end_layout
\begin_layout Subsection
Metaheurísticas
\end_layout
\begin_layout Standard
Dado que
\noun on
VRPTW
\noun default
es un problema
\noun on
NP-HARD
\noun default
(ver
\begin_inset CommandInset citation
LatexCommand cite
key "key-VRP"
\end_inset
), desde el punto de vista de las aplicaciones reales resulta impracticable
buscar la optimalidad mediante algoritmos exactos en instancias grandes,
por lo que se acude a heurísticas o metaheurísticas para obtener buenas
soluciones factibles de los problemas en tiempos acotados.
\end_layout
\begin_layout Standard
Algunas de las metaheurísticas más utilizadas son:
\end_layout
\begin_layout Enumerate
\emph on
Simulated Annealing
\emph default
: basada en un proceso metalurgico que consiste en calentar y dejar enfriar
controladamente un material.
Al calentarse los átomos salen de sus posiciones originales y se muevan
al azar, al enfriarse lentamente tienen mayores posibilidades de encontrar
configuraciones de menor energía que la inicial
\end_layout
\begin_layout Enumerate
\emph on
Tabú search
\emph default
: una búsqueda local que guarda una lista de soluciones ya visitadas para
permitir expander el entorno y no atorarse en un mínimo local
\end_layout
\begin_layout Enumerate
\emph on
Algoritmos genéticos
\emph default
: basada en la evolución natural.
En cada iteración una población de soluciones dada provee un conjunto de
nuevas soluciones que son evaluadas y las
\emph on
más aptas
\emph default
, es decir, las de mejor función objetivo, tendrán más chances de ser parte
de la nueva población, que se formará en base a mutaciones y combinaciones
de las actuales
\end_layout
\begin_layout Enumerate
\emph on
Swarm optimization
\emph default
: son algoritmos basados en comportamientos colectivos de algunos animales,
por ejemplo: colonia de hormigas, colonia de abejas, de libélulas, etc
\end_layout
\begin_layout Section
Ruin & Recreate
\begin_inset CommandInset label
LatexCommand label
name "sec:Ruin-&-Recreate"
\end_inset
\end_layout
\begin_layout Standard
La metaheurística Ruin & Recreate fue desarrollada en el año 1998 por Schrimpf,
Schneider, Stamm-Wilbrandt y Dueck y en un principio fue aplicada a VRPTW,
a problemas de optimización de redes y al viajante de comercio
\begin_inset CommandInset citation
LatexCommand cite
key "key-RR"
\end_inset
.
La misma consiste en arruinar (
\emph on
ruin
\emph default
) una solución (generalmente factible) para luego reconstruirla (
\emph on
recreate
\emph default
) de forma de obtener una mejor solución de la que se partió (ver Algoritmo
\begin_inset CommandInset ref
LatexCommand ref
reference "Flo:RAR"
\end_inset
).
\end_layout
\begin_layout Standard
En el caso de VRPTW, arruinar la solución consiste en quitar
\begin_inset Formula $t$
\end_inset
clientes según un criterio de arruine, dejando una solución infactible,
donde sólo
\begin_inset Formula $n-t$
\end_inset
clientes son visitados por los vehículos.
Luego el algoritmo intenta reintroducir los
\begin_inset Formula $t$
\end_inset
clientes a la solución rota, tratando de obtener una mejor solución de
la cual se partió.
El proceso se repite hasta que una condición es satisfecha, sea porque
se consiguió una solución suficientemente buena, porque se cumplió un número
fijo de iteraciones, porque ocurrieron suficientes iteraciones sin obtener
mejoras a la solución o cualquier otra condición de corte.
\end_layout
\begin_layout Standard
El
\emph on
quid
\emph default
del algoritmo es, claramente, la forma en que se arruina y recrea la solución\SpecialChar \@.
\end_layout
\begin_layout Subsection
Ruin
\end_layout
\begin_layout Standard
Arruinar la solución es computacionalmente sencillo, aunque algorítmicamente
es tan importante como recrearla.
Elegir qué nodos quitar de la solución es crucial a la hora de poder generar
una mejora o no.
En
\begin_inset CommandInset citation
LatexCommand cite
key "key-RR"
\end_inset
se plantean diversas variantes básicas en lo referido a ruteo de vehículos,
por ejemplo:
\end_layout
\begin_layout Itemize
Espacial: dado un nodo
\begin_inset Formula $n$
\end_inset
se quitan de la solución
\begin_inset Formula $n$
\end_inset
y todos los nodos cuya distancia a
\begin_inset Formula $n$
\end_inset