GRASP for the Vehicle Routing Problem with Time Windows, Precedence, Synchronization and Lunch Break Constraints

In this time of health crisis, it is important to make adjustments of resources encountered in many areas dealing with logistical issues by minimizing the costs of transportation and maximizing the satisfaction and preferences of patients in the field of Home Health Care. In this paper, we deal with the vehicle routing problem with time windows, precedence, and synchronization constraints along with staff lunch break requirements combined with the scheduling and planning matter. Oftenly, patients whom are not requiring anymore staying at hospital are needed to leave their spot to another critical case, but need further treatment that can be done at home. Caregivers are assigned to perform special care to needy patients depending on their demands by taking into consideration temporal constraints such as time windows, preferences of patients, precedence, synchronization and more importantly the issue of caregivers’ lunch breaks which give a realistic aspect to the problem.

A caregiver (vehicle) is assigned to a patient (customer) to perform a number of given cares with multiple options according to the customer wishes like time windows requirement often specified by the patient, the precedence constraints are usually done if a specific care must be done before another and could involve more than one caregiver and must have at least one lunch break per day and it is not always taken at a fixed time of the day and must be flexible to maximize the satisfaction of customers’ demands.

To solve this problem, a mathematical model of the problem is described as a Mixed Integer Linear Programming (MILP) and a method based on a Greedy Randomized Adaptive Procedure (GRASP) is proposed. At the end of the paper, results are shown on a benchmark derived from the literature.