FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:     | 1 |   ...   | 16 | 17 || 19 | 20 |

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

-- [ Page 18 ] --

The choice of an adequate metaheuristic framework is important, as a good balance between intensification and diversifications is a key success factor in finding high quality solutions. The Ant Colony Optimisation framework, as described in Chapter 2, is a pure constructive method, and appeared to be less suitable for tackling TTDPs. However, its multistart character provides good diversification, and very good results could be obtained if the result of each ant was to be optimised by a local search procedure. Guided Local Search and Skewed Variable Neighbourhood Search are both local search based methods that perform a single walk. They achieve very good results for the TOP, but they do not sufficiently explore large parts of the solution landscape. A strong diversification mechanism is provided by the GRASP / Path Relinking framework, which combines a constructive heuristic, an intensive local search and a multistart evolutionary mechanism. This combination leads to world–class results. However, the Path Relinking extension comes with a serious computational cost, which is uneconomical in the tourist application as “real–time” response is needed. Therefore, when tackling problems with time windows, the Path Relinking procedure is left out. Moreover, developing a recombination operator is not straightforward when dealing with time windows. The Iterated Local Search framework is a good choice for the TOPTW, as only one neighbourhood, insert, is available. Encapsulating this approach in a multistart procedure, leads to better results for problems with multiple constraints, again at a computational cost.

Fine–tuning parameters still requires a lot of work. Automated parameterisation methods can be used to partly relieve the algorithm developer from this burden.


8.1 Main Contributions While realising the main objective, this work has led to a number of significant

contributions to the field of O.R.:

• Chapter 2 presents two new, multi–level metaheuristic approaches to tackle the OP. O.R. techniques are combined with techniques from the field of information retrieval in order to calculate tailored city tours on–the–fly.

• Chapter 3 presents three new TOP solution approaches: Guided Local Search, Skewed Variable Neighbourhood Search and Path Relinking. The latter achieves very good solutions in a small amount of computational time, or world–class results in a reasonable amount of computation effort, compared to other state–of–the–art approaches.

• Chapter 4 presents, to the best of the author’s knowledge, the first “mobile metaheuristic”, capable of successfully solving OPTW instances up to 50 POIs in an acceptable execution time on a mobile phone with very limited computational power.

• Chapters 2 to 4 combined, provide a survey on the different aspects of the (Team) Orienteering Problem (with Time Windows).

• Chapter 5 presents a generalisation of the OP that focuses on multi–constraint selective vehicle routing problems with time windows. A hybrid solution mechanism efficiently tackles a set of different problem formulations.

• Chapter 6 presents a web–based tourist expert system, named City Trip Planner, that proposes custom–made city trips, tailored to the user’s interests and context.

• Chapter 7 presents a novel path finding problem and solution for recreational cyclists in East Flanders. A web–based planning application provides planning support, and an SMS–based application allows to plan and navigate a cycle route using only a mobile phone instead of an expensive GPS device.

All this work is published, accepted or under review for publication.

8.2 Research Opportunities

–  –  –

Public Transportation integration is identified as one of the most appreciated functionalities of an MTG [Schmidt-Belz et al., 2003, Stroobants, 2006, Beer et al., 2007]. Fomin and Lingas [2002] present the Time Dependent OP (TDOP), an OP extension in which the travel time between i and j depends on the leave time from i, resulting in a three dimensional cost matrix. Each element of this matrix is the result of solving an “Earliest Arrival Problem” between i and j, leaving on time l [Pyrga et al., 2008]. The solution methods presented in this work need to be adapted to incorporate time dependency. A simple approach for calculating an entire time dependent cost matrix would take too long. For instance, this matrix for a medium-sized instance with 50 POIs and 8 hours, has a size of 50*50*8*60=1.200.000, when a time precision of 1 minute is used. This number of Earliest Arrival Problem calculations is not realistic to perform in real–time.

Besides, the evaluation of an insertion becomes much more complex when public transportation is included. A small increase in the planned leave time from one POI can cause a significant increase in the arrival time at the next. For instance, when a tourist just misses the bus and has to wait for the next one or walk to the next POI.

In order to handle the public transportation difficulty, the average travel times between all pairs of POIs can be calculated, resulting in a regular two–dimensional cost matrix. This way, the problem can be solved by a regular “time independent” solution method. A repair procedure needs to adapt the arrival and leave times of the visits of the resulting trip according to the differences between the average travel times and the real travel times. As a consequence, one or more visits can become infeasible and it may be necessary to remove them.

Hotel Selection. The TOP with Hotel Selection generalises the TOP, in which the start and end of each tour are fixed, by making the end location for each tour, except for the last tour, a decision variable. The length of each tour is still restricted to the predetermined time budget, but the end location can be chosen from a set of hotel locations. Only the start of the first tour and the end of the last tour are fixed. Tour i + 1 has to start where tour i ended. An instance of the problem is presented in Figure 8.1.

Mixed Orienteering. The combination of the well-known Vehicle Routing Problem and Arc Routing Problem is defined as the “general routing problem” [Muyldermans et al., 2005]. In the same way, the combination of the OP and the arc routing problem with profits can be defined as the “Mixed Orienteering Problem” (MOP), with scores associated to vertices as well as arcs. Since the name Generalised Orienteering Problem is already assigned [Wang et al., 1996, Ramesh and Brown, 1991, Zong et al., 2005, Wang et al., 2008, Silberholz and Golden, 2009], the name “Mixed Orienteering Problem” is chosen for this new type of problem. To the best


Figure 8.1: The Team Orienteering Problem with Hotel Selection of the author’s knowledge, the MOP has not been subject of scientific publications.

This new problem offers many research opportunities.

Appendix A Real–World Case A.1 Tourist Trip Design Problems A.2 Results

–  –  –

D. Abowd, G. Atkeson, J. Hong, S. Long, R. Kooper, and M. Pinkerton. Cyberguide: A mobile context-aware tour guide. ACM Wireless Networks, 3:421–433, 1997.

E. Alba, F. Luna, and A. Nebro. Advances in parallel heterogeneous genetic algorithms for continuous optimization. International Journal of Applied Mathematics and Computer Science, 14(3):317–333, 2004.

J. Ar´oz, E. Fern´ndez, and C. Zoltan. Privatized rural postman problems. Computers and a a Operations Research, 33:3432–3449, 2006.

J. Ar´oz, E. Fern´ndez, and O. Meza. Solving the prize-collecting rural postman problem.

a a European Journal of Operational Research, 196:886–896, 2009.

C. Archetti, A. Hertz, and M. Speranza. Metaheuristics for the team orienteering problem.

Journal of Heuristics, 13:49–76, 2007.

C. Archetti, D. Feillet, A. Hertz, and M. G. Speranza. The undirected capacitated arc routing problem with profits. Computers and Operations Research, 2009. doi: 10.1016/j.cor.2009.05.005.

C. Archetti, A. Hertz, D. Feillet, and M.G. Speranza. The capacitated team orienteering and profitable tour problem. Journal of the Operational Research Society, 2010. doi: 10.157/ palgrave.jors.2602603.

L. Ardissono, G. Petrone, M. Segnan, and P. Torasso. Ubiquitous user assistance in a tourist information server. In Proceedings of the 2nd international conference on adaptive hypermedia and adaptive web–based systems, volume 2347 of Lecture Notes in Computer Science, pages 14–23, 2002.

L. Ardissono, A. Goy, G. Petrone, M. Signan, and P. Torasso. Intrigue: personalized recommendation of tourism attractions for desktop and handset devices. Applied Artificial Intelligence, 17(8–9):687–714, 2003.

E. Arkin, J. Mitchell, and G. Narasimhan. Resource-constrained geometric network optimization.

In Proceedings of the 14th ACM Symposium on Computational Geometry, pages 307–316, 1998.

R. Baeza-Yates and R Ribeiro-Neto. Modern Information Retrieval. Addison-Wesley, 1999.

J. E. Baker. Reducing bias and inefficiency in the selection algorithm. In Proceedings of the 2nd International Conference on Genetic Algorithms, pages 14–21, Hillsdale, New Jersey, 1987.

Lawrence Erlbaum Associates.

–  –  –

R. Bar-Yehuda, G. Even, and S. Shahar. On approximating a geometric prize–collecting travelling salesman problem with time windows. Journal of Algorithms, 55(1):76–92, 2005.

T. Beer, M. Fuchs, W. H¨pken, H. Werthner, and J. Rasinger. Caips: a context-aware information o push service in tourism. In Information and Communication Technologies in Tourism, pages 129–149, 2007.

P. Beullens, L. Muyldermans, D. Cattrysse, and D. Van Oudheusden. A guided local search heuristic for the capacitated are routing problem. European Journal of Operational Research, 147(3):629–643, 2003.

S. Boussier, D. Feillet, and M. Gendreau. An exact algorithm for the team orienteering problem.

4OR, 5(3):211–230, 2007.

B. Bullnheimer. Ant Colony Optimization in Vehicle Routing. PhD thesis, University of Vienna, 1999.

R. Burke. Encyclopedia of Library and Information Systems, volume 69, chapter Knowledge-based Recommender Systems. 2000.

S. Butt and T. Cavalier. A heuristic for the multiple tour maximum collection problem. Computers and Operations Research, 21:101–111, 1994.

S. Butt and D. Ryan. An optimal solution procedure for the multiple tour maximum collection problem using column generation. Computer and Operations Research, 26:427–441, 1999.

–  –  –

I. Chao, B. Golden, and E. Wasil. Theory and methodology - the team orienteering problem.

European Journal of Operational Research, 88:464–474, 1996a.

I.-M. Chao, B. Golden, and E. Wasil. A fast and effective heuristic for the orienteering problem.

European Journal of Operational Research, 88(3):475–489, 1996b.

R. Chelouah and P. Siarry. A continuous genetic algorithm designed for the global optimization of multimodal functions. Journal of Heuristics, 6:191–213, 2000.

K. Cheverst, N. Davies, K. Mitchell, A. Friday, and C. Efstratiou. Developing a context-aware electronic tourist guide: Some issues and experiences. In Proceedings of ACM CHI Conference on Human Factors in Computer Systems, The Hague, The Netherlands, 2000.

K. Cheverst, N. Davies, and K. Mitchell. The role of adaptive hypermedia in a context-aware tourist guide. Communications of the ACM: Special Issue on Adaptive Web-Based Systems and Adaptive Hypermedia, 45:47–51, 2002.

D. N. Chin and A. Porage. Proceedings of the 8th International Conference on User Modeling, volume 2109 of Lecture Notes in Computer Science, chapter Acquiring user preferences for product customization, pages 95–104. Springer Berlin / Heidelberg, 2001.

L. Console, I. Lombardi, and S. Gioria. Personalized and adaptive services on board a car: an application for tourist information. Journal of Intelligent Information Systems, 21(3):249–284, 2003.

–  –  –

T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press and McGraw–Hill, 1990. ISBN 0-262-03141-8.

D. Costa and A. Hertz. Ants can colour graphs. Journal of the Operational Research Society, 48:

295–305, 1997.

G. Dantzig, R. Fulkerson, and S. Johnson. Solution of a large-scale traveling salesman problem.

Operations Research, 2:393–410, 1954.

B. Dasarathy. Nearest neighbor (NN) norms: NN pattern classification techniques. IEEE Computer Society Press, 1991.

N. Davies, K. Cheverst, K. Mitchell, and A. Efrat. Using and determining location in a contextsensitive tour guide. IEEE Computer: Special Issues on Location Aware Computing, 34:35–41, 2001.

M. Dell’ Amico, F. Maffioli, and P. V¨rbrand. On prize-collecting tours and the asymmetric a travelling salesman problem. International Transactions in Operational Research, 2(3):297–308, 1995.

M. Dell’ Amico, F. Maffioli, and A. Sciomachen. A lagrangian heuristic for the prize collecting travelling salesman problem. Annals of Operations Research, 81:289–306, 1998.

M. Dorigo and L.M. Gambardella. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1):53–66, 1997.

M. Dunlop, P. Ptasinski, A. Morrison, S. McCallum, C. Risbey, and F. Stewart. Design and development of Taeneb city guide - from paper maps and guidebooks to electronic guides.

Technical report, 2004. www.cs.strath.ac.uk/∼mdd/research/publications/04dunlop enter.pdf.

A.S. Dye and S.-L. Shaw. A gis-based spatial decision support system for tourists of great smoky mountains national park. Journal of Retailing and Consumer Services, 14(4):269–278, 2007.

D. Feillet, P. Dejax, and M. Gendreau. The profitable arc tour problem: solution with a branch–and–price algorithm. Transportation Science, 39:539–552, 2005a.

D. Feillet, P. Dejax, and M. Gendreau. Traveling salesman problems with profits. Transportation Science, 39:188–205, 2005b.

T.A. Feo and M.G.C. Resende. A probabilistic heuristic for a computationally difficult set covering problem. Operations Research Letters, 8:67–71, 1989.

Pages:     | 1 |   ...   | 16 | 17 || 19 | 20 |

Similar works:

«bombardier cs300 bombardier cs300 Bombardier CSeries 100 | Ab 2015 im Einsatz | SWISS Ab 2015 beginnt SWISS die Avro RJ100-Flotte mit der Bombardier CSeries 100 abzulösen. Finden Sie die technische Daten zur Bombardier Cseries 100.Bombardier CSeries Wikipedia Bombardier CSeries; CS100-prototyyppi ensilennollaan: Tyyppi: Kanada: Valmistaja: Bombardier: Ensilento: CS100: 16. syyskuuta 2013 CS300: 27 Bombardier Aerospace Wikipedia Bombardier Aerospace ist nach Boeing und Airbus der drittgrößte...»

«Fusion of tarsal the joints Outcome, Diagnostics and Management of patient expectations Mark Stegeman Fusion of the Tarsal Joints: Outcome, Diagnostics and Management of patient expectations Mark Stegeman ISBN: 978-94-6169-772-1 Author: Mark Stegeman This publication was supported by Stichting Orthoresearch Maartenskliniek and by the Nederlandse Orthopaedische Vereniging Copyright Mark Stegeman, 2015 All rights reserved. No part of this publication may be reproduced or transmitted in any form...»

«114 Rev. Ivoir. Sci. Technol., 19 (2012) 114 – 135 ISSN 1813-3290, http://www.revist.ci CONTRIBUTION HYDROGÉOLOGIQUE À LA CONNAISSANCE DES AQUIFÈRES DISCONTINUS DU DÉPARTEMENT DE FERKÉ (NORD DE LA CÔTE D’IVOIRE) POUR UNE MEILLEURE ALIMENTATION EN EAU POTABLE Théophile LASM 1*, Rosine Marie N’Guessan FOSSOU 1, Oscar Zahibo ONETIE1, Derving BAKA 1, Marc YOUAN TA 1,2, Marie Solange OGA 1 et Nagnin SORO 1 Laboratoire des Sciences et Techniques de l’Eau et du Génie de...»

«Surgical Asepsis and Soft tissue Surgery technique Shane Guerin MVB MACVSc CertSAO DVCSc Dipl ECVS MRCVS Gilabbey Veterinary Hospital, Vicars Road, Cork An animals surgical risk is influenced by the significance of its presenting disease and other preexisting abnormalities. Preoperative assessment and stabilisation of the patient allow the surgeon to anticipate complications and to reduce their occurrence. Likewise, preoperative preparation of the patient and operating team helps minimise...»

«Surface Web Semantics for Structured Natural Language Processing Mohit Bansal Electrical Engineering and Computer Sciences University of California at Berkeley Technical Report No. UCB/EECS-2015-20 http://www.eecs.berkeley.edu/Pubs/TechRpts/2015/EECS-2015-20.html May 1, 2015 Copyright © 2015, by the author(s). All rights reserved. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or...»

«An Investigation of Eighth Grade Students’ Problem Posing Skills (Turkey Sample) Elif Esra Arıkan1, Hasan Ünal2 Yildiz Technical University, Turkey, arikanee@gmail.com Yildiz Technical University, Turkey, hunal@yildiz.edu.tr www.ijres.net To cite this article: Arikan, E. E. & Unal, H. (2015). An investigation of eighth grade students’ problem posing skills (Turkey sample). International Journal of Research in Education and Science (IJRES), 1(1), 23-30. This article may be used for...»

«Book Yourself Solid Workbook Book Yourself Solid The Fastest, Easiest, and Most Reliable System for Getting More Clients Than You Can Handle Even if You Hate Marketing and Selling Complimentary WORKBOOK by Michael Port ii © Michael Port & Associates LLC. All rights Reserved. Book Yourself Solid Workbook Copyright All rights reserved. No part of this workbook may be reproduced or transmitted in any form or by any means electronic or mechanical, including photocopying, recording, or by any...»

«BESONDERE VERTRAGSBEDINGUNGEN ZUM VIRTUAL PRIVATE SERVER Stand 17.03.2014 § 1: VERTRAGSGEGENSTAND Diese besonderen Vertragsbedingungen ergänzen die allgemeinen Vertragsbedingungen von OVH und regeln die technischen und finanziellen Bedingungen, nach denen OVH den Virtual Private Server (VPS) des Kunden auf seiner Plattform betreibt. Für den Fall eines Widerspruchs zwischen den allgemeinen und den besonderen Vertragsbedingungen gehen letztgenannte vor. § 2: AUSSTATTUNG OVH bietet einen...»

«KESO: Konstruktiver Speicherschutz für Eingebettete Systeme Der Technischen Fakultät der Universität Erlangen-Nürnberg zur Erlangung des Grades DOKTOR-INGENIEUR vorgelegt von Christian Walter Alois Wawersich Erlangen 2009 Als Dissertation genehmigt von der Technischen Fakultät der Universität Erlangen-Nürnberg Tag der Einreichung: 27.10.2008 Tag der Promotion: 05.03.2009 Dekan: Prof. Dr.-Ing. habil. Huber Johannes Erster Berichterstatter: Prof. Dr. Wolfgang Schröder-Preikschat Zweiter...»

«2011 3rd International Conference on Information and Financial Engineering IPEDR vol.12 (2011) © (2011) IACSIT Press, Singapore Airfare Price Elasticity over non-Business Passengers Mahnosh Kouhpaei MBA Graduate, Multimedia University, Malaysia Technical Manager, Tandisban Tour and Travel Agency, Tehran, Iran E-mail: mahnoush.kouhpaei@gmail.com Abstract. In recent years, the air travel has become the most popular mean of transportation all around the world. As the safest mean of...»

«Drnevich Dissertation Essay 2 draft 032106.doc 1 DRNEVICH DISSERTATION CHAPTER 3. ORDINARY AND DYNAMIC CAPABILITIES: IMPLICATIONS FOR FIRM PERFORMANCE AND COMPETITIVE HETEROGENEITY ABSTRACT A common issue in strategic management research involves sources of interfirm performance differences. Research on this issue assumes such competitive heterogeneity is attributable to variation in firm level factors of resources and capabilities, but this is difficult to establish empirically. This study...»

«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...»

<<  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.