Introducing heterogeneous users and vehicles into models and algorithms for the dial-a-ride problem

Dial-a-ride problems deal with the transportation of people between pickup and delivery locations. Given the fact that people are subject to transportation, constraints related to quality of service are usually present, such as time windows and maximum user ride time limits. In many real world applications, different types of users exist. In the field of patient and disabled people transportation, up to four different transportation modes can be distinguished. In this article we consider staff seats, patient seats, stretchers and wheelchair places. Furthermore, most companies involved in the transportation of the disabled or ill dispose of different types of vehicles. We introduce both aspects into state-of-the-art formulations and branch-and-cut algorithms for the standard dial-a-ride problem. Also a recent metaheuristic method is adapted to this new problem. In addition, a further service quality related issue is analyzed: vehicle waiting time with passengers aboard. Instances with up to 40 requests are solved to optimality. High quality solutions are obtained with the heuristic method.