Aplicação da inteligência artificial à resolução do problema da distribuição

Mestrado em Métodos Matemáticos Aplicados Economia e Gestão de EmpresasA resolução do problema básico da distribuição consiste em definir um conjunto de rotas e em minimizar o custo total de as percorrer. Cada rota é constituída pelo depósito ou armazém e um conjunto de clientes, cada um dos quais tem uma procura e uma localização geográfica definidas, e é percorrida por um veículo, com uma determinada capacidade, o qual parte do depósito visita uma e uma só vez cada cliente e regressa novamente ao depósito. Cada cliente pertence a uma e uma só rota e o depósito é o mesmo para todos os veículos. Este problema surge na prática inúmeras vezes, como por exemplo, quando uma empresa armazenista deseja distribuir os produtos pelos seus clientes, na recolha das moedas das cabinas telefónicas, na recolha do correio dos marcos, numa empresa produtora que pretende colocar os seus produtos em diferentes armazéns geograficamente afastados. Nesta dissertação abordam-se e comparam-se duas formas de resolução do problema básico da distribuição: a exacta, que recorre à técnica da ramificação em árvore e a aproximada que usa o método heurístico de Jameson e Mole. A resolução exacta pelo método da ramificação em árvore implica a determinação de um minorante e de um majorante para cada subproblema gerado pela ramificação e, ainda, a resolução exacta do problema do caixeiro viajante (PCV) a fim de definir o percurso óptimo de cada veículo. Aquele minorante é determinado através da introdução de alguns melhoramentos num minorante para o problema do caixeiroviajante múltiplo (M-PCV). O seu valor é o resultado da soma de três parcelas: o custo de uma árvore geradora mínima de grau K no depósito, o custo de Y arestas adjacentes ao depósito e o custo de MY arestas não adjacentes ao depósito, sendo M o número total de veículos. Mas, para que o valor de um minorante seja o mais alto possível, o problema formado pelo conjunto destas três parcelas é maximizado (dual Lagrangeano) pelo método de optimização subgradiente. O majorante é determinado pelo método de Jameson e Mole ou por outro método concebido pelo autor deste documento que se designa por exploração sistemática. A resolução exacta do PCV é feita através do algoritmo de Little, cuja eficiência é aumentada pela introdução de um majorante inicial que se obtém pela 2-optimização da rota. O trabalho de experimentação computacional foi realizado através do recurso a uma linguagem de programação de muito alto nível, Prolog, dialecto CProlog. Os resultados da execução de diversos exemplos mostraram que a versão da linguagem Prolog (interpretador), que se encontrava disponível no ISEG e LNEC, é pouco eficiente computacionalmente quando comparada com as linguagens imperativas em certos tipos de problemas, mas espera- -se que esta desvantagem possa ser ultrapassada, através da utilização de computadores funcionando em paralelo, de uma versão de Prolog compilada e de estruturas de representação do conhecimento mais eficientes, nomeadamente, árvores 2-3. Em contrapartida, as suas vantagens são já uma realidade, como seja, a eficiência do desenvolvimento de protótipos e a facilidade de compreensão, manutenção, modificação e expansão.The resolution of the basic distribution problem consists of defining a set of routes such that the total cost of travei them beminimum. Each route is composed of the depot or store and a set of clients, each of which has defined a demand and a geographic localization, and it is covered by a vehicle, with a certain capacity, which departs from the depot visits once and only once each client and returns to the depot. Each client belongs to one and only one route and the depot is the same for every vehicles. This problem appears many times in practice, by example, when a wholesaler enterprise wishes distribute the products by is clients, in gathering of coins of the telephone boxes, in the collection of the mail from the boxes, in an industrial company that pretends to put its products in differents warehouses geographically distant. In this dissertation are studied and compared two forms of resolution of the basic distribution problem: the exact, which uses the technique of branch and bound and the approximate resolution which uses the heuristic method of Jameson and Mole The exact resolution by the tree search algorithm implies the determination of a lower bound and an upper bound for each subproblem created by the ramification and, yet, an exact resolution of the travelling salesman problem (TSP) in order to define an optimal trip for each vehicle. That lower bound is determined through the introduction of some improvements in a lower bound for the multiple travelling salesman problem (M-TSP). Its value is the result of adding three parts: the cost of a shortest spanning K-degree tree with centre in depot, the cost of Y edges adjacents to depot and the cost of M-Y edges not adjacents to it, beeing M the total number of vehicles. But in order the value of a lower bound becomes so high as possible, the problem composed by the set of this three parts is maximized (Lagrangean dual) by the subgradient optimization method. The upper bound is determined by Jameson and Mole's method or for other method conceived by the author of this document which is designated for svstematic exploration. An exact resolution of TSP is made through LittWs algorithm, which efficiency is improved by the introdution of an mitial upper bound which is get by 2-optimization of the route. The experimental of computation was realized through the use of the programming language of very high levei, Prolog, on dialect CProlog, The results of execution of various examples shew ^at this version of Prolog language (interpreter), wich was available at ISEG and LNEC, is computationally inefficient when compared with the imperative languages in certain type of problems, but is expected that this disadvantage can be overtaken, through the utilization of parallel computers, of one version of Prolog compiled and more efficient of knowledge representation structures, namely, 2-3 trees. In counterpart, its advantages are a reality, like prototype development efficiency, and the facility of understanding, debugging, maintenance, modification and expansion.