Greedy Insertion with Queue-Based Retry and Dynamic Acceptance Control
摘要
The Dynamic Dial-a-Ride Problem (D-DARP) concerns the real-time assignment of transportation requests to a limited fleet of vehicles, subject to capacity, time-window, service-time, and ride-time constraints. In this study, we develop an insertion-based heuristic designed to operate under streaming demand conditions. The approach incorporates two key mechanisms: a retry queue that allows deferred reconsideration of temporarily infeasible requests, and a fixed admission control threshold that regulates the proportion of dynamic requests admitted over time. Together, these features ensure that all incoming requests are systematically processed until they are either integrated into a feasible route or permanently rejected. The method is implemented and evaluated on the a-series benchmark instances of Cordeau (2006), which comprise between 16 and 96 pickup–delivery requests. Requests are released sequentially with randomized inter-arrival delays to approximate dynamic demand. Performance evaluation reports the number of accepted requests (direct and after retries), the number of definitive rejections, total travel distance, and CPU execution time. Comparative experiments are also conducted with the hybrid Tabu Search–Constraint Programming method of Berbeglia et al. (2012), one of the few existing approaches tested on the same benchmarks. This positions the proposed heuristic within the literature and provides a baseline for future extensions of dynamic DARP solution methods.