180. Branch-and-Price for the line-based Dial-a-Ride Problem without Time Windows
Invited abstract in session WB-1: Ridepooling, stream Mobility, Transportation, and Traffic.
Wednesday, 10:45-12:15Room: Audimax
Authors (first author is the speaker)
| 1. | Kendra Reiter
|
| Institute for Computer Science, University of Würzburg | |
| 2. | Marie Schmidt
|
| Institute for Computer Science, University of Würzburg | |
| 3. | Michael Stiglmayr
|
| School of Mathematics and Natural Sciences, University of Wuppertal |
Abstract
The Dial-a-Ride Problem (DARP) is a well-studied optimization problem, concerned with transporting a set of passenger requests, each with an origin, a destination, a load, and time windows denoting the earliest departure or latest arrival. As the DARP is NP-hard, pre-processing steps that eliminate infeasible connections based on tightened time windows are essential for the success of most MILP-based solution methods.
In the line-based Dial-a-Ride Problem (liDARP), we consider a set of bus stations connected by a line, i.e., with a pre-defined ordering, a set of vehicles, and requests traveling between stations. The vehicles may take shortcuts, wait at stations, and turn when empty. Our objective is to balance the environmental benefits (by pooling passengers and reducing driven kilometers), with the service effectiveness measured by the number of passengers transported.
In rural areas, where demand is sparse and travel distances are longer, strict time windows and maximum ride time constraints leave little flexibility to pool requests, reducing the environmental benefits. We consider a liDARP variant without time windows. While this relaxation promises higher pooling rates, it also renders many common solution methods, which use pre-processing steps dependent on tight time windows, ineffective, requiring new algorithmic approaches with competitive running times. Future work may build upon this variant, using the proposed procedures to consider instances with realistic (non-tight) time windows.
Leveraging the underlying line structure, we introduce subroutes, which are tuples encoding the serviced stations between turns. Using subroutes and alternating the driving direction, we develop a Branch-and-Price framework to solve the liDARP without time windows.
Keywords
- Public Transport
- Mobility
- Transportation
Status: accepted
Back to the list of papers