[pt] Problemas de multifluxos surgem como modelos básicos no contexto de várias aplicações de fluxos em redes, tais como redes de telecomunicações, redes de transporte e logística. Em tais aplicações, os fluxos que atravessam a rede compartilham simultaneamente os mesmos recursos disponíveis e são definidos por suas próprias restrições. A cada uma das arestas ligando os pontos da rede está associado um custo, fixo ou proporcional à sua utilização. Este trabalho trata problemas de projeto de redes multifluxos, em que os custos estão associados às capacidades instaladas nas arestas. Particularmente, será estudado o caso em que a função de custo nas arestas possui o comportamento de uma função escada crescente e descontínua, para o qual métodos exatos de resolução são ineficientes. Métodos heurísticos são propostos para a resolução aproximada do problema e sintetizados em um algoritmo de multi-partida com memória adaptativa. Um mecanismo de intensificação, conhecido na literatura como construção de vocabulário, é também explorado e aplicado. Finalmente, experimentos computacionais são realizados e o método de resolução proposto é analisado quanto aos seus resultados e os resultados obtidos pelo método de resolução proposto são analisados. O método obtém as melhores soluções conhecidas para algumas instâncias da literatura. / [en] Multicommodity flow problems arise widely as basic models in the context of network flows applications such as telecommunication networks, transportation problems, and logistic. In these applicatons, the flows that cross the networks share the same avaiable resources simultaneously and are defined by their own constraints. Each edge connecting two nodes in the network has an associated cost that is either fixed or proportional to its use. This work focuses on a network design problem in which the cost are associated with the capacities installed in the edges. Particularly, the network design problem studied has discrete and step increasing cost functions on the edges, for which exact methods are inefficient. Heuristics are proposed for the approximate memory algorithm. An intensification mechanism, known in the literature as vocabulary building, is also explored and applied. Finally, computational experiments are performed and the results obtained with the proposed solution method are evaluated. The method obtains the best known solutions for some instances in the literature.

Vehicular Ad hoc NETworks (VANETs) are a subclass of Mobile Ad hoc NETworks and represent a relatively new and very active field of research. VANETs will enable in the near future applications that will dramatically improve roadway safety and traffic efficiency. There is a need to increase traffic efficiency as the gap between the traveled and the physical lane miles keeps increasing. The Dynamic Traffic Assignment problem tries to dynamically distribute vehicles efficiently on the road network and in accordance with their origins and destinations. We present a novel dynamic decentralized and infrastructure-less algorithm to alleviate traffic congestions on road networks and to fill the void left by current algorithms which are either static, centralized, or require infrastructure. The algorithm follows an online approach that seeks stochastic user equilibrium and assigns traffic as it evolves in real time, without prior knowledge of the traffic demand or the schedule of the cars that will enter the road network in the future. The Reverse Online Algorithm for the Dynamic Traffic Assignment inspired by Ant Colony Optimization for VANETs follows a metaheuristic approach that uses reports from other vehicles to update the vehicle’s perceived view of the road network and change route if necessary. To alleviate the broadcast storm spontaneous clusters are created around traffic incidents and a threshold system based on the level of congestion is used to limit the number of incidents to be reported. Simulation results for the algorithm show a great improvement on travel time over routing based on shortest distance. As the VANET transceivers have a limited range, that would limit messages to reach at most 1,000 meters, we present a modified version of this algorithm that uses a rebroadcasting scheme. This rebroadcasting scheme has been successfully tested on roadways with segments of up to 4,000 meters. This is accomplished for the case of traffic flowing in a single direction on the roads. It is anticipated that future simulations will show further improvement when traffic in the other direction is introduced and vehicles travelling in that direction are allowed to use a store carry and forward mechanism. / Includes bibliography. / Dissertation (Ph.D.)--Florida Atlantic University, 2016. / FAU Electronic Theses and Dissertations Collection

Submitted by Filipe dos Santos (fsantos@pucsp.br) on 2018-10-19T11:51:51Z No. of bitstreams: 1 Rafael Emídio Murata Rodrigues.pdf: 1071545 bytes, checksum: 468e0f7e27e278e12eed0dd52f4198cc (MD5) / Made available in DSpace on 2018-10-19T11:51:51Z (GMT). No. of bitstreams: 1 Rafael Emídio Murata Rodrigues.pdf: 1071545 bytes, checksum: 468e0f7e27e278e12eed0dd52f4198cc (MD5) Previous issue date: 2018-08-30 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / In our lives, we constantly move in streets and neighborhoods. In general, we consider time and (or distance) when planning the route. However, their solutions may face complex problems arising from the different possibilities of solutions. Similar to route planning, the Vehicle Routing Problem was introduced by George B. Dantzig and John H. Ramser in 1959 and consists of delivering gasoline to several fuel stations; at first a mathematical proposal, later became an algorithmic approach, for planning of routes of delivery of products in an optimized way (searching the "shortest path"). Although, during the search of shortest path, they are limited to the use of the streets. In this context emerges the Human Routing Problem, such an approach is not limited to streets, but makes use of all possible paths, by vehicles and humans. Such a problem can be observed in route planning at airports, museums and a supply chain company that wants to optimize the route of delivery of its products and increase customer satisfaction. Based on the Vehicle Routing Problem, the Human Routing Problem will be proposed. Its problematic will be demonstrated in a prototype, capable of assisting in the planning of human routes and three use cases. Ideas of Human Routing Problem had inspiration in the collective foraging insects / Na nossa vida, nos locomovemos constantemente em ruas e bairros. Em geral, consideramos o tempo e (ou a distância), ao planejar a rota. Contudo, suas soluções podem enfrentar problemas complexos, decorrentes das diversas possibilidades de soluções. Semelhante a planejamento de rotas, o Problema de Roteamento de Veículos foi introduzido por George B. Dantzig, e John H. Ramser em 1959 e consiste em entregar gasolina diversos postos de combustível; a princípio uma proposta matemática, mais tarde tornou-se uma abordagem algorítmica, para planejamento de rotas de entrega de produtos de forma otimizada (buscando o “menor caminho”). Embora, durante a busca de menor caminho, limitam-se ao uso de ruas. Neste contexto emerge o Problema de Roteamento Humano, tal abordagem não se limita a ruas, mas faz uso de todos os caminhos possíveis, por veículos e humanos. Tal problemática, pode ser observada nos planejamentos de rotas em aeroportos, museus e em uma empresa de supply chain que deseja otimizar a rota de entrega dos seus produtos, e aumentar a satisfação dos seus clientes. Tomando como base central, o Problema de Roteamento de Veículos será proposto o Problema de Roteamento Humano. Sua problemática, será demonstrado em um protótipo, capaz de auxiliar no planejamento de rotas humanas e três casos de uso. As ideias do Problema de Roteamento Humano tiveram inspiração no forrageamento dos insetos coletivos

Submitted by Maria Cristina (library@lncc.br) on 2017-05-02T18:23:10Z No. of bitstreams: 1 Tese_Machado.pdf: 522761 bytes, checksum: 871b43ac7f8d7aae60a30b8371cf5898 (MD5) / Approved for entry into archive by Maria Cristina (library@lncc.br) on 2017-05-02T18:23:21Z (GMT) No. of bitstreams: 1 Tese_Machado.pdf: 522761 bytes, checksum: 871b43ac7f8d7aae60a30b8371cf5898 (MD5) / Made available in DSpace on 2017-05-02T18:23:32Z (GMT). No. of bitstreams: 1 Tese_Machado.pdf: 522761 bytes, checksum: 871b43ac7f8d7aae60a30b8371cf5898 (MD5) Previous issue date: 2016-02-22 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (Capes) / The inverse potential problem consists in reconstructing an unknown source with support in a geometrical domain from a single boundary measurement. In order to deal with this severely ill-posed inverse problem, we rewrite it as an optimization problem where a Kohn-Vogelius-type functional measuring the misfit between the solutions of two auxiliary problems is minimized. One auxiliary problem contains information on the boundary measurement while the other one corresponds to the boundary excitation. The solutions of the auxiliary problems coincide once the inverse problem is solved. In order to minimize the Kohn-Vogelius criterion, its total variation with respect to a set of concentrated sources perturbations is explicitly evaluated. Then, a new method for solving the inverse potential problem based on the expression obtained is devised. Finally, some numerical results are presented in order to show the effectiveness of the devised reconstruction algorithm. / O problema inverso do potencial consiste em reconstruir uma fonte desconhecida com suporte em um domínio geométrico a partir de uma única medição sobre a fronteira. Se o domínio de definição do problema inverso for limitado, a medição é total e, caso este domínio seja semi-infinito, a medição é parcial. No caso deste trabalho em particular, o termo fonte buscado é constituído de cargas pontuais e as informações utilizadas na reconstrução são os dados de Cauchy. Para tratar este problema mal posto, a estratégia aqui adotada consiste em reescrevê-lo como um problema de otimização, onde um funcional de forma baseado no critério de Kohn-Vogelius é minimizado. Este funcional mede a diferença entre as soluções de dois problemas auxiliares, onde um deles contém a informação relativa à leitura no contorno enquanto o outro é munido com a informação correspondente à excitação no contorno. As soluções dos problemas auxiliares coincidem quando se está sobre a solução do problema inverso. Para minimizar o critério de Kohn-Vogelius, sua sensibilidade com respeito a um conjunto de fontes concentradas é avaliada explicitamente. Com base na expressão obtida, constrói-se um novo método não iterativo para resolver o problema inverso do potencial em um único passo e sem a necessidade de qualquer regularização. Finalmente, alguns resultados numéricos são apresentados a fim de mostrar a efetividade do algoritmo de reconstrução proposto.

O presente trabalho desenvolve uma extensão do problema de corte de estoque unidimensional no caso em que a demanda pelos vários tipos de itens não é exatamente conhecida. Para considerar a aleatoriedade, foi proposto um modelo de programação estocástica de dois estágios com recurso. As varáveis de primeiro estágio são os números de barras cortadas por padrão de corte, e as variáveis de segundo estágio, os números de itens produzidos em escassez e em escassez. O objetivo do modelo é minimizar o custo total esperado. Para resolver a relaxação linear do modelo, foram propostos um método exato baseado no método Simplex com geração de colunas e uma estratégia heurística, que considera o valor esperado da demanda na resolução do problema de corte de estoque. As duas estratégias foram comparadas, assim como a possibilidade de resolver o problema de corte ignorando as incertezas. Finalmente, observou-se que é mais interessante determinar o valor ótimo do modelo recurso quando o problema sofre mais influência da aleatoriedade / This paper presents an integer linear optimization model of large scale for the one-dimensional cutting stock problem in the case which a demand is considered a random variable. To take this randomness into account, the problem was formulated as a two-stage stochastic linear program with recourse. The first stage decision variables are given by the number of bars that has to be cut according to each pattern, and the second stage decision variables by the number of holding items or backordering items production. The model objective is minimizes the total expected cost. We propose two methods to solve the model linear relaxation, one of them it is a Simplex-based method with column generation. The second method is a heuristic strategy that adopted the expected value of demand. We compare both strategies and the possibly of ignoring uncertainties on model. Finally, we observe that is much more interesting to determine the optimal recourse model solution when we have problems that are more afected by randomness

Uma representação retangular de um grafo plano G é uma representação de G, onde cada vértice é desenhado como um retângulo de modo que dois retângulos devem compartilhar algum segmento de seus lados se e somente se existe uma aresta em G entre os vértices correspondentes aos retângulos. Ainda, a representação de G deve formar um retângulo e não deve existir buracos, ou seja, toda região interna deve corresponder a algum vértice de G. Um desenho retangular de um grafo plano H é um desenho de H, onde todas as arestas são desenhadas como segmentos horizontais ou verticais. Ainda, todas as faces internas são retângulos e as arestas que incidem na face externa também formam um retângulo. Nesta dissertação, apresentamos os principais trabalhos existentes na literatura para problemas associados à representação retangular. Também apresentamos resultados para problemas associados ao desenho retangular. Por fim, apresentamos o algoritmo que desenvolvemos para determinar as coordenadas dos vértices de um desenho retangular quando a orientação das arestas já foram determinadas. / A rectangular representation of a plane graph G is a representation of G, where each vertex is drawn as a rectangle, such as two rectangles have to share some boundary if and only if exist an edge in G between the corresponding vertices. Also, the representation of G must form a rectangle and does not contain any holes, in other words, every point inside the formed rectangle must correspond to some vertex of G. A rectangular drawing of a plane graph H is a drawing of H, where all edges are drawn either in vertical or in horizontal. Also, every internal face is a rectangle and the edges which are incident in the external face define a rectangle. In this dissertation, we present the main studies in the literature for problems associated with the rectangular representation. We also present results for problems associated with rectangular drawing. Finally, we present the algorithm we developed to determine the coordinates of the vertices of a rectangular drawing when the orientation of the edges have been determined.

O Problema de Escalonamento de Médicos (Physician Scheduling Problem) consiste em atribuir tarefas a médicos num horizonte de planejamento respeitando regras laborais, contratuais e de preferências pessoais de modo a satisfazer a demanda de serviços de um hospital. O problema lida majoritariamente com o objetivo de maximizar o atendimento dos requisitos de preferência pessoal, respeitando as restrições laborais e organizacionais. Sobre esta classe de problemas, vários métodos de resolução e suas variantes têm sido propostos na literatura. Ademais, mais características têm sido agregadas ao problema, tornando-o mais complexo e deste modo fazendo-se mais necessária a aplicação de métodos mais elaborados para a sua resolução. Neste trabalho são estudados, reformulados e propostos métodos de resolução baseados em programação matemática para tratar o problema de escalonamento acíclico de médicos em departamento de emergência de hospitais. O primeiro modelo tem como objetivo a minimização da soma ponderada dos desvios das restrições de distribuição. O segundo modelo tem como objetivo, a minimização do máximo dos desvios obtidos nas restrições de distribuição, a fim de se obter escalas mais equilibradas entre os médicos. Foram também propostas heurísticas baseadas na formulação matemática cujos resultados não foram competitivos com as dos modelos. Os modelos foram testados sobre um conjunto de instâncias fictícias resultantes de uma mescla entre instâncias benchmark e características do problema. Os resultados computacionais demonstram que formulação ponderada obteve solução ótima para grande parte das instâncias, embora os limitantes inferiores tenham sido majoritariamente fracos. Em relação ao segundo modelo, soluções ótimas não foram obtidas e os limitantes inferiores foram igualmente fracos. Relativamente a qualidade das escalas, o segundo modelo teve melhor comportamento comparando ao modelo de somas ponderadas. Dada a qualidade das soluções, nota-se a viabilidade da solução baseada em técnicas de otimização em detrimento da manual, pois esta ainda é mais suscetível de erros e acarreta um alto tempo para obtenção de solução. / The Physician Scheduling Problem consists in task assignment to physicians in a planning horizon considering a set of organizational rules, work regulations and individual preferences in order to satisfy an hospital wards work demand. The aim is to find a schedule which maximizes the satisfaction of individual preferences requirements while meeting work regulations and organizational rules. A plethora of solution methods and its variants have been proposed in the literature to solve this class of problem. Moreover, more features have been aggregated to the problem turning it into a more complex and thus estimulating the application of more elaborated methods to its decision. In this work we study, reshape and propose decision methods based in mathematical programming to handle non-ciclic physician scheduling problem in emergency wards. The first formulation targets the minimization of the weighted sum of distribution constraints deviations. The second formulation targets the minimization of the maximum deviations obtained at the distribution constraints aiming more balanced schedules between the physicians. Mathematical formulation heuristics were also proposed and the findings were not satisfactory as they were not competitive with the model. Experiments with our models were performed over a set of dummy instances, as result a of a mixture of benchmark instances and the considered problems features. From our experiments we have found that optimal solutions were obtained through the weighted sum model, despite the poor lower bounds. On the other hand, for the second model, no optimal solution was found and poor lower bounds were similarly obtained. Regarding to the schedules quality, the min-max model had a better performance comparing to the weighted sum model. Given the solutions quality we can assume that optimization based techniques are sustainable comparing to manual, because the latter is prone to errors and omissions and also critical in terms of solutions achievement time.

Made available in DSpace on 2015-03-05T14:01:22Z (GMT). No. of bitstreams: 0 Previous issue date: 12 / Bolsa para curso e programa de Pós Graduação / Este trabalho aborda o uso de uma metaheurística populacional para a solução do problema de otimização conhecido, na Pesquisa Operacional, como Programação de Horário de Cursos Baseada em Currículos. O problema de Programação de Horário de Cursos Baseada em Currículos consiste na construção das grades de horário de cursos em instituição de ensino que indicam em quais períodos semanais cada disciplina destes cursos deverá ocorrer, alocando professores e salas e respeitando um conjunto de requisitos organizacionais, pedagógicos e pessoais. Este trabalho apresenta uma formulação matemática para o problema e especifica um algoritmo de solução baseado na técnica metaheurística Busca Dispersa, combinada com o método de Reconexão por Caminhos. Além disso, é apresentado o registro de testes realizados com instâncias de problemas utilizadas na International Timetabling Competition e também em um problema real de uma instituição local de esino superior. / This paper discusses the use of a populational metaheuristic to solve the optimization problem known in Operational Research, as Curriculum Based Timetabling. The Curriculum Based Timetabling problem is the construction of schedule of courses in educational institutions that indicate which weekly times each subject of these courses should occur, allocating rooms and teachers and a respecting a set of organizational, pedagogical and personal requirements. This paper presents a mathematical formulation for the problem and specify a solution algorithm based on the Scatter Search metaheuristic technique, combined with the method Path Relinking. Furthermore, it is present the record of tests with instances of problems used in the International Timetabling Competition and also a real problem of a local institution.

Submitted by William Justo Figueiro (williamjf) on 2015-07-27T20:23:06Z No. of bitstreams: 1 09d.pdf: 2136888 bytes, checksum: 8bc73fd7975259c3bc984b913580a5c1 (MD5) / Made available in DSpace on 2015-07-27T20:23:06Z (GMT). No. of bitstreams: 1 09d.pdf: 2136888 bytes, checksum: 8bc73fd7975259c3bc984b913580a5c1 (MD5) Previous issue date: 2013 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Com a expansão do transporte marítimo, passou a ser adotado o uso de contêineres para o transporte de cargas, sendo evidenciados alguns problemas. Dentre eles, um dos principais, é o problema de carregamento e descarregamento de contêineres em navios. O problema surge devido aos altos custos operacionais gerados a partir da movimentação de contêineres. Este problema é o foco desta pesquisa, que tem como objetivo principal elaborar planos de carga eficientes que gerem um número mínimo de movimentações de contêineres, nas operações de carga e descarga de navios-contêineres, diminuindo assim os custos de operação. Neste trabalho, é proposta a aplicação da metaheurística Algoritmo Genético e da metaheurística Enxame de Abelhas, resolvendo o problema através de uma codificação baseada em regras de carregamento e descarregamento. A codificação por regras é compacta e adequada, assegurando que as soluções do problema sejam factíveis e de simples representação, acelerando o processo de solução. Nos experimentos realizados, as duas metaheurísticas foram empregadas, assumindo diferentes configurações de regras, com o intuito de comparar o seu desempenho. A proposta de novas regras de carregamento e descarregamento, em complemento às existentes na literatura, trouxeram bons resultados. Desta forma, foram obtidas soluções de boa qualidade e melhores que aquelas encontradas na literatura que abordam o mesmo problema. / With the expansion of maritime transportation, the use of containers for goods transportation has increased, being evidenced some problems. Among these problems, the container ship stowage problem arose as one of the main problems due to the high operational costs related to movement of containers. This problem is the focus of this research, where the main objective is the formulation of stowage plans that generate a minimum number of container shiftings in the operations of loading and unloading performed in port calls of container ships. In order to determine a suitable stowage plan, the application of Genetic Algorithm and Bee Swarm Optimization metaheuristics are proposed to solve the problem by using a rule-based encoding for the solution. The solution encoding based on loading and unloading rules is compact and suitable, ensuring the feasibility of solutions and also the simple representation of it, speeding up the solution procedures. In the performed experiments, both metaheuristics were applied assuming different rules settings with the objective to compare each performance. The proposal of new rules of loading and unloading, in addition with those existing in literature, has produced good solutions. Thereby, good quality solutions were achieved and also better than that found in the literature which discuss the same problem

Submitted by Silvana Teresinha Dornelles Studzinski (sstudzinski) on 2015-11-04T15:30:21Z No. of bitstreams: 1 Kelly Cristina Ferreira Dias.pdf: 6056954 bytes, checksum: f38a4fe2aa64b584f392432c93244c7f (MD5) / Made available in DSpace on 2015-11-04T15:30:21Z (GMT). No. of bitstreams: 1 Kelly Cristina Ferreira Dias.pdf: 6056954 bytes, checksum: f38a4fe2aa64b584f392432c93244c7f (MD5) Previous issue date: 2015-07-29 / Nenhuma / O desempenho operacional das instituições hospitalares tem relação direta com a escala de trabalho das pessoas. Assim, a tarefa de construção das mesmas exige atenção a diversos detalhes para obtenção de bons resultados. É neste contexto que um modelo, computacionalmente viável, para a elaboração das escalas de trabalho de pessoal de enfermagem, capaz de gerar elementos para avaliação de sua influência no desempenho operacional do hospital, torna-se importante. A contribuição desta pesquisa é apresentar um modelo matemático, baseado em restrições que permitam a elaboração de escalas para equipes de enfermagem com suporte computacional. Além disso, o estudo apresenta elementos para avaliação do Quadro de Lotação da equipe de trabalho. A tarefa de escalar pessoal é responsável por consumir muito tempo e nem sempre garantir o cumprimento das legislações e normas vigentes, visto ser normalmente um processo manual, sem uso de ferramentas computacionais personalizáveis às particularidades de cada hospital. O estudo foi realizado a partir de dados levantados junto a Unidade de Internação de um hospital em Porto Alegre/RS. Foram obtidas, no estudo de campo, informações relativas às necessidades da escala de trabalho nesta realidade particular, além do levantamento de indicadores de desempenho. Foram realizados experimentos para avaliar a influência das variáveis de decisão e parâmetros do Algoritmo empregado para a obtenção da solução. Na validação do modelo foram utilizados casos de teste hipotéticos, baseados em dados reais levantados no estudo. Com a aplicação do modelo, as escalas de trabalho puderam ser obtidas de forma a atender as necessidades dos setores hospitalares proporcionando menor impacto no desempenho operacional do hospital. / The operating performance of hospitals have directly related of rostering colaboration. Thus, the construction of the same task requires attention to the many details to obtain good results. In this context, a model computationally feasible to prepare the rostering nursing, capable of generating elements to assess its influence on the hospital's operating performance, it is important. The contribution of this research is to present a formal mathematical model, based on restrictions to allow the construction of scheduling nursing with computer support. In addition, the study presents elements for evaluating the Board's work team Capacity. Personal climbing task is responsible for time-consuming and not always ensure compliance with existing laws and regulations, as it is usually a manual process, without the use of customizable computational tools to the particularities of each hospital. The study was conducted from data collected at the inpatient unit of a hospital in Porto Alegre/ RS. They were obtained from the information field study on working range of needs in this particular reality, beyond the performance indicators survey. Experiments were conducted to evaluate the effect of the decision variables and the influence of the parameters of the Evolutionary Algorithm in the final solution. To validate the model we used cases of hypothetical test, based on real data collected in the study. With the application of the model, working scales can be obtained to meet the needs of hospital departments providing less negative impact on the hospital's operating performancer.