Presenter: Kathrin Klamroth, University of Wuppertal

Link to personal website: https://www.opt.uni-wuppertal.de/en/people/detail/klamroth/

Title: The Dial-a-Ride Problem:
New Formulations, Efficient Solution Methods, and a Multi-objective Perspective

Host: Sune Lauth Gadegaard

Short abstract:

Ridepooling services play an increasingly important role in modern transportation systems. With soaring demand and growing fleet sizes, the underlying route planning problems become increasingly challenging. In this context, we consider the dial-a-ride problem (DARP): Given a set of transportation requests with pick-up and delivery locations, passenger numbers, time windows, and maximum ride times, an optimal routing for a fleet of vehicles, including an optimized passenger assignment, needs to be determined. We present a tight mixed-integer linear programming (MILP) formulations for the DARP by combining two state-of-the-art models into new location-augmented-event-based formulations. We discuss its theoretical properties and its numerical performance as compared to purely location-based or event-based models.

DARP solutions have 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), and possibly other optimization goals. Interestingly, these objectives represent the conflicting goals of the different stakeholders, i.e., the service provider and the customers. To better reflect theses trade-offs, we discuss a multi-objective variant of DARP and present numerical results illustrating the trade-off between cost efficiency and customer satisfaction.

Organisers: Surabhi Verma and Hartanto Wong