Orientador: Walter de Lazaro / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia de Campinas / Made available in DSpace on 2018-07-17T00:23:33Z (GMT). No. of bitstreams: 1 Yamakami_Akebo_D.pdf: 2084670 bytes, checksum: db9f26d6a2d936c43b2d57b704184b48 (MD5) Previous issue date: 1977 / Resumo: Este trabalho tem como objetivo estudar os modelos mais conhecidos de alocação de viagens. São estudadas as principais variáveis envolvidas nos problemas de alocação de viagens, como também são desenvolvidos algoritmos de procura de caminhos mínimos que consideram as penalizações de conversão. São feitas as formulações matemáticas dos problemas de alocação de viagens que verificam os princípios de Wardrop, e são apresentados diversos métodos de alocação, tanto iterativos como de carregamento progressivo, derivados do princípio "egoísta". É apresentado também o modelo probabilístico desenvolvido por R.B. Dia1. São feitas aplicações dos modelos a uma rede não saturada da região de Augusta da cidade de são Paulo, e a uma rede hipotética saturada. Frente aos resultados obtidos os algoritmos de alocação de viagens e os algoritmos de procura de caminhos mínimos que consideram as penalizações de conversão são ana1izados e comparados. / Abstract: Not informed. / Doutorado / Doutor em Engenharia Elétrica

Orientador: Orlando Lee / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-22T15:27:35Z (GMT). No. of bitstreams: 1 Curi_RafaelLima_M.pdf: 1469554 bytes, checksum: 8367cf52c9256338ee2963b9a9cdf41d (MD5) Previous issue date: 2013 / Resumo: Neste trabalho estudamos Jogos de Roteamento. Esta subclasse de jogos e uma das mais estudadas na literatura e permite modelar de forma relativamente simples vários cenários realistas. Por exemplo, tráfego de veículos em rodovias, transporte de mercadorias, redes de telefonia, redes de computadores como a Internet, etc. Analisamos as principais variantes de jogos de roteamento, destacando suas diferenças. Comparamos jogos atômicos versus jogos não-atômicos, jogos com fluxo divisível versus jogos com fluxo indivisível, jogos com demanda uniforme versus jogos com demanda genérica e jogos com redes específicas versus jogos com redes genéricas. Focamos nosso estudo na existência, unicidade e quantificação da ineficiência de equilíbrios que emergem do comportamento independente e egoísta dos jogadores. Estudamos o equilíbrio de Wardrop para jogos não-atômicos e o equilíbrio de Nash para jogos atômicos. Na literatura, notamos que a existência e unicidade de um equilíbrio dependem basicamente de três fatores: pressupostos nas funções que definem os custos dos segmentos de uma rota, tipo dos jogadores (atômicos ou não-atômicos, com demandas iguais ou diferentes) e topologia da rede. Apresentamos também os principais resultados de ineficiência obtidos para as métricas Preço da Anarquia (PoA) e Limite de Bicritério. Nos resultados que vimos, observamos que jogos não-atômicos possuem um PoA menor que o de jogos atômicos, jogos com fluxo divisível possuem um PoA menor que o de jogos com fluxo indivisível e jogos com demanda uniforme um PoA menor que o de jogos com demanda genérica / Abstract: In this work, we study Routing Games. This subclass of games is one of the most studied in the literature and allows us to model several realistic scenarios, in a relatively simple way. For instance, road traffic, freight transportation, telephone networks, computer networks like the Internet, etc. We analyze the main variants of routing games, emphasizing their differences. We compare atomic games versus nonatomic games, unsplittable flow games versus splittable flow games, unweighted games versus weighted games and specific network games versus generic network games. We focus our study on the existence, uniqueness and quantification of the inefficiency of equilibria that emerge from the independent and selfish behavior of the players. We study the Wardrop equilibrium for nonatomic games and the Nash equilibrium for atomic games. In the literature, we note that the existence and uniqueness of an equilibrium depends basically on three factors: assumptions on the functions that define the costs of the segments of a route, type of the players (atomic or nonatomic, with equal or different demands), and network topology. We present the main results of inefficiency obtained for the metrics Price of Anarchy (PoA) and Bicriteria Limit. In the results we have considered, we noticed that nonatomic games have lower PoA than the atomic ones, splittable flow games have lower PoA than the unsplittable flow ones, and unweighted games have lower PoA than the weighted ones / Mestrado / Ciência da Computação / Mestre em Ciência da Computação