Analysis of the Effect of Random Numbers in Stochastic Heuristics for Solving Operations Research Problems

INTRODUCTION: Random numbers are widely employed in stochastic and randomized heuristics to solve diverse Operations Research problems by facilitating the exploration and exploitation of new solution spaces. OBJECTIVES: This paper examines various stochastic randomized heuristics, including Lévy-based heuristics, for solving the Travelling Salesman Problem (TSP), Facility Location Problem (FLP), Permutation Flowshop Scheduling Problem (PFSSP), and real-world engineering problems. For the TSP and PFSSP, the insertion technique of the Nawaz–Enscore–Ham (NEH) algorithm is integrated with random numbers to generate approximate solutions, while the FLP and real-world engineering problems are addressed by executing the randomized algorithm across multiple trials. METHODS: The proposed approaches are evaluated using 12 TSP benchmark instances, including instances with up to 783 nodes, a real-world TSP involving 20 major cities in Slovakia, geodetic coordinates of 79 district headquarters in Slovakia for location science, 90 Taillard instances for scheduling problems, and 10 constrained real-world engineering problems. Up to 20,000 trials are considered, and the minimum, mean, and standard deviation of the resulting solutions are computed. RESULTS: The findings demonstrate that appropriately designed randomized heuristics can achieve promising approximate solutions across diverse Operations Research problems. The statistical metrics are computed and results across all problem classes are compared with algorithms reported in the literature. CONCLUSION: The study highlights the potential of stochastic and randomized approaches as effective computational methods for addressing complex optimization problems.