A linear-time feasibility checking algorithm based on a difference constraints system for the dial-a-ride problem

Sohrabi, Somayeh, Ziarati, Koorush, Keshtkaran, Morteza
Journal of Scheduling · Springer Nature · 2026-10-21 · DOI: 10.1007/s10951-026-00891-2

Abstract

The Dial-a-Ride Problem (DARP) is a well-known routing problem in the field of shared mobility systems. In this problem, instead of isolated trips, people share their rides. In addition to the operational constraints, the convenience of passengers is a primary concern in the DARP, which leads to a variety of timing restrictions. In this regard, the feasibility checking procedure is an essential component of solving methods for the DARP. In this paper, utilizing a novel shortest path algorithm, a linear-time feasibility checking technique is introduced that takes advantage of difference constraints systems. This method can also be employed to minimize the route duration value and to find the earliest and latest feasible departure times of the nodes in a DARP path with O ( n ) time complexity. Thus, the DCFA could also be used to accelerate procedures in the literature that rely on these timing values. In comparison with some other feasibility checking techniques in the literature, our method is substantially easier to comprehend and implement. Moreover, it outperforms these techniques in terms of time complexity. Beyond this theoretical superiority, experimental results indicate the efficiency of this algorithm in practice, particularly when large DARP paths are considered.

Read at publisher →

Similar articles