ࡱ> *,)bjbjUU :?? CCCCCWWWW c Woooooooo,JCoooooCCooooooCoCooooooo@Woo0ovovovCo oooooooooooooooovooooooooo :RESUMO Este trabalho aborda o Problema do Caixeiro Alugador (PCA), uma variante do Problema do Caixeiro Viajante. No PCA um turista deseja viajar por um conjunto de cidades alugando diferentes tipos de veculo a um custo mnimo. O objetivo determinar a rota tima e o tipo de veculo que ser alugado para cumprir cada viagem. Por se tratar de um problema NP-Difcil, neste trabalho so apresentadas duas abordagens exatas e uma heurstica para sua resoluo. Dentre as abordagens exatas, a primeira baseada em uma formulao quadrtica inteira da literatura e a segunda, uma nova formulao linear inteira. A abordagem heurstica baseada na meta-heurstica Multi-Start Iterated Local Search com uma etapa de busca local inspirada na metodologia de Random Variable Neighborhood Descent. Os resultados computacionais obtidos nas abordagens exatas foram capazes de encontrar o timo de 35 das 47 instncias testadas, sendo que 17 destas tiveram o timo provado pela primeira vez. A abordagem heurstica foi aplicada s instncias euclidianas e os resultados obtidos so comparadas com o estado da arte, mostrando que a abordagem proposta possui um melhor desempenho. Palavras-chave: Problema do Caixeiro Alugador. Heursticas. Programao Inteira. Turismo e Transporte. ABSTRACT The present work deals with the Car Renter Salesman Problem (CaRS), which is a Traveling Salesman Problem variant. The CaRS concerns tourists intending to travel through a set of cities using rented vehicles at minimum cost. The aim of the current research is to establish an optimal route and renting vehicle type to each trip. Since CaRS is a NP-Hard problem, this work presents both exact and heuristic approaches. To be more especific, two mathematical formulations are presented. The first one was based on a quadractic formulation from literature, while the second one was a newly developed linear formulation. The heuristic approach was based on a Multi-Start Iterated Local Search metaheuristic. Its local search step was based on the Random Variable Neighborhood Descent methodology. Computational experiments showed that the exact approaches were able to optimally solve 35 out of 47 instances, 17 of these were first proved herein. As for the heuristic approach, tests in Euclidean instances showed that the proposed method outperformed current state-of-art results. Keywords: Car Renter Salesman. Heuristics. Integer Programming. Transport and Tourism.    >Hh)> h)>^J h)>5\    =>$a$$a$ 8P:p)>. 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~_HmHnHsHtHX`X Normal*$,CJKHOJQJ^J_HaJmHnHsHtHDA D 0Default Paragraph FontRiR 0 Table Normal4 l4a (k ( 0No List JJ 0Heading $xCJOJQJ^JaJ8B8 0 Body Text d T/T az0Body Text Char CJKHOJQJ^JaJnHtH$/"$ 0List<"2< 0Caption  $xx6]*B* 0Index $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]   )> @ @@UnknownG*Ax Times New Roman5Symbol3" ArialI xP!Liberation SerifG& xP!Liberation SansACambria Math" 2T2T! 0 $P !xxRESUMOHelioHelioOh+'0x  4 @ LX`hpRESUMOHelioNormal_WordconvHelio2Microsoft Office Outlook@F#@B_@B_՜.+,0 hp|   RESUMO Title  "#$%&'(+Root Entry F0: -1Table vWordDocument:SummaryInformation(DocumentSummaryInformation8!CompObjy  F'Microsoft Office Word 97-2003 Document MSWordDocWord.Document.89q  F#Documento do Microsoft Office Word MSWordDocWord.Document.89q