O problema de localização-roteamento em dois níveis com janelas de tempo e múltiplos entregadores

The Vehicle Routing Problem with Time Windows and Multiple Deliverymen (VRPTWMD) is a real-life goods distribution problem that arises in regions with high customer density and where the delivery vehicles face trafic and parking dificulties. Because of these dificulties, the distribution is carried out in two levels; each vehicle travels between groups (clusters) of customers close to each other, and for each cluster, the delivery of the products is performed by the driver and possibly some helpers traveling with the driver and who visit the customers on foot from the vehicle stop location. The use of multiple deliverymen is a practice of companies for reducing service times in the clusters, which in turn allows increasing the number of customers served within working hours. The vast majority of the works on the theme assumes that the vehicles’ parking spots and the subset of customers in each cluster is previously determined and the routing is limited to the first level with service times in the cluster defined according to the number of deliverymen. In this research we incorporate secondleveldecisions into the VRPTWMD, leading to the extension henceforth called Two-echelon Location-Routing Problem with Time Windows and Multiple Deliverymen (2E -LRPTWMD). The 2E-LRPTWMDaims, therefore, to obtain the location, routing and scheduling of vehicle parking spots, the number ofdeliverymen in each vehicle, as well as the assignment, routing and scheduling of customer subsetsserved by the deliverymen in each vehicle from the selected parking spots. These decisions must betaken in order to minimize the total cost to serve all demands. With this objective, we propose amathematical model whose main feature is the consideration of service times of clusters as not onlyexplicitly dependent on the number of deliverymen allocated to the routes, but also on the distances between the selected customers that comprise the clusters. Computational experiments with smallsizedinstances (12 customers) validate the model while a discussion on the model/solution methodbehaviour under diferent scenarios is performed using instances up to 50 customers generated fromthe Solomon (1987)’s examples for the Vehicle Routing Problem with Time Windows. Additionally,we show that the model/method has a better performance when tackling instances based on real datainvolving up to 50 customers.Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)O Problema de Roteamento de Veículos com Janelas de Tempo e Múltiplos Entregadores (Vehicle Routing Problem with Time Windows and Multiple Deliverymen - VRPTWMD) é um problema logístico que surge em atividades reais de distribuição de bens em regiões com alta densidade de clientes e em que os veículos de entrega enfrentam dificuldades de trânsito e estacionamento. Devido a essas dificuldades, a distribuição é realizada em dois níveis; cada veículo se desloca entre agrupamentos (clusters) de clientes próximos entre si, e em cada cluster, a entrega dos produtos é realizada pelo motorista e possivelmente alguns ajudantes que viajam com o motorista e que visitam os clientes a pé, a partir do local de parada do veículo. O uso de múltiplos entregadores é uma prática de empresas para redução do tempo de serviço nos clusters, o que permite o aumento do número de clientes atendidos durante a jornada de trabalho diária. A grande maioria dos trabalhos no tema pressupõe que os pontos de parada e o subconjunto de clientes em cada cluster tenham sido decididos previamente, estando o roteamento limitado ao primeiro nível com tempos de serviço nos clusters definidos em função do número de entregadores. Nesta pesquisa, as decisões do segundo nível são incorporadas ao VRPTWMD, dando origem à extensão aqui denominada Problema de Localização-Roteamento em Dois Níveis com Janelas de Tempo e Múltiplos Entregadores (Two-echelon Location-routing Problem with Time Windows and Multiple Deliverymen - 2E-LRPTWMD). O 2E-LRPTWMD visa, portanto, obter a localização, o roteamento e a programação de pontos de parada dos veículos, o número de entregadores em cada veículo, assim como a designação, o roteamento e a programação do subconjunto de clientes servidos pelos entregadores de cada veículo a partir dos pontos de parada selecionados. Estas decisões devem ser tomadas de maneira a minimizar o custo total para o atendimento de todas as demandas. Com este objetivo, é proposto um modelo matemático cujo principal destaque é a consideração do tempo de serviço em cada cluster como uma variável não só explicitamente dependente do número de entregadores da rota, como também das distâncias percorridas entre os clientes selecionados para compor o cluster. Experimentos computacionais com instâncias de pequeno porte (12 clientes) mostram a validade do modelo, enquanto uma análise do comportamento do modelo/ método de solução sob diferentes cenários é realizada utilizando instâncias até 50 clientes geradas a partir dos exemplos de Solomon (1987) para o Problema de Roteamento de Veículos com Janelas de Tempo. Além disso, resultados com instâncias baseadas em dados reais envolvendo até 50 clientes, mostram que o modelo/método tem desempenho superior quando comparado ao das instâncias fictícias