The Complexity of Counting Turns in the Line-Based Dial-a-Ride Problem
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917448811282432 |
|---|---|
| author | Lauerbach, Antonio Reiter, Kendra Schmidt, Marie |
| author_facet | Lauerbach, Antonio Reiter, Kendra Schmidt, Marie |
| contents | Dial-a-Ride problems have been proposed to model the challenge to consolidate passenger transportation requests with a fleet of shared vehicles. The line-based Dial-a-Ride problem (LiDARP) is a variant where the passengers are transported along a fixed sequence of stops, with the option of taking shortcuts. In this paper we consider the LiDARP with the objective function to maximize the number of transported requests. We investigate the complexity of two optimization problems: the LiDARP, and the problem to determine the minimum number of turns needed in an optimal LiDARP solution, called the MinTurn problem. Based on a number of instance parameters and characteristics, we are able to state the boundary between polynomially solvable and NP-hard instances for both problems. Furthermore, we provide parameterized algorithms that are able to solve both the LiDARP and MinTurn problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_15192 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Complexity of Counting Turns in the Line-Based Dial-a-Ride Problem Lauerbach, Antonio Reiter, Kendra Schmidt, Marie Computational Complexity Dial-a-Ride problems have been proposed to model the challenge to consolidate passenger transportation requests with a fleet of shared vehicles. The line-based Dial-a-Ride problem (LiDARP) is a variant where the passengers are transported along a fixed sequence of stops, with the option of taking shortcuts. In this paper we consider the LiDARP with the objective function to maximize the number of transported requests. We investigate the complexity of two optimization problems: the LiDARP, and the problem to determine the minimum number of turns needed in an optimal LiDARP solution, called the MinTurn problem. Based on a number of instance parameters and characteristics, we are able to state the boundary between polynomially solvable and NP-hard instances for both problems. Furthermore, we provide parameterized algorithms that are able to solve both the LiDARP and MinTurn problem. |
| title | The Complexity of Counting Turns in the Line-Based Dial-a-Ride Problem |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2409.15192 |