[pt] Os problemas advindos da área de logística de transportes, em especial no que diz respeito ao uso racional de frotas de veículos, são amplamente estudados na área de otimização combinatória. A natureza intrinsicamente combinatorial desses problemas sugere que boa parte deles pode ser formulada e resolvida como um problema de programação linear inteira. Contudo, a maioria dos algoritmos atualmente disponíveis não consegue encontrar, em tempos computacionais aceitáveis, a solução ótima para instâncias de porte razoável. O sucesso desses algoritmos tem sido limitado, em parte devido ao fato dos mesmos não explorarem avanços recentes na área de programação linear inteira. Algumas dessas novas técnicas e suas aplicações a problemas de roteamento de veículos são o objeto de estudo desta dissertação. Primeiro são apresentadas as técnicas básicas de decomposição de problemas de programação linear e linear inteira e de geração de colunas. A resolução de problemas de programação linear inteira neste contexto é tratada em seguida, com a descrição do algoritmo branch-and-bound e das variações branch-and-cut, branch-and-price e branch-and- cut-and-price. Em seguida são descritos problemas de roteamento onde essa metodologia foi aplicada. Inicialmente, é apresentado o problema de roteamente do veículos com restrição de capacidade, o PRVC. Em seguida são apresentados problemas de roteamento de veículos com janela de tempo e frota heterogenea. Para cada problema, descrevemos como as técnicas descritas acima foram aplicadas e os resultados computacionais para um grande número de instâncias. Finalmente, no último capítulo, mostramos um caso real da aplicação do problema de roteamento de veículos com janela de tempo e frota heterogênea, que é o caso do problema de distribuição de jornais numa grande empresa de comunicação do Rio de Janeiro. / [en] Optimization techniques have an important role in Transportation Logistics. The combinatorial nature of several problems related to this area seggests integer programming as a natural approach to solve them. Nevertheless, there are many cases in which instances of reasonable size are still beyond the resolution capability of the algotithms presented in the literature. The sucess of the known algotithms have therefore been limited partly to the fact that most of them have not incorporated any recent relevant advances in the combinatorial optimization field. Some of these new techniques and their applications are the main subject of this dissertation. Firstly, basic decomposition techniques for linear and integer programming problems, as well as the relates column generation approach are addressed. This is followed by the presentation of a reformulation technique for linear and integer programming, which is alternative to the well known Dantzig-Wolfe master program. The new possibilities arousing from this approach are explored and the resulting consequences to the standard branch-and-bound algotithm and its variations branch-and- cut, branch-and-prince and branch-and-cut-and-price are presented. Later, routing problems where this methodology was applied were addressed with the capacitated vehicle routing problems - CVRP and followed by vehicle routing problems with time windows and heterogeneous fleet. For each problem, it is described how the techniques mentioned above were reported. Finally, in the last time windows and heterogeneous fleet, which is the case of a newspaper distribution in a major communication company in Rio de Janeiro.

Orientador: Luzenira Alves Brasileiro / Banca: Jairo Salim Pinheiro de Lima / Banca: Sérgio Antonio Röhm / Resumo: O sistema de transporte dos resíduos sólidos compreende o cálculo da frota necessária e a geração de itinerários. A roteirização de veículos pode ser realizada através de método empírico ou matemático. O método matemático pode ser manual ou computadorizado. O problema do transporte de resíduos sólidos urbanos é, geralmente, sanado através do método empírico; principalmente em cidades de pequeno porte. O objetivo deste trabalho é analisar o transporte de resíduos sólidos comerciais urbanos, através do método matemático computadorizado, utilizando Sistema de Informação Geográfica (SIG). O estudo de caso foi realizado para a cidade de Ilha Solteira - SP, que apresenta aproximadamente 24.000 habitantes. O método utilizado para análise do transporte de resíduos consiste em coleta de dados, caracterização do sistema atual, simulação do sistema utilizando SIG e análise dos resultados. Os dados foram coletados durante o período de julho a agosto de 2006. O sistema atual define a roteirização de veículos pelo método empírico e a frota é igual a 1 veículo, que visita 172 pontos comerciais. O veículo realiza 3 viagens/dia para suprir a demanda. Foram simulados cenários com locais de disposição atual, e mais 4 determinados por um modelo de escolha de locais. Os resultados mostram que há uma economia significativa de distância e tempo no roteamento pelo método computacional, em relação ao método empírico no estudo de caso realizado. O método computacional para roteirização dos veículos de coleta mostrou ser mais eficiente do que o método empírico. / Abstract: The system of transport of the solid residues understands the calculation of the necessary fleet and the generation of itineraries. The routing of vehicles can be carried through through empirical or mathematical method. The mathematical method can manual or be computerized. The problem of the transport of urban solid residues is, generally, cured through the empirical method; mainly in small cities. The objective of this work is to analyze the transport of urban commercial solid residues, through the computerized mathematical method, using of geographic information systems (GIS). The case study it was carried through for the city of Ilha Solteira - SP, that presents 24,000 inhabitants approximately. The method used for analysis of the transport of residues consists of collection of data, characterization of the current system, simulation of system using GIS and analysis of the results. The data had been collected during the period of July the August of 2006. The current system defines the routing of vehicles for the empirical method and the fleet is equal the 1 vehicle, that visits 172 points commercial. The vehicle carries through 3 trips/day to supply the demand. Scenes with places of current disposal had been simulated, and more 4 determined for a model of choice of places. The results show that it has a significant economy of distance and time in the routing for the computational method, in relation to the empirical method in the study of carried through case. The computational method for routing of the collection vehicles showed to be more efficient of the one than the empirical method. / Mestre

Made available in DSpace on 2014-06-11T19:28:21Z (GMT). No. of bitstreams: 0 Previous issue date: 2013-04-08Bitstream added on 2014-06-13T19:36:47Z : No. of bitstreams: 1 franco_mr_me_jabo.pdf: 520960 bytes, checksum: c2ef75b786c73ec01722d89761e3a7da (MD5) / O transporte de animais para o abate é considerada a etapa mais crítica dentro do manejo de pré-abate. Vários são os motivos que influenciam nos efeitos do transporte rodoviário de bovinos de corte e no bem-estar animal e na qualidade de carcaça. O objetivo deste estudo foi descrever os efeitos do transporte rodoviário no bem-estar e na qualidade da carcaça de bovinos de corte destinados ao abate. Foram realizadas avaliações em duas plantas frigoríficas, com 1.038 desembarques, 185 motoristas avaliados e com um total de 19.635 carcaças. Analisando-se os principais efeitos relacionados à caracterização do transporte rodoviário de bovinos em alguns indicadores de bem-estar animal estão relacionados as características das viagens (condição de conservação do veículo, condições das estradas, distância, espaçamento), do condutor (curso na área de bem-estar animal, idade, tempo de experiência em condução de bovinos) e dos animais (raça e sexo). Considerou como variáveis dependentes as frequências de animais deitados, de quedas no desembarque e de hematomas nas carcaças. Os resultados indicaram que todas as variáveis dependentes apresentaram algum efeito sobre o número de hematomas nas carcaças, a porcentagem de animais deitados durante a viagem e a porcentagem de quedas sofridas no desembarque. Destaca-se os efeitos da distância percorrida pelo veículo de transporte, o espaço linear do compartimento de carga por animal e o tempo de experiência e capacitação dos condutores como importantes fontes de variação. Além dessas, o modelo do veículo utilizado para o transporte dos animais, também se mostrou uma forte variável, embora não tenha sido como variável independente nos modelos, devido ao fato da definição do modelo a ser usado no transporte não ser aleatória, dificultando comparações... / Animal transportation is considered the most critical step in preslaughter beef cattle management. The aim of this study was to characterize the road transport of beef cattle and to analyses its impact on cattle welfare and carcass quality. The study was carried out in two slaughterhouses, by assessing the circumstances of 1,038 unloading procedures, interviewing 185 truck drivers and analyzing 19,635 carcasses. The following independent variables were recorded: 1.) vehicle (type and load compartment conditions), 2) road (distance traveled and road conditions), 3.) driver (age, years of experience in cattle transport and attendance to training courses), 4.) animal (breed and gender) and 5.) space available per animal in the load compartment. The dependent variables analyzed were 1.) frequency of animals lying down in the load compartment, 2.) number of falls at unloading and 3.) number of bruises on the carcasses. The results indicated that all dependent variables had some effect on the number of bruises on carcasses and percentages of animals lying down during the trip and of falls at unloading. The distance traveled, the space per animal in the load compartment and the drivers’ experience and attendance to capacitation courses were determined to be the most important sources of variation. In addition, the vehicle model, also showed a strong effect on the dependent variables, although the type of vehicle was not included as independent variable, due to the fact of the model definition used for cattle transport was not by random. We conclude that to assure good animal welfare standards during transport and to achieve better carcass quality it is necessary to improve the transport conditions and this can be achieved by using vehicles that offer less risk to the animals, training the truck drivers, and opting for short-distances

Made available in DSpace on 2014-06-11T19:29:13Z (GMT). No. of bitstreams: 0 Previous issue date: 2006-12-13Bitstream added on 2014-06-13T20:59:27Z : No. of bitstreams: 1 brito_raf_me_ilha.pdf: 1354209 bytes, checksum: 9f2f3580875f7b960861c38a486c01ae (MD5) / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / Fundação para o Desenvolvimento da UNESP (FUNDUNESP) / O sistema de transporte dos resíduos sólidos compreende o cálculo da frota necessária e a geração de itinerários. A roteirização de veículos pode ser realizada através de método empírico ou matemático. O método matemático pode ser manual ou computadorizado. O problema do transporte de resíduos sólidos urbanos é, geralmente, sanado através do método empírico; principalmente em cidades de pequeno porte. O objetivo deste trabalho é analisar o transporte de resíduos sólidos comerciais urbanos, através do método matemático computadorizado, utilizando Sistema de Informação Geográfica (SIG). O estudo de caso foi realizado para a cidade de Ilha Solteira - SP, que apresenta aproximadamente 24.000 habitantes. O método utilizado para análise do transporte de resíduos consiste em coleta de dados, caracterização do sistema atual, simulação do sistema utilizando SIG e análise dos resultados. Os dados foram coletados durante o período de julho a agosto de 2006. O sistema atual define a roteirização de veículos pelo método empírico e a frota é igual a 1 veículo, que visita 172 pontos comerciais. O veículo realiza 3 viagens/dia para suprir a demanda. Foram simulados cenários com locais de disposição atual, e mais 4 determinados por um modelo de escolha de locais. Os resultados mostram que há uma economia significativa de distância e tempo no roteamento pelo método computacional, em relação ao método empírico no estudo de caso realizado. O método computacional para roteirização dos veículos de coleta mostrou ser mais eficiente do que o método empírico. / The system of transport of the solid residues understands the calculation of the necessary fleet and the generation of itineraries. The routing of vehicles can be carried through through empirical or mathematical method. The mathematical method can manual or be computerized. The problem of the transport of urban solid residues is, generally, cured through the empirical method; mainly in small cities. The objective of this work is to analyze the transport of urban commercial solid residues, through the computerized mathematical method, using of geographic information systems (GIS). The case study it was carried through for the city of Ilha Solteira - SP, that presents 24,000 inhabitants approximately. The method used for analysis of the transport of residues consists of collection of data, characterization of the current system, simulation of system using GIS and analysis of the results. The data had been collected during the period of July the August of 2006. The current system defines the routing of vehicles for the empirical method and the fleet is equal the 1 vehicle, that visits 172 points commercial. The vehicle carries through 3 trips/day to supply the demand. Scenes with places of current disposal had been simulated, and more 4 determined for a model of choice of places. The results show that it has a significant economy of distance and time in the routing for the computational method, in relation to the empirical method in the study of carried through case. The computational method for routing of the collection vehicles showed to be more efficient of the one than the empirical method.

Orientador: Mateus José Rodrigues Paranhos da Costa / Banca: Fernando Sebastián Baldi Rey / Banca: Roberto de Oliveira Roça / Resumo: O transporte de animais para o abate é considerada a etapa mais crítica dentro do manejo de pré-abate. Vários são os motivos que influenciam nos efeitos do transporte rodoviário de bovinos de corte e no bem-estar animal e na qualidade de carcaça. O objetivo deste estudo foi descrever os efeitos do transporte rodoviário no bem-estar e na qualidade da carcaça de bovinos de corte destinados ao abate. Foram realizadas avaliações em duas plantas frigoríficas, com 1.038 desembarques, 185 motoristas avaliados e com um total de 19.635 carcaças. Analisando-se os principais efeitos relacionados à caracterização do transporte rodoviário de bovinos em alguns indicadores de bem-estar animal estão relacionados as características das viagens (condição de conservação do veículo, condições das estradas, distância, espaçamento), do condutor (curso na área de bem-estar animal, idade, tempo de experiência em condução de bovinos) e dos animais (raça e sexo). Considerou como variáveis dependentes as frequências de animais deitados, de quedas no desembarque e de hematomas nas carcaças. Os resultados indicaram que todas as variáveis dependentes apresentaram algum efeito sobre o número de hematomas nas carcaças, a porcentagem de animais deitados durante a viagem e a porcentagem de quedas sofridas no desembarque. Destaca-se os efeitos da distância percorrida pelo veículo de transporte, o espaço linear do compartimento de carga por animal e o tempo de experiência e capacitação dos condutores como importantes fontes de variação. Além dessas, o modelo do veículo utilizado para o transporte dos animais, também se mostrou uma forte variável, embora não tenha sido como variável independente nos modelos, devido ao fato da definição do modelo a ser usado no transporte não ser aleatória, dificultando comparações... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: Animal transportation is considered the most critical step in preslaughter beef cattle management. The aim of this study was to characterize the road transport of beef cattle and to analyses its impact on cattle welfare and carcass quality. The study was carried out in two slaughterhouses, by assessing the circumstances of 1,038 unloading procedures, interviewing 185 truck drivers and analyzing 19,635 carcasses. The following independent variables were recorded: 1.) vehicle (type and load compartment conditions), 2) road (distance traveled and road conditions), 3.) driver (age, years of experience in cattle transport and attendance to training courses), 4.) animal (breed and gender) and 5.) space available per animal in the load compartment. The dependent variables analyzed were 1.) frequency of animals lying down in the load compartment, 2.) number of falls at unloading and 3.) number of bruises on the carcasses. The results indicated that all dependent variables had some effect on the number of bruises on carcasses and percentages of animals lying down during the trip and of falls at unloading. The distance traveled, the space per animal in the load compartment and the drivers' experience and attendance to capacitation courses were determined to be the most important sources of variation. In addition, the vehicle model, also showed a strong effect on the dependent variables, although the type of vehicle was not included as independent variable, due to the fact of the model definition used for cattle transport was not by random. We conclude that to assure good animal welfare standards during transport and to achieve better carcass quality it is necessary to improve the transport conditions and this can be achieved by using vehicles that offer less risk to the animals, training the truck drivers, and opting for short-distances / Mestre

Orientador: Antônio Wagner Forti / Banca: Bruno Chaves Franco / Banca: Carlos Alberto Chaves / Resumo: Este trabalho compara qualitativamente sete métodos de modularização, com o objetivo de escolher e aplicar aqueles que melhor se adaptam ao projeto piloto de modularização de uma suspensão traseira a ar para caminhões e ônibus. Dentre os métodos estudados, os métodos MFD (Modular Function Deployment) e DSM (Design Structure Matrix) foram escolhidos, basicamente em função de possuírem: aplicação prática, repetibilidade dos resultados, softwares disponíveis e facilidade de organização dos dados. O método DSM serviu de base para gerar os primeiros possíveis módulos e simplificar o problema dos inicias 44 componentes para 26, simplesmente com uma visão funcional e técnica. O MFD foi utilizado principalmente para estruturar o processo de modularização e atender aos requisitos dos clientes e estratégias do negócio. Os resultados apresentados pelos dois métodos foram analisados de forma detalhada e indicaram a formação de sete módulos, que foram obtidos tanto diretamente dos métodos DSM e MFD, quanto da combinação de ambos. Ficou evidente, através dos resultados alcançados, que a utilização conjunta desses dois métodos, juntamente com a análise criteriosa dos resultados no desenvolvimento do produto aumentou consideravelmente a eficiência do processo de modularização / Abstract: This work presents and compares qualitatively seven modularization methods, in order to choose and apply those that best suits for a rear air suspension modularization pilot project for trucks and buses. Among the methods studied, the MFD (Modular Function Deployment) and DSM (Design Structure Matrix) methods were mainly chosen on the basis that they present: practical application, repeatability, software availability and ease data organization. The DSM method was the basis to generate the first possible modules and simplify the problem from the initial 44 to 26 components, only with a functional and technical approach. The MFD was mainly used to structure the modularization process and meet the customer requirements and business strategies. The results shown by the two methods were analyzed in detail and resulted in the generation of seven modules, which were obtained either directly from DSM and MFD methods, or from the combination of both. It became evident, by the results achieved, that the combined use of these two methods, along with a careful analysis of the results on product development, greatly increased the modularization process efficiency / Mestre

Orientador: Jorge Luiz Alves Trabanco / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Civil, Arquitetura e Urbanismo / Made available in DSpace on 2018-08-08T17:56:23Z (GMT). No. of bitstreams: 1 Amarante_RogerioRodrigues_M.pdf: 20709750 bytes, checksum: c6ce8ad63ef545117f1c4188f8446236 (MD5) Previous issue date: 2007 / Resumo: As empresas que precisam gerir suas frotas de veículos estão cada vez mais utilizando sistemas AVL (Localização Automática de Veículos). Com este sistema é possível conhecer a posição de um veículo em uma central de monitoramento, permitindo, com isso, as mais variadas aplicações dentro de atividades como segurança, logística, atendimento de emergência, etc.. Os produtos AVL disponíveis, normalmente são configurados com taxas de atualização que variam de 1 até 15 minutos, a fim de proporcionar uma boa relação custo benefício para as aplicações procuradas atualmente. Contudo, este formato utilizado, mostra com deficiência quais vias trafegou um veículo em áreas urbanizadas. Aumentar a taxa de atualização significa aumento de gastos com comunicação e armazenamento de dados, em contrapartida a redução da freqüência agrava a representação do trajeto, principalmente em áreas urbanas. Assim, este trabalho propõe apresentar o desenvolvimento de um sistema AVL com uma nova abordagem na atualização de posição, que além de representar melhor os trajetos rastreados dentro de áreas urbanas, evite o aumento significativo de gastos, pois quanto maior aderência do mesmo em relação ao percurso efetuado pelo veículo, maior o valor agregado às aplicações. Esta melhoria na representação dos trajetos poderá possibilitar a criação de novas abordagens de utilização de sistemas AVL que necessitam de mais precisão / Abstract: The use of AVL (Automatic Vehicle Locator) systems by companies that need to manage their fIeet has considerably increased. It is possible with this system to know the vehicle position in a dispatch center, al/owing several applications like safety and security, logistics, and emergency attendance. The available AVL products are usual/y configured with update rates between 1 and 15 minutes, in order to provide a good cost/benefit relationship. However, this update rate shows with deficiencies the route that a vehicle went through in urban areas. Increasing the update rate also increases expenses with communication and storage data; and, on the other hand, decreasing the frequency diminishes the representation of tracks, especial/y in urban areas. Thus, this master thesis proposes to show the AVL deve/opment with a new approach in position update, that aiso better represents the tracks in urban areas, without having significant increase of expenses, therefore, the better adherence to the tracked trajectory, the greater will be the perceived value of the system applications. This trajectory representation enhancement will make possible the creation of new approaches in AVL systems utilization that need accuracy / Mestrado / Transportes / Mestre em Engenharia Civil

Orientador: Franco Giuseppe Dedini / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Mecanica / Made available in DSpace on 2018-08-10T21:06:52Z (GMT). No. of bitstreams: 1 Gimenez_MarcosCarazatto_M.pdf: 5243564 bytes, checksum: f06980474419baf0ce942eb2ee5cccdf (MD5) Previous issue date: 2008 / Resumo: Essa dissertação trata da reestruturação de uma família de chassis de ônibus através da análise modular. A partir de um chassi já em produção, que foi a referência dessa análise, identifica-se a arquitetura da região do motor e seus periféricos, para a formação de um modelo que permite desenvolver novas periferias do motor derivadas do chassi de referência. Através do levantamento do estado da arte da modularidade, foi possível utilizar técnicas, métodos e ferramentas para agrupamento dos módulos, identificação das interfaces, quantificação da modularidade e avaliação de impactos nos módulos devido à inserção de novos módulos ou ajustes das condições de contorno. O resultado é a formação de novas periferias do motor com alto grau de comunização e padronização dos módulos, componentes e sistemas. As conseqüências da unificação das arquiteturas do produto para o projeto são a redução do tempo de desenvolvimento e aumento da confiabilidade do projeto. A origem desse trabalho deriva da necessidade que as montadoras têm de adaptarem seus portfólios de veículos a cada mudança de legislação ambiental. Nos últimos anos, o meio ambiente passou a ser o centro das atenções, refletindo em legislações cada vez mais desafiadoras no controle de emissões de gases danosos à atmosfera. O não atendimento às legislações acarretaria perda de mercado e conseqüente redução de lucros. Nesse cenário, o motor e os seus periféricos passam a ter uma atenção especial, pois depende deles o atendimento dos limites de emissões. Esse trabalho busca auxiliar na reconfiguração da periferia do motor através de um modelo exeqüível baseado na modularidade e que apresentou resultados satisfatórios / Abstract: This thesis describes the reorganization of a bus chassis family through the modular analysis. The reference of this analysis was a chassis already in production. As a first step, it is important to identify the needs and features of the engine and the peripheral components for the creation of the model which allows us to develop new engine peripheral components derived from the reference chassis. Analyzing the state of the art of the modularity, it was possible to apply techniques, methods and tools for grouping the modules, interface identification, modularity measurement and impact evaluation on the modules due to new modules development or boundary condition adjustments. The result is the development of new engine peripherical components with high degree of standardization of the modules, components and systems. The consequences of the standardization of the product architectures to the project are the development time reduction and higher reliability of the project. The origin of this work started due to the necessity that the auto-industry plants have to in order to adapt their vehicle variants for each new emission legislation. In the last years, the environment started to be the center of attention, reflecting in more challenging emission legislation, each time more restrict in relation to the emissions of gases to the atmosphere. The unfulfillment of the legislations would produce the effect of market loss and consequently profit reduction. In this scenario, the engine and peripheral components start to have a special attention, because it will depend on them to fulfill the emission limits. The goal of this work is to redesign the engine periphery by means of a feasible model based on modularization and which produced satisfactory results / Mestrado / Mecanica dos Sólidos e Projeto Mecanico / Mestre em Engenharia Mecânica

Orientador: Carlos Alberto dos Reis Filho / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-24T11:31:26Z (GMT). No. of bitstreams: 1 PolarSeminario_JorgeArturoMartin_M.pdf: 16230358 bytes, checksum: 19a064c9a9babbcedba062d8708fec23 (MD5) Previous issue date: 1998 / Resumo: Este trabalho descreve o projeto, a implementação e a análise dos resultados obtidos de um dos circuitos que perfazem a Unidade Remota da rede automotiva chamada BAM2 (Barramento Automotivo Magneti-Marelli). O circuito de que trata este trabalho executa as funções de interface da Unidade Remota com o meio físico que constitui a rede, sendo então chamada de Unidade de Interface de Rede (UIR). O projeto culminou com o desenvolvimento de um circuito integrado de aplicação específica (AS/C), cujo protótipo foi implementado em tecnologia CMOS-0.8um, ocupa 8.7mm2, contendo 7500 gates equivalentes, dos quais cerca de 30% corresponde à UIR. Para melhor explicar o funcionamento de um circuito que não se constitui numa unidade isolada e autônoma, mas que é parte de um sistema maior, o texto contém no início uma descrição da rede automotiva desenvolvida, que é o sistema hierarquicamente superior, depois focaliza a Unidade Remota, que contém a UIR e finalmente descreve em detalhes a UIR. O projeto da rede automotiva, que resultou no desenvolvimento de uma unidade central controladora, utilizando um microcontrolador comercial; de um AS/C, cujo protótipo foi fabricado pela AMS (Austria Mickro Systeme) através do Projeto Multi-Usuário financiado pela FAPESP e de um transistor de potência MOS que aciona cargas de até 2.5A, foi executado num período de dois anos, tendo a participação de doze pesquisadores. Este projeto constituiu uma das atividades do projeto de cooperação técnica entre a FEEC-UNICAMP e a empresa Magneti-Marelli do Brasil Divisão Eletrônica / Abstract: A circuit to perform the role of serial interface in an integrated system, which interprets a one-wire network protocol, is described in this paper. The circuit was implemented in a 40K gates FPGA and fully tested. A description of the functions performed by the circuit, the design approach and experimental results are presented. / Mestrado / Mestre em Engenharia Elétrica

[pt] A natureza intrinsicamente combinatorial de muitos problemas advindos da área de logística de transportes, em especial aqueles que dizem respeito ao uso racional de frotas de veículos, sugere que boa parte dos mesmos pode ser formulada e resolvida como um problema de programação linear inteira. Contudo, a maioria dos algoritmos até o momento disponíveis não consegue encontrar, em tempos computacionais aceitáveis, a solução ótima para instâncias de porte razoável. O objeto de estudo desta tese é a exploração de técnicas mais recentes da área de programação linear inteira e suas aplicações a problemas de roteamento de veículos. A primeira parte da tese descreve, além das técnicas básicas de decomposição de problemas de programação linear e linear inteira e de geração de colunas, uma proposta de reformulação de problemas de programação linear inteira alternativa àquela que gera o tradicional problema mestre de Dantzig-Wolfe, geralmente utilizados em abordagens por geração de colunas. A resolução de problemas de programação linear inteira neste contexto é tratada em seguida, com a descrição do algoritmo branch-and-bound e das variações branch-and-cut, branch-and-price e branch-and-cut-and-price. Na segunda parte da tese, inicialmente, é apresentada a técnica denominada de Geração Projetada de Colunas e sua aplicação ao problema de Roteamento de Veículos com Restrição de Capacidade. Em seguida é abordada a resolução do problema de Roteamento de Veículos sobre Arcos, através de sua transformação ao primeiro problema citado e uso de um algoritmo branch-and- cut-and-price. Finalmente, é proposto um novo problema na área de redistribuição de veículos de aluguel, para o qual é proposta uma formulação segundo uma abordagem por geração de colunas. São apresentados, ainda, procedimentos para a geração de colunas e resultados computacionais obtidos com um algoritmo branch-and-price para essa formulação. / [en] Optimization techniques have an important role in Transportation Logistics. The combinatorial nature of the problems related to this area suggests integer programming as a natural approach to their resolution. Nevertheless there are many cases where even instances of reasonable size still beyond the resolution capability of the current known algorithms. The success of the known algorithms have therefore been limited. This can be justified by the fact the most of them leave important recent advances in the combinatorial optimization field unexplored. Some of these new techniques and their applications are the main subject of this thesis. In the first part, the basic decomposition techniques for linear and integer programming problems as well as the related column generation approach is addressed. This is followed by the presentation of a reformulation technique for linear and integer programming which is alternative to the well known Dantzig-Wolfe master program. The new possibilities coming from this approach are explored and the resulting consequences to the standard branch-and- bound algorithm and its variations branch-and-cut, branch-and- price and branchand- cut-and-price are presented. The second part of this text addresses the application of the metodologies described in part one to routing problems where capacity constraints are considered. First, a techinque named Projected Column Generation is described in the context of the Capacitated Vehicle Routing Problem. Then, it is presented a new transformation from the Capacitated Arc Routing Problem to the Capacitated Vehicle Routing Problem as well as a tailored branch-and-cut-and-price to solve this problem. Finally, a new problem in vehicle redistrubution is described together with a column generation approach for its resolution. Computational results for all applications are presented.