«Automated Tourist Decision Support Wouter Souﬀriau Dissertation presented in partial fulﬁllment of the requirements for the degree of Doctor in ...»
Between every two arcs d and f of the route the insertion of every possible arc e is checked. An insertion is added to the neighbourhood if
• the cost of the new route is below Cmax,
• its corresponding path does not contain an arc more than once, and
• each vertex, except the start vertex, is not visited more than once.
7.2.3 GRASP Exploring the neighbourhood iteratively in a best–improving or ﬁrst–improving fashion leads to local optima, which are likely to be suboptimal. In order to overcome this problem, a metaheuristic is used to better explore the search space and to escape from the local optima. In general, the GRASP metaheuristic performs a number of independent iterations each consisting of a constructive procedure, which is described in Section 3.5. The behaviour of this procedure is governed by the so–called greediness parameter. The diﬀerent iterations are independent and return the best solution found as the result. Until the stopping criterium is met, a number of construct iterations are performed. The algorithm keeps track of the best solution found so far and returns it as the ﬁnal result when the stopping 116 CYCLE ROUTE PLANNING criterion is met. Algorithm listing 12 overviews this approach.
7.3 Computational Experiments The solution approach is tested by means of real–life test data. Its results are compared with the outcomes of a commercial solver CPLEX 11.0 applied on formulation (7.1)–(7.7). First, Section 7.3.1 describes the generation of the test set. Next, Section 7.3.2 describes a preprocessing step of the network data in order to reduce on–line calculation times. Finally, Section 7.3.3 compares the GRASP approach to the CPLEX implementation.
7.3.1 Test Set
A number of AOP test instances are generated from the cycle network of the province of East Flanders. The data contains 38 parking lots where tourists frequently park their car and start a trip. A random sample of 10 parking lots serves as the set of starting points for the test instances. From each of the starting points, routes are generated for Cmax equal to 20, 40, 60, 80 and 100 kilometres, resulting in a total of 50 test instances.
In order to reduce response times, the network is preprocessed by calculating all pairwise point–to–point shortest paths within a certain range by the Floyd– Warshall algorithm [Cormen et al., 1990]. The resulting paths and their associated cost are stored in the system’s database. In the East Flanders case, all the shortest paths between nodes that are located within a range of 20 kilometres from each other, are calculated. That results in a collection of 29 265 paths. This oﬀ–line operation only needs to be executed partially when the network is updated.
COMPUTATIONAL EXPERIMENTS 117
7.3.3 Computational Results
This section presents the results of the proposed GRASP approach, implemented in JAVA 1.6, compared to those obtained by an implementation of the AOP model (7.1)–(7.7) using CPLEX 11.0. All experiments are performed on an Intel Xeon
2.5GHz. The stopping criterion of the GRASP algorithm is one second of calculation time. The CPLEX experiments are performed for two scenarios, (a) starting from scratch and (b) trying to improve the GRASP solution. Both scenarios can each take one hour per test instance.
Tables 7.1 and 7.
2 present the results of the experiments. The ﬁrst two columns characterise the test instance by the id of the starting point and by Cmax. Column three presents the score found by the GRASP metaheuristic after one second. The column of the solution CPLEX (1) presents the score determined by the CPLEX approach, starting from scratch, and the execution time in seconds. Finally, column CPLEX (2) reports the score and execution times of the CPLEX approach starting from the initial GRASP solution. If the execution time is below one hour (3 600s), the instance is solved to optimality. Optimal scores are printed in bold.
The instance with start id 30 and Cmax 20 000 has no feasible solution and is discarded from result discussions. For all but one instance with Cmax equal to 20 000, GRASP ﬁnds the optimal result in a second of execution time, both CPLEX scenarios ﬁnd all optimal solutions. For Cmax equal to 40 000, both CPLEX scenarios reach the optimum for all ten instances, while GRASP ﬁnds two, but the CPLEX scenarios require substantial computational eﬀort. For Cmax equal to 60 000, CPLEX manages to ﬁnd the optimum in only four cases, due to the increasing complexity of the instances. For higher Cmax values, CPLEX fails to prove optimality within one hour of calculation time.
Table 7.3 summarises the results of the experiment.
First, the average procentual diﬀerence gap of the GRASP result with Cmax illustrates the quality of the proposed approach. Globally, GRASP achieves solutions with lengths that diﬀer only 0.85% from the target lengths. Apparently, the optimal CPLEX results indicate that the requested length cannot be exactly met for many instances. For both CPLEX scenarios, this gap is presented, along with the diﬀerence with the GRASP gap and the average execution times, for each Cmax value and in total. Small and medium instances, with Cmax up to 60 000, CPLEX (1) performs slightly better than GRASP with respect to solution quality, but requires substantial computational eﬀort. For the larger instances, the GRASP approach continues to perform in an excellent way, within one second, while the CPLEX(1) approach performs weaker. Overall, starting from a GRASP solution, CPLEX only achieves a 0.22% improvement and GRASP performs better than CPLEX starting from scratch.
118 CYCLE ROUTE PLANNING
The proposed approach is implemented in East Flanders in a web–based cycle route planner and in a short message service (SMS) system.
The web–based cycle route planner1 allows composing routes “manually” by selecting the starting point and adding a sequence of nodes, in between which the shortest paths are calculated. When the user is happy with the route, it can be printed, downloaded to a GPS device, and even shared with friends and family through social networking sites. Since July 2009, this planner is enhanced with a “suggest” function. A route is tailored from a starting point and a preferred length, removing the need for manual planning. This function uses the GRASP algorithm, with Cmax equal to the preferred length, increased by one kilometre. The score of each arc is set to its length, and is furthermore multiplied by (1 + rnd), with rnd being a random number between 0 and 1 drawn from a uniform distribution. This random factor provides the user with a slightly diﬀerent route when the suggest function is called upon multiple times with the same input. The stopping criterion is set to one second to achieve real–time response. In a period of three months, the suggest function has been used more than 15 000 times.
The second application is a system that delivers cycle routes by SMS. As mentioned above, 38 parking lots are located throughout the province. Each of these has a signboard that provides a map of the cycle network. This signboard also provides the documentation of the SMS service. The cyclist sends an SMS containing the signboard id, the preferred length of the route and an optional direction. The SMS server decodes the signboard id to a location and performs the GRASP algorithm.
The optional direction can be n, e, s or w, corresponding the ﬁrst character of the four wind directions. When a direction is submitted, the algorithm will only select arcs that are inside a bounding box. The outcome is a route in the preferred direction. The cyclist is informed about the solution only a few seconds later by means of an SMS providing a sequence of node numbers deﬁning the route.
Direction signposts guide the user through the network.
This chapter introduces the AOP in order to enable scenic route planning in tourist applications. The AOP model is converted to a special case of the MCTOPTW. In constrast to previous applications, the structure of the underlying road network is taken into account. Therefore, a new solution representation and insertion neighbourhood structure are presented.
1 http://www.tov.be/routeplanner.aspx, accessed December 10, 2009 CONCLUSIONS 121 Traditional route planners only apply shortest time or distance optimisation objectives. For recreational cyclists in East Flanders, a novel path ﬁnding problem has been developed. Its objective is to meet a target distance. The problem is a combinatorial optimisation problem and is solved to near optimality by a GRASP metaheuristic. In only one second, GRASP achieves a diﬀerence of only 0.85% with the requested length, an insigniﬁcant gap for any tourist cycle route application. A commercial exact solver managed to improve the GRASP solutions only by 0.22% on average, after one hour of calculation time. The approach was implemented in two applications: an on–line cycle route planning application oﬀering personalised cycle routes based on user preferences and an SMS service providing cyclists “in the ﬁeld” with routes on demand.
It appears that cycle trip planning is a really new and rich application area for O.R. modelling and optimisation. The applications in East Flanders and the response of the cyclists clearly show a growing need for O.R. support.
For these applications, the score of an arc is correlated to its length. These AOP instances are probably easier to solve than a setting in which the arc’s score and length are unrelated, as is the case for traditional OPs. Next to an insertion operator that increases the score of a solution, OP solution methods typically use a cost reduction operator, e.g. 2-OPT [Lin, 1965]. Future work is required to adapt these approaches to AOPs. The design model can then be reﬁned. The cyclist will be able to seek or avoid dirt roads and steep inclines. Future work will also include planning for multiple days.
The objective of this work was to develop eﬃcient Operational Research techniques that enable a wide range of trip planning functionalities to tourist decision support systems. First, the basic Orienteering Problem model is used, in combination with information retrieval techniques, to automatically propose tailored city walks, achieving personal interest estimation combined with integration of selection and routing. Also, mandatory POIs can be easily incorporated. Dynamic recalculation is achieved by using fast solution techniques, which present solutions in nearly real–time.
The basic model is iteratively extended with multiple tours, time windows, multiple constraints, multiple time windows and arcs. These extensions enable the planning of multiple days, taking opening hours of POIs into account, budget limitations, max–n types and the planning of scenic routes. Furthermore, this work explains how the model can be used to state mandatory POI types and how to tackle weather dependency.
The developed approaches have been incorporated into two web–based tourist decision support systems. First, the City Trip Planner enables planning multi–day city trips, taking opening hours into account, for the ﬁve main ﬂemish historic cities. Second, an on–line cycle route planner for the province of East–Flanders oﬀers personalised cycle routes based on user preferences, while an SMS service provides cyclists “in the ﬁeld” with routes on demand. This shows the applicability of the developed O.R. techniques. The presented techniques are state–of–the–art and ready to be incorporated into real–life tourist decision support applications enabling advanced planning functionalities.
The planning objective throughout this thesis was the maximisation of the estimated tourist interest by visiting relevant POIs. The author is aware of the subjectiveness
of this objective, and wants to point out that it is irrealistic and even utopic to attempt calculating “the perfect tourist route”. Psychologists could work for days to manually determine this perfect route or optimal selection and would not reach a consensus on what is optimal in the context of tourism. Research on POI interest estimation techniques is clearly a task in the ﬁeld of recommendation systems, as described in Section 1.1.2, and it results in a score value for each POI. The O.R. techniques presented in this work focus on the integration of selecting POIs and ﬁnding a route between them, subject to a set of constraints. Feedback by users states that the selected POIs match their interest and that unknown interesting POIs the user would normally neglect, are also selected.
In order to tackle the tourist trip design problems, a number of metaheuristic search procedures have been implemented. These techniques achieve near–optimal solution quality within limited calculation times. This small quality gap with optimality is insigniﬁcant for the application, considering the inherent shortcomings of quantifying a tourist’s personal interest in a location.
Local search based methods have proven to be excellent solution techniques.
Compared to constructive algorithms, the incumbent solution in a local search approach achieves an acceptable quality relatively fast. Therefore, when applied in a tourist decision support application, an initial plan can be suggested in real–time.