El problema del comprador ambulanteThe traveling purchaser problem

  1. Jorge Riera Ledesma
Supervised by:
  1. Juan José Salazar González Director

Defence university: Universidad de La Laguna

Year of defence: 2002

Department:
  1. Matemáticas, Estadística e Investigación Operativa

Type: Thesis

Abstract

Estudia los diversos métodos de resolución para el problema del comprador ambulante. Una vez analizada la bibliografía existente sobre el tema, se han diseñado dos algoritmos exactos, basados en una metodología denominada Branch-and-Cut, técnica aplicada para los casos simétricos y asimétricos del problema. A estos efectos, se han diseñado dos modelos basados en programación lineal entera mixta, y posteriormente se ha efectuado el estudio poliédrico. De todo lo expuesto nos conduce a dos algoritmos que son evaludados computacionalmente. Se analiza la versión biobjetivo del problema del comprador ambulante, y se introduce una nueva técnica que mejora la eficiencia del algoritmo. Y se propone un algoritmo heurístico basado en una búsqueda local con diferentes tipos de vecindad. La comparación con otros problemas existentes ha posibilitado que hallan podido diseñar una transformación entre el Problema del Comprador Ambulante y el Problema del Viajante de Comercio Generalizado, de tal manera que, mediante un resolutor de este último problema se podría resolver el primero. No obstante, el enorme tamaño del problema transformado hace que sea muy costosa la resolución desde el punto de vista computacional.