Pickup and delivery problem with incompatibility constraints

Abstract

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.