Radiotherapy is one of the most widely used treatments in cancer care. One of the main problems in radiotherapy is finding an optimal schedule for the radiation delivered to each patient. This is a complex problem that has a major impact on patient outcomes and the use of healthcare resources. This paper tackles the radiotherapy scheduling problem by (i) proposing a modified 1D Bin Packing Problem formulation, (ii) solving it with an Integer Linear Programming model with two different solvers (SCIP and SAT solver), and with a Constraint Programming model with CP-SAT solver, (iii) solving the same problem by using two Grouping Genetic Algorithm (GGAs) with custom crossover and mutation methods, and finally (iv) comparing all these approaches. The results show that, while GGAs are faster than SCIP and comparable to SAT in terms of execution time, they are slower than CP. In terms of solution quality, GGAs consistently achieve feasible solutions, outperforming SCIP, which fails to find feasible solutions within the time limit, but find slightly worse solutions than those found by SAT and CP.
Addressing Radiotherapy Scheduling with a Bin Packing Problem Formulation: A Comparative Study of Exact Solvers and Genetic Algorithms
Rambaldi Migliore C. C.;Iacca G.
2025-01-01
Abstract
Radiotherapy is one of the most widely used treatments in cancer care. One of the main problems in radiotherapy is finding an optimal schedule for the radiation delivered to each patient. This is a complex problem that has a major impact on patient outcomes and the use of healthcare resources. This paper tackles the radiotherapy scheduling problem by (i) proposing a modified 1D Bin Packing Problem formulation, (ii) solving it with an Integer Linear Programming model with two different solvers (SCIP and SAT solver), and with a Constraint Programming model with CP-SAT solver, (iii) solving the same problem by using two Grouping Genetic Algorithm (GGAs) with custom crossover and mutation methods, and finally (iv) comparing all these approaches. The results show that, while GGAs are faster than SCIP and comparable to SAT in terms of execution time, they are slower than CP. In terms of solution quality, GGAs consistently achieve feasible solutions, outperforming SCIP, which fails to find feasible solutions within the time limit, but find slightly worse solutions than those found by SAT and CP.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
