Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2408.07602 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909654900015104 |
|---|---|
| author | Zhao, Boshuai Wang, Kai Wei, Wenchao Leus, Roel |
| author_facet | Zhao, Boshuai Wang, Kai Wei, Wenchao Leus, Roel |
| contents | The Dial-a-Ride Problem (DARP) is an optimization problem that involves determining optimal routes and schedules for several vehicles to pick up and deliver items at minimum cost. Motivated by real-world carpooling and crowdshipping scenarios, we introduce an additional constraint imposing a maximum number on the number of pickups per trip. This results in the Dial-a-Ride Problem with Limited Pickups per Trip (DARP-LPT). We apply a fragment-based method for DARP-LPT, where a fragment is a partial path. Specifically, we extend two formulations from Rist & Forbes (2021): the Fragment Flow Formulation (FFF) and the Fragment Assignment Formulation (FAF). We establish FFF's superiority over FAF, both from a theoretical as well as from a computational perspective. Furthermore, our results show that FFF and FAF significantly outperform traditional arc-based formulations in terms of solution quality and time. Additionally, compared to the two existing fragment sets, one with longer partial paths and another with shorter ones, our newly generated fragment sets perform better in terms of solution quality and time when fed into FFF. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_07602 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Dial-a-Ride Problem with Limited Pickups per Trip Zhao, Boshuai Wang, Kai Wei, Wenchao Leus, Roel Theoretical Economics The Dial-a-Ride Problem (DARP) is an optimization problem that involves determining optimal routes and schedules for several vehicles to pick up and deliver items at minimum cost. Motivated by real-world carpooling and crowdshipping scenarios, we introduce an additional constraint imposing a maximum number on the number of pickups per trip. This results in the Dial-a-Ride Problem with Limited Pickups per Trip (DARP-LPT). We apply a fragment-based method for DARP-LPT, where a fragment is a partial path. Specifically, we extend two formulations from Rist & Forbes (2021): the Fragment Flow Formulation (FFF) and the Fragment Assignment Formulation (FAF). We establish FFF's superiority over FAF, both from a theoretical as well as from a computational perspective. Furthermore, our results show that FFF and FAF significantly outperform traditional arc-based formulations in terms of solution quality and time. Additionally, compared to the two existing fragment sets, one with longer partial paths and another with shorter ones, our newly generated fragment sets perform better in terms of solution quality and time when fed into FFF. |
| title | The Dial-a-Ride Problem with Limited Pickups per Trip |
| topic | Theoretical Economics |
| url | https://arxiv.org/abs/2408.07602 |