Uma metaheurística Simulated Annealing para o Problema do Caixeiro Viajante Multicommodity com custos fixos, variáveis e prioridades

Abstract

Neste trabalho apresentamos um novo problema do caixeiro viajante multiproduto, no qual além dos custos fixos, consideramos custos variáveis, ou seja, custos dependentes do produto a ser transportado, e prioridades. Estas prioridades constituem valores a serem pagos ao caixeiro de acordo com a ordem de visitação do cliente. Pela natureza do problema, propomos um modelo matemático baseado em fluxo em rede e implementamos uma metaheurística híbrida combinando Simulated Annealing com busca local. A metaheurística proposta mostrou-se competitiva para as instâncias analisadas.