Problema de distribuição de correio

No problema de transportes de serviço postal dos CTT (PTC), os veículos, que distribuem e recolhem o correio, podem imobilizar num ponto, depois de efectuarem um certo trajecto, podendo, mais tarde, realizar um novo trajecto a partir do ponto de imobilização. Este problema pode caracterizar-se como uma generalização do Vehicle Routing Problem (VRP), em que os veículos imobilizados, não tendo a necessidade de voltar ao depósito no trajecto inicialmente efectuado, terão de regressar num novo trajecto a realizar num período do dia diferente. Para além desta questão muito particular, outras especificidades do PTC fazem-no diferir do VRP, surgindo algumas em variantes do VRP como se descreverá. Neste trabalho apresenta-se uma heurística melhorativa de pesquisa local para a resolução do PTC, que apresenta resultados positivos, mas que pode ser melhorada, nomeadamente na possibilidade de reduzir o número de viagens imobilizadas.