key: cord-0047427-qeqd37sz authors: Nucci, F. title: Multi-shift Single-Vehicle Routing Problem Under Fuzzy Uncertainty date: 2020-06-10 journal: Intelligent and Fuzzy Techniques: Smart and Innovative Solutions DOI: 10.1007/978-3-030-51156-2_189 sha: b34431da7aafa6578e5d1ecf24da8aac202964c1 doc_id: 47427 cord_uid: qeqd37sz This research considers the single-vehicle routing problem (VRP) with multi-shift and fuzzy uncertainty. In such a problem, a company constantly uses one vehicle to fulfill demand over a scheduling period of several work shifts. In our case, a crew executes maintenance jobs in different sites. The working team runs during different work shifts, but recurrently returns to the depot by the end of the shift (overtime avoidance). The goal consists in minimizing the number of work shifts (makespan). We observe the impact of uncertainty in travel and maintenance processing time on the overtime avoidance constraint. We realize an Artificial Immune Heuristic to get optimal solutions considering both makespan and overtime avoidance. First, we present a Pareto-based framework to evaluate the uncertainty influence. Then, we show a numerical real case study to survey the problem. In particular, a case study scenario has been created on the basis of the environmental changes in travel and processing times observed in Italy during the Covid-19 lockdown period (started on March 9, 2020). Results present important improvements are obtained with the proposed approach. Vehicle routing problem (VRP) consists in determining a set of routes to visit a set customers, in order to minimize the path length. Different versions of the VRP exist. If customers are only available in a time windows, a VRP with Time Windows (VRPTW) is considered. Basic variants of the VRP consider the route planning for a vehicle fleet in a single period (shift). In that case, the vehicles return to the depot before the end of the shift. This problem originates from a healthcare routing issue [1] [2] [3] . When the health care company ships products to medical sites, if overtime is allowed, performance could be significantly improved. For example, if a location scheduled for the next shift is on the current return route to the depot, a limited overtime allows the vehicle to serve it. This can significantly reduce the workload of the next shift. On one hand, overtime reduces the total number of shifts necessary to complete the work. On the other, the continuous use of overtime can lead to crew health problems [4] . Since overtime increases the chance of micro-sleep in car drivers [5] , company manager could be accused of vehicle collision due to wrong workload scheduling [6] . Indeed, shift planning should maintain shift duration as constant as possible. Uncertainty on travel and processing time can lead to unexpected overtime and performance reduction. Frequently, in optimization problems, data are supposed to be known with certainty. However, in practice this is infrequent. More generally, real data are dependent on uncertainty due to their irregular nature. Since the solution of the optimization problem typically shows a great tendency to data disruption, overlooking the ambiguity of the data can lead to non-optimal or unrealistic solutions for a real case. Robust Optimization is a significant technique to address optimization problems subject to uncertainty [7] . In this case, a methodology is needed to analyze the trade-off between performance and robustness. On one hand, Stochastic VRP (SVRP) was introduced in [8] when uncertainty is statistically known. See [9, 10] for a complete review of SVRP. On the other, Fuzzy set theory is a useful approach to handle non-stochastic uncertainty [11] . Fuzzy sets theory is widely adopted for studying the influence of uncertain factors on VRP [12] [13] [14] [15] [16] [17] [18] [19] [20] . In these works, Fuzzy VRP is analyzed and fuzzy set theory is adopted to manage such uncertain data. In this paper, we examine a multi-shift VRP with travel and processing time modeled as Fuzzy Numbers. The objective consists in reducing both overtime and makespan. The question we considered is derived from a routing problem in maintenance activities as reported in [21] [22] [23] [24] [25] . A maintenance team performs jobs in different sites using a vehicle for movements. A crew works in shifts and should come back to the depot before the shift ends. The goal is completing the maintenance activities in various places reducing both overtime and makespan. We investigate the influence of the uncertainty of driving and job processing time on the objective. The originality of the paper consists in the meta-heuristic approach adopted to solve the problem. Indeed, our meta-heuristic uses a 2-factor ranking method, based on overtime and makespan, to sort the solution set at each step. Consequently, a Pareto set of optimal solutions exists. Considering the papers already examined and two additional review articles [26, 27] , it can be established that no such an approach exists. The body of this paper is structured as follows. In Sect. 2, we report the problem formulation. In Sect. 3, we propose the Artificial Immune Heuristic to solve the problem. We present in Sect. 4 a case study solved with the proposed approach, considering two scenarios: before and after Covid-19 lockdown in Italy (March 9, 2020). We give concluding remarks in Sect. 5. In the VRP, we assume a horizon of P shifts (periods), and let the set P = {1, 2, ..., P } index the shifts of the planning horizon. Each shift duration is L. On a given planning, we seek to serve a set of N customers. Associated with each customer is a task i to be executed, i ∈ N = {1, 2, ..., N }. Task i processing time is q i . For each shift, the crew departs from and returns to the depot. A travel time between task i and task j locations is defined as d i,j . We assume that triangular inequality is valid for driving times. Any task can be executed in a shift. Our problem objective is to minimize the latest task completions time (makespan). The problem can be represented as a directed graph G = (V, E), where V = N ∪{N +1, . . . , N + P +1}. We create P + 1 depot copies represented by node set {N + 1, . . . , N + P + 1}. Node N + 1 is the origin depot of shift 1. Node N + h represents the destination depot of shift h − 1 together with the origin depot of shift h, with h ∈ {2, . . . , P }. Node N + P + 1 stands for the destination depot of last shift P . A solution problem can be represented as a path in the graph G. Since any path starts at node N + 1 and ends at node N + P + 1, a solution can be synthetically represented by variables ω i ∈ N ∪ {N + 2, . . . , N + P } for i = 1, . . . , N + P − 1. Variable ω i stands for the visiting sequence of location task nodes N and shift break nodes {N + 2, . . . , N + P }. Shift duration is equal to the arrival time at node N + 1 + h and is represented by σ h for h ∈ P. Considering N = 5 tasks and P = 2 shifts, in the solution reported in Fig. 1a , crew executes task 2, 3 and 5 on first shift, whereas task 1 and 4 are allocated in the second shift. Instead in Fig. 1b solution, task 1 is anticipated to shift 1. In solution b, overtime occurs in shift 1 although makespan decreases (shift 2 duration is minimal). We model the uncertainty on driving and working times with Triangular Fuzzy Numbers (TFN), see Fig. 2 . In particular, fuzzy travel time is indicated For this reason, variables related to shift duration σ h become fuzzy and have be analyzed to determine whether overtime occurs. In order to assess whether fuzzy shift duration σ h is lower than maximum shift duration L, we adopt the function Φ( σ h ≤ L) defined in (1) . Such a function calculates the possibility a fuzzy number ( σ h ) is lower than a crisp value (L). It is equal to the portion of the area under the TFN membership function on the left of crisp value. For Artificial Immune Algorithm (AIA) is a meta-heuristic based on animal immune system [28] [29] [30] . This paper proposes a fuzzy AIA to find optimal solutions for the considered problem. In short, AIA stands on behavior of animal immune system that protects against foreign pathogens. Immune system reacts to germs and improves the activity of recognizing and eliminating pathogens by using two principles: clonal selection and affinity maturation. Clonal selection creates new immune cells. Such cells encounter high rate of mutations, along with a selection process. As reported in Fig. 1 , a solution is encoded as a string by using a fixed-length integer code, providing the order in which nodes are reached. For a solution ψ, we adopt an innovative 2-factor affinity. Indeed, a solution ψ is described by the node visiting sequence ω ψ i with i = 1, . . . , N + P − 1 and for each shift the corresponding fuzzy duration σ h is computed. Then, the 2-factor solution affinity is determined as (λ, ρ), where λ represents the makespan and ρ is the possibility no-overtime occurs; λ should be minimized whereas ρ should be maximized. In (2) , L·(P −1) is the maximum length of P −1 shifts and σ B P is the crisp duration of last shift. In (3), the minimum of no-overtime possibilities is calculated over shift set. Considering the two solutions a and b reported in Fig. 1 , the corresponding affinities are the two pairs (λ a , ρ a ) and (λ b , ρ b ) . Performing the Pareto comparison of solution a and b, we have λ a > λ b and ρ a > ρ b (supposing ρ a = 1 and ρ b > 0) , consequently no solution is better than the other. The proposed AIA is described in Table 1 . At Step 1.2, Rule1 is the full random rule: random selection of node ω i ∈ N ∪ {N + 2, . . . , N + P } with i = 1, . . . , N + P − 1. While in Rule2 we choose nodes using a probability that is inversely proportional to the distance between the current node and each candidate node. Mutation operator randomly selects two solution indexes i, j = 1, . . . , N + P − 1 and swaps their content ω i and ω j . If the depot node sequence N + 2, . . . , N + P is unfeasible, mutation is cancelled. Considering the ordinary AIA approach, the innovation of this work relies in the step 2 and 3.1. Indeed, step 2 is used to determine the new antibody affinity, whereas step 3.1 preserves the entire Pareto set in the next population. We validated our approach, described in Sect. 3 and we set AIA parameters as follows: population size popsize = 200, No. generations ng = 10000, No. clones nc = 20, mutation rate mr = 0.75, mutation number per generation nm = 40, No. exchangeable antibodies nea = 20. A real case study, in the field of elevator maintenance and repair, is considered. Since data obtained from the company are protected from disclosure, we report only summary data. Company and its customers are located in Salento, in the southeast region of Italy. Uncertainty affects driving and working times, inferred from empirical data. Maximum shift duration is set to L = 480 min. No. jobs is equal to N = 22, whereas No. shifts is P = 5. A base scenario is considered with crisp job processing time q B i of 40 to 80 min. Processing time uncertainty is 20% of crisp value, that is Fig. 3a along with two manual solutions designed by company experts. Company experts analyzed the eight AIA solutions that dominate their own solutions. Since rightmost AIA solution (λ, ρ) = (2300, 100%) is very conservative, managers are unlikely to accept such a high safety margin. Experts preferred solution (2241, 95%) because makespan decreases by almost one hour with 5% risk. Also, solution (2166, 84%) is remarkable because of the good makespan compared to the significant possibility of 84% to avoid overtime. Managers discarded solutions having ρ < 0.5 because of the high risk of overtime. Another scenario called lockdown was analyzed. Because of the environmental changes in travel and processing times during the Italian Covid-19 lockdown period (started on March 9, 2020), maintenance planning was completely redesigned. From one hand, new activities were introduced in the tasks such as cleaning of surfaces using appropriate disinfection methods and wearing personal protective equipment. Crisp working time increased by 8% plus 10 min. Moreover, processing time uncertainty reached 30% of crisp value. From the other, road traffic decreased significantly. Crisp driving times were reduced by 25%. In lockdown scenario, Fig. 3b shows AIA Pareto optimal solutions. Managers experienced difficulties in designing good planning. Note that P = 6 shifts are necessary to complete the previous job set. Because of the high uncertainty only two Pareto optimal solutions were found with ρ > 0.5. Significant difference exists between AIA and Manual solutions in the lockdown scenario: performing tasks in the same area may not be the best strategy because crew may overrun the shift. On the other hand, a change of zone may lead to a better fit of the tasks in the shift, as travel time is shorter than usual. This study presents the single-vehicle routing problem with multi-shift when fuzzy uncertainty is introduced in driving and job processing times. The objective consists of minimizing both the system makespan and shift overtime occurrence. We provide optimal solutions for the decision-maker considering a 2-factor comparison. Our approach was adopted in a real company case study. During the Italian Covid-19 lockdown period, a new robust maintenance planning was rapidly issued. In the future, the possibility of copying only a subset of Pareto optimal solutions in the next population will be investigated. A multi-shift vehicle routing problem with windows and cycle times A mixed integer formulation and an efficient metaheuristic procedure for the k-Travelling Repairmen Problem New integer programming formulation for multiple traveling repairmen problem The effects of working hours on health: a meta-analytic review Negative impacts of shiftwork and long work hours Shift work and health: current problems and preventive actions Robust vehicle routing problem with deadlines and travel time/demand uncertainty A simulation and statistical analysis of stochastic vehicle routing with timing constraints Stochastic vehicle routing Overview of stochastic vehicle routing problems Vehicle routing optimization with soft time windows in a fuzzy random environment The fuzzy set theory approach to the vehicle routing problem when demand at nodes is uncertain Multiple criteria optimization based on unsupervised learning and fuzzy inference applied to the vehicle routing problem A class of random fuzzy programming model and its application to vehicle routing problem Hybrid adaptive predictive control for the multivehicle dynamic pick-up and delivery problem based on genetic algorithms and fuzzy clustering A multiobjective dynamic vehicle routing problem with fuzzy time windows: model, solution and application Dynamic milk-run OEM operations in over-congested traffic conditions A methodology based on evolutionary algorithms to solve a dynamic pickup and delivery problem under a hybrid predictive control approach An unsupervised fuzzy clustering approach to the capacitated vehicle routing problem A multi-objective memetic algorithm based on locality-sensitive hashing for one-to-many-to-one dynamic pickup-and-delivery problem A grasp with iterated local search for the traveling repairman problem with profits Branch-and-price approaches for the multiperiod technician routing and scheduling problem An approximate dynamic programming method for the multi-period technician scheduling problem with experience-based service times and stochastic customers The vehicle routing problem with hard time windows and stochastic travel and service time The technician routing problem with experience-based service times The vehicle routing problem: state of the art classification and review A review of technician and task scheduling problems, datasets and solution approaches Artificial immune systems -models, algorithms and applications An artificial immune algorithm for the flexible job-shop scheduling problem An artificial immune algorithm for the project scheduling problem under resource constraints