Abstract: This study presents a new geospatial information system-based solution that assists people in trip planning to reach multiple destinations considering opening hours of points of interest and duration needed to perform multiple activities using multimodel public transportation media. People encounter with complexities in finding optimum paths in a multimodel public transportation system as they need to consider interactions of different modes of transportations in a more specific and constrained spatio-temporal structure. In this situation people’s context in the form of their activities diary becomes an important issue affecting trip planning and selecting mode of transportation. Activities diary constrains the spatio-temporal order of activities and enables us to study the effect of activities in transportation planning. In this study, the impact of activity diaries and spatio-temporal dimensions of activities in trip planning and optimum path findings are discussed. A new algorithm is proposed for planning itinerary considering network, time and duration constraints. The algorithm assumes that the activities are mandatory and the locations and duration of each activity are fixed. The travelers’ destinations, time and duration constraints provide the input of the algorithm. Using connectivity rules and policies, Dijkstra algorithm for finding the shortest paths is selected. The results determine the possible order of activities and their start and end time. The possible sequences of activities optimized based on minimizing waiting time during the activities i.e., time that person neither is doing an activity nor is traveling between activity locations and must wait till activity can be undertaken according to the time constraints. Finally, efficiency of the algorithm is determined according to the time complexity as a function of number of activity locations in the worst and normal cases. It has been proved that the time complexity of the algorithm depends on the third power of number of activity locations.
INTRODUCTION
This study presents a new geospatial information system-based solution that assists people in trip planning to reach multiple destinations considering opening hours of points of interest and duration needed to perform multiple activities using multimodel public transportation media. Decision making and planning to visit some locations in limited time is a problem that people encounter in different situations (Kolyaie et al., 2008c). In itinerary planning for performing daily activities, determining how and when to reach activity locations in an efficient way considering constraints of decision making is an important issue people are faced. Tourism is a typical application of this problem.
There are many situations that using a classic optimum path finding algorithm does not provide useful solution. For example in case, three places must be reached for performing activities, constrained shortest path problem is solved and routes passing through these locations by minimizing a cost function are determined. However time to reach the locations and duration to perform activities are not considered. For example, reaching an activity location may happen not at opening hours of the service.
| Fig. 1: | Daily itinerary components |
It is clear that reaching locations must occur in a time that performing activity is possible, for example opening hours of a museum or official hours of a bank or an office. It means reaching activity locations must be in a meaningful time which is a time constraint issue. An activity needs duration of time to be performed which can be fixed or dynamic. In computing the accessing time to an activity location, duration must be considered as reaching time plus time needed for performing the activity should not exceed the opening hours of the service intended, which is called duration constraint. Optimum path finding considering activities have some constraints such as sequential constraints. As an example, one has to get money from an ATM and then go to a restaurant to have lunch (Kolyaie et al., 2008a, b).
Daily activity program consists of going to one or a number of locations to perform the activities. Performing each activity needs time duration that results waiting in activity’s locations (Wang and Cheng, 2001). Therefore, daily itinerary includes number of activities that travel is necessary to reach given locations and stay there for performing the activities (Fig. 1).
All human activities have spatio-temporal dimensions (Miller, 2004). Conventionally, travel is considered a derived demand issue from the desire to engage in activities at certain locations (Bowman, 1998). Hence, considering activities for trip planning is an essential issue. Existence of a trip planning system considering activities helps people for optimum use of their time and money and also helps in understanding travel behavior (individual travel behavior includes route, mode and destination choices, travel frequency, activity scheduling and pre-travel decision making in an urban area (Krygsman, 2004) and daily activities that affect estimation of individual responses to policy measures and changes because of environmental constraints (Burns, 1979). In addition trip planning system can be implemented to encourage people to use public transportation media.
Information plays a significant role in the traveling decisions of individuals which has been investigated in several contexts (Vaughna et al., 1999) including route guidance (Bonsall et al., 1997), provision of transit information (Tan et al., 2004) and highway congestion and incident related information (Casas, 2003). Few researches have been reported on trip planning using public transportation system based on activities that consider time constraints which is the focus of this study. Travel itinerary planning which includes scheduling daily activities and travel, is a complex problem and it seems no analytical solution is reported so far. The matter may be viewed as a version of the Travel Salesman Problem (TSP) where a given number of destination locations have to be visited with a minimum travel cost. The problem of daily activity-travel scheduling is much more complicated than TSP because of considering more constraints (Vaughna et al., 1999) such as time (opening hour of each activity location), travel mode, time duration, activity sequencing and activity location.
In this study the impact of activity diaries and spatio-temporal dimensions of activities in trip planning and optimum path finding are discussed. The proposed algorithm can be used for planning itinerary, considering network, time and duration constraints. Using the proposed algorithm, it is possible that origin and final destination coincide that makes the situation more realistic because people usually stay in a place (for example: home, hotel) and leave it to perform multiple activities in different locations and finally back there.
The proposed algorithm assumes that activities are mandatory and the locations of each activity are fixed. The modes of transportation considered here are metro and walking. The algorithm is implemented as a TSP using Dijkstra algorithm for finding the shortest paths. The results determine the possible options including order of activities and their start and end time. The possible sequences of activities optimized based on minimizing the waiting time i.e., time that person neither is doing an activity nor is traveling between activity locations. Finally, efficiency of the algorithm is determined according to time complexity depending on number of activity locations in both the worst and normal cases.
MATERIALS AND METHODS
Here, basic components of the research are introduced. Hence, path finding on multimodel network and activity-based modeling are described. A sample data of Paris urban network has been used in the case study.
Path finding on multimodel networks: Urban transportation networks are increasingly characterized by traffic jam and its corresponding impact on individual accessibility, air pollution and the development of urban economic activities. Individual business and government search the ways to relieve congested roadways and to save travel time and minimize transportation conflicts (Lozano and Storchi, 2001). It is realized that travel demand would never be satisfied with new infrastructure development. Also, the oil crisis and economic recession in the early 1970s encouraged the improvement of public transport (Huang, 2003).
Multimodel transportation network is a system that uses different modes of transportation networks simultaneously to solve network analysis problems (Kolyaie et al., 2008a). Different modes in a multimodel transportation network are integrated as follow:
Multimodel transportation systems can be modeled using graphs adding new lines between nodes of different networks for definition of connectivity among them. Node in a multimodel network is a decision point where one must select either to keep on with the current mode or to change to another. A change of mode or modal transfer is represented by an arc called a transfer arc. In contrast, an arc connecting two nodes with the same travel mode is called a travel arc (Lozano and Storchi, 2001). These properties using graph theory are represented as follow (Lozano and Storchi, 2001):
Where: |
| G | = | A graph representing multimodel network |
| V | = | Vertices or nodes of G |
| E | = | Edges or arcs of G |
| mi | = | Modes of G |
There have been a number of researches on path finding in multimodel networks. For example, Fernandez et al. (1994) developed a path finding on bi-modal networks. Pallottino and Scutella (1997) used number of transfer as the attribute of shortest path. Battista et al. (1995) removed unviable paths using combinations of paths.
One of the main approaches to find reasonable optimum path on a multimodel network is specifying appropriate costs to different types of arcs and nodes (travel and transfer) and then using connectivity rules. Connectivity rules define constraints for finding optimum path. A path consists of consequence of edges that belong to the same connectivity group.
Activity-based modeling: Activity-based modeling is very useful for investigating, planning and feasibility study of travel patterns (Krygsman, 2004). Planning and feasibility study of travel patterns can be done under spatio-temporal constraints and opening hours for performing activities. Time geography investigates human activities in spatio-temporal dimensions as it determines when and where a person does his/her activities. Time-space path tracks a person in different locations in different times (Miller, 2004). In other words, according to activities that one must be engaged with in different possible locations, activity-based modeling helps in determination of where and when one must perform his/her activities to include mandatory activities and maximize number of optional activities (Miller, 2004).
Reaching time to each activity location and duration of the activity are needed to perform each activity just in opening time of the corresponding activity for example opening hours of a museum or official hours of a bank or an office. A sequential constraint means sequences of performing activities which can be pre-determined for some or all activities according to specific spatio-temporal constraints. Location and time to perform an activity can be hard or soft. The location of an activity is considered as hard, if it is the only place where the activity can take place. The location is considered as soft, if it is one of a set of alternative locations where the activity can be pursued (Vaughna et al., 1999). In the same way, activities with hard and soft time are defined. Activities itinerary can include optional and mandatory activities. An individual’s activity schedule is usually constrained by the mandatory activities (Wu and Miller, 2001). On the other hand, optional activities such as sport or shopping must happen between mandatory activities to maximize number of optional activities.
Time, duration and sequential constraints are temporal constraints of the travel. Location of activities and public transportation supply spatial constraints of the itinerary planning problem. These constraints can be considered using time geography and activity-based modeling.
In recent years, methods for analysis of travel behavior in spatio-temporal dimensions are necessary for Travel Demand Management (TDM) and Intelligent Transport System (ITS). Geo-spatial Information System (GIS) is very useful for management, analysis and visualization of spatial and temporal components of transportation systems and in trip patterns (Thill, 2000; Duker and Ton, 2001). Miller (1999), Kwan (1997) are among the researchers who used GIS to study travel activity patterns under spatial and temporal constraints. GIS has high capability for visualization, simulation and analysis of trip patterns in urban areas and transportation systems. 3D visualization of trip patterns in GIS environment increases the capabilities to study travel behaviour patterns investigated by Kwan (2003) and Ohmori et al. (2005).
Methods: The proposed algorithm for itinerary planning considering user constraints using public transportation network is described here. Activity-based modeling is used for planning the system. Activity-based modeling and space-time path are shown in Fig. 2.
3D GIS visualization capabilities are used to illustrate activity based modeling (Fig. 3).
The intended activities are classified first according to different dimensions. Different dimensions of an activity described in above are shown in Table 1. The activities are classified into 16 different classes according to their dimensions (Table 2). The algorithm supports activity class A, E, I and M determined in Table 2 according to user input i.e., if the opening hour of each location is equal to the duration time needed in that location, its time is considered as hard, otherwise it is considered as soft, in the same way sequences are determined.
The flowchart of the proposed algorithm for trip planning is shown in Fig. 4. Assumptions of the algorithm include: (1) activity locations are considered fixed and mandatory; (2) modes of transportation considered include metro and walking.
| Fig. 2: | Visualizing activity-based modeling |
| Fig. 3: | Visualizing activity-based modeling using GIS |
| Fig. 4: | Flowchart of the proposed algorithm for itinerary planning |
| Table 1: | Dimensions of activities considering available options |
| Table 2: | Classification of activities |
The overall algorithm has the following features:
| • | Allows activity destinations as user input |
| • | Considers time and duration constraints according to user input |
| • | Performs on a multimodel network |
| • | Multiple trip planning is managed |
| • | Waiting time minimization in each possible sequence is maintained |
| • | A number of possible options are provided to user with different start and end time and order of visits |
| Fig. 5: | Pseudo code of the itinerary planning |
Pseudo code of the algorithm for itinerary planning is presented in Fig. 5.
The proposed algorithm manages a number of possible options under brute force search solution for itinerary planning. In the proposed algorithm at first, all paths between each pair of locations are determined. Assume a person wants to leave home to go to n different locations and finally back home. In this situation, number of all routes is equal to:
It multiplies by 2 if route from location A to location B differs from that of from location B to location A. After determining routes, all sequences using permutation function are calculated. For visiting n locations, all sequences are equal to n!. This n! sequences are shown in Fig. 6.
| Fig. 6: | n! sequences for n = 3 |
| Fig. 7: | Pseudo code of Compute Arrival Departure Time function |
To reduce time complexity of the algorithm, no extra calculation is done in this part because of high complexity of permutation function and just sequences of names are created. Possibility of each sequence as well as departure and arrival time of each location in each possible sequence are calculated separately using Compute Arrival Departure Time function which its Pseudo code is presented in Fig. 7.
Time is continuous and as a result there are uncountable solutions for one status. To find reasonable solution an algorithm has been suggested as follow.
First for each sequence according to the first destination using its opening hours and considering time needed to move from home (origin) to the destination, start time of each sequence is determined. Then duration time of this activity is added and departure time of the location is calculated. Arrival time of the following activity is calculated according to the earlier activity’s departure time adding time necessary to move from the earlier activity location to this location and the same calculation for other activities will be undertaken. For each sequence if arrival time of each activity plus duration over the opening hour of each location are marked as an impossible sequence, they will be omitted from the next calculations. This method reduces time complexity of the algorithm.
| Fig. 8: | Pseudo code of Optimize Possible Sequences function |
In addition, if arrival time to each activity location be smaller than start time of opening hour of the activity location, the algorithm considers waiting time till the activity location commence. To minimize waiting time i.e., the time that a traveler neither performs activity nor travels between activity locations, optimize possible sequences function is used whose pseudo code is given in Fig. 8.
In optimize possible sequences function all possible sequences are checked in order to find locations that a traveler must wait till the location opens. For each possible sequence if it finds a location that its waiting time is greater than zero, its previous activity arrival and departure time will be checked. First the offset is assumed equal to waiting time and then earlier activity is checked according to end time of opening hour subtracted by its departure time. If this value is smaller than the offset, then offset is set as the smaller value. Finally, offset value will be added to start time of the sequence and arrival and departure time of the earlier activity locations and also to arrival time to the activity location and will be subtracted from waiting time of the location. This function is a shift according to the determined offset value with reference to the earlier part of space-time path of each sequence. Then the marker goes through the following activity and if it finds another location with non zero waiting time, the algorithm will be repeated and then checked for the next possible sequence.
New generation of simulators has been suggested based on new technological developments and further understanding of what people want and expect from their travel environment. According to Kwan (2006), these new systems should include at least some of the following characteristics:
| • | Consider decisions made under particular scenarios on a daily basis |
| • | Be able to adapt to people’s preferences |
| • | Be able to analyze a set of alternatives and make the best choice |
| • | Combine all/some of these characteristics resulting in a faster decision-making process with limited user interaction |
The proposed algorithm includes all of the above options.
RESULTS AND DISCUSSION
Here, first an example of itinerary planning results using the proposed algorithm is shows and then efficiency of the algorithm is discussed.
| Fig. 9: | Itinerary planning system interface (not to scale) |
| Fig. 10: | The user’s home and his/her activity locations (not to scale) |
User first introduce his/her home location and then specify his/her multiple activity locations and their opening hours and time durations. Figure 9 shows interface of the developed program in VBA of ArcGIS 9.2 software environment using ArcObject.
Figure 10 shows activity locations of the user on a map.
After determination of the activity locations and user’s home, the algorithm is executed whose output is shows in Fig. 11 in graphical and text formats.
As already mentioned, the overall concept of the proposed algorithm is TSP on a multimodel network under specific time constraints. No analytical solution seems to be reported for this problem so far. Since, the time dimension is continuous, there are infinitely a number of alternative solutions with trip and activity start time. The problem of travel itinerary planning is, in fact, extremely complex (Vaughna et al., 1999).
The number of activity locations visited in one day is limited. Therefore, a deterministic solution for TSP is used in this study, which is simply to generate all possible sequences, evaluate each and pick the best (Vaughna et al., 1999).
Fig. 11: |
Shows of routes and schedule (not to scale) |
As it is the only way that provides optimized solution. Heuristic methods such as genetic algorithm (Freisleben and Merz, 1996) and ant colony (Dorigo and Gambardella, 1997; Ying and Jianying, 2000) have been used to solve TSP. These methods provide quasi-optimize solution that prefers more efficiency in contrast to the best solution. For n greater than 15, it is suggested to use a heuristic solution. However, it is clear that they do not provide the optimized solution.
Time complexity of the proposed algorithm depends on the number of the activity locations and user’s time constraints. In normal situations, activity locations have different opening hours and impose time constraints, therefore, number of possible sequences is smaller than number of all sequences that reduce time complexity of the algorithm. However, in the worst case i.e., when all the sequences are possible, time complexity of the algorithm is increased. Therefore, time complexity of the algorithm depends on constraints of the inputs. Different time constraints (i.e., opening hours and duration) have been tested to encounter with the worst and norm cases and also for different values of n (i.e., number of activity locations). To simulate the worst case situation, same opening hours of all locations are considered (from 8:00 am till 8:00 pm). For normal case, common time for different activity types are used, for example official hours of a bank or opening hour for a coffee shop.
The algorithm is executed for both the worst and norm situations for different values of n (from 2 to 7) to determine the overall trend of increasing time complexity of the algorithm according to the increase of n.
| Table 3: | Time complexity of the algorithm in both the worst and norm cases for different value of n |
The results are elaborated in Table 3 in which it is clear that with increasing of n, time complexity of the algorithm increases too and also difference between the worst and norm cases becomes more significant.
For determination of the overall trend of time complexity of the algorithm, different functions such as polynomial (degree 1, 2 and 3), power and exponential functions were tested to fit to this value. For investigating the trend of the corresponding value, R-square (Eq. 1) and J (Eq. 2) values are calculated.
The best fitted curve is selected where, J is minimum. R-squared value is a number between 0 and 1 that reveals how closely the estimated values for the trend line corresponds to the actual data. A trend line is most reliable when its R-squared value is 1 or near 1. R-squared is also known as the coefficient of determination. Table 4 and 5 are summary of results to find the most fitted trend.
| Table 4: | Equations used to find the most fitted trend for the norm case (y is t and x is number of activity location) |
| Table 5: | Equations used to find the most fitted trend for the worst case (y is t and x is number of activity location) |
| Fig. 12: | Time complexity of the algorithm fitted to polynomial degree 3 |
(1) |
(2) |
| Where: |
| Y | = | Observed T |
| Ŷ | = | Estimated T |
| n | = | No. of observation |
According to the J and R-squared values achieved the third power of polynomial function is the best fit for the trend of increasing time complexity achieved from the proposed algorithm depending on the number of activity locations (n) (Fig. 12). This function results in the minimum value for J and its corresponding R-squared is near 1.
CONCLUSIONS
There is a need to explore ways to encourage people to use transit and share ride system to reduce traffic congestion and air pollution. One approach is to develop system that help people in path finding and itinerary planning using multimodel networks. Travel itinerary planning system is necessary, not just for one trip, but also for all travels for performing daily activities. The system should consider time constraints of user and activity locations. It is useful for users, in planning daily itinerary by arranging the sequence of stops, suggesting stop locations and routes and providing schedule information.
In this study an algorithm is proposed and successfully tested for planning itinerary considering network and time constraints of users and activity locations. The proposed algorithm assumes that activities are mandatory and the locations of each activity are fixed. The travelers’ destinations, time and duration constraints provide the user input of the algorithm. The algorithm is implemented as a type of TSP using constrained Dijkstra algorithm for finding the shortest paths on the multimodel network. The results determine the possible options with different orders on activities and their start and end time. The possible sequences of activities optimized based on minimizing waiting time defined, time that a person neither undertake an activity nor travel between activity locations. Finally, efficiency of the algorithm is determined according to the time complexity based on the number of activity locations in the worst and normal cases. Time complexity of the algorithm depends on the third power of the number of activity locations.
This study presents the results of an ongoing research on activity-based itinerary planning on multimodel networks. We tend to develop systems which support solutions for daily queries on multimodel networks. We are currently working on extension of the proposed approach to include soft destinations and maximize optional activities. The system can be further developed to include buses and taxis.