аЯрЁБс>ўџ 02ўџџџ/џџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџьЅСq`№ПSbjbjqPqP*&::SџџџџџџЄііііііі NNNN Z Ыі‚‚‚‚‚‚‚‚JLLLLLL$Сh)Xpі‚‚‚‚‚pіі‚‚…***‚і‚і‚J*‚J**іі*‚v @}˜ћDыЬNˆv*J›0Ы*ў*і* *‚‚‚pp‚‚‚Ы‚‚‚‚   D N   N   ііііііџџџџ Heuristic, Exact and Hybrid Approaches for Vehicle Routing Problems Abstract The Vehicle Routing Problem (VRP) is a classical combinatorial optimization problem that was proposed in the late 1950's and it is still one of the most studied in the field of Operations Research. The great interest in the VRP is due to its practical importance, as well as the difficulty in solving it. This work deals with heuristic, exact and hybrid approaches for solving different variants of the VRP, namely: Capacitated VRP (CVRP), Open VRP (OVRP), Asymmetric CVRP (ACVRP), VRP with Simultaneous Pickup and Delivery (VRPSPD), VRP with Mixed Pickup and Delivery (VRPMPD), TSP with Mixed Pickup and Delivery (TSPMPD), Multi-Depot VRP (MDVRP), Multi-Depot Vehicle Routing Problem with Mixed Pickup and Delivery (MDVRPMPD) and Heterogeneous Fleet VRP (HFVRP). An extensive literature review was performed for all these variants, focusing on the main contributions of each work. Commodity flow formulations for the VRPSPD/VRPMPD are theoretically examined and their practical performance are measured by a Branch-and-Cut algorithm. New lower bounds were produced for both VRPSPD and VRPMPD instances with up to 200 customers, including proven optimal solutions for 30 open problems. A general heuristic algorithm is proposed for solving the VRPs considered here. The algorithm, called ILS-RVND, is based on the Iterated Local Search (ILS) metaheuristic and it makes use of a Variable Neighborhood Descent with Random neighborhood ordering (RVND) in the local search phase. The initial solutions are generated using simple insertion procedures. The RVND is respectively composed of 9 inter-route and 6 intra-route neighborhood structures. A total of 4 perturbation mechanisms were implemented. The developed algorithm was tested in 586 test-problems and the results obtained were, on average, highly competitive. Further research steps are also discussed, including the development of a general hybrid algorithm for VRPs and a enhanced exact procedure for improving the lower bounds of the VRPSPD/VRPMD instances. Lucas de Oliveira Bastos Abordagens Heurэsticas, Exatas e Hэbridas para Problemas de Roteamento de Veэculos Resumo O Problema de Roteamento de Veэculos (PRV) щ um problema clсssico de otimizaчуo combinatѓria proposto no final da dщcada de 1950, sendo ainda um dos mais estudados na сrea de Pesquisa Operacional. O elevado interesse no PRV щ devido a sua importтncia prсtica, bem como a dificuldade em resolvъ-lo. Este trabalho trata de abordagens heurэsticas, exatas e hэbridas para diferentes variantes do PRV, a saber: PRV Capacitado (PRVC), PRV com Rotas Abertas (PRVRA), PRV Capacitado e Assimщtrico (PRVCA), PRV com Coleta e Entrega Simultтnea (PRVCES), PRV com Coleta e Entrega Mista (PRVCEM), Problema do Caixeiro Viajante com Coleta e Entrega Mista (PCVCEM), PRV com Mњltiplos Depѓsitos (PRVMD), PRV com Coleta e Entrega Mista e Mњltiplos Depѓsitos (PRVCEMMD) e PRV com Frota Heterogъnea (PRVFH). Uma extensa revisуo da literatura foi efetuada para todas estas variantes, dando destaque as principais contribuiчѕes de cada trabalho. Formulaчѕes baseadas em fluxo em rede para o PRVCES/PRVCEM sуo teoricamente examinadas e seus desempenhos prсticos sуo medidos por meio de um algoritmo Branch-and-Cut. Novos limites inferiores foram produzidos tanto para PRVCES como para o PRVCEM para instтncias com atщ 200 clientes, incluindo soluчѕes ѓtimas provadas para 30 problemas em aberto. Um algoritmo heurэstico щ proposto para resolver os PRVs aqui considerados. O algoritmo, denominado, ILS-RVND, щ baseado na metaheurэstica Iterated Local Search (ILS) que faz uso de procedimento inspirado no mщtodo Variable Neighborhood Descent com ordem aleatѓria na escolha das vizinhanчas (RVND) na fase de busca local. As soluчѕes iniciais sуo geradas por meio de simples procedimentos de inserчуo. O RVND щ composto de 9 estruturas de vizinhanчa entre-rotas e 6 intra-rotas. Um total de 4 mecanismos de pertubaчѕes foram implementados. O algoritmo desenvolvido foi testado em 586 problemas-teste e os resultados obtidos foram, em mщdia, altamente competitivos. Os prѓximos passos da pesquisa tambщm sуo discutidos, incluindo o desenvolvimento de um algoritmo hэbrido para VRPs e um procedimento exato mais elaborado para melhorar os limites inferiores das instтncias do PRVCES/PRVCEM. Data/hora 03 de novembro рs 14:00. Banca examinadora Examinadores internos Luiz Satoru Ochi – UFF (presidente) Eduardo Uchoa – UFF Carlos Alberto de Jesus Martinhon – UFF Examinadores externos Reinaldo Morabito – UFSCar Lucэdio dos Anjos Formiga Cabral – UFPB DFO3K_ВДЛѓCYЌFPk}~”ї SюубуЭЩОЩГЩЌЩЌЩЌЩЁЩЁЩšЩšЩ hQIU5\hQIU5CJ\aJ hQIU6]hQIU5CJ\aJhQIU5CJ \aJ hQIUhАyа"hАyаhQIU5CJ\aJmH sH hАyаhQIUmH sH "hАyаhQIU5CJ \aJ mH sH DEFOPQ123LMNOPQRSTUVWXYZ[\]^њѕѕњѕѕѕѕѕѕѕѕѕѕѕѕѕѕѕѕѕѕѕѕѕѕѕѕ$a$$a$Sў^_ВГДЛМН23456789:;<=>?@ABCDEFњѕњњѕњњњњњњњњњњњњњњњњњњњњњњњ$a$$a$FPQjk}~”•ЙЮії )QRSњњњњњњњњњњњњњњњњњњ$a$(А‚. АЦA!Аn"Аn#n$n%ААаАа а†œ^@ёџ^ Normal1$*$/B*OJQJCJmHsHKHPJ^JaJ_H9tH9>A@ђџЁ> Fonte parсg. padrуoXi@ѓџГX  Tabela normal :V і4ж4ж laі ,k@єџС, Sem lista NўON Tэtulo1 Є№Єx$OJQJCJPJ^JaJ@B@@ Corpo de texto ЄЄx&/@& ListaFўO"F Legenda1 ЄxЄx $CJ6aJ],ўO2, Эndice $S&џџџџDEFOPQ123LMNOPQRSTUVWXYZ[\]^_ВГДЛМН23456789:;<=>?@ABCDEFPQjk}~”•ЙЮії )QRU˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€S^FSS-1œЯгEK›ЅЫеѓ  ь № 4BCK—˜ЄЅЌ{†ДПСХš ЁЅця)0U$3ий3L і  - / `aЄЅchU333_UEKUхQIUАyаџ@€KKРQAKKS@@џџUnknownџџџџџџџџџџџџG‡z €џTimes New Roman5€Symbol3& ‡z €џArial?& џ>чџ§R! џ€DejaVu Sans"Aˆ ХhйЅъftGмw ƒ мw ! 24JJ P №џџџџџџџџџџџџџџџџџџџџџАyаВџџAnand SubramanianTeresaўџр…ŸђљOhЋ‘+'Гй0x˜ЄАЬиь ќ ( 4 @ LX`hpфAnand Subramanian Normal.dotTeresa2Microsoft Office Word@@@ўLЧОpЫ@vязDыЬмwўџеЭеœ.“—+,љЎ0ш hp|„Œ” œЄЌД М ЩфUFF  J'  Tэtulo ўџџџўџџџ !"#$%&ўџџџ()*+,-.ўџџџ§џџџ1ўџџџўџџџўџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџRoot Entryџџџџџџџџ РFЎІћDыЬ3€1TableџџџџџџџџWordDocumentџџџџџџџџ*&SummaryInformation(џџџџDocumentSummaryInformation8џџџџџџџџџџџџ'CompObjџџџџџџџџџџџџuџџџџџџџџџџџџџџџџџџџџџџџџўџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџўџ џџџџ РF#Documento do Microsoft Office Word MSWordDocWord.Document.8є9Вq