The Computational Cost of Feasibility Checking in the Dial-a-Ride Problem (DARP)

Dial-a-Ride Problem (DARP) is one of the shared mobility problems for door-to-door people transportation. In algorithms proposed to tackle the DARP, checking the feasibility of a path is relatively time consuming. This issue has motivated researchers to come up with several methods for dealing with this challenge efficiently. The ۸-step procedure proposed in ۲۰۰۳ is the most popular one, and the approach introduced in ۲۰۱۱, called the Firat procedure, is the one with the least time complexity. As the original Firat procedure has not been proposed for the standard DARP, in this paper, it is discussed in detail how this method is adapted to be used for solving feasibility problems raised in the standard DARP. Moreover, using the benchmark instances for the DARP, the performance of this procedure is compared with the ۸-step procedure in practice. The experimental results indicate that, although the time complexity of the Firat procedure is better than that of the ۸-step scheme, the Firat method does not demonstrate its superiority in practice.

Keywords:

Shared Mobility Systems , Dial-a-Ride Problem (DARP) , Pickup and Delivery Problem with Time Windows (PDPTW) , Shared-Taxi Problem , Feasibility Checking