Stochastic tabu search with ranking and selection. An application for physician scheduling

Tabu Search is a metaheuristic search algorithm used to solve complex combinatorial optimization problems. The algorithm is developed to address deterministic problems. However, nowadays the Optimization Research is pushing to model the real situations with more and more accuracy. In many contexts uncertainty cannot be neglected and because of this, methodologies must be adapted to solve stochastic problems. In stochastic combinatorial optimization problems, the time for computation often represents a constraint. This study aims at integrating the Tabu Search algorithm with procedures from Simulation Optimization. A focus is done on Ranking and Selection, the main procedure of interest. First, in the literature review it is shown an overview of the methodologies and it is stressed how little attention has been given to Tabu Search for stochastic problems. Then, two problems have been addressed: a study case on inventory management and a real-world scheduling problem in the healthcare sector. The study case on inventory management face a fictional situation of classic s,S policy for a warehouse, where the arrival time of the customers, the demand and the replenishment time from the supplier have been modelled as stochastic. This specific problem is a common concern in the literature of Operation Research and Industrial Engineering. It has been chosen so to give an insight in the details of the model and the resulting optimization problem. Simulation has been used to deal with the noise. Ranking and Selection has been integrated in the Tabu Search algorithm and the performances of the methodology developed have been compared with the ones of a simple Tabu Search. Finally, a scheduling problem in Centre Intégré de Cancérologie de Laval (Quebec, Canada) has been addressed. Cancer represents one of the major causes of death in Canada and time is a critical resource for radiation therapy centers. The Tabu Search algorithm used to solve the stochastic version of the optimization problem has been improved. To deal with the complexity of the problem, Ranking and Selection has been integrated along with other procedures from Simulation Optimization. The methodologies developed have been able to improve the performances of interest by reducing considerably the computation time to have good solutions for the problem. The application of the methodology developed could be extended to other combinatorial optimization problems in various fields of Optimization Research.

Tabu Search è un algoritmo meta-euristico di ricerca usato per risolvere problemi complessi di ottimizzazione combinatoria. L’algoritmo è sviluppato per affrontare problemi deterministici. Comunque, al giorno d’oggi la Ricerca Operativa sta spingendo a modellare situazioni reali con sempre più accuratezza. In molti contesti l’incertezza non può essere trascurata e di conseguenza le metodologie devono essere adattate a problemi stocastici. Nei problemi stocastici di ottimizzazione combinatoria, il tempo di calcolo rappresenta spesso un limite. Questo studio mira ad integrare l’algoritmo Tabu Search con procedure di Simulation Optimization. Un focus è stato fatto su Ranking and Selection, la principale procedura utilizzata in questo studio. Per prima cosa, nella revisione della letteratura è mostrata una panoramica delle metodologie citate ed è stressato la poca attenzione data a Tabu Search per problemi stocastici. In seguito, due problemi sono stati affrontati: un caso di studio sulla gestione dell’inventario e un problema reale di scheduling nel settore sanitario. Il caso di studio di gestione dell’inventario è legato ad una situazione fittizia di una classica polizza s,S di un magazzino dove il momento di arrivo dei clienti, la domanda e il tempo di rifornimento dal fornitore vengono modellati come stocastici. Questo problema specifico è un argomento molto presente nella letteratura di Ricerca Operativa e Ingegneria Industriale. È stato scelto di affrontare questo problema così da dare una visione dettagliata del modello e del problema di ottimizzazione che ne scaturisce. La simulazione è stata usata per affrontare l’incertezza. Procedure di Ranking and Selection sono state integrate nell’algoritmo Tabu Search e le performance di questa metodologia sviluppata sono state confrontate con quelle di un semplice Tabu Search. Infine, è stato affrontato un problema di scheduling nel Centre Intégré de Cancérologie de Laval (Quebec, Canada). Il cancro rappresenta una delle maggiori cause di morte in Canada e il tempo è una risorsa critica nei centri per radioterapia. L’algoritmo Tabu Search che era stato utilizzato per risolvere la versione stocastica del problema, è stato migliorato. Per affrontare la complessità del problema, procedure di Ranking and Selection sono state implementate insieme ad altre procedure di Simulation Optimization. Le metodologie sviluppate sono state in grado di migliorare le performances di interesse riducendo soprattutto il tempo di calcolo per ottenere buone soluzioni del problema. L’applicazione della metodologia sviluppata può essere estesa ad altri problemi di ottimizzazione combinatoria in diversi campi della Ricerca Operativa.