Home care vehicule routing problem : the case of chargeable overtime and preferences

In this thesis, we study a particular and new scheduling and routing problem related to home health care. We start by considering a real problem from a provider in New York City, NY, USA, and then we generalize it. We provide a linear model for the problem, whose objective function aims at minimizing three components: total travel time of the caregivers, client and caregiver preferences, and overtime. With respect to the literature, the considered problem has its originality elements, because of the last component: clients are allowed (according to New York case) to pay a higher fee in order to cover additional costs incurred if the assigned caregiver works overtime for them. This means that if a caregiver works more than a certain amount of hours with a client, and therefore will be paid for overtime, the client can be willing to pay for it. This can be seen as an extra payment that will favour continuity of care, since the firm will have no additional costs incumbent upon them. This new aspect is studied, moreover, in a context in which we consider as preferences the answers that both clients and caregivers give to a set of questions, which identify some criteria that can determine the satisfaction of the client. It is important to notice that there is a distinction between hard a soft preferences, i.e. preferences which are very important, and preferences that would increase the satisfaction of the matching, but which are not a priority. Besides the linear formulation of this problem, we propose a matheuristic approach based on Cluster Decomposition to solve it, if the dimensions increase and the complete problem cannot be solved within a suitable time limit. Finally, we validate the complete model and the matheuristic with some numerical simulations on different instances, based on real data provided by the considered Home Health Care provider in New York.

In questa tesi analizziamo un problema di assistenza domiciliare, un caso che coniuga pianificazione e routing e che ha come scopo l’assegnazione di assistenti ai clienti, in modo che le richieste dei clienti siano rispettate. Iniziamo con il considerare un problema reale fornitoci da un’azienda erogatrice di servizi di New York City, New York, USA e, successivamente, lo generalizziamo. In questa tesi forniamo un modello lineare per il problema, in cui la funzione obiettivo mira a minimizzare tre componenti: la distanza totale percorsa dagli assistenti, le preferenze e gli straordinari. Analizzando la letteratura, si osserva che il problema descritto è innovativo, grazie alla terza componente: nel caso di New York considerato, infatti, si dà ai clienti la possibilità di pagare una tariffa più alta, in modo da coprire le spese aggiuntive che si vengono a creare quando un assistente lavora un numero di ore superiore a una normale soglia lavorativa presso di lui. Dando questa disponibilità a pagare gli straordinari, il cliente può ottenere una maggiore continuità di assistenza dato che, d’altro canto, l’azienda non deve sostenere una spesa aggiuntiva. L'aspetto degli straordinari viene trattato in un contesto in cui vi sono, inoltre, alcune preferenze, con cui si intende una serie di criteri che influenzano la reciproca soddisfazione cliente-assistente; questi possono essere "strict", cioè di elevata importanza, oppure “soft”, cioè fattori che influenzano la qualità dell'assistenza, ma che non sono prioritari. Oltre ad una formulazione lineare del modello qui descritto, proponiamo un approccio mateuristico basato su una decomposizione in cluster, utile a risolvere il problema nel caso di istanze di dimensioni elevate. Infine, segue la validazione del modello e del metodo mateuristico, tramite simulazioni effettuate su un insieme di istanze basate su dati reali provenienti dall'azienda erogatrice di servizi considerata.