Metaheuristics With Random Keys And Local Search For The Vehicle Routing Problem With Private Fleet And Common Carrier

Abstract

The Vehicle Routing Problems (VRPs) have been target of a high number of studies in the Operational Research area, given its applicability on several fields. Among its categories are the Vehicle Routing Problems with Profits. Those problems are characterized by the lack of obligatoriness in the service of all customers. Instead, a profit or prejudice rate to the service of each customer is defined. This category presents the Vehicle Routing Problem with Private Fleet and Common Carrier (VRPPFCC). In this problem, besides the traditional vehicle routing to serve customers, considering demand and capacity, there is the possibility of outsourcing partly the service, considering the profitability in such process. This study applies two meta-heuristics based on random keys, Biased Random Keys Genetic Algorithm (BRKGA) and Unified Marginal Distribution Algorithm (UMDA) on the solution of the VRPPFCC. It also combines such meta-heuristics with variations of Random Variable Neighborhood Descent (RVND), Self-Adaptive Variable Neighborhood Descent (SAVND), and additional conceived local search methods, in order to further explore the search space. Aiming to make a better use of computational resources in local searches, the Clustering Search (CS) hybrid method is used, seeking to improve the obtained solutions quality by managing the application of the local search procedure, evaluating promising regions of the search space. Computational tests are performed with available instances in the literature, and the method results and behaviors are compared. Finally, conclusions are made based on the achieved results