# Balancing Staff Finishing Times vs. Minimizing Total Travel Distance in Home Healthcare Scheduling
## 4 Solution Method  
Vehicle Routing with Time Windows is a well-known NP-hard problem whose complexity increases exponentially with the number of variables. Only in rare instances can the problem be precisely solved. Moreover, when the number of nodes is increased, the algorithm is unable to discover an exact solution in some instances. Consequently, metaheuristics are alternative techniques for locating solutions that are sufficient although not optimal. The simulated annealing algorithm (SA) is a local search-based heuristic algorithm that can prevent becoming caught in a local optimum and help explore a larger portion of the search space. Inspired by the work of [29] on the annealing process, SA has been effectively used to solve several combinatorial problems, including location, vehicle and other related problems. The SA algorithm typically begins with an initial solution, which is subsequently improved with each iteration by neighborhood operators (or local search algorithms) based on the problem's characteristics. Neighborhood operators such as swap, move, insert, reverse, ruin-and-recreate, path exchange, etc., are typically employed to address routing problems. Each algorithm containing SA that is used to solve a combinatorial optimization problem always reaches a local optimum. One method for escaping the local optimum is to allow the solution to relocate to a neighborhood solution that is worse than the current one,and then apply the same neighborhood operators to bring the solution back to a new local optimum. In SA, probability is used to determine when the worst potential solution should be accepted. The probability is determined by the variable temperature, which decreases with every iteration. The higher the temperature, the greater the opportunity to switch to a worse solution. In this case, we use the Bolzman function to calculate the probability of accepting the worst solution. As mentioned earlier, our model was formulated using bi-objective mixed integer programming. Our proposed algorithm is based on simulated annealing to solve the problem by converting it to a single-objective problem using the weighted sum of two objectives. In this case, there are two weight coefficients associated with the objective functions where the sum of weights is equal to 1. There are multiple choices to choose from; for the best performance of the algorithm, we limited the set of weights to have only 11 choices: \(\big{\{}\big{(}w_{i},w_{j}\big{)}\big{|}i,j=0,1,\ldots,10,\ w_{i}+w_{j}=10 \big{\}}\). The approach aims to find the Pareto optimal set, which is a set of non-dominated solutions to each other but each is superior to the rest of the solutions in the searching space. Non-dominated solutions are those that have no solution that has a less objective value for all objectives. To optimize multiple objective functions, one objective needs to be sacrificed to improve another. The Pareto set for two objectives, if plotted two-dimensionally, will lie on the surface known as the Pareto front. To obtain the best Pareto set of solutions, we solved the problem using each weighted sum as the single objective function and selected only the pareto solutions to remain in the set. As mentioned above, the problem is an NP-hard problem. To find an optimal solution within a reasonable execution time, we needed to improve the algorithm's efficiency. Here, we provide feasible conditions for preventing the algorithm from searching in an unnecessary solution space. For convenience, the solution is represented in the single vector form. The vector will start with the node \"0\" which is the depot node, followed by the sequence of nodes and finally end at the depot. For example, [0, 1, 2, 3, 0, 4, 5, 0, 6, 7, 8, 0] represents a solution with three routes: the first route starts from depot and visits nodes 1, 2 and 3 before returning to the depot; the second route starts from depot, visits nodes 4 and 5 and then returns to depot; and the third route contains nodes 6, 7 and 8.