Solving the Dial-a-Ride Problem Using an Adapted Genetic Algorithm

The dial-a-ride problem (DARP) deals with the transportation of people from source to destination locations. One of the most common use cases is in the transportation of elderly or sick people, and as such it represents an important problem to consider. Since DARP is NP-hard, it most often has to be solved using various heuristic methods. Previous studies demonstrated that metaheuristics are suitable for solving this kind of problem. However, in most cases, basic metaheuristics have been considered without any adaptation to the problem, which could potentially limit their performance. Therefore, in this study a GA is proposed and several of its elements adapted for solving DARP. The obtained results show that the proposed algorithm can achieve better results than similar methods from previous studies. Moreover, the experiments demonstrate that the results can be improved by considering some constraints as soft constraints and including them in the cost function to give the algorithm more flexibility in the search.