In recent years the structure of transportation networks has become more complex as a result of the fast development of the social and economical infrastructure. When dealing with time dependent multimodal context, transport planning represents a fundamental problem and more specifically for hazardous materials. Several approaches have been proposed that strive to reduce the financial costs, travel time and vehicle operating costs. Our work tends to focus on potential improvements related to resolve the shortest path problem. This paper handles the design and implementation issues of our monolithic approach solving the time dependent multimodal transportation problem aimed at calculating the shortest path from a source node to a destination node. The algorithm on which relies our approach is target oriented and focuses basically on the reduction of the search space by considering a virtual path from the source to the destination as well as a user defined constraint defining a dynamically extendable corridor-like restricted search zone that can be applied on either the Euclidian distance or the travel cost function . The specification details of the algorithm have been already presented in our previous work and will be out the scope of this paper. Especially, this work highlights the aspects related to the different dimensions of the search space, namely the time, the mode and the constraint parameter.
Travelers are often faced to a common route planning problem known in the public transport system as the scheduling decision. It involves the use of different public transport means. The complexity relates in general to the specific schedule of each transport service, the connectivity level of the nodes defining the public transport network and the density of this later. This problem is formulated as the determination of the shortest path between the source and the destination regarding the traveler preferences in terms of travel costs and the transport infrastructure requirements.
A transport network is called multimodal when at least two different means of transport are required to perform a travel between a source and a destination. To find the optimal route manually is not an easy task regarding the constraints mentioned above that’s why there is a need to compute the shortest path in a dynamic environment. 2
Several optimizations approaches have been proposed to improve the calculation of
the shortest path in a time dependent multimodal transport network varying from
classical solution relying on speed up techniques Bast et al. [
In this paper, we will focus on the design and implementation aspects based
specifically on our previous work that expresses a constraint based shortest path algorithm
in a time dependent multimodal context Idri et al. [
In the following, a transport network is considered as a direct graph and is denoted as G = (V, E, M, T), where V = {v1,…,vk} is a set of vertices, E = {e1,…,em} is a set of edges, M = {m1,…,mk} is a set of modes and T = {t1,…,tn} is a set of travels. Each travel tj is represented with a couple (tjd, tja) specifying the departure and the arrival time. In a time-dependent multimodal context, an edge el can be defined as a tuple (vi, vj, mk) expressing that there is a connection between node ei and node ej using mode mk. To highlight time-dependency, an edge is mapped to a timetable that is defined as a set of travels involving all the possibilities of traveling from node ei to node ej using mode mk. This defines a cost function that is applied to the edge el at instant t Cel(t). Note that multiple modes can be applied to the same edge. A path is then a set of connected edges from the start node to the target node P = {es ,…, et }.
a e e c c b g a b g
A sample transport network is given in Table 1. This network contains two modes and a set of edges related to their timetables and cost function which is considered as the travel time in our case. But it can represent the financial cost as well, or any other preferred variable and the same rules remain valid. Whenever we need to demonstrate specific aspects, we will refer to this sample network. 4
This section describes formally our approach by specifying the algorithm and its input parameters.
Figure 1 shows a recursive version of the constraint based shortest path algorithm
(CBSPA) as introduced in our previous work [
Output: shortest path // (VsVt): virtual path which is calculated based on the coordinates (Euclidean case: straight line between Vs and Vt) or the minimal/mean value of the cost function (in our case, the travel time) // Q: the set of the neighbors of u satisfying the constraint control, a parameter needed to forward the intermediate results // t: start time; u: start node // = 1 ,
: represents the mean distance(cost) from all nodes to the virtual path // Dmax: represent the maximum value of d, that’s the distance (cost) to the farthest node of the network
If u = Vt then
Return path Else
In if Q = Ø then
Let Q = {v ∈ Neighbors(u)/ dist(v,(VsVt)) ≤ d} 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Else Else
Let w = predecessor(u) in
Let Qnew =
⋲ ( , ) in Let Q = {v ∈ Qnew/dist(v,(VsVt))<d} in ∀ v ∈ Q, CBSPA(v,d,path ∪ {v},Q\{v},t) search dimensions expressed in terms of abstraction layers. It also handles the building process of the complete solution as well as that of the shortest path. 5.1
Global view
The search process is target oriented and is driven by three dimensions: the mode, the time and the user-defined constraint d. Each time we explore the possibilities of a given edge eij connecting the nodes vi and vj, we deal in fact with a three dimensional search space as illustrated in Figure 2.
Vi eij mode
Vj
time 100 80 60 40 20 emk,tk,dk d fs(m,t,d)
Est Ouest Nord verified c0riteria 1er 2e triemm.13,et1,dtr1im.4e tri…m. trim. Partial solution emk,tk,dk …
The function fs generates instances of the edge eij from which some will belong the partial solution. Note that at the end of the search process, as the constraint d is increased gradually during the search process, the last reached value will be taken into account and will substitute the intermediate values seen that it is the upper bound value of the verified constraints.
Remark . Some criteria might be applied regarding one or more dimensions like a mode is only available up to a departure time t. 5.2
Time dependency layer
In a time dependent context, each edge is assigned a timetable indicating the different departure and arrival times relatively to this edge. An edge scenario which is a departure-arrival case derived from the timetable, can be considered then as an instance of the original edge. Therefore, we will obtain at the end a set of edge instances equivalent to the set of the possible edge scenarios. Following this description, if an edge may be viewed as an abstraction, then to process it in this search space, we have to handle each one of its instances but then for every single mode and constraint as shown in Figure 3-(a).
Vi eij 100 80 Vi 60 40 20 100 80 60 100 80 60 40 20 0 em , t1 , d em , tk , d em1 , t , d emk , t , d
(a) Est Ouest
No(rbd) 1er 2e trim.3e trim.4e trim. trim. em , t , d1 Est
Ouest em , t , dk Nord (c) 0 Est
1er 24e0trim.3e trim.4e trim. Ouest Fig. 3. Seartrcihml.ayers: (a) time layer (b) multimodality layer (Nc)orcdonstraint layer 20 0 5.3 Multimodality layer1er 2e trim.3e trim.4e trim.
trim.
The same way, a mode is considered as an abstraction having a set of instances represented by the different modes connecting the start and the end nodes of the edge, see Figure 3-(b). 5.4
Constraint layer
As for the constraint d (Figure 3-(c)), its instances are generated following the needs of the search process and the size of instances set is unknown in advance. 5.5
Global solution
The current version of our algorithm returns as result the first found shortest path if it exists. One can easily alter this algorithm to include all possible shortest paths. The complete search space based on the above reasoning is nothing more than the combinatorial superposition of the three mentioned layers. 5.6
Building process of the complete solution
The search process targets the first available solution and that’s why we adopted in our algorithm the DFS technique (Depth First Search) which relies on the partial/complete solution approach: the solution is build up progressively from its components mentioned above. Each element is defined by a three dimension edge instance emi, ti , di as seen before. Figure 4 describes the building process as the algorithm explores the search space.
Vj 100 80 60 40 20 0 1er 2e trim.3e trim.4e t trim.
Step k+1 em1, t1 , d1 em2, t2 , d2 ….. emi, ti , di emi+1, ti+1 , di+1 em1, t1 , d1 ….. emi, ti , di emi+1, ti+1 , di+1
To implement this concept, we used a backtracking mechanism, but then we were faced to the optimization process while reducing the search space by the elimination of the visited edge instances in a search scenario.
Again, to mark and unmark an edge instance is an action that has to be performed in the three dimensional space and this is a complex task: a visited edge means in our context a visited three dimensional instance issued from the combined layers described earlier. It is clear that in neither way a whole physical edge can be marked as visited or unvisited like in the classical approach. This leads us to assign the management of this optimization issue to a whole software component accordingly to the backtracking search process. 5.7
Building the shortest path
The building process of the solution is based on the partial/complete solution technique that needs a container. In our context it is simply a temporary queue that is build up of solution component similarly to an edge instance satisfying the search criteria: the departure time, the available mode and the constraint d. Such an instance is pushed in the queue to be handled following the algorithm logic. The next iteration, the edge instance at the top of the BFS queue is substituted with its successors verifying the search criteria.
The search process stops when it reaches the end node or when all possibilities are tried out. If a solution is found, it is stored in the temporary queue with some residues edge instances that couldn’t be tried out because we are interested in the first found solution. To build up the shortest path we need to reconstruct the path backward starting with the end edge instance. Then the next predecessor is the instance edge having as end node the start node of the end edge instance and an arrival time less or equal to the departure time of the end edge instance and so forth until the start edge instance is reached. Overall, it should be noted that during this process the global cost of the shortest path can be calculated by totaling its elementary edge costs.
In this section, a class diagram is given to show how the solution can be implemented based on the concepts introduced earlier.
This model supports either classical multimodal transport graphs based on the Euclidian distance (MMG) or time-dependent multimodal graphs that manipulate timetables (TDMMG). In this context, we are using the second model. The time dimension is captured within the Travel class and a path is modeled as a list of PathElement which is composed of travel (dimension time), mode and Edge (or TDEdge). The virtual path class VPath serves as a reference container of virtual paths.
This section explains the whole process from the specification step to the generation of the shortest path by mean of an example based on the same data given in Table 1.
From the point of view of the concepts handled in the previous sections, we will focus on the performance of our implementation techniques instead of presenting the profiling and the benchmarking related to the business aspects of the approach which were evaluated in our previous work for both the monolithic and the distributed versions. We adopted in this experimentation a cost function defined as travel time and we measured then the behavior of the constraint fluctuation in terms of the necessary iteration to converge to a solution. Also we give hereafter in Figure 6 a result model based on the example of Table 1 to show how we performed our tests. We calculate the proper travel cost and the waiting delay is ignored in these tests. The label “Final D” is the final value of the constraint reached to find the shortest path. In our implementation, the nodes are expressed in numbers respecting in this example the alphabetical order: node A has number 1 and so forth.
Path to find :[ [ Node id: 1 ]======>[ Node id: 2 ] ] [ [ start node: [ Node id: 1 ]] [ end node: [ Node id: 5 ]] [ travel : 1 ===> 3 ===> 2] [ mode : 1] [ start node: [ Node id: 5 ]] [ end node: [ Node id: 3 ]] [ travel : 3 ===> 5 ===> 1] [ mode : 1] [ start node: [ Node id: 3 ]] [ end node: [ Node id: 2 ]] [ travel : 6 ===> 8 ===> 5] [ mode : 1] [ Total cost : 8] ] time :0 s
Final D: 10
Figure 7 shows how the search process behaves regarding the constraint parameter d and the network density expressed in the total nodes number. The final constraint value reached within a search process reflects the iteration number performed to achieve the next node. It is clear that the iteration number refers to the level of the search space reduction. That’s, as long as the maximal value of the constraint parame
AMI Routerter is not reached; this means the search space is restricted accordingly to the number of iterations. Figure 7 shows also that there is an impact of the network size on the iteration number at least with the samples used in these tests.
Our approach to deal with large scale networks is based on parallel distributed architecture that relies on a Manager/Agent model. This model fits well with our needs as it is scalable and each agent runs in an independent way (parallel). Multiple agents cooperate to deliver partial solutions which are gathered by the manager that builds up the complete solution. Figure 8 exposes a distributed architecture relying on a CORBA framework as it offers object-oriented facilities and distributed event management that supports Asynchronous Method Invocation (AMI). A model based on
Dispatcher
Collector Manager Communicati on Manager
AMI Router Agent 1
Agent i
Agent n
Fig. 8. CORBA Architecture
Each agent is assigned the task to compute elementary paths starting from a given intermediate node Vi (initially the start node). These paths are represented by the set of the next nodes directly connected to Vi and satisfying the algorithm constraints. The manager is responsible for dispatching the tasks, collecting the elementary results, building the complete solution as well as covering the communication issues with the agents. 9
In this paper we treated some design and implementation aspects regarding our approach dealing with the time-dependant multimodal transport problem expressed as finding the shortest path algorithm. Especially, we focused on the design techniques to solve the problem in the context of the different search dimensions including the user defined constraint that influences the search process and the final results. To address the big data issue in this context, we adopted a parallel distributed architecture that guarantees the scalability and improves the performance of the algorithm.
We intend in our future work to investigate deeply the behavior of existing algorithms when embedding this approach within these algorithms in a parallel distributed architecture.