Heurísticas para problemas integrados de roteamento e empacotamento de um único veículo com coletas e entregas

Abstract

The present work deals with integrated routing and three-dimensional packing problems of a single vehicle. In particular, the studies consider pickup and delivery constraints in two distinct problems: (i) problems with backhauls, where a single vehicle must depart loaded from the warehouse to perform all deliveries and then perform all pickups as route defined; (ii) problems with pickup and delivery pairs, where a vehicle must leave the warehouse empty to perform the pickups and deliveries during the route, returning then empty to the warehouse. In the first case, there is a precedence constraint between all deliveries and all pickups, while in the second case there are precedence constraints between each pickup client and its respective delivery pair. In both cases, the three-dimensional geometry of the items (boxes) to be picked up and delivered is considered, as well as multiple orientation constraints, packing stability and multiple destinations. Because these are problems that are little addressed in the literature, it is explored in this study how some methods can optimize the search for a feasible solution. Heuristic optimization methods are used to deal with the presented problems, such as the Clarke & Wright algorithm for vehicle routing and the George & Robinson algorithm for boxes packing, as well as the Simulated Annealing meta-heuristic to integrate the use of both algorithms. One algorithm were developed to solve each of the problems addressed in this study with instances generated from the literature. With the results obtained it was possible to observe that the use of heuristic and metaheuristic methods to tackle the problems, as proposed in this study, is promising. The results and methods still provide room for further improvements and testing, but they are capable of generating good quality solutions. Isolated testing of the routing and packing strategies can be improved with the implementation of new local search algorithms and optimizations on the search space.