Planeamento de Rotas num Sistema de Recolha de Desperdícios de Madeira

Neste artigo, analisa-se um novo problema de planeamento de rotas, o Prize Collecting Vehicle Routing Problem with service restrictions (PCVRPsr), sugerido por um caso de recolha de desperdícios de madeira. É um problema onde a frota é homogénea, o depósito único e em que a visita a alguns clientes não é obrigatória, mas condicionada pelas necessidades totais de desperdícios. Propõe-se uma formulação para este problema que deriva de um modelo de fluxo de três índices para o problema de planeamento de rotas de veículos. Para a optimização do plano de rotas, exploraram-se métodos de decomposição. Analisa-se, em particular, a aplicação do método de decomposição de Dantzig-Wolfe à formulação proposta e, para a obtenção de soluções inteiras, o método de partição e geração de colunas (branch-and-price). Foi desenvolvido um algoritmo com o qual se obtiveram os resultados computacionais que analisamos na parte final do artigo. No algoritmo de pesquisa em árvore, foi aplicado um método de determinação de limites inferiores para o problema de empacotamento, baseado em funções duais válidas, que torna o processo mais eficiente.

Bibliographic Details

Main Authors:	Alves,Cláudio Manuel Martins, Carvalho,José Manuel Valério de
Format:	Digital revista
Language:	Portuguese
Published:	APDIO - Associação Portuguesa de Investigação Operacional 2004
Online Access:	http://scielo.pt/scielo.php?script=sci_arttext&pid=S0874-51612004000100002
Tags:	Add Tag No Tags, Be the first to tag this record!