# Time Dependant Routing In Dynamic Transportation Networks Computer Science Essay

**Published:** **Last Edited:**

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

In dynamic transportation network, cost of the link from one node to another node will vary with time. If we assume road network is stored as a large graph with the traffic information in a database then travel time for a given source vs to given destination ve varies with time. At starting time T1, the travel time is Ï„1 from vs to ve .At starting time T2, the travel time is Ï„2 from vs to ve .The values of Ï„1 and Ï„2 is different if T1 â‰ T2. As mentioned in below figure 1, the link travel time from one node to another node changes throughout the day.

For road network the link between source and destination will always be there but travel time varies with time. The travel time on this link will be more for morning and evening peak hours and less for off peak hours. In public transportation the link itself will not exists throughout the whole day. For example for railway network, if you reach to the railway station just before the train departures then waiting time will be less before actual travel time starts. If passenger has missed the train or reach the rail station quite early then the waiting time for train will be more and that will increase total travel time which is actual travel time in train + train waiting time. Same thing applies if passenger using bus transportation or flight transportation. Even some times particular train facilities are not available after certain time of the day, so cost of the travelling from one node to another node depends on waiting time, transportation available or not, traffic over the road, etc.

To count travelling cost from one node to another node we have to consider few factors .Those factors depends on starting time of travel. This situation results new family of shortest path problem or dynamic shortest paths problem.

Finding the shortest path in time dependent network is to find a minimum travel time path from a source to a destination over a time dependent graph for a given starting time.

The rest of the report is organized as follow.

Section II covers graph presentation. Section III is for shortest path algorithms for time independent networks. Section IV is modeling time dependent network. Section V algorithms for time dependent network and section VI is optimization of time dependent routing algorithms.

## GRAPH REPRESENTATION

## Graph:

Graph is made of nodes/vertices and edges/links. All the nodes in graph connect to one or more nodes by edges. Graph G can be represented by G = (V,E) where V is finite set of nodes/vertices and E is finite set of edges. E V x V. The edge between two nodes i.e. Ï… and Î½ is only possible if Î½ and Ï… Ð„ V. The edge is loop if edge e =( Î½, Î½). Backward graph can be obtained by flipping the graph [1].

A directed edge from u to v will be denoted by (u, v) and an undirected edge between u and v will be referred as {u, v}. For a directed edge (u, v), u the tail node and v the head node.

## Adjacency list:

An adjacency list of a node u will refer to the set of all edges occurrence to node u. d(s, t) is refer to the distance between the node s and t in graph G.

## Weights on edges:

Each edge of graph is represented by function and value of this function is called weight of the edge. In time dependent graph, weight of this edge will dependant on time.

The weight edge in time independent graph is constant it will not vary with time whereas for time dependent graph, edge weight will vary with time. For the road network travel time required from one place to another place depends on the peak hours, so value of weight function will vary with time. Train services are not available throughout the day. Train schedule always follow the train timetable. For a given time slot in a day the particular train service will not be available so weight for the edges which is connected from train T1 to train T2 is depending on the train time table . For time dependent route plan, it is good to use periodic function which can accommodate different weight of edge at different time of the day. If set of all positive real number represented by R0+ then the functions associated with any edge weight f is represented by f: R0+ ïƒ R0+ (input to and output from function f is real positive number) and they are elements of function space F~. For any given edge e Ð„ E the weight of the edge denoted by function fe. This periodic function is restricted with time period so Ï€ for all Ï„ Ð„ R0+, f(Ï„) = f(Ï„ mod Ï€) .The function values of f(Ï„) is in time span.

Minimum value of function f for any given time Ï„ where Ï„ Ð„ R0+ is f_:=min Ï„ Ð„ R0+f(Ï„).

Maximum value of function f for any given time Ï„ where Ï„ Ð„ R0+ is f- =max Ï„ Ð„ R0+f(Ï„).

## Time Window:

A time window is a time period, when a node is available for travelling through [14]. There are many practical situations where time windows can be used to describe the time constraints associated with the nodes and edge on a network. In transportation network, time window for node is the time period that a service or transition facility is available for use. Similarly, a time window associated with an edge is the time that a transportation channel is open.

## Paths:

Path is sequence of nodes. For graph G, path P has sequence of nodes [v1,v2,v3,v4â€¦.vk] so for i > 1 and i < k any edge between two nodes vi and vi+1 is belongs to set of graph edge E. If v1=vk then that path P is called a cycle. |P| denotes the number of edges the path has and the length of Path is sum of the weight of each of its edge. Path in graph G contains certain nodes for multiple times without being cycle.

## FIFO property:

A FIFO property guarantees that along an edge it is never possible to depart later but arrive earlier. The functions is fulfilling the FIFO property if for any two time values Ï„1, Ï„2 Ð„ R0+ if Ï„1<Ï„2 then f (Ï„1) + Ï„1 must be less than f(Ï„2) + Ï„2. The time dependent graph is a FIFO graph is every edge f the graph has FIFO property [3].The graph GT(V,E,W) is a FIFO graph if every edge (vi,vj) has FIFO property. An edge (vi,vj) has FIFO property if the value of edge weight function wi,j(t0) at time t0 is wi,j(t0) <= tâˆ† + wi,j(t0+tâˆ†) for tâˆ† >=0.

## Shortest Path:

Source node is s, destination node is v and departure time Ï„ Ð„ R0+, the path in a network with the following properties.

The path must start from s,

The departure time at s is Ï„,

The path ends at v.

The path between node s to v is shortest route if the travel time of all other paths satisfying the properties (i),(ii),(iii) and must be bigger or at least equal. The step (ii) can be ignored, if the network is time-independent [13].

From above steps prove that from all the possible paths from s to v, shortest path is the one which arrives at destination node v at earliest.

Shortest path algorithm is applicable to any time independent or time dependent network which includes road network, railway network and flight network or any other public transportation.

In time independent routing, each edge will assign some constant value. So for edge e the constant value is w(e).this weight could be travel time, or geographical distance or any other metric. If this is geographical distance metric then it will be constant for any given time of the day but if it is travel time metric then weight of this edge can be varies depends on peak hours and non-pick hours traffic.

Difference between shortest path and minimum cost path is, in shortest path the cost of edge is time of that edge but in minimum cost path the cost of the edge could be time, cost or distance.

## Shortest path algorithms for time independent networks

The shortest path problem was represented in 1950s and 1960s by Dijkstra[15], Bellmann and Ford[16] and Nilsson and Raphael(A*)[17]. To find the shortest path for time independent routing, Dijkstra algorithm or Bellman ford algorithm or A* are being used.

## Dijkstra Algorithm:

Dijkstra algorithm conceived by Edsger Dijkstra in 1956 and published in 1959 [21] [22] is an algorithm that finds the single-source shortest path for a time independent graph. Dijkstra algorithm supports non-negative weight of edge.This algorithm finds the shortest path from any source node to destination nodes for any given time independent graph. This algorithm works by making the paths to one more node shortest at each step. At the kth step, you know for sure that there are at least k nodes to which you know the shortest path. Pseudo code for Dijkstra algorithm is given below [23].

For a graph, G = (V,E) where V is finite set of nodes/vertices and E is finite set of edges .Graph G has edge (v1,v2) and a source node s Ð„ V and v Ð„ V.

dist[] : array of distances from the source node s to each destination node

prev[] : array of pointers to preceding node

i : loop index

F : Finished nodes list

U : Unfinished nodes list

/* Initialization: In the initialization part set every distance from a source s to each destination node to "infinity" for each node until the path discovered

And initialize preceding node pointer with null . "prev" pointer that stores the node from which the "explorer" came from*/

for i = 0 to |V| - 1

dist[i] = infinity

prev[i] = null

end

dist[s] = 0 /* The weight of edge from the source to the same source is defined to be zero */

/* below loop is to find the shortest path between source s to each destination v.*/

while(F is missing a node)

Select the node from unfinished nodes in list U with the shortest path to s

add v to F //add node to finished list. i.e node is already //covered

for each edge of v, (v1, v2)

if(dist[v1] + length(v1, v2) < dist[v2])

dist[v2] = dist[v1] + length(v1, v2)

prev[v2] = v1

update U

end if

end for

end while

Initialize distance from source s to each destination node v is infinity. Distance from source to same source is zero. U is number of nodes which are not visited yet.

## Bellman-Ford Algorithm:

The Bellman-Ford algorithm named by its developers, Richard Bellman and Lester Ford, Jr.[24] Similar to Dijsktra algorithm, Bellman Ford algorithm also computes the shortest path for time independent graph.

Dijsktra algorithm supports non negative edge weight.

Bellman Ford algorithm supports both non negative and negative edge weight. Bellman-ford algorithm is similar to

Dijkstra algorithm except approach to find the shortest path

in Bellman Ford algorithm does not select minimum weight

node greedily. Pseudo code for Bellman Ford algorithm is

given below [24].

Fucntion: BellmanFord(list nodes, list edges, source node)

For a graph, G = (V,E) where V is finite set of nodes/vertices and E is finite set of edges .Graph G has edge (u,v) and u,v Ð„ V.

// Step 1: initialize graph: /* Initialization: In the initialization part set every distance from a source to each destination node u, v to "infinity" for each node until the path discovered

And initialize preceding node pointer with "null" */

for each node v in nodes:

if v is source then v.dist := 0

else v.dist := infinity

v.prev := null

// Step 2: relax edges repeatedly. /* below loop is to find the shortest path between source s to each destination v.*/

for i from 1 to size(nodes)-1: //1st part of step 2

for each edge uv in edges: // uv is the edge from u to v

u := uv.source

v := uv.dist

if u.dist + uv.weight < v.dist: //2nd part of step 2

v.dist := u.dist + uv.weight

v.prev := u

// Step 3: check for negative-weight cycles

for each edge uv in edges:

u := uv.source

v := uv.dist

if u.dist + uv.weight < v.dist:

error "Graph contains a negative-weight cycle"

Initialize distance from source to each destination node is infinity. Distance from source to same source is zero.

1st part of step 2, a edge weight is updated by v.distÂ := u.dist + uv.weight. Where u.dist is the edge weight of some path from source to u. Then u.dist + uv.weight is the total weight of the path from source to v via node u so total weight is from sourceïƒ u ïƒ v

2nd part of step 2, consider the shortest path from source to u with at most i edges. Let v be the last node before u on this path. Then, the part of the path from source to v is the shortest path from source to v with at maximum i-1 edges so v.dist after iâˆ’1 cycles is at most the length of this path. Therefore, uv.weight + v.dist is at most the length of the path from s to u. In the ith cycle, u.dist gets compared with uv.weight + v.dist, and is set equal to it if uv.weight + v.dist is smaller. Therefore, after i cycles, u.dist is the shortest path from source to u that uses at most i edges.

## MODELLING TIME DEPENDENT NETWORK

Time dependent network will not have constant weight for any edge for any given day of time. The weight of edge will vary with time. To model time dependent network, the starting time of travel interval, type of gradient and representation of time dependent network has to consider.

Discrete representation of time

Continuous representation of time.

Fixed gradient and Variable gradient.

Representation of different type of time dependent transportation network

## Discrete representation of time:

In Discrete time algorithm, time interval of given graph GT(V,E,W) will discretizing into time points. Time has modelled as a set of integer [13]. In discrete time approach the starting time interval T= [ts,te] will be discretized into k points evenly and construct static graph GT'(V',E',,W',) by making each node and each edge. Value |V'|= k|V|, |E'| = k|E| and edge weight W' is static. For each edge (v's,v'd) belongs to E',edge weight w'i,j is equal to the value of wi,j(t) on a time point. Shortest path can be solved as a static single source shortest path problem in G'T(V',E',W') whose size is enlarged by k times.

The drawbacks for this method are:

In discretized method the travel time is assumed to be step functions of the starting time at the origin node but in real world travel time changes continuously over the time[5]

By using the discrete time algorithm, we can find the shortest path but the error found in shortest path is highly sensitive to k parameter.

Increasing values of k decrease the efficiency of this approach since GT' is k times larger than GT

## Continuous representation of time:

In continuous representation of time, time will be treated as a real number. For this piecewise linear function method can be use. Instead of constant weight for each edge, weight will be a function Æ’ from some function space F. The shortest path between two nodes s and v in time dependent routing depends on the departure time Ï„s. This will give different length of shortest path for different departure time. The periodic function is used for time dependent routing.

The periodic function Æ’: R0+ ïƒ R0+ (whose input and output are positive real number R0+) is called piecewise linear if it consists of a finite segment of linear functions. Æ’ will have finite set B of interpolation points where each interpolation point pi Ð„ B consist of departure time Ï„i and associated function for value f(Ï„i).

For Continuous presentation of time, there are lots of research done to find shortest path either Disktra based algorithm or Bellman - Ford based algorithm [3].

## Fixed gradient and variable gradient:

Variable gradient will vary with time. For road network, two points can be interpolate linearly, variable gradient can be use to find the travel time/edge weight for road network. For rail network or for any public transportation network travel time is waiting time + actual travel time. For train network fixed gradient method is used. Fixed gradient method is used to find the edge weight for any public transportation network. First have to add the waiting time for the next train or bus and then add actual travel time to get the weight of the edge. Figure 2 is indicating variable gradient and fixed gradient.

Piecewise linear function with fixed gradient can be define as below.

f(Ï„)= -Î³.( Ï„i- Ï„) + f(Ï„i)

Where, some arbitrary point Ï„ , the nearest interpolation point Ï„i with fixed gradient Î³. This is very useful when we have to wait for the next train or air plane to depart and then add the actual travel time along that edge.

Figure 2: In above left figure is variable gradient for road network and right figure is for public transportation type network with fixed gradient.

The period of function Æ’ is Ï€. Ï„i is the departure time for each interpolation point. The function space consisting of all piecewise linear functions with a certain gradient Î³ is denoted by BL(Î³).

## Representation of different type of time dependent transportation network:

Road network can represent by set of nodes V and set of edges E. The travel time over road network varies with time throughout the day so it is good to use time dependent routing for road network but road network for big country is very big and time delay on any road network is predictable such as large amount of commuter traffic during the daily peak hours and others less predictable such as weather or road accidents. To represent road network, it is better to use time independent routing. The edge weight w(e) for each edge in the road network can be average travel time on specific road segment. This average travel time is computed by taking the average traffic speed on that road segment which in turn multiplies with geographical length of that road segment to get the travel time.

Railway network always follow timetables [26]. By using this time table we can construct a graph. A railway timetable is tuple (C,B,Z~,Ï€) where B is set of stations, Z~ a set of trains, Ï€ the periodicity of time table C a set of elementary connections. Elementary connection C is also defined by tuple c = (Z,S1,S2, Ï„1,Ï„2) where train Z Ð„ Z~, S1 and S2 Ð„ B and train Z departing from S1 at time Ï„1 < Ï€ and arriving at S2 at time Ï„2 < Ï€.

If arrival time Ï„2 is greater than Ï„1 then travel time of c is simply the difference Ï„2- Ï„1.But if arrival time Ï„2 is less than departure time Ï„1 then travel time will be Ï€ - Ï„1 + Ï„2.

To represent railway network The Condensed Model, Time Expanded Model, Time Dependent Model can be used .All those models use travel time metric.

Time dependent model approach for modeling railway network can overcome all the difficulties which we can face by Time expanded model or Condensed model. Time depended model has two version one is Simple version and another is realistic version.

In Time dependent Simple version, edge function is linear function. The value of function f at ith interpolation point is f(Ï„i). This is the travel time of ith train on that railway network. The weight f(Ï„) of any edge is composed of the travel time f(Ï„i) plus the train waiting time.

f(Ï„)= (Ï„i - Ï„) + f(Ï„i). Where (Ï„i - Ï„) is train waiting time and f(Ï„i) is travel time.

In Time dependent realistic version, each station S Ð„ B is called station node on the graph. Beside these station nodes there are additional nodes called route nodes in the graph. These route nodes are used by trains to go to subsequence route nodes and these routes are finally connected to their respective station nodes with the proper transfer time (edge weight).

Divide Set of trains Z into train routes. The set of these train routes is R~. Each train routes is denoted by R.R Ð„ R~. If we have number of stations [S1,S2,S3â€¦..,SK], for each station node there is route node. For station Si, there is route nodes ri, on the graph. Each subsequent graph will be connected through edges e = (ri,ri+1). Each edge e defined with interpolation function fe. Transfer edge will be use to count transfer time from one train to another. The route nodes r belongs to S. From this route node there will be two edges (r,S) and (S,r)

An edge (r, S) is from the route node to the station node. The weight of this edge is always 0. This edge is for getting off from the train, which is not charged with any time. Another edge (S, r) is the weight of this edge is set to transfer(S). This approach is called constant transfer time approach. For variable transfer time model, the different transfer time between different train routes running through stations S can be allowed. In Below Figure 3 for the simple time dependent model and realistic time dependent models are shown. Blue are departure nodes, purple are route nodes.

Figure 3: In above 1st figure is Simple model and 2nd figure is realistic model

## ALGORITHMS FOR TIME DEPENDENT ROUTING

Although there is a vast literature on the Vehicle Routing Problem (VRP) with time independent travel times, the literature on the Time Dependent Vehicle Routing Problem (TDVRP) is less.

Only few papers are available from Malandraki and Daskin(1992), Ichoua et al(2003), Fleischmann et.al(2004), Haghani and Jung(2005), Donati et al(2008), Van Woensel et. Al.(2008) and Hashimoto et al(2008) [4]. The major weakness of these papers is that they cannot deal with First In First Out (FIFO) property. The time dependent Vehicle Routing Problem (VRP) was first formulated by Malandraki and Daskin (1989, 1992)[7] using a mixed integer linear programming formulation. A greedy nearest-neighbor heuristic based on travel time between customers was proposed, as well as a branch and cut algorithm to solve TDVRP without time windows.

Hill and Benton (1992)[8] considered a node based time dependent vehicle routing problem (without time windows). Computational results for one vehicle and five customers were reported. Ahn and Shin (1991)[9] discussed modifications to the savings, insertion and local improvement algorithms to better deal with TDVRP.

Ichoua et al. showed that ignoring time dependency, i.e. using transportation network models with constant speed, can lead to poor solutions. Ichoua et.la [5] proposes a solution methodology to solve time dependent vehicle routing problems with time windows using Tabu search, which satisfies the FIFO assumption.

According to the method of Ichoua (2003) [5], use step function of speed distribution to represent the dynamic road network. As given in below figure 4, through the step function of edge travel speed, we can get continuous function of edge travel time. This method ensures the network has FIFO property. Travel speed over the edge can be change much faster than the travel time on edge. Due to travel time changes, this model can satisfies the FIFO property. According to method of Ichoua, any vehicle which starts from node later than 1st vehicle will not get incentive even, the speed of 2nd vehicle increase afterwards. Instead of waiting at source node to start, 2nd vehicle could use the waiting time with available speed to get closer to its destination.

Figure 4: Time dependent function (a): travel speed,(b):travel function.

More recently Van Woensel et al. (2008)[12] used a tabu search to together with queuing theory to solve the capacitated vehicle routing problem with time dependent travel times. For the queuing theory, he has considered maximum traffic density of road (maximum number of cars on road segment), minimum space needed by one vehicle on road segment and flow of vehicle on road.

## Time dependent shortest path (TDSP):

To find shortest path for time dependent network Bolin [3] has suggested below method.

Time dependent graph GT is defined by GT(V,E,W) where V is set of nodes Vi, E is set of edges which belongs to VxV and W edge delay function which define how much travel time it takes to travel from one node to another note for a given starting time interval. For every edge (vi ,vj) there is weight function wi,j(t) Ð„ W, where t is time variable which will vary in a given starting time interval T =[ts,te].

wi,j(t) specifies how much time it takes from vi to vj when departing from vi at time t. Shortest path (vs,ve,T) is the minimum travel time from source node vs to destination node ve when user starts from source node vs at any starting time interval T =[ts,te] . To find shortest travel time there will be some waiting time at node vi denoted by áº…(vi).

From any node vi, if departure time is departure(vi) and arrival time is arrival(vi) then

departure (vi) = arrival (vi) + áº… (vi)

For any given fixed time t, fixed path which has v1ïƒ v2ïƒ v3ïƒ v4ïƒ v5ïƒ v6â€¦â€¦.--ïƒ vk with waiting time áº…(vi). If arrival time at node v1 is t then arrival time for node v2 can be calculate by equation (ii). Arrival time at node vk can be calculated by equation (iii). Value of arrival time function is calculated by equation (iv).

arrival (v1) = t

arrival (v2) = departure (v1) + w1,2(departure(v1))

arrival(vk)=departure(vk-1) + wk-1,k(departure(vk-1))

Arrival time function gp(t) = arrival(vk).

Travel time along the path p is thus gp(t)-t shortest travel path from node vi to vk along path p is minimum travel time gp*(t*) - t* where t* is best starting time which results in minimum travel time or shortest path.

To find shortest path over a time dependent graph GT is to find shortest path p* from one node to another with waiting times áº…(vi) and starting time t*.

Similar method mentioned by Frank [20] is TDSPint, is defined for a graph Gi(V ,E), where the availability of edges changes over time. Each edge e = (u, v) Ð„ E is assigned a set Ie of time intervals, during which the edge is available and that is called availability intervals. In certain situations, some roads or lanes of a road network are only available during certain times. Typical examples include no left-turns during rush hours, border crossings that are closed during the night, and lanes restricted for buses during certain peak periods. During the times which outside the set Ie of time intervals, the edge e is not available and has to wait until the start of the next availability interval in Ie. For every availability interval i cost wie represents the time needed to travel to e during availability interval i. For the source node u to destination node v the total arrival time is waiting time at node v + travel cost wie.

## Shortest path time for FIFO time dependent graph:

Although time dependent graph has FIFO property, the weight of edge are not constant, it can vary with different starting time there for any node vs to ve, shortest path will be different for different starting time. In continuous starting time there will be infinite starting values. It is very challenging to select best starting time t* and the shortest path between vs and ve from an infinite number of possible starting times and exponential number of possible path between vs and ve. Below is the solution proposed by Bolin [3] for time dependent FIFO graph.

For FIFO time dependent graph, there is no waiting time allowed [13]. For FIFO time dependent graph, algorithm proposed by Bolin[3] is to decoupled starting time interval T into time refinement and fast path selection. The time refinement, for every node vi Ð„ V and compute the shortest travel time gi(t) departing from arrival node vs to destination node ve at any starting time t Ð„ T.

Based on this shortest travel time gi(t) compute the best starting time t* with minimum travel time ge(t*) - t*. From this shortest travel time, select the path which matches this shortest travel time.

To get the shortest travel time function gi(t) for each node vi in V, refine time arrival function gi(t) incrementally in the given starting time interval T=[ts,te]. For every node vi Ð„ V, let Ii=[ts,Ï„i] Ð„ T be a starting time subinterval, Ï„i Ð„ T. Refine gi(t) by extending Ii to a larger starting time subinterval Ii' =[ts,Ï„i'] Ð„ T and Ï„i' > Ï„i. Refined gi(t) is the shortest path between vs-vi for any starting time t Ð„ Ii.

For the fast path selection the path p* from vs to ve, determine the predecessor of every node on p* backward from ve to vs based on gi(t) and t*. The predecessor of vj is determined at vi if gj(t*) = gi(t*) + wij(gi(t*)), where (vi,vj) Ð„ E. That means shortest travel time at vj i.e. gj(t*) is the arrival time at vj i.e. gi(t*),plus the edge delay from vi to vj, if there is no waiting time at vi.

Similar approached proposed by Ismail Chabini [13] is

shortest travel time required from departure node o to arrival node j is denoted by fj..fj will consider only those paths that visit previous node i at a time greater than or equals to fi.

Where B(j) denotes set of nodes having any outgoing edge to node j.dij(t) is the distance between i to j at starting time t.

If there is not waiting time at any node i.e. graph is FIFO graph then above equation can rewrite as below.

Since for FIFO graph

## Dijkstra based shortest path solution for FIFO time dependent graph:

To get shortest path for FIFO time dependent graph, we can even use Dijkstra algorithm [18] and [19] where we will have one more argument to our Dikjstra function for departure time t. This time t will be consider to find the weight of edge at the departure time. If for any edge e the function fe is being used to find the weight of that edge then the time we have to consider for function fe is departure time t plus the distance along the path to destination v. Weight of edge e is we=fe(t + distance from source s to v)[18]

## Shortest path for non FIFO time dependent graph:

In transportation network it is not necessary that FIFO condition will be satisfied all the time. For non FIFO time dependent graph waiting is allowed at the node [13]. To find the shortest for non FIFO time dependent graph, transform a non-FIFO graph G'T(V,E,W') into FIFO graph GT(V,E,W) where both V and E will be same for both graphs.By using time refinement and fast path selection method we can find the shortest path. To find the time refinement and fast path selection algorithm proposed by Bolin[3] is to separate starting time interval T into time refinement and fast path selection. For the time refinement, for every node vi Ð„ V and some waiting time at node vi denoted by áº…(vi), compute the earliest arrival time gi(t) departing from vs at any starting time t Ð„ T. Details about this computation is mentioned in section 5.1. Based on this early arrival time gi(t) compute the best starting time t* with minimum travel time.ge(t*) - t*. From this shortest travel time select the path which matches this shortest travel time.

To get the shortest travel time function gi(t) for each node vi in V, refine time arrival function gi(t) incrementally in the given starting time interval T=[ts,te]. For every node vi Ð„ V, let Ii=[ts,Ï„i] Ð„ T be a starting time subinterval Ï„i Ð„ T. Refine gi(t) by extending Ii to a larger starting time subinterval Ii' =[ts,Ï„i'] Ð„ T and Ï„i' > Ï„i.

For the fast path selection the path p* from vs to ve, determine the predecessor of every node on p* backward from ve to vs based on gi(t) and t*. The predecessor of vj is determined at vi if gi(t*) = gi(t*) + wij(gi(t*)), where (vi,vj) Ð„ E. That means arrival time at vj, gj(t*) is the arrival time at vj, gi(t*), plus the edge delay from vi to vj, if there is no waiting time at vi.

The shortest path p* found in FIFO graph G'T by inserting some waiting time on each node in path p*.

For each edge delay function w'i,j(t) to construct a FIFO graph GT.

wi,j(t) = âˆ†i,j(t) + w'i,j(t + âˆ†i,j(t))

= min0<=tâˆ†<= te-t {tâˆ† + w'i,j(t+tâˆ†)}

âˆ†i,j(t) is the optimal waiting time to traverse edge ( vi,vj) if arriving at vi is time t. If there are multiple possible value of tâˆ† to minimize w'i,j(t + tâˆ†) + tâˆ† then select any of them a as âˆ†i,j(t).

After finding shortest path p* by time refinement and path selection for FIFO graph, convert this shortest path to p'* for original non FIFO graph by inserting waiting time áº…(vi) = âˆ†i,i+1(t) at node vi for 1<= i <= k-1 where t is the arrival time at node vi along path p* in GT for starting time t*.

Similar approach proposed by Ismail Chabini [13] for non FIFO graph where waiting is allowed at the nodes.

For maximum waiting time is denoted by wi(t) at node i and for departure time interval t then shortest travel time for edge (i,j) is given by function

where s is set of departure time interval. The shortest travel time is

Above equation shows that when waiting is allowed at nodes then shortest path with waiting node is equals to shortest path for no waiting at node and the edge delay function Dij(t).

## A Distributed Shortest path routing algorithm:

A distributed shortest path routing algorithm from Bin Zou[25] is using Dijkstra algorithm and distributed Bellman Ford(DBF) algorithm to find the shortest path in transportation network. The Distributed Bellman-Ford protocol is a proactive table-driven protocol on basis of the Bellman-Ford algorithm. In DBF algorithm every node maintains a routing table. This DBF algorithm need by each node in network to communicate with Wireless Sensor Networks.

Wireless Sensor Network is used to collect and respond to environmental information, data gathering, data aggregation, etc. DBF algorithm is having two major disadvantages compare to Dijkstra Algoritm. These two drawbacks are bouncing effects and counting to infinity problem [25]. Each node is using Dijkstra algorithm as a local shortest path routing algorithm and whole network works in manner of DBF. Each node will maintain a distance table which is made of routing tables of all his neighbors plus a edge vector. From the edge vector each node is receiving its new routing table. Whenever any node received a change in the shortest path from a neighbor to any destination, it renews the corresponding item in its own distance table and thus it will also update its own routing table at the same time.

## OPTIMIZATION OF TIME DEPENDENT ROUTING ALGORITHMS

Nowadays computer based route planning for road network is established. Route planning for road networks is done by Portable Navigation Device (PND). In PND time dependent routing algorithm being use to find the shortest path between two places. PND is embedded application so power consumption by the shortest path algorithm should be less and PND has to respond to customers' query faster too.

There are few speed up techniques suggested by Daniel Delling [27] and by A. Crauser[28].

The problem with Dijkstra algorithm is it takes up to 10 seconds to find the shortest path from one node to another for very big transportation network. Dijkstra algorithm computes the distance to all possible nodes in the network being closer than the target we are interested in. Sometimes it is time consuming if it computes all these not required distances if we are interested in the path between two points only.

There are many speed-up techniques have been developed within the last few years. In this techniques split the work into two parts. During an offline phase, called pre-processing, we compute additional data that accelerates queries during the online phase. This pre-processing technique can reduce the processing time to microsecond.

In Goal directed search, is to push the search towards the target/destination by adding a potential Ï€ to priority of each node. A good potential lowers the priority of nodes that lie on the shortest path to the destination/target. Goal direct search is equals to Dijkstra algorithm on graph but with reduce cost. For the length of edge from source s to destination v is len Ï€ ( v,s) = len(v,s) - Ï€ (v) + Ï€ (s)

Arc-Flag approach computes the partition C of the graph and then attaches a label to each edge of the graph. A label contains for each cell C, a flag AFc(e) which will be true if a shortest path to at least one node in C starts with e. This modified Dijkstra algorithm is calls Arc-Flags Dijkstra which will consider only those edges whose flags of the target nodes cell is true. This method is very use full for further use of query algorithm.

Contraction approach is "Node Reduction". In node reduction, number of nodes is reduced by iteratively bypassing nodes till you get no node is bypass able any more. To bypass any node v, first have to remove all its incoming edges I and outgoing edges O from the graph then for each u Ð„ tails (I) and for each w Ð„ heads (O) add a new edge. If there is an edge already connecting between u and w then consider the edge which is smaller one.

## CONCLUSION

Any transportation networks can represent by graph. The transportation network is dynamic and weight of edge in dynamic transportation network changes with time.

Finding the shortest path for time dependent dynamic transportation network is challenge. For time dependent transportation network continuous representation of time is better than discrete representation of time.

Dijkstra algorithm and Bellman Ford algorithm find the shortest path for time independent network.Dijkstra algorithm and Bellman Ford algorithm can be modify for time dependency and can be use to find the shortest path for time dependent network.

Finding shortest path for non FIFO graph is more complicated compare to FIFO graph. For time dependent FIFO graph, Dijkstra algorithm can be use with some modifications. Time dependent Non FIFO graph, can convert into time dependent FIFO graph[3].

For road network it is better to use time independent network since for big country, road network is very huge and travel time on road network is predictable for peak hours and off peak hours. But for public transportation, time dependent routing is better.

There are certain techniques available to improve the shortest path calculation for network. Research on speed up techniques to find the shortest path over dynamic transportation is in demand.