Simple Temporal Problems in Route Scheduling for the Dial-a-Ride Problem with Transfers

International audienceThe Dial-A-Ride Problem (DARP) consists in defining a set of routes that satisfy transportation requests between a set of pickup points and a set of delivery points. This paper addresses a variant of the DARP where requests can change of vehicle during their trip. This transshipment is made on specific locations called "transfer points". The corresponding problem is called the Dial-A-Ride Problem with Transfers (DARPT). Solving the DARPT yields modeling and algorithmic di culties. In this paper, we focus on e ciently checking the feasibility of routes with regards to the problem temporal constraints in a Large Neighborhood Search. This feasibility problem is a Simple Temporal Problem, well studied in particular in Artificial Intelligence. We propose necessary and su cient conditions to fasten the detection of unfeasible or feasible routes