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.
| Main Authors: | , |
|---|---|
| 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!
|
| Summary: | 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. |
|---|