A new column-generation-based algorithm for VMAT treatment plan optimization

Let K denote the total number of (not necessarily equispaced) control points along one or more treatment arc(s) (in the case of multiple arcs, K represents the total number of control points along all arcs, which will be ordered so that the first control point on the second arc succeeds the last control point on the first arc, etc). We associate with each control point k an aperture A_k, a dose rate r_k (in MU s⁻¹), and a gantry speed s_k (in deg s⁻¹). In addition, we can express the fluence rate (in MU deg⁻¹) at control point k as y_k = r_k/s_k. Note that each control point represents a snapshot of the continuous gantry rotation, i.e. r_k, s_k, y_k and A_k represent the state of the treatment machine as the gantry passes through control point k. For convenience, we will add a dummy control point K + 1 at the end of the arc. For tractability, we will then calculate the dose delivered to each voxel by making the approximation that the aperture, dose rate and gantry speed (and hence fluence rate) are constant throughout the arc spanning from one control point to the next. Note in particular that this means that we do not need to specify any of the variables at the dummy control point K + 1. If the angular distances δ_k between pairs of control points k and k + 1 are small, then this approximation will be sufficiently accurate (Otto 2008).

The gantry speeds and apertures specified at consecutive control points need to be compatible with each other. This compatibility requirement derives from the characteristics of the MLC system used to form the apertures during the treatment. As the gantry travels from control point k to control point k + 1, the leaves of the MLC system need to shift from positions prescribed by aperture A_k to those prescribed by aperture A_{k + 1}. Since the speed of such leaf movement is bounded, the time spent by the gantry moving between the control points needs to be sufficiently large (and hence its speed sufficiently small) to allow for the required leaf movement to take place. We will denote the maximum gantry speed that will allow aperture A' at control point k + 1 to be reached from aperture A at control point k by S^U_{k, k + 1}(A, A') for k = 1, ..., K, where, for convenience, S^U_{K, K + 1}(A, A') = ∞ for all pairs of apertures A and A'.

In addition to the discretization parameters δ_k (k = 1, ..., K), there are several other machine parameters that need to be taken into account. First, a VMAT delivery machine may have upper and lower bounds on gantry speed (denoted by S^U and S^L), and an upper bound on dose rate (denoted by R^U). Furthermore, there typically is an upper bound on the rate of change in speed that the gantry can sustain, which may be given per degree or per control point. We will denote the upper bound on the change in speed between control points k and k + 1 by ΔS_k. Finally, we let $\mathcal {A}$ denote the set of all apertures that are deliverable by the MLC system. In particular, we will assume that left and right leaves within each pair can be positioned at any non-overlapping continuous points within their range, and that motion is independent between leaf pairs. In particular, we assume that there are no interdigitation constraints. After formulating our base model and developing our algorithm, we will discuss how additional constraints, such as a lower bound on dose rate, independent bounds on the fluence rate and interdigitation constraints, can be incorporated into our solution approach when necessary.

Finally, let the discretized set of voxels be $\mathcal {V}$, and denote the delivered dose distribution by $\mathbf {z}=(z_{j}:j\in \mathcal {V})^{\top }$, where z_j is the total dose delivered to voxel $j\in \mathcal {V}$. The quality of the dose distribution z is evaluated using an objective function $F:\mathbb {R}^{|\mathcal {V}|}\rightarrow \mathbb {R}$. Under our approximation, z_j is equal to the sum of the doses delivered to the voxel from all control points. Moreover, since the delivered dose is linear in fluence, it is convenient to denote the dose received by voxel $j\in \mathcal {V}$ from aperture $A\in \mathcal {A}$ at control point k at unit fluence by D_kj(A) (k = 1, ..., K).

The complete VMAT optimization model, which we refer to as the full problem (FP), then reads:

$$\begin{equation} \begin{array}{lll}{\rm (FP)\ }{\rm minimize } &F(\mathbf {z}) & \\\ms \quad\quad\hbox{subject to}&&\\\ms &z_j = \sum\limits _{k=1}^{K} D_{kj}(A_k) \delta _{k} y_k &j \in \mathcal {V}\\\ms & y_k = \dsty\frac{r_k}{s_k}& k =1,\ldots ,K \\\ms & |s_k-s_{k+1}| \le \Delta S_{k} &k =1,\ldots , K-1 \\\ms & s_k\in [S^{L}, S^{U}]& k =1,\ldots , K \\\ms & r_k \in [ 0, R^{U}] &k =1,\ldots , K \\\ms & s_k \le S_{k,k+1}^{U}(A_k,A_{k+1}) &k =1,\ldots ,K \\\ms & A_{k} \in \mathcal {A}& k =1,\ldots ,K, \end{array} \end{equation} \tag{ 1 }$$

where the terminal aperture A_{K + 1} in (1) can be chosen arbitrarily and is added for convenience only.

We can simplify this model by first noting that for any feasible solution s, r, y, z and (A_k: k = 1, ..., K) of (FP) we can obtain another feasible solution with the same apertures and the same values of y and z (and hence the same objective function value), but with all the gantry speeds at their lower bound value S^L by scaling the dose rates by a factor of S^L/s_k ⩽ 1, k = 1, ..., K, to compensate. As a result, we can eliminate the gantry speed variables from the model. In addition, we can then replace the upper bound constraints on the dose rates by upper bounds on fluence rate and eliminate the dose rate variables as well. The problem thus reduces to the following master problem (MP):

$$\begin{eqnarray} \begin{array}{lll} {\rm (MP)\ }{\rm minimize } &F(\mathbf {z}) & \\ \quad\;\;\,\;\,\ \,\hbox{subject to}&& \\ &z_j = \sum \limits_{k=1}^{K} D_{kj}(A_k) \delta _{k} y_k &j \in \mathcal {V} \end{array}\nonumber\\&&[-18pt] \end{eqnarray} \tag{ 2 }$$

$$\begin{eqnarray} \qquad\qquad\qquad \, y_k \in [ 0, Y^{U}] &\;\,\; k =1,\ldots , K \nonumber \\ \qquad\qquad\qquad \, S^L \le S_{k,k+1}^{U}(A_k,A_{k+1}) &\;\,\; k =1,\ldots ,K \end{eqnarray} \tag{ 3 }$$

$$\begin{eqnarray} &&\qquad\qquad\qquad \, A_{k} \in \mathcal {A}\qquad\qquad\quad\;\, k =1,\ldots ,K, \end{eqnarray} \tag{ 4 }$$

where Y^U ≡ R^U/S^L. We will refer to (MP) as the master problem, for reasons made clear in the following section. By construction, for any feasible solution to (MP) we can construct an equivalent feasible solution to (FP), in the sense that it has the same apertures and values of y and z, by setting s_k = S^L and r_k = y_ks_k for k = 1, ..., K. Moreover, there may be several combinations of gantry speeds and dose rates that lead to equivalent solutions to (FP), and some may be more desirable than others, e.g., due to shorter treatment times. We will discuss this in more detail in section 2.5.

Note that (MP) is not convex because of the nonlinearities associated with the apertures in constraints (2)–(4). Therefore, instead of solving problem (MP) exactly, we propose a column-generation-based algorithm.

Our proposed algorithm starts with a dose distribution z = 0 and without an aperture specified at any of the control points. The algorithm then proceeds by, in each iteration, attempting to improve the current treatment plan and dose distribution by selecting an aperture at one of the control points for which none has been specified yet (that is, generating a column in constraint (2) of (MP)), and terminates when a completely specified treatment plan is obtained. In any given iteration, which is characterized by a set $\mathcal {C}\subseteq \lbrace 1,\ldots ,K\rbrace$ of control points and the corresponding collection of apertures $\lbrace \bar{A}_{k},\ k\in \mathcal {C}\rbrace$, we optimize fluence rates of these apertures by solving the so-called restricted master problem (RMP). The RMP is constructed so that a feasible solution to this problem implicitly provides a deliverable plan that can be fully specified by feasibly completing the sequence of apertures while retaining the current aperture fluence rates (in particular, y_k = 0 for $k\not\in \mathcal {C}$). The optimal solution to the RMP then defines the so-called pricing problem (PP) which is used to select the next control point and aperture to be added to the plan. The intuition behind the PP is that, relative to the current solution, each candidate aperture at each control point $k\not\in \mathcal {C}$ has an associated price which is defined as the rate of improvement in the objective function value if the fluence rate of that aperture is increased (from its current value of 0). The PP then finds the control point/aperture combination that has the best price. In contrast with direct aperture optimization for IMRT treatment planning (Preciado-Walters et al 2004, Romeijn et al 2005, Shepard et al 2002), only a single aperture is added for each control point. This makes our algorithm heuristic in nature and, in particular, a greedy heuristic.

More formally, our algorithm can be described as follows:

Column generation based greedy heuristic for (MP)

•   
  Step 0 Set $\mathcal {C}=\varnothing$ and $\bar{\mathbf {z}}=\mathbf {0}$.
•   
  Step 1 Use the information on the current treatment plan (control points $\mathcal {C}$, apertures $\bar{A}_{k}$ for $k\in \mathcal {C}$, and dose distribution $\bar{\mathbf {z}}$) to formulate and solve an instance of the PP.
•   
  Step 2 If the optimal value of the PP is nonpositive, go to step 5. Otherwise, denote the optimal solution to the PP by $\bar{c}$ and $\bar{A}_{\bar{c}}$, and replace $\mathcal {C}$ by $\mathcal {C}\cup \lbrace \bar{c}\rbrace$.
•   
  Step 3 Solve the instance of the RMP associated with $\mathcal {C}$ and $A_{k}=\bar{A}_{k},\ k\in \mathcal {C}$.
•   
  Step 4 If $|\mathcal {C}|<K$, return to step 1.
•   
  Step 5 If necessary, complete the treatment plan by identifying feasible apertures (which will have fluence 0) at control points $c\not\in \mathcal {C}$, and denote the final set of fluence rates by $\bar{y}_{k}$ (k = 1, ..., K).

Figure 1 provides a graphical representation of the structure of this algorithm.

Zoom In Zoom Out Reset image size

In the remainder of this section, we will provide additional details on steps 1–3 of this algorithm in sections 2.3 and 2.4. Section 2.5 discusses obtaining a solution to (FP) based on the solution to (MP) returned by our algorithm. Finally, section 2.6 discusses how additional constraints on the setting of the VMAT delivery machine can be incorporated into (FP) formulation and our solution.

At each iteration of the algorithm, we obtain the RMP from (MP) by fixing the apertures $A_{k}=\bar{A}_{k}$ for all control points in the current set $\mathcal {C}\subseteq \lbrace 1,\ldots ,K\rbrace$ and setting the fluence rates y_k = 0 for all control points $k\not\in \mathcal {C}$. The RMP then reads

$$\begin{eqnarray} \begin{array}{lll} {({\rm RMP}^{(\mathcal {C})})\ \ }{\rm minimize } &F(\mathbf {z}) \\ \qquad\qquad \!\!\kern-1pt\hbox{subject to}\\ &z_j = \sum \limits_{k\in \mathcal {C}} D_{kj}(\bar{A}_k) \delta _{k} y_k &j \in \mathcal {V}\\ & y_k \in [ 0, Y^{U}] &k\in \mathcal {C}. \end{array} \end{eqnarray} \tag{ 5 }$$

(RMP$^{(\mathcal {C})}$) can be thought of as a restriction of (MP) in that it considers a subset of control points, and considers the apertures $\bar{A}_k,\ k\in \mathcal {C}$, to be fixed and given. Note that (RMP$^{(\mathcal {C})}$) is a nonlinear optimization problem with linear constraints, and it is a convex optimization problem provided that F is a convex function.

Recall that any feasible solution to (RMP$^{(\mathcal {C})}$) should correspond to a deliverable plan that can be fully specified by completing the sequence of apertures at control points $k\not\in \mathcal {C}$ in a way that is compatible with apertures $\bar{A}_k,\ k\in \mathcal {C}$, and setting $y_k=0,\ k\not\in \mathcal {C}$. To ensure that this is indeed the case, the set of apertures $\bar{A}_k,\ k\in \mathcal {C}$ in the restricted problem should satisfy the following condition. For all $k\in \mathcal {C}$, let k⁺ be the successor of k in $\mathcal {C}$, i.e. $k^{+}=\min \lbrace k^{\prime }\in \mathcal {C}:k^{\prime }>k\rbrace$, where k⁺ ≡ K + 1 if $k=\max \lbrace k^{\prime }:k^{\prime }\in \mathcal {C}\rbrace$. Any feasible solution to (RMP$^{(\mathcal {C})}$) for any $\mathcal {C}\subseteq \lbrace 1,\ldots ,K\rbrace$ can be extended to a feasible solution to (MP), provided that

$$\begin{equation} S_{kk^{+}}^{U}(\bar{A}_k,\bar{A}_{k^{+}}) \ge S^{L},\ k\in \mathcal {C}. \end{equation} \tag{ 6 }$$

Here we have generalized the notation of (FP) and (MP) by denoting the maximum gantry speed that will allow aperture A' at control point k' to be reached from aperture A at control point k < k' by $S_{kk^{\prime }}^{U}(A,A^{\prime })$ (where again, for convenience, we will let S^U_{k, K + 1}(A, A') = ∞ for all pairs of apertures A and A' and all k = 1, ..., K). The PP described in the following section is designed to ensure that the apertures added at each iteration of the column generation algorithm satisfy (6).

2.4.1. PP derivation

Consider an optimal solution $(\bar{\mathbf {y}},\bar{\mathbf {z}})$ to (RMP$^{(\mathcal {C})}$). Suppose we were to add aperture $A\in \mathcal {A}_{c}$ at a control point $c\not\in \mathcal {C}$, where $\mathcal {A}_{c}\subseteq \mathcal {A}$ is a set of deliverable apertures that can feasibly be added to the current treatment plan. Based on first-order optimality conditions, the rate of improvement (i.e. decrease) in objective function value per unit fluence rate in this aperture can be calculated as

$$\begin{equation*} \boldsymbol \pi _{c}(A) \equiv \sum _{j\in \mathcal {V}} \pi _{j}(\bar{\mathbf {z}}) D_{cj}(A_c) \delta _{c}, \end{equation*}$$

where $(\pi _{j}(\bar{\mathbf {z}}):j\in \mathcal {V})^{\top }=\boldsymbol \pi (\bar{\mathbf {z}}) \equiv -\nabla F(\bar{\mathbf {z}})$. Our strategy will be to select a control point c and aperture A that solve the following optimization problem, which we will refer to as the PP:

$$\begin{equation*} {\rm (PP) } \max _{c\not\in \mathcal {C}} \max _{A\in \mathcal {A}_{c}} \ \ \boldsymbol \pi _{c}(A). \end{equation*}$$

In order to ensure that solutions to PP satisfy condition (6), we need to specify the set $\mathcal {A}_{c}$ in such a way that

$$\begin{equation*} \mathcal {A}_{c} \subseteq \left\lbrace A\in \mathcal {A}: S_{c^-c}^{U}(\bar{A}_{c^-},A) \ge S^{L},\ S_{cc^{+}}^{U}(A,\bar{A}_{c^{+}}) \ge S^{L}\right\rbrace \equiv \mathcal {A}_{c}^{U}. \end{equation*}$$

The choice of $\mathcal {A}_{c}\subseteq \mathcal {A}_{c}^{U}$ in the PP dictates a tradeoff in the behavior of our heuristic algorithm. On the one hand, choosing a smaller set $\mathcal {A}_{c}$ at the current iteration results in lesser flexibility in the current selection of apertures. On the other hand, this can potentially allow for more flexibility in later iterations of the heuristic. We will consider the following family of potential choices for $\mathcal {A}_{c}$ in (PP), parameterized by a lower bound s on the speed between two control points:

$$\begin{equation} \mathcal {A}_{c}(s) = \left\lbrace A\in \mathcal {A}: S_{c^-c}^{U}(\bar{A}_{c^-},A) \ge s,\ S_{cc^{+}}^{U}(A,\bar{A}_{c^{+}}) \ge s \right\rbrace\ {\rm for }\ s\ge S^{L}. \end{equation} \tag{ 7 }$$

It is easy to see that $A_{c}(s^{\prime })\subseteq \mathcal {A}_{c}(s)$ whenever s' ⩾ s, with $A_{c}(S^{L})=\mathcal {A}_{c}^{U}$. Note also that, although the choice of s does not explicitly determine the final gantry speed used at different control points, because it affects the selection of apertures $\mathcal {A}_{c}(s)$, it implicitly affects the final gantry speed and thus the delivery time. We will explore the impact of the choice of parameter s on the overall performance of the algorithm in our experiments.

If the optimal value of (PP) is non-positive, we conclude that the current solution cannot be improved by adding any aperture at any control point (at least in the framework of our algorithm). In this case, the algorithm will be terminated (see step 2), and fluence rates at control points $k\not\in \mathcal {C}$ will remain at zero. However, if an improving control point/aperture is found, the algorithm will proceed to step 3.

2.4.2. Solving the PP

We will now describe a solution approach for the PP. First, it is easy to see that this problem decomposes into a collection of independent problems for the different candidate control points c, so that we can focus on the problem for a given $c\not\in \mathcal {C}$:

$$\begin{equation*} {({\rm PP}^{(c)}) } \max _{A\in \mathcal {A}_{c}}\ \ \sum _{j\in \mathcal {V}} \pi _{j}(\bar{\mathbf {z}}) D_{cj}(A), \end{equation*}$$

where we have also eliminated the scaling constant δ_c.

Next, in the absence of interdigitation constraints, we can decompose PP^(c) by MLC row. In particular, if the MLC system consists of M leaf pairs, we can represent any aperture $A\in \mathcal {A}$ as a collection of leaf settings for its individual rows. Let us denote an aperture by A = (a₁, ..., a_M), where a_m ∈ α describes the leaf settings of MLC row m of aperture A, and α is the set of deliverable 'row apertures'. The set $\mathcal {A}_{c}$ can be written as $\mathcal {A}_{c} = \sf {X}_{m=1}^{M} \mathcal {A}_{cm}$, with

$$\begin{equation} \mathcal {A}_{cm}\subseteq \left\lbrace a: S_{c^-c}^{U}(\bar{a}_{c^-m},a) \ge S^{L},\ S_{cc^{+}}^{U}(a,\bar{a}_{c^{+}m}) \ge S^{L} \right\rbrace , \end{equation} \tag{ 8 }$$

where $\bar{a}_{km}$ is the mth row aperture of $\bar{A}_{k}$ at control point $k\in \mathcal {C}$ and, with a slight abuse of notation, S^U_kc(a, a') denotes the maximum gantry speed that will allow row aperture a' of aperture A' at control point c to be reached from row aperture a at control point k < c. Let D_cmj(a) denote the dose received by voxel $j\in \mathcal {V}$ from row aperture a ∈ α in row m and control point c at unit fluence rate, with D_cj(A) = ∑^M_{m = 1}D_cmj(a_m). The pricing problem (PP^(c)) can then be decomposed by row:

$$\begin{equation*} {({\rm PP}^{({\rm cm})}) } \max _{a\in \mathcal {A}_{cm}}\ \ \sum _{j\in \mathcal {V}} \pi _{j}(\bar{\mathbf {z}}) D_{cmj}(a). \end{equation*}$$

Recall that we would like to consider the family of feasible regions $\mathcal {A}_c=\mathcal {A}_{c}(s)$ defined by (7) for s ⩾ S^L. The corresponding family $\mathcal {A}_{cm}(s)$ of feasible regions for (PP^(cm)) is

$$\begin{equation} \mathcal {A}_{cm}(s)=\left\lbrace a: S_{c^-c}^{U}(\bar{a}_{c^-m},a) \ge s,\ S_{cc^{+}}^{U}(a,\bar{a}_{c^{+}m}) \ge s \right\rbrace\ {\rm for\ }s\ge S^{L}. \end{equation} \tag{ 9 }$$

Let us analyze the structure of these sets in more detail. Any row aperture a can be characterized as a pair of leaf settings (ℓ, r), where 0 ⩽ ℓ ⩽ r ⩽ N are the positions of the left and right leaves, respectively (N, which we assume to be integer, is the range of the MLC row). Furthermore, let v denote the maximum leaf speed (in distance/second, with the unit of distance depending on the choice of N). Then, for k < c,

$$\begin{equation*} \fl \left\lbrace a\in \alpha :S_{kc}^{U}(a,a^{\prime })\ge s\right\rbrace = \left\lbrace (\ell ,r): 0\le \ell \le r\le N;\ |\ell -\ell ^{\prime }|,|r-r^{\prime }|\le \frac{v\delta _{kc}}{s}\right\rbrace , \end{equation*}$$

where $\delta _{kc}=\sum _{k^{\prime }=k}^{c-1}\delta _{k^{\prime }}$. Therefore,

$$\begin{eqnarray} &&\mathcal {A}_{cm}(s)=\bigg \lbrace (\ell ,r):\bigg . 0\le \ell \le r\le N;\ |\ell -\bar{\ell }_{c^-m}|,|r-\bar{r}_{c^-m}|\le \frac{v\delta _{c^-c}}{s}; \nonumber\\ &&\left. |\ell -\bar{\ell }_{c^{+}m}|,|r-\bar{r}_{c^{+}m}|\le \frac{v\delta _{cc^{+}}}{s} \right\rbrace , \end{eqnarray} \tag{ 10 }$$

with the appropriate and obvious definitions of $(\bar{\ell }_{c^-m},\bar{r}_{c^-m})$ and $(\bar{\ell }_{c^{+}m},\bar{r}_{c^{+}m})$. Thus, the set $\mathcal {A}_{cm}(s)$ is simply the set of all (ℓ, r) such that 0 ⩽ ℓ ⩽ r ⩽ N and with upper and lower bounds on ℓ and r which get tighter as s increases.

Finally, in order to fully specify (PP^(cm)), we need to characterize D_cmj(a) = D_cmj(ℓ, r). Specifying D_cmj(ℓ, r) as a function of continuous variables (ℓ, r) will require an immense amount of data. Instead, we use a common approximation obtained by discretizing each MLC row into N beamlets (thus specifying an appropriate MLC row range), where beamlet n represents the interval [n − 1, n]. We then precompute traditional beamlet-based dose deposition coefficients D_cmnj, i.e. the dose rate to voxel $j\in \mathcal {V}$ from beamlet n in MLC row m at control point c (n = 1, ..., N, m = 1, ..., M, c = 1, ..., K) at unit fluence rate and make the following approximation:

$$\begin{equation*} D_{cmj}(\ell ,r) = \int _{\ell }^{r} \phi _{cmj}(x)\, {\rm d}x, \end{equation*}$$

where $\phi _{cmj}:[0,N]\rightarrow \mathbb {R}^{+}$ is the following step function:

$$\begin{equation*} \phi _{cmj}(x) = D_{cmnj},\ n-1<x\le n;\ n=1,\ldots ,N. \end{equation*}$$

To summarize, the pricing problem (PP^cm) with $\mathcal {A}_{cm}=\mathcal {A}_{cm}(s)$ can be written as

$$\begin{equation} \max _{(\ell ,r)\in \mathcal {A}_{cm}(s)}\ \ \int _{\ell }^{r} \boldsymbol \pi _{cm}(x;\bar{\mathbf {z}}) \,{\rm d}x, \end{equation} \tag{ 11 }$$

where

$$\begin{equation*} \boldsymbol \pi _{cm}(x;\bar{\mathbf {z}}) = \sum _{j\in \mathcal {V}} \pi _{j}(\bar{\mathbf {z}}) \phi _{cmj}(x). \end{equation*}$$

The problem (11) can be solved efficiently by noting that the only candidate values for ℓ and r that have to be considered are (i) integers, and (ii) the bounds derived from (10).

Our column generation algorithm will return a feasible solution $\bar{\mathbf {y}},\bar{\mathbf {z}}$ and $\bar{A}_k,\ k=1,\ldots ,K$ to the problem (MP). As a final step of our solution procedure, we need to compute gantry speed and dose rate vectors s and r consistent with this solution. Substituting the apertures and fluence rates into constraints of (FP), we need to find a feasible solution to the following system:

$$\begin{equation} \bar{y}_k = \frac{r_k}{s_k}\qquad k =1,\ldots ,K \end{equation} \tag{ 12 }$$

$$\begin{equation} |s_k-s_{k+1}| \le \Delta S_{k} \qquad k =1,\ldots , K-1 \end{equation} \tag{ 13 }$$

$$\begin{equation} s_k \in [S^{L}, S^{U}]\qquad k =1,\ldots , K \end{equation} \tag{ 14 }$$

$$\begin{equation} r_k \in [ 0, R^{U}]\qquad k =1,\ldots , K \end{equation} \tag{ 15 }$$

$$\begin{equation} s_k \le S_{k,k+1}^{U}(\bar{A}_k,\bar{A}_{k+1})\qquad k =1,\ldots ,K. \end{equation} \tag{ 16 }$$

This system has a feasible solution since the apertures and fluence rates computed by the algorithm are guaranteed to be compatible with the gantry moving at speed S^L. However, this solution would lead to a treatment with undesirably long delivery time. Instead, we would like to identify a solution to (12)–(16) that can be delivered in the shortest time possible. Adding this objective function and rewriting constraints (12)–(16) in terms of the gantry speeds only, we obtain the following convex optimization problem:

$$\begin{eqnarray} \begin{array}{lll} {\rm (SP)\ }\ {\rm minimize } &\sum \limits_{k=1}^K \dsty\frac{\delta _{k}}{s_k} \\\ms \qquad\hbox{subject to}&\\\ms &s_{k} \in [S^{L},S^{U}_{k}] & k =1,\ldots , K \\\ms &|s_k-s_{k+1}| \le \Delta S_{k} & k =1,\ldots , K-1, \end{array}\nonumber\\&&[-16pt] \end{eqnarray} \tag{ 17 }$$

where

$$\begin{equation*} S^{U}_{k} = \min \left\lbrace S^{U} , S_{k,k+1}^{U}(\bar{A}_k,\bar{A}_{k+1}) , \frac{R^{U}}{\bar{y}_{k}}\right\rbrace ,\ k =1,\ldots ,K. \end{equation*}$$

If $\bar{\mathbf {s}}_{k}$ is an optimal solution to this problem, then the corresponding dose rates are $\bar{r}_{k} = \bar{y}_{k}\bar{s}_{k}$, k = 1, ..., K.

In order to assess the impact on delivery time of the bound on the change in speed we will also consider a relaxation of (SP) in which constraints (17) are removed. It is easy to see that the corresponding solution will be to choose s_k = S^U_k and $r_{k}=\bar{y}_{k}S_{k}^{U}$ (for k = 1, ..., K).

We conclude this section by discussing how additional constraints on the setting of the VMAT delivery machine can be incorporated into the model (FP), its reformulation (MP) and our solution heuristic.

2.6.1. Upper bound on fluence rate

2.6.2. Lower bounds on fluence and dose rates

2.6.3. Interdigitation and other MLC constraints

Lastly, consider a VMAT delivery system that does not allow interdigitation of MLC leaves in adjacent rows. The main impact of this constraint is a modification of the solution process of the PP discussed in section 2.4.2.

Before discussing the required modification, we will argue that if interdigitation constraints are satisfied in each iteration of the algorithm (i.e. for all apertures $\bar{A}_k,\ k\in \mathcal {C}$), and we obtain a VMAT plan by linearly interpolating these apertures between control points in $\mathcal {C}$, then the interdigitation constraints will also hold for MLC apertures throughout the treatment. To obtain the interpolation, we assume that both the gantry and each of the leaves move at constant speeds between two consecutive control points. Let us examine two adjacent MLC rows m and m + 1 at two control points k and k⁺. We assume that

$$\begin{equation} \bar{\ell }_{km} \le \bar{r}_{k,m+1}\ {\rm and }\ \bar{\ell }_{k^+m} \le \bar{r}_{k^+,m+1}, \end{equation} \tag{ 18 }$$

i.e. the left leaf in row m and the right leaf in row m + 1 do not overlap at either control point, and denote the time it takes the gantry to rotate from k to k⁺ by Δt. At an intermediate time t ∈ (0, Δt), with the gantry at location c: k < c < k⁺, the leaf positions are computed by linear interpolation as follows:

$$\begin{equation*} \ell _{m} = \bar{\ell }_{km}+ (\bar{\ell }_{k^+m}-\bar{\ell }_{km})\cdot \frac{t}{\Delta t } = \bar{\ell }_{km}\cdot \frac{\Delta t -t}{\Delta t }+ \bar{\ell }_{k^+m}\cdot \frac{t}{\Delta t } \end{equation*}$$

and

$$\begin{equation*} r_{m+1}= \bar{r}_{k,m+1}+ (\bar{r}_{k^+,m+1}-\bar{r}_{k,m+1})\cdot \frac{t}{\Delta t } =\bar{r}_{k,m+1}\cdot \frac{\Delta t -t}{\Delta t }+ \bar{r}_{k^+,m+1}\cdot \frac{t}{\Delta t }. \end{equation*}$$

It is easy to see that because of (18), we have ℓ_m ⩽ r_{m + 1}; using the same technique, we can show that ℓ_{m + 1} ⩽ r_m, assuming same is true at control points k and k + 1. Thus, at any location between the control points, the interdigitation constraints are satisfied.

Now we study the impact of the interdigitation constraints on the PP. Because of the dependence between individual MLC rows created by these constraints, we cannot no longer decompose the problem PP^(c) by row. As before, we characterize row aperture a_m ∈ α at MLC row m of aperture A by (ℓ_m, r_m) where 0 ⩽ ℓ_m ⩽ r_m ⩽ N and the (integer) N represents the range of the MLC row, and denote by S^U_kc(a'_m, a_m) the maximum gantry speed that will allow row m of aperture A = (a₁, ..., a_M) at a control point c to be reached from row m of aperture A' = (a'₁, ..., a'_M) at control point k < c. To incorporate the interdigitation constraints, we add the inequalities

$$\begin{equation} \ell _{m}\le \min \lbrace r_{m+1},r_{m-1} \rbrace ,\ m=1,\ldots ,M \end{equation} \tag{ 19 }$$

to the description of the set A_c(s) in (7), where we let r₀ = r_{M + 1} = ∞. By construction, A_c(s) ≠ ∅ throughout the algorithm.

The PP for $c\notin \mathcal {C}$ under interdigitation constraints can then be written as

$$\begin{eqnarray} \fl \begin{array}{lll} {({\rm PPI}^{(c)})\ }{\rm maximize} &\sum\limits _{j\in \mathcal {V}} \pi _{j}(\bar{\mathbf {z}}) \sum\limits _{m=1}^{M} D_{cmj}(\ell _m,r_m)& \\ \quad\qquad\hbox{subject to}&& \\ & 0 \le \ell _{m}\le r_{m}\le N & m=1,\ldots ,M\\ &|\ell _m-\bar{\ell }_{c^-m}|,|r_m-\bar{r}_{c^-m}|\le \dsty\frac{v\delta _{c^-c}}{s} & m=1,\ldots ,M \end{array}\nonumber\\&&[-20pt] \end{eqnarray} \tag{ 20 }$$

$$\begin{eqnarray} &&|\ell _m-\bar{\ell }_{c^{+}m}|,|r_m-\bar{r}_{c^{+}m}|\le \frac{v\delta _{cc^{+}}}{s}\qquad m=1,\ldots ,M \\ &&\ell _{m}\le \min \lbrace r_{m+1},r_{m-1}\rbrace\qquad m=1,\ldots ,M\nonumber \nonumber , \end{eqnarray} \tag{ 21 }$$

where D_cmj(ℓ_m, r_m), as before, is approximated by an integral of the beamlet-based step function $\phi _{cmj}:[0,N]\rightarrow \mathbb {R}^{+}$. Given this discretization of each MLC row into beamlets, this version of the PP can still be solved efficiently using a dynamic programming approach described in Romeijn et al (2005), with potential left and right leaf positions including integers and bounds in (20) and (21).

Our algorithm was evaluated on a clinical dataset of prostate cancer patients treated at UCSD Moores Cancer Center. The preprocessing steps, including image processing and calculation of the dose deposition coefficients D_cmnj are performed using our in-house treatment planning system. The dose calculations in this system are based on a finite-sized pencil-beam algorithm with 3D density correction (Gu et al 2009a, 2009b). For each case, we used beamlets of size 1 × 1 cm² and voxels of size 4 × 4 × 2.5 mm³. However, in order to reduce its size, the optimization problem used a downsampled voxel grid that selected one of every two voxels along each of the three dimensions in critical structures and one of every four in unspecified tissue. The dimensions (after downsampling) and other characteristics of the five cases are summarized in table 1. Figure 2 illustrates the distribution of control points around the arc. For all cases we used K = 176 control points, and the angular distances between control points are shown in table 1. Finally, the machine parameters we used are based on the Varian RapidArc machine (Varian Medical Systems, Inc., Palo Alto, CA, USA) and are shown in table 2 (where ΔS_k = ΔS for all k = 1, ..., K).

Zoom In Zoom Out Reset image size

Table 1. Problem dimensions of different cases (after downsampling).

Case	No. of voxels	No. of beamlets	No. of Dcmnj ≠ 0	δk (k = 2, ..., 175)	δ1, δ176
1	13 047	21 417	89 360 831	$\frac{330}{175}$	$\frac{1}{2}\cdot \frac{330}{175}$
2	10 130	17 700	63 359 780	$\frac{330}{175}$	$\frac{1}{2}\cdot \frac{330}{175}$
3	12 102	29 913	106 889 530	$\frac{330}{175}$	$\frac{1}{2}\cdot \frac{330}{175}$
4	9602	21 417	79 889 713	$\frac{330}{175}$	$\frac{1}{2}\cdot \frac{330}{175}$
5	13 769	25 488	114 315 187	$\frac{340}{175}$	$\frac{1}{2}\cdot \frac{340}{175}$

The prescription dose to the PTV was set to 79.2 Gy, corresponding to a 44-fraction treatment with 1.8 Gy delivered in each fraction. All dose–volume histogram (DVH)-based criteria for the PTV and critical structures, in particular rectum, bladder and femoral heads, that were used to evaluate all treatment plans are based on clinical protocols at UCSD as well as RTOG protocol Radiation Therapy Oncology Group (2004) (see the tables in the remainder of this section for details). In our optimization model, we chose F to be a voxel-based penalty function that penalizes the dose received by a voxel quadratically but asymmetrically with respect to a threshold dose that depends on the structure containing the voxel; consequently, F is a smooth piece-wise quadratic convex function. The structure-dependent relative weights of these penalty functions were determined using a manual procedure that iteratively modified these weights until satisfactory treatment plans were obtained for all five cases. This led to a common set of weights for all cases, thereby eliminating variation between cases caused by individual parameter tuning. In order to facilitate the comparison between the treatment plans, we normalized each treatment plan by scaling the dose distribution so that 95% of the PTV receives the prescription dose.

Finally, we implemented our algorithm using the CUDA to take advantage of the processing power of the GPU. CUDA is a platform for the implementation of large-scale parallelization of computer code, and has been shown to be very suitable for solving radiation therapy treatment plan optimization problem (Men et al 2009, 2010a, 2010b). The RMP is solved using our in-house gradient-based solver. On an Nvidia Tesla C1060 GPU card, our algorithm takes 22–55 s to complete. The high efficiency of our VMAT optimization engine provides a significant step toward a clinical application of VMAT for adaptive radiotherapy, although of course a treatment planning system for adaptive radiotherapy would contain several additional components.

Before evaluating our VMAT treatment plans, we provide a benchmark for comparison by solving an IMRT treatment plan optimization problem with the same objective function as (FP) and using the K + 1 = 177 beam angles that correspond to control points in the VMAT treatment plan optimization model. These IMRT plans are used to assess the quality of our VMAT plans and are not suitable for clinical use due to the unreasonably long time required to deliver an IMRT plan with 177 beam angles. Since the IMRT treatment plan optimization model allows intensity modulation at each beam angle and contains no constraints on aperture compatibility nor gantry speed, they can be viewed as an ideal, likely clinically unattainable, solution. Therefore, any VMAT treatment plan that is close to this ideal IMRT treatment plan will also be close to the optimal VMAT treatment plan.

Table 3 includes the clinical dose–volume criteria and the 177-beam IMRT plans evaluated with these criteria for all five cases. All plans are able to avoid significant hot and cold spots in the PTV, and are able to satisfy most of the DVH criteria for the critical structures. For case 2, 14% of the bladder volume and 18% of the rectum volume overlap with the PTV, and for case 4 almost 30% of the bladder volume overlaps with the PTV. For these patients, even additional patient-dependent parameter tuning did not allow us to resolve the violations highlighted in the table without introducing more serious ones.

As discussed in section 2.4.1, the column generation heuristic is parameterized by the parameter s, which represents how 'greedy' the heuristic is. Moreover, since the choice of s affects the choice of $\bar{A}_k$, which affects S^U_k in the time-minimization problem (SP), it also impacts the delivery time of the final treatment plans. In this section we test our heuristic under various settings of s, and study the performance of the resulting treatment plans in terms of quality and delivery time.

3.3.1. The most greedy heuristic

3.3.2. Effect of the value of s on treatment quality and time

3.3.3. Least greedy heuristic

3.3.4. VMAT treatment plan quality as compared to benchmark

Figure 3 shows the DVHs of the 177-beam IMRT and VMAT (with s = S^U = 6) treatment plans for case 2. As can be gleaned from the corresponding tables, the largest differences in these plans are with respect to the dose distribution in the femoral heads, but these are still well within the clinical protocol. Given the restrictions that VMAT delivery imposes on a treatment plan, we feel that the quality of the VMAT plan is not only clinically acceptable, but also high since the degradation from the idealized 177-beam IMRT plan is relatively small.

Zoom In Zoom Out Reset image size

3.3.5. Disallowing interdigitation

3.3.6. Rate of change in gantry speed

Finally, we investigate the effect of the constraint on the rate of change in gantry speed on treatment time. As discussed in section 2.5, we can assess the impact of the rate of change restriction by removing the corresponding constraint (17) from problem (SP). As before, we focus this study on case 2.

Figure 4 plots the gantry speeds and dose rates for control points 1–176 for case 2. Graphs (a-1) and (b-1) show gantry speeds, and (a-2) and (b-2) show dose rates, obtained by setting s = S^U = 6 in the column generation algorithm, with rate of change constraint (17) omitted for graphs (a-1) and (a-2), but included for graphs (b-1) and (b-2). Graphs (c-1)–(d-2) contain analogous results with s = 4. It is clear that without a constraint on the rate of change, the gantry speed changes rapidly during the treatment in order to extend the time spent at apparently favorable control points while limiting the time spent at less favorable ones. Note as well that at most control points, the speed remains equal to the value s used in the column generation algorithm even after solving (SP).

Zoom In Zoom Out Reset image size

When the rate of change constraint is enforced, as in parts (a-1) and (c-1), the sequence of speeds is smoothened so that the change in speed between control points is no more than ΔS_k. Note that, as discussed in section 2.5, the rate of change constraint does not have any impact on treatment plan quality. However, if it were technologically feasible to increase or eliminate the bound on the rate of change in gantry speed, the treatment time could be shortened by about 30% to less than 1.5 min, as shown in table 8.

Table 8. Impact of the presence of the bound ΔS on the rate of change in gantry speed on treatment time.

	Case
Treatment time (s)	1	2	3	4	5
Without bound	86.0	88.0	84.3	85.4	86.2
With bound	128.1	128.4	121.7	121.7	122.5