Exploring the Multi-Objective Dial-A-Ride Problem: An Analysis of Genetic Algorithms and MIP

Exploring the Multi-Objective Dial-A-Ride Problem: An Analysis of Genetic Algorithms and MIP

Elhorst, Wytze (TU Delft Electrical Engineering, Mathematics and Computer Science)

Yorke-Smith, N. (mentor)

Delft University of Technology

Computer Science | Algorithmics

2024-01-05

The Multi-Objective Dial-a-Ride Problem (DARP) poses significant challenges in the field of transportation optimization, requiring the simultaneous optimization of conflicting objectives such as travel costs, emission, and customer ride times. In this research, we analyse two distinct approaches for tackling the Multi-Objective DARP: Mixed-Integer Linear Programming (MIP) solvers and Genetic Algorithms (GAs). Through a series of experiments and performance evaluations on diverse problem instances, we assess the strengths and weaknesses of each method. We compare their efficiency, scalability, and ability to generate Pareto-optimal solutions. Additionally, the study explores the impact of algorithmic variations on the convergence and solution quality of the Genetic Algorithm. The results demonstrate that MIP solvers seem entirely unsuited for the generation of quality Multi-Objective Pareto fronts. Of the Genetic Algorithms, the algorithm extended with our proposed guiding heuristics in its genetic operators, manages to construct the best quality Pareto front, outperforming the other algorithms in both finding the best objective solution values, as well as pareto diversity and convergence. We discuss the practical implications of our findings, offering recommendations for researchers and practitioners in the realm of transportation optimization and emission reduction.

MIP
Pareto front
Genetic Algorithm - GA
DARP
Heuristic

http://resolver.tudelft.nl/uuid:ef76c17e-de7f-42ef-b94a-ba9ccd76640a

Student theses

master thesis

© 2024 Wytze Elhorst