Lateral Hyper-Heuristics for the Hub Location Problem: Purposeful Assumption Violation in Heuristic Selection

Kassem Danach1, Email

Wael Hosny Fouad Aly2

Chadi Fouad Riman2

Samir Haddad3 

1Basic and Applied Sciences Research Center, Al Maaref University, Beirut, 1001, Lebanon
2College of Engineering and Technology, American University of the Middle East, Egaila, 54200, Kuwait
3Faculty of Arts and Sciences, Department of Computer Science, University of Balamand, Koura, 100, Lebanon

 

Abstract

The Hub Location Problem (HLP) is a challenging combinatorial optimization problem characterized by deceptive search landscapes and strong centralization biases. Conventional hyper-heuristics, which rely on rational, reward-based heuristic selection, often become trapped in suboptimal solutions. To overcome this limitation, we propose the Lateral Hyper-Heuristic (LHH) framework, which dynamically alternates between Rational Mode for exploitation and Lateral Mode for directed exploration. By monitoring indicators such as search stagnation, hub entropy, and heuristic dominance, LHH identifies epistemic traps and applies low-level heuristics that deliberately violate dominant search assumptions, enabling structural transitions in the solution space. Extensive experiments on the Uncapacitated Single Allocation p-Hub Median Problem (USApHMP) using CAB and AP benchmark datasets show that LHH reduces the average percentage deviation from known lower bounds by 76% compared to the state-of-the-art hyper-heuristic. Furthermore, LHH escapes stagnation more than twice as often, demonstrating that structured assumption violation is a highly effective mechanism for navigating deceptive optimization landscapes. These results establish LHH as a significant advancement in automated heuristic selection for complex combinatorial problems.

Lateral Hyper-Heuristics for the Hub Location Problem: Purposeful Assumption Violation in Heuristic Selection