Chemotherapy planning and multi-appointment scheduling: formulations, heuristics and bounds

The number of new cancer cases is expected to increase by about 50% in the next 20 years, and the need for chemotherapy treatments will increase accordingly. Chemotherapy treatments are usually performed in outpatient cancer centers where patients affected by different types of tumors are treated. The treatment delivery must be carefully planned to optimize the use of limited resources, such as drugs, medical and nursing staff, consultation and exam rooms, and chairs and beds for the drug infusion. Planning and scheduling chemotherapy treatments involve different problems at different decision levels. In this work, we focus on the patient chemotherapy multi-appointment planning and scheduling problem at an operational level, namely the problem of determining the day and starting time of the oncologist visit and drug infusion for a set of patients to be scheduled along a short-term planning horizon. We use a per-pathology paradigm, where the days of the week in which patients can be treated, depending on their pathology, are known. We consider different metrics and formulate the problem as a multi-objective optimization problem tackled by sequentially solving three problems in a lexicographic multi-objective fashion. The ultimate aim is to minimize the patient's discomfort. The problems turn out to be computationally challenging, thus we propose bounds and ad-hoc approaches, exploiting alternative problem formulations, decomposition, and $k$-opt search. The approaches are tested on real data from an Italian outpatient cancer center and outperform state-of-the-art solvers.Comment: 28 pages, 3 figure