Estratégias de Programação Inteira para o VRPTW na logística de entregas urbanas expressas de última milha em grandes instâncias reais de cidades brasileiras

Abstract

Driven by the COVID-19 pandemic and sustained by the country’s economic recov- ery, the growth of e-commerce in Brazil has been enormous, keeping pace with the rest of the world. This expansion has posed a significant challenge for companies, with more complex logistics, same-day delivery, and various time constraints. Given this context, this dissertation explores integer programming strategies to model and solve the dynamic and stochastic aspects of routing problems in express urban delivery logistics, focusing on large Brazilian cities, as represented by the Vehicle Routing Problem with Time Windows (VRPTW). The VRPTW is a complex combinatorial optimization problem that involves finding the most efficient routes for a fleet of vehicles to serve a set of customers, each with a specific time window for service, and that extends the classical NP-hard VRP by impos- ing temporal constraints on the existing. The primary objective is to minimize total travel costs (in terms of distance or time). To solve this problem, integer programming formula- tions implemented in the CPLEX tools were investigated, which use the Branch-and-Cut method, and a purpose-built tool for solving VRPs, VRPSolver, which uses the Branch- and-Price column generation method, where subproblems are modeled as shortest-path problems with resource constraints. In particular, the VRPSolver strategy was tested on three sets of instances: (1) classic artificial Solomon instances; (2) large real urban in- stances of Brazilian cities adapted from the loggiBUD benchmark, from the repository of the express delivery company Loggi, a partner in the research project; (3) and a new set of instances generated from the state of Amazonas (Manaus and some adjacent cities). The results were satisfactory, with the column generation method used by VRPSolver showing better performance in VRPTW, especially when time windows are tighter, as well as in large real urban instances of Brazilian cities, validating its applicability in real- istic logistics scenarios, and with the conducted investigation presenting possibilities for understanding and mitigating logistical complexity in the Brazilian Amazon region.