The two-echelon multi-products location-routing problem with pickup and delivery: formulation and heuristic approaches

The two-echelon location-routing problem (LRP-2E) considers the first-level routes that serve from one depot a set of processing centres, which must be located and the second-level routes that serve customers from the opened processing centres. In this paper, we consider an extension of the LRP-2E, where the second-level routes include three constraints that have not been considered simultaneously in the location routing literature, namely multi-product, pickup and delivery, and the use of the processing centre as intermediate facility in the second-level routes. This new variant is named two-Echelon Multi-products Location-Routing problem with Pickup and Delivery (LRP-MPPD-2E). The objective of LRP-MPPD-2E is to minimise both the location and the routing costs, considering the new constraints. The first echelon deals with the selection of processing centres from a set of potential sites simultaneously with the construction of the first-level routes, such that each route starts from the main depot, visits the selected processing centres and returns to the main depot. The second echelon aims at assigning customers to the selected processing centres and defining the second-level routes. Each second-level route, starts at a processing centre, visits a set of customers, through one or several processing centres, and then returns to the first processing centre. We present a mixed-integer linear model for the problem and use a Cplex solver to solve small-scale instances. Furthermore, we propose non-trivial extensions of the nearest neighbour and insertion approaches. We also develop clustering-based approaches that have not been extensively investigated with regards to location routing. Computational experiments are conducted to evaluate and to compare the performances of the proposed approaches. The results confirm the effectiveness of clustering approaches.