COG: a composite genetic algorithm with local search methods to solve a mixed vehicle routing problem with backhauls

This paper considers a variant of the Vehicle Routing Problem (VRP) called Mixed Vehicle Routing Problem with Backhauls (MVRPB), an extension of the Vehicle Routing Problem with Backhauls (VRPB). This problem involves two sets of customers, called line-haul and backhaul customers. The demand of each line-haul customer is served by a single depot with a set of homogeneous capacitated vehicles. Apart from this, some amount of load needs to be picked up from the backhaul customers and should be taken back to the depot. The visit sequence of vehicles for line-haul and backhaul customers is mixed. The application of the MVRPB for the public healthcare system is explained. The MVRPB is a well-known, proven Non-deterministic Polynomial (NP)-hard problem. Various heuristic algorithms are proposed to solve the MVRPB to obtain approximate solutions. In this paper, we propose a composite Genetic Algorithm (GA) combined with different local search methods to solve the MVRPB. This is the first research paper for the application of metaheuristics with local search methods to solve the MVRPB. Extensive computational investigation for the MVRPB instances shows the efficacy of the proposed algorithm.