Generating Parameters for the Test Instances

To run tests and perform a thorough analysis of the HHC problem, multiple test instances of appropriate sizes must be generated based on the provided data from Visma. To ensure the relevance of the analysis, the structure of the data must be preserved and relative sizes have been used to construct parameters. In cases where the data is insufficient or simply lacking, parameters have been created based on common values from the literature and conversation with the employees in one of the pilot-municipalities. Based on the characteristics described in Section 7.2, this section presents how parameters have been generated to create test instances.

7.3.1 Transition to a New Data Structure

To generate suitable test instances for the model, an appropriate data structure must be created.

In the data set provided, all details are related to a JobID e.g. starting times and duration, but to solve the Weekly Routing and Scheduling Problem (WRSP) efficiently and reduce the complexity of the problem, a new way of structuring the data is introduced. As mentioned, jobs related to a user can be frequent, meaning that certain jobs should be performed a certain amount of times during a week. These jobs can be viewed as completely identical, e.g. distribution of medicine twice a week. Instead of having a set of identical jobs, we create a parenting task, where jobs are instances of the task, and Table 7.4 shows an example of the relation between a task and its user. This example illustrates how the distribution of medicine is a task related to a user, consisting of two identical jobs to be performed on Monday and Wednesday.

Table 7.4: Example of Relation Between Task, User and Jobs Example: Task 10, related to user 9, consisting of two jobs

Monday Tuesday Wednesday Thursday Friday

Job 4 Job 5

To generate these parenting tasks, jobs are set as instances of tasks, based on the shares of frequent jobs in Table 7.3. Therefore, the only input in generating the test instances is the number of jobs. The other parameters are either calculated by using a distribution from the data or chosen randomly from the data. The basic idea is that all details previously related to a job, now belong to the overall task and the data is connected in the following way:

Task = TaskID, JobIDs, UserID, DT, P, ST, LST, !(), D, SR, EU

TaskID=ID,JobID=JobID,UserID=UserID,Driving Time=DT,Pattern=P,Starting Time=ST,Latest Starting Time=LST,Absolute Latest Starting Time=!(),Duration=D,Skill Requirement=SR,Employee-User score=EU,

An elaboration of how the parameters are created and connected to a task follows.

Driving Times

Each task has a specific user, and every user has a home address given in coordinates. These coordinates are used to calculate driving times in minutes between all users, and thereby tasks.

If two tasks belong to the same user, such as showering and distribution of medicine, these can be performed consecutively with a driving time of zero between the two. Driving Time between two tasks may be asymmetric due to, for instance, one-way roads, as the calculations respect feasible driving patterns.

Patterns

To ensure that the jobs within a task are evenly spread over the course of five days, according to the associated frequency, patterns are created. A pattern gives a list of days when the jobs can be performed. There are many possible patterns, for instance, there are ten ways of choosing two days within a five day period for a task with frequency two. To reduce the complexity of the problem and ensure a gap of one day between each job, if attainable, the number of patterns is limited to 15. A description of possible patterns related to frequencies is found in Table 7.5, and a more detailed illustration is found in Appendix B.1.

Table 7.5: Possible Patterns

Every task is given a Starting Time, a Latest Starting Time, and Duration by randomly selecting a job’s associated starting time, latest starting time, and duration from the data. Starting Time and Latest Starting Time are given in minutes after midnight, and Duration is given in minutes.

The difference between the Starting Time and the Latest Starting Time is referred to as a Time Window, given by:

Time Window = Latest Starting Time - Starting Time + Duration

Starting after the Latest Starting Time is allowed at an extra cost related to overtime, however only until the Absolute Latest Starting Time or one hour after the shift ends at 17:00. Absolute Latest Starting Times are given in minutes after midnight, and given by the following:

Absolute Latest Starting Time = minn

Latest Starting Time + 60, 1080o

Maximum waiting time is set to two hours between two jobs and the maximum driving time between two tasks is set to 15 minutes.

A summary of the relations between the different points of time concerning a task is found in Figure 7.3.

Figure 7.3: Relations Between Time Parameters Skill Requirement

All tasks are given a level of skill requirement needed to perform the task. The skill requirements are based on the distribution of skill requirements in the data given in Table 7.6.

Table 7.6: Distribution of Tasks across Skill Requirements

Level 1 2 3 4

Distribution of

Tasks 26.0% 24.0% 24.0% 26.0%

7.3.2 Generating Parameters Related to Employees

The number of employees per day is determined based on the relationship between the number of jobs and the number of employees in the data set provided, as shown in Table7.1. The initial job-employee ratio of 7.5 is rounded up to 8.

Employees are given a skill level related to their education and experience, based on the dis-tribution from the data, given in Table 7.7. To ensure that the skill level of the employees is sufficient to serve the skill requirements of tasks on a certain day, at least one employee with sufficient skill level must work each day.

Table 7.7: Distribution of Employees Across Skill Levels

Level 1 2 3 4

Distribution of

Employees 25.0% 25.0% 25.0% 25.0%

Compliance of user convenience is done by generating a fictive Employee-User score. The Employee-Job preference defined in the mathematical model in Chapter 5 now belongs to a user instead of a job, but the result is the same. The scale of convenience ranges from 0 to 1.

The combination of user and employee is chosen randomly in the creation of the test instance by giving all tasks one preferred employee with a score of 1. Lastly, it is ensured that all employees have approximately the same number of tasks they are preferred for.