Submitted by Raildo Barros Rodrigues (raildo.barros@gmail.com) on 2018-09-24T15:10:31Z No. of bitstreams: 1 Dissertação_Grade_Horária_Raildo_Marins_Aneirson.pdf: 2926580 bytes, checksum: 6799724ac48abd21caecd50cf5156480 (MD5) / Rejected by Pamella Benevides Gonçalves null (pamella@feg.unesp.br), reason: Solicitamos que realize correções na submissão seguindo as orientações abaixo Verificar formatação com a equipe da biblioteca. Agradecemos a compreensão. on 2018-09-24T18:49:58Z (GMT) / Submitted by Raildo Barros Rodrigues (raildo.barros@gmail.com) on 2018-09-25T16:48:30Z No. of bitstreams: 2 Dissertação_Grade_Horária_Raildo_Marins_Aneirson.pdf: 2926580 bytes, checksum: 6799724ac48abd21caecd50cf5156480 (MD5) Dissertação_Grade_Horária_Raildo_Marins_Aneirson.pdf: 2944631 bytes, checksum: d0f33c161c9cb711a7b75cd2666f0470 (MD5) / Approved for entry into archive by Pamella Benevides Gonçalves null (pamella@feg.unesp.br) on 2018-09-25T18:15:24Z (GMT) No. of bitstreams: 1 rodrigues_rb_me_guara.pdf: 2944631 bytes, checksum: d0f33c161c9cb711a7b75cd2666f0470 (MD5) / Made available in DSpace on 2018-09-25T18:15:24Z (GMT). No. of bitstreams: 1 rodrigues_rb_me_guara.pdf: 2944631 bytes, checksum: d0f33c161c9cb711a7b75cd2666f0470 (MD5) Previous issue date: 2018-09-20 / Outra / Esta dissertação trata da construção de um modelo matemático para a elaboração do quadro de horários dos cursos de graduação do CBV/IFRR. A programação de horários é um problema de otimização combinatória estudado há anos pela Pesquisa Operacional e, em termos de complexidade computacional, é tido como NP-Completo, sendo assim, é um problema que exige grande capacidade de processamento. A elaboração do quadro de horários em qualquer instituição de ensino é complexa e demanda tempo para os responsáveis por essa atividade, pois as necessidades dos professores e alunos devem ser atendidas e devem-se evitar conflitos nos horários dos professores. A instituição estudada nesta dissertação assim como outras instituições, possui particularidades institucionais, dessa forma, uma formulação geral do problema acaba não lhe sendo útil. O CBV/IFRR realiza a elaboração dos horários de forma manual, por meio de planilha eletrônica e realização de reuniões entre os gestores, o que torna difícil encontrar uma solução factível. Sendo assim, foi necessária a realização de pesquisa científica para encontrar métodos que poderiam ser aplicados ao problema. Assim, este trabalho teve como objetivo desenvolver um modelo de Programação Matemática que permitisse a elaboração dos horários para cursos de graduação do CBV/IFRR. Utilizou-se entrevistas com as Coordenações de Cursos para obtenção das informações acerca do problema tratado, tais como restrições e prioridades a serem atendidas com a programação de aulas para professores. Estas informações serviram de base para a construção do modelo conceitual, que foi utilizado para elaboração do modelo matemático final, que foi implementado na linguagem de alto nível GAMS® e resolvido pelo solver CPLEX®. Os testes do modelo foram realizados otimizando uma instância com dados reais da instituição estudada. Os resultados obtidos da otimização foram satisfatórios, pois foi possível encontrar uma solução ótima para a instância em tempo computacional adequado, com todas as restrições, impostas pelas características peculiares do problema tratado, sendo respeitadas e as prioridades estabelecidas pelas Coordenações de Cursos atendidas. / This dissertation deals with the construction of a mathematical model for the elaboration of the timetable of the undergraduate courses of the CBV/IFRR. Time scheduling is a combinatorial optimization problem that has been studied for years by Operational Research and, in terms of computational complexity, is considered as NP-Complete, so it is a problem that requires large processing capacity. The elaboration of the timetable in any educational institution is complex and takes time for those responsible for this activity, because the needs of teachers and students must be met and avoid conflicts in the schedules of teachers. The institution studied in this dissertation as well as other institutions, has institutional features, so a general formulation of the problem ends up being of no use to it. The CBV/IFRR performs the elaboration of the schedules manually, through a spreadsheet and holding meetings between managers, which makes it difficult to find a feasible solution. Thus, it was necessary to carry out scientific research to find methods that could be applied to the problem. Thus, this work had the objective of developing a Mathematical Programming model that allowed the elaboration of the schedules for the undergraduate courses of the CBV/IFRR. We used interviews with the Course Coordinators to obtain information about the problem, such as constraints and priorities to be met with the programming of classes for teachers. This information was the basis for the construction of the conceptual model, which was used to elaborate the final mathematical model, which was implemented in the GAMS® high-level language and solved by the CPLEX® solver. The tests of the model were performed optimizing an instance with real data of the studied institution. The results obtained from the optimization were satisfactory, since it was possible to find an optimal solution for the instance in adequate computational time, with all the restrictions imposed by the peculiar characteristics of the problem, being respected and the priorities established by the Coordination of Courses attended.

Esta pesquisa trata da aplicação de meta-heurísticas baseadas em busca em vizinhança variável em problemas de operação de transportes. Desta forma, buscou-se encontrar problemas complexos durante a operação de sistemas de transportes, nas grandes cidades, que possam ser resolvidos com a aplicação de meta-heurística baseada em busca em vizinhança variável. Este trabalho aborda dois diferentes problemas de planejamento e operação de transportes. O primeiro problema abordado neste trabalho é o Problema de Programação da Tabela de Horários, de Veículos e de Tripulantes de Ônibus, no qual as viagens que comporão a tabela de horários, os veículos que executarão as viagens e as tripulações que operarão os veículos são alocadas simultaneamente e de maneira integrada. O segundo problema a ser abordado é o problema de distribuição física, o qual envolve o agrupamento e a alocação de entregas a uma frota de veículos visando minimizar o frete total. Uma abordagem para a modelagem matemática deste problema é modelar como um problema de bin-packing, com bins de tamanho variável unidimensional (do inglês Variable Sized Bin-Packing Problem - VSBPP), ou seja, uma generalização do tradicional problema de bin-packing no qual bins (veículos) de diferentes capacidades e custos estão disponíveis para a alocação de um conjunto de objetos (cargas), de modo que o custo total dos bins (veículos) utilizados seja mínimo. A outra abordagem proposta para o problema de distribuição física é modelar o problema como um problema de bin-packing, com bins de tamanho variável bidimensional (do inglês Bidimensional Variable Sized Bin-Packing Problem BiD-VSBPP). Assim sendo, trata-se de uma expansão do problema de bin-packing com bins de tamanho variável unidimensional (VSBPP), no qual bins (veículos) de diferentes capacidades (capacidade volumétrica e capacidade de carga) e custos estão disponíveis para a alocação de um conjunto de objetos (cargas), os quais possuem as dimensões peso e volume, de modo que o custo total dos bins (veículos) utilizados seja mínimo. Durante a realização deste trabalho, foi desenvolvido um programa computacional em C++, o qual implementa a meta-heurística Busca em Vizinhança Variável (VNS) e duas meta-heurísticas baseadas em VNS. São apresentados resultados de experimentos computacionais com dados reais e dados benchmarking. Os resultados obtidos comprovam a eficácia das meta-heurísticas propostas. / This work approaches variable neighborhood search meta-heuristic applicate on transport operation problems. This way, we sought find complex transport operation problems in large cities that can be solved with the variable neighborhood search meta-heuristic application. This work approaches two different transport planning and operation problems. The first problem approached in this paper is the Bus Timetable Vehicle Crew Scheduling Problem, in which timetabling, bus and crew schedules are simultaneously determined in an integrated approach. The second problem to be approached is the physical distribution problem which comprises grouping and assigning deliveries to a heterogeneous fleet of vehicles aiming to minimize the total freight cost. The problem can be mathematical modeled as one-dimensional Variable Sized Bin-Packing Problem (VSBPP), a generalization of the traditional bin-packing problem, in which bins (vehicles) with different sizes and costs are available for the assignment of the objects (deliveries) such that the total cost of the used bins (vehicles) is minimized. Another proposed approach to the problem of physical distribution is model as two dimensional Variable Sized Bin-Packing Problem (BiD-VSBPP). Therefore, it is an expansion of the bin-packing problem with bins variable-length-dimensional (VSBPP), in which bins (vehicle) of different capacity (capacity and load carrying capacity) and costs are available for allocation a set of objects (loads), which have the dimensions weight and volume, so that minimized the total cost of bins (vehicle). In this work, was developed a C++ software implemented, which was implemented a meta-heuristic Variable Neighborhood Search (VNS) and two others meta-heuristics based on VNS. Computational results for real-world problems and benchmarking problems are presented, showing the effectiveness of these proposed meta-heuristics.

Esta pesquisa trata da aplicação de meta-heurísticas baseadas em busca em vizinhança variável em problemas de operação de transportes. Desta forma, buscou-se encontrar problemas complexos durante a operação de sistemas de transportes, nas grandes cidades, que possam ser resolvidos com a aplicação de meta-heurística baseada em busca em vizinhança variável. Este trabalho aborda dois diferentes problemas de planejamento e operação de transportes. O primeiro problema abordado neste trabalho é o Problema de Programação da Tabela de Horários, de Veículos e de Tripulantes de Ônibus, no qual as viagens que comporão a tabela de horários, os veículos que executarão as viagens e as tripulações que operarão os veículos são alocadas simultaneamente e de maneira integrada. O segundo problema a ser abordado é o problema de distribuição física, o qual envolve o agrupamento e a alocação de entregas a uma frota de veículos visando minimizar o frete total. Uma abordagem para a modelagem matemática deste problema é modelar como um problema de bin-packing, com bins de tamanho variável unidimensional (do inglês Variable Sized Bin-Packing Problem - VSBPP), ou seja, uma generalização do tradicional problema de bin-packing no qual bins (veículos) de diferentes capacidades e custos estão disponíveis para a alocação de um conjunto de objetos (cargas), de modo que o custo total dos bins (veículos) utilizados seja mínimo. A outra abordagem proposta para o problema de distribuição física é modelar o problema como um problema de bin-packing, com bins de tamanho variável bidimensional (do inglês Bidimensional Variable Sized Bin-Packing Problem BiD-VSBPP). Assim sendo, trata-se de uma expansão do problema de bin-packing com bins de tamanho variável unidimensional (VSBPP), no qual bins (veículos) de diferentes capacidades (capacidade volumétrica e capacidade de carga) e custos estão disponíveis para a alocação de um conjunto de objetos (cargas), os quais possuem as dimensões peso e volume, de modo que o custo total dos bins (veículos) utilizados seja mínimo. Durante a realização deste trabalho, foi desenvolvido um programa computacional em C++, o qual implementa a meta-heurística Busca em Vizinhança Variável (VNS) e duas meta-heurísticas baseadas em VNS. São apresentados resultados de experimentos computacionais com dados reais e dados benchmarking. Os resultados obtidos comprovam a eficácia das meta-heurísticas propostas. / This work approaches variable neighborhood search meta-heuristic applicate on transport operation problems. This way, we sought find complex transport operation problems in large cities that can be solved with the variable neighborhood search meta-heuristic application. This work approaches two different transport planning and operation problems. The first problem approached in this paper is the Bus Timetable Vehicle Crew Scheduling Problem, in which timetabling, bus and crew schedules are simultaneously determined in an integrated approach. The second problem to be approached is the physical distribution problem which comprises grouping and assigning deliveries to a heterogeneous fleet of vehicles aiming to minimize the total freight cost. The problem can be mathematical modeled as one-dimensional Variable Sized Bin-Packing Problem (VSBPP), a generalization of the traditional bin-packing problem, in which bins (vehicles) with different sizes and costs are available for the assignment of the objects (deliveries) such that the total cost of the used bins (vehicles) is minimized. Another proposed approach to the problem of physical distribution is model as two dimensional Variable Sized Bin-Packing Problem (BiD-VSBPP). Therefore, it is an expansion of the bin-packing problem with bins variable-length-dimensional (VSBPP), in which bins (vehicle) of different capacity (capacity and load carrying capacity) and costs are available for allocation a set of objects (loads), which have the dimensions weight and volume, so that minimized the total cost of bins (vehicle). In this work, was developed a C++ software implemented, which was implemented a meta-heuristic Variable Neighborhood Search (VNS) and two others meta-heuristics based on VNS. Computational results for real-world problems and benchmarking problems are presented, showing the effectiveness of these proposed meta-heuristics.