Best-matching with interdependent preferences—implications for capacitated cluster formation and evolution

摘要

Generalized best-matching refers to matching the elements of two or more sets, on a many-to-one or many-to-many basis, with respect to their mutual preferences and capacity requirements/limits. Generalized best-matching problem (BMP) has a variety of applications in areas such as team and network design, scheduling, transportation, routing, production planning, facility location, allocation, and logistics. The problem is indeed analogous to the capacitated clustering problem, where a set of individuals are partitioned into disjoint clusters with certain capacities. This work defines, formulates, and analyzes an important behavior associated with the generalized BMP: The mutual influence of the elements of the same set on each other’s preferences, if matched to the same element of the other set. Such preferences are referred to as interdependent preferences (IP). A binary program is developed to formulate the problem and provide the basis for analyzing the impact of IP on generalized best-matching decisions from two perspectives: Optimal cluster formation (fixed sets) and evolution (emergent sets). A set of evolutionary algorithms is then developed to handle the complexity of the cluster formation problem, and enable the network of clusters to autonomously adapt to random changes, recover, and evolve. Results from several experiments indicate (a) significant impact of IP on the optimality of cluster formation and evolution decisions, and (b) efficiency of the developed evolutionary algorithms in handling the problem’s complexity, and the emergent behavior of matching.