Pickup and delivery problem with incompatibility constraints

The purpose of this paper is to present a new version of the One-to-One Pickup and Delivery Problem in which a single vehicle must comply with requests for transportation from specific collect points to specific delivery points. The problem we consider, besides looking for a minimum cost route, adds extra constraints that forbid some requests to be in the vehicle at the same time. We first begin to formally define the problem and show how it is related to the classic graph coloring problem. Then, we introduce a comparative analysis of the computational performance of three integer programming formulations. Some polyhedral results of the most promising formulation are presented in order to strengthen the LP relaxation for increasing the computational efficacy of the model. We implement separation algorithms, a primal heuristic for finding feasible solutions and a branching strategy. All these elements were considered to the development of a Branch and Cut algorithm which is tested on a comprehensive test bed of instances. The algorithm proves to be capable of overcoming state-of-the-art mixed-integer solvers, both in number of solved instances and computational time. Fil: Factorovich, Pablo Matías. Universidad Nacional de Quilmes. Departamento de Ciencia y Tecnología; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina Fil: Méndez Díaz, Isabel. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación en Ciencias de la Computación. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigación en Ciencias de la Computación; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina