DISCRETE DYNAMIC SHORTEST PATH PROBLEMS IN TRANSPORTATION APPLICATIONS: #
Introduction #
- An increasing interest in the concept of dynamic management of transportation systems.
- Link costs generally depend on the entry time of a link
- dynamic shortest paths problems
- time-dependent shortest paths problems
- Various types of dynamic shortest path problems
- fastest vs. minimum cost or shortest path problem
- Discrete vs. continuous representation of time
- FIFO networks vs. non-FIFO networks, where one can depart later at the beginning of one or more arcs and arive earlier at their end
- waiting is allowed vs. waiting is not allowed at nodes
- types of shortest path question asked:
- one-to-all for a given departure time, or all departure times
- all-to-one for all departure times
- integer vs. real valued link travel times and link travel costs
- In this paper, we study three types of shortest path problems in descrete dynamic networks:
- the one-to-all fastest paths problem depending origin node at a given time interval
- the all-to-one fastest paths problem for all departure time intervals
- the all-to-one minimum cost paths problem for all departure time intervals
the one-to-all fastest paths problem #
- G = (N, A, D, C) is called d discrete dynamic network.
- N : the set of nodes
- A : {(i,j) in N x N}, the set of arcs (or links)
- D : {dij(t) | (i,j) in A} the set of time dependent link travel time
- C : {cij(t) | (i,j) in A} the set of time-dependent link travel costs
- FIFO : For all (i,j,t), t + dij(t) <= (t+1) + dij(t+1).
- In this paper, we concentrate on two questions.
- what are the shortest paths from one origin to all destinations departing at instant 0?
- what are the shortest paths from all nodes to one destination node for all departure times?
the all-to-one for all departure times fastest paths problem #
- presents a backward star formulation of this problem.
the all-to-one for all departure times minimum cost pats problem #
- Algorithm DOT for Minimum Cost Paths
- step 0 (Initilization)
Ci(t) = inf, for all i /= q, Cq(t) = 0, for all t < M-1
Ci(M-1) = Static Shortest Paths (Cij(M-1), q) for all i
Note: Ci(t) = Ci(M-1), for all t >= M-1, i
- Step 2 (Main Loop)
For t = M - 2 down to 0 do:
For (i,j) in A do:
Ci(t) = min( Ci(t), cij(t) + Cj(t+dij(t)) )
|
![[http]](/~tetris/study/imgs/http.png)
