Heuristic approaches for solving the dial-a-ride problem with time windows

Abstract

Nowadays, public transport continuously evolves towards more effective solutions to serve the growing demand for mobility. However, some individuals, such as elderly or disabled people, are still unable to use these modes of transportation. Hence, a cost-effective and customized alternative is sought. Such an alternative is the dial-a-ride service, where the customers specify a number of requests for travel, with specified origins and destinations, and optimal routes must be designed based on the available fleet of vehicles. In this dissertation, we provide a clear description of the Dial-A-Ride Problem with Time Windows, where the clients are requesting to be served within a pre-specified time period. Because of the inherent complexity involved in this problem, it is well-known that exact methods fail to provide optimal or near-optimal solutions in a reasonable amount of time. To this end, whenever large instances of the problem are considered, heuristic and metaheuristic techniques must be adopted to guarantee that a good-enough solution can be found promptly. In this study, three approximate methods have been employed, namely, the Large Neighbourhood Search, the Adaptive Large Neighbourhood Search and the Iterated Local Search. An appropriately designed dataset containing 100 real locations has been utilized to illustrate the performance of the algorithms when applied to a fictitious, yet realistic, Dial-A-Ride Problem in Malta.