FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:     | 1 |   ...   | 14 | 15 || 17 | 18 |   ...   | 20 |

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

-- [ Page 16 ] --

Some users give suggestions for extra functionalities such as enabling to save the trip for the next visit or include booking of restaurants and hotels. Others suggest to extend the website to other cities and translate the content to other languages, as it is currently only available in English and Dutch. Overall, apart from the technical malfunctions reported, the remarks concerning the functionality are positive.

6.5 Conclusions

A web–based tourist expert system, named City Trip Planner, is presented in order to demonstrate the applicability of the proposed model. The City Trip Planner proposes custom–made city trips, tailored to the user’s interests and context. The system is implemented as a web site for five historic cities in Flanders, Belgium.

The different tourist offices supply and maintain a detailed database containing information about the different points of interest in their city. A tourist states his context and interest, based on which a selection of visits is filtered. The proposed tourist trip design algorithm maximises the tourist’s trip satisfaction, by selecting the most interesting visits while respecting all constraints. Moreover, a (lunch) break can also be scheduled. Usage statistics and user feedback during the first two months clearly indicate that the City Trip Planner is appreciated and proposes high quality trips to tourists. Based on the high number of users of the system and the feedback from the local tourist offices, it can be concluded that tourists are looking for expert systems like this to plan their trip. Extending the system to take into account weather forecasts, budget limitations or public transportation will certainly increase the usefulness.

The proposed model enables multiple opening hours per day, and different opening hours each day, and thus overcomes the drawbacks of the TOPTW model of Chapter 4. This is achieved by splitting up multiple TW POIs into single TW POIs, and adding knapsack constraints in order to allow only one actual visit, similar to the model presented in Chapter 5.

The web application allows planning multiple day visits in advance. When actually making the trip, unexpected events may turn the planning infeasible. A mobile device could overcome this problem since it could provide immediately an adapted plan. The limited computational resources of a mobile device could become a problem. However, the mobile device only has to take the current day into account, and can discard POIs that are planned to be visited on other days. In this way, 108 THE CITY TRIP PLANNER substantially less computational resources are required to alternate the plan, as shown in Chapter 4.

The City Trip Planner uses a straightforward technique to estimate the interest of the tourist in a POI. As the focus of this work is on integration of selection and routing, subject to a wide range of constraints, less effort has been devoted to the interest estimation part, which could be extended to incorporate more advanced POI recommendation techniques, which are described in Section 1.1.2.

When examining the real–life data from the different historic cities, it can be noticed that about 80% of the POIs are not subject to TW constraints. The remaining POIs have opening hours that largely overlap. This observation supports the need that was already expressed in Section 5.6, namely the need for a procedure that reduces the total travel time, even for problem with TWs.

Chapter 7

Cycle Route Planning

This chapter introduces the Arc Orienteering Problem (AOP), an arc routing variant of the OP, which differs in that score rewards are collected for visiting arcs, instead of vertices. Figure 7.1 illustrates this problem, but (directed) arcs are visualised as (undirected) edges for the sake of clarity. The AOP enables modelling scenic routes in TTDPs.

Figure 7.1: The Arc Orienteering Problem

In countries like Belgium and the Netherlands, cycling is a popular sport and a widespread recreational activity. Many cyclists try to combine sport and leisure by traversing scenic cycle routes, enjoying beautiful sights or riding quietly along a canal or river. Regional tourist offices market their region by offering recreational cyclists a number of products. These products have evolved over the years from static printed route maps to state–of–the–art online applications. First, static scenic routes were developed. A tourist office determined a fixed route, baptised

–  –  –

it with a commercial name, placed signposts along the track and started to sell maps. An example signpost is shown in Figure 7.2. The cyclist could then follow the route in either direction.

–  –  –

Although popular, these routes have a clear drawback of being inflexible both with respect to the track and the length. In order to overcome this limitation, a more versatile concept resulted in the so–called cycling networks. These networks are graphs consisting of nodes (intersections) interconnected by cycle–friendly arcs (tracks). Direction signposts containing node numbers, illustrated by Figure 7.3, are placed throughout the entire network in order to guide the user. The East Flanders’ network is a concatenation of five regions and is composed of 989 nodes and 2963 arcs, with a total of 3585 kilometres. At first, these networks were published as maps, of which in a period of three years (2006–2008), 193208 were sold in East Flanders. With a map of the network, users could plan custom–built routes, tailored to their personal preferences involving length, area, difficulty, etc. Planning a route that satisfies all these requirements is a somewhat complicated problem.

Therefore, the Belgian province of East Flanders came up with an on–line version of their cycling network, which facilitates creating routes, printing or downloading these to a personal navigation device and sharing route information with friends through social networking sites. Furthermore, an automated route planning tool has been developed and is incorporated into the software. This particular planning tool is presented in this chapter. The route planning problem can be perceived as an AOP.

Only a few papers consider arc routing variants of the OP where a profit is associated with each arc. Feillet et al. [2005a] proposed a branch-and-price approach for the “profitable arc tour problem”. Ar´oz et al. [2006] introduce the “privatised rural a postman problem”, which was later called the “prize-collecting rural postman problem” by Ar´oz et al. [2009]. In these problems, the objective is to maximise a the difference between the profit and the total travel distance. Archetti et al.

[2009] describe the “undirected capacitated arc routing problem with profits”. The objective of this problem is to determine a route for each available vehicle in order to maximise the total collected profit, without violating the capacity and time limit of each vehicle. In the next section, the differences between these models and the East Flanders model for cycle route planning is explained.


Figure 7.3: Cycle Network

The remaining of this chapter is structured as follows: in Section 7.1, the problem is described in detail by means of a mathematical optimisation model. Section

7.2 describes a heuristic solution approach for the bike route planning problem.

Section 7.3 tests the approach on real–world data and compares the results with those obtained by a commercial solver.

Section 7.4 elaborates on the present use of the system in East Flanders. Section 7.5 concludes this chapter and points out directions for further research.

7.1 Mathematical Formulation

A cycle route planning tool allows recreational cyclists to choose a starting and ending point in the cycling network and the length of their route. It should immediately design a route in the network corresponding to the requirements. This problem was mathematically modelled as an AOP, which can be defined with the aid of a directed graph G = (V, A), where V = {v1,..., vn } is the vertex set and A is the arc set. With each arc aij ∈ A a cost cij and a non–negative score Sij are associated. The AOP consists of determining a path G ⊂ G, including pre–set start vertex v1 and end vertex vn, with a cost smaller than Cmax. The goal of the AOP is to determine a path that maximises the total collected score. In contrast to previous previous chapters, cij and Cmax are used instead of tij and Tmax, respectively, because the cycling application focuses on distance instead of time.

Making use of the notation introduced above, the AOP is formulated below as an integer program (ui position of vertex i along the path; xij = 1 if arc (vi, vj ) is 112 CYCLE ROUTE PLANNING

included in the path, 0 otherwise):

–  –  –

The objective function (7.1) is to maximise the total collected score. Constraints (7.2) guarantee that the route starts in vertex 1 and ends in vertex n. Constraints (7.3) ensure the connectivity of the route and guarantee that each vertex and each arc is visited at most once. Constraint (7.4) limits the cost of the route. Constraints (7.5) and (7.6) prevent sub–tours.

Formulation (7.1)–(7.7) does not allow multiple visits of a vertex. This requirement can be easily relaxed; in the case of East Flanders, it was imposed to design more SOLUTION APPROACH 113 conventional cycle trips. Typically, cost coefficients cij are equal to arc distances.

Value Cmax is often not a strict upper bound. Recreational cyclists aim at riding a certain number of kilometres, but they do not mind riding a bit more if this brings the total length closer to the requested length. Therefore, Cmax was always enlarged by one kilometre. In the present applications, the score values (Sij ) are also taken equal to cij. As a result, the total length of a trip will indeed be very close to the length requested by the cyclist. In the future, it will be easy to include other types of cyclists’ preferences. Examples of such preferences are: avoid or include steep inclines, dirt roads as much as possible, etc. The score of each arc can easily be modified in order to take these preferences into account, when the necessary data is available. Perhaps it will be necessary to explicitly set a lower n n bound on i=1 j=1 cij xij.

The difference between the AOP as formulated in (7.1)–(7.7) and the prize–collecting rural postman problem [Ar´oz et al., 2009] or privatized rural postman problem a [Ar´oz et al., 2006] is that in the AOP the available cost is limited. The main a difference with the profitable arc tour problem is that in the AOP every arc can be visited at most once. The difference with the “undirected capacitated arc routing problem with profits” [Archetti et al., 2009] is that (a) the AOP uses a directed graph, (b) considers only one route, and (c) has no capacity constraints.

Note that AOP instances can be converted to Multi–Constraint OP instances, by replacing each arc by a vertex, setting the cost between two new vertices to zero if they are connected and to infinity if not, and adding knapsack constraints stating that per vertex of the original AOP formulation at most one incoming arc (and at most one outgoing arc) can be visited.

7.2 Solution Approach

The solution approach implemented in the East Flanders case is based on a GRASP, which was already successfully applied to the TOP in Chapter 3 and used for the City Trip Planner in Chapter 6. However, these former, node–based, solution approaches cannot be straightforwardly applied to the AOP because of the special cost matrix, which is explained at the end of the previous section. Up until now, the structure of the underlying road network was largely ignored. Therefore, Section 7.2.1 first defines a number of concepts and describes how a solution to the AOP is represented. These solutions are related to each other by means of a neighbourhood structure (Section 7.2.2) and form a search landscape. Finally, Section 7.2.3 describes how to explore this landscape efficiently.


7.2.1 Concepts and Solution Representation

In a network, a “path” between two vertices is defined as a list of consecutive arcs.

The cost of a path is the sum of the costs of the individual arcs. The cost between two arcs is the cost of the cheapest path between the end vertex of the first arc and the start vertex of the second arc.

In the solution approach, a “route” is represented by a list of visited arcs. In contrast to a path, these arcs are not required to be connected. A corresponding path can be constructed by augmenting the route with the cheapest paths between the non–consecutive arcs. The cost and score of a route are respectively equal to the cost and score of its corresponding path. A route is a valid solution to the AOP if

• its corresponding path starts at vertex 1,

• its corresponding path ends at vertex n,

• its corresponding path does not contain any arc more than once,

• each vertex is visited at most once, except for the start vertex, and

• its cost is below Cmax.

7.2.2 Neighbourhood Structure A solution s is a member of a neighbourhood of solution s, if it can be converted to s by making a small change. Typical local search based algorithms explore a neighbourhood by iteratively generating the neighbourhood of the current solution and moving from this current solution to an improving neighbouring solution. This process is repeated until the current solution cannot be improved anymore, and thus a local optimum is reached.

The neighbourhood structure for this approach is based on insertion of extra arcs:

a valid route can be enlarged by insertion of an extra arc e between arcs d and f. An insertion leads to a score increase corresponding to the difference between the score of the newly corresponding route minus the score of the current one and to a cost increase equal to the sum of the costs between arcs d and e and arcs e and f minus the cost between arcs d and f. Algorithm listing 11 describes how a neighbourhood of insertions is generated.


–  –  –

Pages:     | 1 |   ...   | 14 | 15 || 17 | 18 |   ...   | 20 |

Similar works:

«TECHNISCHE UNIVERSITÄT MÜNCHEN Fakultät Wissenschaftszentrum Weihenstephan für Ernährung, Landnutzung und Umwelt Lehrstuhl für Experimentelle Genetik Physiology and molecular characterization of metabolism related mouse models for bone disease Shen Chi Vollständiger Abdruck der von der Fakultät Wissenschaftszentrum Weihenstephan für Ernährung, Landnutzung und Umwelt der Technischen Universität München zur Erlangung des akademischen Grades eines Doktors der Naturwissenschaften...»

«TERRA NOSTRA Schriften der Alfred-Wegener-Stiftung 01/1 20. Internationale Polartagung der Deutschen Gesellschaft für Polarforschung DOP 26. 30. März 2001 Programm und Zusammenfassungen der Tagungsbeiträge ß-b Technische Universität Dresden X jp Institut für Planetare Geodäsie IMPRESSUM Terra Nostra 20. Internationale Polartagung der DGP in Dresden Heft 01/1: Programm und Zusammenfassungen der Tagungsbeiträge Herausgeber: Alfred-Wegener-Stiftung (AWS) Arno-Holz-Str. 14 Alexander von...»

«Diss. ETH Nr. 12599 LIFE CYCLE INVENTORY ANALYSIS FOR DECISION-MAKING SCOPE-DEPENDENT INVENTORY SYSTEM MODELS AND CONTEXT-SPECIFIC JOINT PRODUCT ALLOCATION A dissertation submitted to the SWISS FEDERAL INSTITUTE OF TECHNOLOGY ZURICH for the degree of DOCTOR OF TECHNICAL SCIENCES presented by ROLF FRISCHKNECHT Dipl. Bau-Ing. ETH born 17. August 1962 citizen of Basel-Stadt and Schwellbrunn (Appenzell Ausserrhoden) accepted on the recommendation of Prof. Dr. P. Suter, examiner Prof. Dr. D. Spreng,...»

«Supporting Asynchronous Collaboration for Interactive Visualization Jeffrey Michael Heer Electrical Engineering and Computer Sciences University of California at Berkeley Technical Report No. UCB/EECS-2008-166 http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-166.html December 17, 2008 Copyright 2008, 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...»

«Nova Acta Leopoldina NF 111, Nr. 379, 205– 216 (2010) Implantation and Explantation of Active Subretinal Visual Prostheses Using a Combined Transcutaneous and Transchoroidal Approach Florian Gekeler1, Peter Szurman1, Dorothea BeSch1, Martin rohrBach1, Eberhart zrenner1, Karl Ulrich Bartz-Schmidt1, and Helmut SachS2 With 5 Figures Abstract We are reporting on the surgical technique for implantation and explantation of subretinal visual implants with extra-ocular and extra-corporeal parts. We...»

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

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

«3.1 Bericht Teilprojekt 5 3.1.1 Titel / Title Reaktionen von gespeicherten kalten Ionen mit H Atomen und interstellar relevanten Molekülen Reactions of stored cold ions with H atoms and molecules of interstellar relevance 3.1.2 Berichtszeitraum / reported period 01.07.2003 31.12.2006 3.1.3 Projektleiter / principle investigator Gerlich, Dieter, Prof. Dr., Dipl.-Phys., Universitätsprofessor Institut für Physik, Technische Universität, 09107 Chemnitz Luca, Alfonz, Dr., wiss. Assistent...»

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

«CITY OF TARPON SPRINGS CURRENT OPENINGS EFFECTIVE APRIL 21, 2016 Position: HUMAN RESOURCES/RISK MANAGEMENT COORDINATOR (REVISED) Department: HUMAN RESOURCES Annual Salary Range: $47,112 $75,900 D.O.Q. Closing Date: OPEN UNTIL FILLED Under limited supervision, analyzes, develops and implements processes involved with human resources and risk management functions. Position involves a broad range of responsibility and requires the ability to work independently with considerable latitude for...»

«Although many researchers have documented higher levels of black-white inequality in areas with a high concentration of blacks, the mechanisms underlying this finding have been elusive. Black underrepresentation in management may be one such mechanism. We ask whether black workers’ underrepresentation in managerial jobs is especially pronounced in labor markets with a larger black population. Using a unique, two-level data set that combines a large data set of private sector firms with Census...»

«UNIVERSIDAD COMPLUTENSE DE MADRID FACULTAD DE INFORMÁTICA Departamento de Arquitectura de Computadores y Automática TESIS DOCTORAL Técnicas de planificación en entornos reconfigurables para aplicaciones multimedia Scheduling techniques in reconfigurable environments for multimedia applications MEMORIA PARA OPTAR AL GRADO DE DOCTOR PRESENTADA POR Juan Antonio Clemente Barreira Directores: Daniel Mozos Muñoz Jesús Javier Resano Ezcaray Madrid, 2011 ISBN : 978-84-694-8487-6 © Juan Antonio...»

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