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.
Sohrabi, Somayeh, Ziarati, Koorush, Keshtkaran, Morteza. A linear-time feasibility checking algorithm based on a difference constraints system for the dial-a-ride problem. // Journal of Scheduling. – 2026. – DOI: 10.1007/s10951-026-00891-2. – URL: http://link.springer.com/openurl/fulltext?id=doi:10.1007/s10951-026-00891-2
Sohrabi, Somayeh, Ziarati, Koorush, Keshtkaran, & Morteza (2026). A linear-time feasibility checking algorithm based on a difference constraints system for the dial-a-ride problem. Journal of Scheduling. https://doi.org/10.1007/s10951-026-00891-2
Sohrabi, et al. “A linear-time feasibility checking algorithm based on a difference constraints system for the dial-a-ride problem.” Journal of Scheduling, 2026. doi:10.1007/s10951-026-00891-2.
@article{Sohrabi2026,
title = {A linear-time feasibility checking algorithm based on a difference constraints system for the dial-a-ride problem},
author = {Sohrabi and Somayeh and Ziarati and Koorush and Keshtkaran and Morteza},
journal = {Journal of Scheduling},
year = {2026},
doi = {10.1007/s10951-026-00891-2},
url = {http://link.springer.com/openurl/fulltext?id=doi:10.1007/s10951-026-00891-2}
}
In this paper, we consider cost-sharing problems defined on rooted trees. We refer to these problems as cost-tree problems and to the induced transferable utility cooperative games as irrigation games. We introduce a formal notion of...
In this paper, we focus on nonlinear programming problems with cardinality constraints that restrict the number of nonzero components of the decision vector. We start with a straightforward mixed-integer programming reformulation....
Portfolio selection is a critical issue in financial management under uncertainty. In this paper, we propose a complex approach for portfolio selection with quantile return approximation. In particular, we propose a practical workflow...
The transcendental logarithmic (translog) production function is recognised as a flexible functional form for modelling production processes. It accommodates varying elasticities of input substitution and diverse types of...
This study investigates mothership-drone route determination using two optimization approaches: a Mixed Integer Linear Programming (MILP) model based on a discrete hexagonal grid, and a Mixed Integer Nonlinear Programming (MINLP) model...