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

► We consider a variant of the Location-Routing Problem (LRP), namely the LRP with simultaneous pickup and delivery. ► We propose two polynomial-size mixed integer linear programming formulations, called flow- and node-base formulations, and a family of valid inequalities to strengthen the formulations. ► We also propose a two-phase heuristic approach based on simulated annealing, tp_SA, to solve the large-size problems. ► Computational results show that while the flow-based formulation performs better than the node-based formulation on small-size problems, the node-based formulation can yield competitive lower bounds on medium-size problems. ► The proposed heuristic approach is computationally efficient in finding good quality solutions.