Orientador : Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-28T19:54:03Z (GMT). No. of bitstreams: 1 Rodrigues_MaikolMagalhaes_M.pdf: 4069676 bytes, checksum: b0b8e4bc9cdbe5bfc3fb90f34a46b43e (MD5) Previous issue date: 2001 / Resumo: Este trabalho de mestrado procurou estudar e resolver o problema de planejamento de viagens de linhas de ônibus da região metropolitana de São Paulo. Para tanto foi proposta uma ferramenta computacional capaz de gerar automaticamente as programações de viagens para uma linha de ônibus urbano. A programação de viagens tem um grande impacto não só na qualidade do serviço prestado aos passageiros da linha mas também no custo operacional das empresas de transporte. Portanto, o problema aqui estudado é de grande relevância prática e social. Os dados de entrada incluem uma curva com a demanda horária de passageiros da linha e um conjunto de restrições operacionais relativas à frota e aos funcionários. Na saída, deve-se produzir uma tabela com os horários das viagens além da escala de serviço completa dos carros e dos funcionários que irão operar na linha. Os algoritmos propostos por essa dissertação concentram-se no desenvolvimento de heurísticas baseadas em modelos de Programação Linear Inteira para resolver o problema de programação de viagens. Estes algoritmos foram implementados como parte de uma ferramenta computacional e os resultados são comparados com as soluções adotadas atualmente pelas empresas de transportes urbano. A análise dos resultados computacionais mostra que é possível obter reduções substanciais nos custos da operação sem que com isso haja uma redução na qualidade de serviço / Abstract: This dissertation aimed at studying and solving a real world trip planning problem. The problem considered arises from the daily operation of an urban transit bus company that serves the metropolitan area of the city of São Paulo, in Brazil. In this work we present a software that automatically generates a planning for the trips of a urban bus line. The trip planning has an enormous impact not only on the quality of the service offered to the passengers but also on the operational cost of the transportation companies. Therefore, the problem tackled here is of great importance for practical and social reasons. The input data includes the hourly demand of passengers and a set of operational constraints related to the vehicles and the employees. In the output, the trip time table as well as the vehicle and the crew schedules are produced. All the proposed algorithms in this work focus on the design of heuristics based on Integer Linear Programming models for the problem. The algorithms are implemented as part of a software whose results are compared with the solutions adopted in the bus companies nowadays. The analysis of our experiments indicates that it was possible to achieve a substantial cost reduction without loss in the quality of service / Mestrado / Mestre em Ciência da Computação

Orientador: Vinicius Amaral Armentano / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-13T19:39:00Z (GMT). No. of bitstreams: 1 Takahata_AndreKazuo_M.pdf: 1113954 bytes, checksum: 18f4c96c943dced30f100b8a56c97258 (MD5) Previous issue date: 2009 / Resumo: Este trabalho trata do desenvolvimento de heurísticas de busca genéricas para obtenção de soluções de problemas de otimização combinatória formulados como modelos de programação linear inteira, com o uso do pacote de otimização XPRESS. Este é um tema recente, em que são conjugados a flexibilidade de heurísticas e os avanços dos solvers de otimização para a obtenção de soluções de alta qualidade em tempo reduzido. As heurísticas propostas são baseadas em arredondamentos gerados a partir de raios de um cone, cujo vértice é associado à solução ótima da relaxação de programação linear, e em trajetórias factíveis e infactíveis em relação à fronteira desta relaxação. A motivação para este enfoque é dada pelo apelo geométrico e no sucesso de estratégias similares em heurísticas para problemas combinatórios. O trabalho descreve a concepção e a implementação dessas heurísticas e apresenta resultados de testes em instâncias da literatura. / Abstract: In this work we develop a set of generic search heuristics for solving combinatorial optimization problems formulated as linear integer programming models, using the XPRESS optimization package. This is a recent theme, in which efforts have been made in order to combine the flexibility offered by heuristics and the expressive advances achieved in the development of optimization solvers so as to obtain high quality solutions in a short time. The proposed heuristics are based on rounding solutions located on the rays of a cone whose vertex is associated with the optimal solution of the linear programming relaxation, and in feasible and infeasible trajectories relative to the frontier of such relaxation. This approach is motivated by its geometric appeal and by the success of similar approaches in heuristics for solving combinatorial problems. This work describes the development and implementation of the heuristics and presents computational tests on instances from literature. / Mestrado / Automação / Mestre em Engenharia Elétrica

Na maioria das cidades brasileiras, o ônibus é o principal, senão o único meio de transporte público de passageiros, atendendo àqueles que não possuem carro, mas também contribuindo para reduzir os congestionamentos e, dessa forma, melhorando a qualidade de vida. A fim de incentivar a sua utilização em muitas cidades, inúmeras medidas devem ser tomadas, incluindo um esforço para reduzir custos e, em decorrência, as tarifas pagas pelos usuários, definindo uma tarifa justa que privilegie a população de baixa renda, na qual estão inseridos uma grande parcela dos seus usuários. Nesse contexto, a programação eficiente de veículos e tripulações é essencial para essa redução de custos, uma vez que representa uma parcela significativa dos mesmos. Este trabalho trata do Problema de Programação de Veículos e de Tripulantes de Ônibus, em que ambas as programações são determinadas simultaneamente e de maneira integrada. Durante a realização deste trabalho, foi desenvolvido um programa computacional em C++, o qual implementa a metaheurística Busca em Vizinhança Variável (VNS) utilizada para resolver esse problema complexo. São apresentados resultados de experimentos computacionais com dados reais de uma empresa de transporte coletivo. Os resultados obtidos comprovam a eficácia da abordagem integrada em comparação com quatro outras abordagens encontradas na literatura. / In most Brazilian cities, bus has become the main, and oftentimes the only mean of public transportation, not only servicing those who cannot afford to have a car, but also helping to reduce traffic congestion and thus improving quality of life. In order to encourage the bus usage in many cities, several measures must be taken, including an effort to reduce overall costs and, as a result, fares paid by the users, thus benefit mainly low income users which represent a major part of its users. In this context, an efficient scheduling of vehicles and crews is essential to achieve cost reduction, since it accounts for a major part of overall costs. In this paper, we deal with the Bus Vehicle Crew Scheduling Problem, in which bus and crew schedules are simultaneously determined in an integrated approach. We propose an approach based on Variable Neighborhood search to solve this complex problem, which was implemented in C++. Computational results for real-world problems are presented, showing the effectiveness of this novel approach in comparison with other four approaches found in the literature.

Submitted by isabela.moljf@hotmail.com (isabela.moljf@hotmail.com) on 2017-05-05T12:33:32Z No. of bitstreams: 1 hedersoaresbernardino.pdf: 1908457 bytes, checksum: 7dfb54846a46eb894ddf55decf7be4a1 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-05-17T13:34:58Z (GMT) No. of bitstreams: 1 hedersoaresbernardino.pdf: 1908457 bytes, checksum: 7dfb54846a46eb894ddf55decf7be4a1 (MD5) / Made available in DSpace on 2017-05-17T13:34:58Z (GMT). No. of bitstreams: 1 hedersoaresbernardino.pdf: 1908457 bytes, checksum: 7dfb54846a46eb894ddf55decf7be4a1 (MD5) Previous issue date: 2008-02-29 / FAPEMIG - Fundação de Amparo à Pesquisa do Estado de Minas Gerais / Neste trabalho são propostas, implementadas e testadas computacionalmente algumas possibilidades de hibridização de algoritmos genéticos e sistemas imunológicos artificiais visando a solução de problemas de otimização com restrições. Tais problemas aparecem frequentemente na modelagem computacional de problemas científicos e tecnológicos relevantes. Após breve formulação e caracterização da solução de um problema de otimiza- ção com restrições em Ɽn é feita uma introdução na modelagem estrutural e aos problemas de otimização desta área, mostrando sua importância e as dificuldades no desenvolvimento de métodos de resolução aproximados. São apresentadas então diversas meta-heurísticas bio-inspiradas para a resolu-ção destes problemas de otimização, em especial os algoritmos genéticos (AGs) e os sistemas imunológicos artificiais (SIAs). Em seguida, são propostas algumas possibilidades de hibridização de AGs e SIAs para a otimização restrita. Experimentos computacionais visando avaliar o desempenho dos procedimentos propostos são realizados considerando vários problemas-teste da literatura e, finalmente, são apresentadas conclusões e propostas para trabalhos futuros / In this work some possibilities of hibridization of genetic algorithms and artificial immune systems are proposed, computationally implemented, and tested in order to solve constrained optimization problems. Such problems arise frequently in the computational modeling of relevant scientific and technological problems. After a brief formulation and solution characterization for a constrained optimization problem in Ɽn, an introduction is made to structural modeling and the optimization problems in this area, showing their relevance and the dificulties arising in the development of approximate solution methods. Several bio-inspired meta-heuristics for solving such optimization problems are then presented with emphasis on genetic algorithms (GAs) and artiticial immune systems (AISs). Some possible GA-SIA hybrids are then proposed. In order to assess the performance of the proposed procedures, computational experiments are conducted considering several test-problems from the literature and, finally, conclusions as well as future work proposals are presented.

Orientador: Orlando Fontes Lima Júnior / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Civil, Arquitetura e Urbanismo / Made available in DSpace on 2018-08-26T02:20:07Z (GMT). No. of bitstreams: 1 Paiva_EduardoPereiraLimade_M.pdf: 15061304 bytes, checksum: 0389c666bf0c3316bd357dbeeb9b2c54 (MD5) Previous issue date: 2014 / Resumo: O serviço de entrega por bicicleta representa um mercado de prestação de serviços promissor e em crescimento. O transporte de carga movido por propulsão humana tem recebido bastante atenção por ser capaz de reduzir custos e emissão de poluentes em operações logísticas de curta distância e por aliviar a quantidade de veículos motorizados utilizados em centros urbanos. A distribuição de pequenas encomendas por bicicleta em área urbana de pequeno porte foi objeto deste trabalho. Com base nos métodos de Districting (divisão por distritos), de Clarke e Wright e Diagramas de Voronoi, realizou-se um estudo de caso envolvendo a distribuição de malotes no campus de Campinas da UNICAMP (Universidade Estadual de Campinas). Os resultados dessas aplicações foram comparados entre eles e em relação à situação existente, e as dificuldades e restrições para a implantação de serviços de bicicletas foram exploradas considerando-se a viabilidade econômica e social da substituição do veículo motorizado pelo veículo movido a propulsão humana / Abstract: The bicycle delivery service is a promising and growing service delivery market. Human propelled load transportation has received great attention these days for being able to reduce costs and pollution emission in short distance logistics operations, as well as to diminish the amount of motor vehicles in urban centers. The subject of this paper is the distribution of small orders by bicycle in small urban areas. Based on the Districting method (division by districts), Clarke and Wright Algorithm, and Voronoi Diagrams, a case study was developed considering the distribution of pouches in the campus of Campinas State University (Universidade Estadual de Campinas - UNICAMP), São Paulo, Brazil. The results of these applications were compared among themselves and to the actual situation, and the difficulties and restrictions imposed to the implementation of bicycle service delivery were explored from the point of view of the economic and social viability of motor vehicle replacement for human propelled vehicle / Mestrado / Transportes / Mestre em Engenharia Civil

Orientador: Vinicius Amaral Armentano / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-03T17:30:49Z (GMT). No. of bitstreams: 1 Yamashita_DeniseSato_D.pdf: 2970003 bytes, checksum: 72c1667962da475bb3a8d324efecf62b (MD5) Previous issue date: 2003 / Doutorado

Orientadores: Akebo Yamakami / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-03T22:32:38Z (GMT). No. of bitstreams: 1 Takahashi_MarciaTomie_D.pdf: 1514697 bytes, checksum: bf74eb1142b348387b3427a6f3cb4420 (MD5) Previous issue date: 2004 / Doutorado

Oreintadores: Luiz Manoel Aguilera, Paulo Morelato França / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-25T06:20:25Z (GMT). No. of bitstreams: 1 Toledo_ClaudioFabianoMotta_M.pdf: 11299946 bytes, checksum: e9df3be1555cd8e5c6e40cc5ef52d41f (MD5) Previous issue date: 1999 / Resumo: O Problema de Roteamento de Veículos (PRV) procura estabelecer uma eficiente distribuição de bens de forma a atender as demandas existentes. Os atuais avanços em tecnologia de informação como rádio transmissores, telefonia celular, sistemas de localização via satélite, estão alterando o cenário em que um PRV pode ocorrer permitindo, por exemplo, a atualização de dados e localização de veículos em tempo real. Um PRV será considerado dinâmico caso seus dados não sejam conhecidos pelo usuário a priori e atualizados simultaneamente a determinação ou execução do conjunto de rotas. Um Problema de Roteamento Dinâmico de Veículos (PRDV) será estabelecido e um método de resolução, chamado algoritmo MORSS, será adaptado para resolver instâncias deste PRDV. Em seguida, um Problema Dinâmico de Programação (PDP) também será estabelecido e o algoritmo MORSS adaptado para resolver instâncias deste PDP. Um segundo método, baseado em heurísticas de busca em vizinhança e inserção, também será proposto para resolver as instâncias do PDP. O trabalho se propõe a resolver dois diferentes tipos de problemas dinâmicos procurando avaliar a adaptabilidade e desempenho do algoritmo MORSS enquanto método de resolução. No caso do PDP, o desempenho de um segundo método também é analisado e comparado ao desempenho obtido pelo algoritmo MORSS / Abstract: The Vehicle Routing Problem (VRP) is the efficient distribution of products in order to attend customer requirement. Recently, the advances in information technology as radio transmission, cellular telephone, localization systems by satellite, are altering the scenarios in that VRP occurs and allowing update of information and vehicle localization occur in real time. The VRP is dynamic if the inputs of the problem are known by the decision-maker and are updated concurrentlY with the deterrnination or execution of the route's set. A Dynamic Vehicle Routing Problem (DVRP) will be established and a solution's method, called MORSS algorithm, will be adapted to solve DVRP instances. Next, a Dynamic Scheduling Problem (DSP) will be established and the MORSS algorithm will be adapted to solve DSP instances. A second method, based in heuristics of neighborhood search and insertion, will be also proposed to solve DSP instances. This work proposes to solve two different dynamic problems searching to evaluate the MORSS algorithm adaptability and performance as resolution method. In the PDP, the performance of the second method proposed also will be analyzed and compared with the performance obtained by MORSS algorithm / Mestrado / Mestre em Engenharia Elétrica

Orientador: Maria Regina Wolf Maciel / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Quimica / Made available in DSpace on 2018-07-25T08:22:56Z (GMT). No. of bitstreams: 1 Carvalho_CaioAugustoCamargode_M.pdf: 6588270 bytes, checksum: 80a5b72912c3481a7d6d07599851454c (MD5) Previous issue date: 1995 / Resumo: : Uma seqüência de destilação tem por finalidade o fracionamento de uma mistura multicomponente de alimentação em produtos que exigem uma determinada composição. No caso estudado, a composição dos produtos visa um único componente cujo grau de pureza pose ser estabelecido inicialmente, sendo então projetada toda a estrutura de separação baseada nesta exigência. Tal característica torna o procedimento de síntese aqui desenvolvido mais flexível do que os propostos em literatura, onde somente um tipo de especificação pode ser utilizado em cada coluna, resultando unicamente em produtos de alta pureza. Neste trabalho, a síntese de uma seqüência de destilação é abordada de modo a incorporar uma análise rigorosa do comportamento de cada separador englobando a otimização de suas variáveis mais importantes. Exigi-se para isto a elaboração de uma metodologia para que um simulador comercial possa ser utilizado, uma vez que a natureza multivariável do problema pode torna-lo extremamente complexo.Assim uma trabalho desenvolvido consiste em obter as especificações para a simulação em cada coluna das seqüências pesquisadas, o numero de estágios, diâmetro, razão de refluxo e prato de alimentação ótimo de cada uma. O resultado é a obtenção de um procedimento que é especialmente indicado para final de uma seqüência de destilação a partir de um grupo pré-selecionado de seqüências iniciais e um projeto final otimizado de cada uma com estimativas reais de custos operacionais e de investimento / Abstract: The main of a distillation sequence is to split a multicomponent feed mixture to products which have a particular composition. In this work only one component has a particular importance in product mixture whose purity may be initially defined making then all the separation structure be designed in accordance with it. This feature allow more flexibility than others procedures proposed in literature where only a unique specification is possible to each column resulting is a high pure products. The synthesis of a distillation sequence is made incorporating a rigorous behavior analysis of each separator including optimization of its more important variables. It demands elaboration of a methodology for use a commercial simulator since the multivariable problem¿s nature may make it extremely complex. So, a critical selection of variables and procedures can be done through analysis. In this context, the work consist in to get the specifications for simulation of each column for searched sequences, the number of stages, diameter, reflux rate, and optimal feed stage. The results is a specially indicated procedure for choice of a final distillation sequence based on a pre-selected group of initial sequences and a final optimal design of each one with realistic estimates of operational and investment costs / Mestrado / Desenvolvimento de Processos Químicos / Mestre em Engenharia Química

Orientador: Paulo Morelato França / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-25T20:34:59Z (GMT). No. of bitstreams: 1 Campos_DanilodaSilva_M.pdf: 5708291 bytes, checksum: 3aee68b9155ce0d5d427287c5fa57bc1 (MD5) Previous issue date: 1999 / Resumo: Neste trabalho foi estudado o problema de inventário e roteamento de veículos (PIRV). Um estudo de caso originado na agroindústria, para o problema de distribuição de ração de frangos foi relatado. O problema foi modelado como uma variação do PIRV tradicional. Uma série de restrições foram levantadas de maneira incremental e discutidas ao longo do trabalho. A estratégia de resolução focou, em primeiro lugar, o problema de manutenção do inventário nas granjas e depois, num segundo nível, no roteamento dos veículos. O algoritmo de programação de envios apresentado respeita todas as restrições técnicas e operacionais relacionadas ao problema de distribuição de ração. O algoritmo de montagem das rotas é usado sob demanda no momento dos despachos dos veículos da fábrica. O algoritmo foi colocado em operação e validado na prática. Uma simulação é apresentada para efeito de análise. Finalmente, foi desenvolvido um sistema computacional que integra todas as informações pertinentes ao problema, bem como que oferece uma interface amigável para os usuários do planejamento da empresa / Abstract: In this work we have studied the inventory and vehicle routing problem (IRVP). A case study, raised on the agribusiness area, for distribution of chicken food have been described. The problem was modeled as a variation of the traditional IRVP. Many constraints have been reported in an incremental way and explained throughout this work. The resolution strategy focused, first, on the inventory guarantee problem, and in a second levei on vehicle routing problem. The delivery planning algorithm considers ali technical and operational constraints related with the distribution chicken food system. The dispatching algorithm is used on demand, when each vehicle arrive in the factory. The algorithms have been evaluated and validated in a real operation. The analysis of the performance of the method was done by simulation. Finally, we have developed a software that integrate ali information needed to the planner, with a friendly user interface / Mestrado / Mestre em Engenharia Elétrica