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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Greedy Insertion with Queue-Based Retry and Dynamic Acceptance Control

  • Kamilia Bedhief,
  • Sonia Nasri,
  • Hend Bouziri

摘要

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.