5.2 The ABP Problem Compared with the VRPTWSV
5.2.2 The Objectives
There are two special issues to take into consideration when comparing the solutions found by the methods in the ABP programme and the solutions found by the methods in this project.
1. The objective function in the VRPTWSV is used for comparison, be-cause the objective function in ABP is not known exactly. This may cause a poor comparison, and therefore to make the comparison as good as possible the objective function in ABP is approximated to the objective function in the VRPTWSV
2. There may arise a problem, if the good solutions with respect to the objective function in the VRPTWSV is situated in the solution space S1\ S2. This will only be a problem ifS1⊂ S2.
There are given examples of what can happen if the objective function in ABP is different from the objective function in the VRPTWSV, and exam-ples of how the difference between S1 and S2 can give a poor comparison.
At the end of this subsection it is explained how the objective function in the ABP programme is approximated to the objective function in the VRPTWSV.
It it easier to compare the two objective functions, if we assume the two solution spaces S1 and S2 to be equal. In figure 5.2 it is illustrated how there could be two objective functions; one for the ABP problem and one for VRPTWSV.
The two optimal solutions are x∗1 and x∗2 with the values c∗1 and c∗2. The two solutions have to be compared. Because only the formula for objective function in VRPTWSV is known it is used for comparison. The solution value forx∗2 isc2, which is worse thanc∗1 in the example in figure 5.2.
CHAPTER 5. THE ABP PROGRAMME
Solutions ABP
VRPTWSV Objective value
PSfrag replacements
x∗2 x∗1 c2
c∗2 c∗1
Figure 5.2: Two optimal solutions compared with the objective function in VRPTWSV, when the solution spaces are equal.
The optimal solution value c2 will not necessarily always be worse thanc∗1, it could also be just as good, but never better.
If the solutions ˆx1 and ˆx2 with the values ˆc1 and ˆc2 are found but not necessarily are the optimal solutions, one can not be sure that c2 ≥ ˆc1. Figure 5.3 depicts an example of this.
Solutions ABP
VRPTWSV Objective value
PSfrag replacements
ˆ
x2 xˆ1 c2
ˆ c2 ˆ c1
Figure 5.3: Two solutions compared with the objective function in VRPTWSV, when the solution spaces are equal.
It shall be kept in mind, that when performing the method in ABP for finding the solution ˆx2 it is not known that the comparative objective value is c2 and not ˆc2 and the method might therefore go to the ”wrong” places searching for a good solution ˆx2.
Now follows an example of what can happen if S1\ S2 6= ∅ and the good solutions are situated inS1\S2. Then the method in ABP has worse changes of searching the right places for good c2 values. An example of this is in figure 5.4, where the horizontal axis illustrates the solution spaceS1. Figure 5.4 shows how it could be not possible to find a solution ˆx2with good values for the objective function in VRPTWSV.
CHAPTER 5. THE ABP PROGRAMME
Solutions ABP
VRPTWSV Objective value
PSfrag replacements
ˆ
x2 xˆ1
c2
ˆ c2 ˆ c1
Figure 5.4: Two solutions compared with the objective function in VRPTWSV, when the solution spaces are not equal
In the following the objective function in the ABP problem is described. It is explained how it is approximated to the objective function in VRPTWSW if it is necessary for the comparison.
Demand and Priority for Visits Each visit has a type of demand, which for instance could be personal hygiene or cleaning. The priority of a visit is determined by the type of demand e.g. personal hygiene could be more important than cleaning. The objective is to schedule the most important visit, when not all visits can be scheduled. The VRPTWSV does not distinguish between different types of visits, and therefore all visits are set to have the same demand, which is practical help, when performing the comparison.
Regular Caretakers at Citizens Each citizen has three regular caretak-ers. The regular caretakers are weighted equal or higher than the non regular caretakers to be the ones performing the visits at each citizen.
The weights can be set as parameters, and they are set at different levels in the comparison.
Minimize Caretakers’ Travel Time Each caretaker should travel as short time a possible. This objective is the same in the VRPTWSV and will not influence the comparison.
Caretakers’ Qualifications and Fitness of Visits’ Demands The care-takers can be categorized according to different qualifications. The categories are for instance helpers, assistants and nurses. Each cat-egory has different qualifications in different areas such as cleaning, normal personal hygiene, complex personal hygiene etc. A helper is for instance preferred for practical help such as cleaning. An objective is that the qualifications fit the demands as well as possible. There are no demands or qualifications in the VRPTWSV. All demands are
CHAPTER 5. THE ABP PROGRAMME
set to practical help in the comparison. All caretakers are defined as helpers to avoid that some caretakers are preferable to others in the comparison.
Caretakers Cost A cost is defined for letting a caretaker start, which is minimized. This cost is set to zero in the comparison.
Caretakers’ Spare Time after last Visit The ABP maximizes the spare time after the last visit for each caretaker. The VRPTWSV does not take that into a account, and therefore the solution methods for the VRPTWSV have an advantage when the comparison is done with the objective function in the VRPTWSV.
The weights in the objective functions are difficult to approximate to each other, and hence different parameter settings are tried. The other difference between the objective functions is the maximization of the spare time after the last visit.