Solving the multi-objective Dial-a-Ride problem without using routing heuristics

Abstract

Door-to-door transportation services are very important for disabled or elderly people, as they have difficulties using regular public transport services. These services work on a on-demand basis and use taxi vehicles that can service multiple jobs at the same time to reduce the operational costs. The problem however is that deciding how to schedule each taxi to pickup and drop-off a customer is very difficult, as there are multiple objectives involved such as operational costs, vehicle efficiency and service quality (which itself is composed of several subobjectives). Since these objectives are related to each other it is very difficult to balance them. Two major decisions in this problem are the clustering (assigning customers to taxis) and routing (computing the driving schedule of each taxi). In this thesis we introduce the Random Insertion Genetic Algorithm (RIGA) that solves both clustering and routing using only a genetic algorithm. We show that this algorithm may outperform other (genetic) algorithms that do rely on a specialized routing procedure.