Abstract: This study describes scheduling an itinerary in multimodal urban transportation network proposed to address the tour planning problem which is usually required in tourism. The approach has utilized a genetic algorithm to solve the problem aims at catching as many scores as possible considering user preferences and restrictions of interested points. The proposed approach has been developed for analyzing the transportation network of Tehran and the experimental results are given in this study. The results show the high capabilities of proposed methodology.
INTRODUCTION
Over the last two decades, progresses in information and communication technology (ICT) have changed the tourism industry and lead it towards the e-tourism. Emersion of handheld and palm-sized computers in different forms of smart cell phones, PDAs, pocket PCS, etc. together with advancement in positioning techniques open new horizons in tourist travel planning and guidance fields. The prominent characteristics of these devices such as their small volume and light weight made them more useful in mobile computing where a tourist may be assumed as a mobile and moving object. The integrations of these products with the tourist requirements resulted in some applications, which support the moving tourist based on both geospatial data and attributes, are usually called Mobile Tourist Guide (MTG).
The MTGs offer a ubiquitous access, i.e., at anytime, from anywhere with any media, to tourism information such as points of interest (POIs) and available facilities (Schwinger et al., 2005; Vansteenwegen and Oudheusden, 2007). They may assist tourists during whole of three phases of a travel lifeline, i.e., before, during and after a trip. In pre-trip phase a tourist may use these systems to study and review the POIs to design his/her itinerary. During the trip, these systems provide the tourist with online and offline information and explanation about the visited POIs and re-designing the tour based on changed current parameters. It is also possible for user to add some attributes to points in the database of system. Finally, post-trip phase may include review of visited places and analysis of trip based on saved information in system such as position and time.
Most of the existing MTGs benefit the contextual information to present more suitable and user-friendly information and services to their users. Up to now, many context-aware MTGs such as Cyberguide (Abowd et al., 1997), DEEP MAP (Malaka and Zipf, 2000), CRUMPET (Poslad et al., 2001), Gulliver’s Genie (O’Hare and O’Grady, 2003) and GUIDE (Cheverst et al., 2002) have been developed. An almost comprehensive survey of existing systems may be found by Schwinger et al. (2005).
In almost all of the existing MTGs, general collections of analysis and queries such as representation and user interface, query on POIs and map, path finding and guidance are available for the users. Among them, the most interesting analysis are finding the (shortest) path between two specific points and planning generic visitor tours. Although these functions are of importance for users of MTGs, but tourists often would like to prepare their own personalized tours which pass through some prioritized POIs in a delineated temporal interval according to their preferences (Kramer et al., 2006). Further more, using public transportation network of visited urban area, which is multimodal in nature, is more attractive to some tourists.
Adding the capabilities of designing a multimodal tour based on the constraints and user preferences to existing MTGs can improve the efficiency of them and introduce the new generation of these systems as the 2G MTGs. A framework to implement such an extension is shown in Fig. 1. In this framework, the user introduces his/her preferences to the system and these information as well as processed context information is utilized as the constraints of tour planning. The system uses a geodatabase to access the transportation networks and POIs.
| Fig. 1: | The proposed framework for 2G extension of current MTGs |
| Fig. 2: | (a) Monomodal route and (b) Multimodal route |
In the engine of the system, the tour planning module uses a shortest multimodal path finding module as a subroutine. The final result of the system is an itinerary for a tourist based on his/her constraints and preferences.
In this study, the main focus is on tour planning module of proposed framework in which the problem of planning a multimodal tour is modeled and formulated and an algorithm is described to solve this problem. In this problem, it is necessary to consider specifications and parameters of each mode on real transit network, time constraints of user and POIs and the spatial characteristics of pathways and visited points.
Before starting the main problem statement, it is necessary to define the monomodal and multimodal routes in transportation network. As illustrated in Fig. 2a, in a monomodal route, a tourist may use just one type of transportation modes, i.e., taxi, subway, bus, walking, personal car, etc. to transport between a specific departure and destination, while as depicted in Fig. 2b, in multimodal routes, the tourist utilizes the combination of several modes of transportation. Multimodal routes may be selected due to different reasons such as decreasing the cost or time of travel. In this study, it is assumed that the network consists of three modes of bus, subway and walking.
By tour planning problem, we mean the problem that involves generating a schedule or itinerary to visit some POIs which are achieved through a transportation network and satisfies some objective function(s), given a set of constraints. The tour may be either closed in which the first and last point are the same or open where the first and last point are different. It is common to use the term of Tour for closed one in tourism. This problem may have several applications in different fields. For instance, a citizen may wish exit her home to visit some stores and return there; hence she may need to plan a tour to minimize the spent time or maximize the number of visiting stores. Tour planning problem may be considered as a variation of well-known Travelling Salesperson Problem (TSP). Tour planning is strongly a NP-hard problem and to solve this problem, several methods and techniques have been proposed up to now (Gutin and Punnen, 2002).
According to the definition of tour planning, three types of tours may be generally encountered:
| • | The tour should pass through POIs where all of them are mandatory |
| • | The tour should pass through POIs where some of them are mandatory |
| • | The tour should pass through POIs where none of them are mandatory |
For each of these three general groups, some subgroups may be found if objective function is either single or multiple, some POIs have priority over the others, entrance to and staying at POIs are time-dependent and etc. The problem which is dealt with in this study is a subset of second type of tour planning. Since it is not possible for a tourist to visit all POIs during limited time of staying in a city, thus he/she should select those POIs which have higher priority for him/her and then a tourist needs to have an itinerary to visit these points. Thus the problem is to design an itinerary for a given time duration, e.g., an 8 h program, for a tourist who wishes to visit as many high priority POIs as possible in this duration. Priority value indicates how strong the tourist wishes to visit that POI. For example, for a tourist going to a museum may has higher priority degree than going to a shopping center. He/she may encounter some restrictions and constraints using POIs such as opening/closing time and closed days. As well, he/she may wish to use the shortest multimodal routes to go from one POI to the other one. To solve this optimization problem in a multimodal and temporal network a genetic algorithm have been assisted which is described in details in the next section.
Personalized and user-oriented tour planning has been one of the main research interests among researchers who work on developing mobile guides systems. One of the first generation of MTGs which offer tour planning considering user profile is GUIDE (Cheverst et al., 2002). In this system, tourists select the POIs and the system create a tour in the city of Lancaster taking into account the selected attractions, the preferences of the user, the opening times of POIs, etc. This system has the capabilities of updating the user profile and dynamic re-planning the tour as the context of user change. The major drawback of this system was difficulties a tourist encounters when enter his/her personal preferences to create a personalized tour (Souffriau et al., 2008).
Maruyama et al. (2004) proposed a personal navigation system for tourism called P-Tour. In this system, a user selects some sightseeing spots with importance degree and temporal restrictions on arrive and stay duration. Then, the system computes the nearly best schedule to visit some of the specified points. As well, it also provides the users with temporal guidance and automatic modification of schedule as the situation and context changes. To solve the problem, they use the genetic algorithm. They extended P-tour to allow the user to design a multi-objective tour and navigate the user between POIs (Shiraishi et al., 2005). They assumed that the paths between POIs are monomodal and have known values.
Another system which plans personalized tours on-the-fly is the Dynamic Tour Guide (DTG) developed by Ten Hagen et al. (2005). They used the so-called Tour Building Blocks (TBB) as the points of interest and developed an ontology consists of a tree of concept classes and describes each TBB. This part of system calculates the similarity between the TBB and the profile of the user. Then, according to assignment of interest matching points, an algorithm tries to plan a tour by maximizing the sum of the interest matching points within a given time frame (Ten Hagen et al., 2005).
More recent research to solve Tourist Trip Design Problems (TTDP) is the work by Souffriau et al. (2008). In addition to tour planning, they developed an approach to extract the scores associated to POIs automatically. Documents related to POIs are indexed using the vector space model and then the similarities between the tourist’s interests and the documents are calculated. In this way the personalized scores for locations are extracted and used in a guided local search metaheuristic approach to maximize the total score of the visited locations, while keeping the total time (or distance) below the available time budget.
PROPOSED METHODOLOGY FOR ITINERARY PLANNING
To solve the tour planning problem, the Genetic algorithm (GA) is assisted. Genetic algorithm is a member of a group of methods, known as meta-heuristics, which comprise of simulated annealing method, tabu search method, the ant colony algorithms, particle swarm optimization, artificial immune systems, distributed reinforcement learning, etc. and have been proposed to solve the difficult possible optimization problems (Dreo et al., 2006). Genetic algorithms were invented by John Holland in the 1960s and (Holland, 1975) were developed by Holland and his students and colleagues at the University of Michigan in the 1960s and the 1970s (Goldberg, 1989). The general algorithm of this approach is shown in Fig. 3.
GA is different from other heuristic methods in several ways. The most important difference is that GA works on a population of possible solutions, while other heuristic methods use a single solution in their iterations. The general acceptance is that GA is particularly suited to multidimensional global search problems where the search space potentially contains multiple local minima (Haupt and Haupt, 2004). The basic GA does not require extensive knowledge of the search space, such as likely solution bounds or functional derivatives. As well, GA has a number of other advantages, some of them are: (1) Concept is easy to understand, (2) Modular, separate from application, (3) Supports multi-objective optimization, (4) Easy to exploit previous or alternate solutions, (5) Always an answer; answer gets better with time, (6) Ability to scan a vast solution set quickly, (7) Bad Initial population do not affect the end solution negatively, (8) Are usefuland efficient when the search space is large, complex or poorly understood. According to these considerable advantages of GA, this approach may be the first candidate when someone wishes to solve an optimization problem. Additional information can be found in Goldberg (1989), Buckles and Petry (1992), Melanie(1999), Haupt and Haupt (2004) and Ashlock (2006).
As shown in Fig. 3, the first step to take advantage of GA is coding the chromosome and initialization. Since the amount of achieved priority levels of POIs must be maximized, the numbers of POIs is not known and the chromosome with variable length is used to show a tour in the network. The values of genes show the IDs of POIs and the locus of genes in a chromosome represents the order of that POI in a tour. Both the length of the chromosome and the alleles (except the first and last one which shows the predefined source and destination) are selected randomly (Fig. 4).
To keep the information about POIs, a table is created as shown in Table 1. The user may modify the data of Priority and Staying time columns of this table to coincide his/her criteria. If the table is not changed by user, the default state of table is considered in which all of the priorities assumed to be the same. Since the transportation services in a multimodal network, which is used to transport between two POIs, are time-dependent, the user should input the start time and duration of the tour.
| Fig. 3: | Steps of a generic GA (Dr’eo et al., 2006) |
| Fig. 4: | Proposed chromosome configuration |
| Table 1: | Information table of POIs |
To produce the initial population, the genes are generated randomly one by one to create the chromosomes. When the population is generated, the cost of each chromosome is calculated and associated to them. To estimate the cost, the information table of POIs and multimodal route function is utilized. The multimodal shortest route finding function calculates the temporal weight of routes between points whenever called and is:
[Route, τij] = MMRoute (POIi,
POIj, τ) |
Inputs to this function are the source (POIi), destination (POIj) and start time of trip (τ). The function returns the shortest multimodal route (Route) and the travel duration (τij).
The next step is natural selection in which the fittest chromosomes are survived and the remaining ones are discarded from population. The selection rate, Crate, which is usually arbitrary, is used to show the fraction of survived chromosomes:
numkeep = Cratexnumpop |
It is often to keep half of the population in each iteration, i.e., Crate = 50%. This rate is used in this procedure. The kept chromosomes form the mating pool. The third step is the selection in which two chromosomes are selected from mating pool to produce two new offspring. The procedure continues until numpop-numkeep offspring are born to replace the discarded chromosomes. There are several selection methods such as random paring, weighted random (roulette wheel) paring and tournament selection (Haupt and Haupt, 2004). The roulette wheel paring is used in this section. In this method, the probability assigned to a chromosome is inversely proportional to its cost (Goldberg, 1989). Elitism strategy is also adopted as well which guarantees that the best individuals in a population survive into the next generation. In proposed solution, two chromosomes are kept as elite ones. The mating is the fourth step in which offspring are created from parents selected in the previous step. It is often to produce two offspring from mating two parents using randomly selected crossover point(s) on the parents’ chromosome.
In proposed algorithm, the combination of both single-point and two-point crossover is used.
| Fig. 5: | Validation of chromosomes after crossover process |
As well, a post-process procedure is assisted to ensure that all chromosomes to be a valid tour without subtour(s). In this procedure, some genes are added to/removed from chromosome to rebuild a valid tour. Adding some genes to a chromosome is like the adding genes to build the initial chromosomes. An example is shown in Fig. 5 in which two parents (chromosomes (a) and (b)) are mated and the result is generation of two offspring (chromosomes (c) and (d)). Chromosome (d) has a subtour, thus is not valid. The validation step which is conducted after mating change the chromosome (d) by removing two genes (fourth and fifth ones) and the chromosome (e) remains unchanged.
After this step, the numbers of chromosomes are again equal to population size. To keep away from local optimal solution and keep the algorithm converging fast before sampling the entire search space, in the next step the random mutation is assisted. This procedure changes some alleles according to the mutation rate. Since the chromosomes shows a tour as the sequence of visiting POIs, thus changing the value of any genes may made the chromosome to be ineligible and do not show any valid tour. Again a post-processing procedure is assisted to validate the tours. The costs associated with offspring and mutated chromosomes are again computed and assigned. The whole process, i.e., step 2 to 5 is iterated until the termination criteria are satisfied.
EXPERIMENTAL RESULTS
The proposed algorithm is evaluated through conduction of some experimental tests over the data of a portion of city of Tehran, capital city of Iran. The data set include pathways (consists of streets and avenues) and subway system (consists of lines and stations) as shown in Fig. 6a as well as bus service lines and stops. The dataset is prepared as they should be, i.e. the topologic structure is rebuilt and required tables are created.
| Fig. 6: | Dataset used to evaluate the proposed methodology |
| Fig. 7: | The tour planning and its corresponding convergence plot |
Moreover, some POIs have been added to dataset and assigned corresponding attribute data. POIs are classified into six main classes of Handicraft Centers, Restaurants, Shopping Centers, Hotels, Museums and Cinemas (Fig. 6b).
To evaluate the efficiency and robustness of proposed tour planning algorithm, it is conducted over 100 different requests. These prepared requests had different duration and different start time. Figure 7 shows one of the cases. In this case, a user wish to start a trip from his hotel and visit some museums and shops during a 5 h tour started at 8 am, he would like to go a traditional restaurant after 1pm and stay 2 h there and then come back to his hotel. As depicted in Fig. 7, the solution uses all of the transportation modes. From hotel to subway station, he may use bus and walking, then use the subway and after getting off the subway, he walk to museums and then walk to a shopping center and walk to subway station and go the next station and walk to the restaurant. After it, he walk to subway station and go to the next station and come back to hotel by bus. Figure 7a shows the solution in dataset and Fig. 7b shows the tour with more concentration. The parameters of the genetic algorithm were: numpop = 100, Crate = 50%, 0.8 for crossover probability and 0.08 for mutation probability. These values are determined after sensitivity analysis of parameters. Different tests were conducted changing the values and the range in which the results had not meaningful differences.
The convergence curve of genetic algorithm is shown in Fig. 7c. As the convergence plot for selected case shows in the first few generations, there is a rapid increase of the fitness values. The curve also indicates that the process is converged. This behavior was observed with slight differences in all cases of evaluation.
In some of the cases, tour planning result in monomodal itinerary is the best alternative according to the requests and preferences of user. This shows that the proposed algorithm is robust which also could handle monomodal solutions.
Considering the obtained results from all cases of this experiment, it may be concluded that they show the efficiency and robustness of proposed algorithm.
CONCLUSION
In this study, the possibility of using genetic algorithm to solve the tour planning problem is investigated in which the routes between two POIs are parts of multimodal transportation network. The proposed algorithm has been tested on a dataset of a part of Tehran. Case studies were in the form of 100 different requests which had different duration and different start time. The results show the high performance and robustness of proposed algorithm.
Several topics remain for future research. In this research, the tour planning problem with just one criterion of time is solved, but in real cases, the tourists wish to have a tour according to several criteria such as cost and time. Modeling the delays which occurs during a tour due to delays of transportation services or extension of the visit of some points may lead the proposed algorithm towards more actual solutions.