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

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.