UN PROBLEMA DE WEBER CON UNA FUNCIÓN DE COSTOS CONTINUA POR PARTES

Abstract

Este trabajo analiza la localización de un centro de distribución en un área urbana usando el problemasingle-source de Weber con costos fijos por partes y continuos para encontrar la localización óptima global.El costo fijo es caracterizado por medio de un método de interpolación de Kriging. Para hacer el costo fijotratable, aproximamos esta interpolación con una función por partes y continua que sea convexa en cadaparte, a través del uso la triangulación de Delaunay. Presentamos tres propuestas de solución para el problema:un método de descomposición, un método cónico de descomposición y una reformulación monolíticacónica para resolver a optimalidad el problema de localización de una única instalación considerando unafunción de costos fijos por partes y continuos. A pesar que este enfoque continuo no garantiza la localizaciónóptima global factible, permite delimitar una zona donde se puede intensificar la búsqueda de puntosfactibles.Para las instancias que fueron testeadas, los resultados computacionales muestran que el enfoquecontinuo encuentra una mejor localización que el enfoque discreto en el 23;25% de las instancias y que elmétodo de descomposición es el mejor, en términos de tiempo CPU, con un speedup promedio de 7.98xy 7.72x sobre el método de descompisición cónica y la reformulación monolítica cónica, respectivamente.Además, se presenta una comparación entre dos métodos de solución para el problema deWeber sin considerarlos costos fijos, donde los resultados computacionales muestran que es mejor el algoritmo de Weiszfeldpor sobre una reformulación cónica.

This paper analyze the location of a distribution center in an urban area using a single-source Weberproblem with continuous piecewise fixed cost to find a global optimal location. The fixed cost is characterizedby a Kriging interpolation method and, to make the fixed cost tractable, we approximate this interpolationwith a continuous piecewise function that is convex in each piece, using Delaunay triangulation.We present a decomposition formulation, a decomposition conic formulation and a conic logarithmic disaggregatedconvex combination model to optimally solve the single-source Weber problem with continuouspiecewise fixed cost. Although our continuous approach does not guarantee the global feasible optimal location,it allow us to delimit a zone where we can intensify the search of feasible points.For instances we tested, computational results show that our continuous approach found better locationsthan the discrete approach in 23;25% of the instances and that the decomposition formulation is thebest one, in terms of CPU time.