FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:     | 1 |   ...   | 15 | 16 || 18 | 19 |   ...   | 20 |

«Automated Tourist Decision Support Wouter Souffriau Dissertation presented in partial fulfillment of the requirements for the degree of Doctor in ...»

-- [ Page 17 ] --

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 first–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 different 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 final 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.

7.3.2 Preprocessing

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 off–line operation only needs to be executed partially when the network is updated.


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 first 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 finds the optimal result in a second of execution time, both CPLEX scenarios find all optimal solutions. For Cmax equal to 40 000, both CPLEX scenarios reach the optimum for all ten instances, while GRASP finds two, but the CPLEX scenarios require substantial computational effort. For Cmax equal to 60 000, CPLEX manages to find 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 difference gap of the GRASP result with Cmax illustrates the quality of the proposed approach. Globally, GRASP achieves solutions with lengths that differ 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 difference 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 effort. 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.


–  –  –

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 different 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 first 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 defining the route.

Direction signposts guide the user through the network.

7.5 Conclusions

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 finding 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 difference of only 0.85% with the requested length, an insignificant 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 offering personalised cycle routes based on user preferences and an SMS service providing cyclists “in the field” 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 refined. The cyclist will be able to seek or avoid dirt roads and steep inclines. Future work will also include planning for multiple days.

Chapter 8


The objective of this work was to develop efficient 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 five main flemish historic cities. Second, an on–line cycle route planner for the province of East–Flanders offers personalised cycle routes based on user preferences, while an SMS service provides cyclists “in the field” 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 field 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 finding 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 insignificant 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.

Pages:     | 1 |   ...   | 15 | 16 || 18 | 19 |   ...   | 20 |

Similar works:

«Abschnitt 9 Technisches Schreiben Schreiben ist schwierig.... ] Es ist schwierig, weil es eine Reihe von Aktivitaten verlangt, die gemeinhin als Denken bezeichnet werden. Ernst Jacobi In diesem Anhang geht es um das Schreiben technischer Dokumente, seien es nun SoftwareEntwurfsdokumente, Benutzerhandbucher, wissenschaftliche Artikel oder sonst etwas derartiges.Fertigkeiten im technischen Schreiben werden oftmals nicht als ein wesentliches Quali kationsmerkmal von Softwaretechnikern...»

«The Wells Fargo Rewards® Program Terms and Conditions Effective: September 2013 Section 1: Your Contract With Us Section 2: Your Rewards Program Account, Rewards Currency And Earning Mechanisms Section 3: Options For Redeeming Rewards Section 4: Transfer And Gifting Of Rewards Currency Section 5: About Rewards Redemption Section 6: Dispute Resolution Program: Arbitration Provision Section 1: Your Contract With Us “You”, “Your”, or “Customer” means, as applicable, each person who is...»

«THL Schutzjacke und Schutzhose Protective jacket and Protective trousers Verwenderinformation User information Verwenderinformation D User information GB Rosenbauer THL, Schutzjacke / Schutzhose THL Schutzjacke / Schutzhose zur technischen Hilfeleistung Die Schutzjacke und Schutzhose sind eine Feuerwehrschutzbekleidung ▪ gemäß EN 469:2005+A1:2006 Die Feuerwehtschutzjacke THL muss immer gemeinsam mit der ▪ Feuerwehrschutzhose THL oder einer anderen Rosenbauer Schutzhose gemäß EN...»

«Umberto Lucia nasce il 25 aprile 1966 ad Alessandria. Svolge i suoi studi elementari alla scuola elementare “Galileo Galilei”, quelli medi alla scuola media “Alessandro Manzoni” e superiori in Alessandria conseguendo la maturità scientifica presso il Liceo Scientifico “Galileo Galilei”, dove è supplente di matematica e di fisica durante gli studi universitari. Nel 1991 si laurea in Fisica, indirizzo fisica delle particelle elementari, presso l’Università degli Studi di Torino...»

«CCT/03-10 Mechanical stability of Pt/Pd thermocouples F.Edler1, H. Lehmann2 Physikalisch Technische Bundesanstalt, Abbestr. 2-12, Berlin, Germany electrotherm GmbH, Geraberg, Germany Numerous investigations of Pt/Pd thermocouples are mainly addressed to the characterisation of their thermoelectric properties. Burns, Ripple and Battuello [1] published data for the construction of the reference function for Pt/Pd thermocouples, Hill [2] and Bentley [3] presented advanced investigations concerning...»

«ISLAMIC TASAWWUF WITH BRIEF DISCUSSIONS IN THE LIGHT OF QUR‟AAN AND MODERN SCIENCE          Nay! This is a Glorious Qur'aan, (Inscribed) in Al-Lauh Al-Mahfooz (The Preserved Tablet)! (85:21-022) DR ISLAM NABI JAFRI CPhys, MInstP, PhD COPY RIGHTS © Dr Islam Nabi Jafri 2010 All rights reserved. No part of this book may be reproduced or...»

«Approaching Human Performance The Functionality Driven Awiwi Robot Hand Markus Grebenstein Diss. ETH No 20471 APPROACHING HUMAN PERFORMANCE: THE FUNCTIONALITY DRIVEN AWIWI ROBOT HAND A dissertation submitted to ETH ZURICH for the degree of Doctor of Sciences presented by MARKUS GREBENSTEIN Dipl. Ing., Technische Universität München born on September 27nd 1969 citizen of Germany accepted on the recommendation of Prof. Dr. Roland Siegwart, supervisor Prof. Dr. Gerd Hirzinger, co-supervisor...»

«Biosynthesis of Vitamin B2 (Riboflavin). Studies on the Reaction Mechanism of Riboflavin Synthase. Dissertation Zur Erlangung des Doktorgrades des Fachbereiches Chemie der Universität Hamburg Institut für Lebensmittelchemie Vorgelegt von Ryuryun Kim Hamburg, im März 2012 Die vorliegende Arbeit wurde in der Zeit von January 2008 bis September 2011 unter der wissenschaftlichen Betreuung von Prof. Dr. Markus Fischer und Dr. Boris Illarionov an Institut für Lebensmittelchemie der Universität...»

«Zur Einrichtung von Nationalparks in Syrien – Exemplarisch untersucht am Tal des Al Asi/Orontes vorgelegt von Dip.–Ing. Sabah AlBrahim aus Hama, Syrien von der Fakultät VI Planen Bauen Umweltder Technischen Universität Berlin zur Erlangung des akademischen Grades Doktorin der Ingenieurwissenschaften -Dr.Ing.genehmigte Dissertation Promotionsausschuss: Vorsitzende: Prof. Dr. Cordula Loidl-Reisch Gutachter: Prof. Dr. Johannes Küchler Gutachterin: Prof. Dr. Sonja Nebel Gutachter: Prof. Dr....»

«Benutzerhandbuch MFC-8440 MFC-8840D Das Gerät ist mit einem N-kodierten TAE-Anschlusskabel versehen. Das Gerät arbeitet auch an nachgeschalteten und zugelassenen Telekom-Endgeräten. Wichtiger Hinweis Brother macht darauf aufmerksam, dass dieses Gerät nur in dem Land, für das es geprüft wurde, richtig arbeitet. Brother übernimmt keine Garantie für den Anschluss des Gerätes an öffentliche Telefonnetze in anderen Ländern, für die das Gerät nicht zugelassen wurde. Zu diesem Handbuch...»

«DIPLOMARBEIT Titel der Diplomarbeit Die zentrale Rolle des Staates in der nachholenden Industrialisierung. Der Staat als Koordinator und Förderer langfristiger, ökonomischer Entwicklung in Taiwan und Südkorea Verfasserin Elisabeth Reither angestrebter akademischer Grad Magistra (Mag.) Wien, 2010 Studienkennzahl lt. Studienblatt: A 057 390 Studienrichtung lt. Zulassungsbescheid: Internationale Entwicklung Betreuerin: Dr. Silvia Michal-Misak Danke. Vielen Dank an Dr. Silvia Michal-Misak für...»

«Hair Loss & Replacement FOR DUMmIES ‰ Hair Loss & Replacement FOR DUMmIES ‰ by William R. Rassman, M.D., Jae P. Pak, M.D., Eric Schweiger, M.D., and Robert M. Bernstein, M.D. Hair Loss & Replacement For Dummies® Published by Wiley Publishing, Inc. 111 River St. Hoboken, NJ 07030-5774 www.wiley.com Copyright © 2009 by Wiley Publishing, Inc., Indianapolis, Indiana Published by Wiley Publishing, Inc., Indianapolis, Indiana Published simultaneously in Canada No part of this publication may be...»

<<  HOME   |    CONTACTS
2016 www.abstract.xlibx.info - Free e-library - Abstract, dissertation, book

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.