[pt] Este trabalho apresenta uma aplicação prática do roteamento de navios com coleta-e-entrega e janelas de tempo para o alívio de plataformas de petróleos para exportação. Especificamente para este caso, os navios aliviadores fazem o transporte do petróleo de plataformas offshore diretamente para um terminal de transbordo, onde a carga será transferida para outro navio para ser exportado. Foram propostas adaptações a um modelo de programação linear inteira mista já existente, buscando descrever as peculiaridades deste processo e facilitar a sua resolução pelo método exato. O modelo foi testado com dados realísticos de uma empresa petrolífera e pode fornecer soluções de alta qualidade para testes com períodos de até 30 dias em um tempo de processamento computacional inferior a 10 minutos, estando assim adequado ao uso na rotina do programador de navios desta empresa. / [en] This study presents a practical application of ship routing with pickup-anddelivery and time windows for offloading operations in offshore oil platforms. Specifically in this case, the shuttle tankers transport crude oil from the offshore platforms directly to an onshore terminal, where the cargo will be transferred to another vessel to be exported. Adaptations to an existing mixed-integer linear programming model are proposed to better represent this process and facilitate its resolution by the exact method. The model was tested with realistic data from an oil and gas company and it can provide high-quality solutions for tests with periods up to 30 days, in a processing time of less than 10 minutes, thus being suitable for use in the routine of the company s ship programmer.

O transporte rodoviário é uma das atividades econômicas do homem que mais contribuem para a emissão de Gases de Efeito Estufa (GEE) na atmosfera. Sabe-se que a emissão de CO2 está diretamente vinculada ao consumo de combustível. Por isso, é possível encontrar uma série de trabalhos que objetivam diminuir as emissões por meio da redução do consumo de combustível dos veículos. A otimização de rotas é uma importante ferramenta para essa redução e, consequentemente, possibilita minimizar as emissões dos veículos. Esta pesquisa tem como objetivo aplicar em uma empresa líder na distribuição de revistas no país o PRP, que é um modelo de minimização do consumo de combustível/emissão de GEE por meio de ajustes das variáveis como velocidade média, quantidade de carga transportada, distância percorrida e inclinações das vias. Como a maioria das metodologias de estimativa de combustível existentes na literatura não considera a inclinação das vias nos seus cálculos, neste trabalho foi necessário desenvolver uma metodologia para incluí-la no modelo. Testes foram efetuados com variações nas janelas de tempo, e o modelo mostrou-se sensível a cada uma das variáveis analisadas, gerando economias em 100% das rotas estudadas. / Road transport is one of the biggest contributors of Greenhouse Gases emissions of all humans economic activities. It is known that CO2 emissions are directly related to fuel consumption, so that is why it is possible to find a series of studies that aims to reduce emissions by reducing vehicles fuel consumption. Route optimization is an important tool for reducing fuel consumption and hence emissions. This research aims to implement the PRP model in a leading company in the country, which is a model that minimizes fuel consumption/GHG emissions through adjustments of variables such as average speed, pay load, distance traveled and slopes of the road. Most existing fuel estimation methodologies found in the literature does not consider the slope of the roads in their calculations. So in this research it was necessary to develop a methodology to include it in the model. Tests were performed with variations in the time windows and the model was sensitive to each of the variables analyzed, generating savings on 100% of the studied routes.

Um tema pouco estudado na literatura, mas frequentemente encontrado por empresas prestadoras de serviço, é o Problema de Escalonamento de Técnicos de Campos (Field Technician Scheduling Problem). O problema consiste em associar um número de tarefas - em diversos locais, com diferentes prioridades e com janelas de tempo - a uma quantidade de técnicos - com diferentes horários de expediente e com habilidades distintas - que saem no início do horário de trabalho da sede da empresa, para onde devem retornar antes do fim do expediente. Cada tarefa é atendida por um único técnico. Esse problema é estudado neste trabalho. A primeira parte do trabalho apresenta um modelo de programação linear inteira mista (PLIM) e, dada a complexidade do problema, heurísticas construtivas e meta-heurísticas foram desenvolvidas. Na função objetivo, procura-se principalmente maximizar o número ponderado de tarefas executadas em um dia de trabalho, de acordo com as suas prioridades. Em linhas gerais, as heurísticas construtivas ordenam as tarefas de acordo com um critério pré-estabelecido e, em seguida, designam cada uma a um dos técnicos capazes de realiza-la sem violar as restrições do problema. Tendo em conta o bom desempenho obtido em outros problemas semelhantes, foi adotado um Algoritmo Genético denominado Biased Random-Key Genetic Algorithms (BRKGA), que utiliza chaves aleatórias para codificar e decodificar as soluções. Codificadores e decodificadores adaptados ao problema foram desenvolvidos e testes computacionais são apresentados. As soluções obtidas em problemas de pequenas dimensões são comparadas com as soluções ótimas conhecidas e, para aprimorar a avaliação do desempenho nas instâncias médias e grandes, quatro procedimentos para obter limitantes superiores foram propostos. Testes computacionais foram realizados em 1040 instâncias. O BRKGA encontrou 99% das 238 soluções ótimas conhecidas e, nas 720 instâncias de dimensões médias e grandes, ficou em média a 3,8% dos limitantes superiores. As heurísticas construtivas superaram uma heurística construtiva da literatura em 90% das instâncias. A segunda parte do trabalho apresenta uma nova abordagem para o Problema de Escalonamento de Técnicos de Campo: um modelo biobjetivo, onde uma segunda função objetivo buscará que as tarefas prioritárias sejam realizadas o mais cedo possível. Uma versão multiobjectivo do BRKGA foi desenvolvida, considerando diversas estratégias para classificar a população do algoritmo e escolher as melhores soluções (estratégias de elitismo). Codificadores e decodificadores foram criados para o problema multiobjectivo. Os resultados computacionais obtidos são comparados com os resultados de um Algoritmo Genético conhecido na literatura, o Nondominated Sorting Genetic Algorithm II (NSGA II). Para instâncias de pequenas dimensões, os resultados da meta-heurística proposta também são comparados com a fronteira ótima de Pareto de 234 instâncias, obtidas por enumeração completa. Em média, o BRKGA multiobjectivo encontrou 94% das soluções da fronteira ótima de Pareto e, nas instâncias médias e grandes, superou o desempenho do NSGA-II nas medidas de avaliação adotadas (porcentagem de soluções eficientes, hipervolume, indicador epsílon e cobertura). / An important topic in service companies, but little studied until now, is the field technician scheduling problem. In this problem, technicians have to execute a set of jobs or service tasks. Technicians have different skills and working hours. Tasks are in different locations within a city, with different time windows, priorities, and processing times. Each task is executed by only one technician. This problem is addressed in this thesis. The first part of the research presents the mixed integer linear programming model (MILP) and, due to the complexity of this problem, constructive heuristics and metaheuristics were proposed. The objective function is to maximize the sum of the weighted performed tasks in a day, based on the priority of tasks. In general terms, in the proposed constructive heuristics, jobs are ordered according to a criterion and, after that, tasks are assigned to technicians without violating constraints. A Genetic Algorithm (the Biases Randon Key Genetic Algorithm - -RKGA) is applied to the problem, based on its success in similar problems; the BRKGA uses random keys and a decoder transforms each chromosome of the Genetic Algorithm into a feasible solution of the problem. Decoders and encoders adapted to the problem were developed and computational tests are presented. A comparison between the solutions of the heuristic methods and optimal solutions values was also conducted for small instances and, to analyze medium and large instances, four upper bound models were proposed. Computational experiments with 1040 instances were carried out. The BRKGA reached 99% of the 238 optimal solutions and, for 720 medium and large instances, the average upper bound gap was 3,8%. Constructive heuristics overcame a heuristic of the literature in 90% of the instances. The second part of this research presents a new approach of the Field Technician Scheduling Problem: a multiobjective model, with a second objective function to execute the priority tasks as soon as possible. A multiobjective BRKGA was developed, with different strategies to classify the Genetic Algorithm population and to select the elite solutions (elite strategies). Decoders and encoders were developed for the multiobjective problem too. The results were compared with a known Genetic Algorithm, the Nondominated Sorting Genetic Algorithm II (NSGA II). For 234 small instances, the results were compared with the Pareto optimal solutions, obtained by complete enumeration. On average, the BRKGA found 94% of the Pareto optimal solutions and, for 720 medium and large instances, outperformed the NSGA-II by means of the measures adopted (percentage of efficient solutions, hypervolume, epsilon and coverage).

O transporte rodoviário é uma das atividades econômicas do homem que mais contribuem para a emissão de Gases de Efeito Estufa (GEE) na atmosfera. Sabe-se que a emissão de CO2 está diretamente vinculada ao consumo de combustível. Por isso, é possível encontrar uma série de trabalhos que objetivam diminuir as emissões por meio da redução do consumo de combustível dos veículos. A otimização de rotas é uma importante ferramenta para essa redução e, consequentemente, possibilita minimizar as emissões dos veículos. Esta pesquisa tem como objetivo aplicar em uma empresa líder na distribuição de revistas no país o PRP, que é um modelo de minimização do consumo de combustível/emissão de GEE por meio de ajustes das variáveis como velocidade média, quantidade de carga transportada, distância percorrida e inclinações das vias. Como a maioria das metodologias de estimativa de combustível existentes na literatura não considera a inclinação das vias nos seus cálculos, neste trabalho foi necessário desenvolver uma metodologia para incluí-la no modelo. Testes foram efetuados com variações nas janelas de tempo, e o modelo mostrou-se sensível a cada uma das variáveis analisadas, gerando economias em 100% das rotas estudadas. / Road transport is one of the biggest contributors of Greenhouse Gases emissions of all humans economic activities. It is known that CO2 emissions are directly related to fuel consumption, so that is why it is possible to find a series of studies that aims to reduce emissions by reducing vehicles fuel consumption. Route optimization is an important tool for reducing fuel consumption and hence emissions. This research aims to implement the PRP model in a leading company in the country, which is a model that minimizes fuel consumption/GHG emissions through adjustments of variables such as average speed, pay load, distance traveled and slopes of the road. Most existing fuel estimation methodologies found in the literature does not consider the slope of the roads in their calculations. So in this research it was necessary to develop a methodology to include it in the model. Tests were performed with variations in the time windows and the model was sensitive to each of the variables analyzed, generating savings on 100% of the studied routes.

Um tema pouco estudado na literatura, mas frequentemente encontrado por empresas prestadoras de serviço, é o Problema de Escalonamento de Técnicos de Campos (Field Technician Scheduling Problem). O problema consiste em associar um número de tarefas - em diversos locais, com diferentes prioridades e com janelas de tempo - a uma quantidade de técnicos - com diferentes horários de expediente e com habilidades distintas - que saem no início do horário de trabalho da sede da empresa, para onde devem retornar antes do fim do expediente. Cada tarefa é atendida por um único técnico. Esse problema é estudado neste trabalho. A primeira parte do trabalho apresenta um modelo de programação linear inteira mista (PLIM) e, dada a complexidade do problema, heurísticas construtivas e meta-heurísticas foram desenvolvidas. Na função objetivo, procura-se principalmente maximizar o número ponderado de tarefas executadas em um dia de trabalho, de acordo com as suas prioridades. Em linhas gerais, as heurísticas construtivas ordenam as tarefas de acordo com um critério pré-estabelecido e, em seguida, designam cada uma a um dos técnicos capazes de realiza-la sem violar as restrições do problema. Tendo em conta o bom desempenho obtido em outros problemas semelhantes, foi adotado um Algoritmo Genético denominado Biased Random-Key Genetic Algorithms (BRKGA), que utiliza chaves aleatórias para codificar e decodificar as soluções. Codificadores e decodificadores adaptados ao problema foram desenvolvidos e testes computacionais são apresentados. As soluções obtidas em problemas de pequenas dimensões são comparadas com as soluções ótimas conhecidas e, para aprimorar a avaliação do desempenho nas instâncias médias e grandes, quatro procedimentos para obter limitantes superiores foram propostos. Testes computacionais foram realizados em 1040 instâncias. O BRKGA encontrou 99% das 238 soluções ótimas conhecidas e, nas 720 instâncias de dimensões médias e grandes, ficou em média a 3,8% dos limitantes superiores. As heurísticas construtivas superaram uma heurística construtiva da literatura em 90% das instâncias. A segunda parte do trabalho apresenta uma nova abordagem para o Problema de Escalonamento de Técnicos de Campo: um modelo biobjetivo, onde uma segunda função objetivo buscará que as tarefas prioritárias sejam realizadas o mais cedo possível. Uma versão multiobjectivo do BRKGA foi desenvolvida, considerando diversas estratégias para classificar a população do algoritmo e escolher as melhores soluções (estratégias de elitismo). Codificadores e decodificadores foram criados para o problema multiobjectivo. Os resultados computacionais obtidos são comparados com os resultados de um Algoritmo Genético conhecido na literatura, o Nondominated Sorting Genetic Algorithm II (NSGA II). Para instâncias de pequenas dimensões, os resultados da meta-heurística proposta também são comparados com a fronteira ótima de Pareto de 234 instâncias, obtidas por enumeração completa. Em média, o BRKGA multiobjectivo encontrou 94% das soluções da fronteira ótima de Pareto e, nas instâncias médias e grandes, superou o desempenho do NSGA-II nas medidas de avaliação adotadas (porcentagem de soluções eficientes, hipervolume, indicador epsílon e cobertura). / An important topic in service companies, but little studied until now, is the field technician scheduling problem. In this problem, technicians have to execute a set of jobs or service tasks. Technicians have different skills and working hours. Tasks are in different locations within a city, with different time windows, priorities, and processing times. Each task is executed by only one technician. This problem is addressed in this thesis. The first part of the research presents the mixed integer linear programming model (MILP) and, due to the complexity of this problem, constructive heuristics and metaheuristics were proposed. The objective function is to maximize the sum of the weighted performed tasks in a day, based on the priority of tasks. In general terms, in the proposed constructive heuristics, jobs are ordered according to a criterion and, after that, tasks are assigned to technicians without violating constraints. A Genetic Algorithm (the Biases Randon Key Genetic Algorithm - -RKGA) is applied to the problem, based on its success in similar problems; the BRKGA uses random keys and a decoder transforms each chromosome of the Genetic Algorithm into a feasible solution of the problem. Decoders and encoders adapted to the problem were developed and computational tests are presented. A comparison between the solutions of the heuristic methods and optimal solutions values was also conducted for small instances and, to analyze medium and large instances, four upper bound models were proposed. Computational experiments with 1040 instances were carried out. The BRKGA reached 99% of the 238 optimal solutions and, for 720 medium and large instances, the average upper bound gap was 3,8%. Constructive heuristics overcame a heuristic of the literature in 90% of the instances. The second part of this research presents a new approach of the Field Technician Scheduling Problem: a multiobjective model, with a second objective function to execute the priority tasks as soon as possible. A multiobjective BRKGA was developed, with different strategies to classify the Genetic Algorithm population and to select the elite solutions (elite strategies). Decoders and encoders were developed for the multiobjective problem too. The results were compared with a known Genetic Algorithm, the Nondominated Sorting Genetic Algorithm II (NSGA II). For 234 small instances, the results were compared with the Pareto optimal solutions, obtained by complete enumeration. On average, the BRKGA found 94% of the Pareto optimal solutions and, for 720 medium and large instances, outperformed the NSGA-II by means of the measures adopted (percentage of efficient solutions, hypervolume, epsilon and coverage).

O tema de roteamento de veículos é de grande importância na literatura e tem sido amplamente estudada pela sua importância para muitas indústrias. Com a evolução na literatura, mais características foram adicionadas para torná-lo mais próximo de situações reais. Alinhado com esta tendência, este trabalho aborda o problema de roteamento de veículos quando há a terceirização da frota que realiza as entregas. Uma forma de cobrança do frete é por meio de custos escalonados, que são calculados de acordo com o tipo de veículo e a distância percorrida, com valores fixos para cada faixa de distância. Embora seja uma forma comum de trabalho na indústria, nenhum trabalho focado nesta característica foi encontrado na literatura. Este problema é o problema de roteamento de veículos com frota mista, janelas de tempo e custos escalonados (FSMVRPTWSC). Ao abordar este problema, este trabalho apresenta um modelo de programação linear inteira mista que é avaliado em um cenário real da indústria. Além disso, três heurísticas de inserção sequencial são propostas para lidar com problemas maiores. Estes métodos são examinados por meio de testes computacionais em 168 problemas de referência gerados para este problema. Os experimentos numéricos mostram que os métodos são robustos e eficientes, apresentando um bom desempenho em conjuntos de problemas com diversas características. / The theme of vehicle routing is of great importance in the literature and has been widely studied for its relevance to many industries and, throughout the literature, more characteristics have been added to make it closer to real situations. Aligned with this trend, this paper addresses the vehicle routing problem when there is outsourcing of the fleet that delivers goods. One form of freight charging is by scaled costs, which are calculated according to the type of vehicle and the distance traveled, with fixed values for each distance range. Though it is a common form of work in the industry, no work focused on this characteristic was found in the literature. This problem is the fleet size and mix vehicle routing problem with time windows and scaled costs (FSMVRPTWSC). In approaching this problem, this paper presents a mixed integer linear programming model that is evaluated under a real situation scenario. Furthermore, three sequential insertion heuristics are proposed in order to deal with larger problems. These methods are examined through a computational comparative study in 168 benchmark problems generated for this problem. The numerical experiments show that the methods are robust and efficient, performing well in different problem sets.

Submitted by Victor Mario Noble Ramos (vicmanr90@gmail.com) on 2017-12-01T18:27:41Z No. of bitstreams: 2 TextoFinalDissertationVicman-PosDefesa.pdf: 37720288 bytes, checksum: e8e3336733bc8151bd42eab9118f2b2a (MD5) CartaTextoFinal.pdf: 241030 bytes, checksum: 8c46be374e02fb08ecd2b0f6ac30a27b (MD5) / Approved for entry into archive by Milena Rubi ( ri.bso@ufscar.br) on 2017-12-04T12:40:00Z (GMT) No. of bitstreams: 2 TextoFinalDissertationVicman-PosDefesa.pdf: 37720288 bytes, checksum: e8e3336733bc8151bd42eab9118f2b2a (MD5) CartaTextoFinal.pdf: 241030 bytes, checksum: 8c46be374e02fb08ecd2b0f6ac30a27b (MD5) / Approved for entry into archive by Milena Rubi ( ri.bso@ufscar.br) on 2017-12-04T12:40:12Z (GMT) No. of bitstreams: 2 TextoFinalDissertationVicman-PosDefesa.pdf: 37720288 bytes, checksum: e8e3336733bc8151bd42eab9118f2b2a (MD5) CartaTextoFinal.pdf: 241030 bytes, checksum: 8c46be374e02fb08ecd2b0f6ac30a27b (MD5) / Made available in DSpace on 2017-12-04T12:40:54Z (GMT). No. of bitstreams: 2 TextoFinalDissertationVicman-PosDefesa.pdf: 37720288 bytes, checksum: e8e3336733bc8151bd42eab9118f2b2a (MD5) CartaTextoFinal.pdf: 241030 bytes, checksum: 8c46be374e02fb08ecd2b0f6ac30a27b (MD5) Previous issue date: 2017-11-24 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / This dissertation adresses the general integrated lot sizing and scheduling problem for non-alcoholic beverage production with synchronization between stages and operating time windows for scheduling preventive maintenances. The problem is characterized by having two interdependent synchronized stages. In the first stage, machines (tanks) can supply several filling lines at the same time in the second stage, where the final items are packed. Production sequence-dependent times and costs exist. The review of the related literature indicates that existing models refer, generally, to particular cases of the general problem adressed here, the most common cases are the dedication of tanks to the lines, and disregarding the perishability of syrups and the possibility of scheduling preventive maintenances. A mathematical model for the general problem, called SMMRPM, has been proposed and applied in several instances to show the adherence and flexibility of the model to represent practical cases that can be found in reality. For the case of the dedication of tanks to lines, the model was compared with the dedicated model F1 (FERREIRA et al, 2012). The results indicate that the SMMRPM model is flexible and adherent to represent practical scenarios in which other models are not applicable, for example the possibility of scheduling preventive maintenance and consideration of perishability are differential of the proposal. In the plans obtained, it was shown that it is important to include these considerations that significantly affect the productive plans. In the case of dedication, compared to the dedicated model, the formulation SMMRPM achieves production plans, on average, 52.63 \% less costly than F1. / Nesta dissertação de mestrado é pesquisado o problema geral integrado de dimensionamento e sequenciamento de lotes da produção de bebidas não alcoólicas com sincronia ente os estágios e janelas de tempo de operação para programação de manutenções preventivas. O problema é caracterizado por ter dois estágios sincronizados e dependentes entre si. As máquinas do primeiro estágio (tanques) podem suprir ao mesmo tempo várias linhas de envase no segundo estágio, onde são envasados os itens finais. Existem tempos e custos de setup dependentes da sequência de produção. A revisão da literatura relacionada indica que modelos existentes referem-se, em geral, a casos particulares do problema geral aqui tratado, sendo que os casos mais comuns são a dedicação de tanques à linhas, e desconsideração da perecibilidade dos xaropes e da possibilidade de programar manutenções preventivas. Foi proposto um modelo matemático para o problema geral, denominado SMMRPM, e aplicado em diversas instâncias a fim de mostrar a aderência e a flexibilidade do modelo para representar casos práticos que podem ser achados na realidade. Para o caso da dedicação de tanques a linhas, o modelo foi comparado com o modelo dedicado F1 (FERREIRA et al, 2012). Os resultados indicam que o modelo SMMRPM é flexível e aderente para representar cenários práticos em que outros modelos não são aplicáveis, por exemplo a possibilidade de programar manutenções preventivas e consideração da perecibilidade são diferenciais da proposta. Nos planos obtidos foi mostrada a importância da inclusão destas considerações que afetam significativamente os planos produtivos. No caso da dedicação, comparado com o modelo dedicado, a formulação SMMRPM consegue planos de produção, em média, 52.63 % menos custosos que o F1. / Demanda Social

O tema de roteamento de veículos é de grande importância na literatura e tem sido amplamente estudada pela sua importância para muitas indústrias. Com a evolução na literatura, mais características foram adicionadas para torná-lo mais próximo de situações reais. Alinhado com esta tendência, este trabalho aborda o problema de roteamento de veículos quando há a terceirização da frota que realiza as entregas. Uma forma de cobrança do frete é por meio de custos escalonados, que são calculados de acordo com o tipo de veículo e a distância percorrida, com valores fixos para cada faixa de distância. Embora seja uma forma comum de trabalho na indústria, nenhum trabalho focado nesta característica foi encontrado na literatura. Este problema é o problema de roteamento de veículos com frota mista, janelas de tempo e custos escalonados (FSMVRPTWSC). Ao abordar este problema, este trabalho apresenta um modelo de programação linear inteira mista que é avaliado em um cenário real da indústria. Além disso, três heurísticas de inserção sequencial são propostas para lidar com problemas maiores. Estes métodos são examinados por meio de testes computacionais em 168 problemas de referência gerados para este problema. Os experimentos numéricos mostram que os métodos são robustos e eficientes, apresentando um bom desempenho em conjuntos de problemas com diversas características. / The theme of vehicle routing is of great importance in the literature and has been widely studied for its relevance to many industries and, throughout the literature, more characteristics have been added to make it closer to real situations. Aligned with this trend, this paper addresses the vehicle routing problem when there is outsourcing of the fleet that delivers goods. One form of freight charging is by scaled costs, which are calculated according to the type of vehicle and the distance traveled, with fixed values for each distance range. Though it is a common form of work in the industry, no work focused on this characteristic was found in the literature. This problem is the fleet size and mix vehicle routing problem with time windows and scaled costs (FSMVRPTWSC). In approaching this problem, this paper presents a mixed integer linear programming model that is evaluated under a real situation scenario. Furthermore, three sequential insertion heuristics are proposed in order to deal with larger problems. These methods are examined through a computational comparative study in 168 benchmark problems generated for this problem. The numerical experiments show that the methods are robust and efficient, performing well in different problem sets.