One-to-one pickup and delivery problem with incompatibilities

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

Buenos Aires

Workshop; Workshop in Operations, Networks and Data Analytics; 2018

Universidad Torcuato Di Tella

: In this work we study the one-to-one pickup and delivery problem withincompatibilities (PDPwI), a variant of the well known one-to-one pickup and deliveryproblem (PDP) not yet introduced in the routing literature. We define formally the PDPwIand show that it generalizes the PDP, the vertex coloring problem, the bin packing problemand the bin packing problem with conflicts.We formulate three different integer programming models which are computationallyevaluated through Branch And Cut algorithms on a testbed of instances. Based on thesetests and other considerations, we pick one of the models. We perform a polyhedral studyof the associated polytope, characterize the polyhedron dimension and find several familiesof valid lineal restrictions.Following the mentioned analysis we develop a Branch And Cut algorithm and we improveit by developing a cutting plane algorithm, a primal heuristic and a branching strategy.Finally, we show the effectiveness of those components testing them on a testbed ofinstances.