VNS methods for home care routing and scheduling problem with temporal dependencies, and multiple structures and specialties

• Published date: 01 January 2020
• Author: Malek Masmoudi,Sana Frifita
• DOI: http://doi.org/10.1111/itor.12604
• Date: 01 January 2020

Intl. Trans. in Op. Res. 27 (2020) 291–313

DOI: 10.1111/itor.12604

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

VNS methods for home care routing and scheduling

problem with temporal dependencies, and multiple

structures and specialties

Sana Frifitaa,b,c,d and Malek Masmoudib, c,d

aLaboratory of Modeling and Optimization for Decisional, Industrial and Logistic Systems (MODILS), Faculty of

Economics and Management of Sfax, Sfax, Tunisia

bUniversity of Lyon,Saint-Etienne F-42023, France

cUniversity of Saint Etienne, Jean Monnet, Saint-Etienne F-42000, France

dLASPI, IUT de Roanne F-42334, France

E-mail: sanafrifita@gmail.com [Frifita]; malek.masmoudi@univ-st-etienne.fr [Masmoudi]

Received 5 February2017; received in revised form 7 March 2018; accepted 25 September 2018

Abstract

The need for optimization in the Home Care Service is becoming more and more legitimate in the face of

the increase of demand and cost all over the world. Recently, many researchers in the Operation Research

community have been attracted by this issue, which presents interesting aspects related to the vehicle routing

problems. In this paper, we consider a new variant called the vehicle routing problem with time windows,

temporal dependencies (synchronization, precedence, and disjunction), multi-structures, and multispecialties

problem (VRPTW-TD-2MS). This new variant is an extension of the vehicle routing problems with time

windows and synchronization constraints (VRPTW-S) that is well-studied in literature. We present a Mixed

Integer Programming method, and propose three Variable Neighborhood Search approaches. Extensive

experiments show the effectivenessand efficiency of the General Variable Neighborhood Searchwith Ejection

Chains-based local search for solving VRPTW-TD-2MS and VRPTW-S.

Keywords: VRPTW; home care; multiple structures; multiple specialties; synchronization; time windows; precedence;

disjunction; VNS; GVNS; GVNS-EC

1. Introduction

In many countries, great importance is attached to the satisfaction of people’s needs and the

improvement of living conditions. The home care service is mainly dedicated to dependent people

such as citizens who have difficulty leaving their homes by offering them social, medico-social, and

medical services such as cleaning, cooking, shopping, hygiene assistance, nursing, etc. These types

of services are provided in France by different public and private home care structures belonging to

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

292 S. Frifita and M. Masmoudi / Intl. Trans. in Op. Res. 27 (2020) 291–313

the social, medico-social, and medical fields. These structures are numerous and work together in a

complete coordination to provide a high quality of service to clients. The main types of structures

in France are called SAD,SSIAD,CSI,andSPASAD:

rSAD (Services d’Aide `

a Domicile): Social structure helping seniors to do what they do no longer

have the ability to do, such as dressing, shopping, preparing meals, etc. The domestic tasks

are carried out by home-support workers, and the accompaniment is provided by life-auxiliary

worker s.

rSSIAD (Services de Soins Infirmiers `

a Domicile): Medico-social structure providingthe necessary

nursing care (hygiene, various cares, etc.) by nursing assistants to maintain a dependent person at

home.

rCSI (Centre de Soins Infirmiers): Medical structure providing nursing care such as promoting

and maintaining health and preventing risks by nurses.

rSPASAD (Services Polyvalents d’Aide et de Soins A Domicile): Structure offering all services

provided by SAD, SSIAD, and CSI.

Tounderstand how home care structures schedule their caregivers’routes and how they coordinate

their activities together, we made a questionnaire and interviewedthe coordinators and/or managers

of different structures (2 SPASAD, 2 SAD, 3 SSIAD, and 2 CSI) in Roanne (France). Several

constraints and issues have been exposed by the interviewees.

In the literature, many issues relative to Home Care Service (HCS) are considered such as the

geographical partitioning of a territory into districts (Benzarti et al., 2013), the assignment of

human resources to districts (Hertz and Lahrichi, 2006), and the daily resources scheduling and

routing that consists of assigning resources to clients and designing the optimal sequence of visits

(Gayraud et al., 2013; Frifita et al., 2017). In this paper, we focus particularly on the scheduling

and routing problem that is modeled as a vehicle routing problem with time windows (VRPTW)

with synchronized visits (VRPTW-S) (Bredstr¨

om and R¨

onnqvist, 2008). The goal is to design least

cost routes for home care workers serving a set of geographically dispersed customers respecting

time windows and time-dependent constraints such as synchronization,disjunction, and precedence

between visits.

The benchmarking that we made on a set of real home carestructures per mitted us to discover the

complexity and the originality of the real routing and scheduling problem at home care structures

in comparison to existing problems in literature. This allowed us to define a new variant of routing

and scheduling problem related to home care domain and evaluate the extent of related parameters

and variables.

The coordination is a major problem between the home care structures due to the existence

of time-dependency constraints between the visits to be carried out at common clients request-

ing more than a service from different structures. This realistic concept is specific to home care

domain. Thus we added multiple structures and multiple specialties concepts to VRPTW with time-

dependency problem. We present the mathematical formulation of the new variant called vehicle

routing problems with time windows, time dependencies (synchronization,precedence, and disjunc-

tion), multi-structures, and multispecialties problem (VRPTW-TD-2MS). The original problem,

VRPTW-S, is NP-Hard, thus the new variant is NP-Hard too. We developed three VNS methods

to solve this problem in a reasonable computation time: Variable Neighborhood Search (VNS),

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies