A Set Cover Mapping Heuristic for Demand-Robust Fleet Size Vehicle Routing Problem with Time Windows and Compatibility Constraints
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911914146136064 |
|---|---|
| author | Makansi, Jordan |
| author_facet | Makansi, Jordan |
| contents | We study the demand-robust fleet size vehicle routing problem with time windows and compatibility constraints. Unlike traditional robust optimization, which considers uncertainty in the data, demand-robust optimization considers uncertainty in which constraints must be satisfied. This paper is the first to solve a practical demand-robust optimization problem at large scale. We present an MILP formulation and also propose a heuristic that maps the problem to set cover in polynomial time. We show that under modest assumptions the relative difference in time complexity from a standard branch-and-bound algorithm to the proposed heuristic scales exponentially with the size of the problem. We evaluate our heuristic using a simulation case study on the Solomon benchmark instances for a variety of practical problem sizes, and compare with Gurobi. The empirical approximation ratio remains below 2.0. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_07719 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Set Cover Mapping Heuristic for Demand-Robust Fleet Size Vehicle Routing Problem with Time Windows and Compatibility Constraints Makansi, Jordan Systems and Control We study the demand-robust fleet size vehicle routing problem with time windows and compatibility constraints. Unlike traditional robust optimization, which considers uncertainty in the data, demand-robust optimization considers uncertainty in which constraints must be satisfied. This paper is the first to solve a practical demand-robust optimization problem at large scale. We present an MILP formulation and also propose a heuristic that maps the problem to set cover in polynomial time. We show that under modest assumptions the relative difference in time complexity from a standard branch-and-bound algorithm to the proposed heuristic scales exponentially with the size of the problem. We evaluate our heuristic using a simulation case study on the Solomon benchmark instances for a variety of practical problem sizes, and compare with Gurobi. The empirical approximation ratio remains below 2.0. |
| title | A Set Cover Mapping Heuristic for Demand-Robust Fleet Size Vehicle Routing Problem with Time Windows and Compatibility Constraints |
| topic | Systems and Control |
| url | https://arxiv.org/abs/2406.07719 |