Pickup & Delivery with Time Windows and Transfers: combining decomposition with metaheuristics
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910927874424832 |
|---|---|
| author | Avgerinos, Ioannis Mourtos, Ioannis Tsompanidis, Nikolaos Zois, Georgios |
| author_facet | Avgerinos, Ioannis Mourtos, Ioannis Tsompanidis, Nikolaos Zois, Georgios |
| contents | This paper examines the generalisation of the Pickup and Delivery Problem that allows mid-route load exchanges among vehicles and obeys strict time-windows at all locations. We propose a novel Logic-Based Benders Decomposition (LBBD) that improves optimality gaps for all benchmarks in the literature and scales up to handle larger ones. To tackle even larger instances, we introduce a refined Large Neighborhood Search (LNS) algorithm that improves the adaptability of LNS beyond case-specific configurations appearing in related literature.
To bridge the gap in benchmark availability, we develop an instance generator that allows for extensive experimentation. For moderate datasets (25 and 50 requests), we evaluate the performance of both LBBD and LNS, the former being able to close the gap and the latter capable of providing near-optimal solutions. For larger instances (75 and 100 requests), we recreate indicative state-of-the-art metaheuristics to highlight the improvements introduced by our LNS refinements, while establishing its scalability. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_02158 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Pickup & Delivery with Time Windows and Transfers: combining decomposition with metaheuristics Avgerinos, Ioannis Mourtos, Ioannis Tsompanidis, Nikolaos Zois, Georgios Optimization and Control Artificial Intelligence This paper examines the generalisation of the Pickup and Delivery Problem that allows mid-route load exchanges among vehicles and obeys strict time-windows at all locations. We propose a novel Logic-Based Benders Decomposition (LBBD) that improves optimality gaps for all benchmarks in the literature and scales up to handle larger ones. To tackle even larger instances, we introduce a refined Large Neighborhood Search (LNS) algorithm that improves the adaptability of LNS beyond case-specific configurations appearing in related literature. To bridge the gap in benchmark availability, we develop an instance generator that allows for extensive experimentation. For moderate datasets (25 and 50 requests), we evaluate the performance of both LBBD and LNS, the former being able to close the gap and the latter capable of providing near-optimal solutions. For larger instances (75 and 100 requests), we recreate indicative state-of-the-art metaheuristics to highlight the improvements introduced by our LNS refinements, while establishing its scalability. |
| title | Pickup & Delivery with Time Windows and Transfers: combining decomposition with metaheuristics |
| topic | Optimization and Control Artificial Intelligence |
| url | https://arxiv.org/abs/2505.02158 |