A memetic algorithm for the capacitated location-routing problem with mixed backhauls

The design of distribution networks is one of the most important problems in supply chain and logistics management. The main elements in designing a distribution network are location and routing decisions. As these elements are interdependent in many distribution networks, the overall system cost can decrease if location and routing decisions are simultaneously tackled. In this paper, we consider a Capacitated Location-Routing Problem with Mixed Backhauls (CLRPMB) which is a general case of the capacitated location-routing problem. CLRPMB is defined as finding locations of the depots and designing vehicle routes in such a way that pickup and delivery demands of each customer must be performed with the same vehicle and the overall cost is minimized. Since CLRPMB is an NP-hard problem, we propose a memetic algorithm to solve the problem. To evaluate the performance of the proposed approach, we conduct an experimental study and compare its results with the lower bounds obtained by the branch-and-cut algorithm on a set of instances derived from the literature. Computational results indicate that the proposed approach is able to find optimal or very good quality solutions in a reasonable computation time.