The Dial-a-Ride Problem with Limited Pickups per Trip

The Dial-a-Ride Problem (DARP) is an optimization problem that involves determining optimal routes and schedules for several vehicles to pick up and deliver items at minimum cost. Motivated by real-world carpooling and crowdshipping scenarios, we introduce an additional constraint imposing a maximum number on the number of pickups per trip. This results in the Dial-a-Ride Problem with Limited Pickups per Trip (DARP-LPT). We apply a fragment-based method for DARP-LPT, where a fragment is a partial path. Specifically, we extend two formulations from Rist and Forbes (2021): the Fragment Flow Formulation (FFF) and the Pickup-Space Fragment Formulation (PSFF). Furthermore, our results show that PSFF outperforms FFF, which in turn surpasses traditional arc-based formulations in both solution quality and computational efficiency. Additionally, we compare several existing fragment sets that differ in the length of their partial paths and find that the sets with shorter partial paths yield the best solution times when used with PSFF. In addition, we propose a new mixed fragment set, which is useful when the sets with longer partial paths become too large. In such cases, it yields the lowest CPU time.