Feasibility algorithms for two pickup and delivery problems with transfers

International audienceThis presentation follows the PhD thesis of Renaud Masson [1] on the Pickup and Delivery Problem with Transfers (PDPT). The motivating application is a dial-a-ride problem in which a passenger may be transferred from the vehicle that picked him/her up to another vehicle at some predetermined location, called transfer point. Both the PDPT and the Dial-A-Ride Problem with Transfers (DARPT) were investigated. An adaptive large neighborhood search has been developed to solve the PDPT [2] and also adapted to the DARPT [3]. In both algorithms, multiple insertions of requests in routes are tested. E ciently evaluating their feasibility with respect to the temporal constraints of the problem is a key issue