The dial-a-ride problem (DARP) involves the dispatching of a fleet of vehicles to transport customers requesting service and is one of the most challenging tasks of combinatorial optimization. We study the DARP as a constraint satisfaction problem, where the goal is to find a feasible solution with respect to the time, capacity, and precedence constraints, or to prove infeasibility. The main contribution of our work is a new robust method for this problem formulation. The algorithm is based on a dynamic subroutine that finds for any set of customers a maximum cluster, that is, a maximal set of customers that can be served by a single vehicle. The performance of the algorithm is analyzed and evaluated by means of computational experiments, justifying the efficiency of the solution method.
No takes yet. Share an insight, caveat, or question.
Häme et al. (2014) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: