Solution Method
6.3 The Iterative Improvement Heuristic
The IIH optimizes a part of the WRP in each iteration by allowing reallocations of jobs. This section presents possible reallocations of jobs by defining a set of operators and outlines the process of the IIH.
6.3.1 The Operators of the Iterative Improvement Heuristic
The initial WRP is assumed to be relatively efficient on a daily basis, however, changes to the routes may prove to be favorable when considering the weekly problem. To investigate potential changes and utilize the existing routes, four operators are proposed to define possible realloca-tions of jobs; the Intra Swap Operator, the Inter Swap Operator, the Intra Move Operator, and the Inter Move Operator.
Intra Swap Operator
The Intra Swap Operator defines swaps of two jobs within the same route, i.e. the jobs swap indices while the rest of the route is unchanged. An example of an intra swap is illustrated in Figure 6.3, where job 5 and 22 swap index 2 and 5.
Figure 6.3: Example of the Intra Swap Operator Intra Move Operator
The Intra Move Operator defines a move within the route the job currently belongs to, resulting in a change in the index of the job. An example of an intra move is illustrated in Figure6.4, as job 5 moves from index 2 to index 4, resulting in a change in indices,:-1, for jobs 11 and 15, as shown by the stippled square.
Figure 6.4: Example of the Intra Move Operator Inter Swap Operator
The Inter Swap Operator defines two jobs swapping routes, meaning exchange in the employee, day, or both. Figure 6.5shows an example of an inter swap between job 5 and job 21. In this example, job 5 swaps with job 21 from index 2 to 4, from day 1 to 2 and employee 1 to 2. The remaining jobs are unaffected.
Figure 6.5: Example of the Inter Swap Operator Inter Move Operator
The Inter Move Operator defines the move of a job to a different route, implying a different employee, day, or both. An example of an inter move across both day and employee is shown in Figure6.6. The example shows how job 5 with index 2 from the route belonging to employee=1 on day , moves to the route belonging to employee on day with index 5. The figure also
marks the jobs on 31 and 32 affected by the operator with a stippled square, having changed indices: to: 1 and:+1 respectively.
Figure 6.6: Example of the Inter Move Operator
6.3.2 The Process of the Iterative Improvement Heuristic
This section outlines the process of the IIH. The IIH optimizes parts of the WRSP while con-tinuously updating the routes to generate improved current solutions, based on an initial WRP.
The WRSP is solved using a mathematical model that allows the reallocation of jobs according to the operators describes in Section6.3.1. As the mathematical model permits several realloca-tions simultaneously, the risk of reaching a local optimum is decreased. The starting point is an initial Weekly Route Plan, which is set to be the Current Solution. At the beginning of the IIH, the entire Current Solution is fixed. The fixed Current Solution comprises fixed jobs, meaning that the related preceding job, employee, and day is fixed accordingly. The set of fixed jobs is denoted J . Parts of this fixed Current Solution is iteratively opened up and added to the optimization problem, which is solved by the mathematical model. The optimization problem then comprises a set of open jobs J$, and a set of jobs R$ in open routes, representing the only jobs allowed to be reallocated. The process of the IIH is presented in Algorithm 1. The algorithm consists of two steps, step one comprising lines 3-4 and step two lines 5-8.
In step one, a set of open jobs J$ of the Current SolutionB⇠, is chosen by applying the func-tion$?4= >1(4;42C8>=(B⇠) to the Current Solution. The mathematical model solves the problem comprising only the set of open jobs J$, allowing reallocations according to any of the moves and swaps defined by the operators. The output from this step is a new Current Solution B⇠ containing updated routes. This is the input of step two of the IIH.
In step two, the search space is enlarged through increasing the number of possible reallocations of the set of open jobs, by opening routes in the Current Solution. The$?4='>DC4(4;42C8>=(B⇠,3,=) function is applied to the Current Solution and used to select jobs in an open route, denoted as the set R$. The open route is not defined as an entire route, but may also be only a selection of jobs in a route. The jobs in the open route are still fixated to a route with a given employee
= on a given day3 in the Current Solution, but not to the preceding job. The model now solves the optimization problem comprising the open jobs and jobs in open routes, being the set of J$ and R$. The reallocations of the open jobs are still allowed according to any of the operators.
In addition, the open jobs may interact with the open route by performing inter moves to the open route. Jobs in the open routes are only permitted to be reallocated according to the intra swap and intra move operator, as these jobs are still fixated to an employee and a day. This process continues until all routes have been explored as open routes for the reallocation of the
open jobs. The Current Solution, B⇠, is updated every time a new route is opened, and the output of step two is an improved Current Solution.
Algorithm 1:The Iterative Improvement Heuristic Input: Initial Solution,B
Input: Maximum Run Time)C>C0;
Output: Current Solution,B⇠
1 B⇠ :=B
2 while run time)C>C0; do
3 J$ := OpenJobSelection(B⇠)
4 B⇠ solve mathematical model withJ$
5 for3 2D,=2 N3 do
6 R$:= OpenRouteSelection (B⇠,3,=)
7 B⇠ solve mathematical model withJ$ andR$
8 end
9 end hei
One round of the heuristic search consists of multiple iterations of solving the mathematical model until all routes of the week have been explored. The while-loop starting on line 2 illus-trates that the heuristic search may be iteratively conducted by choosing a new set of open jobs.
In that case, the output of step two will be the input of step one, and the open jobs are chosen by applying$?4= >1(4;42C8>=(B⇠), to the new Current Solution.
Figure 6.7illustrates how a set of open jobs and a set of jobs in open routes can be chosen from a solution. In this example, the open jobs are jobs 5, 10, 18, and 20, and the open route is the route belonging to employee=1 on day33, comprising jobs 13, 4, 7, 32, 16 and 34.
Figure 6.7: Example of Two Open Jobs and an Open Route
Figure 6.8 illustrates how the mathematical model may choose a combination of moves and swaps defined by the operators to improve the solution. This example shows an inter move of job 5 and an intra swap of job 4 and 34.
Figure 6.8: Example of the Intra Swap Operator and the Inter Move Operator
The updated Current Solution is presented in Figure 6.9, illustrating the affected parts by stippled squares. Jobs 11, 15, 22, 30, and 24 change indices to:-1 due to the inter move of job
5. Job 5 changes index, day, and employee, while jobs 34 and 4 change indices only.
Figure 6.9: Example of Changes in Routes due to the Operators