Un novel esquema de acotamiento dual para la optimización de planes territoriales
DOI:
https://doi.org/10.29105/cienciauanl21.90-3Keywords:
diseño de territorios comerciales, localización discreta, relajación lagrangiana, esquema de acotamiento dualAbstract
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.
Downloads
References
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. DOI: https://doi.org/10.1016/j.ejor.2009.02.022
Daskin, M.S. (1995). Network and Discrete Location: Models, Algorithms and Applications. Wiley, New York, EUA. DOI: https://doi.org/10.1002/9781118032343
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. DOI: https://doi.org/10.1016/j.cor.2013.11.006
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. DOI: https://doi.org/10.1287/ijoc.1030.0028
Fisher, M.L. (1981). The Lagrangian relaxation method for solving integer programming problems. Management Science. 27(1):1-18. DOI: https://doi.org/10.1287/mnsc.27.1.1
Fisher, M.L. (1985). An applications oriented guide to Lagrangian relaxation. Interfaces. 15(2):2-21. DOI: https://doi.org/10.1287/inte.15.2.10
Geoffrion, A.M. (1974). Lagrangean relaxation for integer programming. Mathematical Programming Studies. 2:82-114. DOI: https://doi.org/10.1007/BFb0120690
Guignard, M. (2003). Lagrangean relaxation. TOP. 11(2):151-228. DOI: https://doi.org/10.1007/BF02579036
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. DOI: https://doi.org/10.1007/BF02578982
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. DOI: https://doi.org/10.1137/0137040
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. DOI: https://doi.org/10.1137/0604028
Minieka, E. (1996). The m-center problem. SIAM Review. 12(1):138-139; 1970. DOI: https://doi.org/10.1137/1012016
Ö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. DOI: https://doi.org/10.1016/j.cor.2004.09.035
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. DOI: https://doi.org/10.1016/j.cor.2007.10.024
Ríos-Mercado, R. Z., y Escalante, H.J. (2016). GRASP with path relinking for commercial districting. Expert Systems with Applications. 44:102-113. DOI: https://doi.org/10.1016/j.eswa.2015.09.019
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. DOI: https://doi.org/10.1016/j.omega.2012.08.002
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. DOI: https://doi.org/10.1007/s11067-010-9151-6
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. DOI: https://doi.org/10.1016/j.trc.2010.09.011
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. DOI: https://doi.org/10.1007/s10732-011-9160-8
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. DOI: https://doi.org/10.1007/s10479-011-1045-6
Downloads
Published
Versions
- 2023-10-26 (2)
- 2023-10-20 (1)
