Location-Allocation Problem Based on Order Distribution in Instant Retailing: An Efficient Branch-and-Bound Integrated Lagrangian Relaxation

What the paper says

To meet the 30-min delivery demand for online orders, instant retailers (IRs) must strategically locate micro-fulfillment centers (MCs) to serve their dedicated communities. These MCs, densely distributed near communities with limited capacity, may only partially fulfill demand, necessitating integrated decisions on item assortment. Furthermore, the per-order delivery model underscores the substantial impact of order distribution on fulfillment costs a factor often overlooked in conventional location-allocation problems. We address these challenges by formulating an integer programming model that incorporates order distribution to simultaneously optimize MC location selection, service area allocation, and item assortment with inventory. To reduce computational complexity, we propose a branch-and-bound integrated Lagrangian relaxation algorithm, which decomposes the model into two subproblems. For the first subproblem, concerning MC location selection, we design a pegging test to streamline the branch-and-bound process; this method can be extended to scale down general location problems. For the second subproblem, we use approximated shadow prices to design heuristics for the remaining allocation and assortment decisions with inventory. Using real-world and synthetic data, we demonstrate our algorithm’s efficiency compared to Gurobi and a metaheuristic, as it achieves a 2[Formula: see text] gap from the upper bound efficiently. We also demonstrate the importance of incorporating order distribution in instant retailing.