Conference Agenda

The dial-a-ride problem involves planning routes for a fleet of vehicles to pool passengers, based on ride requests that specify an origin, destination, and an arrival time window. The electric dial-a-ride problem also incorporates scheduling charging activities to ensure vehicles remain operational. Traditional deterministic approaches often plan conservatively for worst-case scenarios or lack robustness by only accounting for expected energy consumption. To address these limitations, we introduce a two-stage stochastic model with recourse for the electric dial-a-ride problem in this work. Our model leverages real-time data on the state of charge, permitting adjustments to the planned charging time if deviations in energy consumption occur. We also develop an extension of the event-based graph, the so-called event-energy graph, which encodes energy consumption information. This graph features separate layers for each energy level, where events are connected by energy-feasible arcs. Furthermore, we propose an adaptive large neighborhood search algorithm to solve benchmark instances of the electric dial-a-ride problem. We assess the effectiveness of our approach across different ride-pooling systems employing various battery electric vehicles.

Efficient public transport is key to the sustainable mobility transformation, especially in rural areas where traditional line-based bus services struggle due to the sparse demand. Therefore, innovative on-demand buses, with flexible routes and schedules, present a practical solution for improving rural mobility. Public transport providers aim to maximize the number of served passengers with these on-demand buses but operate within limited resources, leading to challenging decisions on accepting or rejecting passenger requests. Moreover, the dynamic booking process requires an immediate decision without knowing the impact of the request on potential future requests. Therefore, the problem of predicting the request fit for dynamic passenger-maximizing dial-a-ride problems (PM-DARPs) emerges.

To address this problem, we introduce the request fit predictor (RFP) framework. Within this framework, we model the request fit as a binary classification task and learn the fit with supervised machine learning models, having perfect information about historical requests. The RFP combines the request fit learned from static PM-DARPs with dynamic components of the cheapest insertion to guarantee feasibility, integrate request prescience, and facilitate an immediate acceptance/rejection decision.

The RFP is tested on real-life data from a German public transport provider and serves 26.19% more passengers than the current business practice. Compared to the cheapest insertion, the RFP not only serves 7.48% more passengers but also covers 6.68% less distance. In the presentation, we will discuss the trade-offs of the RFP’s performance KPIs and give further insights into the framework’s fairness and adaptability.

What if we use existing infrastructure to establish new mobility concepts? The well-established schedule-based bus system relies on fixed routes and fixed bus stops in its operation, offering high predictability even when there are high variations in demand. This concept is rivaled by on-demand systems, which offer very high flexibility with little predictability. We bridge the gap between the two systems with the line-based dial-a-ride problem (liDARP), where vehicles travel along a pre-defined sequence of bus stations, with the flexibility of taking shortcuts, waiting at stations, or turning if no passenger is on board. Service promises ensure operational quality to encourage users to utilize our system.

We propose three Mixed-Integer formulations to model the liDARP. The first employs flexible sublines, where sequences of sublines driving in opposite directions transport passengers between bus stations. The second is based on the classical 3-index DARP formulation, where a specifically constructed graph network ensures all directional constraints are met. The last model is an event-based formulation, where nodes represent events and arcs the transition between them, adapted to meet our specific problem constraints. We examine our formulations in diverse operational contexts, additionally comparing the efficiency of a classic DARP formulation and a schedule-based bus.