The effect of different initial solutions on the metaheuristic algorithms for the single allocation p-hub center and...

This article introduces methods for initializing a single-trajectory-based metaheuristic, specifically a simulated annealing (SA) algorithm, using constructive heuristics. These methods are designed to target promising regions within the search space of an nondeterministic polynomial time (NP)-hard problem, namely the single allocation p-hub center and routing problem. The objective of this problem is to allocate demand centers to hubs and design vehicle routes such that the maximum distance between all origin-destination pairs is minimized. To analyze the impact of different initial solutions, various constructive heuristics, including greedy and hybrid strategies, have been proposed. Additionally, a problem decomposition approach leveraging domain-specific knowledge has been incorporated through a matheuristic initial solution strategy to enhance the efficiency of the simulated annealing algorithm. This approach generates high-quality initial solutions by first solving the p-hub center problem and then using the obtained hubs and their assignments as inputs to the min-max multiple traveling salesman problem. In this problem, the objective function is formulated differently from the literature by minimizing the longest distance between the two nodes. Several experiments have been conducted on the Turkish network, and upon examining the results, it has been observed that each initial solution generation strategy provides improvements in problem instances with specific characteristics, such as the number of vehicles and nodes. We also observed lower objective function values for all medium- and large-sized test problems taken from the literature, highlighting the effectiveness of the proposed strategies.