Skip to main content
main-content

Tipp

Weitere Kapitel dieses Buchs durch Wischen aufrufen

2018 | OriginalPaper | Buchkapitel

32. Diversity and Equity Models

verfasst von: Fernando Sandoya, Anna Martínez-Gavara, Ricardo Aceves, Abraham Duarte, Rafael Martí

Erschienen in: Handbook of Heuristics

Verlag: Springer International Publishing

share
TEILEN

Abstract

The challenge of maximizing the diversity of a collection of points arises in a variety of settings, and the growing interest of dealing with diversity resulted in an effort to study the management of equity. While the terms diversity and dispersion can be found in many optimization problems indistinguishable, we undertake to explore the different models behind them.
In particular, this chapter describes the mathematical models for two diversity and three equity models. Additionally, we also review two related models that have recently received special attention. This chapter also reviews heuristics and metaheuristics for finding near-optimal solutions for these problems, where constructive and local search-based methods, such as greedy randomized adaptive search procedure (GRASP) and tabu search, play an important role.
Literatur
1.
Zurück zum Zitat A \(\check {g}\)ca S, Eksioglu B, Ghosh JB (2000) Lagrangian solution of maximum dispersion problems. Nav Res Logist 47:97–114 A \(\check {g}\)ca S, Eksioglu B, Ghosh JB (2000) Lagrangian solution of maximum dispersion problems. Nav Res Logist 47:97–114
2.
Zurück zum Zitat Aringhieri R, Cordone R (2011) Comparing local search metaheuristics for the maximum diversity problem. J Oper Res Soc 62:266–280 Aringhieri R, Cordone R (2011) Comparing local search metaheuristics for the maximum diversity problem. J Oper Res Soc 62:266–280
3.
Zurück zum Zitat Aringhieri R, Cordone R, Grosso A (2015) Construction and improvement algorithms for dispersion problems. Eur J Oper Res 242:21–33 Aringhieri R, Cordone R, Grosso A (2015) Construction and improvement algorithms for dispersion problems. Eur J Oper Res 242:21–33
4.
Zurück zum Zitat Asada H, Toyama F, Shoji K, Miyamichi J (2010) Genetic local search with adaptative crossover probability and its application to maximum diversity problem. IEEJ Trans Electron Inf Syst 130:529–520 Asada H, Toyama F, Shoji K, Miyamichi J (2010) Genetic local search with adaptative crossover probability and its application to maximum diversity problem. IEEJ Trans Electron Inf Syst 130:529–520
5.
Zurück zum Zitat Brimberg J, Mladenovic N, Urosevic D, Ngai E (2009) Variable neighborhood search for the heaviest k-subgraph. Comput Oper Res 36:2885–2891 Brimberg J, Mladenovic N, Urosevic D, Ngai E (2009) Variable neighborhood search for the heaviest k-subgraph. Comput Oper Res 36:2885–2891
6.
Zurück zum Zitat Campos V, Laguna M, Martí R (2005) Context-independient scatter and tabu search for permutation problems. INFORMS J Comput 17(1):111–122 Campos V, Laguna M, Martí R (2005) Context-independient scatter and tabu search for permutation problems. INFORMS J Comput 17(1):111–122
7.
Zurück zum Zitat Carrasco R, Pham A, Gallego M, Gortázar F, Martí R, Duarte A (2015) Tabu search for the max-mean dispersion problem, Knowledge based systems 85:256–264 Carrasco R, Pham A, Gallego M, Gortázar F, Martí R, Duarte A (2015) Tabu search for the max-mean dispersion problem, Knowledge based systems 85:256–264
8.
Zurück zum Zitat Castillo O, Melin P, Gamez E, Kreinovich V, Kosheleva O (2009) Intelligence techniques are needed to further enhance the advantage with diversity in problem solving. In: IEEE workshop hybrid intelligent models and applications (HIMA’09), Nashville, pp 48–55 Castillo O, Melin P, Gamez E, Kreinovich V, Kosheleva O (2009) Intelligence techniques are needed to further enhance the advantage with diversity in problem solving. In: IEEE workshop hybrid intelligent models and applications (HIMA’09), Nashville, pp 48–55
9.
Zurück zum Zitat Dell’Amico M, Trubian M (1998) Solution of large weighted equicut problems. Eur J Oper Res 106:500–521 Dell’Amico M, Trubian M (1998) Solution of large weighted equicut problems. Eur J Oper Res 106:500–521
10.
Zurück zum Zitat Della Groce F, Grosso A, Locatelli M (2009) A heuristic approach for the max-min diversity problem based on max-clique. Comput Oper Res 36(8):2429–2433 Della Groce F, Grosso A, Locatelli M (2009) A heuristic approach for the max-min diversity problem based on max-clique. Comput Oper Res 36(8):2429–2433
11.
Zurück zum Zitat Deng Y, Bard JF (2011) A reactive GRASP with path relinking for capacitated clustering. J Heuristics 17:119–152 Deng Y, Bard JF (2011) A reactive GRASP with path relinking for capacitated clustering. J Heuristics 17:119–152
12.
Zurück zum Zitat Duarte A, Martí R (2007) Tabu search and GRASP for the maximum diversity problem. Eur J Oper Res 178:71–84 Duarte A, Martí R (2007) Tabu search and GRASP for the maximum diversity problem. Eur J Oper Res 178:71–84
13.
Zurück zum Zitat Duarte A, Sánchez-Oro J, Resende M, Glover F, Martí R (2015) GRASP with exterior path relinking for differential dispersion minimization. Inf Sci 296(1):46–60 Duarte A, Sánchez-Oro J, Resende M, Glover F, Martí R (2015) GRASP with exterior path relinking for differential dispersion minimization. Inf Sci 296(1):46–60
14.
Zurück zum Zitat Erkut E (1990) The discrete p-dispersion problem. Eur J Oper Res 46:48–60 Erkut E (1990) The discrete p-dispersion problem. Eur J Oper Res 46:48–60
15.
Zurück zum Zitat Erkut E, Neuman S (1989) Analytical models for locating undesirable facilities. Eur J Oper Res 40:275–291 Erkut E, Neuman S (1989) Analytical models for locating undesirable facilities. Eur J Oper Res 40:275–291
16.
Zurück zum Zitat Feo T, Goldschmidt O, Khellaf M (1992) One-half approximation algorithms for the k-partition problem. Oper Res 40:S170–S173 Feo T, Goldschmidt O, Khellaf M (1992) One-half approximation algorithms for the k-partition problem. Oper Res 40:S170–S173
17.
Zurück zum Zitat Freitas ARR, Guimarães FG, Pedrosa Silca RC, Souza MJF (2014) Memetic self-adaptive evolution strategies applied to the maximum diversity problem. Optim Lett 8(2): 705–714 Freitas ARR, Guimarães FG, Pedrosa Silca RC, Souza MJF (2014) Memetic self-adaptive evolution strategies applied to the maximum diversity problem. Optim Lett 8(2): 705–714
18.
Zurück zum Zitat French E (2005) The importance of strategic change in achieving equity in diversity. Strateg Change 14:35–44. Wiley InterScience French E (2005) The importance of strategic change in achieving equity in diversity. Strateg Change 14:35–44. Wiley InterScience
19.
Zurück zum Zitat Gallego M, Laguna M, Martí R, Duarte A (2013) Tabu search with strategic oscillation for the maximally diverse grouping problem. J Oper Res Soc 64(5):724-734 Gallego M, Laguna M, Martí R, Duarte A (2013) Tabu search with strategic oscillation for the maximally diverse grouping problem. J Oper Res Soc 64(5):724-734
20.
Zurück zum Zitat Ghosh JB (1996) Computational aspects of the maximum diversity problem. Oper Res Lett 19:175–181 Ghosh JB (1996) Computational aspects of the maximum diversity problem. Oper Res Lett 19:175–181
21.
Zurück zum Zitat Glover F (1977) Heuristics for integer programming using surrogate constraints. Decis Sci 8(1):156–166 Glover F (1977) Heuristics for integer programming using surrogate constraints. Decis Sci 8(1):156–166
22.
Zurück zum Zitat Glover F (2014) Exterior path relinking for zero-one optimization. Int J Appl Metaheuristic Comput 5(3):1–8 Glover F (2014) Exterior path relinking for zero-one optimization. Int J Appl Metaheuristic Comput 5(3):1–8
23.
Zurück zum Zitat Glover F, Laguna M (1997) Tabu Search. Kluwer Academic Publishers, Boston Glover F, Laguna M (1997) Tabu Search. Kluwer Academic Publishers, Boston
24.
Zurück zum Zitat Glover F, Kuo CC, Dhir KS (1995) A discrete optimization model for preserving biological diversity. Appl Math Model 19:696–701 Glover F, Kuo CC, Dhir KS (1995) A discrete optimization model for preserving biological diversity. Appl Math Model 19:696–701
25.
Zurück zum Zitat Glover F, Kuo CC, Dhir KS (1998) Heuristic algorithms for the maximum diversity problem. J Inf Optim Sci 19(1):109–132 Glover F, Kuo CC, Dhir KS (1998) Heuristic algorithms for the maximum diversity problem. J Inf Optim Sci 19(1):109–132
26.
Zurück zum Zitat Hansen P, Mladenovic N (2001) Variable neighborhood search: principles and aplications. Eur J Opns Res 130:449–467 Hansen P, Mladenovic N (2001) Variable neighborhood search: principles and aplications. Eur J Opns Res 130:449–467
27.
Zurück zum Zitat Hansen P, Mladenovic N (2003) Variable neighborhood search. In: Glover F, Kochenberger G (eds) Handbook in metaheuristics. Kluwer Academic Publishers, Boston Hansen P, Mladenovic N (2003) Variable neighborhood search. In: Glover F, Kochenberger G (eds) Handbook in metaheuristics. Kluwer Academic Publishers, Boston
28.
Zurück zum Zitat Hassin R, Rubinstein S, Tamir A (1997) Approximation algorithms for maximum dispersion. Oper Res Lett 21:133–137 Hassin R, Rubinstein S, Tamir A (1997) Approximation algorithms for maximum dispersion. Oper Res Lett 21:133–137
29.
Zurück zum Zitat Katayama K, Narihisa H (2005) An evolutionary approach for the maximum diversity problem. In: Recent advances in memetic algorithms, vol 166. Springer, Berlin/New York, pp 31–47 Katayama K, Narihisa H (2005) An evolutionary approach for the maximum diversity problem. In: Recent advances in memetic algorithms, vol 166. Springer, Berlin/New York, pp 31–47
30.
Zurück zum Zitat Kincard RK (1992) Good solutions to discrete noxious location problems via metaheuristics. Ann Oper Res 40:265–281 Kincard RK (1992) Good solutions to discrete noxious location problems via metaheuristics. Ann Oper Res 40:265–281
31.
Zurück zum Zitat Kuo CC, Glover F, Dhir KS (1993) Analyzing and modeling the maximum diversity problem by zero-one programming. Decis Sci 24:1171–1185 Kuo CC, Glover F, Dhir KS (1993) Analyzing and modeling the maximum diversity problem by zero-one programming. Decis Sci 24:1171–1185
32.
Zurück zum Zitat Laguna M, Marí R (2003) Scatter search: methodology and implementations in C. Kluwer Academic Publishers, Dordrecht Laguna M, Marí R (2003) Scatter search: methodology and implementations in C. Kluwer Academic Publishers, Dordrecht
33.
Zurück zum Zitat Martí R, Sandoya F (2013) GRASP and path relinking for the equitable dispersion problem. Comput Oper Res 40:3091–3099 Martí R, Sandoya F (2013) GRASP and path relinking for the equitable dispersion problem. Comput Oper Res 40:3091–3099
35.
Zurück zum Zitat Martínez-Gavara A, Campos V, Gallego M, Laguna M, Martí R (2015) Tabu Search and GRASP for the Capacited Clustering Problem. Comput Optim Appl 62:589–607 MathSciNetCrossRef Martínez-Gavara A, Campos V, Gallego M, Laguna M, Martí R (2015) Tabu Search and GRASP for the Capacited Clustering Problem. Comput Optim Appl 62:589–607 MathSciNetCrossRef
36.
Zurück zum Zitat Mladenović N, Todosijević R, Urosević D (2016) Less is more: basic variable neighborhood search for minimum differential dispersion problem. Inf Sci 326:160171 CrossRef Mladenović N, Todosijević R, Urosević D (2016) Less is more: basic variable neighborhood search for minimum differential dispersion problem. Inf Sci 326:160171 CrossRef
37.
Zurück zum Zitat Morán-Mirabal LF, González-Velarde JL, Resende MGC, Silva RMA (2013) Randomized heuristics for handover minimization in mobility networks. J Heuristics 19:845–880 CrossRef Morán-Mirabal LF, González-Velarde JL, Resende MGC, Silva RMA (2013) Randomized heuristics for handover minimization in mobility networks. J Heuristics 19:845–880 CrossRef
38.
Zurück zum Zitat O’Brien FA, Mingers J (1995) The equitable partitioning problem: a heuristic algorithm applied to the allocation of university student accommodation. Warwick Business School, Research Paper no. 187 O’Brien FA, Mingers J (1995) The equitable partitioning problem: a heuristic algorithm applied to the allocation of university student accommodation. Warwick Business School, Research Paper no. 187
39.
Zurück zum Zitat Page SE (2007) The difference: how the power of diversity creates better groups, firms, schools, and societies. Princeton University Press, Princeton Page SE (2007) The difference: how the power of diversity creates better groups, firms, schools, and societies. Princeton University Press, Princeton
40.
Zurück zum Zitat Palubeckis G (2007) Iterated tabu search for the maximum diversity problem. Appl Math Comput 189(1):371–383 MathSciNetMATH Palubeckis G (2007) Iterated tabu search for the maximum diversity problem. Appl Math Comput 189(1):371–383 MathSciNetMATH
41.
Zurück zum Zitat Pisinger D (2006) Upper bounds and exact algorithms for p-dispersion problems. Comput Oper Res 33:1380–1398 CrossRef Pisinger D (2006) Upper bounds and exact algorithms for p-dispersion problems. Comput Oper Res 33:1380–1398 CrossRef
42.
Zurück zum Zitat Porumbel D, Hao J, Glover F (2011) A simple and effective algorithm for the MaxMin diversity problem. Ann Oper Res 186(1):275–293 CrossRef Porumbel D, Hao J, Glover F (2011) A simple and effective algorithm for the MaxMin diversity problem. Ann Oper Res 186(1):275–293 CrossRef
43.
Zurück zum Zitat Prokopyev OA, Kong N, Martinez-Torres DL (2009) The equitable dispersion problem. Eur J Oper Res 197:59–67 MathSciNetCrossRef Prokopyev OA, Kong N, Martinez-Torres DL (2009) The equitable dispersion problem. Eur J Oper Res 197:59–67 MathSciNetCrossRef
44.
Zurück zum Zitat Ravi SS, Rosenkrantz DJ, Tayi GK (1994) Heuristic and special case algorithms for dispersion problems. Oper Res 42:299–310 CrossRef Ravi SS, Rosenkrantz DJ, Tayi GK (1994) Heuristic and special case algorithms for dispersion problems. Oper Res 42:299–310 CrossRef
45.
Zurück zum Zitat Resende MGC, Werneck R (2004) A hybrid heuristic for the p-median problem. J Heuristics 10(1):59–88 CrossRef Resende MGC, Werneck R (2004) A hybrid heuristic for the p-median problem. J Heuristics 10(1):59–88 CrossRef
46.
Zurück zum Zitat Resende MGC, Martí R, Gallego M, Duarte A (2010) GRASP and path relinking for the max−min diversity problem. Comput Oper Res 37(3):498–508 MathSciNetCrossRef Resende MGC, Martí R, Gallego M, Duarte A (2010) GRASP and path relinking for the max−min diversity problem. Comput Oper Res 37(3):498–508 MathSciNetCrossRef
47.
Zurück zum Zitat Wang J, Zhou Y, Cai Y, Yin J (2012) Learnable tabu search guided by estimation of distribution for maximum diversity problems. Soft Comput 16(4):711–728 CrossRef Wang J, Zhou Y, Cai Y, Yin J (2012) Learnable tabu search guided by estimation of distribution for maximum diversity problems. Soft Comput 16(4):711–728 CrossRef
Metadaten
Titel
Diversity and Equity Models
verfasst von
Fernando Sandoya
Anna Martínez-Gavara
Ricardo Aceves
Abraham Duarte
Rafael Martí
Copyright-Jahr
2018
DOI
https://doi.org/10.1007/978-3-319-07124-4_61

Premium Partner