«Automated Tourist Decision Support Wouter Souﬀriau Dissertation presented in partial fulﬁllment of the requirements for the degree of Doctor in ...»
The choice of an adequate metaheuristic framework is important, as a good balance between intensiﬁcation and diversiﬁcations is a key success factor in ﬁnding 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 diversiﬁcation, 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 suﬃciently explore large parts of the solution landscape. A strong diversiﬁcation 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.
Fine–tuning parameters still requires a lot of work. Automated parameterisation methods can be used to partly relieve the algorithm developer from this burden.
MAIN CONTRIBUTIONS 125
8.1 Main Contributions While realising the main objective, this work has led to a number of signiﬁcant
contributions to the ﬁeld 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 ﬁeld of information retrieval in order to calculate tailored city tours on–the–ﬂy.
• 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 eﬀort, compared to other state–of–the–art approaches.
• Chapter 4 presents, to the best of the author’s knowledge, the ﬁrst “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 diﬀerent 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 eﬃciently tackles a set of diﬀerent 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 ﬁnding 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 identiﬁed as one of the most appreciated functionalities of an MTG [Schmidt-Belz et al., 2003, Stroobants, 2006, Beer et al., 2007]. Fomin and Lingas  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 signiﬁcant 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 diﬃculty, 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 diﬀerences 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 ﬁxed, 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 ﬁrst tour and the end of the last tour are ﬁxed. 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 deﬁned as the “general routing problem” [Muyldermans et al., 2005]. In the same way, the combination of the OP and the arc routing problem with proﬁts can be deﬁned 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
RESEARCH OPPORTUNITIES 127Figure 8.1: The Team Orienteering Problem with Hotel Selection of the author’s knowledge, the MOP has not been subject of scientiﬁc publications.
This new problem oﬀers 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 proﬁts. 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 proﬁtable 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 Artiﬁcial 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 ineﬃciency 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 eﬀective 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:
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 classiﬁcation 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. Maﬃoli, 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. Maﬃoli, 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 proﬁtable 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 proﬁts. Transportation Science, 39:188–205, 2005b.
T.A. Feo and M.G.C. Resende. A probabilistic heuristic for a computationally diﬃcult set covering problem. Operations Research Letters, 8:67–71, 1989.