ࡱ> /1.bjbjUU > ??EEEEEYYYY e Yqqqqqqqq.EqqqqqEEqqqqqqEqEqqqqqqqXJYqq0qqqEq qqqqqqqqqqqqqqqqqqqqqqqqq :Ttulo: AN EFFICIENT HEURISTIC FOR ONE-TO-ONE PICKUP AND DELIVERY PROBLEMS Abstract This thesis deals with two one-to-one pickup and delivery problems: the Multi-vehicle one-to-one Pickup and Delivery Problem with Split Loads (MPDPSL) and the Multi-Vehicle Profitable Pickup and Delivery Problem (MVPPDP). Both are NP-hard problems and important for various practical applications, including bulk product transportation by ships and bike-sharing systems. Three challenging vehicle routing attributes are combined in this study, one-to-one pickup and delivery, split loads, and selection of customers, which are known to require advanced local-search neighborhoods and exploration procedures. Initially, we developed a heuristic algorithm based on Iterated Local Search (ILS) and Random Variable Neighborhood Descent (RVND) to solve the MPDPSL. The core of this algorithm consists of a new large-neighborhood search that efficiently deals with pickup and delivery locations and split loads reducing the problem of finding the best insertion combination of a pickup and delivery pair into a route to a resource-constrained shortest path problem, which is solved via dynamic programming. Next, non-dominated labels are obtained for each separate route and a knapsack problem is solved to find the best insertion plan considering the whole solution. Computational experiments on benchmark instances showed the great performance of the proposed algorithm, finding new best solutions on 92 out of 93 instances and also outperforming previous methods in average. New instances for the MPDPSL and also new results are reported, producing consistently good solution on several runs. The good results found on the MPDPSL motivated us to adapt this algorithm for solving the MVPPDP. Then, again, an ILS combined with a RVND was used, but now the idea was to allow the algorithm to accept infeasible solutions during its search process. In order to reduce the search space of infeasible solutions, a granular local search concept was also incorporated into the algorithm. The proposed algorithm had a great performance on instances from the literature, finding 20 better or equal results on 36 instances than previous methods. Keywords: vehicle routing, one-to-one pickup and delivery; split loads; customer selection; metaheuristics; large neighborhoods Resumo Esta tese trata dois problemas de coleta e entrega um-para-um: o Problema de Roteamento de Veculos com Coleta e Entrega Fracionria Um-para-um (PRVCEFU) e o Problema de Roteamento de Veculos com Coleta e Entrega Premiada (PRVCEP). Ambos so problemas NP-difceis e importantes para vrias aplicaes prticas, incluindo o transporte de produtos a granel por navios e sistemas de compartilhamento de bicicletas. Trs atributos desafiadores de roteamento de veculos so combinados neste estudo, coleta e entrega um-para-um, coleta e entrega fracionria e seleo de clientes, que so conhecidos por exigirem vizinhanas avanadas de buscas locais e procedimentos de explorao eficientes. Inicialmente, desenvolvemos um algoritmo heurstico baseado na metaheurstica Iterated Local Search (ILS) e no mtodo Random Variable Neighborhood Descent (RVND) para resolver o PRVCEFU. O ncleo deste algoritmo consiste em uma busca em grande vizinhana que lida eficientemente com localizaes de coleta e entrega e cargas fracionrias, reduzindo o problema de encontrar a melhor combinao de insero de um par de coleta e entrega em uma rota para um problema de caminho mnimo com recursos limitados, que resolvido via programao dinmica. Em seguida, os rtulos no dominados so obtidos para cada rota separada e um problema da mochila resolvido para encontrar o melhor plano de insero, considerando a soluo completa. Experimentos computacionais em instncias da literatura mostraram o desempenho competitivo do algoritmo proposto, encontrando novas melhores solues em 92 de 93 casos e tambm superando os mtodos anteriores na mdia. Novas instncias para o PRVCEFU e tambm novos resultados so relatados, produzindo consistentemente boas solues em vrias execues. Os bons resultados encontrados no PRVCEFU nos motivaram a adaptar este algoritmo para resolver o PRVCEP. Ento, novamente, um ILS combinado com o RVND foi usado, porm agora a ideia foi permitir que o algoritmo aceitasse solues inviveis durante seu processo de busca. A fim de reduzir o espao de busca de solues inviveis, o conceito de busca local granular tambm foi incorporado ao algoritmo. O algoritmo proposto teve um desempenho competitivo em instncias da literatura, encontrando 20 resultados melhores ou iguais em 36 instncias do que os mtodos anteriores. Palavras-chave: roteamento de veculos; coleta e entrega um-para-um; coleta e entrega fracionria; seleo de clientes; metaheursticas; grandes vizinhanas JKLTUV*+-34efgwȺhnLCJOJQJ^JaJhnLOJQJ^J hnL^J#hnLB*CJOJQJ^JaJph!!!)hnL5B*CJOJQJ\^JaJph!!!KLUV+,-45fg$a$<P1h:pnL. 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 0Ttulo1 $xCJOJQJ^JaJ8B8 0 Body Text d T/T u[0Body Text Char CJKHOJQJ^JaJnHtH$/"$ 0List<"2< 0Caption  $xx6],B, 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]  QnL@@@UnknownG*Ax Times New Roman5Symbol3" ArialI xP!Liberation SerifG& xP!Liberation SansACambria Math" gJUGgJUG  0 $PQ!xxJTtulo: AN EFFICIENT HEURISTIC FOR ONE-TO-ONE PICKUP AND DELIVERY PROBLEMSHelioHelioOh+'0 8 HT x  LTtulo: AN EFFICIENT HEURISTIC FOR ONE-TO-ONE PICKUP AND DELIVERY PROBLEMSHelioNormal_WordconvHelio2Microsoft Office Outlook@@J;@J; ՜.+,04 hp|   KTtulo: AN EFFICIENT HEURISTIC FOR ONE-TO-ONE PICKUP AND DELIVERY PROBLEMS Title  !"#$%'()*+,-0Root Entry F8bJ21TableWordDocument> SummaryInformation(DocumentSummaryInformation8&CompObjy  F'Microsoft Office Word 97-2003 Document MSWordDocWord.Document.89q  F#Documento do Microsoft Office Word MSWordDocWord.Document.89q