Esse trabalho trata do problema do roteamento e da programação de uma frota de veículos no contexto da distribuição física. Com base nos resultados da análise de alguns casos reais, propos-se a formulação matemática do problema de roteamento e programação (PRP), de forma a incorporar as principais condicionantes identificadas nesses casos. A revisão bibliográfica indicou que, dentre os caminhos potenciais para o PRP se destaca uma heurística de decomposição do problema de roteamento em dois subproblemas: o agrupamento de tarefas a cada um dos veículos e o posterior roteamento de cada um dos veículos da frota. Nesse contexto foram implementados dois algorítmos: um de programação dinâmica para o roteamento de um único veículo e o outro para o problema de caminho mínimo com janelas de tempo, para o qual se propos um critério adicional de dominação. Ambos os algoritmos foram implementados em microcomputador. Foram realizados testes que comprovam a efeciência computacional do algoritmo de caminho mínimo com o teste adicional de dominação; com relação ao algoritmo de roteamento, concluiu-se haver necessidade de aprimoramentos para melhorar seu desempenho.

This paper addresses the multiple vehicle routing and scheduling problem in the context of the physical distribution, specially in large cities and urban areas. Some typical examples of physical distribution are described and analysed. The proposed mathematical formulation was based on the results of this analysis and deals with multiple vehicles, time windows, vehicle capacity and precedence constraints. The literature review indicated some potential solution strategies, including branch-and-bound and column generation based algorithms. It was also found that a heuristic which decomposes a multiple vehicle routing problem into a clustering stage and a routing stage seems to be a very promising solution strategy. Thus, two different algorithms were implemented: a dynamic programming algorithm for the single vehicle routing problem and a generalized permanent labelling algorithm for the shortest path problem with time windows. The former may be used in the context of the decomposition heuristic mentioned above as well as in a branch-and-bound strategy. The later, wich includes a new dominance criterion, may be used in a branch-and-bound algorithm and for the subproblem arisen in the column generation method. Both algorithms were implemented on a microcomputer. Tests performed point out the efficiency of the new dominance criterion for the shortest path algorithm. On the other hand, the single vehicle routing algorithm requires the introduction of additional criteria for the elimination of infeasible states in order to improve its computational performance.