Un novel esquema de acotamiento dual para la optimización de planes territoriales

Roger Z. Ríos Mercado*, Mónica G. Elizondo Amaya*, Juan A. Díaz**

CIENCIA UANL / AÑO 21, No.90 julio-agosto 2018

https://doi.org/10.29105/cienciauanl21.90-3

RESUMEN

En este trabajo se presenta un esquema de acotamiento dual para el problema de diseño de territorios comerciales. Este problema consiste en encontrar una p-partición de un conjunto de unidades geográficas tal que se minimice una medida de dispersión territorial, sujeto a múltiples restricciones de balance. Las cotas duales son generadas mediante un procedimiento de búsqueda binaria que explora un conjunto de distancias de cobertura. Para cada distancia de cobertura se utiliza de manera efectiva una relajación lagrangiana de un modelo auxiliar de máxima cobertura. La evidencia empírica muestra que el esquema propuesto proporciona mejores cotas que aquéllas obtenidas por la relajación lineal. Hasta donde se conoce, éste es el primer estudio sobre obtención de cotas duales desarrollado para un problema de diseño de territorios comerciales.

Palabras clave: diseño de territorios comerciales; localización discreta; relajación lagrangiana; esquema de acotamiento dual.

ABSTRACT

In this work, we present a dual bounding scheme for a commercial territory design problem. This problem consists of finding a p-partition of a set of geographic units that minimizes a measure of territory dispersion, subject to multiple balance constraints. Dual bounds are obtained using a binary search over a range of coverage distances. For each coverage distance a Lagrangian relaxation of a maximal covering model is used effectively. Empirical evidence shows that the bounding scheme provides tighter lower bounds than those obtained by the linear programming relaxation. To the best of our knowledge, this is the first study about dual bounds ever derived for a commercial territory design problem.

Keywords: comercial territory design, discrete location; lagrangian relaxation; dual bounding scheme.

La investigación operativa (IO) es la rama de las matemáticas que brinda soporte científico a problemas de toma de decisiones. Dentro de sus subáreas, existe una muy importante: la optimización discreta, la cual lidia con problemas de toma de decisiones en las cuales las variables de decisión utilizan únicamente valores enteros o discretos. La mayoría de trabajos de investigación se enfocan, naturalmente, en el desarrollo de métodos de solución para tales problemas. Sin embargo, es bien conocido que gran parte de estos problemas de optimización es sumamente difícil de resolver en el sentido de que cualquier método que pretenda encontrar la solución óptima al problema emplea un tiempo de cómputo que crece, en el peor de los casos, exponencialmente con el tamaño del mismo. Por tanto, surge el campo de los métodos heurísticos, los cuales intentan encontrar soluciones de buena calidad, pero sin garantía de optimalidad global, en tiempos de cómputo razonables. Una limitación en los trabajos de investigación enfocados en desarrollo de heurísticas es que, como precisamente no se sabe dónde están los óptimos globales para los problemas en estudio, resulta imposible evaluar qué tan buena o mala es la calidad de las soluciones reportadas por dichos métodos aproximados.

Esto motiva al nacimiento de otra área de investigación, la del desarrollo de procedimientos de acotación, de suma importancia ya que cuando se desarrolla una buena cota es posible evaluar la calidad de los métodos heurísticos. En el presente trabajo se desarrolla un novel esquema de acotamiento inferior que integra de forma inteligente técnicas y estrategias avanzadas de optimización para abordar un problema importante de optimización combinatoria que surge de un caso práctico en el campo del diseño territorial. El problema en estudio consiste en particionar un conjunto de unidades geográficas (manzanas) en territorios o distritos más pequeños sujeto a varios requerimientos de planificación con el fin de hacer más eficiente su manejo comercial.

El esquema propuesto consiste en realizar una búsqueda binaria sobre un conjunto determinado de radios de cobertura. En cada iteración se considera un dual lagrangiano (Fisher, 1981; 1985; Guignard, 2003) proveniente de un problema auxiliar de cobertura, cuya evaluación determina, mediante un criterio de comparación establecido, si dicho radio es una cota inferior para el problema de diseño territorial.

La metodología desarrollada fue evaluada computacionalmente en diversos conjuntos de instancias del problema. El resultado principal de este trabajo se encuentra en que las cotas proporcionadas por el esquema propuesto son de mucho mejor calidad que las obtenidas por los métodos convencionales existentes, como la relajación lineal y el método exacto de ramificación y acotamiento truncado.

DESCRIPCIÓN DEL PROBLEMA

El diseño de territorios se puede definir como el agrupamiento de pequeñas áreas geográficos llamadas unidades básicas en grupos geográficos más grandes llamados territorios, de manera que éstos sean aceptables respecto a determinados criterios de planificación (Kalcsics, Nickel y Schröder, 2005). En la bibliografía, existen varios estudios sobre problemas de planificación territorial comercial, sin embargo, todos éstos se enfocan en el desarrollo de métodos heurísticos (Ríos-Mercado y Fernández, 2009; Ríos-Mercado y Escalante, 2016; Ríos-Mercado y López-Pérez, 2013; Salazar-Aguilar, Ríos-Mercado y Cabrera-Ríos, 2011; Salazar-Aguilar, Ríos-Mercado y González-Velarde, 2011; Salazar-Aguilar, Ríos-Mercado y González-Ve- larde, 2013; Salazar-Aguilar et al., 2012).

El problema que se aborda en este trabajo proviene de una problemática real en una empresa productora y distribuidora de bebidas embotelladas de la ciudad de Monterrey, N.L., México. La empresa desea dividir el conjunto de puntos de venta distribuidos en toda la ciudad en territorios de acuerdo a criterios económicos y geográficos bien definidos, con el propósito de lograr una mejor administración y abastecimiento de los mismos.

Sea V el conjunto de unidades básicas (UBs), manzanas en este caso. Sea  la medida de actividad a ∈ A = {1, 2} en la UB i, donde a = 1 denota el número de clientes y a = 2 denota la demanda del producto. Una distancia euclidiana  puede calcularse entre cada par de UBs i y j. El conjunto de UBs debe ser dividido en p territorios, de tal modo que cada nodo pertenezca sólo a un territorio (asignación exclusiva). Sea   el tamaño del territorio Vk ⊆V con respecto a la actividad a. En particular, la empresa requiere territorios balanceados con respecto a las dos medidas de actividad asociadas a las unidades básicas (volumen de ventas y número de clientes), con el propósito de equilibrar el trabajo de la gente encargada del abastecimiento de los puntos de venta. Debido a la estructura discreta del problema y a la restricción de asignación exclusiva, es prácticamente imposible tener territorios perfectamente balanceados, es decir, territorios con exactamente el mismo tamaño con respecto a cada medida de actividad. Entonces, con el fin de modelar el balance, se introduce un parámetro de tolerancia τª para cada actividad a. Este parámetro mide la desviación relativa con respecto al tamaño deseado en cada actividad. Este valor deseado está dado por el tamaño promedio μª=wª (V)/p. Finalmente, el objetivo principal es que los grupos formados tengan una forma geográfica compacta, es decir, que las unidades básicas que conforman un territorio se ubiquen relativamente cerca entre sí. Con el fin de lograr esto, en este trabajo se utiliza una función de dispersión basada en el objetivo del problema de p-centro (Kariv y Hakimi, 1979; Minieka, 1996). Se supone que la demanda y el número de clientes se conocen con certeza.

Formalmente, el problema consiste en encontrar una p-partición del conjunto V que cumpla con múltiples restricciones de balance y que minimice una medida de dispersión dada. Cabe aclarar que esta versión del problema no impone requerimientos adicionales de conectividad territorial.

FORMULACIÓN DE PROGRAMACIÓN ENTERA

Para el modelo matemático se introducen las siguientes variables de decisión basadas en centros para modelar el requerimiento de compacidad.

La función objetivo (1) busca minimizar la dispersión territorial (equivalente a maximizar compacidad territorial). Las restricciones (2) aseguran la asignación única de unidades básicas a los territorios. La restricción (3) garantiza la creación de exactamente p territorios. Las restricciones (4)-(5) representan el balance con respecto a cada actividad estableciendo que el tamaño de cada territorio debe estar dentro de un rango de variación (determinado por τª) con respecto al valor promedio (μª). Además, de acuerdo a (5) si no se ubica un centro en i no se pueden asignar unidades básicas a éste. Finalmente, las restricciones (6) definen la naturaleza binaria de las variables de decisión. Este modelo puede ser visto en términos de programación entera como un problema de p-centro con múltiples restricciones de capacidad (5) y restricciones adicionales (4).

Es claro que el problema TDP abordado es NP-duro ya que el problema de p-centro (conocido como NP-duro; Kariv y Hakimi, 1979) es polinomialmente reducible al TDP (tomando el caso especial τª = ∞, a ∈ A).

ESQUEMA DE ACOTAMIENTO DUAL PROPUESTO

El esquema de acotamiento propuesto en este trabajo explota el conocimiento que subyace a una amplia gama de métodos exitosos de solución exacta y aproximada en el área de localización.

En particular, para el problema del p-centro (y sus variaciones) se han propuesto diversos métodos de solución basados en la generación y resolución de una secuencia de problemas auxiliares que mantienen una estrecha relación estructural con el problema de p-centro y aseguran su resolución a optimalidad. En este caso, el uso de un problema auxiliar permite lograr el mismo objetivo a través de formulaciones más simples.

Por tanto, diversas técnicas exitosas de solución exacta para el problema de p-centro se basan en un principio común: ejecutar una búsqueda iterativa sobre un conjunto de distancias de cobertura hasta encontrar el radio más pequeño para el cual la solución óptima asociada al problema auxiliar provee, además, una solución factible para el problema original. Trabajos representativos para el problema de p-centro se encuentran en Minieka (1996), Daskin (1995; 2000) y Elloumi et al. (2004). Para la versión capacitada (CpCP), la cual ha sido menos estudiada, se encuentran los trabajos de Özsoy y Pinar (2006), así como Albareda-Sambola et al. (2010). Dado que el CpCP es una subestructura del modelo TDP que aquí se estudia, en este trabajo se explota el conocimiento generado en Albareda-Sambola et al. (2010) para derivar cotas duales para el problema de diseño de territorios comerciales.

Para introducir el esquema propuesto, destacamos las siguientes observaciones sobre la formulación TDP.

Por lo tanto, el algoritmo se basa en un procedimiento iterativo de búsqueda que intenta encontrar la mejor cota inferior (dual) explorando el conjunto de distancias  . En cada iteración se establece un umbral de distancia para la resolución de un problema asociado de cobertura. Este problema auxiliar permite determinar cuándo no es posible asignar todas las unidades básicas en p o menos territorios dentro de dicho radio de cobertura, proporcionando por lo tanto una cota inferior válida para el valor óptimo de TDP.

A continuación se describe el uso de un problema auxiliar de cobertura en la obtención de cotas inferiores para el TDP.

EL PROBLEMA DE MÁXIMA COBERTURA DE DEMANDA

A partir del TDP, derivamos el problema de máxima cobertura de demanda () como un problema auxiliar que indica si es posible asignar el total de unidades básicas en a lo sumo p territorios dentro de un radio determinado δ. Este problema opera con un umbral de distancia fija δ conocido como radio de cobertura y consiste en maximizar el total de demanda que puede satisfacerse con máximo p territorios. Este problema auxiliar puede verse como una extensión del ampliamente conocido problema de cobertura de conjuntos (MCLP), en el sentido de que incorpora además las restricciones de capacidad (4)-(5).

Para formular el MDCPδ se introduce la siguiente notación adicional:

donde  denota el conjunto de centros territoriales cuya distancia a la unidad j no excede a δ. Análogamente, para un centro territorial dado  denota el conjunto de unidades básicas cuya distancia al centro territorial i no excede el radio δ. Adicionalmente, el parámetro  fortalece el modelo ya que representa un ajuste en el límite superior de las restricciones de balance (5). El problema de máxima cobertura de demanda  se puede formular de la siguiente forma:

La función objetivo (7) maximiza el total de demanda (medida de actividad a = 1, a ∈ A) que puede cubrirse. Las restricciones (8) garantizan que cada unidad básica sea asignada a lo más a un territorio. Las restricciones (10)-(11) conforman las restricciones de balance de los territorios, a las cuales se hace referencia como restricciones de capacidad mínima y máxima de los territorios, respectivamente. En particular, las restricciones (11) garantizan que no se asignen unidades básicas a un territorio que no ha sido seleccionado. Finalmente, la restricción (9) asegura la formación de máximo p territorios. Entonces, el problema de cobertura de demanda consiste en maximizar la demanda de las unidades básicas que puede satisfacerse con un límite de p territorios, dentro de un radio de cobertura δ dado.

La relación que guarda este problema con el TDP es primordial en el entendimiento del esquema de acotamiento propuesto y se detalla a continuación. Sea   la suma de la medida de actividad a=1 (demanda de producto) sobre todas las unidades básicas. Al resolver , se tienen los siguientes casos:

• Caso 1: si para algún k∈K, el total de la demanda que se puede satisfacer dentro de un radio   y p centros territoriales son seleccionados, entonces todas las unidades básicas han sido asignadas y, además, la asignación que resulta del  es una solución factible para el TDP. Por lo tanto, el radio  es una cota superior válida para el TDP.

• Caso 2: la solución óptima para el TDP puede obtenerse mediante el problema auxiliar  al encontrar el radio más pequeño para el cual todas las unidades básicas se pueden asignar (esto es, el índice más pequeño k∈K tal que   y exactamente p centros territoriales son seleccionados. Nótese que una solución óptima para el , , en la cual todas las unidades básicas se asignan a menos de p territorios es posible. Sin embargo, el número de territorios que se requieren para cubrir el total de demanda incrementa si el tamaño del radio de cobertura se reduce. Por lo tanto, siempre puede encontrarse un radio más pequeño  para el cual la solución óptima para el * cubre la demanda total  usando exactamente p territorios (de otro modo, el TDP sería infactible y no tendría solución).

• Caso 3: si para algún k∈K, , entonces no ha sido posible asignar el total de las unidades básicas dentro de tal radio de cobertura y por lo tanto  es una cota inferior válida para el TDP.

Una ventaja en el uso del problema auxiliar  es que su función objetivo W(δ) determina si un radio de cobertura δ es una cota (inferior o superior) o bien el valor óptimo del TDP, dependiendo de la cantidad de unidades básicas que fueron asignadas en la solución óptima del correspondiente .

El  puede verse como el problema estándar de cobertura (MCLP) con restricciones adicionales de capacidad. Dado que el MCLP es NP-duro (Megiddo, Zemel y Hakimi, 1983), se sigue que  es también NP-duro.

Los métodos exactos desarrollados para otras versiones del problema de máxima cobertura no son aplicables al  en primera instancia, a menos que sean adaptados a sus particularidades. Sin embargo, las características reales de las instancias del problema de diseño territorial sobrepasan la capacidad de solución de dichos métodos de solución exacta. Por tal motivo, en su lugar se resuelve una relajación del  para obtener cotas superiores válidas del mismo.

Proposición 1. Sea una cota superior para el , si , entonces el radio de cobertura δ es también una cota inferior válida para el valor óptimo del TDP.

La obtención de cotas superiores del problema de máxima demanda se convierte entonces en una parte importante del esquema de acotamiento para el problema de diseño territorial de interés. Relajar un problema de optimización consiste en transformarlo en otro problema de optimización tal que el valor óptimo de este último es una cota (dual) para el valor óptimo del problema original. Comúnmente estas cotas se pueden obtener por medio de relajaciones lineales y relajaciones lagrangianas. La bibliografía existente acerca esta técnica de relajación es muy amplia. Excelentes tutoriales para este tema pueden encontrarse en los trabajos de Guignard (2003), Geoffrion (1974) y Fisher (1981;1985). Se sabe que las cotas calculadas con una relajación lagrangiana son al menos iguales o mejores que las obtenidas por medio de una relajación lineal. Por tal razón, en la obtención de una cota dual (superior) para el  se utiliza una relajación lagrangiana (véase en Elizondo-Amaya et. al., 2014).

Para un vector de multiplicadores lagrangianos  dado, una cota superior en el valor óptimo del  se obtiene al resolver el problema lagrangiano . Como es bien sabido, la mejor cota lagrangiana y los multiplicadores óptimos asociados se obtienen resolviendo el problema dual lagrangiano

Para resolver el dual lagrangiano LDδ se utiliza un algoritmo general de optimización por subgradiente (Elizondo-Amaya, Ríos-Mercado y Díaz, 2014).

EL ESQUEMA DE ACOTAMIENTO DUAL

En esta sección se describe el procedimiento desarrollado para la obtención de cotas inferiores (duales) para el TDP. La idea que subyace en este procedimiento es llevar a cabo una búsqueda binaria explorando los elementos del conjunto ordenado de distancias  con el propósito de encontrar la mejor cota inferior para el valor óptimo del TDP. El procedimiento resuelve una serie de duales lagrangianos  en busca del máximo radio de cobertura  que satisface las condiciones de la proposición (1), obteniendo así la mejor cota dual del conjunto de radios de cobertura candidatos en .

El conjunto  se puede reducir de manera importante mediante las siguientes pruebas de eliminación.

Eliminación por cota inferior: si LB es una cota inferior para el TDP, entonces el conjunto , donde  es el mayor índice tal que  LB, puede ser descartado.

Eliminación por cota superior: si UB es una cota superior para el TDP, entonces el conjunto, donde  es el menor índice tal que UB, pueden ser descartados.

De esta manera, el conjunto inicial reduce la exploración sobre el nuevo conjunto . Estos principios de reducción impactan significativamente la eficiencia con que opera el algoritmo.

Por tanto, se desarrolla un procedimiento de preproceso, el cual reduce significativamente el esfuerzo computacional de la búsqueda binaria mediante la obtención de cotas inferior y superior iniciales. Aunado a esto, se modifica el criterio de terminación del algoritmo, al utilizar una tolerancia relativa ε para el tamaño del intervalo de búsqueda.

Una cota superior inicial para el TDP se obtiene de aplicar una heurística conocida para el problema de diseño de territorios comerciales. En este caso se aplica la heurística GRASP de Ríos-Mercado y Fernández (2009). El procedimiento para la obtención de una cota inferior inicial se puede encontrar con detalle en Elizondo-Amaya, Ríos-Mercado y Díaz, (2014). El algoritmo de acotamiento dual, denotado en adelante como DBS_P, se resume en el algoritmo 1.

Algoritmo1. DBS_P(P, )

 

EVALUACIÓN DEL MÉTODO Y RESULTADOS

En esta sección se realiza un estudio computacional del esquema de acotamiento dual desarrollado para el TDP. El propósito general de esta fase es medir la calidad y eficiencia del algoritmo. En específico los siguientes puntos son estudiados: (1) una comparación del esquema de acotamiento propuesto con la relajación lineal. (2) La evaluación de la calidad de las cotas del esquema DBS_P al probarse en instancias relativamente medianas, para las cuales se conocen las soluciones óptimas.

Todos los procedimientos desarrollados fueron codificados en el lenguaje C++ y compilados con el compilador de C++ de Sun versión 8.0. La relajación lineal del modelo TDP fue resuelta con CPLEX 11.2. Todos los experimentos fueron realizados en un ordenador SunFire V440 bajo el sistema operativo Solaris 9 en el Laboratorio de Cómputo de Alto Desempeño del Programa de Posgrado en Ingeniería de Sistemas de la Facultad de Ingeniería Mecánica y Eléctrica de la UANL. Se utilizaron instancias generadas aleatoriamente basadas en datos reales provenientes de la compañía. La topología de cada instancia se generó utilizando el generador desarrollado por Ríos-Mercado y Fernández (2009). En este trabajo, los autores usaron información histórica de la compañía y obtuvieron la distribución de los datos asociados al número de clientes y volumen de venta. La topología de cada instancia fue generada aleatoriamente como un grafo planar en el plano [0, 500] × [0, 500]. El conjunto  tiene entonces n² diferentes distancias en el rango [0, 500] en el peor caso. Para todos los experimentos se emplean instancias con una tolerancia de desviación τª=0.05, a ∈ A. En cada experimento se describen las características particulares de las instancias utilizadas.

 

COMPARACIÓN CON LA RELAJACIÓN LINEAL

Se analizan las cotas obtenidas respecto a las proporcionadas por la relajación lineal (LPR) del TDP, la cual consiste en resolver el mismo problema ignorando las restricciones de integralidad de las variables, es decir, permitir que éstas puedan tomar valores continuos.

Se probaron tres conjuntos de 30 instancias con (n, p) ∈ {(500, 10), (1000, 20), (2000, 20)}. Existen diferentes métodos disponibles en CPLEX para la resolución de problemas de programación lineal. Llevamos a cabo un experimento preliminar en el que se encontró que el método de tamizado (Sifting Algorithm) presenta el mejor rendimiento en este caso.

En la tabla I se resumen los resultados de la comparación empírica. En la primera columna se muestra el tamaño de las instancias. La segunda columna muestra la desviación relativa promedio (DR) entre las cotas de los esquemas DBS_P y LPR. En la tercera y cuarta columnas se muestran los tiempos promedio de ejecución obtenidos por cada esquema. Esta desviación representa la mejora relativa de la cota encontrada por el esquema (lb(DBS_P)) con respecto a la cota proporcionada por la relajación lineal (lb(LPR)) y es calculado de la siguiente forma:

 

Como puede apreciarse en primera instancia, los tiempos promedio de cómputo del DBS_P son notablemente mayores respecto a los reportados por la resolución del problema lineal. Sin embargo, se aprecia que este esfuerzo invertido por DBS_P reditúa significativamente al proporcionar cotas de mucha mejor calidad que las reportadas por la relajación lineal. La DR promedio varía de 252.46 a 346.16%, lo cual es considerablemente alto. Esta superioridad en la calidad de las cotas generadas por DBS_P se aprecia mejor en la figura 1 que muestra los valores de ambas cotas para cada una de las 30 instancias probadas en cada tamaño.

COMPARACIÓN CON UNA COTA LPR MEJORADA

Uno de los objetivos que se pretende concretar como resultado del estudio computacional de este esquema de acotamiento es mostrar la valía del mismo. Del experimento anterior se observó que la superioridad en la calidad de la cota del DBS_P está ligada a un mayor esfuerzo computacional. Por lo tanto, en esta prueba se investiga la mejora de la cota obtenida por el esquema LPR cuando ésta se incorpora en un esquema de ramificación y acotamiento (B&B por sus siglas en inglés, Branch and Bound). Como se sabe, el método B&B es uno de los más populares en la solución exacta de problemas de programación entera y consiste en ir mejorando una cota dual y una cota primal del problema de manera que se va acotando el valor de la función objetivo hasta converger al valor óptimo. La idea principal detrás de este experimento es ejecutar el método B&B, permitiendo la misma cantidad de tiempo que el esquema DBS_P tarda en converger, y hacer una comparación entre la cota obtenida por DBS_P y la cota LPR mejorada (ILPR) bajo el mismo esfuerzo computacional.

Este experimento se llevó a cabo en 15 instancias bajo diferentes configuraciones de tamaños (n, p) ∈ {(500, 10), (1000, 20), (2000, 20)}. La tabla II muestra la desviación relativa (calculada de manera similar al experimento anterior) entre ambas cotas obtenidas por ILPR y DBS_P.

El resultado más importante de este experimento fue que para todas las instancias probadas en cada una de las configuraciones de tamaño, el método de ramificación y acotamiento no fue capaz de mejorar significativamente la cota dual obtenida en el nodo raíz, es decir, la relajación lineal. En otras palabras, considerando el mismo tiempo de ejecución para ambas estrategias, el procedimiento de solución exacta no fue capaz de mejorar la cota de la relajación lineal, mientras que el esquema propuesto sigue siendo mejor que la cota ILPR, mostrando desviaciones relativas promedio desde un 255.13 hasta 342.91%, lo cual es en verdad impactante.

En la figura 2 se aprecian las diferencias entre los valores de ambas cotas para cada una de las 30 instancias probadas en cada tamaño.

 

COMPARACIÓN CON SOLUCIONES ÓPTIMAS

Finalmente, se evalúa la calidad de las cotas obtenidas mediante el esquema propuesto con respecto a las soluciones óptimas conocidas para el TDP. Con este fin, se resuelven instancias de 60 y 100 nodos mediante el método exacto B&B implementado por CPLEX. Éste es el máximo tamaño de instancias que puede ser resuelto a optimalidad en tiempos razonables.

La tabla III muestra un resumen de las estadísticas calculadas con base en 20 instancias para cada combinación de tamaño mostrada. Para cada esquema de acotamiento se calcula un intervalo de optimalidad relativa (IOR), la cual nos indica qué tan lejos está la cota encontrada del óptimo global (opt). Este indicador se calcula como Gap = . Como puede verse en la tabla, el esquema DBS_P provee una opción significativamente más atractiva que la relajación lineal, confirmando así los resultados de los experimentos previos. En particular, se observó que 90% de las instancias de 60 nodos tienen intervalos de optimalidad relativa de menos de 10% bajo el esquema propuesto DBS_P. La tabla 3 muestra los valores de las cotas obtenidas por LPR y DBS_P, así como los valores de las soluciones óptimas para cada una de las instancias en cada conjunto de prueba (n, p).

 

CONCLUSIONES

En este trabajo hemos presentado un esquema de acotamiento dual para un problema de diseño territorial. Este problema incluye la compacidad y el equilibrio entre los territorios como los criterios de planificación. En particular, el problema abordado ha sido intratable mediante métodos exactos para el tamaño y características de las instancias reales, por lo tanto, se han propuesto diferentes enfoques heurísticos de solución para este problema. Sin embargo, hasta donde se conoce, no existen trabajos previos en la generación de cotas duales para TDPs en general. Como es bien sabido, la generación de cotas duales es importante para evaluar la calidad de las soluciones reportadas por algoritmos de solución aproximada desarrollados para el problema en estudio. Por otra parte, las cotas duales contribuyen en la construcción de métodos exactos de solución.

El procedimiento propuesto explota las similitudes de las metodologías para la solución del bien conocido problema de p-centro capacitado. En este trabajo hemos ampliado las ideas que subyacen a dichas metodologías y propusimos una adaptación para manejar múltiples restricciones de balance. Las cotas duales para el TDP se obtienen mediante la ejecución de una búsqueda binaria en los elementos de la matriz de distancias entre unidades básicas. En cada iteración del procedimiento se considera la resolución de un problema dual lagrangiano derivado de un problema de cobertura. Esto permite evaluar, para un radio de cobertura dado, si es posible asignar todas las unidades básicas de manera factible en p territorios. Cuando esto no se cumple, el radio explorado se considera una cota inferior para el problema de diseño territorial. Con la finalidad de mejorar los tiempos de ejecución del algoritmo, se calcularon cotas iniciales para reducir el número de radios de cobertura candidatos a ser explorados durante la búsqueda binaria. La evaluación empírica demostró que la cota dual desarrollada para el TDP es de considerablemente mejor calidad que las obtenidas por la relajación lineal del modelo.

Hay varias extensiones a este trabajo que merecen atención. Una de éstas es que resulta interesante el estudio de otros problemas de localización relacionados que se pueden utilizar como problemas auxiliares en el esquema de acotamiento, ya que podrían proporcionar diferentes cotas duales para TDP. Por ejemplo, el problema de cobertura de conjuntos (LSCPδ) el cual busca minimizar el número de territorios que cubren la demanda total sujeta a la asignación de las unidades básicas dentro de un determinado radio de cobertura δ.

Finalmente, una extensión natural que se desprende de este trabajo es la construcción de métodos exactos para el TDP. Una alternativa en la resolución exacta del problema es considerar el uso de las cotas generadas junto a un método de ramificación y acotamiento, estrategia que ha dado muy buenos resultados en diversos problemas de programación entera. Las heurísticas de Lagrange forman también una amplia familia de métodos que funcionan bien en la búsqueda de soluciones para muchos problemas de programación entera.

AGRADECIMIENTOS

Agradecemos las sugerencias de los revisores anónimos. Este trabajo de investigación ha sido apoyado por el Consejo Nacional de Ciencia y Tecnología (apoyo Conacyt CB-2005-01-48499Y y CB-2011-01-166397), y la Universidad Autónoma de Nuevo León a través de su Programa de Apoyo a la Investigación Científica y Tecnológica (apoyo UANL-Paicyt CE012-09, IT51110, y CE728-11).

* Universidad Autónoma de Nuevo León.

** Universidad de Las Américas, Puebla.

Contacto: roger@yalma.fime.uanl.mx

REFERENCIAS

Albareda-Sambola, M., Díaz, J.A., y Fernández, E. (2010). Lagrangean duals and exact solution to the capacitated p-center problem. European Journal of Operational Research. 201(1): 71-81.

Daskin, M.S. (1995). Network and Discrete Location: Models, Algorithms and Applications. Wiley, New York, EUA.

Daskin, M.S. (2000). A new approach to solve the vertex p-center problem to optimality: Algorithm and computational results. Communications of the Operations Research Society of Japan. 45(9): 428-436.

Elizondo-Amaya, M.G., Ríos-Mercado, R.Z., y Díaz, J.A. (2014). A dual bounding scheme for a territory design problem. Computers & Operations Research, 44: 193-205.

Elloumi, S., Labbé, M., y Pochet, Y. (2004). A new formulation and resolution method for the p-center problem. INFORMS Journal on Computing. 16(1): 84-94.

Fisher, M.L. (1981). The Lagrangian relaxation method for solving integer programming problems. Management Science. 27(1): 1-18.

Fisher, M.L. (1985). An applications oriented guide to Lagrangian relaxation. Interfaces. 15(2): 2-21.

Geoffrion, A.M. (1974). Lagrangean relaxation for integer programming. Mathematical Programming Studies. 2: 82-114.

Guignard, M. (2003). Lagrangean relaxation. TOP. 11(2): 151-228.

ILOG, Inc. (2007). ILOG CPLEX 11.0 User’s Manual. Mountain View, EUA.

Kalcsics, J., Nickel, S., y Schröder, M. (2005). Toward a unified territorial design approach: Applications, algorithms, and GIS integration. TOP. 13(1): 1-56.

Kariv, O., y Hakimi, S.L. (1979). An algorithmic approach to network location problems. I: The p-centers. SIAM Journal on Applied Mathematics. 37(3): 513-538.

Megiddo, N., Zemel, E., y Hakimi, S. L. (1983). The maximum coverage location problem. SIAM Journal of Algebraic and Discrete Methods, 4(2): 253-261.

Minieka, E. (1996). The m-center problem. SIAM Re- view. 12(1): 138-139; 1970.

Özsoy, F.A., y Pinar, M.C. (2006). An exact algorithm for the capacitated vertex p-center problem. Computers & Operations Research. 33(5): 1420-1436.

Ríos-Mercado, R.Z., y Fernández, E. (2009). A reactive GRASP for a commercial territory design problem with multiple balancing requirements. Computers & Operations Research. 36(3): 755- 776.

Ríos-Mercado, R. Z., y Escalante, H.J. (2016). GRASP with path relinking for commercial districting. Expert Systems with Applications. 44: 102-113.

Ríos-Mercado, R.Z., y López-Pérez, J.F. (2013). Commercial territory design planning with realignment and disjoint assignment requirements. Omega. 41(3): 525- 535.

Salazar-Aguilar, M.A., Ríos-Mercado, R.Z., y Cabrera-Ríos, M. (2011). New models for commercial territory design. Networks and Spatial Economics. 11(3): 487-507.

Salazar-Aguilar, M.A., Ríos-Mercado, R.Z., y González-Velarde, J.L. (2011). A bi-objective programming model for designing compact and balanced territories in commercial districting. Transportation Research Part C: Emerging Technologies. 19(5): 885-895.

Salazar-Aguilar, M.A., Ríos-Mercado, R.Z., y González-Velarde, J.L. (2013). GRASP strategies for a bi-objective territory design problem. Journal of Heuristics, 19(2): 179-200.

Salazar-Aguilar, M.A., Ríos-Mercado, R.Z., González-Velarde, J.L., et al. (2012). Multiobjective scatter search for a commercial territory design problem. Annals of Operations Research. 199(1): 343-360.

 

RECIBIDO: 25/04/2017

ACEPTADO: 12/04/2018