Solving Multi-capacitated Facility Location Problem in Traffic Control Systems Using Lagrangian Relaxation and Decomposition Approach

The Budget-Constraint Multi-Capacitated Location Problem represents a generalized extension of the classical p-median location problems. It involves the allocation of predetermined capacity levels constraints to each facility while efficiently assigning customers within a network to minimize total connection costs. In this study, we explore the application of this model in the domain of road traffic regulation to optimize network installation and determine the appropriate server configurations required for processing data collected from sensors. In the second section of this paper, we address the problem through a new approach rooted in Lagrangian relaxation and decomposition. This innovative approach facilitates parallel computing, resulting in a notable reduction in execution time. The resolution of this complex problem encompasses two key stages: the calculation of Lagrange multipliers and the implementation of a heuristic method to ensure solution feasibility. Ultimately, we present computational results obtained by solving new instances derived from p-median problems found in the existing literature. Our research contributes to addressing real-world traffic management challenges by optimizing facility placement and resource allocation, with practical implications for improving traffic control systems.