\n
RESUMEN<\/b><\/p>\n
En este trabajo se presenta un esquema de acotamiento dual para el problema de dise\u00f1o de territorios comerciales. Este problema consiste en encontrar una p-<\/i>partici\u00f3n de un conjunto de unidades geogr\u00e1ficas tal que se minimice una medida de dispersi\u00f3n territorial, sujeto a m\u00faltiples restricciones de balance. Las cotas duales son generadas mediante un procedimiento de b\u00fasqueda binaria que explora un conjunto de distancias de cobertura. Para cada distancia de cobertura se utiliza de manera efectiva una relajaci\u00f3n lagrangiana de un modelo auxiliar de m\u00e1xima cobertura. La evidencia emp\u00edrica muestra que el esquema propuesto proporciona mejores cotas que aqu\u00e9llas obtenidas por la relajaci\u00f3n lineal. Hasta donde se conoce, \u00e9ste es el primer estudio sobre obtenci\u00f3n de cotas duales desarrollado para un problema de dise\u00f1o de territorios comerciales.<\/p>\n
Palabras clave: <\/b>dise\u00f1o de territorios comerciales; localizaci\u00f3n discreta; relajaci\u00f3n lagrangiana; esquema de acotamiento dual.<\/p>\n
ABSTRACT<\/b><\/p>\n
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.<\/i><\/p>\n
Keywords: <\/i><\/b>comercial territory design, discrete location; lagrangian relaxation; dual bounding scheme.<\/i><\/p>\n
La investigaci\u00f3n operativa (IO) es la rama de las matem\u00e1ticas que brinda soporte cient\u00edfico a problemas de toma de decisiones. Dentro de sus sub\u00e1reas, existe una muy importante: la optimizaci\u00f3n discreta, la cual lidia con problemas de toma de decisiones en las cuales las variables de decisi\u00f3n utilizan \u00fanicamente valores enteros o discretos. La mayor\u00eda de trabajos de investigaci\u00f3n se enfocan, naturalmente, en el desarrollo de m\u00e9todos de soluci\u00f3n para tales problemas. Sin embargo, es bien conocido que gran parte de estos problemas de optimizaci\u00f3n es sumamente dif\u00edcil de resolver en el sentido de que cualquier m\u00e9todo que pretenda encontrar la soluci\u00f3n \u00f3ptima al problema emplea un tiempo de c\u00f3mputo que crece, en el peor de los casos, exponencialmente con el tama\u00f1o del mismo. Por tanto, surge el campo de los m\u00e9todos heur\u00edsticos, los cuales intentan encontrar soluciones de buena calidad, pero sin garant\u00eda de optimalidad global, en tiempos de c\u00f3mputo razonables. Una limitaci\u00f3n en los trabajos de investigaci\u00f3n enfocados en desarrollo de heur\u00edsticas es que, como precisamente no se sabe d\u00f3nde est\u00e1n los \u00f3ptimos globales para los problemas en estudio, resulta imposible evaluar qu\u00e9 tan buena o mala es la calidad de las soluciones reportadas por dichos m\u00e9todos aproximados.<\/p>\n
Esto motiva al nacimiento de otra \u00e1rea de investigaci\u00f3n, la del desarrollo de procedimientos de acotaci\u00f3n, de suma importancia ya que cuando se desarrolla una buena cota es posible evaluar la calidad de los m\u00e9todos heur\u00edsticos. En el presente trabajo se desarrolla un novel esquema de acotamiento inferior que integra de\u00a0forma inteligente t\u00e9cnicas y estrategias avanzadas de optimizaci\u00f3n para abordar un problema importante de optimizaci\u00f3n combinatoria que surge de un caso pr\u00e1ctico en el campo del dise\u00f1o territorial. El problema en estudio consiste en particionar un conjunto de unidades geogr\u00e1ficas (manzanas) en territorios o distritos m\u00e1s peque\u00f1os sujeto a varios requerimientos de planificaci\u00f3n con el fin de hacer m\u00e1s eficiente su manejo comercial.<\/p>\n
El esquema propuesto consiste en realizar una b\u00fasqueda binaria sobre un conjunto determinado de radios de cobertura. En cada iteraci\u00f3n se considera un dual lagrangiano (Fisher, 1981; 1985; Guignard, 2003) proveniente de un problema auxiliar de cobertura, cuya evaluaci\u00f3n determina, mediante un criterio de comparaci\u00f3n establecido, si dicho radio es una cota inferior para el problema de dise\u00f1o territorial.<\/p>\n
La metodolog\u00eda 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\u00e9todos convencionales existentes, como la relajaci\u00f3n lineal y el m\u00e9todo exacto de ramificaci\u00f3n y acotamiento truncado.<\/p>\n
DESCRIPCI\u00d3N DEL PROBLEMA<\/b><\/p>\n
El dise\u00f1o de territorios se puede definir como el agrupamiento de peque\u00f1as \u00e1reas geogr\u00e1ficos llamadas unidades b\u00e1sicas en grupos geogr\u00e1ficos m\u00e1s grandes llamados territorios, de manera que \u00e9stos sean aceptables respecto a determinados criterios de planificaci\u00f3n (Kalcsics, Nickel y Schr\u00f6der, 2005). En la bibliograf\u00eda, existen varios estudios sobre problemas de planificaci\u00f3n territorial comercial, sin embargo, todos \u00e9stos se enfocan en el desarrollo de m\u00e9todos heur\u00edsticos (R\u00edos-Mercado y Fern\u00e1ndez, 2009; R\u00edos-Mercado y Escalante, 2016; R\u00edos-Mercado y L\u00f3pez-P\u00e9rez, 2013; Salazar-Aguilar, R\u00edos-Mercado y Cabrera-R\u00edos, 2011; Salazar-Aguilar, R\u00edos-Mercado y Gonz\u00e1lez-Velarde, 2011; Salazar-Aguilar, R\u00edos-Mercado y Gonz\u00e1lez-Ve- larde, 2013; Salazar-Aguilar et al.<\/i>, 2012).<\/p>\n
El problema que se aborda en este trabajo proviene de una problem\u00e1tica real en una empresa productora y distribuidora de bebidas embotelladas de la ciudad de Monterrey, N.L., M\u00e9xico. La empresa desea dividir el conjunto de puntos de venta distribuidos en toda la ciudad en territorios de acuerdo a criterios econ\u00f3micos y geogr\u00e1ficos bien definidos, con el prop\u00f3sito de lograr una mejor administraci\u00f3n y abastecimiento de los mismos.<\/p>\n
Sea V <\/i>el conjunto de unidades b\u00e1sicas (UBs), manzanas en este caso. Sea\u00a0 Formalmente, el problema consiste en encontrar una p-<\/i>partici\u00f3n del conjunto V <\/i>que cumpla con m\u00faltiples restricciones de balance y que minimice una medida de dispersi\u00f3n dada. Cabe aclarar que esta versi\u00f3n del problema no impone requerimientos adicionales de conectividad territorial.<\/p>\n FORMULACI\u00d3N DE PROGRAMACI\u00d3N ENTERA<\/b><\/p>\n Para el modelo matem\u00e1tico se introducen las siguientes variables de decisi\u00f3n basadas en centros para modelar el requerimiento de compacidad.<\/p>\n La funci\u00f3n objetivo (1) busca minimizar la dispersi\u00f3n territorial (equivalente a maximizar compacidad territorial). Las restricciones (2) aseguran la asignaci\u00f3n \u00fanica de unidades b\u00e1sicas a los territorios. La restricci\u00f3n (3) garantiza la creaci\u00f3n de exactamente p <\/i>territorios. Las restricciones (4)-(5) representan el balance con respecto a cada actividad estableciendo que el tama\u00f1o de cada territorio debe estar dentro de un rango de variaci\u00f3n (determinado por \u03c4\u00aa) con respecto al valor promedio (\u03bc\u00aa). Adem\u00e1s, de acuerdo a (5) si no se ubica un centro en i <\/i>no se pueden asignar unidades b\u00e1sicas a \u00e9ste. Finalmente, las restricciones (6) definen la naturaleza binaria de las variables de decisi\u00f3n. Este modelo puede ser visto en t\u00e9rminos de programaci\u00f3n entera como un problema de p<\/i>-centro con m\u00faltiples restricciones de capacidad (5) y restricciones adicionales (4).<\/p>\n Es claro que el problema TDP abordado es NP-duro ya que el problema de p<\/i>-centro (conocido como NP-duro; Kariv y Hakimi, 1979) es polinomialmente reducible al TDP (tomando el caso especial \u03c4\u00aa\u00a0<\/i><\/span>= \u221e, a <\/i>\u2208 <\/span>A).<\/p>\n ESQUEMA DE ACOTAMIENTO DUAL PROPUESTO<\/b><\/p>\n El esquema de acotamiento propuesto en este trabajo explota el conocimiento que subyace a una amplia gama de m\u00e9todos exitosos de soluci\u00f3n exacta y aproximada en el \u00e1rea de localizaci\u00f3n.<\/p>\n En particular, para el problema del p-<\/i>centro (y sus variaciones) se han propuesto diversos m\u00e9todos de soluci\u00f3n basados en la generaci\u00f3n y resoluci\u00f3n de una secuencia de problemas auxiliares que mantienen una estrecha relaci\u00f3n estructural con el problema de p-<\/i>centro y aseguran su resoluci\u00f3n a optimalidad. En este caso, el uso de un problema auxiliar permite lograr el mismo objetivo a trav\u00e9s de formulaciones m\u00e1s simples.<\/p>\n Por tanto, diversas t\u00e9cnicas exitosas de soluci\u00f3n exacta para el problema de p-<\/i>centro se basan en un principio com\u00fan: ejecutar una b\u00fasqueda iterativa sobre un conjunto de distancias de cobertura hasta encontrar el radio m\u00e1s peque\u00f1o para el cual la soluci\u00f3n \u00f3ptima asociada al problema auxiliar provee, adem\u00e1s, una soluci\u00f3n factible para el problema original. Trabajos representativos para el problema de p-<\/i>centro se encuentran en Minieka (1996), Daskin (1995; 2000) y Elloumi et al. <\/i>(2004). Para la versi\u00f3n capacitada (Cp<\/i>CP), la cual ha sido menos estudiada, se encuentran los trabajos de \u00d6zsoy y Pinar (2006), as\u00ed como Albareda-Sambola et al. <\/i>(2010). Dado que el Cp<\/i>CP es una subestructura del modelo TDP que aqu\u00ed se estudia, en este trabajo se explota el conocimiento generado en Albareda-Sambola et al. <\/i>(2010) para derivar cotas duales para el problema de dise\u00f1o de territorios comerciales.<\/p>\n Para introducir el esquema propuesto, destacamos las siguientes observaciones sobre la formulaci\u00f3n TDP.<\/p>\n Por lo tanto, el algoritmo se basa en un procedimiento iterativo de b\u00fasqueda que intenta encontrar la mejor cota inferior (dual) explorando el conjunto de distancias A continuaci\u00f3n se describe el uso de un problema auxiliar de cobertura en la obtenci\u00f3n de cotas inferiores para el TDP.<\/p>\n EL PROBLEMA DE M\u00c1XIMA COBERTURA DE DEMANDA<\/b><\/p>\n A partir del TDP, derivamos el problema de m\u00e1xima cobertura de demanda ( Para formular el MDCP\u03b4 <\/span>se introduce la siguiente notaci\u00f3n adicional:<\/p>\n donde La funci\u00f3n objetivo (7) maximiza el total de demanda (medida de actividad a <\/i>= 1, a <\/i>\u2208 <\/span>A) que puede cubrirse. Las restricciones (8) garantizan que cada unidad b\u00e1sica sea asignada a lo m\u00e1s a un territorio. Las restricciones (10)-(11) conforman las restricciones de balance de los territorios, a las cuales se hace referencia como\u00a0restricciones de capacidad m\u00ednima y m\u00e1xima de los territorios, respectivamente. En particular, las restricciones (11) garantizan que no se asignen unidades b\u00e1sicas a un territorio que no ha sido seleccionado. Finalmente, la restricci\u00f3n (9) asegura la formaci\u00f3n de m\u00e1ximo p <\/i>territorios. Entonces, el problema de cobertura de demanda consiste en maximizar la demanda de las unidades b\u00e1sicas que puede satisfacerse con un l\u00edmite de p <\/i>territorios, dentro de un radio de cobertura \u03b4 dado.<\/p>\n La relaci\u00f3n que guarda este problema con el TDP es primordial en el entendimiento del esquema de acotamiento propuesto y se detalla a continuaci\u00f3n. Sea \u00a0 \u2022 Caso 1: si para alg\u00fan k<\/i>\u2208<\/span>K<\/i>, el total de la demanda que se puede satisfacer dentro de un radio \u2022 Caso 2: la soluci\u00f3n \u00f3ptima para el TDP puede obtenerse mediante el problema auxiliar \u2022 Caso 3: si para alg\u00fan k<\/i>\u2208<\/span>K<\/i>, Una ventaja en el uso del problema auxiliar El Los m\u00e9todos exactos desarrollados para otras versiones del problema de m\u00e1xima cobertura no son aplicables al Proposici\u00f3n 1. Sea La obtenci\u00f3n de cotas superiores del problema de m\u00e1xima demanda se convierte entonces en una parte importante del esquema de acotamiento para el problema de dise\u00f1o territorial de inter\u00e9s. Relajar un problema de optimizaci\u00f3n consiste en transformarlo en otro problema de optimizaci\u00f3n tal que el valor \u00f3ptimo de este \u00faltimo es una cota (dual) para el valor \u00f3ptimo del problema original. Com\u00fanmente estas cotas se pueden obtener por medio de relajaciones lineales y relajaciones lagrangianas. La bibliograf\u00eda existente acerca esta t\u00e9cnica de relajaci\u00f3n 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\u00f3n lagrangiana son al menos iguales o mejores que las obtenidas por medio de una relajaci\u00f3n lineal. Por tal raz\u00f3n, en la obtenci\u00f3n de una cota dual (superior) para el Para un vector de multiplicadores lagrangianos Para resolver el dual lagrangiano LD\u03b4 <\/span>se utiliza un algoritmo general de optimizaci\u00f3n por subgradiente (Elizondo-Amaya, R\u00edos-Mercado y D\u00edaz, 2014).<\/p>\n EL ESQUEMA DE ACOTAMIENTO DUAL<\/b><\/p>\n En esta secci\u00f3n se describe el procedimiento desarrollado para la obtenci\u00f3n de cotas inferiores (duales) para el TDP. La idea que subyace en este procedimiento es llevar a cabo una b\u00fasqueda binaria explorando los elementos del conjunto ordenado de distancias El conjunto Eliminaci\u00f3n por cota inferior: si LB es una cota inferior para el TDP, entonces el conjunto Eliminaci\u00f3n por cota superior: si UB es una cota superior para el TDP, entonces el conjunto De esta manera, el conjunto inicial reduce la exploraci\u00f3n sobre el nuevo conjunto Por tanto, se desarrolla un procedimiento de preproceso, el cual reduce significativamente el esfuerzo computacional de la b\u00fasqueda binaria mediante la obtenci\u00f3n de cotas inferior y superior iniciales. Aunado a esto, se modifica el criterio de terminaci\u00f3n del algoritmo, al utilizar una tolerancia relativa \u03b5 para el tama\u00f1o del intervalo de b\u00fasqueda.<\/p>\n Una cota superior inicial para el TDP se obtiene de aplicar una heur\u00edstica conocida para el problema de dise\u00f1o de territorios comerciales. En este caso se aplica la heur\u00edstica GRASP de R\u00edos-Mercado y Fern\u00e1ndez (2009). El procedimiento para la obtenci\u00f3n de una cota inferior inicial se puede encontrar con detalle en Elizondo-Amaya, R\u00edos-Mercado y D\u00edaz, (2014). El algoritmo de acotamiento dual, denotado en adelante como DBS_P, se resume en el algoritmo 1.<\/p>\n Algoritmo1. DBS_P(P, <\/p>\n EVALUACI\u00d3N DEL M\u00c9TODO Y RESULTADOS<\/b><\/p>\n En esta secci\u00f3n se realiza un estudio computacional del esquema de acotamiento dual desarrollado para el TDP. El prop\u00f3sito general de esta fase es medir la calidad y eficiencia del algoritmo. En espec\u00edfico los siguientes puntos son estudiados: (1) una comparaci\u00f3n del esquema de acotamiento propuesto con la relajaci\u00f3n lineal. (2) La evaluaci\u00f3n de la calidad de las cotas del esquema DBS_P al probarse en instancias relativamente medianas, para las cuales se conocen las soluciones \u00f3ptimas.<\/p>\n Todos los procedimientos desarrollados fueron codificados en el lenguaje C++ y compilados con el compilador de C++ de Sun versi\u00f3n 8.0. La relajaci\u00f3n 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\u00f3mputo de Alto Desempe\u00f1o\u00a0del Programa de Posgrado en Ingenier\u00eda de Sistemas de la Facultad de Ingenier\u00eda Mec\u00e1nica y El\u00e9ctrica de la UANL. Se utilizaron instancias generadas aleatoriamente basadas en datos reales provenientes de la compa\u00f1\u00eda. La topolog\u00eda de cada instancia se gener\u00f3 utilizando el generador desarrollado por R\u00edos-Mercado y Fern\u00e1ndez (2009). En este trabajo, los autores usaron informaci\u00f3n hist\u00f3rica de la compa\u00f1\u00eda y obtuvieron la distribuci\u00f3n de los datos asociados al n\u00famero de clientes y volumen de venta. La topolog\u00eda de cada instancia fue generada aleatoriamente como un grafo planar en el plano [0, 500] \u00d7 [0, 500]. El conjunto <\/p>\n COMPARACI\u00d3N CON LA\u00a0<\/b>RELAJACI\u00d3N LINEAL<\/b><\/p>\n Se analizan las cotas obtenidas respecto a las proporcionadas por la relajaci\u00f3n lineal (LPR) del TDP, la cual\u00a0consiste en resolver el mismo problema ignorando las\u00a0restricciones de integralidad de las variables, es decir,\u00a0permitir que \u00e9stas puedan tomar valores continuos.<\/p>\n Se probaron tres conjuntos de 30 instancias con (n, p<\/i>) \u2208 <\/span>{(500, 10), (1000, 20), (2000, 20)}. Existen diferentes m\u00e9todos disponibles en CPLEX para la resoluci\u00f3n de problemas de programaci\u00f3n lineal. Llevamos a cabo un experimento preliminar en el que se encontr\u00f3 que el m\u00e9todo de tamizado (Sifting Algorithm<\/i>) presenta el mejor rendimiento en este caso.<\/p>\n En la tabla I se resumen los resultados de la comparaci\u00f3n emp\u00edrica. En la primera columna se muestra el tama\u00f1o de las instancias. La segunda columna muestra la desviaci\u00f3n 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\u00f3n obtenidos por cada esquema. Esta desviaci\u00f3n representa la mejora relativa de la cota encontrada por el esquema (lb(DBS_P)) con respecto a la cota proporcionada\u00a0por la relajaci\u00f3n lineal (lb(LPR)) y es calculado de la siguiente forma:<\/p>\n <\/p>\n Como puede apreciarse en primera instancia, los tiempos promedio de c\u00f3mputo del DBS_P son notablemente mayores respecto a los reportados por la resoluci\u00f3n del problema lineal. Sin embargo, se aprecia que este esfuerzo invertido por DBS_P redit\u00faa significativamente al proporcionar cotas de mucha mejor calidad que las reportadas por la relajaci\u00f3n lineal. La DR promedio var\u00eda 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\u00f1o.<\/p>\n COMPARACI\u00d3N CON UNA COTA\u00a0<\/b>LPR MEJORADA<\/b><\/p>\n Uno de los objetivos que se pretende concretar como\u00a0resultado del estudio computacional de este esquema\u00a0de acotamiento es mostrar la val\u00eda del mismo. Del experimento anterior se observ\u00f3 que la superioridad en\u00a0la calidad de la cota del DBS_P est\u00e1 ligada a un mayor\u00a0esfuerzo computacional. Por lo tanto, en esta prueba se investiga la mejora de la cota obtenida por el esquema LPR cuando \u00e9sta se incorpora en un esquema de ramificaci\u00f3n y acotamiento (B&B por sus siglas en ingl\u00e9s, Branch and Bound<\/i>). Como se sabe, el m\u00e9todo B&B es uno de los m\u00e1s populares en la soluci\u00f3n exacta de problemas de programaci\u00f3n 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\u00f3n objetivo hasta converger al valor \u00f3ptimo. La idea principal detr\u00e1s de este experimento es ejecutar el m\u00e9todo B&B, permitiendo la misma cantidad de tiempo que el esquema DBS_P tarda en converger, y hacer una comparaci\u00f3n entre la cota obtenida por DBS_P y la cota LPR mejorada (ILPR) bajo el mismo esfuerzo computacional.<\/p>\n Este experimento se llev\u00f3 a cabo en 15 instancias\u00a0bajo diferentes configuraciones de tama\u00f1os (n, p<\/i>) \u2208 <\/span>{(500, 10), (1000, 20), (2000, 20)}. La tabla II muestra la desviaci\u00f3n relativa (calculada de manera similar al experimento anterior) entre ambas cotas obtenidas por ILPR y DBS_P.<\/p>\n El resultado m\u00e1s importante de este experimento fue que para todas las instancias probadas en cada una de las configuraciones de tama\u00f1o, el m\u00e9todo de ramificaci\u00f3n y acotamiento no fue capaz de mejorar significativamente la cota dual obtenida en el nodo ra\u00edz, es decir, la relajaci\u00f3n lineal. En otras palabras, considerando el mismo tiempo de ejecuci\u00f3n para ambas estrategias, el procedimiento de soluci\u00f3n exacta no fue capaz de mejorar la cota de la relajaci\u00f3n 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.<\/p>\n 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\u00f1o. <\/p>\n COMPARACI\u00d3N CON SOLUCIONES \u00d3PTIMAS<\/b><\/p>\n Finalmente, se eval\u00faa la calidad de las cotas obtenidas mediante el esquema propuesto con respecto a las soluciones \u00f3ptimas conocidas para el TDP. Con este fin, se resuelven instancias de 60 y 100 nodos mediante el m\u00e9todo exacto B&B implementado por CPLEX. \u00c9ste es el m\u00e1ximo tama\u00f1o de instancias que puede ser resuelto a optimalidad en tiempos razonables.<\/p>\n La tabla III muestra un resumen de las estad\u00edsticas calculadas con base en 20 instancias para cada combinaci\u00f3n de tama\u00f1o mostrada. Para cada esquema de acotamiento se calcula un intervalo de optimalidad relativa (IOR), la cual nos indica qu\u00e9 tan lejos est\u00e1 la cota\u00a0encontrada del \u00f3ptimo global (opt<\/i>). Este indicador se calcula como Gap = <\/p>\n CONCLUSIONES<\/b><\/p>\n En este trabajo hemos presentado un esquema de acotamiento dual para un problema de dise\u00f1o territorial. Este problema incluye la compacidad y el equilibrio entre los territorios como los criterios de planificaci\u00f3n. En particular, el problema abordado ha sido intratable mediante m\u00e9todos exactos para el tama\u00f1o y caracter\u00edsticas de las instancias reales, por lo tanto, se han propuesto diferentes enfoques heur\u00edsticos de soluci\u00f3n para este problema. Sin embargo, hasta donde se conoce, no existen trabajos previos en la generaci\u00f3n de cotas duales para TDPs en general. Como es bien sabido, la generaci\u00f3n de cotas duales es importante para evaluar la calidad de las soluciones reportadas por algoritmos de soluci\u00f3n aproximada desarrollados para el problema en estudio. Por otra parte, las cotas duales contribuyen en la construcci\u00f3n de m\u00e9todos exactos de soluci\u00f3n.<\/p>\n El procedimiento propuesto explota las similitudes de las metodolog\u00edas para la soluci\u00f3n del bien conocido problema de p-<\/i>centro capacitado. En este trabajo hemos ampliado las ideas que subyacen a dichas metodolog\u00edas y propusimos una adaptaci\u00f3n para manejar m\u00faltiples restricciones de balance. Las cotas duales para el TDP se obtienen mediante la ejecuci\u00f3n de una b\u00fasqueda binaria en los elementos de la matriz de distancias entre unidades b\u00e1sicas. En cada iteraci\u00f3n del procedimiento se considera la resoluci\u00f3n 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\u00e1sicas de manera factible en p <\/i>territorios. Cuando esto no se cumple, el radio explorado se considera una cota inferior para el problema de dise\u00f1o territorial. Con la finalidad de mejorar los tiempos de ejecuci\u00f3n del algoritmo, se calcularon cotas iniciales para reducir el n\u00famero de radios de cobertura candidatos a ser explorados durante la b\u00fasqueda binaria. La evaluaci\u00f3n emp\u00edrica demostr\u00f3 que la cota dual desarrollada para el TDP es de considerablemente mejor calidad que las obtenidas por la relajaci\u00f3n lineal del modelo.<\/p>\n Hay varias extensiones a este trabajo que merecen atenci\u00f3n. Una de \u00e9stas es que resulta interesante el estudio de otros problemas de localizaci\u00f3n relacionados que se pueden utilizar como problemas auxiliares en el esquema de acotamiento, ya que podr\u00edan proporcionar diferentes cotas duales para TDP. Por ejemplo, el problema de cobertura de conjuntos (LSCP\u03b4<\/span>) el cual busca minimizar el n\u00famero de territorios que cubren la demanda total sujeta a la asignaci\u00f3n de las unidades b\u00e1sicas dentro de un determinado radio de cobertura \u03b4.<\/p>\n Finalmente, una extensi\u00f3n natural que se desprende de este trabajo es la construcci\u00f3n de m\u00e9todos exactos para el TDP. Una alternativa en la resoluci\u00f3n exacta del problema es considerar el uso de las cotas generadas junto a un m\u00e9todo de ramificaci\u00f3n y acotamiento, estrategia que ha dado muy buenos resultados en diversos problemas de programaci\u00f3n entera. Las heur\u00edsticas de Lagrange forman tambi\u00e9n una amplia familia de m\u00e9todos que funcionan bien en la b\u00fasqueda de soluciones para muchos problemas de programaci\u00f3n entera.<\/p>\n AGRADECIMIENTOS<\/b><\/p>\n Agradecemos las sugerencias de los revisores an\u00f3nimos. Este trabajo de investigaci\u00f3n ha sido apoyado por el Consejo Nacional de Ciencia y Tecnolog\u00eda (apoyo Conacyt CB-2005-01-48499Y y CB-2011-01-166397), y la Universidad Aut\u00f3noma de Nuevo Le\u00f3n a trav\u00e9s de su Programa de Apoyo a la Investigaci\u00f3n Cient\u00edfica y Tecnol\u00f3gica (apoyo UANL-Paicyt CE012-09, IT51110, y CE728-11).<\/p>\n * Universidad Aut\u00f3noma de Nuevo Le\u00f3n.<\/p>\n ** Universidad de Las Am\u00e9ricas, Puebla.<\/p>\n Contacto: roger@yalma.fime.uanl.mx<\/p>\n REFERENCIAS<\/b><\/p>\n Albareda-Sambola, M., D\u00edaz, J.A., y Fern\u00e1ndez, E. (2010). Lagrangean duals and exact solution to the capacitated p-center problem. European Journal of Operational Research. <\/i>201(1): 71-81.<\/p>\n Daskin, M.S. (1995). Network and Discrete Location<\/i>: Models, Algorithms and Applications. <\/i>Wiley, New York, EUA.<\/p>\n Daskin, M.S. (2000). A new approach to solve the vertex p-<\/i>center problem to optimality: Algorithm and computational results. Communications of the Operations Research Society of Japan. <\/i>45(9): 428-436.<\/p>\n Elizondo-Amaya, M.G., R\u00edos-Mercado, R.Z., y D\u00edaz, J.A. (2014). A dual bounding scheme for a territory design problem. Computers & Operations Research<\/i>, 44: 193-205.<\/p>\n Elloumi, S., Labb\u00e9, M., y Pochet, Y. (2004). A new formulation and resolution method for the p-<\/i>center problem. INFORMS Journal on Computing<\/i>. 16(1): 84-94.<\/p>\n Fisher, M.L. (1981). The Lagrangian relaxation method for solving integer programming problems. Management Science. <\/i>27(1): 1-18.<\/p>\n Fisher, M.L. (1985). An applications oriented guide to Lagrangian relaxation. Interfaces. <\/i>15(2): 2-21.<\/p>\n Geoffrion, A.M. (1974). Lagrangean relaxation for integer programming. Mathematical Programming Studies. <\/i>2: 82-114.<\/p>\n Guignard, M. (2003). Lagrangean relaxation. TOP. 11(2): 151-228.<\/p>\n ILOG, Inc. (2007). ILOG CPLEX 11.0 User\u2019s Manual. <\/i>Mountain View, EUA.<\/p>\n Kalcsics, J., Nickel, S., y Schr\u00f6der, M. (2005). Toward a unified territorial design approach: Applications, algorithms, and GIS integration. TOP. <\/i>13(1): 1-56.<\/p>\n Kariv, O., y Hakimi, S.L. (1979). An algorithmic approach to network location problems. I: The p-centers. SIAM Journal on Applied Mathematics. <\/i>37(3): 513-538.<\/p>\n Megiddo, N., Zemel, E., y Hakimi, S. L. (1983). The maximum coverage location problem. SIAM Journal of Algebraic and Discrete Methods, <\/i>4(2): 253-261.<\/p>\n Minieka, E. (1996). The m-center problem. SIAM Re- view. 12(1): 138-139; 1970.<\/p>\n \u00d6zsoy, F.A., y Pinar, M.C. (2006). An exact algorithm for the capacitated vertex p-center problem. Computers & Operations Research. <\/i>33(5): 1420-1436.<\/p>\n R\u00edos-Mercado, R.Z., y Fern\u00e1ndez, E. (2009). A reactive GRASP for a commercial territory design problem with multiple balancing requirements. Computers & Operations Research<\/i>. 36(3): 755- 776.<\/p>\n R\u00edos-Mercado, R. Z., y Escalante, H.J. (2016). GRASP with path relinking for commercial districting. Expert Systems with Applications. <\/i>44: 102-113.<\/p>\n R\u00edos-Mercado, R.Z., y L\u00f3pez-P\u00e9rez, J.F. (2013). Commercial territory design planning with realignment and disjoint assignment requirements. Omega. <\/i>41(3): 525- 535.<\/p>\n Salazar-Aguilar, M.A., R\u00edos-Mercado, R.Z., y Cabrera-R\u00edos, M. (2011). New models for commercial territory design. Networks and Spatial Economics. <\/i>11(3): 487-507.<\/p>\n Salazar-Aguilar, M.A., R\u00edos-Mercado, R.Z., y Gonz\u00e1lez-Velarde, J.L. (2011). A bi-objective programming model for designing compact and balanced territories in commercial districting. Transportation Research Part C: Emerging Technologies<\/i>. 19(5): 885-895.<\/p>\n Salazar-Aguilar, M.A., R\u00edos-Mercado, R.Z., y Gonz\u00e1lez-Velarde, J.L. (2013). GRASP strategies for a bi-objective territory design problem. Journal of Heuristics<\/i>, 19(2): 179-200.<\/p>\n Salazar-Aguilar, M.A., R\u00edos-Mercado, R.Z., Gonz\u00e1lez-Velarde, J.L., et al. <\/i>(2012). Multiobjective scatter search for a commercial territory design problem. Annals of Operations Research<\/i>. 199(1): 343-360.<\/p>\n <\/p>\n RECIBIDO: 25\/04\/2017<\/i><\/p>\n ACEPTADO: 12\/04\/2018<\/i><\/p>\n <\/p>\n","protected":false},"excerpt":{"rendered":" Roger Z. R\u00edos Mercado*, M\u00f3nica\u00a0G. Elizondo Amaya*, Juan A. D\u00edaz** CIENCIA UANL \/ A\u00d1O 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\u00f1o de territorios comerciales. Este problema consiste en encontrar una p-partici\u00f3n de un conjunto de unidades geogr\u00e1ficas tal que se minimice una medida de dispersi\u00f3n territorial, […]<\/p>\n","protected":false},"author":4,"featured_media":8036,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[27],"tags":[],"class_list":["post-7983","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-investigacion"],"_links":{"self":[{"href":"https:\/\/cienciauanl.uanl.mx\/index.php?rest_route=\/wp\/v2\/posts\/7983","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/cienciauanl.uanl.mx\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/cienciauanl.uanl.mx\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/cienciauanl.uanl.mx\/index.php?rest_route=\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/cienciauanl.uanl.mx\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=7983"}],"version-history":[{"count":7,"href":"https:\/\/cienciauanl.uanl.mx\/index.php?rest_route=\/wp\/v2\/posts\/7983\/revisions"}],"predecessor-version":[{"id":8053,"href":"https:\/\/cienciauanl.uanl.mx\/index.php?rest_route=\/wp\/v2\/posts\/7983\/revisions\/8053"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/cienciauanl.uanl.mx\/index.php?rest_route=\/wp\/v2\/media\/8036"}],"wp:attachment":[{"href":"https:\/\/cienciauanl.uanl.mx\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=7983"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/cienciauanl.uanl.mx\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=7983"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/cienciauanl.uanl.mx\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=7983"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/04\/w-e1532535806968.png\")
<\/a>\u00a0la medida de actividad a <\/i>\u2208 <\/span>A = {1, 2} en la UB i<\/i>, donde a <\/i>= 1 denota el n\u00famero de clientes y a <\/i>= 2 denota la demanda del producto. Una distancia euclidiana\u00a0![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/04\/foto.png\")
<\/a>\u00a0puede calcularse entre cada par de UBs i <\/i>y j<\/i>. El conjunto de UBs debe ser dividido en p <\/i>territorios, de tal modo que cada nodo pertenezca s\u00f3lo a un territorio (asignaci\u00f3n exclusiva). Sea\u00a0![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/Wa-e1532536174439.png\")
<\/a>\u00a0![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/04\/wia-e1524594439886.png\")
<\/a>\u00a0<\/i><\/span>el tama\u00f1o del territorio V<\/i>k \u2286<\/i><\/span>V <\/i>con respecto a la actividad a<\/i>. En particular, la empresa requiere territorios balanceados con respecto a las dos medidas de actividad asociadas a las unidades b\u00e1sicas (volumen de ventas y n\u00famero de clientes), con el prop\u00f3sito 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\u00f3n de asignaci\u00f3n exclusiva, es pr\u00e1cticamente imposible tener territorios perfectamente balanceados, es decir, territorios con exactamente el mismo tama\u00f1o con respecto a cada medida de actividad. Entonces, con el fin de modelar el balance, se introduce un par\u00e1metro de tolerancia \u03c4\u00aa<\/span>\u00a0<\/i><\/span>para cada actividad a<\/i>. Este par\u00e1metro mide la desviaci\u00f3n relativa con respecto al tama\u00f1o deseado en cada actividad. Este valor deseado est\u00e1 dado por el tama\u00f1o promedio \u03bc\u00aa=w\u00aa<\/i>\u00a0<\/i><\/span>(V<\/i>)\/p<\/i>. Finalmente, el objetivo principal es que los grupos formados tengan una forma geogr\u00e1fica compacta<\/i>, es decir, que las unidades b\u00e1sicas que conforman un territorio se ubiquen relativamente cerca entre s\u00ed. Con el fin de lograr esto, en este trabajo se utiliza una funci\u00f3n de dispersi\u00f3n basada en el objetivo del problema de p-<\/i>centro (Kariv y Hakimi, 1979; Minieka, 1996). Se supone que la demanda y el n\u00famero de clientes se conocen con certeza.<\/p>\n![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/formula1-e1532536547705.png\")
<\/a><\/p>\n![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/parrafo-e1532538651698.png\")
<\/a><\/p>\n![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/D-e1532633271903.png\")
<\/a>\u00a0<\/i>. En cada iteraci\u00f3n se establece un umbral de distancia para la resoluci\u00f3n de un problema asociado de cobertura. Este problema auxiliar permite determinar cu\u00e1ndo no es posible asignar todas las unidades b\u00e1sicas en p <\/i>o menos territorios dentro de dicho radio de cobertura, proporcionando por lo tanto una cota inferior v\u00e1lida para el valor \u00f3ptimo de TDP.<\/p>\n![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/MDCP-e1532540995850.png\")
<\/a>) como un problema auxiliar que indica si es posible asignar el total de unidades b\u00e1sicas en a lo sumo p <\/i>territorios dentro de un radio determinado \u03b4. Este problema opera con un umbral de distancia fija \u03b4 conocido como radio de cobertura y consiste en maximizar el total de demanda que puede satisfacerse con m\u00e1ximo p <\/i>territorios. Este problema auxiliar puede verse como una extensi\u00f3n del ampliamente conocido problema de cobertura de conjuntos (MCLP), en el sentido de que incorpora adem\u00e1s las restricciones de capacidad (4)-(5).<\/p>\n![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/formula2-e1532548444391.png\")
<\/a><\/p>\n![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/ij-e1532540765424.png\")
<\/a>\u00a0denota el conjunto de centros territoriales cuya distancia a la unidad j <\/i>no excede a \u03b4. An\u00e1logamente, para un centro territorial dado ![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/iji-e1532540796770.png\")
<\/a>\u00a0denota el conjunto de unidades b\u00e1sicas cuya distancia al centro territorial i no excede el radio \u03b4. Adicionalmente, el par\u00e1metro\u00a0![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/bi-e1532540875709.png\")
<\/a>\u00a0fortalece el modelo ya que representa un ajuste en el l\u00edmite superior de las restricciones de balance (5). El problema de m\u00e1xima cobertura de demanda <\/a>\u00a0<\/span>se puede formular de la siguiente forma:<\/p>\n![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/formula3-e1532548399569.png\")
<\/a><\/p>\n![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/wtot-e1532627217507.png\")
<\/a>\u00a0<\/span>la suma de la medida de actividad a<\/i>=1 (demanda de producto) sobre todas las unidades b\u00e1sicas. Al resolver <\/a>, se tienen los siguientes casos:<\/p>\n![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/dk--e1532627693854.png\")
<\/a>\u00a0![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/dk-e1532627540653.png\")
<\/a><\/i><\/span>\u00a0<\/i><\/span>y p <\/i>centros territoriales son seleccionados, entonces todas las unidades b\u00e1sicas han sido asignadas y, adem\u00e1s, la asignaci\u00f3n que resulta del <\/a>\u00a0<\/span>es una soluci\u00f3n factible para el TDP. Por lo tanto, el radio <\/a>\u00a0<\/i><\/span>es una cota superior v\u00e1lida para el TDP.<\/p>\n<\/a>\u00a0<\/span>al encontrar el radio m\u00e1s peque\u00f1o para el cual todas las unidades b\u00e1sicas se pueden asignar (esto es, el \u00edndice m\u00e1s peque\u00f1o k<\/i>\u2208<\/span>K <\/i>tal que ![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/wd-e1532627865163.png\")
<\/a>\u00a0\u00a0<\/span>y exactamente p <\/i>centros territoriales son seleccionados. N\u00f3tese que una soluci\u00f3n \u00f3ptima para el <\/a>, ![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/SED-e1532631309931.png\")
<\/a>, en la cual todas las unidades b\u00e1sicas se asignan a menos de p <\/i>territorios es posible. Sin embargo, el n\u00famero de territorios que se requieren para cubrir el total de demanda incrementa si el tama\u00f1o del radio de cobertura se reduce. Por lo tanto, siempre puede encontrarse un radio m\u00e1s peque\u00f1o ![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/SED-1-e1532631563152.png\")
<\/a>\u00a0para el cual la soluci\u00f3n \u00f3ptima para el <\/a>*\u00a0<\/span>cubre la demanda total ![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/wt-e1532631743162.png\")
<\/a>\u00a0<\/span>usando exactamente p <\/i>territorios (de otro modo, el TDP ser\u00eda infactible y no tendr\u00eda soluci\u00f3n).<\/p>\n![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/wdk-e1532631939936.png\")
<\/a>, entonces no ha sido posible asignar el total de las unidades b\u00e1sicas dentro de tal radio de cobertura y por lo tanto <\/a>\u00a0<\/i><\/span>es una cota inferior v\u00e1lida para el TDP.<\/p>\n<\/a>\u00a0<\/span>es que su funci\u00f3n objetivo W<\/i>(\u03b4<\/i>) determina si un radio de cobertura \u03b4 es una cota (inferior o superior) o bien el valor \u00f3ptimo del TDP, dependiendo de la cantidad de\u00a0unidades b\u00e1sicas que fueron asignadas en la soluci\u00f3n \u00f3ptima del correspondiente <\/a>.<\/p>\n<\/a>\u00a0<\/span>puede verse como el problema est\u00e1ndar de cobertura (MCLP) con restricciones adicionales de capacidad. Dado que el MCLP es NP-duro (Megiddo, Zemel y Hakimi, 1983), se sigue que <\/a>\u00a0<\/span>es tambi\u00e9n NP-duro.<\/p>\n<\/a>\u00a0<\/span>en primera instancia, a menos que sean adaptados a sus particularidades. Sin embargo, las caracter\u00edsticas reales de las instancias del problema de dise\u00f1o territorial sobrepasan la capacidad de soluci\u00f3n de dichos m\u00e9todos de soluci\u00f3n exacta. Por tal motivo, en su lugar se resuelve una relajaci\u00f3n del <\/a>\u00a0<\/span>para obtener cotas superiores v\u00e1lidas del mismo.<\/p>\n![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/WS-e1532632354808.png\")
<\/a> una cota superior para el <\/a>, si ![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/WStot-e1532632421788.png\")
<\/a>, entonces el radio de cobertura \u03b4 es tambi\u00e9n una cota inferior v\u00e1lida para el valor \u00f3ptimo del TDP.<\/i><\/p>\n<\/a>\u00a0<\/span>se utiliza una relajaci\u00f3n lagrangiana (v\u00e9ase en Elizondo-Amaya et. al., <\/i>2014).<\/p>\n![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/ER-e1532632613857.png\")
<\/a>\u00a0dado, una cota superior en el valor \u00f3ptimo del <\/a>\u00a0<\/span>se obtiene al resolver el problema lagrangiano ![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/Ls-e1532632734601.png\")
<\/a>. Como es bien sabido, la mejor cota lagrangiana y los multiplicadores \u00f3ptimos asociados se obtienen resolviendo el problema dual lagrangiano<\/p>\n![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/formula4-1-e1532632826670.png\")
<\/a><\/p>\n![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/formula5-e1532632853438.png\")
<\/a><\/p>\n<\/a>\u00a0<\/i>con el prop\u00f3sito de encontrar la mejor cota inferior para el valor \u00f3ptimo del TDP. El procedimiento resuelve una serie de duales lagrangianos ![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/Wdk-e1532633369383.png\")
<\/a>\u00a0en busca del m\u00e1ximo radio de cobertura ![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/dk--e1532633007513.png\")
<\/a>\u00a0<\/i><\/span>que satisface las condiciones de la proposici\u00f3n (1), obteniendo as\u00ed la mejor cota dual del conjunto de radios de cobertura candidatos en <\/a>.<\/p>\n<\/a>\u00a0<\/i>se puede reducir de manera importante mediante las siguientes pruebas de eliminaci\u00f3n.<\/p>\n![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/ddd-e1532633600520.png\")
<\/a>, donde ![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/KlEK-e1532633650420.png\")
<\/a>\u00a0<\/i>es el mayor \u00edndice tal que ![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/dkl-e1532633699516.png\")
<\/a>\u00a0LB, puede ser descartado.<\/p>\n![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/dku-e1532634298822.png\")
<\/a>![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/dkmax-e1532634342161.png\")
<\/a>, donde ![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/KuEK-e1532634403722.png\")
<\/a>\u00a0<\/i>es el menor \u00edndice tal que ![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/dku-1-e1532634621530.png\")
<\/a>UB,\u00a0pueden ser descartados.<\/p>\n![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/dkldkl-e1532634673662.png\")
<\/a>. Estos principios de reducci\u00f3n impactan significativamente la eficiencia con que opera el algoritmo.<\/p>\n<\/a>)![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/formula6-e1532634878507.png\")
<\/a><\/p>\n<\/a>\u00a0<\/i>tiene entonces n\u00b2\u00a0<\/span>diferentes distancias en el rango [0, 500] en el peor caso. Para todos los experimentos se emplean instancias con una tolerancia de desviaci\u00f3n \u03c4\u00aa=0.05, a <\/i>\u2208 <\/span>A<\/i>. En cada experimento se describen las caracter\u00edsticas particulares de las instancias utilizadas.<\/p>\n![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/figura1-2-e1532635262766.png\")
<\/a><\/p>\n![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/formula7-e1532698360928.png\")
<\/a><\/p>\n![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/tabla1-2-e1532701301877.png\")
<\/a><\/p>\n![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/tabla2-2-e1532698612403.png\")
<\/a><\/p>\n![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/figura2-2-e1532698736157.png\")
<\/a><\/p>\n![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/100-e1532698996137.png\")
<\/a>. Como puede verse en la tabla, el esquema DBS_P provee una opci\u00f3n significativamente m\u00e1s atractiva que la relajaci\u00f3n lineal, confirmando as\u00ed los resultados de los experimentos previos. En particular, se observ\u00f3 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\u00ed como los valores de las soluciones \u00f3ptimas para cada una de las instancias en cada conjunto de prueba (n<\/i>, p<\/i>).![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/07\/tabla3-2-e1532699052436.png\")
<\/a><\/p>\n