аЯрЁБс>ўџ ')ўџџџ&џџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџьЅСq`№ПЯbjbjqPqP4::Я џџџџџџЄ(ЌЌЌЌ И (ќаааааааа„††††††$ hi 4ЊаааааЊааПdddа:аа„dа„dddаФ РИG]ŽеЌ :d„е0d D d d dаааЊЊZ ааааааа(((„Ќ(((Ќ(((џџџџ Resumo: Problemas de otimizaчуo sуo encontrados em diversos setores da produчуo industrial, buscando em geral minimizar os custos e maximizar os lucros. No contexto das Cidades Inteligentes, se torna prioridade a transparъncia para o cidadуo e uma logэstica efetiva de transporte de pessoas e bens de consumo, motivando uma sщrie de propostas acadъmicas para o tema. O estudo desses problemas щ essencial para se manter a competitividade de cadeias produtivas, tambщm sendo um desafio a tarefa de encontrar uma soluчуo de boa qualidade em um tempo computacional baixo. De forma especэfica, a logэstica tъm sido bastante estudada devido a seu grande nњmero de aplicaчѕes prсticas e, neste sentido, este trabalho explora o estudo de dois problemas de transportes. O Problema de Caminho com Coleta de Prъmios, consiste em encontrar um ($s$, $t$)-caminho que minimiza a soma dos pesos de suas arestas (tempo total de transporte) menos o prъmio total dos nѓs em tal caminho. Por sua vez, para o Problema de Roteamento de Veэculos para o Transporte de Funcionсrios, deve-se minimizar os custos de transporte e, respeitar em contrapartida, as restriчѕes de qualidade de serviчo para os funcionсrios. Ambos os problemas estуo presentes no nњcleo de diversas aplicaчѕes relevantes em сreas como Telecomunicaчѕes, Transporte Pњblico e Manutenчуo de Equipamentos. Neste trabalho serуo exploradas diferentes tщcnicas de resoluчуo que vуo desde mщtodos exatos atщ heurэsticas inteligentes. Palavras-chave: Coleta de Prъmios; Roteamento de Veэculos; Treewidth. Abstract: Optimization problems are found in different sectors of industrial production where it is desired to minimize costs and maximize profits. In the context of Smart Cities, transparency for citizens, and effective logistics for the transportation of people and consumer goods becomes a priority, motivating a series of academic proposals on the subject. The study of these problems is essential for maintaining the competitiveness of supply chains; however, the task of finding a good quality solution in a short computational time is challenging. At this point, logistics have been extensively studied due to their large number of practical applications and, in this sense, this work explores the study of two transportation problems. The Prize-Collecting Path Problem consists of finding a ($s$, $t$)-path that minimizes the sum of its edge weights (total transportation time) minus the total prize collected on nodes of that path. In turn, for the Vehicle Routing Problem for Transportation of Employees, the overall costs should be minimized according to the quality of service constraints defined for the employees. Both problems are present at the core of several relevant applications in areas such as Telecommunications, Public Transportation, and Equipment Maintenance. In this work, different resolution techniques will be explored, ranging from exact methods to intelligent heuristics. Keywords: Prize-collecting; Vehicle Routing Problem; Treewidth.   Щ и й ˜Я№ужу№жуЦуВž|ž| hфЬh7L-OJQJ^JmH sH  hфЬhфЬOJQJ^JmH sH &hфЬh7L-5OJQJ\^JmH sH &hфЬhфЬ5OJQJ\^JmH sH hфЬh7L-6OJQJ]^JhфЬhфЬOJQJ^JhфЬh7L-OJQJ^JhфЬh7L-5OJQJ\^J  Ш Щ ŽЯњњњњњњњњњњњњ$a$ Я§20p€1XА‚. АЦA!Аn"Аn#n$n%ААаАа а†œn@ёџn Normal1$*$7$5$3$A$3B*OJQJCJmHnHsHKHPJtH^JaJ_H9>A@ђџЁ> Fonte parсg. padrуoXi@ѓџГX  Tabela normal :V і4ж4ж laі ,k@єџС, Sem lista NўON Heading Є№Єx$OJQJCJPJ^JaJFB@F Corpo de textodЄЄŒ*/@* Lista^JH"@"H Legenda ЄxЄx $CJ6^JaJ].ўO2. Index $^JЯ џџџџ ШЩŽ  б ˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€Я Я Я эїьі Ф Э б "Qe'.ЕЛб 3б б х7L-фЬџ@€††lXššš††Я @@џџUnknownџџџџџџџџџџџџG‡: џTimes New Roman5€Symbol3& ‡: џArialIџрџxP!ПLiberation SerifiAR PL SungtiL GBTimes New RomanILohit DevanagariG& џрџxP!ПLiberation Sans"Aˆ Хh1йyЇŸъzGиї ƒиї ! 24Щ Щ  P №џџџџџџџџџџџџџџџџџџџџџфЬВџџHelioўџр…ŸђљOhЋ‘+'Гй0d˜ЄАМШи шє   , 8DLT\фNormalHelio2Microsoft Office Word@FУ#@@>uе@Т3]Žеиї ўџеЭеœ.“—+,љЎ0ш hp|„Œ” œЄЌД М ЩфЩ ц  Tэtulo ўџџџўџџџўџџџ !"#$%ўџџџ§џџџ(ўџџџўџџџўџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџRoot Entryџџџџџџџџ РFАJ]Žе*€1TableџџџџџџџџWordDocumentџџџџџџџџ4SummaryInformation(џџџџDocumentSummaryInformation8џџџџџџџџџџџџCompObjџџџџџџџџџџџџuџџџџџџџџџџџџџџџџџџџџџџџџўџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџўџ џџџџ РF#Documento do Microsoft Office Word MSWordDocWord.Document.8є9Вq