«Automated Tourist Decision Support Wouter Souﬀriau Dissertation presented in partial fulﬁllment of the requirements for the degree of Doctor in ...»
The GRILS heuristic is extended in order to deal with the distance constraint in a similar way like the other constraints. One distance constraint is deﬁned per path. First, the importance of a distance constraint is deﬁned as the sum of scores related to uninstantiated visit variables multiplied by their corresponding distance consumption (cheapest insertion) divided by the remaining distance budget. Next, the denominator of equation (5.11) is extended with the product of the importance of the distance constraint and the distance consumption.
The datasets of Gueguen  are used, which extend data sets deﬁned for the VRPTW [Solomon, 1987], for instances with 50 and 100 locations; distance constraints (L) of 50, 100 and 150; and m up to 10. Table 5.3 compares the performance of GRILS to that of the ILS approach of Garcia et al. . The ﬁrst column indicates n, the number of locations, the second column distance constraint L. The second column gives the name of the test set over which the results are aggregated. The third column presents the results of Garcia et al. , while the next three columns present the best, average and worst result of the GRILS approach, out of 10 runs. All solution qualities are presented as the procentual gap with the optimal results of Boussier et al.  and are the average of m = 1 to m = 10. GRILS outperforms ILS, even with the worst results of 10 runs. Only the test instances with n = 50 and L = 50 seem to perform worse. The last two columns present the execution times of Garcia et al.  and those of the GRILS approach, which are the sum of 10 independent runs. It can be concluded that the worst result of GRILS outperforms ILS using less computational eﬀort, except for n = L = 50.
Note that Garcia et al.  truncated the Euclidean distance between two locations to one decimal, which is standard for Solomon based test instances. If GRILS is run with the same precision, some test instances lead to better results than the optimal one of Boussier et al. , who do not appear to apply any
COMPUTATIONAL RESULTS 89
rounding. When GRILS is run with a precision of rounding to 3 decimals (similar to no rounding but necessary to prevent ﬂoating point arithmetic errors), no better solutions are found than the “optimal” ones of Boussier et al. . This rounding is stricter than truncating to 1 decimal, as distances are always at least as long.
Finally, the results show that with the test instances of Boussier et al. , the capacity constraint is never binding. If this constraint is removed, the same results can be obtained for all test problems. Thus, although the results for these SVRPTW instances are promising, another set of test problems is required to test the behaviour of the heuristic with multiple constraints.
Garcia et al.  designed MCTOPTW test problems, based on the available test sets for the TOPTW. These test sets use one and two extra constraints, for m = 1 and m = 2. Table 5.4 compares the GRILS approach to the ILS approach of Garcia et al. . The ﬁrst two columns state the number of paths m and the number of extra constraints Z. The third column states the test set on which the results presented were averaged. The next four columns respectively present the results of ILS and the best, average and worst results of 10 GRILS runs as the gap with the best solution known, as described in [Garcia et al., 2010]. The last two columns present the execution times of both approaches. On average, the best GRILS run outperforms ILS, however, using more computational eﬀort. On the Cordeau–based instances, GRILS achieves a better results within the same computational time.
As the test sets of Garcia et al.  are limited to two routes and two extra constraints, new test sets are deﬁned to evaluate the proposed approach, reﬀered
90 MULTIPLE CONSTRAINTS
to as “MCTOPTW Set 2”. Solomon’s *100 and Cordeau’s pr01 to pr09 instances, except pr06 for which no optimal solution is known, are extended with 11 extra constraints: one money budget constraint and 10 max–n type constraints. m ranges from 1 to 4. For the money constraint, each location is given a random entrance fee between 0 and 99. For each max–n type constraint, each location i has a 0.2 probability of ezi = 1, 0 otherwise. Ez is determined for each constraint, starting from a known (T)OPTW solution: for m = 1 the optimal solution of Righini and Salani  is used, for m 1 the solution of Vansteenwegen et al. . Ez is the sum of all ezi, with i belonging to this solution. Designing the new test sets in this manner, this particular high quality (T)OPTW solution is also a feasible high quality solution of the new MC(T)OPTW problem. Therefore, a very good solution is known and can be compared with.
Table 5.5 presents the results of the GRILS approach on these new test problems.
The ﬁrst column gives the number of paths m, the second column the origin of the test problems. The next three columns present the average gap (with the best known solutions on which the Ez were based) for the best, average and worst results of 10 independent runs. The last columns presents the execution times.
The results are very good: an average run has a score gap of only 3.26%, using 1 second of computational eﬀort. In 27% of the test instances, the initial high quality solution was found, in 9% of the instances, this solution was improved. When m=1, even 70% of the optimal solutions were found.
Tests using a naive feasibility check, as mentioned in 5.3, lead to execution times that are 10 to 20 times higher for MCTOPTW Set 2, which indicates the necessity
COMPUTATIONAL RESULTS 91
for the intelligent neighbourhood consistency algorithm.
5.5.4 Parameter Sensitivity In this section, the inﬂuence of the diﬀerent GRILS parameters is examined.
StartGreed, greedRange, greedDecrease and nrIterations are individually varied over a series of setting. The standard values are 0.89, 0.30, 0.01 and 100, respectively.
Also, a pure GRASP and a pure ILS version of the approach is examined and compared to the hybrid approach. The presented results are obtained using MCTOPTW Set 2.
Table 5.6 to 5.
9 present the inﬂuences of the diﬀerent GRILS parameters individually.
The ﬁrst column presents the parameter value. The next three columns present respectively the best, average and worst score gaps, averaged over MCTOPTW Set
2. The last column states the execution time as the sum of 10 runs, also averaged over MCTOPTW Set 2.
Table 5.6 presents the inﬂuence of the startGreed parameter.
Solution quality worsens as this parameter decreases in value. The table indicates that 0.99 is a better choice than the initial 0.89. This parameter has little or no inﬂuence on the execution time of the algorithm.
Table 5.7 presents the inﬂuence of the greedRange parameter.
Solution quality and execution time increase with this parameter. The table indicates that the 0.2 setting leads to higher quality best solutions in a smaller amount of time compared to 0.3. The average and minimal values, however, are slightly worse. Increasing
92 MULTIPLE CONSTRAINTS
Table 5.8 presents the inﬂuence of the greedDecrease parameter.
Solution quality worsens as this parameter increases. A signiﬁcant amount of computation time can be saved when a small amount of solution quality is sacriﬁced.
Table 5.9 presents the inﬂuence of parameter nrIterations.
It can be seen that an increase of this parameter leads to small improvements of the solution quality, and a signiﬁcant increase in computational eﬀort. In light of the envisioned tourist application, setting this parameter to 100 is a good compromise between quality and calculation time.
Table 5.10 compares the results of GRILS, with the standard parameter setting, to a pure GRASP approach (nrIterations set to 1), and to a pure ILS approach CONCLUSIONS 93
(startGreed = 1, greedRange = 0.01). Pure ILS outperforms pure GRASP, as it achieves better results in a smaller amount of computation time. GRILS achieves better results than the others, however, using signiﬁcant computational eﬀort.
5.6 Conclusions This chapter presents the Multi–Constraint TOPTW. This formulation enables to model entrance fees, max–n type constraints and mandatory POI-types.
A hybrid solution mechanism eﬃciently tackles MCTOPTW instances. The
94 MULTIPLE CONSTRAINTSproposed algorithm quickly propagates variable assignments in order to maintain a neighbourhood of possible insertions, which is explored heuristically using the importance of the diﬀerent constraints as a common denominator. Moreover, this solution method also performs well on the TOPTW and the SVRPTW.
Solomon –based test instances are solved signiﬁcantly better than Cordeau et al. –based instances, which have broader TWs. A “smart” 2-OPT procedure might reduce this gap by detecting a sequence of visits, with a broad common TW, and performing 2-OPT in order to reduce the total travelling time.
Another way to improve the results is to ﬁrst look at the distribution of the TWs and identify “busy” periods, during which lots of visits are possible. For each of these busy periods, an extra constraint could be added. Their high importance will bias the insertions in less busy periods. Also, an integration of bottleneck scheduling approaches [Goldratt, 1984] seems appropriate.
The City Trip Planner
This chapter presents the City Trip Planner, which is a web–based tourist decision support system that proposes city trips tailored to the user’s context and personal interests. The system plans city visits of multiple days, with for each POI multiple time windows which can diﬀer from day–to–day. Moreover, lunch breaks can also be scheduled and the city’s tourist oﬃce can suggest a few POIs to be included in a trip. The City Trip Planner integrates the selection of POIs and the routing between them. To the best of the author’s knowledge, such an integrated system is unique.
In order to take opening hours into account, the MCTOPTW is extended with Multiple Time Windows (MCTOPMTW). Each vertex is extended allowing W TWs for each day, instead of one. Also, the TWs can be diﬀerent on diﬀerent days. An instance of the problem and a solution are presented by Figure 6.1. The multiple TW model overcomes the drawbacks of the (T)OPTW: opening hours of POIs can now be modelled by allowing multiple opening hours per day, and diﬀerent opening hours each day.
The OP with Multiple TWs has recently been given attention by Tricoire et al.
, who solve the Multi-Period OP with Multiple TWs, a generalisation of the TOPTW. In this problem, every vertex can also have more than one time window on a given day and time windows can be diﬀerent on diﬀerent days. They propose a Variable Neighbourhood Search (VNS) algorithm and embed an exact algorithm to deal with a path feasibility sub problem. Extensive experimental results show that they obtain high quality solutions for problems with 100 vertices and 2 paths in around one minute of computation time. The application described by Tricoire et al.  is about facilitating the planning of future working days by ﬁeld workers and sales representatives.
Figure 6.1: The Orienteering Problem with Multiple Time Windows This chapter is organised as follows.
Section 6.1 extends the OP mathematical deﬁnition and explains how extra tourist decision support functionalities can be modelled. In Section 6.2, the diﬀerent components of the City Trip Planner are presented. Section 6.3 illustrates the usage of the City Trip Planner. Statistics and feedback are used to evaluate the system in Section 6.4. Finally, Section 6.5 concludes this chapter.
6.1 Mathematical Formulation
Based on the notation introduced in sections 2.1, 3.1, 4.1 and 5.1, the MCTOPMTW can be formulated as an integer program ( xijd = 1 if, in path d, a visit to vertex i is followed by a visit to vertex j, 0 otherwise; yiwd = 1 if vertex i is visited during TW w in path d, 0 otherwise; sid is the start of the service at vertex i in path d;
Oiwd and Ciwd are the opening and closing times of TW w of vertex i in path d;
M a large constant;):
The objective function (6.1) maximises the total collected score. Constraint (6.2) guarantees that all paths start in vertex 1 and end in vertex n. Constraints (6.3) and (6.4) determine the connectivity and time line of each tour. Constraints (6.5) guarantee that every vertex is visited at most once. Knapsack constraints (6.6) limit the selection by constraining attributes of the vertices. Constraints (6.7) restrict the start of the visit to the time window.
The multiple knapsack constraints (6.6) model of the previous chapter (constraints (5.6)) allowed to express the constraints that each location can be visited at most once, in addition to other more obvious usages. Section 5.2 explained how mandatory POI type constraints can be modelled by simply splitting up certain POIs and adding extra constraints. This same technique will now allow to model multiple TWs: locations with multiple TWs are split up into diﬀerent visits to the same location, with one TW, and adding an extra constraint allowing only one visit to the actual location. Moreover, weather dependency can also be modelled by splitting up a POI: the POI with a TW marking a sunny period has a higher score than the same POI with a TW for a rainy period, and both can be visited at most once. In this case, Si should be replaced by Siwd in Equation 6.1.
98 THE CITY TRIP PLANNER
6.2 System Architecture