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

Abstract

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.