EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

1178. The Multi-objective 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. Michael Stiglmayr
School of Mathematics and Natural Sciences, University of Wuppertal

Abstract

Ridepooling applications ask for fast computation of vehicle routes and passenger allocations. This so-called dial-a-ride problem (DARP) has to compromise between the efficiency of the ridepooling system (e.g., routing costs) and customer satisfaction (excess ride time and the number of served requests), subject to time window constraints, vehicle load constraints, and maximum ride time constraints. In this talk, we present a multi-objective variant of DARP and investigate the trade-off between the objectives of the service provider and those of the customers.

Moreover, we present a tight mixed-integer linear programming (MILP) formulation for the DARP by combining two state-of-the-art models into a novel location-augmented-event-based formulation. The formulation is tight in the sense that, if time windows shrink to a single point in time, the linear programming relaxation yields integer (and hence optimal) solutions. Strong valid inequalities and lower and upper bounding techniques are derived to further improve the formulation. We then demonstrate the theoretical and computational superiority of the new model: First, we prove that the new formulation has a tighter linear programming relaxation than the two-index formulation. Second, extensive numerical experiments on benchmark instances show that computational times are on average reduced by 49.7% compared to the state-of-the-art event-based approach.

Keywords

Status: accepted

Back to the list of papers