![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2018\/04\/foto.png\")
<\/a>\u00a0la distancia eucl\u00eddea entre BUs i <\/em>y j<\/em>, con i<\/em>, j <\/em>\u2208 V<\/em>. Para cada BU i<\/em>\u2208V <\/em>hay tres par\u00e1metros o atributos asociados. Sea\u00a0<\/a>\u00a0el valor del atributo a <\/em>en el nodo i<\/em>, donde a <\/em>= 1, 2 y 3, representa el n\u00famero de clientes, demanda de producto y carga de trabajo, respectivamente. El n\u00famero de territorios es conocido y dado por el par\u00e1metro p<\/em>. Una p<\/em>-partici\u00f3n de V <\/em>se denota por X<\/em>=(X<\/em>1,…,X<\/em>p) , donde X<\/em>\u03ba <\/em>\u2282 V <\/em>es un territorio de V<\/em>.\u00a0Sea w<\/em>\u00aa <\/em>(X\u03ba<\/em>\u00a0<\/em>)=\u00a0<\/a>\u00a0el tama\u00f1o del territorio\u00a0 <\/a>\u00a0<\/em>con respecto a la actividad a <\/em>\u2208 A <\/em>= {1, 2, 3}y k <\/em>\u2208 K <\/em>= {1,\u2026,p}. Las restricciones de balance territorial se modelan mediante la introducci\u00f3n de un par\u00e1metro de tolerancia ta aque mide la desviaci\u00f3n relativa permitida de una meta promedio \u03bc\u00aa\u00a0, dada por \u03bc\u00aa\u00a0<\/em>=w\u00aa<\/em>\u00a0<\/em>(V<\/em>)\/ p <\/em>, para cada a<\/em>\u2208 A<\/em>. Otro requerimiento es que todos los nodos asignados a un territorio est\u00e1n conectados por una ruta contenida totalmente en el territorio. Finalmente, se persigue minimizar la dispersi\u00f3n territorial. Sea \u03a0<\/strong> la colecci\u00f3n de todas las p<\/em>-particiones de V<\/em>. El modelo de optimizaci\u00f3n combinatoria (CTDP) est\u00e1 dado por:<\/p>\nEl objetivo (1) mide la dispersi\u00f3n territorial. Las restricciones (2) representan el balance territorial con respecto a cada atributo. Las restricciones (3) garantizan la conectividad territorial, donde G\u03ba<\/i>\u00a0<\/i><\/span>es el grafo inducido en G <\/i>por el conjunto de nodos DESCRIPCI\u00d3N DE LA HEUR\u00cdSTICA<\/b><\/p>\n Como se indic\u00f3 en la secci\u00f3n anterior, todos los m\u00e9todos existentes desarrollados para la distribuci\u00f3n comercial no son aplicables en este caso, dada la naturaleza de la funci\u00f3n objetivo que se optimiza. Es necesario desarrollar software espec\u00edfico.<\/p>\n En esta secci\u00f3n se presenta GPR-CTDP, una heur\u00edstica GRASP con reencadenamiento de trayectorias para el problema en cuesti\u00f3n. GRASP es una metaheur\u00edstica\u00a0bien conocida basada en mecanismos de b\u00fasqueda \u00e1vida y construcci\u00f3n aleatorizada (Feo y Resende, 1995) que se ha utilizado con \u00e9xito para muchos problemas de optimizaci\u00f3n combinatoria, incluyendo CTDP (R\u00edos-Mercado y Fern\u00e1ndez, 2009). Proponemos un GRASP mejorado con reencaminamiento de trayectorias. Naturalmente, se espera que la incorporaci\u00f3n de un mecanismo de b\u00fasqueda sofisticado como PR proporcione soluciones de mucho mejor calidad que las obtenidas mediante la simple b\u00fasqueda local. La heur\u00edstica comprende un nuevo procedimiento de construcci\u00f3n y un mecanismo de PR muy eficaz. El procedimiento de construcci\u00f3n maneja inteligentemente una estrategia para construir territorios simult\u00e1neamente, mientras que el PR nos permite obtener soluciones de mucho mejor calidad que las obtenidas con la b\u00fasqueda local simple. El detalle de los componentes de la heur\u00edstica pueden encontrarse en R\u00edos-Mercado y Escalante (2016).<\/p>\n Reencadenamiento de trayectorias<\/b><\/p>\n El reencadenamiento de trayectorias fue originalmente propuesto por Glover y sus colegas como una forma de incorporar estrategias de intensificaci\u00f3n y diversificaci\u00f3n en la b\u00fasqueda tab\u00fa (Glover, 1996). PR consiste en explorar la trayectoria de las soluciones intermedias entre dos soluciones seleccionadas llamadas\u00a0 En el contexto de GRASP, PR puede ser considerado como una forma de introducir la memoria en el proceso de b\u00fasqueda. Hasta donde sabemos, el PR no se ha utilizado en el contexto del dise\u00f1o de territorios. En este trabajo se consideran dos variantes de PR hacia adelante-y-hacia atr\u00e1s, llamadas est\u00e1tica y din\u00e1mica, que han demostrado ser muy efectivas en problemas relacionados (Resende et al., <\/i>2010).<\/p>\n Las denominadas estrategias de PR hacia adelante-y-hacia atr\u00e1s exploran las rutas entre Esto puede deberse a la codicia de los m\u00e9todos de PR habituales, los cuales evalu\u00e1n todas las posibles soluciones que se pueden generar al hacer un movimiento desde una soluci\u00f3n inicial y elegir el movimiento que da como resultado la mejor soluci\u00f3n intermedia. Por lo tanto, estos m\u00e9todos exploran un gran n\u00famero de soluciones y, por ende, el PR hacia adelante no ayuda a mejorar la calidad de las soluciones. En este trabajo seleccionamos movimientos de tal manera que se eval\u00faa un solo movimiento para generar soluciones intermedias. Esta forma de PR es m\u00e1s eficiente a expensas de sacrificar un poco el beneficio de estrategias \u00e1vidas. Los detalles de la implementaci\u00f3n pueden encontrarse en R\u00edos-Mercado y Escalante (2016).<\/p>\n RESULTADOS COMPUTACIONALES<\/strong><\/p>\n En esta secci\u00f3n se presentan los resultados experimentales obtenidos con GPR-CTDP. El m\u00e9todo propuesto\u00a0fue implementado en MATLAB\u00ae. Todos los experimentos se ejecutaron en una estaci\u00f3n de trabajo de 64\u00a0bits con un procesador Corei7 a 3.4 GHz y 8 GB en\u00a0RAM. Para los experimentos utilizamos la base de datos de R\u00edos-Mercado y Fern\u00e1ndez (2009). Se trata de\u00a0instancias generadas aleatoriamente basadas en datos\u00a0de instancias reales. Los conjuntos de datos DS y DT\u00a0se consideran para la experimentaci\u00f3n. El primer conjunto genera los pesos de las BUs a partir de una distribuci\u00f3n uniforme y el segundo utiliza una distribuci\u00f3n\u00a0triangular. Estos conjuntos de datos se describen completamente en R\u00edos-Mercado y Fern\u00e1ndez (2009). Para\u00a0cada uno de los conjuntos de datos DS y DT hay 20\u00a0instancias diferentes de tama\u00f1o n<\/em> = 500 y p<\/em> = 10. Para\u00a0todas las instancias de los conjuntos de datos usamos\u00a0un nivel \u03c4\u00aa\u00a0= 0.05, a \u2208 \u0391. A lo largo de la evaluaci\u00f3n,\u00a0el GRASP se ejecuta con i<\/em>\u00a0max= 500. Basado en la experimentaci\u00f3n preliminar para calibrar los par\u00e1metros algor\u00edtmicos de GPR-CTDP, se utilizan los valores reportados en la tabla I.<\/p>\n <\/p>\n Evaluaci\u00f3n de los procedimientos de construcci\u00f3n y b\u00fasqueda local dentro del marco de GRASP<\/strong><\/p>\n En esta secci\u00f3n se presentan los resultados de los experimentos dise\u00f1ados para evaluar el efecto de los procedimientos de construcci\u00f3n y b\u00fasqueda local. Para ello se aplica la fase de construcci\u00f3n dentro de un marco GRASP, es decir, no se aplica ninguna fase PR en este experimento. Primero aplicamos el GRASP s\u00f3lo con fase de construcci\u00f3n y luego aplicamos el GRASP completo con fases de construcci\u00f3n y b\u00fasqueda local\u00a0(no PR). Para cada ejecuci\u00f3n probamos los dos conjuntos de datos DT y DS.<\/p>\n La tabla II resume el desempe\u00f1o de los procedimientos de construcci\u00f3n y b\u00fasqueda local en todas las instancias de los conjuntos de datos DT y DS. Para el t\u00e9rmino de dispersi\u00f3n (funci\u00f3n objetivo) F(S)<\/em>, se muestra la desviaci\u00f3n relativa entre la soluci\u00f3n obtenida con cada procedimiento y la mejor soluci\u00f3n conocida para cada instancia, RDB =\u00a0<\/a><\/p>\n<\/a>. N\u00f3tese que hay un n\u00famero exponencial de estas restricciones. El CTDP es NP-duro (R\u00edos-Mercado y Fern\u00e1ndez, 2009).<\/p>\n<\/a>\u00a0y <\/a>\u00a0<\/span>con la hip\u00f3tesis de que algunas de las soluciones intermedias pueden ser mejores que <\/a>\u00a0<\/span>y <\/a>\u00a0<\/span>(intensificaci\u00f3n) o comparables, pero suficientemente diferentes de <\/a>\u00a0<\/span>y <\/a>\u00a0<\/span>(diversificaci\u00f3n). Las soluciones intermedias se generan realizando movimientos desde la soluci\u00f3n inicial <\/a>\u00a0<\/span>hasta la soluci\u00f3n gu\u00eda <\/a>, de tal manera que estos movimientos introducen atributos que est\u00e1n presentes en la soluci\u00f3n gu\u00eda <\/a>.<\/p>\n<\/a>\u00a0<\/span>y <\/a>\u00a0<\/span>de dos maneras diferentes (es decir, de <\/a>\u00a0y <\/a>\u00a0<\/span>y viceversa). El principal beneficio de estas estrategias es que se pueden generar m\u00e1s y diferentes soluciones, aunque se ha encontrado que hay poca ganancia sobre las estrategias unidireccionales (Ribeiro, Uchoa y Werneck, 2002).<\/p>\n<\/a><\/p>\n<\/a>\u00a0La columna etiquetada como \u201cb\u00fasqueda local\u201d indica que ambas fases (construcci\u00f3n y b\u00fasqueda local) son aplicadas. El t\u00e9rmino G(S)<\/em> representa el grado de infactibliad, es decir, mide qu\u00e9 tanto la soluci\u00f3n S<\/em> se desv\u00eda de las restricciones de balance. Un valor G(S)<\/em>=0 significa que no hay violaci\u00f3n a las restricciones, es decir, es factible. De esta tabla podemos apreciar que el promedio de la suma de las infactibilidades relativas se mantiene bajo en el procedimiento de construcci\u00f3n para ambos\u00a0conjuntos de datos. El procedimiento propuesto es capaz de obtener soluciones aceptables en t\u00e9rminos del grado de satisfacci\u00f3n de las restricciones de balance a pesar de que parte del procedimiento de construcci\u00f3n se basa en un criterio puramente de distancia.<\/p>\n