.png){kind=icon}
.png){kind=icon}
Return
The stochastic maximum diversity problem
.png){kind=icon}
PRE
AI
DOI：10.1080/01605682.2026.2636610.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The Maximum Diversity Problem (MDP) is a well-known combinatorial optimisation model with applications ranging from facility location to social network analysis. This paper introduces a stochastic extension, the Stochastic Maximum Diversity Problem (SMDP), to better model applications based on attributes that may change, such as the travel time in location or routeing problems and affinity or preferences in social networks. The mathematical programming literature widely recognises that using stochastic data introduces an additional layer of difficulty to optimisation problems and therefore makes them more difficult to solve. The MDP is an NP-hard problem; consequently, the stochastic maximum diversity problem (SMDP) considered in this paper is difficult to solve. This paper proposes an extension to the scatter search (SS) method, the Stochastic SS, which integrates SS with simulation to solve the SMDP efficiently. Specifically, a Simheuristic SS algorithm is considered. It is based on customised search strategies to explore the solution space efficiently. The proposed approach is validated by an extensive comparison with alternative reference methods, and the results show the superior performance of the proposed method for stochastic problems.
Keywords:
Stochastic combinatorial optimisation problems
diversity problem
metaheuristics
simheuristics
Journal
IF:
2.7
Papers:
389
Citations:
9.2K
Organization
View more organizations