Modelagem matemática e métodos de solução para o problema do caixeiro viajante

• Processo: 07/08352-2
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de junho de 2008
• Data de Término da vigência: 31 de dezembro de 2008
• Área de conhecimento: Engenharias - Engenharia de Produção - Pesquisa Operacional
• Pesquisador responsável: Maria Do Socorro Nogueira Rangel
• Beneficiário: Michelli Maldonado Carretero
• Instituição Sede: Instituto de Biociências, Letras e Ciências Exatas (IBILCE). Universidade Estadual Paulista (UNESP). Campus de São José do Rio Preto. São José do Rio Preto , SP, Brasil
• Vinculado ao auxílio: 06/03496-3 - Teoria e prática dos problemas de corte e empacotamento, AP.TEM
• Assunto(s): Planejamento da produção Problemas de sequenciamento de padrões de corte Dimensionamento de lotes Problema do caixeiro viajante (PCV) Otimização combinatória Branch-and-cut Inequações
• Palavra(s)-Chave do Pesquisador: branch and cut | inequações válidas | Métodos exatos | problema do caixeiro viajante | Problemas Integrados | sequenciamento | Otimização Combinatória

Resumo

O planejamento da produção em indústrias que envolvem a produção de diversos itens, utilizando várias máquinas, são tarefas complexas e precisam ser realizadas rotineiramente. Em alguns setores industriais, tais como, bebidas, móveis, fios condutores, a produção dos itens envolve tempos e custos de preparo das máquinas dependentes da ordem em que os itens são produzidos. Muitas vezes o planejamento da produção envolve o dimensionamento dos lotes (e/ou corte de matéria prima) e o sequenciamento dos itens. Estes aspectos do problema podem ser tratados de forma independente ou integrados. No caso do desenvolvimento de modelos integrados (e.g. dimensionamento de lotes e sequenciamento, corte de matéria prima e sequenciamento), o problema do caixeiro viajante pode ser usado para capturar o aspecto do sequenciamento. O presente projeto tem como objetivo investigar a formulação matemática e métodos de solução para o problema do Caixeiro Viajante Assimétrico com ênfase na reformulação automática do problema através da inclusão de inequações válidas e à investigação da eficiência do método branch and cut. (AU)