Loading...
Publication
O problema do mercador viajante
| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 1.16 MB | Adobe PDF |
Authors
Advisor(s)
Abstract(s)
O propósito deste trabalho é de dar a conhecer o Problema do Mercador Viajante (Travelling
Purchaser Problem – TPP), apresentado-o e resolvendo-o. O TPP tem uma lista de mercados e uma lista
de produtos. As distâncias entre mercados são dadas, assim como os preços de cada produto em cada
mercado. Pretende-se encontrar um trajeto onde seja possível adquirir todos os produtos, sendo esse
trajeto um conjunto ordenado de mercados. O objetivo é encontrar o trajeto mais curto e ao mesmo
tempo mais barato, por outras palavras, onde os produtos se adquirem aos seus menores preços.
Existem duas grandes dificuldades. A primeira é o facto de o TPP se tratar de um problema
pertencente a NP-Hard. A segunda dificuldade reside no facto de se pretender minimizar dois objetivos:
a distância e o preço. Esses objetivos entram em conflito um com o outro. Em vez de se procurar uma
solução ótima, deve procurar-se uma fronteira de eficiência ótima. Esse tipo de problemas é designado
por bi-objetivo, pois ao melhorar-se um objetivo, quase sempre se piora o outro. Sendo assim, mantémse
um conjunto de soluções ótimas, onde existem algumas com boas distâncias e outras com bons
preços, e apresenta-se esse conjunto como uma fronteira não dominada de soluções.
É usado um algoritmo branch and bound para encontrar as fronteiras de soluções ótimas.
Aplicam-se alguns cortes básicos no espaço de resultados durante a execução do algoritmo exato para
evitar percorrer soluções desnecessárias.
É ainda criada uma base de dados de soluções obtidas a partir do algoritmo exato truncado e de
um algoritmo de escalada do monte.
The purpose of this work is to present and solve the Travelling Purchaser Problem. The TPP has a list of markets and a list of products. The distances between markets are given, and the prices of each product in each market as well. The aim is to find a path where it is possible to buy all the products, and that path being a set of ordered markets. The goal is to find the shortest path and, at the same time, the cheapest one, where the products can be bought at their minimum price among all the markets. There are two major issues. The first one is the fact that the TPP is an NP-Hard problem. The second issue lies in the fact that both objectives should be minimized: the distance and the price. These objectives are in conflict with each other. Instead of searching for an optimal solution, we must search for an optimal efficient front. This kind of problems are referred as bi-objective, because improving one objective, almost always lowers the other. So, we keep a set of optimal solutions, where there are some with good distances and others with good prices, and we present this set as a non dominated front. We use a branch and bound algorithm in order to find the non dominated fronts of optimal solutions. We apply some basic cuts in the search space during the exact algorithm, in order to avoid visiting unnecessary solutions. We create a database of solutions obtained by the truncated exact algorithm and a Hill Climbing algorithm.
The purpose of this work is to present and solve the Travelling Purchaser Problem. The TPP has a list of markets and a list of products. The distances between markets are given, and the prices of each product in each market as well. The aim is to find a path where it is possible to buy all the products, and that path being a set of ordered markets. The goal is to find the shortest path and, at the same time, the cheapest one, where the products can be bought at their minimum price among all the markets. There are two major issues. The first one is the fact that the TPP is an NP-Hard problem. The second issue lies in the fact that both objectives should be minimized: the distance and the price. These objectives are in conflict with each other. Instead of searching for an optimal solution, we must search for an optimal efficient front. This kind of problems are referred as bi-objective, because improving one objective, almost always lowers the other. So, we keep a set of optimal solutions, where there are some with good distances and others with good prices, and we present this set as a non dominated front. We use a branch and bound algorithm in order to find the non dominated fronts of optimal solutions. We apply some basic cuts in the search space during the exact algorithm, in order to avoid visiting unnecessary solutions. We create a database of solutions obtained by the truncated exact algorithm and a Hill Climbing algorithm.
Description
Keywords
TPP (Travelling Purchaser Problem) Mercados Produtos Preços Otimização biobjetivo Algoritmos Travelling Purchaser Problem Exponential complexity Algorithms Optimization Bi-objective
Citation
Marques, João Carlos Rodrigues - O problema do mercador viajante [Em linha]. [S.l.]: [s.n.], 2016. 77 p.