Esta tese estuda a implementação de heurísticas e da metaheurística scatter search (SS) em um problema de roteirização de veículos com frota heterogênea, janelas de tempo e entregas fracionadas (Heterogeneous Fleet Vehicle Routing Problem with Time Windows and Split Deliveries – HFVRPTWSD). O HFVRPTWSD é uma combinação do problema de roteirização com frota heterogênea (HFVRP), problema de roteirização de veículos com janelas de tempo (VRPTW) e problema de roteirização com entregas fracionadas (VRPSD). O problema é baseado em um único depósito, a demanda dos clientes pode ser maior que a capacidade dos veículos e, além das restrições de janelas de tempo, há também restrições de capacidade dos veículos e restrições quanto ao tipo de veículo. O VRPSD foi introduzido na literatura por Dror e Trudeau em 1989. No problema de roteirização de veículos com entregas fracionadas, cada cliente pode ser abastecido por mais de um veículo, enquanto no problema clássico de roteirização de veículos (VRP), cada cliente é atendido por um único veículo. Desta forma, para o VRPSD, além dos roteiros de entrega, deve-se determinar a quantidade entregue a cada cliente em cada veículo. Todos os problemas de roteirização com entregas fracionadas encontrados na literatura (VRPSD e suas extensões) têm como característica frota homogênea. O problema estudado neste trabalho difere, portanto, de todos os problemas de roteirização com entregas fracionadas da literatura, pois tem, como característica, frota heterogênea. O mesmo raciocínio vale para problemas de roteirização de veículos com frota heterogênea. Os modelos são aplicados em uma rede de varejo no Brasil que é abastecida a partir de um centro de distribuição. A rede compõe um total de 519 lojas distribuídas em 12 estados do país. As heurísticas e a metaheurística scatter search também são aplicadas em três conjuntos de problemas encontrados na literatura (SOLOMON, 1987; HO E HAUGLAND, 2004; LIU E SHEN, 1999), com o objetivo de avaliar o desempenho dos algoritmos para cada problema. O problema consiste em determinar, a cada dia, como alocar os caminhões às lojas, a quantidade de carga em cada caminhão a ser entregue em cada uma das lojas, qual o melhor roteiro e o tempo de início de atendimento do primeiro cliente da rota, de forma a minimizar o custo total de distribuição, garantindo que a demanda das lojas seja atendida e as demais restrições do problema sejam respeitadas. Para a resolução do VRPSD e suas extensões, a única metaheurística encontrada na literatura foi busca tabu. Para o problema de roteirização com frota heterogênea e suas extensões, foram implementadas apenas as metaheurísticas busca tabu e BATA (Back-Tracking Adaptative Threshold Accepting). As estratégias de solução propostas no presente trabalho consistem na implementação de heurísticas construtivas e da metaheurística scatter search. As soluções iniciais de SS são obtidas através da implementação de quatro heurísticas construtivas: heurística de economias, heurística de inserção seqüencial baseada nas idéias de Solomon (1987), heurística de inserção seqüencial baseada nas idéias de Ho e Haugland (2004) e adaptação da heurística de inserção seqüencial de Dullaert et al. (2002). Para o caso real, foi possível uma redução no custo total da frota comparado com a solução atual da empresa. Para algumas instâncias dos três conjuntos de problemas da literatura, os algoritmos apresentaram resultados similares ou superiores às melhores soluções encontradas. / This thesis studies the implementation of heuristics and scatter search (SS) metaheuristic in a Heterogeneous Fleet Vehicle Routing Problem with Time Windows and Split Deliveries (HFVRPTWSD). The HFVRPTWSD is a combination of Heterogeneous Fleet Vehicle Routing Problem (HFVRP), Vehicle Routing Problem with Time Windows (VRPTW) and Vehicle Routing Problem with Split Deliveries (VRPSD). The problem is based in a single depot, the demand of each client can be greater than the vehicle’s capacity and beyond the time windows constraints, and there are also constraints on the vehicle capacity and vehicles type. The VRPSD was introduced in the literature by Dror e Trudeau in 1989. In the split deliveries vehicle routing problem, each client can be supplied by more than one vehicle; while in a classic vehicle routing problem (VRP) each client is supplied by only one vehicle. Thus, for the VRPSD, besides the delivery routes, the amount to be delivered to each client in each vehicle must also be determined. All the split delivery vehicle routing problems researched in the literature (VRPSD and its extensions) have as a characteristic the homogeneous fleet. Therefore, the problem studied differs from the split deliveries vehicle routing problems of the literature because it has a heterogeneous fleet. The same reasoning can be applied in heterogeneous fleet vehicle routing problem. The models will be applied in a retail market in Brazil that is supplied by a distribution center. The market has 519 stores distributed in 12 Brazilian states. The heuristics and the scatter search metaheuristic will also be applied in three benchmark problems (SOLOMON, 1987; HO AND HAUGLAND, 2004; LIU AND SHEN, 1999), aiming to evaluate the design of the algorithms for each problem. The problem consists in determining, each day, how to allocate the trucks to the stores, the amount to be delivered in each truck to each client, which one is the best route and the initial time for attending the first client, with the aim of minimizing the total distribution cost, attending the clients’ demand and respecting all the problem’s constraints. For the VRPSD and its extensions, the only metaheuristic implemented in the literature was tabu search. For the heterogeneous fleet vehicle routing problem and its extensions, only the tabu search and BATA (Back-Tracking Adaptative Threshold Accepting) metaheuristics have been implemented. The strategies proposed here consist in the implementation of constructive heuristics and the scatter search metaheuristic. The initial solutions of SS are obtained with the implementation of four constructive heuristics: saving heuristics, sequential insertion heuristic based on the ideas of Solomon (1987), sequential insertion heuristic based on the ideas of Ho e Haugland (2004) and adaptation of the sequential insertion heuristic of Dullaert et al. (2002). For the real case, it was possible to reduce the total fleet cost, when comparing to the actual solution. At some instances of the three benchmark problems, the algorithms presented similar or better results when compared to the best solutions in the literature.

A localização de instalações está entre as mais importantes decisões logísticas. A questão é tratada, em geral, por técnicas de Pesquisa Operacional, principalmente a programação linear inteira mista, cuja modelagem tem aspectos que podem ser aprimorados. Esta tese apresenta uma proposta metodológica subdividindo o problema em duas fases, visando localizar centros de distribuição de carga (CDs). A Fase 1 define as localizações ótimas dos CDs, iniciando com uma agregação de nós de demanda em clusters através de uma heurística, complementada pela metaheurística simulated annealing (SA). Em seguida, buscam-se, em cada cluster, os melhores locais candidatos. Entre estes candidatos definem-se as localizações ótimas, através de um modelo de programação linear inteira mista ou por SA. Foi conduzido um experimento controlado, com solução ótima conhecida, tendo coincidido em vários casos com a solução obtida através da metodologia proposta. A Fase 2 define a quantidade ótima de CDs, modelando os custos de estoque, armazenagem e vendas perdidas, não considerados na primeira fase. Estes modelos exógenos ao modelo de otimização da primeira fase podem trabalhar sem a restrição de linearidade, trazendo assim, maior realismo a modelagem. Ao final consolida-se o conjunto de custos logísticos (Fases 1 e 2) de forma a se identificar a quantidade de CDs que conduz ao mínimo custo total. A metodologia foi aplicada a um caso real com mais de duzentos pontos de demanda distribuídos sobre os três estados da região sul do país. Os resultados mostraram a aplicabilidade da abordagem proposta. / The facility location is one of the most important logistic decisions. The problem is usually handled through the use of operations research techniques, mainly with the use of mixed integer linear programming (MILP), which modeling process can be improved in some of its aspects. This thesis presents a methodological proposal subdividing the problem in two stages, in order to locate distribution centers (DCs). Stage 1 identifies the optimal DC locations, starting with a heuristics, complemented by the metaheuristic simulated annealing (SA), to cluster the demand nodes. Next, the heuristics searches for best DCs candidates in each cluster. Among these best candidates are defined the optimal locations, with the use of a MILP model or through the use of SA. In order to validate the methodology, it was conducted a controlled experiment, with a known optimal solution, having matched in many cases with the solutions obtained through the proposed approach. Stage 2 defines the optimal DC number, modeling the costs of inventory, storage and lost sales, which were not considered in the first stage. These models, exogenous to the Stage 1 optimization model, could represent the costs behavior without the linear restriction, bringing more realism to the modeling process. Finally, the whole set of logistic costs (Stages 1 and 2) is combined in order to identify the DC quantity with minimal total cost. The methodology was applied to a real world problem encompassing more than two hundred demand points spread over the three states of the southern Brazilian region. The results have shown the applicability of the proposed approach.

Os terminais intermodais operam com modos de transporte com diferentes capacidades, e podem constituir pontos de gargalo no sistema de transporte. O objetivo deste trabalho é avaliar a influência que as incertezas nos processos de chegadas causam no desempenho e no dimensionamento do terminal. Na investigação de hipótese adotou-se o método de simular as condições operacionais de um terminal onde existem dados da operação atual. Para isto, coletaram-se dados referentes aos processos de chegadas de barcaças e vagões a um terminal intermodal fluvial localizado na hidrovia Tietê-Paraná. A operação do terminal foi simulada utilizando o software ARENA, representando o período de 150 dias, correspondente a safra de soja. Concluiu-se que a variação estocástica nos processos de chegadas de barcaças e vagões possuem forte influência no desempenho do terminal, e que uma melhoria na gerência operacional desses processos pode representar ganhos consideráveis para os agentes envolvidos. / The difference in the arrival flow of cargo carried in vehicles of different loading capacities usually transform intermodal terminals into bottlenecks of the transportation system. The aim of this study is to evaluate the influence of the uncertainties in the sizing of an intermodal terminal. Data obtained from the observation of arrival process of barges and trains to a grain intermodal terminal located at Tietê-Paraná inland waterway is used in a case study. The operation of the terminal during the 150-day harvest period of oy beans is simulated using the ARENA software. It is concluded that the stochastic variation in the arrival process of bargers and trains have strong influence on the terminal performance, and that better management of these processes would provide considerable gains to all operation in the partners.

Made available in DSpace on 2014-06-11T19:22:18Z (GMT). No. of bitstreams: 0 Previous issue date: 2010-04-16Bitstream added on 2014-06-13T20:28:18Z : No. of bitstreams: 1 martins_at_me_sjrp.pdf: 1107946 bytes, checksum: 4889aecbca6c259500ae7438b3cb059b (MD5) / Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) / Neste trabalho estudamos o problema de corte de estoque bidimensional originado da realidade de uma fábrica de móveis. Descrevemos o sistema de produção de uma fábrica de móveis característica do Polo Moveleiro de Votuporanga, com ênfase no setor de corte da matéria-prima, e propomos um algoritmo para resolver o problema de corte de estoque considerando a minimização do número de objetos cortados e do número de ciclos da serra. A ideia principal do algoritmo proposto (AFM-P) consiste em adicionar ao problema, de forma dinâmica, restrições que imponham uma frequência mínima para a utilização de um dado padrão de corte. A cada iteração uma solução é gerada e no final do algoritmo existe um conjunto de soluções que são analisadas segundo critérios de dominância. Realizamos um estudo computacional utilizando os dados reais da fábrica visitada para analisar o comportamento do AFM-P. O estudo computacional mostrou que através do algoritmo proposto é possível encontrar soluções próximas e, na maioria das vezes, melhores que a prática da indústria tomada como estudo de caso / In this work we study the two-dimensional cutting stock problem originated from a furniture industry. We describe the production system of a characteristic furniture plant situated at Votuporanga Regional Center and we propose an algorithm to solve the cutting stock problem taking into account the minimization of the number of objects and the number of saw cycles. The main idea of the algorithm (AFM-P) is adding to the problem, in a dynamic way, constraints that impose a minimum frequency to the use of a given cutting pattern. At each iteration a solution is generated and at the end there is a set of solutions that are analyzed according to dominance criteria. The AFM-P algorithm is tested using data from the furniture plant visited. The computational study shows that using the proposed algorithm it is possible to find solutions that are close the ones used in the industry practice and, in most cases, better than theirs

Made available in DSpace on 2014-06-11T19:22:18Z (GMT). No. of bitstreams: 0 Previous issue date: 2013-02-28Bitstream added on 2014-06-13T20:48:30Z : No. of bitstreams: 1 greccho_tx_me_sjrp.pdf: 478270 bytes, checksum: 87e981ec8683b4fe4c15ca85ae4b8b66 (MD5) / Neste trabalho apresentamos métodos de decomposição para problemas de otimização inteira que auxiliam no processo de geração de colunas aplicado ao problema de corte de estoque bidimensional. É feita uma revisão de literatura sobre problemas considerando o corte simultâneo de objetos (ciclos da serra). Visando a aceleração do método de ge- ração de colunas, propomos uma técnica de decomposição para o problema de corte de estoque com minimização de ciclos da serra que incorpora informações duais associadas às restrições de ciclos da serra no subproblema pricing / In this paper we present decomposition methods for integer optimization problems that will help the column generation process applied to the two-dimensional cutting stock problem. It’s made a literature review about problems considering the simultaneous cutting of objects (cycles saw). Seeking an acceleration in the generation column method, the propose a decomposition technique for the cutting stock problem with minimization saw cycles which incorporates dual information associated to saw cycles restrictions in the pricing subproblem

Orientador: João Carlos Cury Saad / Banca: Alba Maria Guadalupe O. Gonzalez / Banca: João Luís Zocoler / Banca: Alexandre Barcellos Dalri / Banca: Júlio César Thoaldo Romeiro / Resumo: A técnica da irrigação visa o aumento da produtividade das culturas, principalmente em regiões onde a escassez de água é fator limitante para o desenvolvimento vegetal, entretanto, causa um grande impacto na disponibilidade hídrica dos mananciais, pois requer a captação de um grande volume de água, devido ao grande consumo requerido pelos cultivos. O manejo adequado da irrigação beneficia além do produtor, com a redução do custo de produção, a todos os usuários da água, devido à economia deste bem e de outras vantagens advindas de seu uso eficiente. Uma maneira racional de se definir planos ótimos de cultivo, bem como escolher uma lâmina de água que seja economicamente viável e produtiva dentre todas as opções existentes, é o emprego de técnicas que ajudem na tomada de decisão. As técnicas de programação linear e nãolinear são poderosas ferramentas que podem ser utilizadas para a alocação ótima desses recursos. Esta pesquisa objetivou propor planos ótimos de cultivos, utilizando a técnica de programação não-linear (PNL), que proporcionassem a maximização do retorno líquido da fazenda Olhos D'água, em Paranapanema, SP, aliando as restrições de disponibilidade de água, terra e condições de produção das culturas, bem como estudar os efeitos de diferentes disponibilidades anuais de água sobre a renda líquida da propriedade. O modelo consistiu de uma função objetivo, sujeita a restrições no uso dos recursos terra e água, assim como restrições na produção das culturas, tendo como objetivo a maximização da soma dos benefícios líquidos decorrentes da produção das culturas no ano agrícola 2013/2014. O valor otimizado do retorno financeiro da fazenda Olhos D'água foi de R$ 746.988,69, para o ano agrícola 2013/2014 e apresentou o seguinte padrão de cultivo em sua solução ótima: ... / Abstract: The technique of irrigation aims at increasing crop yields, especially in regions where water scarcity is a limiting factor to production, however, has an expressive impact on the water availability of water sources, it requires the captation of a large volume of water due consumption required by crops. Proper irrigation management benefits the producer with reducing the cost of production and all water users due to economy this resource and other advantages arising from their efficient use. A rational way to define optimal plans of cultivation, as well as choose a water slide that be economically viable and productive among all the existing options, is the use of techniques that help in decision making, and the techniques of linear programming and nonlinear are powerful tools that can be used for the optimal allocation of these resources. This research aims to propose optima plans of cultivation, using the techniques of nonlinear programming, which provide the maximization of net return of Farm Olhos D'Agua, on Paranapanema - SP, allying the constraints of water availability, land and market, as well how to study the effects of different annual volumes of water available over the net income from the property. The model consists of an objective function, which is subject to restrictions on use of crop area and water resources as well as constraints in crop production and aim to maximization the sum of net benefits stemming from the production of crops in agricultural year 2013/2014. The optimized value of the financial returns of Olhos D'água farm was R$ 746.988,69, for the agricultural year 2013/2014, and presented the following cropping pattern in its optimal solution: 60 ha of cotton, 205 ha of beans, 119 ha of maize, 138 ha of soybeans planted in September and 112 ha of soybeans planted in December to ... / Doutor

Orientador: Maria do Socorro Nogueira Rangel / Banca: Deisemara Ferreira / Banca: Silvio Alexandre de Araujo / Resumo: Neste trabalho apresentamos métodos de decomposição para problemas de otimização inteira que auxiliam no processo de geração de colunas aplicado ao problema de corte de estoque bidimensional. É feita uma revisão de literatura sobre problemas considerando o corte simultâneo de objetos (ciclos da serra). Visando a aceleração do método de ge- ração de colunas, propomos uma técnica de decomposição para o problema de corte de estoque com minimização de ciclos da serra que incorpora informações duais associadas às restrições de ciclos da serra no subproblema pricing / Abstract: In this paper we present decomposition methods for integer optimization problems that will help the column generation process applied to the two-dimensional cutting stock problem. It's made a literature review about problems considering the simultaneous cutting of objects (cycles saw). Seeking an acceleration in the generation column method, the propose a decomposition technique for the cutting stock problem with minimization saw cycles which incorporates dual information associated to saw cycles restrictions in the pricing subproblem / Mestre

Os terminais intermodais operam com modos de transporte com diferentes capacidades, e podem constituir pontos de gargalo no sistema de transporte. O objetivo deste trabalho é avaliar a influência que as incertezas nos processos de chegadas causam no desempenho e no dimensionamento do terminal. Na investigação de hipótese adotou-se o método de simular as condições operacionais de um terminal onde existem dados da operação atual. Para isto, coletaram-se dados referentes aos processos de chegadas de barcaças e vagões a um terminal intermodal fluvial localizado na hidrovia Tietê-Paraná. A operação do terminal foi simulada utilizando o software ARENA, representando o período de 150 dias, correspondente a safra de soja. Concluiu-se que a variação estocástica nos processos de chegadas de barcaças e vagões possuem forte influência no desempenho do terminal, e que uma melhoria na gerência operacional desses processos pode representar ganhos consideráveis para os agentes envolvidos. / The difference in the arrival flow of cargo carried in vehicles of different loading capacities usually transform intermodal terminals into bottlenecks of the transportation system. The aim of this study is to evaluate the influence of the uncertainties in the sizing of an intermodal terminal. Data obtained from the observation of arrival process of barges and trains to a grain intermodal terminal located at Tietê-Paraná inland waterway is used in a case study. The operation of the terminal during the 150-day harvest period of oy beans is simulated using the ARENA software. It is concluded that the stochastic variation in the arrival process of bargers and trains have strong influence on the terminal performance, and that better management of these processes would provide considerable gains to all operation in the partners.

Orientadora: Adriana Cristina Cherri Nicola / Coorientador: Luiz Henrique Cherri / Banca: Pedro Augusto Munari Junior / Banca: Edilaine Martins Soler / Resumo: Este trabalho propõe diferentes estratégias de solução para a técnica de geração de colunas utilizada para resolver o problema de corte de estoque com sobras aproveitáveis (PCESA). Este problema consiste em atender a demanda de produção de itens solicitados por clientes a partir do corte de objetos comprados de fornecedores ou de sobras resultantes de cortes anteriores. O objetivo é de cunho econômico e visa, por exemplo, a minimização da perda gerada com o corte dos objetos. Neste problema, durante o processo de corte, sobras podem ser geradas para o estoque e não são contabilizadas como perdas. Uma técnica bastante utilizada para resolver este problema, assim como o clássico problema de corte de estoque, é o método de geração de colunas, que é um método iterativo no qual a cada iteração novas colunas (padrões de corte) são geradas a fim de encontrar a melhor solução para a relaxação linear do problema. A geração de colunas utiliza o problema da mochila para gerar as colunas que serão inseridas a cada iteração no problema de corte. Desta forma, o objetivo deste trabalho é estudar o impacto da inserção de K soluções, obtidas pelo problema da mochila em instâncias do PCESA unidimensional, a cada iteração do método de geração de colunas. Para as estratégias propostas, testes computacionais foram realizados utilizando classes de instâncias que variaram o valor de K. Os resultados mostraram que as estratégias reduzem o número de iterações e podem reduzir o tempo computacional em ... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: This work proposes different solution strategies to the column generation method used to solve the cutting stock problem with usable leftovers (CSPUL). This problem consists in meeting client demands cutting objects bought from the market or leftovers resulted from previous cuts. The objective is economic and aims, for example, to minimize the total waste generated by cutting objects. In this problem, during the cutting process, leftovers can be generated for the stock and are not counted as wastes. A very useful technique to solve this problem, as well as the classic cutting stock problems, is the column generation method that is an iterative method. In each iteration of the method, new columns (cutting patterns) are generated in order to find the best solution for the linear relaxation of the problem. The column generation uses the knapsack problem to generate the columns that will be inserted at each iteration in the cutting problem. Thus, the objective of this work is to study the impact of the insertion of K solutions obtained in the knapsack problem in instances of the one-dimensional CSPUL in each iteration of the column generation method. For the proposed strategies, computational tests were performed using classes of instances that varied the k value. The results showed that the strategies reduce the number of iterations and can reduce computational time in relation to the standard column generation, when only one column is inserted at each iteration / Mestre

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Engenharia Elétrica. / Made available in DSpace on 2012-10-22T21:56:01Z (GMT). No. of bitstreams: 1 238306.pdf: 412990 bytes, checksum: 45884af398ed6a91e04edd7726745cd9 (MD5) / O problema clássico de caminhos mínimos pode ser resolvido com algoritmos conhecidos de tempo de execução polinomial. Mas quando restrições de tempo ou recursos são impostas ao problema, este se torna NP-Difícil. Este problema é conhecido como problema de caminhos mínimos sob restrições e são estudados neste trabalho a sua modelagem, algoritmos e aplicações. O algoritmo de programação dinâmica e o de aproximação-e são os métodos de maior destaque, que nesta dissertação foram implementados e exemplificados. No presente trabalho são apresentados aplicação em diversos contextos: em agentes móveis, em tráfego urbano e em redes de computadores. No contexto de agentes móveis este tipo de algoritmo pode resolver problemas como o escalonamento de tarefas com restrição de tempo de execução, ou seja, com um deadline. Em redes de tráfego veicular pode auxiliar na resolução de um problema mais complexo, ou simplesmente obter o caminho mais rápido com restrições orçamentárias. E por fim, em rede de computadores pode criar rotas que satisfazem métricas de Qualidade de Serviço (QoS).