ࡱ> +-*bjbjUU >??HH  H|rP!j0H HH Q:Aluno: Igor Machado Coelho Orientadores: Luiz Satoru Ochi e Luidi Simonetti Ttulo: Hybrid and Parallel Algorithms for Single and Multi-Objective Routing Problems Resumo: This thesis deals with single and multi-objective routing problems by means of hybrid and parallel metaheuristics. The first routing problem is called the Single Vehicle Routing Problem with Deliveries and Selective Pickups (SVRPDSP) and consists in finding a route that starts from the depot and visits all delivery customers. Some pickup customers may also be visited, since the capacity of the truck is not exceeded, and there is also a revenue associated with each pickup. We develop an algorithm inspired on the Variable Neighborhood Search metaheuristic that explores the power of modern Graphics Processing Unit (GPU) to provide routes in reasonable computational time. Our experimental results show that the proposed algorithm is able to improve the quality of the solution for 51 instances out of 68 instances taken from the literature. We obtained speedups up to 14.49 times, varying from 17.42 up to 76.84 for each local search, measured over a set of new large size instances. We also propose a multi-objective evolutionary approach with an exact one-to-many decoder for bi-objective arc routing. This problem requires servicing a set of required edges with positive demands using a fleet of vehicles of limited capacity. The goal is to minimize: (i) the total length of all traversed edges and (ii) the length of the longest route. The evolutionary algorithm works with an indirect solution representation based on permutations of the required edges. Each permutation is mapped to a Pareto set of solutions by a multi-objective decoder based on dynamic programming. Results show that the proposed method offers a significant improvement over previous algorithms in terms of solution quality for both objectives, while also exhibiting a better Pareto front convergence. Experiments with the proposed algorithms show novel convergence behaviors that can be explored in other single and multi-objective problems. Palavras-chave: Metaheuristics; Arc Routing Problem; Single Vehicle Routing Problem with Deliveries and Selective Pickups; Multi-Objective Problems; GPU Computing. h3LM45E$a$ <P1h:p3. A!n"n#n$n% Dp^ 666666666vvvvvvvvv66666686666666666666666666666666666666666666666666666666hH6666666666666666666666666666666666666666666666666666666666666666662 0@P`p2( 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p8XV~_HmHnHsHtHR`R Normal*$1$$CJKHPJ_HaJmHnHsHtHDA D 0Default Paragraph FontRiR 0 Table Normal4 l4a (k ( 0No List J/J 0Absatz-StandardschriftartP/P 0WW-Absatz-StandardschriftartN"N 0Heading $xCJOJPJQJ^JaJ2B"2 0 Body TextxL/1L pR0Body Text CharCJKHPJaJnHtH$/!B$ 0List<"R< 0Caption  $xx6]*b* 0Index $J"J 0Ttulo1 $xCJOJQJ^JaJ>> 0Legenda1  $xx6],, 0ndice $PK![Content_Types].xmlj0Eжr(΢Iw},-j4 wP-t#bΙ{UTU^hd}㨫)*1P' ^W0)T9<l#$yi};~@(Hu* Dנz/0ǰ $ X3aZ,D0j~3߶b~i>3\`?/[G\!-Rk.sԻ..a濭?PK!֧6 _rels/.relsj0 }Q%v/C/}(h"O = C?hv=Ʌ%[xp{۵_Pѣ<1H0ORBdJE4b$q_6LR7`0̞O,En7Lib/SeеPK!kytheme/theme/themeManager.xml M @}w7c(EbˮCAǠҟ7՛K Y, e.|,H,lxɴIsQ}#Ր ֵ+!,^$j=GW)E+& 8PK!Ptheme/theme/theme1.xmlYOo6w toc'vuر-MniP@I}úama[إ4:lЯGRX^6؊>$ !)O^rC$y@/yH*񄴽)޵߻UDb`}"qۋJחX^)I`nEp)liV[]1M<OP6r=zgbIguSebORD۫qu gZo~ٺlAplxpT0+[}`jzAV2Fi@qv֬5\|ʜ̭NleXdsjcs7f W+Ն7`g ȘJj|h(KD- dXiJ؇(x$( :;˹! I_TS 1?E??ZBΪmU/?~xY'y5g&΋/ɋ>GMGeD3Vq%'#q$8K)fw9:ĵ x}rxwr:\TZaG*y8IjbRc|XŻǿI u3KGnD1NIBs RuK>V.EL+M2#'fi ~V vl{u8zH *:(W☕ ~JTe\O*tHGHY}KNP*ݾ˦TѼ9/#A7qZ$*c?qUnwN%Oi4 =3ڗP 1Pm \\9Mؓ2aD];Yt\[x]}Wr|]g- eW )6-rCSj id DЇAΜIqbJ#x꺃 6k#ASh&ʌt(Q%p%m&]caSl=X\P1Mh9MVdDAaVB[݈fJíP|8 քAV^f Hn- "d>znNJ ة>b&2vKyϼD:,AGm\nziÙ.uχYC6OMf3or$5NHT[XF64T,ќM0E)`#5XY`פ;%1U٥m;R>QD DcpU'&LE/pm%]8firS4d 7y\`JnίI R3U~7+׸#m qBiDi*L69mY&iHE=(K&N!V.KeLDĕ{D vEꦚdeNƟe(MN9ߜR6&3(a/DUz<{ˊYȳV)9Z[4^n5!J?Q3eBoCM m<.vpIYfZY_p[=al-Y}Nc͙ŋ4vfavl'SA8|*u{-ߟ0%M07%<ҍPK! ѐ'theme/theme/_rels/themeManager.xml.relsM 0wooӺ&݈Э5 6?$Q ,.aic21h:qm@RN;d`o7gK(M&$R(.1r'JЊT8V"AȻHu}|$b{P8g/]QAsم(#L[PK-![Content_Types].xmlPK-!֧6 +_rels/.relsPK-!kytheme/theme/themeManager.xmlPK-!Ptheme/theme/theme1.xmlPK-! ѐ' theme/theme/_rels/themeManager.xml.relsPK]   3=@@@UnknownG*Ax Times New Roman5Symbol3. *Cx ArialQ Droid SansMS MinchoG& xP!Liberation SansACambria Math" i3'i3'ax! 0 $P=!xxAluno: Igor Machado CoelhoIgor HelioOh+'0 $ H T `lt|Aluno: Igor Machado CoelhoIgor Normal_WordconvHelio2Microsoft Office Outlook@G@j@jax՜.+,0 hp|   Aluno: Igor Machado Coelho Title  !#$%&'(),Root Entry F@l+j.1Table WordDocument>SummaryInformation(DocumentSummaryInformation8"CompObjy  F'Microsoft Office Word 97-2003 Document MSWordDocWord.Document.89q  F#Documento do Microsoft Office Word MSWordDocWord.Document.89q