2023/04/21 by Etika Agarwal, Agarwal, Etika, Karthik S. Gurumoorthy +5
Business, Management and Accounting · Engineering · #FOS: Mathematics #Facility Location and Emergency Management #Maritime Ports and Logistics #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2304.10799
openalex publication_date 2023/04/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the extended version of the non-uniform, capacitated facility location problem with multiple fulfilment channels between the facilities and clients, each with their own channel capacities and service cost. Though the problem has been extensively studied in the literature, all the prior works assume a single channel of fulfilment, and the existing methods based on linear programming, primal-dual relationships, local search heuristics etc. do not scale for a large supply chain system involving millions of decision variables. Using the concepts of sub-modularity and optimal transport theory, we present a scalable algorithm for determining the set of facilities to be opened under a cardinality constraint. By introducing various schemes such as: (i) iterative facility selection using incremental gain, (ii) approximation of the linear program using novel multi-stage Sinkhorn iterations, (iii) creation of facilities one for each fulfilment channel etc., we develop a fast but a tight approximate solution, requiring O((3+k)/(m)ln(\frac1ε)) instances of optimal transport problems to select k facilities from m options, each solvable in linear time. Our algorithm is implicitly endowed with all the theoretical guarantees enjoyed by submodular maximisation problems and the Sinkhorn distances. When compared against the state-of-the-art commercial MILP solvers, we obtain a 100-fold speedup in computation, while the difference in objective values lies within a narrow range of 3%.