One-to-one pickup and delivery problem with incompatibilities

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

Ciudad Autónoma de Buenos Aires

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

Universidad Torcuato Dei Tella

In this work we study the one-to-one pickup and delivery problem with incompatibilities (PDPwI), a variant of the well known one-to-one pickup and delivery problem (PDP) not yet introduced in the routing literature.We define formally the PDPwI and show that it generalizes the PDP, the vertex coloring problem, the bin packing problem and the bin packing problem with conflicts.We formulate three different integer programming models which are computationally evaluated through Branch And Cut algorithms on a testbed of instances.Based on these tests and other considerations, we pick one of the models. We perform a polyhedral study of the associated polytope, characterize the polyhedron dimension and find several families of valid lineal restrictions.Following the mentioned analysis we develop a Branch And Cut algorithm and we improve it 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 of instances.