1510. The clustered multimode set covering problem
Invited abstract in session MA-15: Applications to Logistics and Supply Chain Management, stream Combinatorial Optimization.
Monday, 8:30-10:00Room: Esther Simpson 1.08
Authors (first author is the speaker)
| 1. | Andrea Mancuso
|
| Department of Political Sciences, University Federico II of Naples | |
| 2. | Antonio Manuel Rodriguez-Chia
|
| Estadistica e IO, Universidad de Cádiz | |
| 3. | Francisco Saldanha-da-Gama
|
| Sheffield University Management School | |
| 4. | Claudio Sterle
|
| Department of Electrical Engineering and Information Technology, Università Federico II di Napoli |
Abstract
Covering problems optimize facility placement to serve demand points while minimizing costs or maximizing coverage. Classical models, such as the set covering (SCP) and maximal covering location problems, achieve this by either minimizing the number of facilities required to cover all demand points or maximizing coverage with a fixed number of facilities. However, they usually assume a single facility type, which overlooks real-world scenarios where individuals require access to multiple services. In these cases, multiple facility types may compete for locations, preventing the problem from decomposing into independent subproblems. Moreover, ensuring proximity to facilities of each type may be insufficient, as individuals often visit several facilities on a single trip. Thus, facilities should also be located to accommodate multi-purpose trips.
To address this challenge, we introduce the clustered multimode set covering problem, an extension of the SCP that ensures coverage by multiple facility types while promoting spatial clustering. Specifically, we propose an ILP formulation that forms clusters composed of different facility types, allowing each facility to belong to multiple clusters. By using cluster compactness as a proxy for routing, our approach optimizes facility placement and travel efficiency. Additionally, we develop a branch-and-cut algorithm to solve large scale instances. Experimental results demonstrate the effectiveness of our method in real-world settings.
Keywords
- Location
- Strategic Planning and Management
- Branch and Cut
Status: accepted
Back to the list of papers