New AutoRL Methods Optimize Sequential Ordering Problem Routes

The study, published in July 2025, presents AutoRL-SOP and AutoRL-SOP-MtL, which utilize hyperparameter optimization and metalearning to automatically tune the settings of reinforcement learning algorithms. These methods aim to address a gap in the literature where specific automated systems for combinatorial optimization, particularly for the Sequential Ordering Problem, have been lacking. The primary objective is to assist artificial intelligence users in finding the best configurations for machine learning models without extensive manual intervention.

The Sequential Ordering Problem involves finding the shortest route between a group of cities while observing specific precedence restrictions between locations. Unlike the traditional Traveling Salesman Problem, where the goal is simply to visit each city once and return to the start, the Sequential Ordering Problem adds constraints that dictate the order in which certain nodes must be visited. The study focuses on using reinforcement learning, a subarea of machine learning where an agent learns from rewards received in an environment, to navigate these constraints effectively.

The core innovation of the proposed approach lies in the automated tuning of three specific hyperparameters for the SARSA reinforcement learning algorithm: the learning rate, the discount factor, and the epsilon-greedy policy. These parameters directly influence how quickly the agent learns, how much it values future rewards versus immediate ones, and how often it explores random actions versus exploiting known best actions. The new methods employ the Scott-Knott Clustering and HyperTuningSK algorithms to statistically determine the most effective values for these hyperparameters.

AutoRL-SOP operates by sequentially optimizing each hyperparameter. The process begins by adjusting the epsilon-greedy policy, as the system’s sensitivity to random actions is considered high. It then tunes the learning rate, followed by the discount factor. At each stage, the algorithm simulates multiple configurations and uses analysis of variance to identify significant differences in performance. The best-performing group of hyperparameters is selected for the next phase, ensuring that the final configuration is robust. This step-by-step optimization allows the system to narrow down the vast space of possible settings to a highly effective combination.

The second method, AutoRL-SOP-MtL, introduces a metalearning component that transfers hyperparameter knowledge from one domain to another. Specifically, it uses the Asymmetric Traveling Salesman Problem as a source domain to initialize the hyperparameters for the Sequential Ordering Problem target domain. Since many SOP instances are derived from ATSP instances by adding precedence constraints, this transfer is theoretically sound. By leveraging the experience gained from solving the simpler ATSP problem, the metalearning approach aims to reduce the computational cost of finding optimal hyperparameters for the more constrained SOP instances.

The experiments were conducted using 28 instances from the TSPLIB library, a widely adopted public dataset for combinatorial optimization problems. The hardware used for the simulations included an Intel Core i7-8565 CPU, 8 GB of RAM, and an NVIDIA GeForce MX110 GPU. The software environment was built using the R programming language, version 4.3.3, with specific libraries for reinforcement learning and hyperparameter tuning. This setup ensures that the results are reproducible and grounded in standard computational tools available to the research community.

The results demonstrate that the proposed AutoRL methods achieved the best solutions in 23 out of the 28 simulated instances when compared to recent literature studies. The AutoRL-SOP method alone obtained the smallest distances in 15 of the 21 instances where both techniques were tested. In the remaining instances, the metalearning variant or ties with the best known literature solutions were observed. This indicates a strong generalization capability of the proposed methods across different problem sizes and complexities, from smaller instances like br17.10 to larger, more complex ones like ry48p.4.

A significant advantage of the AutoRL-SOP-MtL method is the reduction in computational cost. The study reports that the metalearning approach achieved lower computational costs in 19 of the 21 instances where it was applicable. In twelve instances, the percentage difference in average computational time was greater than 50%. For example, in the ry48p.4 instance, the total execution time dropped from 2345.59 minutes using standard AutoRL-SOP to 265.31 minutes with metalearning. This dramatic reduction highlights the efficiency of transferring tuned hyperparameters from the ATSP domain to the SOP domain, bypassing the need for extensive re-optimization.

The hyperparameter configurations recommended by the methods showed certain patterns. The epsilon value of 0.05 was the most frequently recommended for both techniques, suggesting that a low level of randomness is beneficial for these specific optimization tasks. Similarly, a high learning rate of 0.85 was often selected, indicating that rapid adaptation to new information is crucial. The discount factor varied slightly between methods, with AutoRL-SOP generally preferring 0.25 and the metalearning variant preferring 0.05. These findings provide insights into the specific characteristics of the SARSA algorithm when applied to sequential ordering problems.

Learning curves for the ft70.3 instance illustrate the effectiveness of the tuned hyperparameters. Both methods led to improvements in performance throughout the episodes. Initially, the reinforcement learning algorithm produced poorer results, with route distances exceeding 70,000. However, after approximately 200 episodes, the algorithm began to achieve results closer to the best-known solution, dropping below 50,000. This progression demonstrates that the automated tuning process successfully identifies configurations that allow the agent to learn efficiently and converge on optimal solutions.

The study also compares its approach with two previous literature studies that applied reinforcement learning to the Sequential Ordering Problem. While those studies used 11 and 18 instances respectively, the current work tested 28 instances, providing a more comprehensive evaluation. The previous studies either used analytical methods for hyperparameter tuning or focused on transfer learning of the Q-matrix rather than hyperparameters. The current paper innovates by combining automated hyperparameter tuning with metalearning across domains, offering a more integrated and efficient solution for combinatorial optimization.

The study suggests future work on applying these methods to other combinatorial problems and real-world scenarios, such as path planning for autonomous robots. Further improvements could involve exploring other metalearning strategies, such as transfer learning, to enhance the efficiency and accuracy of the automated reinforcement learning process.

In conclusion, the proposed AutoRL-SOP and AutoRL-SOP-MtL methods represent a significant advancement in the field of automated reinforcement learning for combinatorial optimization. By automating the tuning of critical hyperparameters and leveraging metalearning, these methods achieve superior solutions with reduced computational costs. The findings underscore the potential of AutoML techniques to streamline the development of intelligent systems for complex optimization tasks, offering a practical tool for researchers and practitioners in the field.

Subject of Research: Automated reinforcement learning for combinatorial optimization

Article Title: Automated reinforcement learning for sequential ordering problem using hyperparameter optimization and metalearning

Article References: Ottoni, A. L. C. (2025). Automated reinforcement learning for sequential ordering problem using hyperparameter optimization and metalearning. Autonomous Intelligent Systems, 5(1), Article 15. https://doi.org/10.1007/s43684-025-00103-2

Image Credits: AI Generated

DOI: 10.1007/s43684-025-00103-2

Keywords: reinforcement learning, combinatorial optimization, hyperparameter optimization, metalearning, sequential ordering problem, AutoML, SARSA, traveling salesman problem, artificial intelligence, machine learning, Automated, reinforcement