https:\/\/doi.org\/10.29105\/cienciauanl22.96-5<\/a><\/p>\r\n <\/p>\r\n\r\n\r\n\r\n En este trabajo se aborda un problema de dise\u00f1o territorial motivado por una problem\u00e1tica real en el sector de repartici\u00f3n de bebidas embotelladas.\u00a0\u00a0\u00c9ste es un problema de toma de decisiones donde debe decidirse c\u00f3mo particionar el conjunto de manzanas geogr\u00e1ficas de una ciudad en varios territorios para eficientar las tareas y el servicio proporcionado por la empresa a sus clientes.\u00a0\u00a0El problema se plantea como una cuesti\u00f3n de optimizaci\u00f3n biobjetivo, donde se desea optimizar simult\u00e1neamente dos medidas de desempe\u00f1o: la dispersi\u00f3n territorial y el desbalance territorial respecto a la demanda del producto. El problema est\u00e1 tambi\u00e9n sujeto a restricciones de balance con respecto al n\u00famero de clientes y conectividad territorial.\u00a0\u00a0Para resolver este complejo problema se ha desarrollado e implementado una metaheur\u00edstica multiobjetivo basada en b\u00fasqueda dispersa.\u00a0\u00a0Se presenta una evaluaci\u00f3n computacional donde se demuestra el excelente desempe\u00f1o del m\u00e9todo propuesto, superando incluso a los mejores dos m\u00e9todos conocidos a nivel mundial para problemas de optimizaci\u00f3n multiobjetivo (NSGA-II y SSPMO).<\/p>\r\n\r\n\r\n\r\n Palabras clave: investigaci\u00f3n de operaciones, dise\u00f1o de territorios, optimizaci\u00f3n multiobjetivo, metaheur\u00edsticas.<\/p>\r\n\r\n\r\n\r\n A territory design problem motivated by a real-world application in the bottled beverage distribution industry is addressed in the present research. The problem is categorized as a decision-making problem, where suitable partition of customers or city blocks in a city into territories must be decided, such that companies can provide a better service. The problem was modeled as a bi-objective optimization problem, where two performance responses are simultaneously optimized; (i) territory dispersion and (ii) territory imbalance with respect to product demand.\u00a0\u00a0The problem is subject to balancing with respect to the number of customers and territory connectivity constraints.\u00a0\u00a0To solve the complex problem, a scatter search-based multi-objective metaheuristic method has been developed and implemented.\u00a0\u00a0An empirical assessment showed the performance of the proposed method, outperforming the two most popular methods used worldwide (NSGA-II and SSPMO).<\/em><\/p>\r\n\r\n\r\n\r\n Keywords: operations research, territory design, multi-objective optimization, metaheuristics.<\/em><\/p>\r\n\r\n\r\n\r\n En este trabajo se aborda un problema de dise\u00f1o de territorios comerciales, el cual consiste en dividir un conjunto dado de unidades b\u00e1sicas (UBs) en p grupos llamados territorios, de acuerdo a algunos criterios espec\u00edficos de planeaci\u00f3n.\u00a0\u00a0Se considera una versi\u00f3n biobjetivo del problema, es decir, se optimizan simult\u00e1neamente dos funciones objetivo.\u00a0<\/p>\r\n\r\n\r\n\r\n La versi\u00f3n monoobjetivo de este problema fue introducida por R\u00edos-Mercado y Fern\u00e1ndez (2009). Debido a la complejidad del problema, ellos desarrollaron un procedimiento GRASP (Greedy Randomized Adaptive Search Procedure) reactivo para resolverlo. El procedimiento que propusieron super\u00f3 el m\u00e9todo utilizado en la compa\u00f1\u00eda, tanto en la calidad de la soluci\u00f3n como en el grado de infactibilidad con respecto a los requerimientos de balance. Tambi\u00e9n se han estudiado diferentes versiones monoobjetivo de este problema (L\u00f3pez-P\u00e9rez y R\u00edos-Mercado, 2013; R\u00edos-Mercado y L\u00f3pez-P\u00e9rez, 2013; R\u00edos-Mercado y Escalante, 2016).<\/p>\r\n\r\n\r\n\r\n En relaci\u00f3n a estudios multiobjetivo para otros problemas de distritos, hay algunas pocas aplicaciones, por ejemplo, en distritos pol\u00edticos (Bong y Wang, 2004), distritos escolares\u00a0(Bowerman, Hall y Calamai, et al<\/em>., 1995) y servicios p\u00fablicos (Tavares-Pereira et al<\/em>., 2007). Sin embargo, \u00e9stos son modelos diferentes al que se estudia en este trabajo. Antes de realizar este proyecto, los \u00fanicos trabajos en dise\u00f1o de territorios comerciales multiobjetivo eran los de Salazar-Aguilar et al<\/em>. (2011a; 2013). En el primero, se introdujo el modelo biobjetivo y se propuso un m\u00e9todo mejorado del \u03b5-constraint para encontrar las fronteras \u00f3ptimas de Pareto. Una de las limitaciones de este trabajo es, por supuesto, el tama\u00f1o de las instancias que podr\u00edan ser resueltas de forma exacta. La instancia m\u00e1s grande que se puede tratar con ese m\u00e9todo tiene 150 UBs y seis territorios. En el segundo trabajo se desarrollaron heur\u00edsticas basadas en GRASP para tratar de abordar instancias de gran escala del problema, el desempe\u00f1o de los m\u00e9todos fue relativo. Por tanto, la motivaci\u00f3n del\u00a0 presente trabajo fue el de desarrollar un mejor m\u00e9todo y m\u00e1s efectivo para abordar instancias grandes del problema de dise\u00f1o de territorios comerciales (TDP, por sus siglas en ingl\u00e9s). Para mayor detalle acerca de otras aplicaciones de TDP mono-objetivo, el lector puede referirse al trabajo de Kalcsics y R\u00edos-Mercado (Kalcsics y R\u00edos-Mercado, 2019).<\/p>\r\n\r\n\r\n\r\n En este trabajo se desarroll\u00f3 una metaheur\u00edstica basada en b\u00fasqueda dispersa (SS). El m\u00e9todo de b\u00fasqueda dispersa para dise\u00f1o de territorios multiobjetivo (SSMTDP, por sus siglas en ingl\u00e9s) propuesto en este trabajo fue evaluado en un conjunto de instancias grandes. Los resultados indican que el SSMTDP es capaz de encontrar buenas soluciones que est\u00e1n muy bien distribuidas a lo largo de la frontera eficiente. Incluso si las soluciones iniciales tienen una evaluaci\u00f3n pobre en las funciones objetivo, el m\u00e9todo de combinaci\u00f3n propuesto tiene la habilidad de explorar nuevas regiones en el espacio de b\u00fasqueda y el m\u00e9todo mejorado permite obtener mejores soluciones que est\u00e1n bastante lejos del conjunto inicial. Cuando se compar\u00f3 con el estado del arte de los m\u00e9todos multiobjetivo como el procedimiento de b\u00fasqueda dispersa tab\u00fa para optimizaci\u00f3n multiobjetivo (SSPMO) y el algoritmo gen\u00e9tico de clasificaci\u00f3n no-dominada (NSGA-II), se encontr\u00f3 que estos procedimientos se esforzaron bastante para generar soluciones factibles del problema. Se observ\u00f3 que pocas instancias pueden ser resueltas con estos procedimientos. En contraste, el SSMTDP report\u00f3 soluciones significativamente mejores para aquellas instancias resueltas tanto por SSPMO como por NSGA-II.<\/p>\r\n\r\n\r\n\r\n Dado un conjunto V de manzanas (unidades b\u00e1sicas, UBs), la compa\u00f1\u00eda desea dividir este conjunto en un n\u00famero fijo (p) de territorios disjuntos satisfaciendo algunos criterios de planeaci\u00f3n como balance, conexidad y compacidad. Se requiere\u00a0el balance en los territorios para asegurar una mejor distribuci\u00f3n de la carga de trabajo. La conexidad garantiza la movilidad dentro de los territorios, es decir que, cada territorio tiene que estar conectado de tal forma que se pueda llegar a cada unidad b\u00e1sica desde cualquier otra sin salir del territorio. La compacidad del territorio se requiere para garantizar que los clientes dentro del territorio est\u00e9n relativamente cerca unos de otros. La compa\u00f1\u00eda identifica a la compacidad y el balance respecto al n\u00famero de clientes como los criterios m\u00e1s importantes. Por tanto, en el presente trabajo estos criterios son considerados como funciones objetivo y los criterios restantes se tratan como restricciones.<\/p>\r\n\r\n\r\n\r\n Sea G<\/em> = (V,E<\/em>), donde E<\/em> es el conjunto de aristas que representan la adyacencia entre UBs. Una arista e<\/em> \u03f5 E<\/em> conectando a los nodos i<\/em> y j<\/em> existe si i<\/em> y j<\/em> son UBs adyacentes. A cada nodo j<\/em> \u03f5 V<\/em> se le asocian m\u00faltiples atributos como coordenadas geogr\u00e1ficas (c<\/em>j<\/sub>x<\/sup>, c<\/em>j<\/sub>y<\/sup>), n\u00famero de clientes y volumen de ventas. Espec\u00edficamente, la compa\u00f1\u00eda desea un balance perfecto entre los territorios, es decir, cada territorio debe contar con la misma cantidad de clientes y el mismo volumen de ventas. Sea K<\/em> el conjunto de \u00edndices de territorios tal que |K<\/em>|=p. Sea A = {1,2} el conjunto de actividades nodales, donde 1 es el n\u00famero de clientes y 2 el volumen de ventas. Definimos el tama\u00f1o del territorio X<\/em>K<\/em><\/sub> con respecto a la actividad a como w<\/em>(a)<\/sup>(X<\/em>k<\/em><\/sub>) = \u2211i\u03f5X<\/em>K<\/em><\/sub>w<\/em>i<\/sub>(a)<\/sup>, donde w<\/em>i<\/em><\/sub>(a)<\/sup>\u00a0 es el valor asociado a la actividad a<\/em> \u03f5 A<\/em> en el nodo i <\/em>\u03f5 V<\/em>. El valor promedio (deseado) est\u00e1 dado por \u00b5<\/em>(a)<\/sup>= \u2211i\u03f5X<\/em>K<\/em><\/sub>w<\/em>i<\/sub>(a)<\/sup>\/p. Debido a la naturaleza discreta de este problema, es pr\u00e1cticamente imposible tener territorios perfectamente balanceados. Por consiguiente, se introdujo un par\u00e1metro de tolerancia \u03c4(2)<\/sup> para el volumen de ventas que permite una desviaci\u00f3n relativa con respecto al valor promedio \u00b5<\/em>(2)<\/sup>. Para medir la dispersi\u00f3n utilizamos la medida de dispersi\u00f3n del conocido problema de la p-mediana. Bajo los supuestos anteriores, el modelo combinatorio biobjetivo puede escribirse como:<\/p>\r\n\r\n\r\n\r\n El objetivo es encontrar una p<\/em>-partici\u00f3n X<\/em>= (X<\/em>1 <\/sub>,…, X<\/em>p<\/sub>) de V<\/em>, tal que, tanto la dispersi\u00f3n (1) en cada territorio como la desviaci\u00f3n m\u00e1xima relativa con respecto al n\u00famero de clientes en cada territorio (2) sean minimizados simult\u00e1neamente. Las restricciones (3)-(4) establecen que el tama\u00f1o del territorio (volumen de ventas) debe estar entre el rango permitido por el par\u00e1metro de tolerancia \u03c4(2)<\/sup>. Las restricciones (5) aseguran la conexidad de cada territorio, donde G<\/em>k<\/sub> es el grafo inducido en G<\/em> por el conjunto de nodos X<\/em>K<\/em><\/sub>. El problema anterior es NP-duro (Salazar- Salazar-Aguilar,\u00a0 2011b).<\/p>\r\n\r\n\r\n\r\n El enfoque evolutivo llamado b\u00fasqueda dispersa (SS, por sus siglas en ingl\u00e9s) se basa en diversificar la b\u00fasqueda en el espacio de soluciones. Opera sobre un conjunto de soluciones denominado el conjunto de referencia, formado por soluciones buenas y diversas de la poblaci\u00f3n principal. \u00c9stas son combinadas con el prop\u00f3sito de generar nuevas soluciones con mejor valor objetivo, mientras se mantiene la diversidad. La estructura b\u00e1sica de SS (Mart\u00ed, Laguna y Glover, 2006) est\u00e1 formada por cinco m\u00f3dulos principales. La figura 1 ilustra la representaci\u00f3n esquem\u00e1tica del SS propuesto, donde se muestra c\u00f3mo interact\u00faan los m\u00f3dulos.<\/p>\r\n\r\n\r\n\r\n SS es una t\u00e9cnica muy flexible debido a que algunos m\u00f3dulos de su estructura pueden definirse de acuerdo al problema bajo estudio. Por ejemplo, en este trabajo, los m\u00f3dulos de diversificaci\u00f3n, mejora y combinaci\u00f3n se propusieron e implementaron ad hoc<\/em> para este problema espec\u00edfico, para tratar de aprovechar su estructura. En nuestro dise\u00f1o, el m\u00f3dulo de diversificaci\u00f3n genera un conjunto de soluciones iniciales apoyado en estrategias de GRASP, en las cuales la funci\u00f3n voraz est\u00e1 basada en las dos funciones objetivo del problema. El m\u00f3dulo de mejora trata de optimizar una soluci\u00f3n dada utilizando una estrategia de b\u00fasqueda local encadenada para problemas multiobjetivo, utilizando las funciones objetivo del problema una a la vez de forma secuencial. El m\u00f3dulo de combinaci\u00f3n de soluciones transforma dos soluciones dadas en una o m\u00e1s soluciones (hijos), tratando de mantener caracter\u00edsticas buenas de las soluciones combinadas; el m\u00f3dulo de generaci\u00f3n de subconjuntos genera las soluciones a ser combinadas en el m\u00f3dulo anterior. En esta aplicaci\u00f3n espec\u00edfica se generan exactamente tres soluciones hijo de dos dise\u00f1os de territorio dados. Estos tres m\u00f3dulos del problema espec\u00edfico se describen completamente en Salazar-Aguilar et al<\/em>. (2012). Finalmente, los dos m\u00f3dulos restantes, los cuales no son dependientes del problema, son el m\u00f3dulo de actualizaci\u00f3n\u00a0del conjunto referencia y el m\u00f3dulo de generaci\u00f3n de conjuntos. El primero de los m\u00f3dulos mantiene una porci\u00f3n de las mejores soluciones en el conjunto referencia. En este caso, el conjunto referencia est\u00e1 formado por soluciones no-dominadas que van de acuerdo al criterio de Pareto, donde se consideraron ambas funciones objetivo del problema. Cuando se encuentra una soluci\u00f3n no-dominada, \u00e9sta entra al conjunto de referencia y aquellas soluciones que son dominadas por la soluci\u00f3n que se agreg\u00f3 son eliminadas del conjunto de referencia. El m\u00f3dulo de generaci\u00f3n de subconjuntos act\u00faa en el conjunto de referencia, en \u00e9ste los subconjuntos de soluciones que deben ser combinados son creados por todos los pares de soluciones posibles del conjunto de referencia.\u00a0<\/p>\r\n\r\n\r\n\r\n Durante cada iteraci\u00f3n del SSMTDP, se utiliz\u00f3 una memoria temporal para evitar combinaciones que fueron realizadas en la iteraci\u00f3n previa. En otras palabras, para una iteraci\u00f3n espec\u00edfica, el proceso de combinaci\u00f3n se aplica s\u00f3lo para aquellos pares de soluciones que no fueron combinados en la iteraci\u00f3n anterior.<\/p>\r\n\r\n\r\n\r\n El procedimiento fue programado en C++, y compilado en Sun C++ versi\u00f3n 8.0 bajo el sistema operativo Solaris 9, y se ejecut\u00f3 en un SunFire V440. Los conjuntos de datos se tomaron de la base de datos (R\u00edos-Mercado y Fern\u00e1ndez, 2009). Estos conjuntos de datos contienen instancias generadas aleatoriamente basadas en datos reales proporcionados por una compa\u00f1\u00eda. El SSMTDP se aplic\u00f3 sobre dos conjuntos de instancias con (n,p<\/em>) \u03f5\u00a0 {(500,20),(1000,50)}. Para cada conjunto se generaron diez instancias y se utiliz\u00f3 un par\u00e1metro de tolerancia \u03c4(2)<\/sup> = 0.05 para todos ellos. Se utilizaron dos criterios de parada en el SSMTDP, l\u00edmite de iteraciones y convergencia. En estos experimentos, el n\u00famero m\u00e1ximo de iteraciones es 10.<\/p>\r\n\r\n\r\n\r\n Durante el trabajo experimental, se observ\u00f3 que el SSMTDP convergi\u00f3 sin alcanzar el n\u00famero m\u00e1ximo de iteraciones en todas las instancias probadas. As\u00ed, en todos los casos el SSMTDP se detuvo cuando no hubo nuevas soluciones para agregarse al conjunto de referencia. La figura 2 muestra el desempe\u00f1o del SSMTDP para la instancia DU500-08, con 500 UBs y 20 territorios. La primera frontera (BGRASP-I) es el conjunto de soluciones iniciales generado por el m\u00f3dulo de diversificaci\u00f3n (BGRASP-I). Las siguientes fronteras muestran las soluciones que pertenecen al conjunto de referencia en cada iteraci\u00f3n del SSMTDP. Recuerde que el SSMTDP comienza con un conjunto de soluciones no-dominadas que se obtiene a trav\u00e9s del m\u00f3dulo de diversificaci\u00f3n. Estas soluciones se asignan al conjunto de referencia inicial. Despu\u00e9s de eso, cada par de soluciones en el conjunto de referencia es combinado para generar tres soluciones diferentes. Las nuevas soluciones generadas son\u00a0mejoradas a trav\u00e9s del RLS y despu\u00e9s se actualiza el conjunto de referencia obtenido, as\u00ed se genera un nuevo conjunto de referencia. Cuando el conjunto de referencia ya no cambia, el SSMTDP se detiene. En el caso mostrado en la figura 2, el SSMTDP converge en la iteraci\u00f3n 9. Es decir, en esta iteraci\u00f3n, la combinaci\u00f3n de las soluciones del conjunto de referencia no produjo soluciones no-dominadas para agregarse al conjunto de referencia. De esta manera, el SSMTDP reporta como conjunto de soluciones no-dominadas a aqu\u00e9llas que pertenecen al conjunto de referencia en la \u00faltima iteraci\u00f3n.<\/p>\r\nRESUMEN<\/h4>\r\n\r\n\r\n\r\n
ABSTRACT<\/h4>\r\n\r\n\r\n\r\n
DESCRIPCI\u00d3N DEL PROBLEMA<\/h4>\r\n\r\n\r\n\r\n
![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2019\/07\/formulas1-1.png\")
<\/figure>\r\n<\/div>\r\n\r\n\r\n\r\nPROCEDIMIENTO DE SOLUCI\u00d3N PROPUESTO<\/h4>\r\n\r\n\r\n\r\n
![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2019\/07\/figura1-2.png\")
<\/figure>\r\n<\/div>\r\n\r\n\r\n\r\nTRABAJO EXPERIMENTAL<\/h4>\r\n\r\n\r\n\r\n
![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2019\/07\/figura2-6.png\")
<\/a><\/p>\r\n\r\n\r\n\r\n\r\n\r\n![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2019\/07\/figura3-8.png\")
<\/a><\/p>\r\n\r\n\r\n\r\n\r\n\r\n![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2019\/07\/tabla1-1.png\")
<\/figure>\r\n<\/div>\r\n\r\n\r\n\r\n![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2019\/07\/tabla2.png\")
<\/figure>\r\n<\/div>\r\n\r\n\r\n\r\n![\"\"](\"http:\/\/cienciauanl.uanl.mx\/wp-content\/uploads\/2019\/07\/figura4-5.png\")
<\/figure>\r\n<\/div>\r\n\r\n\r\n\r\n