The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach

In this paper, we consider a variant of the Location-Routing Problem (LRP), namely the LRP with simultaneous pickup and delivery (LRPSPD). The LRPSPD seeks to minimize total cost by simultaneously locating the depots and designing the vehicle routes that satisfy pickup and delivery demand of each customer at the same time. We propose two polynomial-size mixed integer linear programming formulations for the problem and a family of valid inequalities to strengthen the formulations. While the first formulation is a node-based formulation, the second one is a flow-based formulation. Furthermore, we propose a two-phase heuristic approach based on simulated annealing, tp_SA, to solve the large-size LRPSPD and two initialization heuristics to generate an initial solution for the tp_SA. We then empirically evaluate the strengths of the proposed formulations with respect to their ability to find optimal solutions or strong lower bounds, and investigate the performance of the proposed heuristic approach. Computational results show that the flow-based formulation performs better than the node-based formulation in terms of the solution quality and the computation time on small-size problems. However, the node-based formulation can yield competitive lower bounds in a reasonable amount of time on medium-size problems. Meantime, the proposed heuristic approach is computationally efficient in finding good quality solutions for the LRPSPD.