Scenario-to-Zone Assignment and Route Planning for Autonomous Vehicle Testing: Hybrid Genetic Algorithm-Integer Programming Approach

Abstract

This study proposes a hybrid optimization framework for efficient execution planning of scenario-based autonomous vehicle (AV) testing in physical proving grounds. Using K-City, Korea’s national AV testbed, as a case study, the framework addresses the practical challenge of executing many predefined scenarios under spatial feasibility constraints and operational limitations. A genetic algorithm (GA) is integrated with an integer programming (IP) model to jointly determine scenario-to-zone assignments and execution routes, explicitly capturing the dependency between scenario allocation and routing efficiency. Unlike conventional sequential approaches, IP-based route optimization is embedded within the GA fitness evaluation, allowing route cost to directly guide the search process. The methodology was validated on both a simplified grid network and the full K-City road network comprising 47 scenarios. Results showed substantial reductions in total travel distance compared with a naive sequential baseline, demonstrating the effectiveness of the integrated approach. To reflect real testing conditions, execution constraints on the number of scenarios per cycle were incorporated, producing repeatable and operationally feasible routes. The proposed framework improves execution efficiency and consistency and can be readily adapted to other AV testbeds with similar constraints.