Problema de transportes nos CTT

Abstract

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.

In the problem of transportation of CTT (PTC), the vehicles can immobilize at the end of its journey, and afterwards resume a new route from the point of immobilization to the depot. This problem can be characterized as a Vehicle Routing Problem (VRP), in which vehicles routes are divided in two separate sets: delivery routes and pick up routes to be performed in a different period of time. At the end of delivery routes, the vehicle does not need to return to the depot. Therefore, pick up routes may begin either on an immobilization point or at the depot, but both must end at the base depot of the vehicle. In addition to this very particular point, other aspects of the PTC, make it differ from the VRP, as it will be described. In this work, an improvement local search heuristic to solve the PTC, will be present. Computational experiment shows good performance of the proposed heuristic, but it can be improved, including the possibility of reducing the number of immobilized trips.