A hybrid column generation and simulated annealing algorithm for direct aperture optimization

The purpose of this work was to develop a hybrid column generation (CG) and simulated annealing (SA) algorithm for direct aperture optimization (H-DAO) and to show its effectiveness in generating high quality treatment plans for intensity modulated radiation therapy (IMRT) and mixed photon-electron beam radiotherapy (MBRT). The H-DAO overcomes limitations of the CG-DAO with two features improving aperture selection (branch-feature) and enabling aperture shape changes during optimization (SA-feature). The H-DAO algorithm iteratively adds apertures to the plan. At each iteration, a branch is created for each field provided. First, each branch determines the most promising aperture of its assigned field and adds it to a copy of the current apertures. Afterwards, the apertures of each branch undergo an MU-weight optimization followed by an SA-based simultaneous shape and MU-weight optimization and a second MU-weight optimization. The next H-DAO iteration continues the branch with the lowest objective function value. IMRT and MBRT treatment plans for an academic, a brain and a head and neck case generated using the CG-DAO and H-DAO were compared. For every investigated case and both IMRT and MBRT, the H-DAO leads to a faster convergence of the objective function value with number of apertures compared to the CG-DAO. In particular, the H-DAO needs about half the apertures to reach the same objective function value as the CG-DAO. The average aperture areas are 27% smaller for H-DAO than for CG-DAO leading to a slightly larger discrepancy between optimized and final dose. However, a dosimetric benefit remains. The H-DAO was successfully developed and applied to IMRT and MBRT. The faster convergence with number of apertures of the H-DAO compared to the CG-DAO allows to select a better compromise between plan quality and number of apertures.