EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

1378. Mixed-integer linear programming formulations for the line-based dial-a-ride problem

Invited abstract in session MC-54: Ridehailing & Ridepooling, stream Public Transport Optimization.

Monday, 12:30-14:00
Room: S01 (building: 101)

Authors (first author is the speaker)

1. Marie Schmidt
Institute for Computer Science, University of Würzburg
2. Kendra Reiter
Institute for Computer Science, University of Würzburg
3. Daniela Gaul
OPTANO GmbH
4. Michael Stiglmayr
School of Mathematics and Natural Sciences, University of Wuppertal

Abstract

On trajectories with low demand, scheduled busses are often not efficient. If operated frequently, they may be able to capture a significant fraction of overall demand, but often run with few passengers on board or even empty. If frequencies are decreased, the service becomes inconvenient for passengers, and demand will further decline.
On-demand ridepooling has been proposed as an alternative. However, while high service levels can be achieved if enough capacity is provided, such services are inefficient if demand is not properly pooled or if a significant amount of deadheading occurs.
For this reason, we propose an intermediate solution where services are line-based but not schedule-based. In the line-based dial-a-ride problem (liDARP ) we study the following optimization problem: Given a sequence of stops, a number of vehicles, and a set of stop-to-stop transportation requests with time windows for pickup and delivery, assign services to the vehicles and passengers to the services such that each service visits the stops in the indicated sequence, and passengers are transported from origin stop to destination stop by the service they are assigned to, whilem aximizing a weighted sum of transported requests, km driven, vehicles used, and car km saved.
We compare three MILP formulations of the liDARP, one that encodes assignment of vehicles and passengers to services, one that relies on the 3-index formulation for the general DARP, and one event-based formulation.

Keywords

Status: accepted

Back to the list of papers