Modelos e algoritmos para problemas integrados de distribuição e roteamento (Models and algorithms for the integrated routing and distribution problems)

Abstract

Since the Vehicle Routing Problem (VRP) was introduced by Dantzig and Ramser, it became one of the most studied problems in Combinatorial Optimization. Different solution approaches were proposed over the past decades to solve the VRP and its vari-ants. In this thesis, we discuss about two VRP variants, resulting from the integrationof VRPs with distribution problems. The first problem takes place by integrating the VRP with loading/unloading de-cisions in a Cross-Docking warehouse, which allows the consolidation of loads between their pickup and delivery. The problem of dealing with routing and distribution deci-sions at the Cross-Docking is named the Vehicle Routing Problem with Cross-Docking (VRPCD). We introduced two Integer Programming (IP) formulations for the VRPCD and respective branch-and-price (BP) algorithms to evaluate them. We also consider aslightly different approach for solving the VRPCD, where vehicles are allowed to bypass the Cross-Docking and loads eventually are not consolidated. We call this problem as the Pickup and Delivery Problem with Cross-Docking (PDPCD). We also introduced an IP model for the PDPCD and a BP algorithm to solve it. The second problem we deal in this thesis arises in multi-echelon systems. The Two-Echelon Capacitated Vehicle Routing Problem (2E-CVRP) arises where loadsmust be shipped from a depot to customers passing through intermediate warehouses named satellites. Loads are shipped from the depot to satellites, where they are con-solidated before to be delivered to their respective customers. We propose an IP for-mulation for 2E-CVRP which holds an exponential number of variables. In addition, we introduce four families of valid inequalities for the problem. To solve such a formu-lation, including valid inequalities, we implement a Branc h-and-cut-and-price (BCP) algorithm. Our computational results show that BCP algorithm evaluates stronger lower and upper bounds than previous algorithms for 2E-CVRP and also provides new optimality certificates for different instances of the literature.