A General Variable Neighborhood Search Approach for the Dynamic Dial-a-Ride Problem

This paper addresses the Dynamic Dial-a-Ride Problem (D-DARP), which arises in ride-sharing systems where transportation requests appear dynamically over time. The objective is to minimize a weighted function that combines total travel cost, passenger ride time, and penalties for unserved requests, aiming to balance operational efficiency and service quality.
To solve the problem, we propose a mathematical programming formulation and a metaheuristic algorithm based on the General Variable Neighborhood Search (GVNS). The algorithm combines a constructive insertion heuristic with a Randomized Variable Neighborhood Descent (RVND) local search, ensuring a balance between intensification and diversification throughout the search process.
Computational experiments were conducted on dynamic benchmark instances generated from the New York City Yellow Taxi dataset. The results indicate that the proposed approach is capable of producing competitive solutions within computational times compatible with dynamic decision-making environments.