×

zbMATH — the first resource for mathematics

New models for commercial territory design. (English) Zbl 1235.90028
Summary: In this work, a series of novel formulations for a commercial territory design problem motivated by a real-world case are proposed. The problem consists on determining a partition of a set of units located in a territory that meets multiple criteria such as compactness, connectivity, and balance in terms of customers and product demand. Thus far, different versions of this problem have been approached with heuristics due to its NP-completeness. The proposed formulations are integer quadratic programming models that involve a smaller number of variables than heretofore required. These models have also enabled the development of an exact solution framework, the first ever derived for this problem, that is based on branch and bound and a cut generation strategy. The proposed method is empirically evaluated using several instances of the new quadratic models as well as of the existing linear models. The results show that the quadratic models allow solving larger instances than the linear counterparts. The former were also observed to require fewer iterations of the exact method to converge. Based on these results the combination of the quadratic formulation and the exact method are recommended to approach problem instances associated with medium-sized cities.

MSC:
90B06 Transportation, logistics and supply chain management
90C11 Mixed integer programming
Software:
DICOPT; SPEA2
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aerts JCJH, Eisinger E, Heuvelink GBM, Stewart TJ (2003) Using linear integer programming for multi-site land-use allocation. Geogr Anal 35(2):148–169
[2] Altman M (1997) The computational complexity of automated redistricting: is automation the answer? Rutgers Comput Technol Law J 23(1):81–142
[3] Altman M (1998) Districting principles and democratic representation. PhD thesis, California Institute of Technology, Pasadena
[4] Bozkaya B, Erkut E, Laporte G (2003) A tabu search heuristic and adaptive memory procedure for political districting. Eur J Oper Res 144(1):12–26 · Zbl 1037.90535 · doi:10.1016/S0377-2217(01)00380-0
[5] Caballero-Hernández SI, Ríos-Mercado RZ, López F, Schaeffer E (2007) Empirical evaluation of a metaheuristic for commercial territory design with joint assignment constraints. In: Fernandez JE, Noriega S, Mital A, Butt SE, Fredericks TK (eds) Proceedings of the 12th annual international conference on industrial engineering theory, applications, and practice (IJIE). Cancun, Mexico, pp 422–427. ISBN: 978-0-9654506-3-8
[6] Cormen TH, Leiserson CE, Rivest RL (1990) Introduction to algorithms. MIT Press, Cambridge
[7] Domínguez E, Muñoz J (2008) A neural model for the p-median problem. Comput Oper Res 35(2):404–416 · Zbl 1141.90464 · doi:10.1016/j.cor.2006.03.005
[8] Drexl A, Haase K (1999) Fast approximation methods for sales force deployment. Manage Sci 45(10):1307–1323 · Zbl 1231.90250 · doi:10.1287/mnsc.45.10.1307
[9] Fleischmann B, Paraschis JN (1988) Solving a large scale districting problem: a case report. Comput Oper Res 15(6):521–533 · Zbl 0659.90088 · doi:10.1016/0305-0548(88)90048-2
[10] Garfinkel RS, Nemhauser GL (1970) Solving optimal political districting by implicit enumeration techniques. Manage Sci 16(8):B495–B508 · Zbl 0195.22103
[11] Hess SW, Samuels SA (1971) Experiences with a sales districting model: criteria and implementation. Manage Sci 18(4):998–1006
[12] Hess SW, Weaver JB, Siegfeldt HJ, Whelan JN, Zitlau PA (1965) Nonpartisan political redistring by computer. Oper Res 13(6):998–1006 · doi:10.1287/opre.13.6.998
[13] Hojati M (1996) Optimal political districting. Comput Oper Res 23(12):1147–1161 · Zbl 0876.90062 · doi:10.1016/S0305-0548(96)00029-9
[14] Kalcsics J, Nickel S, Schröder M (2005) Towards a unified territorial design approach: applications, algorithms, and GIS integration. Top 13(1):1–56 · Zbl 1072.90058 · doi:10.1007/BF02578982
[15] Kocis GR, Grossmann IE (1989) Computational experience with DICOPT solving MINLP problems in process systems engineering. Comput Chem Eng 13(3):307–315 · doi:10.1016/0098-1354(89)85008-2
[16] Marlin P (1981) Application of the transportation model to a large-scale districting problem. Comput Oper Res 8(2):83–96 · doi:10.1016/0305-0548(81)90036-8
[17] Mehrotra A, Johnson EL, Nemhauser GL (1998) An optimization based heuristic for political districting. Manage Sci 44(8):1100–1113 · Zbl 0988.90542 · doi:10.1287/mnsc.44.8.1100
[18] Ricca F, Simeone B (2008) Local search algorithms for political districting. Eur J Oper Res 189(3):1409–1426 · Zbl 1146.91016 · doi:10.1016/j.ejor.2006.08.065
[19] Ríos-Mercado RZ, Fernández EA (2009) A reactive GRASP for a commercial territory design problem with multiple balancing requirements. Comput Oper Res 36(3):755–776 · Zbl 1157.90515 · doi:10.1016/j.cor.2007.10.024
[20] Segura-Ramiro JA, Ríos-Mercado RZ, Álvarez-Socarrás AM, de Alba Romenus K (2007) A location-allocation heuristic for a territory design problem in a beverage distribution firm. In: Fernandez JE, Noriega S, Mital A, Butt SE, Fredericks TK (eds) Proceedings of the 12th annual international conference on industrial engineering theory, applications, and practice (IJIE). Cancun, Mexico, pp 428–434. ISBN: 978-0-9654506-3-8
[21] Shirabe T (2009) Districting modeling with exact contiguity constraints. Environ Plann B Plann Des 36(6):1053–1066 · doi:10.1068/b34104
[22] Viswanathan J, Grossmann IE (1990) A combined penalty function and outer approximation method for MINLP optimization. Comput Chem Eng 14(7):769–782 · doi:10.1016/0098-1354(90)87085-4
[23] Xiao N (2006) An evolutionary algorithm for site search problems. Geogr Anal 38(3):227–247 · doi:10.1111/j.1538-4632.2006.00684.x
[24] Zoltners AA, Sinha P (2005) Sales territory design: Thirty years of modeling and implementation. Mark Sci 24(3):313–331 · doi:10.1287/mksc.1050.0133
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.