Autor(es)

Pablo Factorovich and Isabel Méndez-Díaz and Paula Zabala

URL Pública

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 …