Este trabalho aborda o problema de roteamento de veículos com frota mista, janelas de tempo e custos escalonados o FSMVRPTWSC (the Fleet Size and Mix Vehicle Routing Problem with Time Windows and Step Costs). Esse problema adiciona ao problema de roteamento de veículos custos fixos por faixas de distância percorridas por veículo, de acordo com o seu tipo. Essa forma de aferição de custo é possível quando a entrega é feita por um parceiro logístico e é uma prática que simplifica o cálculo e verificação da cobrança frete a pagar pela empresa contratante e contratada. Ao endereçar esse problema, este trabalho o caracteriza cuidadosamente e propõe diferentes abordagens para sua solução. Um modelo de programação linear inteira mista é apresentado; seguido por duas heurísticas construtivas, com base em inserções sequenciais, três movimentos de busca em vizinhança, duas meta-heurísticas, o VNS (Variable Neighbourhood Search) e GRASP (Greedy Randomized Adaptive Search Procedure), e um método híbrido que combina os dois. Os métodos são avaliados em instâncias geradas com base em referências na literatura, além de outras de dimensões menores, a fim de se obter resultados ótimos globais, e instâncias reais a partir de um estudo de caso. Apesar do ineditismo do problema na literatura, as comparações feitas com os resultados obtidos pelos diferentes métodos e instâncias mostram que as escolhas feitas no trabalho se justificam.

This work addresses the FSMVRPTWSC, the Fleet Size and Mix Vehicle Routing Problem with Time Windows and Step Costs. This problem is a proposition of adding attributes to the vehicle routing problem that seeks to bring fixed costs per distance traveled by each type of vehicle. This form of cost attirbution is possible when the delivery is performed by a logistics partner and is a practice that simplifies the calculation and verification of the freight costs to be payed by the company that hires the service. In addressing this problem, this work carefully characterizes and proposes a mathematical model, two constructive heuristical method, three neighborhood search movements, two metaheuristics, the VNS (Variable Neighborhood Search) and GRASP (Greedy Randomized Adaptive Search Procedure) and a hybrid method combining both meta-heuristics. The methods are evaluated in instances generated based on references in the literature, in addition to smaller dimensions, in order to obtain optimal global results, and real instances with from a case study. Despite the novelty of the problem in the literature, comparisons made with the results obtained in the di?erent methods and instances show that the choices made in the work are justified.