Multi-Period Profit-Oriented Location Routing Problem in Multi-User Warehouses with Backordering and Order Acceptance: A Relax-Fix-Optimize Heuristic

This paper addresses profit maximization in location routing problem (LRP) where backordering is allowed and serving all customers is not mandatory. The problem is motivated by the practical case of distribution companies using temporary multi-user warehouses to serve their customers. We propose a multi-period novel mixed integer linear programming (MILP) model for the problem where demand is price sensitive. The model seeks to find optimal locations of warehouses over the planning horizon, set of orders to serve, to backorder or to reject, and routing decisions giving optimal profit. The commercial solver (CPLEX) is used to solve the model on small instances. For medium and large instances, we propose a solution approach that incorporates the Relax and Fix (R&F), Fix and Optimize (F&O) procedures combined with local search heuristics. Computational experiments and economic analysis show the relevance of the proposed approach and the impact of parameters on generated profit.