Pickup and Delivery Problem with Incompatibility Constraints

PABLO FACTOROVICH; ISABEL MÉNDEZ-DÍAZ; PAULA ZABALA

Villa Mondragone, Frascati

Workshop; 10-th Cologne-Twente Workshop on graphs and combinatorial optimization; 2011

DIA, Università di Roma Tre and DII, Università di Roma Tor Vergata

In the Pickup and Delivery Problem, a vehicle must accomplish a set of requests, each one related to a pickup node preceding a delivery one. In many scenarios, certain goods cannot be on the vehicle simultaneously (e.g. food & detergents). To model them, a variation of PDP can be defined by adding an “incompatibility graph” to be obeyed.In this research we propose four formulations for this problem and we algorithmically compare them. Following these results, we have choose one of the models and, based on it, we have developed a polyhedral study and a Branch and Cut algorithm.