Event-based MILP models for ride pooling applications
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2021
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914887299497984 |
|---|---|
| author | Gaul, Daniela Klamroth, Kathrin Stiglmayr, Michael |
| author_facet | Gaul, Daniela Klamroth, Kathrin Stiglmayr, Michael |
| contents | Ridepooling services require efficient optimization algorithms to simultaneously plan routes and pool users in shared rides. We consider a static dial-a-ride problem (DARP) where a series of origin-destination requests have to be assigned to routes of a fleet of vehicles. Thereby, all requests have associated time windows for pick-up and delivery, and may be denied if they can not be serviced in reasonable time or at reasonable cost. Rather than using a spatial representation of the transportation network we suggest an event-based formulation of the problem, resulting in significantly improved computational times. While the corresponding MILP formulations require more variables than standard models, they have the advantage that capacity, pairing and precedence constraints are handled implicitly. The approach is tested and validated using a standard IP-solver on benchmark data from the literature. Moreover, the impact of, and the trade-off between, different optimization goals is evaluated on a case study in the city of Wuppertal (Germany). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2103_01817 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Event-based MILP models for ride pooling applications Gaul, Daniela Klamroth, Kathrin Stiglmayr, Michael Optimization and Control Ridepooling services require efficient optimization algorithms to simultaneously plan routes and pool users in shared rides. We consider a static dial-a-ride problem (DARP) where a series of origin-destination requests have to be assigned to routes of a fleet of vehicles. Thereby, all requests have associated time windows for pick-up and delivery, and may be denied if they can not be serviced in reasonable time or at reasonable cost. Rather than using a spatial representation of the transportation network we suggest an event-based formulation of the problem, resulting in significantly improved computational times. While the corresponding MILP formulations require more variables than standard models, they have the advantage that capacity, pairing and precedence constraints are handled implicitly. The approach is tested and validated using a standard IP-solver on benchmark data from the literature. Moreover, the impact of, and the trade-off between, different optimization goals is evaluated on a case study in the city of Wuppertal (Germany). |
| title | Event-based MILP models for ride pooling applications |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2103.01817 |