Solving a Bi-Objective Dial-a-Ride Problem Using Multi-Directional Local Search and an Exact Scheduling Procedure

Abstract

A dial-a-ride system is an application of demand-responsive, collective people transportation. Each user requests a trip between an origin and a destination of choice, to which a number of service level requirements are linked. The service provider attempts to develop efficient routing schedules, respecting these service level requirements and the technical constraints of a pickup and delivery problem. The balancing of human and economic perspectives involved in solving such a dial-a-ride problem explains why these systems are particularly useful for organizing quality-oriented, but efficient transportation for users having special needs, such as door-to-door transportation for elderly and disabled. Since demand for dial-a-ride systems is increasing, service providers need efficient planning algorithms to safeguard quality and cost efficiency. Single-objective methods usually minimize operational costs while ensuring a minimum quality level imposed by the service level requirements. This solution technique emphasizes the fundamental nature of the problem by solving a bi-objective dial-a-ride problem with real-life characteristics. Total user ride time, being the total time users spend aboard the vehicles, is explicitly minimized as an additional, quality-oriented objective without making a priori choices regarding the importance of both objectives. To this end, a multi-directional local search (MDLS) metaheuristic is developed, in which a variable neighborhood search (VNS) principle is embedded to perform local search. An exact scheduling procedure is integrated into the metaheuristic framework in order to produce schedules which minimize total user ride time. Although a bi-objective case is considered here, the principle of MDLS allows any number of objectives.