A definição do mix de produção proporciona a alocação dos recursos produtivos no processo de manufatura, visando a otimização da sua utilização e do desempenho do sistema produtivo o que, por sua vez, em um nível gerencial, norteia a performance da organização. Entretanto, apesar de sua importância, a definição do mix de produção é um problema do tipo NP-Completo, ou seja, de difícil solução. Assim, com o auxílio da Teoria das Restrições - TOC, muitas heurísticas construtivas têm sido apresentadas para fazer frente a esse problema. Nesse sentido, o objetivo deste trabalho é propor uma nova heurística, denominada TOC-SN, baseado na TOC e no problema da mochila, que proporcione melhores soluções quando comparada com as principais heurísticas apresentadas na literatura, a TOC-h de Fredendall e Lea e a TOC-AK de Aryanezhad e Komijan. Para realização dessa comparação foram realizadas experimentações computacionais visando identificar o mix de produção que possibilitasse o maior ganho possível, em situações nas quais não há recursos disponíveis para produção de todos os produtos. Como resultado, observou-se que a TOC-SN obteve uma solução mais satisfatória quando comparada à aplicação das outras heurísticas e à solução ótima o que, em conclusão, evidencia a sua importância na definição de mix de produção. / The product-mix decision make possible to distribute the resources in the manufacture process, with the objective of optimizing the use of the resources and the performance of the productive system. This problem is well-known for being NP-Complete and therefore, most contributions to the topic focus on developing heuristics able to obtain good solutions for the problem in a short CPU time. Then, the objective in this thesis is to propose a new constructive heuristic or the TOC-SN based on the Theory of Constraints - TOC and on the Knapsack Problem that indicates better solutions than the TOC-h heuristic proposed by Fredendall and Lea and the TOC-AK heuristic proposed by Aryanezhad and Komijan. Experimentation computational was accomplished with the objective of testing the heuristics in the definition of product mix that made possible the best throughput in situations with scarcity of productive resources. The computational results indicate that the proposed heuristic obtains better results than the existing heuristic.

O presente trabalho trata da solução para o problema da elaboração de programações de transporte do sistema de distribuição de materiais da Força Aérea Brasileira (FAB). Essas programações de transporte consistem em definir os roteiros de entrega e coleta de materiais a serem realizadas simultaneamente em cada local de entrega/coleta a partir de um centro de distribuição, considerando-se a frota de veículos homogênea. Isto é característico de um Problema de Roteirização de Veículos com Coletas e Entregas Simultâneas (PRVCES). A gestão do sistema de distribuição física da FAB considera a complexidade desse sistema e os dados relativos às demandas de transporte de carga em cada um desses locais para elaborar as programações de transporte. Essas programações são elaboradas tendo em vista os limites de capacidade dos veículos, as características físicas das cargas e as prioridades de embarque. O gestor desse sistema possui boa visibilidade das demandas de transporte, porém, devido à grande quantidade de informações disponíveis e à elevada complexidade desse sistema, é impossível elaborarem-se manualmente programações de transporte que resultem em viagens de distribuição eficientes. O PRVCES foi resolvido por meio da meta-heurística Busca Dispersa (do inglês Scatter Search) integrada com a meta-heurística Descida em Vizinhança Variável (do inglês Variable Neighborhood Descent) utilizada como método de melhoria das soluções. Os resultados superaram ou se igualaram a alguns dos obtidos por outros autores para os mesmos problemas de teste com as mesmas restrições, o que demonstra que a Busca Dispersa implementada é competitiva para solucionar o PRVCES. Quanto à aplicação na FAB, os resultados mostraram que a utilização do método de solução desenvolvido resultará em programações de transporte elaboradas em curto tempo de processamento e que estas incidirão positivamente sobre a eficiência do sistema de distribuição de materiais da FAB. / This work deals with the solution to the problem of drawing up transport schedules in the material distribution system of the Brazilian Air Force (BAF). These transport schedules consist in defining the routes for material pickup and delivery to be accomplished simultaneously in each delivery/pickup location from a distribution center, considering a homogeneous fleet of vehicles. This is characteristic of a Vehicle Routing Problem with Simultaneous Delivery and Pick-up (VRPSDP). The management of the physical distribution of BAF considers the complexity of this system and the data regarding the cargo transport demands in each one of those locations to draw up transport schedules. These schedules are drawn up regarding the capacity limits of the vehicles, the physical characteristics of the cargoes and the shipping priorities. A good visibility of transport demands in each location is available to the manager of this system, but due to the great quantity of data to deal with and the high complexity of the physical distribution system of BAF, it is impossible to draw up transport schedules that result in efficient distribution trips. The VRPSDP was solved by means of the Scatter Search meta-heuristic integrated with the Variable Neighborhood Descent meta-heuristic as the solution improvement method. The results exceeded or equaled some of those obtained by other authors using the same test problems with the same restrictions, what indicates that the implemented Scatter Search is competitive to solve the VRPSDP. As for the application in the BAF, the results showed that using the solution method developed will result in schedules drawn up in short processing time and focused on the efficiency of the material distribution system of the BAF.

Esta dissertação trata do problema do agrupamento de cargas fracionadas na distribuição de cimento ensacado partindo de um depósito central. O problema consiste em definir quais entregas de cimento serão carregadas juntas em um determinado veículo, de modo a aproveitar ao máximo sua capacidade e ao mesmo tempo reduzir o custo com o frete pago aos transportadores que farão sua distribuição. Em especial, o método de resolução proposto pode ser dividido em três fases. Na primeira fase, as entregas pertencentes a um mesmo cliente são agrupadas prioritariamente. Na segunda fase, são agrupadas as entregas de clientes dentro de uma mesma cidade. Neste caso, uma simplificação necessária é considerar que todas as entregas de uma mesma cidade estão localizadas em um único ponto. Com isso, a distância entre os clientes se torna irrelevante e é proposto um método baseado em um algoritmo genético para resolução de problemas de bin-packing (BPP). Para a terceira fase, é considerado o agrupamento para pontos de entrega pertencentes a cidades diferentes, onde as distâncias rodoviárias são consideradas. Nesta etapa, é proposta uma variação do método anterior, incorporando ao modelo algumas heurísticas para resolução de problemas de roteirização de veículos, como o algoritmo de Clarke & Wright e o algoritmo do Vizinho Mais Próximo. / This thesis deals with the problem of merging less-than-truckload deliveries in bagged cement distribution from a central depot. The problem consists in defining which cement deliveries shall be loaded in each given vehicle, in order to maximize the vehicle full capacity as well as reduce carriers freights. Particularly, the solution method can be divided hierarchically in three stages. In the first stage, the deliveries from the same client are merged with priority. In the second stage, the deliveries from the same city are merged. In this case, a necessary assumption is to consider the deliveries from the same city as located in a single destination point. Consequently, the distances among deliveries can be assumed as irrelevant and a heuristic method is proposed, which relies on a genetic algorithm for the bin-packing problem (BPP). In the third stage, merging of different delivery points that are apart from each other is considered. For this step, a variation of the previous method is proposed, incorporating some heuristics to solve the vehicle routing problem, like the Clarke & Wrights savings algorithm and the Nearest Neighbor algorithm.

Este trabalho propõe modelos matemáticos e heurísticas para a definição da malha de voos de uma empresa aérea, como parte de seu planejamento operacional, visando à maior eficiência de operação frente às restrições relacionadas aos aeroportos, a equipamentos e à demanda. Em especial, é proposta uma função objetivo, baseada no momento de transporte, para a modelagem integrada dos problemas de Programação de Voos e Alocação de Frotas que inclui elementos específicos para a consideração de slots de pouso e decolagem. A abordagem tem aplicação especialmente relevante no âmbito de empresas aéreas de pequeno e médio porte atuando em mercados regionais, cuja malha é composta principalmente por voos de curta duração, em geral operando com aeronaves de pequeno e médio porte. Nestas condições, tais empresas trabalham com margens de lucro limitadas e, portanto, podem-se beneficiar sensivelmente da definição de uma malha mais eficiente e eficaz. Os modelos desenvolvidos, baseados em programação linear inteira e na meta-heurística Ant Colony Optimization, foram aplicados com sucesso ao caso de uma empresa aérea regional, com atuação no mercado brasileiro, possibilitando a definição de malhas alternativas, bem como fornecendo subsídos para a avaliação dos impactos na malha oriundos da utilização de novas aeronaves. / This research proposes mathematical models and heuristics to define the flight mesh of an airline, as part of its operational planning, considering restrictions related to airports, equipment and demand. In particular, an objective function is formulated, based on transport momentum, proposed for the integrated modeling of Flight Scheduling and Fleet Assignment problems that includes specific elements to consider landing and takeoff slots at airports. The approach is especially relevant for small and medium airlines operating in regional markets, with short-haul flights, in general operating with small or medium size aircraft. Accordingly, these companies work with limited profit margins, and, therefore, they can take great benefit from a more efficient and effective flight mesh. The models proposed, based on integer linear programming and on the Ant Colony Optimization meta-heuristic, were successfully applied to the case of a regional airline with operations in Brazil, enabling the definition of mesh alternatives as well as providing information for the assessment of impacts in its flight network arising from the utilization of new aircraft.

Nesta tese é tratado o caso particular, único e ainda não estudado, do problema de formação de carga e distribuição de veículos novos no Brasil, com o objetivo de obter as melhores combinações de veículos a serem carregados nos caminhões cegonha, para serem entregues às suas respectivas concessionárias, em um horizonte de planejamento preestabelecido, tal que essas formações resultem no menor valor de frete total pago pela transportadora, respeitando todas as restrições existentes. O problema, reconhecidamente um NP-Difícil, é prático e comum à várias empresas atuando no setor. Para resolver o problema de formação de carga e distribuição de veículos zero quilômetro no Brasil, foi desenvolvido um algoritmo em programação linear inteira mista, capaz de resolver pequenas instâncias do problema. A execução de múltiplos testes com instâncias de portes maiores, indicou que não é possível obter soluções ótimas para o problema abordado considerando a aplicação do modelo matemático, seja utilizando computadores pessoais ou infraestruturas de elevada capacidade computacional. Entretanto, os resultados ótimos encontrados para as instâncias de pequeno porte foram utilizados como parâmetro de avaliação da proposta de solução heurística apresentada. A heurística de busca local multi-início desenvolvida e apresentada nesta tese foi capaz de encontrar a solução ótima para todas as quatro instâncias reais e de pequeno porte, reduzindo o número de veículos entregues atrasados tanto na comparação com os resultados obtidos pelo modelo matemático, quanto pela comparação com a alocação manual feita pelo funcionário da empresa de transportes que cedeu os dados para esta pesquisa. Por fim, a heurística desenvolvida foi utilizada para solucionar um problema de tamanho condizente com aquele encontrado no dia-a-dia da operação real de uma transportadora de veículos, obtendo soluções de valor de frete menores que aqueles obtidos pela alocação manual e reduzindo drasticamente o número de veículos entregues atrasados, com tempo de execução aceitável para sua aplicação prática. / This thesis proposes a new solution to the problem of load formation and distribution of new vehicles in Brazil. The problem consists in selecting among all vehicles parked at a transportation company staging area the best combination of units to be loaded on available auto-carrier trucks and delivered to its respective dealers, over a multipleday planning horizon. The group of vehicles selected to each auto-carrier has to be physically possible to load. Thus, several group formation constraints have to be respected. Transportation company does not own the fleet. It pays a per trip freight to auto-carrier owners, responsible for transporting vehicles to dealers. There exists a minimum freight cost to be paid to auto-carrier owners, which is calculated to each trip, according to its load formation. Sometimes, the minimum freight is greater than the sum of each loaded vehicle freight individually taken. The object is to minimize the transportation company total freight cost. Described problem belongs to the NP-hard class. An algorithm capable of solving small instances of the problem was developed using mixed integer linear programming (MILP). The execution of multiple tests, with instances of larger sizes, indicated that it is not possible to obtain optimal solutions considering the mathematical model, either using personal computers or high capacity clusters. However, the optimal results obtained for four small and real instances were used as evaluation parameter for the proposed heuristic solution. The multi-start local search heuristic developed was able to find the optimal solution for all four small instances solved using the MILP. Besides that, it was able to reduce the total number of late deliveries in comparison with the results obtained by the mathematical model and by the manual allocation done at the transportation company. Finally, the multi-start heuristic was used to solve larger size problems, compatible with those encountered in real life, obtaining smaller freight value than those obtained by the manual allocation made at the transportation company, also drastically reducing the number of late deliveries with acceptable processing time for practical applications.

Este trabalho propõe uma heurística construtiva determinística e uma heurística construtiva probabilística para resolver o problema de programação de projetos com custo de disponibilidade de recursos e custo de penalidade por atraso no término do projeto (RACPT - Resource Availability Cost Problem with Tardiness). Os algoritmos combinam a flexibilidade da atividade com a flexibilidade do recurso para selecionar a próxima atividade a ser programada. A data de início de uma atividade é a data mais cedo em que sua execução não gera o maior pico de utilização dos recursos ou a data mais cedo na qual o custo total do projeto for menor. A melhor versão das heurísticas foi obtida após o teste de várias regras de prioridade, conforme a revisão bibliográfica realizada. As heurísticas propostas foram testadas em 360 instâncias de testes e seus resultados foram comparados aos obtidos pela formulação matemática baseada em strip packing e restrições disjuntivas implementada no programa CPLEX. A heurística construtiva determinística gera uma solução viável rapidamente, porém de baixa qualidade. Já a heurística construtiva probabilística gera soluções ótimas ou próximas da ótima para problemas pequenos ou para problemas fáceis e gera soluções muito melhores do que o CPLEX na metade do tempo computacional para os problemas médios e grandes ou para problemas difíceis. Dado os bons resultados obtidos e à implementação no programa VBA for Microsoft Excel, a heurística construtiva probabilística proposta é um método bom e prático para resolução do RACPT. / This work proposes a deterministic constructive heuristic and a probabilistic constructive heuristic for solving the resource availability cost problem with tardiness (RACPT). The algorithms combine the flexibility of an activity with the flexibility of a resource to select the next activity to be scheduled. The start time of the activity is the earliest date in which the activity\'s execution does not create resources usage peak or the earliest date with the lowest total project cost. We tested several priority rules according to the literature review and determined the best version of the heuristics. Afterwards, we tested the proposed heuristics in 360 instances and compared its results with the solutions obtained by the optimization software CPLEX. The RACPT implementation on CPLEX utilized a mathematical formulation based on strip packing concepts and disjunctive constraints. The computational results showed that the deterministic constructive heuristic generates feasible solutions of poor quality in low computational time. The probabilistic constructive heuristic achieved better results. For small instances or easy problems, it found optimal or near-optimal solutions. For medium and large instances or hard problems, it obtained better results than CPLEX in half-computational time. We believe that the probabilistic constructive heuristic is a good and practical method for solving the RACPT. The proposed algorithm produced good results in reasonable computational time and was implemented on the popular software VBA for Microsoft Excel.

Os problemas de corte e empacotamento são muito comuns nas indústrias e na logística. Dado um conjunto de N itens com diferentes pesos e um conjunto de M contentores com capacidade C, o problema de empacotamento unidimensional consiste em determinar o menor número de contentores a serem utilizados para alocar todos os itens respeitando a restrição de capacidade dos contentores. Nesse estudo pretende-se resolver o problema com instâncias benchmark da literatura, por meio de sessenta heurísticas diferentes, que são comparadas a quatro limitantes inferiores propostos na literatura com o intuito de avaliar a qualidade da solução heurística. Quatro limitantes inferiores e dez heurísticas construtivas diferentes foram programados em C++ num mesmo ambiente computacional, permitindo sua comparação tanto em termos de qualidade das soluções, quanto em termos dos tempos de processamento. Uma heurística simples de troca de itens entre contentores chamada Diferença-de-Quadrados foi proposta para melhorar as soluções iniciais do problema. A metaheurística simulated annealing foi acionada para melhorar a solução inicial quando o limitante inferior não foi atingido. Os parâmetros dos simulated annealing foram determinados com os dados das instâncias de forma diferente da utilizada na literatura. As combinações entre as dez soluções iniciais, a heurística Diferença-de-Quadrados e o simulated annealing geraram um conjunto de sessenta heurísticas diferentes. Os resultados mostraram que o algoritmo proposto é eficiente para resolver o problema com tempos de processamento adequados a tomada de decisão. / Cutting and packing problems are very common in industries and logistics. Given a set of N items with different weights and a set of M bins with full capacity C, the one-dimensional bin packing problem consists of determining the smallest number of bins capable to allocate all items respecting the capacity constraint of the bins. that impose that the sum of the weights of the items allocated to the bin is less than or equal to their capacity. In this study we intend to solve the problem with benchmark instances of the literature, by means of sixty different heuristics, which are compared to four lower bounds proposed in the literature in order to evaluate the quality of the heuristic solution. Four lower bounds and ten different constructive heuristics were programmed in C++ in the same computational environment, allowing their comparison both in terms of the quality of the solutions and in terms of processing times. A simple heuristic of item exchange between bins called Difference-of-Squares was proposed to improve the initial solutions of the problem. The simulated annealing metaheuristic was triggered to improve the initial solution when the lower bounds was not reached. The parameters of the simulated annealing were determined with the data of the instances differently from that used in the literature. The combinations of the ten initial solutions, the Difference-of-Squares heuristic and the simulated annealing generated a set of sixty different heuristics. The results showed that the proposed algorithm is efficient to solve the problem with adequate processing times for decision making.

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.

Este trabalho destina-se a realizar um estudo dos efeitos da heurística da ancoragem em estimativas numéricas, e esta fundamentado em pressupostos teóricos apresentados por Amos Tversky e Daniel Kahneman em um estudo seminal de 1974. Sendo assim, este trabalho tem por objetivo examinar quais os efeitos da heurística da ancoragem nas estimativas numéricas sob a perspectiva da avaliação de bens de consumo. Os objetivos específicos foram testar o método proposto por Jacowitz e Kahneman (1995) para a mensuração dos efeitos da ancoragem em estimativas de quantidades incertas e comparar os resultados deste estudo, com os resultados dos trabalhos realizados anteriormente nesta área em outros países. O método utilizado segue as etapas propostas por Jacowitz e Kahneman (1995). Os resultados indicaram que, embora, novos experimentos sejam necessários para um avanço no entendimento de como a ancoragem pode influenciar o processo decisório de consumo, a confirmação da manifestação dos efeitos da ancoragem na estimação de quantidades incertas no experimento 1, e dos preços de diferentes produtos e serviços no experimento 2, numa avaliação do grupo total de participantes da pesquisa, foi a principal contribuição deste trabalho, além de seus resultados corroborarem com os resultados encontrados em estudos similares realizados em outros países, revelando que, no contexto brasileiro, também se observam os efeitos da ancoragem. Além disso, os resultados estendem a pesquisa dos efeitos da ancoragem na estimação do preço de produtos e serviços, e contribui para um melhor entendimento do comportamento do consumidor. Especificamente, o experimento 2 fornece novas percepções relativas aos estudos da ancoragem e indica como um número arbitrário apresentado a um indivíduo pode alterar o seu julgamento, quanto ao preço de um produto ou serviço. Deste modo, esses resultados sugerem que, em vez de dependerem de um enfoque mais passivo na estimação do valor de um produto para os compradores em potencial, e fixarem um preço de acordo com os métodos tradicionais de precificação, os varejistas podem adotar um papel mais ativo na determinação dos preços de determinados produtos, baseados na análise de fatores subjetivos que afetam os julgamentos de preços dos consumidores. / This research paper aims to study the effects of anchoring heuristic in numerical estimates, based on the theoretical presuppositions presented in the seminal work of Amos Tversky and Daniel Kahneman in 1974. The purpose of this work is hence to examine what effects of anchoring heuristic has in numerical estimates for an assessment of consumer goods. The specific objectives were to test the method suggested by Jacowitz and Kahneman (1995) to measure the anchoring effects in estimates of uncertain quantities and compare the results of this study with those of surveys previously conducted in this field in other countries. The method used follows the steps suggested by Jacowitz and Kahneman (1995). The results indicated that, although new experiments are necessary to further understand how the anchoring is likely to influence the consumer decision process, the confirmed appearance of the anchoring effects on the estimate of uncertain quantities in experiment 1, and the prices of different products and services in experiment 2, in an overall group assessment of those who participated in the research, was the main contribution to this work, besides the fact that its results corroborated the results found in similar studies conducted in other countries, thereby revealing that the anchoring effects are also observed in the Brazilian context. Moreover, the results broaden the research on the anchoring effects when estimating product and service prices, and contribute to a better grasp of consumer behaviour. Experiment 2, more specifically, supplies new perceptions as to surveys on anchoring and reveals how an arbitrary number presented to an individual can change their judgement as to the price of a product or service. Hence, the results suggest that instead of having to concentrate more passively on a value estimate of a product for potential buyers and fixing a price according to traditional pricing methods, retailers may adopt a more active role when fixing the price of specific products, based on the analysis of subjective factors that affect the consumer’s judgement on prices.

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.