# «Automated Tourist Decision Support Wouter Souﬀriau Dissertation presented in partial fulﬁllment of the requirements for the degree of Doctor in ...»

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 ﬁve historic cities in Flanders, Belgium.

The diﬀerent tourist oﬃces supply and maintain a detailed database containing information about the diﬀerent points of interest in their city. A tourist states his context and interest, based on which a selection of visits is ﬁltered. 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 ﬁrst 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 oﬃces, 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 diﬀerent 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 eﬀort 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 diﬀerent 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 diﬀers 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 oﬃces market their region by oﬀering 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 oﬃce determined a ﬁxed 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 inﬂexible 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 ﬁve regions and is composed of 989 nodes and 2963 arcs, with a total of 3585 kilometres. At ﬁrst, 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, diﬃculty, etc. Planning a route that satisﬁes 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 proﬁt is associated with each arc. Feillet et al. [2005a] proposed a branch-and-price approach for the “proﬁtable 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 diﬀerence between the proﬁt and the total travel distance. Archetti et al.

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

## MATHEMATICAL FORMULATION 111

** 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 deﬁned 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 coeﬃcients 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 modiﬁed 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 diﬀerence 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 diﬀerence with the proﬁtable arc tour problem is that in the AOP every arc can be visited at most once. The diﬀerence with the “undirected capacitated arc routing problem with proﬁts” [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 inﬁnity 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 ﬁrst deﬁnes 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 eﬃciently.

114 CYCLE ROUTE PLANNING

**7.2.1 Concepts and Solution Representation**

In a network, a “path” between two vertices is deﬁned 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 ﬁrst 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 diﬀerence 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.

SOLUTION APPROACH 115