Variable Neighborhood Search for the Multi-Depot Multiple Set Orienteering Problem
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914914738634752 |
|---|---|
| author | Kant, Ravi Shahid, Salmaan Bhat, Anuvind Mishra, Abhishek |
| author_facet | Kant, Ravi Shahid, Salmaan Bhat, Anuvind Mishra, Abhishek |
| contents | This paper introduces a variant of the Set Orienteering Problem (SOP), the multi-Depot multiple Set Orienteering Problem (mDmSOP). It generalizes the SOP by grouping nodes into mutually exclusive sets (clusters) with associated profits. Profit can be earned if any node within the set is visited. Multiple travelers, denoted by $t$ $(> 1)$, are employed, with each traveler linked to a specific depot. The primary objective of the problem is to maximize profit collection from the sets within a predefined budget. A novel formulation is introduced for the mDmSOP. The paper utilizes the Variable Neighborhood Search (VNS) meta-heuristic to solve the mDmSOP on small, medium, and large instances from the Generalized Traveling Salesman Problem (GTSP) benchmark. The results demonstrate the VNS's superiority in robustness and solution quality, as it requires less computational time than solving the mathematical formulation with GAMS 37.1.0 and CPLEX. Additionally, increasing the number of travelers leads to significant improvements in profits. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_08922 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Variable Neighborhood Search for the Multi-Depot Multiple Set Orienteering Problem Kant, Ravi Shahid, Salmaan Bhat, Anuvind Mishra, Abhishek Optimization and Control This paper introduces a variant of the Set Orienteering Problem (SOP), the multi-Depot multiple Set Orienteering Problem (mDmSOP). It generalizes the SOP by grouping nodes into mutually exclusive sets (clusters) with associated profits. Profit can be earned if any node within the set is visited. Multiple travelers, denoted by $t$ $(> 1)$, are employed, with each traveler linked to a specific depot. The primary objective of the problem is to maximize profit collection from the sets within a predefined budget. A novel formulation is introduced for the mDmSOP. The paper utilizes the Variable Neighborhood Search (VNS) meta-heuristic to solve the mDmSOP on small, medium, and large instances from the Generalized Traveling Salesman Problem (GTSP) benchmark. The results demonstrate the VNS's superiority in robustness and solution quality, as it requires less computational time than solving the mathematical formulation with GAMS 37.1.0 and CPLEX. Additionally, increasing the number of travelers leads to significant improvements in profits. |
| title | Variable Neighborhood Search for the Multi-Depot Multiple Set Orienteering Problem |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2408.08922 |