A Multi-Directional Local Search Metaheuristic for a Bi-Objective Dial-a-Ride Problem

Abstract

A dial-a-ride system is an application of demand-dependent, 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 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 (DARP) 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 generally increasing, service providers need efficient planning algorithms to safeguard quality and cost efficiency. The objective of this paper is to solve a bi-objective problem variant in which the conflicting interests of users and service providers are both incorporated as an objective. Contrary to single-objective methods, which usually minimize operational costs while ensuring a minimum quality level imposed by the service level requirements, the fundamental nature of the DARP is emphasized by explicitly minimizing user inconvenience. To this end, a multi-directional local search (MDLS) metaheuristic is developed, in which a variable neighborhood search (VNS) framework is embedded to guide the local search part. Initially, this metaheuristic is applied on a problem having standard characteristics, but its applicability can be extended by incorporating additional real-life features.