Abstract: This study presents the investigations on the application of genetic algorithms to solve multimodal shortest path problem. To evaluate the efficiency and robustness of proposed method, the algorithm was carried out over 250 randomly selected pairs of origin and destination points with different distances and number of nodes. It was assumed that three modes of walking, bus and subway are used to travel between points. The classification of results in three main classes of monomodal, bimodal and multimodal paths shows that more than 65% of paths are multimodal. These results show the robustness of proposed model. It is also concluded that these experimental outcomes validate the effectiveness of evolutionary methodology to solve the problem.
INTRODUCTION
Multimodal shortest path problem concerns with finding a path from a specific origin to a specific destination in a given multimodal network while minimizing the total cost associated with the path (Deo and Pang, 1984). Despite a monomodal transportation network, a multimodal network comprises combinations of several services and modes of transportation such as taxi, subway, bus and walking which operate concurrently under the changing conditions (Fig. 1). Associated travel time and cost of each arc change with time in these networks and using them requires information about timetables of transportation means (Kaufmann and Smith, 1993; Ziliaskopoulos and Wardell, 2000). Thus, it is necessary to have start time of travel to solve the problem. The main motivations to solve this problem are emerging requirements for routing in Intelligent Transportation Systems (ITS), urban trip planning and route advisory systems (Aifadopoulou et al., 2007; Barrett et al., 2002; Bérubé et al., 2006; Feillet et al., 2004; Kramer et al., 2006; Souffriau et al., 2008; Vansteenwegen and Oudheusden, 2007).
There have been different researches on computing multimodal shortest path. A considerable portion is about finding solutions for static multimodal shortest path problem (Crainic and Rousseau, 1986; Spiess and Florian, 1989; Modesti and Sciomachen, 1998; Nguyen et al., 2001).
| Fig. 1: | A path in (a) monomodal network and (b) multimodal network |
Most of these algorithms approximate waiting time of transfer according to headway or using generating of artificial waiting time arcs. But, recent researches have changed the direction towards working on dynamic solutions (Pallottino and Scutellà, 1998; Ziliaskopoulos and Wardell, 2000; Abdelghany and Mahmassani, 2001; Lozano and Storchi, 2001, 2002; Chang et al., 2007; Bielli et al., 2006; Ayed et al., 2008; Qu and Chen, 2008).
In addition to these researches, some practical systems have been developed mostly in the form of path planners to find multimodal shortest paths for users. Among these systems, we may refer to EasyGo (Pun-Cheng et al., 2007), RADS (Meng et al., 1999), EasyTransport (Fragouli and Delis, 2005; BayernInfo, 2009; JPL, 2009; SCOTTY, 2009).
The major weakness of these researches is that they were not carried out on real dataset of any metropolises that include complex transportation networks. In these cities, search spaces are too large and highly complex. Thus, the problem will be too complex to be solved by traditional methods and efficient optimization strategies are required that are able to deal with this difficulty.
A novel formulation and evolutionary-based solution is proposed in this study to compute single-objective shortest path on multimodal networks taking both travel and switching time into account. It was assumed that the multimodal network consists of three modes of walking, bus and subway and also the arcs of network have time-dependent weights.
PROPOSED FORMULATION
In contrast with finding monomodal paths, computing the shortest multimodal path may encounter some difficulties. The algorithm should take all service lines and transportation modes passing one station into account according to their temporal schedules. Furthermore, it is necessary to model the waiting time when the services/modes are changed (Fig. 2).
| Fig. 2: | A multimodal network |
Let the multimodal transportation network be assumed as a weighted directed graph of G = (N, A) where N is the set of nodes and A represents the set of arcs. In classic representation of a graph, nodes are often the junctions of network arcs, but in this modeling, these points are the stops of transportation services (i.e., subway stations and bus stops) as well as origin and destination points. Thus, the arcs are the paths between two successive nodes. Since, three modes of bus, subway and walking are considered in this article, a weight vector of wij≥(wijb,wijs,wijw) is associated to arc (i,j) where wijb≥0, wijs≥0 and wijw≥0 show the weights of bus, subway and walking modes for this arc, respectively. The weights reflect the time duration taken to travel between two nodes. The values of wijw depend on contextual information of user such as age and health situation, while wijb and wijs are functions of time. They are calculated using information of timetables of service lines. When the origin or destination point is not one of the stops, they are dynamically assumed as nodes and the connecting arc of these nodes to nearest stations is assigned walking weight.
The differences between modeling of monomodal and multimodal path are illustrated through an example. As depicted in Fig. 3, it is assumed that there are three service lines and some bus stops. Each service line, SLi, is represented by the sequence of stops. For example, SL3 = (…, 301, 102, 103, 202, 203, 401,…) shows the service line with ID number of 3 passing through the mentioned stations. Each line has a departure timetable and it is possible to build a timetable for each of the stations according to the temporal distance of precedent stations and line number. If the non-temporal monomodal path from O to D is represented by Path (O,D) = (O,101,102,103,202,203,204,205,D), then this sequence may coincide with different multimodal paths such as the following list:
| Fig. 3: | Sample service lines in a multimodal network |
| • | Walking from O to S101, waiting for the bus at S101, going up to S103 by SL1, walking from S103 to S202, waiting for the bus at S202, going by SL3 up to S205 and finally walking to D |
| • | Walking from O to S101, waiting for the bus at S101, going up to S102 by SL1, waiting to change the bus, going by SL2 up to S203, again waiting to change the bus, then going by SL3 up to S205 and finally walking to D |
| • | Walking from O to S102, waiting for the bus at S102, going up to S203 by SL2, waiting to change the bus, going by SL3 up to S205 and finally walking to D |
| • | Obviously, these paths may have different corresponding total cost |
The cost of each multimodal path consists of two main parts of traveling and waiting time. Travelling time shows the duration of travelling and waiting time represents the periods when someone changes the service line(s) of transportation. Consequently, the objective function of finding a multimodal shortest path between an origin (O) and a destination (D) consists of two general parts of minimizing the weights of used arcs (first summations) and minimizing the waiting time (second summation) when the modes are changed (Eq. 1).
(1) |
In this optimization function, xij is a binary variable associated
to each arc connecting two nodes and equal to 1 if and only if the corresponding
arc is used in the solution.
PROPOSED SOLUTION
A solution based on an evolutionary algorithm is proposed to compute the multimodal shortest path in this study. The evolutionary algorithm is a class of optimization methods that simulate the process of natural evolution (Zitzler, 1999). Evolutionary computing comprises Genetic Algorithm (GA), genetic programming, evolutionary programming, evolutionary strategy and classifier systems (Bäck et al., 1997). This algorithm is also a member of a group of methods, known as meta-heuristics. This set of techniques includes simulated annealing method, tabu search method, ant colony algorithm, bee algorithm, particle swarm optimization, artificial immune systems and distributed reinforcement learning. They have been proposed to solve the difficult possible optimization problems (Dreo et al., 2006).
Genetic Algorithm is different from the other mentioned meta-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.
The engine of proposed genetic algorithm to find the shortest multimodal path works in 5 steps. Coding of chromosomes is the first step. Since, the numbers of nodes for a path are not predefined in this problem, the chromosome with variable length is used to show a path in the network. The values of odd genes show the labels (IDs) of nodes. The values of even genes represent transportation modes between two successive nodes where number 1 and service line IDs are used for walking and the other modes, respectively. The position of a node represents the order of that node in a path. Figure 4 shows an example of encoding. The randomly generated genes (nodes) are appended sequentially to construct a chromosome (path). When the population reached the population size (numpop), the cost of each chromosome is calculated. Velocity of user, which actually depends on the context of the user, is assumed an average amount of 4 km h-1.
In the next step, i.e., natural selection, half of the best chromosomes (numkeep) are selected from a sorted list of chromosomes to form the mating pool. Afterwards, two chromosomes are selected from mating pool according to roulette wheel paring method in the third step to produce two new offspring.
The mating is the fourth step, in which offspring are created from parents selected in the previous step.
| Fig. 4: | An example of a path and related encoded chromosome |
| Fig. 5: | (a) Single-point crossover and (b) versus two-point crossover |
A combination of both single-point and two-point crossover is used in this study. When two chromosomes are selected from mating pool, they are compared with each other. They should have at least one common gene except for origin and destination. It is not necessary the location of common genes in two chromosomes be the same. If there is exactly one common odd gene in both of them, then single-point crossover is applied. In this type of crossover, the genes following common genes are swapped (Fig. 5a). If there is more than one common odd gene in selected chromosome, two of them are selected randomly and the two-point crossover is performed. In this type, the genes of two chromosomes, which are between two common genes, are swapped (Fig. 5b). The procedure continues until numpop-numkeep offspring are born to replace the discarded chromosomes. Furthermore, elitism strategy is also adopted and two chromosomes are kept as elite ones in iterations.
Since, a chromosome shows a path as the sequences of stations and connecting transportation modes, changing the value of any genes may made the chromosome to be ineligible due to emersion of loops. To cope with this issue, a rectification procedure was utilized to eliminate the loops to ensure that newly generated chromosomes are valid paths. This procedure removes genes between the same genes to rebuild a valid path (Fig. 6).
To keep away from local optimal solutions and keep the algorithm converging fast before sampling the entire cost surface, the random mutation is used in the next step.
| Fig. 6: | Implementation of rectification procedure to eliminate loops |
In proposed solution, the mutation is applied only to odd genes. The even genes (transportation modes) are modified according to odd genes. Since, changing the value of a gene in a chromosome may make it to be ineligible as a path, the modification procedure is also applied after mutation. This procedure includes two modules namely loop removal and validation and works in three steps. In the first step, existing of any loops in the path is checked and if there are any loops, they are eliminated. Afterwards, the validity of sequences of genes as a path is evaluated. Wherever there are gaps between successive nodes, some valid genes are added between to reform the path. Finally, the loop removal module is applied again.
It is noticeable that both crossovers and mutations are used with a probability level. The costs associated with offspring and mutated chromosomes are once again computed and assigned.
The whole process, i.e., step 2 to 5, is iterated until the temporal differences between twenty best cost paths reach zero in successive iterations. However, if the algorithm does not stop according to specified criterion, the process is set to terminate after 500 iterations.
RESULTS
The proposed framework and formulation are evaluated through conduction of some experimental tests over the data of a part of Tehran. Tehran is one of the metropolises of Iran that has an extent of about 700 km2 and comprises 22 districts. Public transportation employs five main modes that are taxi, van, minibus, bus and subway in this city. Among them subway, due to its high speed and bus, due to its extensive coverage, is of more interest for travelers and commuters. Table 1 shows some statistics of these two modes.
As shown in Fig. 7, the data set consists of pathways (i.e., streets, avenues and highways used by buses) and subway system (consists of lines and stations). The data set is prepared as it should be, i.e., the topologic structure is rebuilt and required tables are created.
To evaluate the multimodal shortest path algorithm, 500 points (in the form of 250 pairs of sources and destinations) with different number of nodes and start time were selected. They were used as the input origin and destination of algorithm. Some of these pairs are shown in Fig. 8, where lighter labels show origins and darker labels illustrate destinations. According to this Fig. 8, the distance and distribution of endpoints of paths are diverse.
The proposed algorithm starts with generating of a large population of chromosomes as the initial population. For initial population it is inferred that numipop = 250 is a good choice. Then, the cost of each chromosome is calculated based on fitness (objective) function and chromosomes are sorted in descending order according to the assigned cost. In the next step, numikeep = numpop = 100 best chromosomes, which had lower costs, are kept for next iteration and the others were discarded. It is realized that numpop = 100 is a suitable value according to persent experience.
| Table 1: | Information about bus and subway transportation networks in Tehran |
| Fig. 7: | Dataset used for evaluation |
| Fig. 8: | Some of origin (light labels) and destination points (dark labels) |
In the next iterations, Crate = 50% is selected. The next steps were natural selection, mutation and checking termination criteria. Due to stochastic nature of algorithm, 30 runs are conducted for each pairs of endpoints and the best value of each set is selected as the representative that shows the shortest multimodal path between those two points.
The classification of results in three classes of monomodal, bimodal and multimodal paths shows that more than 65% of paths are multimodal (Fig. 9). These results also show that the multimodal shortest path, i.e., combination of modes to travel, is not the optimum one in all cases.
The result for one of the case studies is illustrated in Fig. 10. The path of this case consists of a combination of all three modes.
The convergence curve, which shows the cost of minimum cost path as the function of iterations, is adopted to represent how the results of iterations for this case are.
| Fig. 9: | The diversity of resulted paths according to used models |
As the convergence plot for selected case shows (Fig. 11), there is a rapid decrease of the fitness values in the first few generations. The curve also indicates that the process is converged. This behavior is observed in all cases of evaluation.
| Fig. 10: | The result of one of the cases |
| Fig. 11: | Convergence plot for presented case |
To measure the quality of proposed method, the failure ratio (Ahn and Ramakrishna, 2002) is utilized. This ratio shows the times that GA fails to find the global optimum in respect of whole runs. This index is calculated for each of 250 paths and shows the frequency of paths which fails to be optimum among 30 runs for each of the cases. Figure 12 shows this ratio for evaluated data set. The horizontal axis of this diagram shows the number of failed runs in 30 runs and vertical axis illustrates the frequency of number of failures among all cases. It was perceived that average failure ratio of proposed path finding algorithm is about 2.77. Therefore, the quality of solution and path optimality is bout 90.75%.
| Fig. 12: | Failure ratio of calculated paths |
DISCUSSION
The proposed algorithm was tested over 250 different cases with start time, origin and destination. The results indicated that the numbers of iterations in genetic algorithm increase as the distance between endpoints increases. The number of iterations for each problem was between 50 and 220. The comparison of results also highlighted that in the completely similar conditions when the start time changed, the paths changed. This behavior supports the time-dependent nature of shortest multimodal problem.
In some cases, the paths were compositions of two modes of bus and walking even in the area where there were subway. The best path used just walking in some cases. These were evidences to robustness of proposed algorithm.
In all of the evaluated cases, the convergence plots have similar behavior. They show considerable fall during the first iterations and then decrease slightly up to the iterations where the plots remain stable.
The high average amount of success rate of algorithm shows the high performance of proposed algorithm.
Existing researches generally presented a special case study rather than a general method. On the other hand, the commercial route advisory systems do not consider the temporal nature of problem. This study proposes a novel metaheuristic approach based on genetic algorithm to solve the time-dependent multimodal shortest path problem. In contrast with other researches, it could be extended to include other modes and big search area such as metropolises due to the high capabilities of proposed method. The other distinction between this method and existing systems and approaches is consideration of contextual elements such as user profile and on-line congestion information.
CONCLUSION
In this study, the possibility of using genetic algorithm to solve time-dependent shortest path problem in urban multimodal transportation networks is investigated. The proposed approach has been tested on a dataset of a part of Tehran City. To evaluate the algorithm, 250 pairs of points were selected randomly as the source and destination. The results may be divided into three main groups where path consists of one, two, or three modes of transportation. These show that the paths with combinations of all three modes are not essentially the shortest one in all cases. Thus, that proposed algorithm has high degree of robustness that enables it to cover monomodal solutions as the special case of multimodal paths. Moreover, it may be concluded that proposed algorithm can efficiently explore the search space to find the shortest multimodal path. Several topics remain for future research. Since some of the decisions made by citizens to select their way to transport between two points are not just the function of time, thus extension of our proposed algorithm to address the multi-criteria path-finding problem is important. The second activity may be consideration of real-time implementation of our algorithm that in turn needs some modifications to improve the speed and management of on-line input parameters. To develop a useful and practical path-finding module for a user, considering his/her contextual information is critical. These parameters may let the selected path adapt the user situations as much as possible.