Our computational experiments are summarized in the figures 5.1 through 5.5. Figures 5.1 through 5.3 depict the average total traveled distance by the repairman as a function of the number of immediate requests for Scenarios A, BandC, respectively.
In Appendix B the log files and the actual routes of a single instance of the Scenario B dataset produced by the NN-FCFS and the PART poli-cies are shown. Immediate requests begin to be generated at 8:00 and new customers are generated according to equation 5.1 at rateλ= 1.125 requests/hour until the clock turns 16:00. In this case a total of 30 cus-tomers were generated, 21 of these were advance requests and the remaining
5.3. COMPUTATIONAL RESULTS 71
40 60 80 100 120 140 160 180
0 20 40 60 80 100
Distance (km)
Degree of dynamism (%) PDTRP - E{n_tot} = 20.
First Come First Serve - SQM First Come First Serve PART 9 subregions PART 4 subregions Nearest Neighbor Nearest Neighbor - FCFS
Figure 5.1: Scenario A: The distance traveled as a function of the degree of dynamism in the system.
9 were immediate requests (please note that customer number 22 is an im-mediate customer calling in at 8:00:02 - two seconds after the calling center opens). Using the terminology mentioned above we haventot= 30,nadv= 21 andnimm= 9. The degree of dynamism then isdod= nnimmtot = 0.3. This means that 30 % of the customers are immediate request customers. The log files tell us that the NN-FCFS policy produces the shortest route with a length of 88.91 km, whereas the PART policy produces a slightly longer route with a distance of 89.61 km. In Figures B.1 and B.2 in Appendix B the actual routes produced by the two policies are shown. The routes are seen to differ quite a lot. Both routes start by serving Customer 4.
Thereafter, the NN-FCFS policy chooses to go to the nearest customer, in this caseCustomer 18sinceCustomer 25has not yet placed its request for service. The PART policy goes toCustomer 11, since the first customer on the route was located in the upper-left region and the repairman therefore
40 60 80 100 120 140 160 180 200 220 240
0 20 40 60 80 100
Distance (km)
Degree of dynamism (%) PDTRP - E{n_tot} = 30.
First Come First Serve - SQM First Come First Serve PART 9 subregions PART 4 subregions Nearest Neighbor Nearest Neighbor - FCFS
Figure 5.2: Scenario B: The distance traveled as a function of the degree of dynamism in the system.
has to serve this subregion, until no more requests are waiting in line to be served. The PART policy then serves the lower-left, the lower-right, the upper-right and then again the upper-left subregions and this goes on until no more requests are waiting to be served.
Figure 5.4 shows the average number of minutes the repairman is busy serv-ing or travelserv-ing to customers as a function of the degree of dynamism. The busy time is seen to increase considerably for increasing levels of dynamism.
In Figure 5.5 the distance is shown as the function of the degree of dy-namism for four different values of the number of subregions. It can be seen that the best performance is obtained with 4 subregions for this sce-nario. Generally, one should expect to see good performance with respect to the distance driven when using a small number of subregions, since the few subregions mean that good routes can be formed within each subregion.
5.3. COMPUTATIONAL RESULTS 73
100 150 200 250 300
0 20 40 60 80 100
Distance (km)
Degree of dynamism (%) PDTRP - E{n_tot} = 40.
First Come First Serve - SQM First Come First Serve PART 9 subregions PART 4 subregions Nearest Neighbor Nearest Neighbor - FCFS
Figure 5.3: Scenario C: The distance traveled as a function of the degree of dynamism in the system.
Naturally, such good performance with respect to the distance is obtained at the expense of experiencing poor performance with respect to the wait-ing time of the customers. This could be explained, as the increase in the distance is due to the fact that the PART policy becomes the FCFS policy as nsubreg → ∞, which could also be formulated as the service offered to the customers increases asnsubreg → ∞.
The average waiting time of the immediate requests are shown as a function of the degree of dynamism in Figure 5.6 for Scenario C. Except for the FCFS and the FCFS-SQM policies the average waiting times are seen to be rather invariant to the level of dynamism. For the FCFS and the FCFS-SQM policies the average waiting time is seen to be considerably higher for weakly dynamic instances than for strongly dynamic instances. This may at first seem a bit surprising but should be explained as follows: The waiting time based policies (the FCFS and the FCFS-SQM) will start by
100 150 200 250 300 350 400 450
0 20 40 60 80 100
Busy time (min)
Degree of dynamism (%) PDTRP - Busy time for Nearest Neighbor.
E{n_tot} = 20 E{n_tot} = 30 E{n_tot} = 40
Figure 5.4: The busy time of the repairman for scenariosA, Band Cas a function of the degree of dynamism in the system.
serving the advance request customers and let the (few) immediate request wait until the advance requests have been served. This means that the average waiting time of the immediate requests will be relatively high for instances with few immediate and many advance requests.
5.3.1 Effective Degree of Dynamism
In addition to the three scenarios we also considered a special instance of Scenario C. We will refer to this scenario as Scenario C*. As for the other scenarios we generated 50 different instances. However, instead of generating the instance using the basicdodmeasure we used the effective degree of the dynamism measure, edod, as defined in section 4.1.2. Even though the range of theedodmeasure is the same as the range of thedod
5.3. COMPUTATIONAL RESULTS 75
200 250 300 350 400 450
0 20 40 60 80 100
Distance (km)
Degree of dynamism (%) PDTRP - E{n_tot} = 40.
PART 9 subregions PART 4 subregions PART 16 subregions PART 25 subregions
Figure 5.5: Scenario C: The distance as a function of the degree of dy-namism for the different versions of the PART policy.
measure it is not realistic to generate instances with edod= 100%, since this would mean that all requests would have to be received at the very end of the planning horizon. Therefore we chose to generate 50 instances, each withedod={0,3,6, ...,57,60}%1. In Figure 5.7 the distance is shown as a function of the effective degree of the dynamism. The behavior of the distance is seen to be very similar to the behavior of Figure 5.3. However, for instances withedod >50 % the distance seems to decrease for increasing values ofedod. We see no explanation to this rather unexpected behavior.
Judging from Figure 5.7, theedodmeasure does not seem to offer anything special not already captured by the more simpledodmeasure.
1During the tests we tried to generate 50 instances each with edod = {0,4,8, ...,76,80}%. However, after more than 3000 minutes of computation time on an HP/9000-785 computer only instances withedod≤68 % were complete and only 7 instances withedod= 72 and none withedod >76 % were generated.
0 20 40 60 80 100 120 140 160 180
0 20 40 60 80 100
Avg. waiting time (min)
Degree of dynamism (%) PDTRP - E{n_tot} = 40.
First Come First Serve - SQM First Come First Serve PART 9 subregions PART 4 subregions Nearest Neighbor Nearest Neighbor - FCFS
Figure 5.6: Scenario C: The average waiting time of the immediate re-quests as a function of the degree of the dynamism.
5.3.2 General Observations
For all three scenarios one also notes that as the level of dynamism be-comes stronger, the behavior of NN increasingly resembles that of FCFS.
This is because the presence of larger numbers of immediate request cus-tomers spreads their scheduling over time, implicitly decreasing the set of neighbors each customer has at any given point in time. At the higher end of dynamism the customer currently being serviced may only have one neighbor - the next immediate request customer. Hence, as the level of dynamism increases, we observe an expected transition from a geograph-ical to a temporal emphasis. Furthermore, the figures illustrate that the average total distances for the FCFS and the FCFS-SQM policies were al-most independent of the degree of dynamism. The difference was larger inScenario A than inBandCsince the repairman had slightly more idle