Solving the Line-Based Dial-a-Ride Problem by Generating Stopping Patterns
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917318457556992 |
|---|---|
| author | Lauerbach, Antonio Mallach, Sven Reiter, Kendra Schmidt, Marie Stiglmayr, Michael |
| author_facet | Lauerbach, Antonio Mallach, Sven Reiter, Kendra Schmidt, Marie Stiglmayr, Michael |
| contents | In the line-based dial-a-ride problem (liDARP), vehicles operate along a predefined bus line, with the possibility of skipping stations and turning when empty. Motivated by the practical observation that tight passenger time windows often limit pooling in on-demand services, we introduce a new variant of this transportation system by removing all temporal constraints, which we call the liDARP without TWs. We introduce a new MILP formulation for the liDARP without TWs, which constructs feasible tours as sequences of stopping patterns; first, we consider a fundamental single-vehicle, single-pass special case. Based on our insights, we develop a branch-and-price algorithm where the pricing problem generates profitable stopping patterns. For practical applications, we additionally propose a root node heuristic, using the stopping patterns generated at the root node. Computational experiments show that our branch-and-price algorithm is competitive, finding solutions with a MIP gap of less than 5% for large instances in 60 minutes. Further, the root node heuristic scales to instances with up to 100 requests, outperforming the state-of-the-art and reaching optimality gaps of less than 5% within 15 minutes. This method is highly effective in generating solutions for practical applications, where solving large problems quickly is more valuable than reaching optimality. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_06295 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Solving the Line-Based Dial-a-Ride Problem by Generating Stopping Patterns Lauerbach, Antonio Mallach, Sven Reiter, Kendra Schmidt, Marie Stiglmayr, Michael Optimization and Control In the line-based dial-a-ride problem (liDARP), vehicles operate along a predefined bus line, with the possibility of skipping stations and turning when empty. Motivated by the practical observation that tight passenger time windows often limit pooling in on-demand services, we introduce a new variant of this transportation system by removing all temporal constraints, which we call the liDARP without TWs. We introduce a new MILP formulation for the liDARP without TWs, which constructs feasible tours as sequences of stopping patterns; first, we consider a fundamental single-vehicle, single-pass special case. Based on our insights, we develop a branch-and-price algorithm where the pricing problem generates profitable stopping patterns. For practical applications, we additionally propose a root node heuristic, using the stopping patterns generated at the root node. Computational experiments show that our branch-and-price algorithm is competitive, finding solutions with a MIP gap of less than 5% for large instances in 60 minutes. Further, the root node heuristic scales to instances with up to 100 requests, outperforming the state-of-the-art and reaching optimality gaps of less than 5% within 15 minutes. This method is highly effective in generating solutions for practical applications, where solving large problems quickly is more valuable than reaching optimality. |
| title | Solving the Line-Based Dial-a-Ride Problem by Generating Stopping Patterns |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2603.06295 |