KAIST develops AI that generates executable plans for delivery, manufacturing and shift scheduling

KAIST researchers have developed an AI technology capable of generating plans that satisfy real-world constraints — from parcel delivery routes and factory production schedules to hospital shift rosters.

KAIST announced Monday that a research team led by Kim Min-su, a professor in the School of Computing, has developed a reinforcement learning technology called RL-SPH (Reinforcement Learning-based Start Primal Heuristic), which trains AI to produce executable plans without relying on external specialized optimization software.

Parcel delivery routing, vehicle path planning, factory production scheduling and hospital shift assignment are classic examples of integer linear programming (ILP) problems, which require finding the most efficient plan while simultaneously satisfying multiple constraints.

In parcel delivery, for instance, a plan must not only minimize travel time but also respect vehicle load limits, driver working hours and complete coverage of all delivery stops. A route that violates even one of those conditions cannot be used in practice, no matter how fast it is.

Conventional AI systems frequently proposed plans that reduced cost or time but violated real-world constraints such as vehicle capacity, working hours or equipment limits. As a result, specialized optimization programs such as Gurobi and SCIP had to step in at the final stage to correct errors in AI-generated plans, making it difficult for AI alone to complete the planning process.

Rather than predicting a solution all at once, RL-SPH revises a current plan step by step, much as a person would. It adjusts variables — such as the number of staff, vehicles or production output — one at a time, resolves constraint violations and learns from the results.

The system is designed to find a usable plan before seeking the best plan. In factory production scheduling, for example, it first generates a plan that satisfies all conditions — delivery deadlines, equipment capacity and workforce requirements — then works to reduce production costs and working hours.

To achieve this, the team applied a two-stage search strategy: first locating a feasible solution that satisfies all constraints, then optimizing for cost and time.

The team also developed an AI model called ILP-GT, which learns the relationships between variables and constraints. It applies a feasibility-aware search strategy that prioritizes modifying the variables most effective for solving the problem, improving computational efficiency.

When the team evaluated RL-SPH across five benchmarks, it found executable plans in 100 percent of all problems. The system maintained the same performance even on complex problems involving general integer variables.

Compared with existing technologies, RL-SPH improved the primal gap — a measure of how close a solution is to the optimal — by an average of 28.6 times, and the primal integral, which evaluates search quality and speed, by 2.6 times. The time to find the first feasible plan also fell by an average of 2.5 times.

Against the latest AI approaches including PAS, DDIM and DiffILO, RL-SPH was the only method to achieve a 100 percent feasibility rate across all benchmarks. Its average training time of 30 minutes was 14.7 times faster than existing methods and about 34 times faster than unsupervised learning-based approaches.

On MIPLIB, an international optimization benchmark, the system reliably found feasible solutions for problems up to 67 times larger than those seen during training, as well as for entirely new problem types it had not encountered before.

"In the real world, a plan that can actually be executed matters more than the theoretically best answer," Kim said. "This work demonstrates that AI can generate executable plans on its own, without the help of specialized optimization software."

He added that the technology is expected to become a core enabler of AI-driven decision-making across industries including logistics, manufacturing, semiconductor production and workforce management.

Lee Tae-hun, a doctoral student in KAIST's School of Computing, served as first author, with Kim as corresponding author. The findings were presented last month at the International Conference on Machine Learning (ICML). The research was supported by the Ministry of Science and ICT, the Institute of Information and Communications Technology Planning and Evaluation, and the National Research Foundation of Korea.