Quadratic assignment problem

Dissertação de mestrado integrado em Engenharia e Gestão IndustrialO Problema de Afetação Quadrática, Quadratic Assignment Problem (QAP) tem recebido a atenção da comunidade académica devido a sua importância e complexidade. Este é um dos problemas mais difíceis de otimização combinatória. É fácil de descrever, não é tão fácil de formular e é muito difícil de resolver. O QAP foi introduzido por Koopmans e Beckman em 1957, num contexto económico. A preocupação destes autores era afetar estabelecimentos industriais em locais predeterminados, de tal maneira que o custo de transporte fosse minimizado. Na sua aplicação, o custo é o produto dos termos da matriz fluxo e da matriz distância. Desde o surgimento do QAP uma miríade de aplicações tem emergido. Algumas formulações do QAP apresentadas na literatura foram usadas para resolver o problema com base na atividade de picking. A atividade de picking normalmente representa cerca 50% dos custos de trabalho direto num armazém. Esta atividade despende 50% do seu tempo total em deslocações. Na operação de um armazém de picking, a tomada de decisão quanto à localização dos produtos pode condicionar os custos de deslocação entre as posições dos produtos. Daí a pertinência de modelar o QAP na operação de um armazém de picking. Para tal, inicialmente gerou-se instâncias com dados aleatórios numa aplicação programada em linguagem VBA (Visual Basic Application). De seguida, modelou-se em linguagem AMPL (A Mathematical Programming Language), algumas formulações apresentadas na literatura, designadas por: linearização de Lawler, linearização de Frieze e Yadegar e a linearização de Adam e Johnson. Para serem submetidas no servidor NEOS server (Network-Enabled Optimization System), com as instâncias geradas. As instâncias também foram submetidas no LPSolve e na aplicação da heurística de pesquisa local. Gerou-se uma heurística de pesquisa local em linguagem VBA tendo como suporte o Microsoft Excel. O servidor NEOS server apresentou resultados para instâncias de dimensão até =31. O LPSolve não consegue resolver instâncias de grandes dimensões em tempo computacional aceitável devido ao grande número de variáveis e restrições, uma vez que o LPSolve só resolve problemas com formulação linear inteira mista. A heurística de pesquisa local programada em linguagem VBA obteve resultados em todas instâncias geradas para o propósito deste trabalho.The Quadratic Assignment Problem (QAP) has received the attention of the academic community, due to its importance and complexity. It is one of the most difficult problems of combinatorial optimization. It is easy to describe, not so easy to formulate and very difficult to solve. The QAP was introduced by Koopmans and Beckman in 1957, in an economic context. The concern of these authors was assigning industrial establishments in predetermined locations, to minimize the transportation cost. In this problem, the cost is the result of the product of flow matrix by distance matrix. Since the emergence of the QAP, a myriad of applications has emerged. Some formulations presented in the literature were used to solve the QAP based on the picking activity. The picking activity usually consumes about 50% of direct labor costs in a warehouse. Moreover, this activity spends 50% of its total travel time. In the operation of a picking warehouse, the decision making about products location may influence the travel costs between the possible positions. Hence, the relevance to modelling the QAP in the operation of a picking warehouse. To this end, instances were generated with random data in Microsoft Excel, which was programmed using Visual Basic Application (VBA) language. Then, some formulations presented in the literature were modeled using A Mathematical Programming Language (AMPL). The used formulations are the linearization of Lawer, Frieze and Yadegar, and Adam and Johnson. The linearizations were submitted to a Network-Enabled Optimization System (NEOS server) with the generated instances. Instances were also submitted in LPSolve and an application of the local search heuristc . For the latter, a local search heuristic was developed using VBA language. The NEOS server presented results for dimension instances to n = 31. LPSolve only solves problems with mixed integer linear formulation. So it cannot solve large instances in acceptable computational time due to the large number of variables and constraints. The heuristic of local search developed in VBA language obtained results for all instances generated for the purpose of this work