A Branch-and-Cut Algorithm for the Deliveryman Problem

MÉNDEZ-DÍAZ, ISABEL; ZABALA, PAULA; LUCENA, ABILIO

Paris

Conferencia; V ALIO/EURO Conference on Combinatorial Optimization; 2005

Asociación Latino-Iberoamericana de Investigación Operativa y Association of European Operational Re

In a previous work, we introduced a new integer programming model to TDP. We also presented results of a cutting plane algorithm that uses a number of valid inequalities derived from the polytope of feasible solutions associated with that formulation. The good quality computational results motivated the implementation of the branch-and-cut algorithm presented here. In this study, different aspects of our implementation are presented. In particular, we describe, among others, preprocessing algorithms, branching strategies, cutting plane schemes and primal heuristics. We evaluate the performance of our branchand-cut algorithm on randomly generated instances and compare it with the TDP model. From the results obtained, we conclude that the proposed algorithm is competitive with the best in the literature.