Exploring the Multi-Objective Dial-A-Ride Problem: An Analysis of Genetic Algorithms and MIP
W.J. Elhorst (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Neil Yorke-Smith – Mentor (TU Delft - Algorithmics)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
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.