Esta dissertação trata do problema da distribuição de combustíveis com caminhões-tanque para realizar a entrega de derivados de petróleo para diversos postos de abastecimento a partir de uma base de distribuição. O problema consiste da determinação de rotas para veículos de uma frota heterogênea, visando minimizar o custo total de distribuição dos veículos envolvidos sujeitos a restrições de capacidade dos compartimentos de cada veículos. O objetivo é garantir que cada entrega seja alocada a exatamente um veículo e que todos os veículos sejam adequadamente seqüenciados. Deve-se notar que cada caminhão pode ter até seis compartimentos com diferentes capacidades. Além disso, são consideradas restrições que impedem que um veículo atenda determinado cliente. As restrições relacionadas a essa alocação de pedidos aos compartimentos dos veículos fazem esse problema tornar-se muito diferente de outros problemas de roteirização de veículos. Para ilustrar isso, uma entrega de 5.000 litros para um cliente apenas pode ser alocada em um compartimento de exatamente 5.000 litros, mas não a um compartimento maior preenchido parcialmente. Adicionalmente, caminhões do mesmo tamanho e capacidade (e.g. 30.000 litros) podem possuir diferentes números de compartimentos, inclusive de diferentes tamanhos (e.g. um caminhão de 30.000 litros pode ter 6 compartimentos de 5.000 litros ou 2 compartimentos de 10.000 litros e 2 compartimentos de 5.000 litros), tornando o problema aindamais complexo. Propõe-se inicialmente uma modelagem matemática inédita para o problema. Dada a dificuldade de resolver instâncias de tamanhos reais utilizando ferramentas comerciais de otimização como o ILOG CPLEX 9.0, foi também proposto um algoritmo heurístico que pode alcançar boas soluções em tempos curtos de processamento. Este algoritmo é inspirado em algumas idéias do GRASP. ) Ele se baseia em um método heurístico rápido de construção, que é repetidamente aplicado, baseado em um algoritmo de controle que, repedida e aleatoriamente, remove alguns pedidos da solução corrente, e então reconstrói uma nova solução a partir dos pedidos não-alocados restantes. Também são relatados resultados computacionais com diversos problemas de teste que foram gerados, considerando diferentes tamanhos de problema, bem como diferentes níveis de dificuldade de alocação de pedidos aos caminhões. / This Master\'s dissertation deals with the problem of distributing fuels by petroleum tank trucks in the context of the delivery of petroleum products to gas stations originating at a single distribution base. The problem comprises determining the vehicle delivery routes for a heterogeneous fleet, aiming to minimize the total distribution and fixed costs of the vehicles involved subject to capacity constraints for the tank compartments of each vehicle. The objective is to ensure that each delivery is assigned to exactly one truck and all trucks are properly sequenced. It should be noticed that each truck may have one to six tank compartments with different capacities eventually. In addition, there may be restrictions on which vehicles can service each client. The constraints related to the assignment of deliveries to truck compartments makes this problem much different from other vehicle routing problems, thus preventing the traditional routing approaches and formulations to be applied in this case. To illustrate this, a delivery of 5,000 liters to a single client can only be assigned to a compartment of exactly 5,000 liters, but not to a larger compartment which is not entirely filled up. In addition, trucks of the same size and capacity (e.g. 30,000 liters) may have different numbers of compartments and even different sizes (e.g. a 30,000 liters truck may have 6 compartments of 5,000 liters or 2 compartments of 10,000 liters and 2 compartments of 5,000 liters), making the problem even more complicated. We initially propose a novel mathematical IP formulation for this problem. Given the difficulty to solve instances of the same size as found in practice using off-the-shelf cutting-edge optimization tools like ILOG CPLEX 9.0, we also propose a heuristic algorithm that can reach good solutions in very short CPU times. This algorithm is inspired on some ideas of GRASP. ) It relies on a fast constructive heuristic, which is repeatedly applied, based on a control algorithm that repeatedly and randomly remove some deliveries from the current solution, and then rebuilds a new solution from the remaining unassigned and unrouted deliveries. We also report the computational results with several test problems that we have generated, considering different problem sizes, as well as different levels of difficulty related to assignment of orders to trucks.

A necessidade de redução de custos logísticos tem obrigado as empresas a colaborar entre si. O problema de logística colaborativa aqui enfocado é assim definido: identificar ciclos (ou seja, um percurso fechado) em um conjunto de rotas de carga de lotação (onde o caminhão coleta carga em um ponto e vai diretamente ao local de descarga, pois é completamente preenchido) de vários embarcadores de forma a minimizar o reposicionamento (isto é, viagens sem carga útil) de caminhões, dado que o subconjunto de rotas de um determinado embarcador pode conter rotas que complementam aquelas de outro. Desta maneira, vários embarcadores combinados podem oferecer aos transportadores um conjunto de ciclos com movimentação regular de veículos com carga completa e com mínimo reposicionamento. Esse problema pode ser modelado como um problema particular de cobertura de conjuntos com restrição de ciclos, o problema de cobertura de rotas com cardinalidade restrita (PCRCR), que é NP-Hard. Este estudo apresenta uma heurística alternativa que obtém resultados, em média, 1,74% melhores que a literatura existente, além de solucionar instâncias maiores. Ademais, o tempo de execução da heurística cresce de forma polinomial em função do tamanho do problema, ao contrário dos demais métodos aqui avaliados, que possuem comportamento exponencial. / Cost and sustainability imperatives are compelling reasons to make companies to collaborate with each other in order to operate more efficiently. The shipper collaboration problem can be defined as how to identify tours (i.e. a closed path) in a set of lanes from various shippers that minimize truck repositioning (deadheads), as the sub-set of routes from a single shipper may have lanes that complement the routes of another shipper. Thus, combined shippers may offer to carriers a set of tours with regularly executed truckload movements (where the truck loads at a point and go directly to the disposal location) with minimum asset repositioning. This problem can be modeled as a particular case of the set covering formulation with constrained cycles, the cardinality constrained lane covering problem (CCLCP), which is NP-hard. This work resents an alternative heuristic that obtains results about 1.74% better than the existing literature, and solves larger instances. Besides, the heuristics execution time presents polynomial growth, unlike other methods that have exponential behavior.

Este trabalho trata de um problema de programação de tarefas em ambiente flow shop com algumas características específicas que, juntas, o diferenciam dos problemas usuais. Há N tarefas a serem processadas por M máquinas independentes e cada tarefa tem seu roteiro particular ao longo da oficina (shop), não passando necessariamente por todas as máquinas; cada tarefa deve ser concluída dentro de um respectivo intervalo de tempo, designado de janela de tempo, e há punições por adiantamento e atraso na conclusão da tarefa. O desempenho da programação é medido pela soma das punições por adiantamento e atraso. Trata-se de um problema de natureza combinatória, pertencente à classe NP-Difícil, para o qual, no limite, há (N !)^M alternativas. Neste trabalho, propõe-se um modelo matemático para representação do problema; para sua resolução é utilizado o pacote de programação linear mista inteira CPLEX; dada a dificuldade da obtenção de solução exata para as instâncias maiores, são propostas heurísticas para resolução do problema. São apresentados também procedimentos combinados, utilizando uma solução inicial gerada por heurística e o modelo matemático, quer usando a estrutura geral de ramificação do CPLEX, quer usando a técnica de ramificação local (Local Branching). / This study focuses a job scheduling problem in a flow shop with some specific features, which, all together, make it different from the usual flow shop scheduling problems. There are N jobs to be processed in M different machines and each job has a particular route, skipping, eventually, one or more machines; each job should be finished within a time interval, called time window, and there are penalties for earliness and tardiness. This is a combinatorial problem for which, in the extreme case, there are (N!)^M solutions, belonging to NP-Hard class. In this study, a mathematical model is proposed for representing the problem; the CPLEX solver is used for solving the mixed integer linear problem obtained. Given the computational complexity of the model, heuristic procedures are proposed in order to solve large- scale instances of this problem. Combined procedures, using an initial solution obtained by a proposed heuristic and the mathematical model, either using the general branching procedure of CPLEX or a specific local branching procedure, are also shown.

O objetivo desse trabalho é o de estudar o problema de programação de tarefas num ambiente produtivo com uma única máquina com data comum de entrega. Nesse caso, as tarefas, depois de processadas uma única vez na máquina, devem ser entregues em uma data comum e sofrem penalidades de adiantamento e de atraso conforme o instante em que são completadas. Na prática, esse problema é encontrado em casos de pedidos de lotes de produtos com data de entrega comum préespecificada, embarques para exportação e material químico ou misturas que têm vida média de curta duração. Problemas desse tipo são NP-hard (Hall, Kubiak & Sethi, 1991; Hoogeven & van de Velde, 1991), sendo comumente tratados na literatura através de heurísticas e meta-heurísticas. Visto não ser de nosso conhecimento a existência na literatura de tratamento desse problema através de métodos exatos, propôs-se a utilização de um algoritmo do tipo branch-and-bound para obtenção da solução ótima do problema que minimize a soma das penalidades de adiantamento e de atraso. No desenvolvimento do algoritmo, a utilização de propriedades do problema foi importante na elaboração de limitantes inferiores e regras de dominância que melhoraram a eficiência do modelo. Os experimentos realizados avaliaram o desempenho de diferentes critérios elaborados, como escolha do nó pai, limitante inferior, ordem de execução das estratégias e ordem de construção da seqüência. Os resultados obtidos mostraram-se robustos quando comparados com o benchmark da literatura e revelaram o bom desempenho do modelo para problemas de pequeno porte, superando o desempenho de programas de otimização comerciais. / The objective of this work is to study the single-machine scheduling problem with a common due date. In this case, jobs, after be processed only once in the machine, must be delivered in a common due date and they are penalized of earliness or tardiness according to their completion time. This problem is found in cases of batch production with prespecified common due date, exportation shipping and chemical material that has short half-life period. This kind of problem is NP-hard (Hall, Kubiak & Sethi, 1991; Hoogeven & van de Velde, 1991) and it has been treated in the literature by heuristics and meta-heuristics. Not having knowledge about previous treatment by exact methods in the literature, it was proposed the implementation of a branch-and-bound algorithm to obtain the optimal solution that minimizes the total weighted earliness and tardiness penalties. In the development of the algorithm, the utilization of problem properties was important to the elaboration of lower bounds and pruning rules that have enhanced the efficiency of the model. The realized tests have evaluated the performance of different criteria, like the choice of father node, lower bound, strategy execution order and sequence construction order. The obtained results have demonstrated robustness comparing to benchmark and they have revealed the good working of the model for small problems, overcoming optimization software performance.

Nesta tese foi considerado o problema de classificação de objetos (indivíduos, empresas, produtos) em dois ou mais grupos. A abordagem tradicional se fundamenta principalmente em modelos como Logit ou Análise Discriminante. Resulta deste modo, como função de classificação, uma medida estatística - um ponto de corte (escore) ou uma medida de distância padronizada ao centro do agrupamento ou uma hipersuperfície de separação - definida com a utilização simultânea de toda a amostra. No modelo proposto foi considerado que as variáveis de classificação são limitadas, inferior ou superiormente. Esta hipótese determina uma fronteira, limite da região domínio de cada grupo em observação. Objetivou-se, como proposta final, efetuar o desenvolvimento de uma técnica para identificar estas fronteiras, associado a uma medida de natureza probabilística para cada unidade observada, especificando quanto a mesma está inserida em seu respectivo grupo, relativamente à fronteira deste. Em seguida foram propostos os procedimentos para classificar nova unidade objeto, no grupo onde a medida de inserção fosse maior e, também, procedimentos para viabilizar o refinamento constante da forma das envoltórias, a partir da análise de novas unidades. Para avaliação, foram utilizados dois exemplos ilustrativos, possibilitando o teste do modelo contra as técnicas de Análise Discriminante, Regressão Logística e mesmo Programação Linear Inteira, testada pelo autor de um dos exemplos. Os resultados se mostraram favoráveis, apontando para a viabilidade do uso do modelo.

O Problema de Transporte de Derivados de Petróleo em Oleodutos consiste em determinar como operar uma rede de oleodutos, atendendo às demandas dos mercados locais, levando em conta o plano de produção dentro de um horizonte temporal pré-estabelecido, satisfazendo restrições operacionais e minimizando os custos de transporte nos oleodutos. A realidade atual vivida pela indústria do petróleo no Brasil aponta para uma tendência de independência crescente entre os envolvidos com a distribuição dutoviária. Este novo cenário exigirá maior segurança e privacidade da informação trocada entre os participantes, impossibilitando um processo de solução centralizado como o atual. Este trabalho mostra a adequação de modelar este problema como um DCOP (Problema de Satisfação de Restrições Distribuído com Otimização), onde as variáveis e restrições são distribuídas entre múltiplos agentes autônomos, que representam diferentes terminais e refinarias, de forma a manter a privacidade das informações associadas a cada um deles. Para a solução deste DCOP é utilizado o algoritmo Adopt (Assíncrono Distribuído com Otimização), que foi adaptado para o problema de oleodutos e comparado com o algoritmo SBB (Branch-and-Bound Sincronizado), um algoritmo reconhecidamente completo para DCOP. Esta avaliação de desempenho é realizada utilizando tanto a métrica tradicional de Número de Ciclos, quanto a métrica de Custo Cumulativo, que é uma alternativa para algoritmos distribuídos genéricos, e considera diferentes heurísticas para Adopt e SBB. Além disso, uma técnica de pré-processamento foi desenvolvida para melhorar a eficiência do Adopt. Tal como no trabalho original do Adopt, os resultados experimentais confirmam sua superioridade sobre o SBB também para este tipo de problema, e indicam as heurísticas mais adequadas.

A área crítica para vigilância do espaço aéreo Brasileiro é a Amazônia Legal, cobrindo uma área de aproximadamente 5,08 milhões de quilômetros quadrados. O problema de localizar um dado número de facilidades de vigilância ou localizar um dado número de esquadrões de interceptação para maximizar a área de cobertura em uma definida região geográfica é conhecido na literatura como um Problema de Localização de Máxima Cobertura (Maximum Covering Location Problem - MCLP). O objetivo deste trabalho é apresentar o MCLP, sugerindo novas restrições para adaptá-lo à realidade do problema estudado. Como resultado foi desenvolvida uma metodologia que se mostra flexível para aplicações na situação em estudo e em outras áreas de interesse da Força Aérea Brasileira. Os resultados obtidos no estudo de caso mostram que tal metodologia auxilia o decisor, mostrando a variação com relação à área de cobertura quando se deseja trabalhar com diferentes alcances de missão e restrições impostas às características das localidades de facilidades utilizadas, como por exemplo a bonificação logística, que indica o grau de facilidade operacional de implantação do esquadrão na localidade de facilidade.

A Racionalização dos recursos num sistema hospitalar pode ser melhorada e depende, dentre outros fatores, de políticas de admissão de pacientes que podem ser implementadas pelo controle nas admissões e pela combinação de altas prematuras de pacientes com Assistência Domiciliar (Homecare). A Assistência Domiciliar destina-se a pacientes cujo tratamento exige internações prolongadas e freqüentes. Este trabalho tem como objetivos (a) apresentar o sistema de Assistência Domiciliar como política viável de controle de alta hospitalar; e (b) apresentar a formulação de um modelo de Processo Markoviano de Decisão aplicado à Assistência Domiciliar de pacientes. Estes pacientes são classificados em pacientes tipo 1 (graves) e pacientes tipo 2 (não graves). O modelo matemático proposto permite monitorar a chegada dos pacientes tipo 2 e alta prematura de ambos os tipos de pacientes no sistema. A adoção do programa de Assistência Domiciliar depende da elegibilidade do paciente para este tipo de tratamento, que inclui aspectos social e econômico do paciente além da classificação da complexidade da doença.

Atualmente existem vários métodos para a análise de eficiência de unidades produtivas, os quais apresentam vantagens e limitações quanto à sua aplicação. Dois desses métodos podem ser encontrados com maior grau de regularidade na literatura: a Análise por Envoltória de Dados (DEA) e a Análise por Fronteira Estocástica (SFA). O DEA estima uma fronteira não paramétrica linear por partes, constituída pelas unidades eficientes. O SFA trata da análise de fronteira de modo estocástico, o qual supõe que as incertezas seguem alguma distribuição de probabilidade, introduzindo no modelo o termo de erro. O objetivo deste trabalho é desenvolver um estudo comparativo entre o DEA e o SFA, de forma empírica, baseado em uma mesma massa de dados. Para tanto, os métodos de comparação de eficiência estudados foram confrontados à luz de informações obtidas do segmento aéreo brasileiro entre os anos de 1997 e 2004, utilizando quatro modelos distintos: Cross section aplicado a cada ano, cross section da totalidade de dados de todos os anos, panel data sem a inclusão de variáveis exógenas e panel data com a inclusão de variáveis exógenas. Os resultados de eficiência de cada unidade produtiva em cada um dos modelos foram então comparados entre si utilizando o teste de Wilcoxon-Mann-Whitney. Ao fim, foram encontradas indicações de que, quando do uso de uma base de dados com um maior número de amostras e DMUs, a utilização preferencial de um dos métodos não parece ser extremamente relevante. Outrossim, a restrição do uso desses métodos parece estar mais relacionada com a limitação do formato que a base de dados impõe. Porém, a possibilidade de inclusão de variáveis exógenas, assim como a inclusão de um termo que trata do ruído estatístico no método SFA, parece trazer vantagens significativas na maioria das análises, se comparada com o método DEA.

O mercado de transporte aéreo apresenta em todo o mundo um contínuo crescimento na demanda de passageiros, provocando o aumento do fluxo de operações dos aeroportos. Para absorver este crescimento e evitar problemas, como congestionamentos e atrasos de vôos, estudos apontam soluções de longo e curto prazo aos aeroportos. A expansão da infra-estrutura aeroportuária é uma das soluções de longo prazo, no entanto, de alto investimento e inviável em determinadas situações. Este fato eleva a importância de soluções de curto prazo, como a otimização da utilização dos recursos disponíveis. Neste contexto, este trabalho se faz pertinente por desenvolver um modelo matemático de otimização da designação dos vôos aos gates, aplicado ao Aeroporto Internacional de São Paulo/Guarulhos (AISP/GRU), um dos principais do país. O modelo matemático foi formulado como um problema de programação linear inteira binário, com a função objetivo de minimizar a distância total caminhada pelos passageiros e o número de passageiros a embarcar e desembarcar em posições remotas. O tempo de processamento computacional para obter uma solução ótima exata, utilizando o software AIMMS versão 3.7, com o solver CPLEX 10.1, foi muito rápido (em torno de segundos). A solução da designação dos vôos aos gates, realizada manualmente pelos operadores da Empresa Brasileira de Infra-Estrutura Aeroportuária (Infraero) do AISP/GRU, foi considerada no estudo como uma referência comparativa para análise de desempenho do modelo matemático proposto. Os indicadores de desempenho foram: distância média caminhada por passageiro e número de passageiros e de vôos alocados em posições remotas. O modelo matemático aplicado na fase de planejamento e posteriormente na fase operacional do AISP/GRU, apresenta um desempenho superior em todos os indicadores em comparação às soluções da Infraero. Desta forma, conclui-se que para absorver a demanda crescente por transporte aéreo, o desenvolvimento do modelo matemático pode ser uma das soluções de curto prazo, capaz de melhorar a qualidade dos serviços aos passageiros.