Landscape properties of the very large-scale and the variable neighborhood search metaheuristics for the multidimensional assignment problem

Alla Kammerdiner (), Alexander Semenov () and Eduardo L. Pasiliao ()
Additional contact information
Alla Kammerdiner: Eglin Air Force Base
Alexander Semenov: The University of Florida Research and Engineering Educational Facility (REEF)
Eduardo L. Pasiliao: Eglin Air Force Base

Journal of Global Optimization, 2024, vol. 88, issue 3, No 4, 653-683

Abstract: Abstract We study the recent metaheuristic search algorithm for the multidimensional assignment problem (MAP) using fitness landscape theory. The analyzed algorithm performs a very large-scale neighborhood search on a set of feasible solutions to the problem. We derive properties of the landscape graphs that represent these very large-scale search algorithms acting on the solutions of the MAP. In particular, we show that the search graph is a generalization of a hypercube. We extend and generalize the original very large-scale neighborhood search to develop the variable neighborhood search. The new search is capable of searching even larger large-scale neighborhoods. We perform numerical analyses of the search graph structures for various problem instances of the MAP and different neighborhood structures of the MAP algorithm based on a very large-scale search. We also investigate the correlation between fitness (i.e., objective values) and distance (i.e., path lengths) of the local minima (i.e., sinks of the landscape). Our results can be used to design improved search-based metaheuristics for the MAP.

Keywords: Combinatorial optimization; Metaheuristics; The multidimensional assignment problem (MAP); Very large-scale neighborhood search (VLNS); Variable neighborhood search (VNS); Fitness landscapes (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-023-01285-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:88:y:2024:i:3:d:10.1007_s10898-023-01285-w

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-023-01285-w

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().