Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2018-09-05T17:12:27Z No. of bitstreams: 1 texto completo.pdf: 804859 bytes, checksum: ed4ee44a672aa18b9e35cf4a363ab38a (MD5) / Made available in DSpace on 2018-09-05T17:12:27Z (GMT). No. of bitstreams: 1 texto completo.pdf: 804859 bytes, checksum: ed4ee44a672aa18b9e35cf4a363ab38a (MD5) Previous issue date: 2017-12-14 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho aborda um problema de sequenciamento (scheduling) onde as tarefas são processadas em lotes em máquinas paralelas idênticas. Neste problema uma má- quina pode executar um conjunto (lote) de tarefas simultaneamente. Além disso, as tarefas são classificadas em famílias, onde uma família agrupa tarefas que possuam alguma característica em comum. Assim, os lotes devem conter somente tarefas de uma mesma família. O problema também considera tarefas com diferentes tempos de chegada (release times) e tempos de processamento. As tarefas possuem ainda uma data de entrega e uma prioridade. O problema consiste em determinar os lo- tes (grupos) de tarefas para serem sequenciados nas máquinas de tal maneira que o atraso total ponderado das tarefas seja minimizado. O problema envolvendo se- quenciamento de lotes, que é uma extensão do sequenciamento de tarefas clássico (onde uma máquina processa somente uma tarefa por vez), possui muitas aplicações reais, como em indústrias de fundição, de fabricação de móveis, de processamento de metais, de processamento de alimentos, farmacêuticas e de semicondutores. Para resolver o problema abordado, três algoritmos baseados em meta-heurísticas foram desenvolvidos: Adaptive Large Neighborhood Search (ALNS), Iterated Greedy (IG) e Simulated Annealing (SA). Todos estes algoritmos utilizam técnicas de busca em vizinhança para melhorar a qualidade de uma solução. As meta-heurísticas ALNS, IG e SA possuem estruturas simples e elas têm sido aplicadas satisfatoriamente para resolver diferentes problemas de otimização combinatória, especialmente problemas de sequenciamento da produção, o que justifica a utilização para o problema em es- tudo. Experimentos computacionais, utilizando dados da literatura foram realizados a fim de avaliar o desempenho dos algoritmos. Os resultados são comparados com os resultados gerados por dois algoritmos da literatura (Memetic Algorithm e Variable Neighborhood Search) e com os resultados da resolução do modelo matemático do problema. Os experimentos e testes realizados demonstram que os algoritmos de- senvolvidos neste trabalho geram soluções válidas de excelente qualidade superando as melhores soluções apresentadas na literatura. / This work addresses a scheduling problem where the jobs are processed in batches on a identical parallel machines. In this problem a machine can process a set (batch) of jobs simultaneously. In addition, jobs are classified into families, where a family groups jobs that have some characteristic in common. Thus, the batches must con- tain only jobs of a same family. Also, the problem considers jobs with different release times and processing times. The jobs also have a due date and a priority. The objective of the problem is to group the job set into batches and assign the batches to the parallel machines in order to minimize the total weighted tardiness of the jobs. The parallel batch processing machines scheduling problem, that is an extension of classic job sequencing(where a machine processes only one task at a time) has many real application, such as in the foundry industry manufacturing, food processing industries, pharmaceutical industries and semiconductor industries. To solve this problem, three algorithms based on meta-heuristics were developed: Adaptive Large Neighborhood Search (ALNS), Iterated Greedy (IG) and Simula- ted Annealing (SA). All of these algorithms use neighborhood search techniques to improve the quality of solutions. In addition, the meta-heuristics ALNS, IG and SA have been applied satisfactorily to solve different combinatorial optimization problems. Computational experiments using literature data were performed to eva- luate the performance of the algorithms. The obtained results are compared with the results generated by two algorithms from the literature (Memetic Algorithm and Variable Neighborhood Search) and with the mathematical model of the problem. The computational experiments demonstrate that the algorithms developed in this work generate valid solutions of excellent quality, outperforming the best solutions presented in the literature.

Orientador: Pedro Sergio de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-21T13:12:10Z (GMT). No. of bitstreams: 1 Rodrigues_RosianedeFreitas_M.pdf: 9358851 bytes, checksum: aa44aaf61d515209c1ff85e92e7915a9 (MD5) Previous issue date: 1996 / Resumo: Times Assíncronos (do inglês Asynchronous Teams ou A-Teams) constituem uma abordagem multi-algorítmica para a resolução aproximada de problemas, cujo princípio básico é a cooperação sinérgica entre um conjunto de algoritmos, que se comunicam assincronamente através de memórias compartilhadas, propiciando soluções de melhor qualidade do que as geradas pelos mesmos algoritmos quando executados isoladamente. Este método tem sido aplicado com sucesso em problemas combinatórios com uma única função objetivo. O presente trabalho apresenta Times Assíncronos como sendo adequado à resolução de problemas de otimização combinatória com múltiplas funções objetivo. Diferentes estratégias para a manipulação de soluções multidimensionais foram desenvolvidas, tornando possível a rápida obtenção de soluções próximas ou mesmo pertencentes ao Pareto Ótimo do problema. Em especial, foi desenvolvida uma estrutura de manipulação de soluções multidimensionais que possibilita a consideração simultânea de todos os objetivos envolvidos para a geração de soluções. É proposto um novo problema NP-dificil como uma generalização do clássico Problema do Caixeiro Viajante (do inglês Traveling Salesman Problema ou TSP), onde ao invés de apenas uma matriz de distância existem múltiplas matrizes, sendo intitulado Problema do Caixeiro Viajante com Múltiplas Distâncias (do inglês Multi-Distance Traveling Salesman Problem ou MDTSP) e ao qual foi aplicado o método de Times Assíncronos. Os testes computacionais foram realizados de forma concorrente e paralela, obtendo-se conjuntos de soluções não-dominadas bem distribuídas dentro de uma ampla faixa de valores fornecidos pelas funções objetivo envolvidas, para todas as instâncias, mesmo envolvendo várias dimensões. Isto demonstra que os melhores conjuntos de soluções não-dominadas gerados pelos AT eams foram numerosos e contiveram soluções significativamente distintas entre s~ abrangendo todo o espectro desejado. Para as menores instâncias foi possível constatar que o melhor conjunto de soluções não-dominadas obtido fora o próprio Pareto Otimo. Ainda, foram desenvolvidos algoritmos para o novo problema que incorporam conceitos adequados a problemas multiobjetivos / Abstract: Asynchronous Teams or A-Teams constitute a mu1ti-algorithm approach for approximated problem solving, whose basic principle is the sinergic cooperation among a set of algorithms that communicate asynchronously through shared memories, providing solutions of better quality than those generated by the same algorithms when executed separately. This method has been successfully applied to Combinatorial Optimization Problems with a single objective function. This work presents Asynchronous Teams as an adequated method to solving Combinatorial Optimization Problems with multiple objective junctions. Different strategies to the manipulation of multi-dimensional solutions were developed, allowing it possible to obtain near-optimal or Pareto Optimal solutions quickly. In special, was developed a structure for multidimensional solution manipulation that allowing it possible the simultanea consideration of all objectives involved to the solution generation. It is proposed a new NP-hard problem as a generalization of classic Traveling Salesman Problem or TSP, which, instead of only one distance matrix, has various matrices. It has been entitled of Multi-Distance Traveling Salesman Problem or MDTSP and to which was applied the Asynchronous Teams method. The implementation tests were accomplished in a concurrent and parallel way, obtaining set of non-dominated solutions well-distributed on a wide range of values provided by the objective functions involved, over the tested instances. This demonstrates that the best sets of non-dominated solutions obtained are numerous and contain solutions significantly distinct among them. To the small instances was possible to show that the best set of non-dominated solutions generated was the Pareto Optimal. Algorithms have been developed for the new problem with the incorporation of compromisse decision and dominance concepts. Still, were developed algorithms to the new problem that incorpore adequated concepts to multiobjective problems / Mestrado / Mestre em Ciência da Computação

Orientador: Paulo Morelato França / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e Computação / Made available in DSpace on 2018-07-21T18:54:37Z (GMT). No. of bitstreams: 1 Coelho_MarcoAntonioFreitasdoEgito_D.pdf: 7042998 bytes, checksum: 9bebcee2dc4b60902fd40a01d09293f9 (MD5) Previous issue date: 1996 / Resumo: Nesta tese novos métodos e procedimentos para resolver o problema de programação de tarefas em múltiplas máquinas paralelas com custos de atraso e adiantamento são propostos. As máquinas são não-relacionadas, a divisão de tarefas é permitida, as tarefas podem ter datas previstas de entrega diferentes e os tempos de preparação de máquina para executar uma tarefa depende da tarefa anterior processada na mesma máquina. Este é um problema novo, de dificil resolução e não foram encontradas referências na literatura especializada. Apesar disso, tem muitas possíveis aplicações na manufatura. O problema é formulado através de um modelo linear de programação inteira mista para o caso sem divisão de tarefas e, posteriormente,dois outros modelos lineares são propostos para o caso onde a divisão de tarefas é permitida. Como o problema de minimização foi mostrado ser NP-completo, os modelos podem apenas ser utilizados para resolver pequenos problemas de teste. A partir do modelo de programação inteira mista, um método de busca em árvore é desenvolvido para uso com procedimentos Branch & Bound e Busca em Feixe Filtrada. Dois limitantes inferiores são desenvolvidos para o Branch & Bound e quatro limitantes para a Busca em Feixe Filtrada. Algumas propriedades e teoremas do problema original e um método de decomposição eficiente para resolver o modelo linear derivado do modelo de programação inteira mista, também são apresentados. Muitos problemas de teste com até 120 tarefas e 6 máquinas são utilizados para mostrar o desempenho dos métodos desenvolvidos aqui / Abstract: In this thesis new methods and procedures to solve the multimachine scheduling problem with early and tardy costs are proposed. The machines are unrelated, job splitting is allowed, the jobs may have different due dates and the changeover time to process a new job on a machine depends on the job previously processed on the same machine. This problem is new, hard to solve and no references have been found in respecialized literature. However, it has many applications in the manufacturing. Two linear mixed-integer programming models one stated when job splitting is allowed, as well as similarmodel is proposed for the case without job splitting. Since the problem is NP-hard, the models can oniy be used to solve small test problems. Based on the mixed-integer formulation, a tree search method is developed to be used in a Branch & Bound and in a Filtered Beam Search procedures. Two lower bounds are developed for the Branch & Bound and four bounds for the Filtered Beam Search. Some properties of the original problem and an efficient decomposition method to solve the LP model derived from the mixed-integer problem are presented. Many test problems with up to 120 jobs and 6 machines has been used to show the performance of the proposed methods / Doutorado / Doutor em Engenharia Elétrica

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-21T20:24:03Z (GMT). No. of bitstreams: 1 MaqueraSosa_NelidaGladys_M.pdf: 3207129 bytes, checksum: d82f6742a78882c2faf1ce8aef31ccc1 (MD5) Previous issue date: 1996 / Resumo: As técnicas de agrupamento são aplicadas com diferentes finalidades e necessárias em muitos campos da ciência. No Problema de Agrupamento Capacitado (PAC) são dados objetos que possuem um peso associado que devem ser particionados em agrupamentos com capacidades limitadas. Apresentam-se quatro heurísticas de construção baseadas em pesos e distâncias dos objetos; uma heurística de melhoria que realiza inserções e permutações de objetos e uma aplicação de Busca Tabu (BT) simples. Além disso, é aplicado um mecanismo de abordagem adaptativa de horizonte arbitrário (HTA) baseado em BT que integra as fases de intensificação e diversificação durante a busca. Foram realizados testes computacionais mostrando que HTA obtém soluções de boa qualidade independentemente do ponto de partida e que algoritmos baseados em pesos .dos objetos têm melhor desempenho que algoritmos baseados em distâncias. Aplica-se a mesma metodologia ao Problema de Distritamento Político (PDP) que é um caso particular do PAC. É realizado um estudo preliminar de distritamento da cidade de Campinas dividindo-a em 10 distritos eleitorais. Estes resultados foram obtidos com aplicação da BT, mostrando que este problema pertencente às ciências políticas pode ser tratado pela programação matemática com erros mínimos / Abstract: Clustering techniques can be applied aiming different purposes with applications in severa! fields of science. In the Capacitated Clustering Problem (CCP) objects with distinct weights must be partitioned into clusters with limited capacity. It is presented four constructive heuristics that use weights and distances as optimization criteria. An improvement heuristic that performs insertions and interchanges of objects and a single Tabu Search (TS) application is also proposed. Moreover, it is applied an adaptive mechanism (HTA) based on TS which joins both intensifying and diversifying phases during the search. Computational tests show that HTA attains good quality solutions independent1y from the starting solution. They also show that a!gorithms based on object weights perform better than the ones based on distances. The same methodology is applied to a Political Districting Problem (PDP) which is a particular case of CCP. A preliminary study on the districting of Campinas city has shown that districting plans can be obtained with very reasonable errors / Mestrado / Mestre em Engenharia Elétrica

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-22T11:40:25Z (GMT). No. of bitstreams: 1 Macambira_ElderMagalhaes_M.pdf: 3883760 bytes, checksum: 901048c885d22ea3a00674f4c248ef9b (MD5) Previous issue date: 1997 / Resumo: Esta dissertação dá ênfase à abordagem poliedral para a resolução exata do Problema da Clique .Máxima com Peso nas Arestas. Dado um grafo completo não-dirigido Kn = (Vn, En), onde |Vn|= n, com um peso Cij associado a cada aresta (i,j) ? En, e um inteiro b, onde b = n; procuramos uma clique C em Kn cuja sorna dos pesos das arestas em C seja máxima e |C| = b. São apresentadas e discutidas diferentes formulações de programação linear inteira para o problema. Investigamos ainda a estrutura facial do poliedro associado ao problema realizando urna revisão bibliográfica das desigualdades conhecidas e introduzindo novas famílias de facetas. Por último, descrevemos os experimentos computacionais realizados com um algoritmo branch-and-cut e com urna metaheurística, ambos propostos neste trabalho. As maiores instâncias resolvidas de forma exata para este problema na literatura referem-se a grafos completos com no máximo 30 vértices. Neste trabalho, resolvemos exatamente instâncias para grafos com até 48 vértices e mostramos a força computacional para as novas desigualdades que introduzimos. / Abstract: Given a complete non-directed graph Kn = (Vn, En) on n nodes with weights on the edges and an integer b = n, we look for a clique C in Kn whose sum of the weights of the edges in e is maximum and such that |C| = b. We discuss on different integer programming formulations and investigate the facial structure of the polyhedron associated to the problem. New families of facet defining inequalities are introduced. Finally we describe our computational experiments with a branch-and-cut algorithm and a metaheuristic that we have proposed. The largest instances that are solved exactly in the literature refer to complete graphs with at most 30 nodes. In this work we solve to optimality instances for graphs with up to 48 nodes and we show the computational strength of the new inequalities we have introduced. / Mestrado / Mestre em Ciência da Computação

Orientador: Christiano Lyra Filho / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-27T01:55:40Z (GMT). No. of bitstreams: 1 Bueno_EdilsonAparecido_M.pdf: 2749662 bytes, checksum: 4aed2eedc35e7de920f72fc065f5d3d7 (MD5) Previous issue date: 2000 / Resumo: Em sistemas de energia elétrica, continuamente ocorrem perdas, devido à resistência elétrica nas linhas e equipamentos. Estima-se que 7% de toda a energia elétrica gerada em sistemas de potência são perdidas, sendo 2% na transmissão e 5% na distribuição. O problema de minimização de perdas procura encontrar uma configuração da rede onde o montante das perdas seja reduzido. Este trabalho propõe um procedimento que combina técnicas para otimização de fluxos em redes com funções não lineares com o método GRASP para otimização combinatória. GRASP é um método iterativo que combina um método construtivo com busca local. Na fase de construção, cria uma solução viável, combinando uma função gulosa com seleção aleatória. Na fase de busca local, procura melhorar a solução. A estrutura da rede de distribuição de energia elétrica é usualmente radial. Inicialmente, relaxa-se a restrição de operação radial, encontrando-se uma solução otimista (limitante inferior) para o problema. Informações sobre os valores dos fluxos nos arcos da solução otimista são utilizadas para abrir chaves, guiando a fase de construção do método GRASP para encontrar soluções factíveis de boa qualidade. A busca local procura obter reduções adicionais de perdas através do método de troca de ramos. Estudos de casos ilustram as possibilidades da abordagem / Abstract: Energy is continuously dissipated in electric power systems due to electrical resistance in the lines and equipment. Losses amount to around 7% of total energy production, 2% in transmission and 5% in distribution. The problem of loss minimization tries to find a network configuration where the amount of losses is reduced. This work proposes a procedure that combines non-linear network flow optimization techniques with the GRASP method. GRASP is an iterative method that uses a combination of a constructive procedure with a local search. The construction phase obtains a feasible solution, combining a greedy function with a randomize selection. The local search tries to improve the solution. The structure of the electric power distribution network usually has a radial configuration. Initially, the constraint of radial operation is relaxed, meeting an optimistic solution (a lower bound) for the problem. Information from are flows in the optimistic solution are used to open switches, guiding the construction phase of GRASP to find feasible and good quality solutions. The local search tries to get additional reductions of losses through the branch-exchange procedure. Case studies iIIustrate the possibilities of the approach / Mestrado / Mestre em Engenharia Elétrica

Orientador : Marcelo Firer / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-07-27T17:53:18Z (GMT). No. of bitstreams: 1 Faria_MercioBotelho_M.pdf: 14611582 bytes, checksum: 61aa064159bcc7d73d18470e00be77ed (MD5) Previous issue date: 2000 / Resumo: Começamos o texto com uma breve apresentação de conceitos essenciais ao desenvolvimento do trabalho: uma introdução à geometria hiperbólica (capítulo 1) e grupos fuchsianos (capítulo 2), grupos discretos de isometrias do plano hiperbólico. Introduzimos a seguir, em sua forma genérica, o problema de empacotamento de esferas (capítulo 3). Apresentamos alguns resultados importantes para o caso euclidiano e a seguir, introduzimos as definições necessárias para o estudo do problema de empacotamento em espaços hiperbólicos. Neste caso, fazemos também uma apresentação de diversos resultados importantes, cobrindo parte relevante da literatura atual sobre o tema. No capítulo 4, desenvolvemos duas questões referentes a empacotamentos no plano hiperbólico (bi-dimensional). A primeira delas é o estudo da densidade local de ladrilhamentos (p,q) do plano. Provamos que a o limite da densidade local quando p e q tendem a ¥ existe e é igual a 2/p, portanto menor que o melhor limitante conhecido, a densidade simplicial d2=3/p. Este resultado conduz naturalmente à questão de determinar se, ao menos nos casos de empacotamentos associados a reticulados, a densidade local maximal é atingida em domínios de Dirichlet regulares. Para estudar esta questão, perturbamos um polígono regular de 4g lados, domínio de Dirichlet de um grupo isomorfo ao grupo fundamental de uma superfície compacta de genus g e estudamos o comportamento local da função densidade. Para isto, precisamos definir uma projeção adequada no espaço de teichmuller Tg, definida a partir de uma pseudo-homotetia do espaço hiperbólico. Analisamos então as derivadas parciais da constante de pseudo-homotetia como função da perturbação obtendo que, ao menos para uma perturbação restrita a um semi espaço fechado, a função densidade atinge um máximo local no polígono regular. Além disto, obtemos indícios que este é de fato um ponto de máximo. / Abstract: Not informed. / Mestrado / Mestre em Matemática

Orientador: Dione Lucchesi de Carvalho / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Educação / Made available in DSpace on 2018-07-28T15:52:51Z (GMT). No. of bitstreams: 1 Sturm_Wilton_M.pdf: 6516292 bytes, checksum: aaa2ae277f87c90abcca580f46f19aa4 (MD5) Previous issue date: 1999 / Resumo: A pesquisa que originou esta dissertação teve como foco os procedimentos apresentados pelos alunos e pelo professor, perante uma proposta pedagógica alternativa de Análise Combinatória. A deno minação ¿alternativa¿ deve-se a características como abertura à participação dos alunos e predominância do pensamento combinatório ao invés da ênfase às fórmulas. Foi desenvolvida em uma sala de 2' série do Ensino Médio. Uma razão que motivou este trabalho foi que boa parte dos professores consideram Análise Combinatória como algo complicado. Consideram-na um assunto de difícil entendimento por parte dos alunos. Estes, por sua vez, acabam vendo-se frente a várias fórmulas e nomenclaturas ¿sem sentido¿. Outra razão é a dificuldade de se encontrar textos relativos ao ensino de Análise Combinatória. A análise se desenvolveu numa perspectiva qualitativa, na qual o pesquisador analisou sua própria prática pedagógica, como professor da turma. O principal instrumento de registro foi o 'primaiário¿, no qual foi anotado com o máximo de detalhes o que ocorreu durante as aulas. Foram selecionados dois episódios para análises. O primeiro refere-se a um exercício trabalhado durante as aulas, que reúne a inclusão do exercício na proposta, seu desenvolvimento em aula e os momentos de debates após o mesmo ter sido apresentado. O outro episódio discute a relação entre Arranjo e Combinação, verificando como alguns textos tratam este assunto e analisando as aulas dedicadas a esta parte da proposta. Finalmente, foram feitas considerações acerca da pesquisa e mais especificamente, da proposta, e abertos horizontes para outras pesquisas / Abstract: The research that originated this dissertation had as focus the procedures presented by the students and the teacher, front an alternative pedagogical proposal of Combinatorial Analysis. The denomination alternative is due to characteristics as opening to students¿ participation and privilege of combinatorial reasoning instead of emphasis on formulas. The proposal was developed in a 2"' made classroom of high school. One reason that motivated this work was that a considerable part of teachers consider Combinatorial Analysis as something complicated. They consider it dificult to be understood by the students. The students, from their point of view, face several formulas and nomenclatures without any significance. Another reason is the difficult to find texts relationed to the teaching of Combinatorial Analysis. The analysis was developed in a qualitative perspective, in which the researcher analysed his proper pedagogical practice, being the teacher of the class. The pricipal instrument applied to report the data was the 'Primary¿, in which the researcher wrote the maximun of details of what occurred during the classes. Two episodes was selected. The first one refers to an exercise developed during the classes, with discussions about the inclusion of the exercise in the proposal, its development in the classes and the discussions that ocurred after it was presented. The other episode discusses the relation between arrangement and combination, verifying how some texts treat this subject and analysing the classes dedicated to this part of the proposal. Finally, considerations were made about the research and, more specificaly, of the proposal. Besides this, another point that can be observed is perspectives to new researches / Mestrado / Educação, Conhecimento, Linguagem e Arte / Mestre em Educação

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

Orientadores : Christiano Lyra Filho, Fernando Jose Von Zuben / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-28T21:50:26Z (GMT). No. of bitstreams: 1 Vargas_PatriciaAmancio_M.pdf: 2530480 bytes, checksum: 72376c7703959b22a234b9724e9756c4 (MD5) Previous issue date: 2000 / Mestrado