An Improved Tabu Search Heuristic for Static Dial-A-Ride Problem

Dial-A-Ride Problem (DARP) addresses the issue of doorto-door transportation service for the customers with high customer satisfaction. Now-a-days, transportation services have increasing need in our daily life, and it started to directly impact our environment as well as quality of living. According to a study conducted by University of British Columbia, the road pricing or pay-per-use is the most effective way to reduce emissions and traffic [1]. DARP has many applications ranging from taxi services to autonomous cargo and ground operations at the airports. DARP is an extension of pickup and delivery problem under the class of vehicle routing problem (VRP) [2]. It is a combinatorial optimization problem with an objective function to minimise the overall cost while satisfying a specific set of constraints such as time-window, maximum waiting time and maximum ride time to ensure high-quality customer service. In this problem, a set of customers makes a request for pickup and drop-off at certain locations within a predefined time-window. An approach to solve DARP based on dynamic programming has been proposed in [3], in which divide and conquer method is used to solve the problem.