This paper studies the problem of heterogeneous electric vehicles, fast chargers, and synchronized jobs that have time windows in home healthcare routing and scheduling. We consider a problem that aims to establish daily routes and schedules for healthcare nurses to provide a variety of services to patients located in a scattered area. Each nurse should be assigned to an electric vehicle (EV) from a heterogeneous fleet of EVs to perform the assigned jobs within working hours. We consider three different types of EVs in terms of battery capacity and energy consumption. We aim to minimize the total cost of energy consumption, fixed nurse cost, and costs arising from the patients that cannot be served within the working day. We model the problem as a mixed integer programming formulation. We develop a hybrid metaheuristic based on a greedy random adaptive search procedure heuristic, to generate good quality initial solutions quickly, and an adaptive variable neighborhood search algorithm to generate high quality solutions in reasonable time. The hybrid metaheuristic employs a set of new advanced efficient procedures designed to handle the complex structure of the problem. Through extensive computational experiments, the performance of the mathematical model and the hybrid metaheuristic are evaluated. We conduct analyses on the robustness of the metaheuristic and the performance contribution of employing adaptive probabilities. We analyze the impact of problem parameters such as competency requirements, job duration, and synchronized jobs.
Hinweise
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
Home healthcare services (HHC), also known as in-home care, are an important element of primary care that offers professional service to patients at home in their familiar environment. A wide spectrum of services can be offered as home healthcare such as medical, therapeutical, and non-medical services. However, the specifications and the range of services differ from one country to another due to demographic tendencies. Other important factors are how efficiently the government or private healthcare management system works and how the HHC is prioritized (WHO 2012).
Universal health coverage (UHC) means that all people have access to health services when and where they need them without financial hardship. It encompasses the entire spectrum of essential health services, from health promotion to prevention, treatment, rehabilitation, and palliative care (WHO 2022). Therefore, HHC is a valuable asset for the UHC. Although HHC is not created for a specific target group, it is observed that the elderly uses HHC more. The convenience, effectiveness, and financial aspects of the service are the primary reasons why HHC is more beneficial for the elderly. Post-hospital care may also necessitate the assistance of a professional. In such cases, visiting a hospital for an elderly person is more difficult, requires travel time, and results in a higher cost. On the other hand, HHC assists the patient in receiving treatment in the comfort of her/his own home at a lower cost. The world’s elderly population is expected to double from 2019 to 2050, reaching nearly 1.5 billion (UN 2019). The growing rate of chronic diseases as well as inadequate room capacity of hospitals, and elderly housing make HHC more demanded, necessary, and functional.
Anzeige
In addition, with COVID-19, countries’ healthcare systems were tested. Unfortunately, due to the limited capacity in hospitalization and the limited number of healthcare professionals, many patients were unable to receive the necessary treatment on time. Since hospitals prioritized COVID-19 patients due to their urgency, the limited capacity of hospitals and healthcare professionals had a dramatic effect on patients with other diseases. For this reason, the necessary precautions should be taken for the unforeseeable challenges in the healthcare sector in order to increase the well being of the community, especially the elderly. In support of these, the development of HHC services is considered a sustainable solution (World Economic Forum 2020).
The idea behind HHC is to provide social benefits and better healthcare for patients. In practice, it requires establishing daily routes and schedules of healthcare professionals, resulting in a routing and scheduling problem, which has been discussed in many studies in the literature. The home healthcare routing and scheduling problem (HHCRSP) is an extension of the vehicle routing problem (VRP) in the HHC sector.
In this study, we deal with the routing and scheduling problem of home health professionals with the use of electric vehicles (EVs). Although the scheduling and routing of the healthcare nurses with fossil fuel cars is a widely studied problem in the literature since 1990s (Begur et al. 1997), we examined different types of EVs in this particular case. The world is shifting from fossil fuels to electricity in transportation due to environmental issues, energy efficiency, cost, and performance benefits of EVs (IEA 2019). The process of integration of EVs has already begun in many countries with strict policies and subsidies, especially in European Union countries. We will possibly witness more implications and solutions regarding EVs in transportation in the future. In the last five years, numerous companies have designed and produced innovative EVs. This presents a distinct opportunity, especially for HHC providers, to diversify their vehicle fleet and establish a heterogeneous fleet strategy for daily operations. In light of these new developments, this study not only has an empirical function but also provides an opportunity for future solutions to EV-related issues.
Our paper can lead to better outcomes in three main areas. First, home healthcare has a social impact, and therefore, development of HHC services will result in equal access to support and treatment in communities regardless of their status, gender, or age. Second, this approach will overcome some of the limitations in HHC, such as capacity constraints and increasing demand, to result in a sustainable HHC. Lastly, with the usage of different types of EVs, the concept becomes more eco-friendly for each party, i.e., service providers, governments, and patients.
Anzeige
1.1 A review of the literature
In the classical VRP, the goal is to create a schedule for a set number of vehicles to serve customers while minimizing the associated costs. As the focus of the VRP is the delivery of an asset or a service by workers who need routing, the problem is found to be applicable for many different sectors, such as the routing of mobile medical facilities (Yücel et al. 2020) and the delivery of mobile health services using mobile clinics (Salman et al. 2021). Although HHC services have been adopted many years ago and have been an important part of the modern primary healthcare system (Murkofsky and Alston 2009), the first VRP for HHC nurses in the literature was studied by Begur et al. (1997).
In parallel with the growth in the utilization of HHC services, HHCRSP has been progressively studied with different objective functions and constraints that aim to reflect real-world conditions. While minimization of solely travel time (Begur et al. 1997), distance (Akjiratikarl et al. 2007) and cost (Eveborn et al. 2006) make a basis for the problem, additional objectives such as waiting time, overtime, preference, workload balance have also been studied (Hiermann et al. 2015; Mankowska et al. 2014). Many types of heuristics have been used in the literature. Heuristics include memetic algorithm (Hiermann et al. 2015), swarm optimization algorithm (Akjiratikarl et al. 2007), variable neighborhood search (VNS) (Mankowska et al. 2014), MIP-based decomposition (Yadav and Tanksale 2022), simulated annealing (Mankowska et al. 2014; Hiermann et al. 2015), and adaptive large neighborhood search (Koç et al. 2019).
The HHCRSP receives significant attention from the OR community as it is directly related to practice. Many different variants of this problem have recently been studied. Tanoumand and Ünlüyurt (2021) developed an exact algorithm for the resource constrained HHCRSP. Li et al. (2021) introduced the HHCRSP considering outpatient services and developed a hybrid genetic algorithm. Savaşer and Kara (2022) studied the mobile healthcare services in rural areas and modeled the problem as a periodic location-routing problem. Akbari et al. (2023) addressed the minimizing total weighted latency in the HHCRSP with patient prioritization. The reader is referred to Fikar and Hirsch (2017), Grieco et al. (2021), and Euchi et al. (2022) for a detailed review of HHCRSP and its variants.
The electric (E-VRP) considers the limited range, battery capacities, and charging times of EVs along with the decision of available charging options (Schneider et al. 2014; Kucukoglu et al. 2021). While the goal of the problem remains the same, vehicles consume electricity as an alternative to fossil fuels. Due to climate change and the environmental effects of the logistics sector, interest in this line of studies has progressively increased (Bektaş et al. 2019). The problem has received significant interest in the literature. Koç et al. (2019) studied the E-VRP with a nonlinear charging function that considers joint investments in charging stations (CSs). Lee (2021) proposed a branch-and-price and column generation algorithm to solve the nonlinear charging function version of the problem. Keskin et al. (2019) studied the extension with additional constraints, including limited capacity and waiting time at CSs. Dönmez et al. (2022) studied the mixed fleet VRP with partial recharging by multiple chargers.
In terms of the HHCRSP, EVs have been considered in several articles. Erdem and Koç (2019) studied the HHC and E-VRP with time windows that only consider linear charging and a single type of CS, and developed a metaheuristic algorithm. Erdem et al. (2022) studied the electric HHCRSP with time windows and fast chargers, which considers a homogeneous EV fleet and three types of charging technologies, normal, fast and super-fast. The authors developed an adaptive large neighborhood search (ALNS) heuristic to solve the problem. Most recently, Yazır et al. (2023) introduced the multi-period HHCRSP with EVs and used ALNS to solve the problem. The problem aims to construct weekly routes for healthcare nurses considering homogeneous vehicles and three types of charging technologies.
Recognizing the inherent diversity of the fleet of vehicles used by healthcare providers and their imperative to synchronize service requests for operational efficiency, our problem differs from the aforementioned studies by incorporating a heterogeneous EV fleet and considering synchronized service requests. In scenarios that require synchronized service, specific job requirements can require simultaneous execution by two different nurses, leading to interdependent routes for nurses. Altering one route affects the others and could potentially render them infeasible (Afifi et al. 2016; Bazirha et al. 2023). Furthermore, it is important to note that the problem in its current form cannot be effectively addressed using the solution methodologies proposed in previous studies.
1.2 Scientific contributions and structure of the paper
In the context of the HHCRSP, this paper studies the problem of heterogeneous electric vehicles, fast chargers, synchronized jobs, and time windows. In most practical distribution scenarios, diverse fleets of vehicles are employed to meet the demands of customers (Hoff et al. 2010; Koç et al. 2016). Similarly, in the HHC services heterogeneous fleets provides an opportunity to construct minimum costly routing plans. All of these problem components contribute to an increase in problem complexity, particularly the fleet mix decision. Although there is a large amount of research on each part of the problem separately, there is no research that investigates the impact of all these aforementioned and practically widely used factors integrated together. Our first contribution is to formally introduce and model this new problem. Our second contribution is to develop a hybrid metaheuristic based on greedy random adaptive search procedure (GRASP) algorithm to generate good initial solutions quickly and adaptive variable neighborhood search (AVNS) algorithm that integrates several problem specific effective heuristic mechanisms to generate high quality solutions in reasonable time. Our third contribution is to provide managerial insights by conducting extensive computational experiments to gain a deep understanding of the interactions between the components of the problem such as the impact of competency requirements, job duration, and synchronized jobs.
The remainder of this paper is organized as follows. Section 2 presents the problem definition, notation, and the mathematical formulation. Section 3 details the hybrid metaheuristic algorithm. Section 4 presents the results of computational experiments and analyses. The paper is concluded in Sect. 5.
2 Problem statement
The problem aims to determine the daily schedules and routes of the HHC nurses to provide the necessary service to patients living in a scattered region. Each nurse is assigned to an EV from an EV fleet to drive to patient homes. Therefore, the term nurse and EV will be used interchangeably. The EV fleet is considered heterogeneous in terms of price, range, and energy consumption.
As the problem is defined on a geographical area and EVs have a limited range, CSs must be visited if the EV battery is not enough to complete the corresponding EV’s route. The CSs have only one type of charging technology, i.e., the fast-charging option, which is the most common and preferred one for intraday charging according to Erdem et al. (2022). The EVs can be partially charged at a CS. The state of charge (SoC) should be tracked for each EV to maintain energy feasibility. The EVs are assumed to start their schedule with fully charged batteries presuming that they were charged the previous night. Within working hours, each nurse starts and ends the shift at a hospital, which is referred to as the depot of the related nurse. Overtime is not allowed.
Each patient service request has a predetermined service duration and a time window for the service. The service duration depends on the estimated service time prescribed/recommended by the doctor for the required service. The service request of a patient corresponds to a job. Let J be the set of jobs, where a job \(i \in J\) has a predetermined duration represented by \(d_{i}\) and a time window denoted by \([a_{i},b_{i}]\). If an assigned nurse arrives at the job location early, then the nurse must wait until the start time of the predetermined time window, \(a_{i}\). If a job \(i \in J\) cannot be completed within its time window, a penalty cost \(\alpha _{i}^P\) is incurred.
Each job requires a number of specific level competency types and can only be served by the same or more qualified nurse for each competency type. Let N be the set of nurses and U denote the types of competence. The competency level requirement of job \(i \in J\) for competency type \(u \in U\) is indicated by \(q_{iu}\) and the competency level of nurse \(n \in N\) for competency type \(u \in U\) is defined by \(q'_{nu}\). Job \(i \in J\) can be assigned to nurse \(n \in N\) if only the nurse has the same or higher proficiency for each competency type, i.e., \(q'_{nu}\ge q_{nu}\) for each \(u \in U\). Each nurse \(n \in N\) has a daily fixed cost denoted by \(\alpha ^N_n\) depending on her/his proficiency. Some patient service requests may require more than one nurse resulting in multiple simultaneous jobs. For such cases, a copy of the related job is created for each nurse required. Such copy jobs \(i,j \in J\) are paired and nurses assigned to these paired jobs should be present at the home of the patient simultaneously to provide the required service. The binary parameter \(p_{ij}\) indicates whether jobs i,\(j \in J\) are paired and should be synchronized or not. The working time window of nurse \(n \in N\) is denoted by \([a'_{n},b'_{n}]\).
Let K be the set of EVs. The starting depot and the ending depot locations of EV \(k \in K\) are represented by \(0_{k}\) and \(n_{k}\), respectively. Each nurse begins and ends shift from the depot of the vehicle to which nurse is assigned. The battery capacity and the energy consumption rate of EV \(k \in K\) are denoted by \(Y_{k}\) and \(c_{k}\), respectively. Each CS has only fast chargers, and the recharging rate and unit energy cost of using a fast charger are assumed to be the same for each CS, which are denoted by r and \(\alpha ^C\), respectively. We create multiple copies of a CS to enable multiple visits of each CS by the same vehicle. Let S be the set of CSs including the copy CSs.
The set of nodes including the jobs and the CSs is denoted by V, i.e., \(V = J \cup S\). For an EV \(k \in K\); the set \(V_{0_k}\) includes the jobs, CSs, and the starting depot \(0_{k}\), i.e., \(V_{0_k}=V\cup \{0_k\}\), and the set \(V_{n_k}\) includes the jobs, CSs, and the ending depot \(n_{k}\), i.e., \(V_{n_k}=V\cup \{n_k\}\). All nodes that can be visited by EV \(k \in K\), including the starting depot \(0_{k}\), jobs, CSs, and ending depot \(n_{k}\) are denoted as \(V_{0_{k},n_{k}}\), i.e., \(V_{0_{k},n_{k}}=V\cup \{0_k, n_k\}\).
The problem is defined in a complete directed graph \(G=(\bigcup _{k\in K} V_{0_{k},n_{k}},A)\) where \(\bigcup _{k\in K}\)\(V_{0_{k},n_{k}}\) is the set of nodes and \(A=\{(i,j): i, j \in \,\bigcup _{k\in K} V_{0_{k},n_{k}}\}\) is the set of arcs. Parameters \(s^d_{ij}\) and \(s_{ij}\) represent the distance and travel time of an arc \((i,j) \in A\), respectively.
The objective is to minimize the total cost of energy consumption, fixed nurse cost, and costs arising from the patients that cannot be served within the working day. Binary variables are as follows. Let \(x_{ijk}\) be 1, if EV \(k \in K\) travels on arc \((i,j) \in A\) and 0, otherwise. Let \(z_{nk}\) be 1, if nurse \(n \in N\) is assigned to EV \(k \in K\) and 0, otherwise. Let \(h_{j}\) be 1, if a job \(j \in J\) is served. The continuous variables are as follows. The State of Charge (SoC) of an EV \(k \in K\) at the arrival time of node \(i \in V_{0_{k},n_{k}}\) is defined as \(y_{ik}\) and, the SoC of an EV at the departure time of node \(i \in S\) is \(g_{ik}\). Let \(t_{ik}\) be the service starting time of a nurse using EV \(k \in K\) for job \(i \in J\). Let \(w_{ik}\) be the charging duration of EV \(k \in K\) at CS \(i \in S\). Let \(\sigma _{ik}\) be the amount of recharged energy at CS \(i \in S\) for EV \(k \in K\). All the notation of the problem is presented in Table 15 in the Appendix.
An illustration of a solution for a problem instance having two nurses, four jobs of four patients, two competency types, and one CS is shown in Fig. 1. The job of Patient2 requires two nurses simultaneously. In the solution, Nurse-1 having a level of 3 for both competency types is assigned to EV-1 and starts her/his route from the hospital, visits Patient1 first, the CS second, Patient2 third, and returns back to the hospital. Nurse-2 having a level of 2 for both competency types is assigned to EV-2 and starts her/his route from the hospital, visits Patient2 first, Patient3 s, Patient4 third, and returns back to the hospital. Note that Nurse-1 and Nurse-2 serve Patient2 at the same time. The arrival time of each EV to each node and the SoC at the time of arrival are provided in Fig. 1.
Fig. 1
Illustration of a solution for a problem instance having two nurses, four patients, two competency types and one CS
×
2.1 Mathematical formulation
The mathematical model of the problem is formulated as follows:
The objective function (1) aims to minimize the total cost that comprises three terms. The first term corresponds to the total travelling cost of EVs. The second term refers to the total fixed cost of healthcare nurses utilized. The last term corresponds to the penalty costs of jobs that are not served.
Constraints (2) ensure that each job is visited at most once. Constraints (3) guarantee that each CS copy is visited at most once by the same vehicle within the planning horizon. Constraints (4) and (5) keep track of departures and arrivals from and to the depot for the utilized EVs, respectively. Constraints (6) guarantee the conservation of flow for an EV and a node, i.e., if an EV arrives at a job or CS node, then it should depart from that node. Constraints (7) and (8) ensure that an EV tour must be completed within the daily working hours of the corresponding nurse. Constraints (9) and (10) ensure that jobs are served within their time windows. Constraints (11) and (12) calculate the node visit times considering travelling times between nodes, service times of jobs, and charging times at CSs. Constraints (13) and (14) calculate the SoC of an EV at the time of arrival of a node considering energy consumption during travelling. Constraints (15) define the limits of the SoC of an EV at the time of departure from a CS node. Constraints (16) guarantee that each EV starts its tour with full charge. Constraints (17) and (18) calculate the amount of energy charged and the charging duration, respectively, for an EV that visits a CS. Constraints (19) guarantee that paired jobs are served simultaneously. Constraints (20) ensure that a job is assigned to an eligible nurse having sufficient level for each competency type. Constraints (21) ensure that each nurse is assigned to at most one EV. Constraints (22) ensure that each EV is assigned to at most one nurse. Constraints (23) identify whether a job is served or not. Constraints (24)-(28) define the domains of decision variables.
3 Hybrid metaheuristic
To effectively solve this complex optimization problem, we develop a hybrid metaheuristic algorithm based on GRASP and AVNS. First, GRASP-based constructive matheuristic obtains a good initial solution quickly and then AVNS algorithm improves the initial solution through adaptive probabilities associated with the neighborhood structures. We describe the GRASP in Sect. 3.1 and the AVNS algorithms in Sect. 3.2.
3.1 GRASP-based constructive matheuristic
Basic greedy constructive heuristics, based on the greedy choice applied at each iteration, provide a single solution for a problem and the resulting solution is generally far from the optimal. Different from the basic greedy approaches, GRASP is based on randomly selecting a choice from a pool of best alternatives instead of the best choice at each iteration (Feo and Resende 1995; Resende and Ribeiro 2016).
Our GRASP-based constructive matheuristic generates a feasible solution for the problem in two steps. The first step assigns nurses to EVs and jobs to nurses through an assignment algorithm based on GRASP described in Sect. 3.1.1. The second step determines the routes of EVs through a mathematical model as described in Sect. 3.1.2. Hereafter, this algorithm is denoted as GRASP, in short.
3.1.1 Assignment of nurses to EVs and jobs to nurses
The assignment algorithm presented in Algorithm 1 starts with calculating a nurse-score \(\lambda _{n}\) for each nurse \(n\in N\) (line 1). The score \(\lambda _{n}\) of nurse \(n\in N\) is calculated through equations (29–32) and has three terms \(\Phi _{n}^{t}, \Phi _{n}^{f}\), and \(\Phi _{n}^{u}\) (corresponding to the length of the her/his time window, the fixed cost of the nurse and her/his competency level, respectively) each associated with a weight, \(\Omega ^{t}, \Omega ^{f}\), and \(\Omega ^{u}\), respectively. The formulation of the nurse score aims to enhance the likelihood of selecting nurses with longer working durations, lower fixed costs, and higher competency levels, thereby maximizing overall benefit potential.
For a nurse \(n \in N\) and job \(i \in J\) pair; a piece-wise compatibility parameter \(compatibility_{(n,i)}\) is set to \(\lambda _{n}\) if nurse n works within the time windows of job j and has relevant competency level for each competency type, and 0 otherwise (lines 2–10). Next, each job \(i\in J\) is assigned to a nurse \(n^{'} \in N\), using a roulette wheel selection procedure that uses a selection probability proportional to \(compatibility_{(n,i)}\) for each nurse \(n\in N\) (lines 12-15). Nurses are then randomly assigned to EVs (lines 16-19). The output of the assignment algorithm is the set of assigned jobs \(J_k\) and the nurse \(n_k\) assigned for each EV \(k\in K\).
Algorithm 1
Assignment algorithm
×
3.1.2 Tour construction algorithm
The following mathematical model is used to determine the route of each EV \(k\in K\) considering the jobs assigned to the corresponding nurse, i.e., \(J_k\).
The objective function (33) aims to minimize the total travelling cost of the EV k and the total penalty costs of jobs in \(J_k\) that are not served. Constraints (34) ensure that each job in \(J_k\) can be visited at most once. Constraints (35) guarantee that an EV can visit at most one CS within the planning horizon. Constraints (36) and (37) keep track of departures and arrivals from the depot, respectively. Constraints (38) guarantee the conservation of flow for each node that can be visited. Constraints (39) ensure that jobs are served within their predetermined time intervals. Constraints (40) ensure that the EV tour must be completed within the daily working time of the corresponding nurse. Constraints (41) and (42) calculate the node visit times considering travelling times between nodes, service times of jobs, and charging times at CSs. Constraints (43) and (44) calculate the SoC of the EV at the time of arrival of a node considering energy consumption during travelling. Constraints (45) define the limits of the SoC of the EV at the time of departure from a CS node. Constraints (46) ensure that the EV must start tour with full charge. Constraints (47) and (48) calculate the amount of energy charged and the charging duration, respectively. Constraints (49) determine whether job in \(J_k\) is served or not. Constraints (50)-(53) define the domains of decision variables.
After determining the route of the EV \(k\in K\) through the above model, the set of jobs that cannot be served, i.e., the ones having \(h_i=0\), are assigned to an eligible EV whose route has not been determined yet, using the roulette wheel selection procedure applied in line 13 of Algorithm 1. After the routes of all EVs are determined, the cost of the solution is calculated as the sum of travelling costs of all EVs, the fixed costs of utilized nurses, and the penalties associated with the unserved jobs. GRASP is run 1 time and generates the initial solution.
The variable neighborhood search (VNS) is an effective metaheuristic that can be applied to a large variety of combinatorial optimization problems (Mladenovic and Hansen 1997). The VNS represents a flexible framework for utilizing heuristics to address optimization problems. On the contrary of using single neighborhood structure, VNS systematically changes its neighborhood structures in search of an optimal solution (Hansen et al. 2016). Basic VNS algorithm consists of three steps: (1) shaking step, (2) improvement step, and (3) neighborhood change. The main goal of the shaking step is to escape from the local optimum via selecting a random solution from one of the predetermined neighborhood structures. The improvement step aims to find a better solution from the current neighborhood of the current solution. In the neighborhood change step, at each iteration, the neighborhood structure to be used is determined. Different versions of the VNS employ different neighborhood selection approaches (e.g., random, enlarging). There are several successful applications of adaptive neighborhood selection approaches (Li and Tian 2016). We propose an Adaptive VNS (AVNS) that selects the current neighborhood based on the past performance of neighborhoods (see Sect. 3.2.3).
Algorithm 2 presents the pseudocode of the AVNS. It starts with an initial solution, \(s^{initial}\), found by the GRASP heuristic proposed, and at each iteration, a neighborhood structure is chosen from the set of neighborhood structures NS based on their past performances. If the random neighboring solution \(s^{'}\) in the chosen neighborhood meets the acceptance criteria (see Sect. 3.2.4), the current solution, \(s^{current}\), is updated, and if the random neighboring solution \(s^{'}\) is better than the best solution \(s^{best}\), the best solution, \(s^{best}\) is also updated. At each iteration, the current score of the selected neighborhood, \(\psi ^{NS^{current}}\) is updated according to its performance (see section 3.2.3) and at every \(n^{adjust}\) iterations, weights of each neighborhood, \(w^x\) are updated. In order to avoid local minima, a special shaking procedure is used. The parameter \(n^{shake}\) refers to the shaking period and after each \(n^{shake}\) non-improving iterations, a random solution is generated using the shaking procedure (see Sect. 3.2.2). At each iteration, current temperature T is cooled by \(\gamma\) cooling rate and the algorithm is continuous as long as the stopping criteria (a maximum number of iterations \(iter^{max}\) or a maximum number of non-improving iterations \(iter^{non\_imp}\)) is not met.
Algorithm 2
AVNS algorithm
×
3.2.1 Neighborhood structures
The proposed AVNS employs the following seven neighborhood structures that are specifically designed for the problem.
Job relocation A job is removed from the route of the EV, which it is currently assigned and assigned to another compatible EV to the best position in terms of cost. All such possible adjustments for all jobs are explored and the best one is applied.
Random vertical job swap Two jobs that are assigned to two different EVs and that can be interchanged in terms of competency compatibility are randomly selected and interchanged.
Unassigned job insertion A job from the current unassigned job set is assigned to a compatible EV to the best position in terms of cost. All such insertions are evaluated for all unassigned jobs and the best one is applied.
Greedy EV destruction The jobs assigned to the EV with the fewest number of jobs are transferred to another compatible EV, if possible, with the aim of eliminating the former EV.
Nurse-EV swap The assignment of two nurses to two EVs are interchanged, together with their jobs. The best interchange option in terms of cost, if exists, is applied.
Nurse swap The nurses of two EVs are interchanged preserving the nurse-job assignments. The best interchange option in terms of cost, if exists, is applied.
3-opt This operator is a special form of the k-opt algorithm (Dorigo et al. 2006). It involves removing three links (or edges) of a route an EV and reconnecting the route in the best of all eight possible ways. The 3-opt algorithm is applied separately for each EV.
In order to avoid infeasible solutions; the battery feasibility, time window feasibility, and competency feasibility of a candidate neighboring solution are checked first and only feasible neighboring solutions are evaluated with an acceptance criteria (see section 3.2.4). While checking the battery feasibility of each EV, all CS visits in its route are removed and starting from the first node visited, the SoC at each node visit is checked and the closest CS visit is inserted to the route when necessary.
3.2.2 Shaking procedure
The shaking procedure in VNS aims to resolve the local minima traps. Let \(s^{best}\) be the best-found solution at the time of appliance of the shaking procedure. A basic shaking procedure is based on choosing a random solution from one of \(N^{k^{th}} \in N\) of a given solution \(s^{best}\) (Hansen et al. 2016). In the shaking procedure, there is a balance between perturbing the solution and maintaining good aspects of the solution (Hemmelmayr et al. 2009). Moving far away from the best solution may degrade the algorithm performance, whereas making minor changes may result in the local minimum not being escaped. In order to escape from local minima traps, we employed a random relocation operator, where a random number of jobs between 1 and \(relocate^{max}\), are chosen and reassigned to EVs based on their resulting additional costs.
3.2.3 Weight adjustment procedure
We employed the weight adjustment procedure provided by (Yücel et al. 2022) to adjust the weights of neighborhood structures in NS. The score of each neighborhood structure \(x\in NS\), namely \(\psi ^{x}\), and the number of times the corresponding neighborhood structures \(x \in NS\) is used during the last adjustment period, namely \(\upsilon ^{x}\), are set to zero at the beginning of each adjustment period \(n^{adjust}\). Let \(w^{x}\) be the weight of the neighborhood structure \(x \in NS\). Once a neighborhood structure \(x \in NS\) is applied during an iteration, \(\psi ^{x}\) is increased by \(\Delta \psi\) according to the performance of the neighboring solution \(s^{'}\) obtained, where \(\Delta \psi\) is calculated based on Equation (54).
At the beginning of each adjustment period, weight of a neighborhood \(x \in N\) is calculated based on its current weight and its score at the end of the previous period based on Equation (55).
where \(\rho\) is the reaction factor taking values in range [0, 1] and is used to adjust the influence of the recent success and past performance. When \(\rho\) is close to 1, the effect of the recent success increases, when it is close to 0, the effect of the past performance increases. The initial weight of each heuristic is set to 1/|N| and at the beginning of each adjustment period the selection probability of a heuristic \(x \in N\), p(x), is calculated based on Equation (56).
We use the Metropolis criteria introduced by Metropolis et al. (1953) as the acceptance criteria in the proposed AVNS. It has been successfully used in many neighborhood search based heuristics. If a neighboring solution \(s^{'}\) is better than \(s^{current}\) (i.e. \(c(s^{'})<c(s^{current})\) where c(s) denotes the objective function value of solution s), then the solution \(s^{'}\) is always accepted and replaces \(s^{current}\). If a neighboring solution \(s^{'}\) is worse than \(s^{current}\), the solution \(s^{'}\) is accepted with probability of \(e^{-(c(s^{'}) -c(s^{current}))/T}\) where T denotes the current temperature. Based on the approach used in Pisinger and Ropke (2007), the initial temperature, \(T_0\), is set to a value that accepts a solution that is \(\phi\)% worse than the initial solution with \(\xi\)% probability. At each iteration, the current temperature is cooled with a cooling rate of \(\gamma\).
4 Computational experiments
We now present the results of our computational experiments. We first explain how the data used in computational analysis is generated in Sect. 4.1. We analyze the robustness of the proposed algorithms through changing the number of GRASP replications in Sect. 4.2. The performance contribution of employing adaptive probabilities of VNS is analyzed in Sect. 4.3. We then compare the performance of the GRASP and AVNS, and mathematical model on small and medium-sized instances in Sect. 4.4. We report the results of large-size instances in Sect. 4.5. We analyze the effects of the problem parameters (such as the number of competency types, the variance in job durations, the existence of synchronized jobs, and the heterogenity of the vehicle fleet) on the solutions in Sect. 4.6.
The mathematical model is implemented in Python and solved by CPLEX 20.1 with a run time limit of three hours. The proposed AVNS algorithm is implemented in Python. The computational experiments are conducted on a workstation with 64 GB of RAM and i7 2.3 GHz CPU. For each instance, an initial solution obtained through the proposed GRASP algorithm and the GRASP solution is improved through the proposed AVNS algorithm. For each instance, we performed 10 AVNS replications and the average and the standard deviation of the results and the best found solutions over 10 replications are reported. After a parameter tuning process conducted on small-size instances, the parameters of the GRASP and the AVNS algorithms are set as provided in Table 1.
Table 1
Parameters of the GRASP and the AVNS algorithms
Description
Value
Parameters of GRASP
1
time window coefficient, \(\Omega ^{t}\)
0.10
2
fixed cost coefficient, \(\Omega ^{f}\)
0.40
3
competency level coefficient, \(\Omega ^{u}\)
0.50
4
number of GRASP replications, \(GRASP^{rep}\)
1
Parameters of AVNS
1
maximum number of non-improving iteration \(iter^{max\_non\_imp}\)
1000
2
maximum number of iteration, \(iter^{max}\)
10,000
3
initial temperature determination parameter-1 (%), \(\phi\)
50
4
initial temperature determination parameter-2 (%), \(\xi\)
50
5
cooling rate, \(\gamma\)
0.99
6
reaction factor, \(\rho\)
0.50
7
weight adjustment period, \(n^{adjust}\)
25
8
shaking period, \(n^{shake}\)
100
9
score increased for improving the best found solution, \(\alpha _{1}\)
70
10
score increased for improving the current solution, \(\alpha _{2}\)
50
11
score increased for non-improving but accepted solutions, \(\alpha _{3}\)
20
12
maximum number of jobs to be relocated, \(relocate^{max}\)
6
4.1 Data
We used both synthetic data based on the literature and real-world data to generate our benchmark instances. In all instances, nurse working hours start at 8 a.m. and finish at 5 p.m. The fixed cost of a nurse, \(\alpha _n^N\), is calculated between 400 and 600 based on the daily salary of a nurse according to Medisozluk (2020), and her/his competency levels. There are two competency types, i.e., \(\mid U\mid =2\), and there are three levels for each.
Patient locations are generated based on the "Address Based Population Registration System" database of Turkish Statistical Institute (2020), which provides the population data for each province, district, and neighborhood of the city of Ankara province. Two different location selection methods are used to determine the patient locations: (1) random selection, rs in short, and (2) weighted random selection, wrs in short. In rs, patient locations are chosen randomly from the neighborhoods of Ankara. In wrs, patient locations are chosen randomly from the neighborhoods of Ankara based on their populations. The depot location of each vehicle is set as a random one of the public hospitals. Finally, the exact locations of the CSs are determined by use of Google Maps API (ZES 2020). The distance matrix, i.e., \(s_{ij}^d\)’s, is generated based on the Haversine formula (Movable Type Scripts 2020).
The EV fleet has three types of EVs (types a, b, and c) that differ in capacity and energy consumption. Consumption rates of EV type a, b, and c are 0.158 kWh, 0.158 kWh, and 0.165 kWh, respectively. Traveling cost is calculated by multiplying the unit consumption rate by the unit electricity cost in kWh. The battery capacities of EV types a, b and c are 26.8, 32.3, and 52, respectively. The EV speed to be used for travel times is determined as 55 km/h based on the study by (Gupta et al. 2017). In order to serve as many jobs as possible, the cost of not serving a patient job is set to \(\alpha _{j}^P=800, \forall j \in J\).
We generated small-, medium- and large-size instances. Small-size instances have 10 jobs, medium-size instances have 20 or 30 jobs, and large-size instances have 40, 50, or 60 jobs. There are 10 instances generated with rs method and 10 instances generated with wrs method for each job set size, up to 30 jobs. Therefore, a total of 3x10x2=60 small- and medium-size instances are generated. The following naming convention is used for the small- and medium-size instances, where “j” refers to the number of jobs, “n” to the number of nurses, “cs” to the number of CSs, “s” to the number of competency types, “w” to wide time windows for jobs, “t” to narrow time windows for jobs, “sy” to the number of synchronized jobs, “R” to rs method, and “W" to wrs method. For example, the instance “10j3n3cs2s-w-1sy-R4” refers to the fourth instance having 10 randomly selected jobs with wide time windows, three nurses, three CS, two types of competences, and one synchronized job.
In order to analyze the effect of the problem parameters, large-size instances are divided into seven groups as G1-G7. The groups differ in the location selection method (rs or wrs), charger type (super-fast or fast), the existence of competency requirement (1, corresponding to the case where there is one competency type with 3 levels, or 0, corresponding to the case where all jobs require the same competency), the percentage of synchronized jobs among all jobs (0% or 10 %), and job duration (randomly selected in [20, 60] or randomly selected in [10, 90] minutes) as provided in Table 2.
Table 2
Features of large-size instance groups
Group
Location generation method
Charger type(kW/h)
\(\mid U\mid\)
% of synchronized jobs
Job durations
G1
rs
Fast (0.183)
0
0
randomly selected in [20, 60]
G2
rs
Super-fast (0.883)
0
0
randomly selected in [20, 60]
G3
wrs
Fast (0.183)
0
0
randomly selected in [20, 60]
G4
wrs
Super-fast (0.883)
0
0
randomly selected in [20, 60]
G5
rs
Fast (0.183)
1
0
randomly selected in [20, 60]
G6
rs
Fast (0.183)
1
0
randomly selected in [10, 90]
G7
rs
Fast (0.183)
1
10
randomly selected in [20, 60]
For e.g., for instances in group G1, rs is used for job locations, fast charger type is used, all jobs have the same competency requirement, there is no synchronized job and the variance in job durations is low. The following naming convention is used for large-size instances, where “j” refers to the number of jobs, which can be 40, 50, or 60; "G" refers to the group name. For e.g., the instance "40j-G1–1” refers to the first instance in group G1 having 40 jobs. Therefore, a total of 3x7x2=42 large-size instances are generated. The generated data is publicly available at Cebeci et al. (2023).
4.2 An analysis on the robustness of algorithms
In order to analyze the robustness of the GRASP algorithm, we ran the GRASP algorithm with varying number of replications (1, 50, or 100) on instances having 20 and 40 jobs and compared the best found solution among the replications. In addition, to analyze how the solution quality and the run time of the proposed AVNS is affected by the initial solution, we started the AVNS with the best found solution of the GRASP algorithm having varying number of replications. In Table 3, for instances having 20 jobs and 40 jobs separately, we report the average, minimum, and maximum values of the best objective function values and total run times of the GRASP with one replication and the AVNS starting with that GRASP solution. In addition, in the table we provide the comparison of the GRASP with 50 and 100 replications and the AVNS starting with those GRASP solutions with the GRASP with one replication and the AVNS starting with that solution in terms of the average, minimum, and maximum values of best objective improvement percentages and the run time increase percentages for the GRASP and AVNS solutions generated with varying number of replications of the GRASP.
Table 3
Comparative results for varying replication sizes of the GRASP algorithm
Instance
1 GRASP Replication
1 GRASP Replication vs. 50 GRASP Replications
1 GRASP Replication vs. 100 GRASP Replications
Group
GRASP
GRASP
AVNS
AVNS
GRASP
GRASP
AVNS
AVNS
GRASP
GRASP
AVNS
AVNS
Best Obj
Time (s)
Best Obj
Time (s)
Best Obj. Imp. (%)
Time (s)
Best Obj. Imp. (%)
Time (s)
Best Obj. Imp. (%)
Time (s)
Best Obj. Imp. (%)
Time (s)
20 jobs
avg
2917.22
<1
1771.80
31.55
5.30
37.33
0.00
24.32
4.90
72.32
0.01
20.45
min
2268.00
<1
1000.93
25.00
\(-\)20.74
27.29
\(-\)0.18
12.85
\(-\)20.49
53.01
\(-\)0.26
14.40
max
4353.90
<1
3623.65
40.00
19.96
53.12
0.12
59.81
23.80
120.77
0.11
41.72
40 jobs
avg
7602.64
29.71
3381.66
182.71
9.86
181.29
\(-\)0.03
180.88
13.06
329.68
\(-\)0.01
198.94
min
5378.24
26.00
2496.32
105.00
\(-\)3.48
166.71
\(-\)0.21
125.50
\(-\)3.64
301.20
\(-\)0.54
118.41
max
9703.98
35.00
5535.63
246.00
18.53
202.13
0.21
246.88
19.57
353.92
0.35
424.82
According to the results provided in Table 3, the best solution found in the GRASP algorithm decreased by at most 20.49 % or increased by at most 23.80 % when the number of replications increased from 1 to 50 or 100. This is an expected result of the randomness in the GRASP framework and demonstrates that the robustness of the GRASP can vary depending on the problem instance. On the other hand, the percentage change in the best found solution of the AVNS algorithm is less than 1%, demonstrating the robustness of the proposed AVNS with respect to the initial solution quality. Based on this observation and long GRASP run times for a higher number of GRASP replications, we set the number of GRASP replications to 1 in the remaining analysis.
4.3 An analysis on the performance contribution of employing adaptive probabilities
In order to analyze the performance contribution of employing adaptive probabilities for neighborhood structures in VNS, we compared the results of the proposed heuristic (AVNS) with and without adaptive component on instances having 20 and 40 jobs. The version of the proposed heuristic without adaptive component is referred to as the VNS. In Table 4, for instances having 20 and 40 jobs, we report the average, minimum, and maximum values of the best objective function values and total run times of the AVNS and its starting solution GRASP. In addition, in the table we report the comparison of the AVNS and VNS in terms of the average, minimum, and maximum values of best objective improvement percentages of the VNS solutions compared to AVNS solutions and the run time increase percentages of the VNS compared to AVNS.
Table 4
Comparative results for AVNS and VNS
Instance
AVNS
AVNS vs. VNS
Group
GRASP
AVNS
VNS
VNS
Best Obj
Time (s)
Best Obj
Time (s)
Best Obj. Imp. (%)
Time Inc. (%)
Avg
2917.22
<1
1771.80
31.55
\(-\)3.72
0.70
20 jobs
Min
2809.00
<1
1000.93
32.00
\(-\)1.11
30.28
Max
4353.90
<1
3623.65
29.00
\(-\)9.92
19.98
Avg
7602.64
29.71
3381.65
153.00
\(-\)5.84
11.97
40 jobs
Min
7199.48
30.00
2496.32
75.00
\(-\)1.13
\(-\)40.55
Max
9703.98
30.00
5535.632
208.00
\(-\)12.71
91.26
The results in Table 4 shows that removing the adaptive component from the AVNS leads to 3.72 % decrease on the average (1.11% min. and 9.92% max.) in the best found objective value for instances having 20 jobs, and 5.84 % decrease on the average (1.13% min. and 12.71% max.) in the best found objective value for instances having 40 jobs. In addition, although it cannot be generalized for all instances, the adaptive component can lead to a run time improvement in the overall search process. We also note that in the proposed constructive matheuristic, GRASP framework primarily addresses the job-nurse assignment component of the problem, while the routing aspect for each nurse is managed through the mathematical model. Since the Traveling Salesman Problem (TSP) is a special case of the routing problem solved for each nurse, as observed in Table 4, the solution time of the constructive matheuristic tends to increase significantly as the number of jobs increases.
4.4 Comparative results on small- and medium-size instances
This section compares the performance of the GRASP and the AVNS with the mathematical model on small- and medium-size instances. Tables 5, 6 and 7 provide the results for small- and medium-size instances having 10, 20, and 30 jobs, respectively. For each instance the objective function value of best found solution, the number of EVs used, the number of unserved jobs, and the run times are reported for the MIP and the AVNS, in addition to the objective function value of the GRASP solution.
Table 5
Comparative results of the small-size instances (having 10 jobs)
Instance
MIP
GRASP
AVNS
MIP-GRASP
MIP-AVNS
GRASP-AVNS
Best
# of
# of Unserved
Time
Best
Time
Best
# of
# of Unserved
Time
Diff
Diff
Imp
Obj
EVs
Jobs
(s)
Obj
(s)
Obj
EVs
Jobs
(s)
(%)
(%)
(%)
10j3n3cs0s-md-w-0sy-W1
2596.30
3
1
< 10
2599.12
< 1
2596.30
3
1
< 10
\(-\)0.1
0.0
0.1
10j3n3cs1s-md-w-0sy-W2
1815.17
3
0
< 10
1823.42
< 1
1815.17
3
0
< 10
\(-\)0.5
0.0
0.5
10j3n3cs1s-md-t-0sy-W3
1836.09
3
0
< 10
1862.40
< 1
1836.09
3
0
< 10
\(-\)1.4
0.0
1.4
10j3n3cs1s-md-w-0sy-W4
2513.55
3
1
< 10
2522.99
< 1
2513.55
3
1
< 10
\(-\)0.4
0.0
0.4
10j3n3cs2s-md-w-0sy-W5
1112.47
2
0
< 10
1217.00
< 1
1112.47
2
0
< 10
\(-\)9.4
0.0
8.6
10j3n3cs2s-md-w-0sy-W6
1835.22
2
1
< 10
2494.35
< 1
1835.22
2
1
< 10
\(-\)35.9
0.0
26.4
10j3n3cs2s-md-t-0sy-W7
2530.69
3
1
< 10
3144.94
< 1
2530.69
3
1
< 10
\(-\)24.3
0.0
19.5
10j3n3cs2s-md-t-0sy-W8
2597.23
3
1
< 10
3126.15
< 1
2597.23
3
1
< 10
\(-\)20.4
0.0
16.9
10j3n3cs2s-md-t-0sy-W9
1170.13
2
0
< 10
1799.39
< 1
1170.13
2
0
< 10
\(-\)53.8
0.0
35.0
10j3n3cs2s-md-w-2sy-W10
1862.20
3
0
< 10
2639.69
< 1
1862.20
3
0
< 10
\(-\)41.8
0.0
29.5
10j3n3cs0s-md-w-0sy-R1
1677.52
3
0
< 10
1750.57
< 1
1677.52
3
0
< 10
\(-\)4.4
0.0
4.2
10j3n3cs1s-md-w-0sy-R2
2645.21
3
1
< 10
3412.11
< 1
2645.21
3
1
< 10
\(-\)29.0
0.0
22.5
10j3n3cs1s-md-t-0sy-R3
2478.36
3
1
< 10
2479.98
< 1
2478.36
3
1
< 10
\(-\)0.1
0.0
0.1
10j3n3cs1s-md-w-0sy-R4
2425.92
2
2
< 10
2496.56
< 1
2425.92
2
2
< 10
\(-\)2.9
0.0
2.8
10j3n3cs2s-md-w-0sy-R5
2598.26
3
1
< 10
2610.98
< 1
2598.26
3
1
< 10
\(-\)0.5
0.0
0.5
10j3n3cs2s-md-w-0sy-R6
2429.78
2
2
< 10
2536.13
< 1
2429.78
2
2
< 10
\(-\)4.4
0.0
4.2
10j3n3cs2s-md-t-0sy-R8
1151.94
2
0
< 10
1359.67
< 1
1151.94
2
0
< 10
\(-\)18.0
0.0
15.3
10j3n3cs2s-md-t-0sy-R9
2416.14
3
1
< 10
2515.04
< 1
2416.14
3
1
< 10
\(-\)4.1
0.0
3.9
10j3n3cs2s-md-w-2sy-R10
1898.30
3
0
< 10
2765.95
< 1
1898.30
3
0
< 10
\(-\)45.7
0.0
31.4
Min
2
0
< 10
\(-\)53.8
0.0
0.07
Max
3
2
< 10
\(-\)0.1
0.0
34.97
Avg
2.7
0.6
< 10
\(-\)14.9
0.0
11.25
Table 6
Comparative results of the medium-size instances having 20 jobs
Instance
MIP
GRASP
AVNS
MIP-GRASP
MIP-AVNS
GRASP-AVNS
Best
# of
# of Unserved
Time
Best
Time
Best
# of
# of Unserved
Time
Diff
Diff
Imp
Obj
EVs
Jobs
(s)
Obj
(s)
Obj
EVs
Jobs
(s)
(%)
(%)
(%)
20j6n4cs0s-md-w-0sy-W1
1501.19
3
0
10,800
2809.00
< 1
1000.93
2
0
32
\(-\)87.1
33.3
64.4
20j6n4cs1s-md-w-0sy-W2
2088.04
4
0
10,800
2811.13
< 1
2075.86
4
0
28
\(-\)34.6
0.6
26.2
20j6n4cs1s-md-t-0sy-W3
1559.02
3
0
10,800
2268.00
< 1
1529.31
3
0
25
\(-\)45.5
1.9
32.6
20j6n4cs1s-md-w-0sy-W4
1576.56
3
0
10,800
2900.74
< 1
1549.10
3
0
35
\(-\)84.0
1.7
46.6
20j6n4cs2s-md-w-0sy-W5
1118.97
2
0
10,800
2796.20
< 1
1118.07
2
0
38
\(-\)149.9
0.1
60.0
20j6n4cs2s-md-w-0sy-W6
2141.95
4
0
10,800
2831.38
< 1
1637.02
3
0
29
\(-\)32.2
23.6
42.2
20j6n4cs2s-md-t-0sy-W7
1626.81
3
0
10,800
2898.84
< 1
1612.78
3
0
29
\(-\)78.2
0.9
44.4
20j6n4cs2s-md-t-0sy-W8
1706.18
3
0
10,800
2469.46
< 1
1702.76
3
0
25
\(-\)44.7
0.2
31.0
20j6n4cs2s-md-t-0sy-W9
1681.91
3
0
10,800
2923.21
< 1
1671.98
3
0
30
\(-\)73.8
0.6
42.8
20j6n4cs2s-md-w-2sy-W10
1668.91
3
0
10,800
2832.74
< 1
1656.38
3
0
37
\(-\)69.7
0.8
41.5
20j6n4cs0s-md-w-0sy-R1
1623.43
3
0
10,800
3001.47
< 1
1601.46
3
0
27
\(-\)84.9
1.4
46.6
20j6n4cs1s-md-w-0sy-R2
2174.20
4
0
10,800
3011.82
< 1
2173.67
4
0
32
\(-\)38.5
0.0
27.8
20j6n4cs1s-md-t-0sy-R3
2139.52
4
0
10,800
2920.49
< 1
1652.02
3
0
36
\(-\)36.5
22.8
43.4
20j6n4cs1s-md-w-0sy-R4
1613.73
3
0
10,800
2806.50
< 1
1592.26
3
0
28
\(-\)73.9
1.3
43.3
20j6n4cs2s-md-w-0sy-R5
1725.45
3
0
10,800
2955.26
< 1
1710.85
3
0
40
\(-\)71.3
0.8
42.1
20j6n4cs2s-md-w-0sy-R6
1657.97
3
0
10,800
2879.13
< 1
1643.80
3
0
33
\(-\)73.7
0.9
42.9
20j6n4cs2s-md-t-0sy-R7
3676.26
5
1
10,800
4353.90
< 1
3623.65
5
1
29
\(-\)18.4
1.4
16.8
20j6n4cs2s-md-t-0sy-R8
2273.01
4
0
10,800
2916.10
< 1
1879.20
3
0
39
\(-\)28.3
17.3
35.6
20j6n4cs2s-md-t-0sy-R9
2265.40
4
0
10,800
2967.48
< 1
2257.82
4
0
31
\(-\)31.0
0.3
23.9
20j6n4cs2s-md-w-2sy-R10
2283.17
4
0
10,800
2991.55
< 1
1747.01
3
0
28
\(-\)31.0
23.5
41.6
Min
2
0
25
\(-\)149.9
0.0
16.8
Max
5
1
40
\(-\)18.4
33.3
64.4
Avg
3.2
0.1
31.6
\(-\)59.4
6.7
39.8
Table 7
Comparative results on medium-size instances having 30 jobs
Instance
MIP
GRASP
AVNS
MIP-GRASP
MIP-AVNS
GRASP-AVNS
Best
# of
# of Unserved
Time
Best
Time
Best
# of
# of Unserved
Time
Diff
Diff
Imp
Obj
EVs
Jobs
(s)
Obj
(s)
Obj
EVs
Jobs
(s)
(%)
(%)
(%)
30j10n5cs0s-md-w-0sy-W1
2468.03
5
0
10,800
4837.24
3
1935.54
4
0
104
\(-\)96.0
21.6
60.0
30j10n5cs1s-md-w-0sy-W2
2472.76
5
0
10,800
4490.47
4
1945.24
4
0
84
\(-\)81.6
21.3
56.7
30j10n5cs1s-md-t-0sy-W3
2446.53
5
0
10,800
4404.14
4
1963.69
4
0
67
\(-\)80.0
19.7
55.4
30j10n5cs1s-md-w-0sy-W4
2451.95
5
0
10,800
3372.34
4
2429.96
5
0
94
\(-\)37.5
0.9
27.9
30j10n5cs2s-td-w-0sy-W5
2445.96
5
0
10,800
4236.49
3
1918.27
4
0
48
\(-\)73.2
21.6
54.7
30j10n5cs2s-wd-w-0sy-W6
2547.62
4
0
10,800
4320.42
5
2001.38
4
0
75
\(-\)69.6
21.4
53.7
30j10n5cs2s-wd-t-0sy-W7
2476.05
5
0
10,800
4330.03
4
1955.82
4
0
71
\(-\)74.9
21.0
54.8
30j10n5cs2s-wd-t-0sy-W8
2562.10
5
0
10,800
4378.92
4
2021.35
4
0
96
\(-\)70.9
21.1
53.8
30j10n5cs2s-wd-t-0sy-W9
1958.39
4
0
10,800
4328.67
3
1937.52
4
0
62
\(-\)121.0
1.1
55.2
30j10n5cs2s-wd-w-2sy-W10
4073.24
5
2
10,800
4307.45
4
2464.30
5
0
67
\(-\)5.7
39.5
42.8
30j10n5cs0s-md-w-0sy-R1
3030.42
6
0
10,800
4621.91
5
2526.86
5
0
62
\(-\)52.5
16.6
45.3
30j10n5cs1s-md-w-0sy-R2
2492.15
5
0
10,800
4276.42
4
1952.76
4
0
92
\(-\)71.6
21.6
54.3
30j10n5cs1s-md-t-0sy-R3
3098.16
6
0
10,800
4714.52
4
2572.14
5
0
104
\(-\)52.2
17.0
45.4
30j10n5cs1s-md-w-0sy-R4
3053.95
6
0
10,800
4498.27
4
2505.24
5
0
80
\(-\)47.3
18.0
44.3
30j10n5cs2s-td-w-0sy-R5
2743.28
5
0
10,800
4580.94
4
2097.95
4
0
64
\(-\)67.0
23.5
54.2
30j10n5cs2s-wd-w-0sy-R6
3162.59
6
0
10,800
4635.34
4
2744.99
5
0
67
\(-\)46.6
13.2
40.8
30j10n5cs2s-wd-t-0sy-R7
2650.60
5
0
10,800
5326.18
4
2607.46
5
0
83
\(-\)100.9
1.6
51.0
30j10n5cs2s-wd-t-0sy-R8
3127.80
6
0
10,800
4498.19
4
2563.55
5
0
61
\(-\)43.8
18.0
43.0
30j10n5cs2s-wd-t-0sy-R9
3111.50
6
0
10,800
5712.43
4
3067.68
6
0
95
\(-\)83.6
1.4
46.3
30j10n5cs2s-wd-w-2sy-R10
5217.25
7
2
10,800
5348.31
3
2787.79
5
0
101
\(-\)2.5
46.6
47.9
Min
4
0
48
\(-\)121.0
0.9
27.9
Max
6
0
104
\(-\)3.0
46.6
60.0
Avg
4.6
0.0
78.9
\(-\)63.9
18.3
49.4
According to the Table 5, all small-size instances can be solved to optimality by both the MIP and the AVNS within 10 s. The AVNS improves the GRASP solution by 11% on the average.
According to the results in Table 6, for medium-size instances having 20 jobs, the MIP cannot guarantee the optimality within 3 h for any instance and the AVNS provides 6.7% better results on the average within 40 s. The number of EVs used in the AVNS are fewer than the MIP in 5 out of 20 instances. The AVNS improves the GRASP solution by 39.8% on the average.
According to the results in Table 7, for medium-size instances with 30 jobs, the MIP cannot guarantee the optimality within 3 h and compared to the MIP, the AVNS provides 18.3% better results on average (46.6% max., 0.9% min) within 2 min. The number of EVs used in the AVNS solutions are fewer than the MIP solutions in 15 out of 20 instances. The AVNS improves the GRASP solution by 49.4% on average.
Table 8 provides the average results for small- and medium-size instances in terms of the best objective value and the solution time for the MIP, GRASP, and AVNS, and the percentage differences between the best found solutions. Table 8 shows that as the number of jobs increases, the difference between the quality of the best found solutions of the AVNS and the MIP and the improvement percentage of the AVNS on the GRASP solution increase.
Table 8
Average results on small- and medium-size instances
|J|
MIP
GRASP
AVNS
Best Obj
Time (s)
Best Obj
Time (s)
MIP-GRASP Diff (%)
Best Obj
Time (s)
MIP-AVNS Diff (%)
GRASP-AVNS Imp (%)
10
2070.14
< 10
2345.49
< 1
\(-\)14.9
2070.14
< 10
0
11.2
20
1905.08
10,800
2889.89
< 1
\(-\)59.4
1786.73
32
6.7
39.8
30
2879.52
10,800
4691.62
3.9
\(-\)63.9
2258.54
88
18.3
49.4
4.5 Results on large-size instances
The results of the proposed GRASP and AVNS algorithms for large-size instances having 50 jobs are presented in Table 9 and the results of the instances that have 40 and 60 jobs are presented in Tables 16 and 17 in the Appendix. The tables report the objective function value for the best solutions found in GRASP and AVNS, the solution time of AVNS, the share of each cost term in the total cost of the AVNS solutions and the percentage improvement of AVNS in the GRASP solutions.
Table 9 indicates that AVNS improves the GRASP solution by 61.3% on average (49.1% minimum) in at most 11 min. The fixed nurse costs account for 87.6% on the average of the total cost and the travel costs account for 7.9% on the average. The unserved jobs occur in 4 out of 14 instances leading to a share in between 14.3\(\%\) and 18\(\%\). The results in Table 16 show that the AVNS improves the GRASP solution by 55.5% on the average (43.0% minimum) within at most 4 min. The fixed nurse cost has the largest share in all instances accounting for 89.9% of the total cost on the average. The travelling cost accounts for 6.2% of the total cost on the average, demonstrating the need for efficient routing. In 3 out of 14 instances, there are unserved jobs leading to an unserved job cost share in between 14.5\(\%\) and 20.7\(\%\). Table 17 indicates that the AVNS improves the GRASP solution by 60.1% on the average (44.6% min) within at most 16 min. The fixed nurse costs account for 80.4% on the average of the total cost and the travel costs account for 9.9% on the average. The unserved jobs occur in half of 14 instances leading to a share in between 12.1\(\%\) and 35.9\(\%\).
Table 9
GRASP and AVNS results for instances with 50 jobs
Instance
GRASP
AVNS
GRASP-AVNS
Best Obj
Time (s)
Best Obj
Time (s)
Fixed Nurse Cost (%)
Travelling Cost (%)
Unserved Job Cost(%)
Imp (%)
50j-G1–1
8293.67
62
3594.40
479
91.8
8.2
0.0
56.7
50j-G1–2
11808.35
57
3561.78
269
92.7
7.3
0.0
79.8
50j-G2–1
9680.82
56
2615.12
353
87.9
12.1
0.0
73.0
50j-G2–2
9153.51
58
3661.45
324
90.1
9.9
0.0
60.0
50j-G3–1
10699.81
60
4890.73
426
77.7
5.9
17.1
54.3
50j-G3–2
9322.02
60
3046.92
427
93.5
6.5
0.0
67.3
50j-G4–1
9725.85
55
3505.86
282
94.1
5.9
0.0
64.0
50j-G4–2
9279.71
57
2942.83
229
95.1
4.9
0.0
68.3
50j-G5–1
7835.76
58
3603.96
226
91.6
8.4
0.0
54.0
50j-G5–2
10157.95
62
4595.54
575
93.6
6.4
0.0
54.8
50j-G6–1
12360.55
59
3831.33
321
90.0
10.0
0.0
69.0
50j-G6–2
12511.05
63
4445.16
372
77.6
4.4
18.0
64.5
50j-G7–1
11942.40
64
5581.73
416
77.0
8.6
14.3
53.3
50j-G7–2
10549.91
62
5365.91
224
73.6
11.5
14.9
49.1
Min
224
73.6
4.4
0.0
49.1
Max
575
95.1
12.1
18.0
73.0
Avg
351.8
87.6
7.9
4.5
61.3
4.6 Effects of problem parameters
This section analyzes the effects of the problem parameters such as the existence of simultaneous jobs, the level of variety in job durations, the existence of competency levels, synchronization, the dispersion of patient locations, and the heterogeneity of the vehicle fleet on the results.
The effect of the job location selection method is analyzed by comparing the average results of G1 and G2, in which wrs is used, with the average results of G3 and G4, in which rs is used. The comparative results are presented in Table 10 in terms of the best objective value, the value of each cost term in the objective function, and the average working, spare, service, and travel times of nurses.
Table 10
Effect of the dispersion of patient location (i.e., location selection method used in data generation) on results
Loc. Selection
Groups
Best
Fixed Nurse
Travelling
Unserved Job
Avg. Working
Avg. Spare
Avg. Service
Avg. Travel
Method
Obj
Cost
Cost
Cost
Time (min.)
Time (min.)
Time (min.)
Time (min.)
wrs
G1, G2
3669.30
3304.17
273.47
66.67
518.22
60.18
282.67
175.36
rs
G3, G4
4052.82
3266.67
319.49
466.67
520.95
42.47
269.19
209.27
According to Table 10, the total cost of AVNS solutions for instances using wrs method is 10% lower on the average than that of the instances using rs selection method. As job locations are more dispersed when rs is used and are closer when wrs is used, the average travel time and therefore, the share of the travelling cost is larger and the number of jobs that cannot be served is higher when rs is used although the average working and service times are close to each other for both cases. This table also shows that the average spare times are very low and nurses are efficiently utilized during the working day.
The effect of the competency requirement is analyzed by comparing the average results of G1, in which all jobs have identical competency requirement, with the average results of G5, in which each job requires a specific level (1, 2, or 3) from one competency type. The comparative results are presented in Table 11 in terms of the best objective value, the value of each cost term in the objective function, and the average working, spare, service, and travel times of nurses.
Table 11
Effects of the variety in job competency requirements on results
|U|
Group
Best
Fixed Nurse
Travelling
Unserved Job
Avg. Working
Avg. Spare
Avg. Service
Avg. Travel
Obj
Cost
Cost
Cost
Time (min.)
Time (min.)
Time (min.)
Time (min.)
0
G1
4088.89
3383.33
305.56
400.00
524.50
44.56
267.46
212.48
1
G5
4131.04
3550.00
297.71
266.67
522.36
58.16
272.38
191.82
According to Table 11, the fixed nurse costs are higher when jobs require different levels of competency (for group G1) and nurses can be utilized more efficiently (with lower spare time on the average) if each nurse can serve any job (for group G5). Although the unserved job cost for group G1 may be expected as lower than that of group G5, as G1 instances utilize fewer nurse, the unserved job cost for group G5 is smaller than that of group G1.
The effect of the variety in job durations is analyzed by comparing the average results of G5, in which job durations are random in between 20 and 60, with the average results of G6, in which job durations are random in between 10 and 90. The comparative results are presented in Table 12 in terms of the best objective value, the value of each cost term in the objective function, and the average working, spare, service, and travel times of nurses.
Table 12
Effects of the level of variety in job durations on results
Job
Group
Best
Fixed Nurse
Travelling
Unserved Job
Avg. Working
Avg. Spare
Avg. Service
Avg. Travel
Durations
Obj
Cost
Cost
Cost
Time (min.)
Time (min.)
Time (min.)
Time (min.)
random in [20, 60]
G5
4131.04
3550.00
297.71
266.67
522.36
58.16
272.38
191.82
random in [10, 90]
G6
4764.57
4066.67
297.90
400.00
522.79
70.68
284.92
167.2
According to Table 12, the results of instances having job durations in between 20 and 60 are 13% smaller on the average than that of the instances having job durations in between 10 and 90. The larger average and variance in job durations for group G6 result in longer service times for nurses, higher fixed nurse costs and larger unserved job costs.
The effect of the existence of synchronized jobs is analyzed by comparing the average results of G5, in which there is no synchronized job, with the average results of G7, in which 10 % of all jobs are synchronized jobs. The comparative results are presented in Table 13 in terms of the best objective value, the value of each cost term in the objective function, and the average working, spare, service, and travel times of nurses.
Table 13
Effects of the existence of synchronized jobs on results
% of
Group
Best
Fixed Nurse
Travelling
Unserved Job
Avg. Working
Avg. Spare
Avg. Service
Avg. Travel
Sync. Jobs
Obj
Cost
Cost
Cost
Time (min.)
Time (min.)
Time (min.)
Time (min.)
0
G5
4131.04
3550.00
297.71
266.67
522.36
58.16
272.38
191.82
10
G7
4812.23
3850.00
428.90
533.33
522.51
44.71
252.16
225.64
According to Table 13, the total cost of instances without synchronized jobs is 15% lower on the average than the instances having synchronized jobs. In group G7, in which 10% of all jobs are synchronized, 10% of patients require to be served by more than one nurse at the same time in the patient’s home. Therefore, more nurses are required and the fixed nurse cost in the G7 instances is 8% higher on the average than that of the G5 instances. Although the average working times for nurses are very close for these two groups; for G7 instances, the average nurse service times and travel times are longer and the average travelling cost and unserved job cost are significantly higher.
We analyze how the variety of vehicle types affects the results for large-size instances (G1-G7). To do this, we conduct a comparative assessment by contrasting the average results obtained when employing a homogeneous fleet comprising exclusively of type ’a’ vehicles (characterized by the lowest consumption rate and the smallest battery capacity) with those achieved using a mixed fleet of vehicles. These comparative findings are comprehensively presented in Table 14, encompassing the optimal objective value, the individual cost components within the objective function, as well as the average durations of nurses’ working, spare, service, and travel times.
Table 14
Effects of vehicle types on results
Vehicle
Group
Best
Fixed Nurse
Travelling
Unserved Job
Avg. Working
Avg. Spare
Avg. Service
Avg. Travel
Fleet
Obj
Cost
Cost
Cost
Time (min.)
Time (min.)
Time (min.)
Time (min.)
Homogeneous
G1 to G7
4250.59
3517.14
350.59
342.86
520.45
58.93
270.01
191.50
Heterogeneous
G1 to G7
4186.51
3488.33
354.36
323.81
520.85
51.32
270.98
198.55
Table 14 reveals that instances that utilize a heterogeneous fleet lead to a decrease in the objective function compared to those reliant on a homogeneous fleet. This result is mainly attributed to the larger battery capacity inherent in the heterogeneous fleet, which allows for more extensive travel without the need for recharging. Consequently, this leads to a reduction in the fixed nurse cost within these instances. Additionally, it is worth noting that the unserved job cost in scenarios involving a heterogeneous fleet is notably lower compared to instances with a homogeneous fleet. Although the average working time for nurses remains relatively consistent across both groups, instances leveraging a heterogeneous fleet tend to exhibit longer average travel times alongside shorter average spare times.
5 Conclusions
This paper delves into a practical challenge encompassing various facets such as heterogeneous electric vehicles, fast chargers, synchronized job scheduling, and time windows within the context of home healthcare routing and scheduling. The primary objective is the minimization of the total cost incurred, which comprises energy consumption, fixed nurse expenses, and the cost associated with unattended jobs. We have introduced a hybrid metaheuristic based on adaptive variable neighborhood search (AVNS) algorithm, which employs a GRASP algorithm that uses a more easily solvable submathematical model to obtain an initial solution. Our algorithms encompass several specialized heuristic mechanisms designed to address the unique intricacies of the problem. In particular, in our AVNS algorithm, we depart from the traditional variable neighborhood search by introducing adaptive probabilities to select each neighborhood, improving its problem-solving capabilities.
We have conducted extensive computational studies on small, medium and large instances. For small instances featuring 10 jobs, our hybrid metaheuristic algorithm consistently identifies optimal solutions in 10 s. In medium-sized instances involving 20 and 30 jobs, our metaheuristic yielded 6.7% and 18.3% better results on average, respectively, compared to MIP running with a three-hour time limit. Furthermore, we observed a significant improvement in the results of the constructive GRASP heuristic with the use of the hybrid metaheuristic. In other words, our metaheuristic has generated high-performance solutions in a short time, demonstrating its relevance for practical operations. We conducted additional computational experiments to explore the impact of various parameters of the problem. These factors include the presence of simultaneous jobs, the variety of job durations, the considerations of competency level, the heterogeneity of the vehicle fleet and the dispersion of the patient’s location. These analyses provide valuable insights into the problem sensitivity to these parameters. Finally, our study quantifies the advantages of using heterogeneous electric vehicles over homogeneous counterparts, offering practical guidance for decision-makers in home healthcare routing and scheduling.
Future work could explore the stochastic extensions of the current problem. Unforeseen events may occasionally occur, leading to delays in the provision of health services, which can compromise their quality or safety. Patients typically require multiple care interventions throughout the day, some of which may need to be carried out simultaneously, such as dressing, mobilizing, and bathing. Deterministic models overlook these kinds of real-life uncertainty, which can arise unexpectedly and consequently disrupt adherence to predetermined schedules. In the context of home health care, the primary sources of uncertainty are travel and service durations. These extensions could be addressed in future studies through specifically designed solution methods for stochastic programming such as stochastic mixed integer models, chance constrained models, metaheuristics, matheuristics, stochastic programming models with recourse, and simulations techniques. By incorporating stochastic elements, researchers can better capture the inherent uncertainties in home healthcare scheduling and routing, leading to more robust and effective solutions.
Acknowledgements
This work was supported by the Scientific and Technological Research Council of Türkiye (TÜBİTAK) under grant number 119M007. This support is gratefully acknowledged. The authors are indebted to Alican Yılmaz for his technical support. Thanks are due to two referees and associate editor for their valuable comments.
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.