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
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.
|| 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 activitys 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.
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,
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):
||A graph representing multimodel network
||Vertices or nodes of G
||Edges or arcs of G
||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 individuals 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
|| Visualizing activity-based modeling
|| Visualizing activity-based modeling using GIS
||Flowchart of the proposed algorithm for itinerary planning
||Dimensions of activities considering available options
|| 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
|| Pseudo code of the itinerary planning
Pseudo code of the algorithm for itinerary planning is presented in Fig.
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.
|| n! sequences for n = 3
||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 activitys 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.
|| 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
||Be able to adapt to peoples 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.
||Itinerary planning system interface (not to scale)
||The users 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 users 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).
| 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 users 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.
||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.
|| Equations used to find the most fitted trend for the norm
case (y is t and x is number of activity location)
||Equations used to find the most fitted trend for the worst
case (y is t and x is number of activity location)
||Time complexity of the algorithm fitted to polynomial degree 3
||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.
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.