A carregar...
Publicação
An iterated local search algorithm for the traveling purchaser problem
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 477.81 KB | Adobe PDF |
Autores
Orientador(es)
Resumo(s)
The Traveling Purchaser Problem (TPP) is a generalization of the Traveling
Salesman Problem (TSP) in which a list of items must be acquired by
visiting a subset of markets. The objective is to minimize the total cost
sustained along the route, including purchasing and traveling costs. Due to
the NP-hard nature of the problem, solving the TPP in an exact manner
is computationally challenging, implying the need for heuristic approaches
in order to obtain quality solutions efficiently. This study proposes an algorithm
based on the metaheuristic Iterated Local Search (ILS), complemented
by a route configuration procedure that adjusts the subset of markets in the
solution. The algorithm is tested in benchmark instances, providing a performance
comparison with other methods. The computational experiment
for the asymmetric instances reveals the effectiveness and efficiency of the
algorithm, outperforming previously published results with statistical significance.
Additional experiments are presented for the symmetric instances,
pointing to the competitiveness and versatility of the algorithm in relation
to other heuristic approaches used in the literature.
O problema do comprador viajante é uma generalização do problema do caixeiro viajante, no qual uma lista de itens tem de ser adquirida ao visitar um subconjunto de mercados. O objetivo consiste em minimizar o custo total que inclui os custos de compra dos itens e os custos de deslocação. Trata-se de um problema NP-difícil, pelo que resolvê-lo de forma exata é ineficiente em termos computacionais, implicando a necessidade de recorrer a métodos heurísticos de modo a obter soluções de qualidade de forma eficiente. Este estudo propõe um algoritmo baseado no conceito metaheurístico de pesquisa local iterativa, complementado com um procedimento de configuração de rota que ajusta o subconjunto de mercados da solução. O algoritmo é testado em instâncias de referência, proporcionando uma comparação de desempenho com outros resultados na literatura. A experiência computacional para as instâncias assimétricas revela a eficácia e eficiência do algoritmo, obtendo melhores resultados com significância estatística. São apresentadas experiências computacionais adicionais para as instâncias simétricas, apontando a competitividade e versatilidade do algoritmo em relação a outros métodos heurísticos usados na literatura.
O problema do comprador viajante é uma generalização do problema do caixeiro viajante, no qual uma lista de itens tem de ser adquirida ao visitar um subconjunto de mercados. O objetivo consiste em minimizar o custo total que inclui os custos de compra dos itens e os custos de deslocação. Trata-se de um problema NP-difícil, pelo que resolvê-lo de forma exata é ineficiente em termos computacionais, implicando a necessidade de recorrer a métodos heurísticos de modo a obter soluções de qualidade de forma eficiente. Este estudo propõe um algoritmo baseado no conceito metaheurístico de pesquisa local iterativa, complementado com um procedimento de configuração de rota que ajusta o subconjunto de mercados da solução. O algoritmo é testado em instâncias de referência, proporcionando uma comparação de desempenho com outros resultados na literatura. A experiência computacional para as instâncias assimétricas revela a eficácia e eficiência do algoritmo, obtendo melhores resultados com significância estatística. São apresentadas experiências computacionais adicionais para as instâncias simétricas, apontando a competitividade e versatilidade do algoritmo em relação a outros métodos heurísticos usados na literatura.
Descrição
Mestrado Bolonha em Métodos Quantitativos para a Decisão Económica e Empresarial
Palavras-chave
Traveling purchaser problem Metaheuristics Iterated local search Route configuration Problema do comprador viajante Meta-heurísticas Pesquisa local iterativa Configuração de rota
Contexto Educativo
Citação
Kapancioglu, Tomás Silva (2024). “An iterated local search algorithm for the traveling purchaser problem”. Dissertação de Mestrado. Universidade de Lisboa. Instituto Superior de Economia e Gestão
Editora
Instituto Superior de Economia e Gestão