Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2409.11883 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916399632351232 |
|---|---|
| author | Baldomero-Naranjo, Marta Kalcsics, Jörg Marín, Alfredo Rodríguez-Chía, Antonio M. |
| author_facet | Baldomero-Naranjo, Marta Kalcsics, Jörg Marín, Alfredo Rodríguez-Chía, Antonio M. |
| contents | We study the upgrading version of the maximal covering location problem with edge length modifications on networks. This problem aims at locating p facilities on the vertices (of the network) so as to maximise coverage, considering that the length of the edges can be reduced at a cost, subject to a given budget. Hence, we have to decide on: the optimal location of p facilities and the optimal edge length reductions.
This problem is NP-hard on general graphs. To solve it, we propose three different mixed-integer formulations and a preprocessing phase for fixing variables and removing some of the constraints. Moreover, we strengthen the proposed formulations including valid inequalities. Finally, we compare the three formulations and their corresponding improvements by testing their performance over different datasets. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_11883 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Upgrading edges in the maximal covering location problem Baldomero-Naranjo, Marta Kalcsics, Jörg Marín, Alfredo Rodríguez-Chía, Antonio M. Optimization and Control We study the upgrading version of the maximal covering location problem with edge length modifications on networks. This problem aims at locating p facilities on the vertices (of the network) so as to maximise coverage, considering that the length of the edges can be reduced at a cost, subject to a given budget. Hence, we have to decide on: the optimal location of p facilities and the optimal edge length reductions. This problem is NP-hard on general graphs. To solve it, we propose three different mixed-integer formulations and a preprocessing phase for fixing variables and removing some of the constraints. Moreover, we strengthen the proposed formulations including valid inequalities. Finally, we compare the three formulations and their corresponding improvements by testing their performance over different datasets. |
| title | Upgrading edges in the maximal covering location problem |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2409.11883 |