Esta tese trata do problema de roteirizarão de veículos com restrições operacionais, em especial janelas de tempo e duração máxima da jornada. Os veículos da frota podem ser de diferentes tamanhos. O problema consiste na determinação de um conjunto de roteiros econômicos, que devem atender a um conjunto de clientes, respeitando-se as janelas de tempo. A revisão da literatura disponível abrangeu a classificação dos problemas de roteirizarão, bem como os métodos de solução. Foram também discutidos os fatores que afetam a aplicação dos modelos em situações reais e relacionadas as principais referências encontradas na literatura. A estratégia de solução proposta é baseada na relaxação Lagrangiana das restrições do modelo relacionadas ao atendimento de todos os clientes exatamente uma vez. Como o problema relaxado é ainda difícil de resolver, a estratégia proposta é heurística, e utiliza uma versão aprimorada de um algoritmo de etiquetamento permanente para o problema de caminho mínimo com janelas de tempo. Três diferentes heurísticas foram desenvolvidas a partir desta estratégia de solução. Duas delas destinam-se exclusivamente a problemas com frota homogênea. Já a heurística de agrupamento e alocação sequêncial pode ser utilizada em problemas com frota heterogênea.

This thesis deals with the vehicle routing problem with operational constraints, including time Windows and maximum journey length. The fleet may be composed of vehicles of different sizes. This problem involves the design of a set of minimum cost routes which must serve a set of customers with known demands. Each customer must be serviced exactly once during its allowable delivery time or time window. A literature review has been achieved, concerning the classification of routing problems and also the proposed methods for its solution. Practical issues concerning real world applications are also discussed. Some important references about practical applications found in the literature are listed. It has been proposed a solution strategy which is based on the Lagrangian relaxation of the constraints which require each costumer to be served exactly once. As the relaxed problem is still hard to solve for instances with more than one vehicle, the heuristic solution proposed uses an improved version of the generalized permanent labeling algorithm for the shortest path problem with time windows. Based on this strategy, three different heuristics have been developed. Two of them deal only with problems with homogeneous fleets. In the third one, the Cluster and Sequential Alocation Heuristic, the fleet may be composed of vehicles of different sizes and types. All heuristics were evaluated based on the six test problem sets developed by SOLOMON (1987). The results demonstrate that the Cluster and Sequential Alocation Heuristic perform better than Solomons tested models for most sets of problems. The others perform well in some sets of problems. The Cluster and Sequential Alocation Heuristic has also been applied to a real urban distribution problem in São Paulos metropolitan area. This problems comprises 136 costumers with time windows constraints. The results have shown expressive reduction on the total distance travelled, the cost of the solution and the number of vehicles used, when compared to the manual scheduling performed by the companys scheduling staff.