Backward Dijkstra Algorithms for Finding the Departure Time Based on the Specified Arrival Time for Real-Life Time-Dependent Networks

Gelareh Bakhtyar¹, Vi Nguyen², Mecit Cetin¹, Duc Nguyen^1,3

¹Department of Civil and Environmental Engineering, Old Dominion University, Norfolk, USA.
²Department of Mechanical and Aerospace Engineering, Old Dominion University, Norfolk, VA, USA.
³Department of Modeling, Simulation, and Visualization Engineering, Old Dominion University, Norfolk, VA, USA.

DOI: 10.4236/jamp.2016.41001                

Abstract

A practical transportation problem for finding the “departure” time at “all source nodes” in order to arrive at “some destination nodes” at specified time for both FIFO (i.e., First In First Out) and Non-FIFO “Dynamic ” Networks is considered in this study. Although shortest path (SP) for dynamic networks have been studied/documented by various researchers, contributions from this present work consists of a sparse matrix storage scheme for efficiently storing large scale sparse network’s connectivity, a concept of Time Delay Factor (TDF) combining with a “general piece- wise linear function” to describe the link cost as a function of time for Non-FIFO links’ costs, and Backward Dijkstra SP Algorithm with simple heuristic rules for rejecting unwanted solutions during the backward search algorithm. Both small-scale (academic) networks as well as large- scale (real-life) networks are investigated in this work to explain and validate the proposed dynamic algorithms. Numerical results obtained from this research work have indicated that the newly proposed dynamic algorithm is reliable, and efficient. Based on the numerical results, the calculated departure time at the source node(s), for a given/specified arrival time at the destination node(s), can be non-unique, for some Non-FIFO networks’ connectivity.

Keywords

Backward Dijkstra, Dynamic Networks, Piece-Wise Linear Function, Specified Arrival Time

1. Introduction

For most people who have to commute from their homes to their work-places, they want to have the answers for either of the following questions: if we leave our home at a specified time, what time we will arrive at the office? Or what time we should depart from home in order to arrive at the office at a specified time? Similar questions have been asked by long distance travelers, etc.

The vast majority of Shortest Path Problem (SPP) publications have dealt with static (i.e., non-time-dependent) networks that have fixed topology and constant link costs. In recent years, there has been a renewed interest in the study of Time-Dependent Shortest Path Problems (TDSPP). Thus, one of the fundamental network problems in such applications is the computation of the shortest paths from all nodes to a set of destination nodes for all possible departure time, in a given time-dependent network.

Orda and Rom [1] have presented an algorithm for finding the shortest path and minimum delay under various waiting constraints, and for all instances of time. The properties of the derived path (under arbitrary functions for link delays) are also investigated in their studies. Daganzo [2] have solved the backward SSP on a network with FIFO links. The FIFO property means “First In First Out” and states that if a vehicle leaves node i at time and the other one leaves the same node at time, then the second vehicle cannot arrive at node j before the first one. Chabini and Ganugapati [3] have proposed an efficient dynamic solution algorithm, call algorithm DOT, and prove that no sequential algorithm with a better worst-case computational complexity can be developed. Wuming and Pingyang [4] introduced an algorithm to solve the shortest paths in time-dependent network by converting Non-FIFO network to a FIFO network and solve the problem using the traditional SSP algorithms. Ding, Yu, and Qin [5] have proposed a new Dijkstra-based algorithm by decoupling path-selection and time-re- finement in the starting-time interval T. They have also established/proved the time complexity and space complexity based on their proposed 2 step approached. Through extensive numerical studies, they have also concluded that their dynamic algorithm outperforms existing solution algorithms in terms of efficiency.

Bidirectional Dijkstra search is a standard technique to speed up computations on static networks. However, since the arrival time at the destination is unknown, the cost of time-dependent links around the target node cannot be evaluated, thus bidirectional search cannot be directly applied on time-dependent networks. Nannicini [6] has proposed a solution to the above problem by using a time-independent lower bounding function in the backward search.

Computational strategies for families of Frank-Wolfe (FW), Conjugate FW, Bi-conjugate FW Deterministic User Equilibrium (DUE) algorithms for static networks have also been reported by Allen [7].

The focus of this paper is to find the departure time at the source node(s) for a given (or specified) arrival time at the destination node(s) in FIFO, and Non-FIFO networks. This present work consists of a sparse matrix storage scheme for efficiently storing large scale sparse network’s connectivity, a concept of Time Delay Factor (TDF) combining with a general piece-wise linear function to describe the link cost as a function of time (for Non-FIFO links’ costs), and Backward Dijkstra SP Algorithm with simple heuristic rules for rejecting unwanted solutions during the backward search algorithm.

The remaining of this paper is organized as following. Dynamic networks are discussed in Section 2, where the concept of TDF in conjunction with piece-wise linear time function for the links’ costs are also introduced in this section. A small numerical example of a dynamic network (with 5 nodes and 9 links) is used in Section 3 to facilitate the discussions of the Polynomial LCA and Forward Dijkstra algorithms for finding the arrival time at the destination node, based on the known departure time at the source node. Furthermore, this same dynamic network will also be used in Section 3 for finding the departure time at the source node in order to arrive at the destination node at a given time. The issue of unique (or non-unique) solution for this focused problem (i.e. finding the departure time at the source node for a specified arrival time at the destination node) is also discussed in Section 3. Real-life (large-scale) dynamic transportation networks are investigated, using the proposed time-dependent Backward Dijkstra algorithm, and the numerical results are presented in Section 4 to validate the proposed dynamic algorithm. Finally, conclusion is summarized in Section 5.

2. Time Delay Factor and Piece-Wise Linear Time Function in Dynamic Networks

For dynamic networks, the time to travel from node “i” to node “j” of a particular link “k” is no longer a constant. The actual travel time on link “k” will depend on the departure time at node “i”. In this work, the following formulas are employed for a typical link “k”, connected by node “i” to node “j”:

(1)

where Arrival Time at node “j” for a typical link “k”, Departure Time at node “i” for a typical link “k”, Constant “Static” Time for a typical link “k”, Time Delay Factor (), which is dependent on and can be defined as Equation (2), and is the appropriated time function for a typical link “k”.

(2)

In this work, the time function (which depends on) can be represented as shown in Figure 1 where piece-wise linear time function is used. For typical travel time in real dynamic networks, travel time will be increased during certain hours of the day, say during 6 am - 8 am in the morning (due to morning rush, since travelers drive to work), and say during 16 hours-18 hours (or 4:00 pm - 6:00 pm, since travelers leave their offices for heading homes).

In Figure 1, the coordinates () of such points O, A, B, C, D, E, F, G, H, and I are defined as the input parameter (provided by the software user). Thus, this piece-wise linear time function can be (conveniently, and appropriately) provided to take into account of different local traffic congested time. In general, one may have different function for different links. However, in our research work, we assume that all links (see Figure 2(a)) will have the same travel behavior as the one shown in Figure 1.

The value of can be varied (say, from 0.00 to 1.00 as indicated in Figure 1). Thus, for static networks, the defined in Equation (2) is equal to 1 (by setting = 0.00), while for dynamic networks, the value of could be any where within the range, depending on the value of. The following 2 important observations can be made:

1) On a typical link “k”, if the departure time at node “i” is known, then the arrival time at node “j” can be uniquely and easily computed (by using Equation (1-2), and Figure 1).

2) On a typical link “k”, if the arrival time at node “j” is known, then the departure time at node “i” can also be computed (by using Equation (1)-(2), and Figure 1). However, in this case, the computed departure time at node “i” may NOT be unique. Some sorts of elimination (heuristic) rules need be developed in order to find an acceptable single solution.

3. Finding the Departure Time at the Source Node(s) Based on the Specified Arrival Time at the Destination Node(s)

In this section, a dynamic network with 5 nodes and 9 links, shown in Figure 2(a), will be analyzed. For convenience, all links will be assumed to have the same time function as illustrated in Figure 1. The following problem’s cases will be investigated.

Problem 1. Use the polynomial LCA (time dependent) method to find the time dependent shortest path from any source node, say to any destination node, say at the following three possible departure time:

Case (a): 9 hrs. = 9:00 am (to simulate right after rushed /busy hours, see Figure 1).

Case (b): 15 hrs. = 3:00 pm (to simulate right before rushed /busy hours, see Figure 1).

Case (c): 16.75 hrs. = 4:45 pm (to simulate during rushed /busy hours, see Figure 1).

Figure 1. Piece-wise linear time function for a typical link “k”.

(a) (b)

Figure 2. (a) A dynamic network topology; (b) A dynamic reversed network topology with 5 nodes and 9 links.

This problem is rather straight forward, since the departure time is known at the source node 5. For any subsequent links, since the departure time of node “i” for links is known, hence:

The function can be easily/uniquely determined (from Figure 1), the Time Delay Factor can be easily/uniquely determined (from Equation (2)), and the arrival time at node “j” can be easily/ uniquely determined (from Equation (1)). Eventually, the at node 2 (for all cases a, b, and c) were found and presented in Table 1.

Problem 2. Re-do problem 1 (for all cases a, b, and c), but using the regular forward time dependent Dijkstra algorithm.

The final results are identical to the one obtained in Problem 1 (using Polynomial LCA time-dependent algorithm (see Table 1)).

Problem 3. Find the departure time for the known arrival time using dynamic backward Dijkstra algorithm for all three cases of the previous problem. Based on the numerical results obtained in problems 1 and 2, we knew that if the driver departs from the source node 5 at 9:00am (case a), or at 3:00pm (case b), or at 4:45pm (case c), then he/she will arrive at the destination node 2 at 16.00 (or 4:00pm), or at 24.00 (or mid-night), or at 26.25 (or 2:15am next day), respectively.

To find the solutions for the above questions, our proposed modified dynamic backward Dijkstra algorithms can be summarized in the following major steps:

Step 1. Revised the links’ direction of the given network (see Figure 2(b)). The given arrival times (obtained from problems 1 and 2) can be used as the known departure time at the source node 2.

Step 2. In this step, we would like to find “what time the driver should depart from the source node i (for link), in order to arrive at the destination node j at a specified time?”. For this situation, Equation (1) can also be used. However, the known variables are and, and the unknown variable is. This is completely different from the defined problems 1 and/or 2, where the known variables are and, and the unknown variable is. While the unknown variable can be easily (and uniquely) found from Equation (1) for Problems 1 and 2, the unknown variable for Problem 3 may not be easily (and/or uniquely) found from Equation (1). Combining Equation (1) and Equation (2), one obtains:

(3)

The only unknown in Equation (3) is Departure time (). To illustrate this point, the following numerical details are provided and explained for Problem 3, case (b), where we start with the known at node 2 as 24.00 (or mid-night). Starting from node, find all the connected out-going links (based on Figure 2(b)).

Start first iteration, when, , (the array of explored nodes), (Given arrival time at destination node). For Outgoing link 2-1, we have, and, Equation (3) will give the 9 computed values (corresponding to the 9 time functions shown in Figure 1) as following:

(4)

However, Figure 1 implies that the time function is only valid if is within the range [0.00 - 5.00 hours], the time function is only valid if is within the range [5.00 - 6.00 hours], the time

Table 1. Numerical Results for Dynamic Network in Figure 2.

function is only valid if is within the range [6.00 - 8.00 hours], the time function is only valid if is within the range [8.00 - 9.00 hours], the time function is only valid if is within the range [9.00 - 15.00 hours], the time function is only valid if is within the range [15.00 - 16.00 hours], the time function is only valid if is within the range [16.00 - 18.00 hours], the time function is only valid if is within the range [18.00 - 19.00 hours], and the time function is only valid if is within the range [19.00 - 24.00 hours].

For the above reasons/restrictions, out of the 9 computed (shown in Equation (4)), we can only accept the value hours, with the value, which correspond to the. We can update our information as below:

,

,.

For outgoing link 2-3, we have, and (for link 2 - 3) = 4.5, Equation (3) will give the 9 computed values (corresponding to the 9 time functions:, shown in Figure 1) as following:

(5)

Based on the restrictions imposed on the 9 functions, shown in Figure 1, out of the 9 computed (shown in Equation (5)), there were 3 possible solutions for, or, or hours. The corresponding values for, and . Among the 3 possible solutions for (such as, or, or), we select the largest hours, since this choice will correspond to the smallest. In other words, our selected choice will give the smallest which will give the smallest travel cost for this particular link. We can update our information as below:

,

,.

The next node to explore is node 1 (i.e.,), so the second iteration can start by searching toward all the outgoing links from node 1 in which the arrival time at node 1 is 21.5 (), and. The algorithm will stop when the next node to explore is the destination node.

Eventually, the at node 5 for all cases a, b, and c of the problem were found, and presented in Table 1. Thus, for certain dynamic networks, there may be more than one solution for the departure time at node i (say) which still give the same specified arrival time at node j (say). By using the suggested criterion to select the value of, the resulted path will also often corresponds to the SP as well.

4. Numerical Result for Large Scale Real-Life Networks

In this section, 12 large-scale examples based on real-life networks data have been solved using the regular forward Dijkstra, and backward Dijkstra algorithms. The regular forward Dijkstra algorithm is employed to find the arrival time at the destination node j, based on the known departure time at the source node i. The backward Dijkstra algorithm is employed to find the departure time at the source node , based on the known (specified) arrival time at the destination node j. For cases where multiple solutions for do exist, we will select the which gives the smallest value of, which corresponds to the smallest value for. This is the criterion which has been used in Section 3.

For convenient purposes, the arrival time at the destination node j of the Forward Dijkstra algorithm will be used as the departure time for the destination j of the Backward Dijkstra algorithm, for the same network with reversed links’ directions. All numerical results are compiled and tabulated in Table 2.

For the problem of finding the departure time at the source node(s) based on the specified/given arrival time at the destination node(s), and based on the numerical results presented in Table 2, the following major observations can be made:

a) Unique solution has been obtained in all examples except example 2 and 11.

b) Multiple (or non-unique) solutions have been found in examples 2, and 11. For these examples, different departure time at the source node can lead to the same specified arrival time at the destination node. In example 2, if the driver departs at the source node 25 at either 6.00 hours, or at 7.236 hours, he/she still arrives at the destination node 110 at the specified time 21.7647 hours. Of course, if the driver departs at the source node 25 at 7.9032 hours, then not only he will arrive at his destination node on time (at the specified time 21.7647 hours), but this selected path will also be the shortest path.

Table 2. Comparisons of forward and backward Dijkstra results for real networks.

^*FIFO Network (example 1 through 12 correspond to Non-FIFO Network).

c) In example 11, the driver departs from source node 48 at 1.00 hour (=1:00am), and he/she will arrive at the destination node 1415 at 63.3523 hours (=63.3523 − 48 = 15.3523 hours, two days later), based on the Forward Dijkstra search. Based on the Backward Dijkstra search, the driver should depart (at the same source node) at 1.5262 hours (=1:5262 am hours), if he/she wishes to arrive at the same destination node at the specified time 63.3523 hours.

5. Conclusions

In this paper, the well-known polynomial LCA, and the Regular Forward Dijkstra algorithms have been conveniently applied to dynamic (time dependent) networks, through the concept of piece-wise linear function and Time Delay Factor () which is a function of the departure time () at node “i” for a typical link.

The practical problems of finding the departure time at the source node(s) based on the specified/given arrival time at the destination node(s) can be efficiently solved by using the proposed Backward Dijkstra algorithm, which basically employs the Forward Dijkstra algorithm on the same dynamic network with all links’ direction are reversed. Extensive numerical results based on a small-scale (academic) dynamic network (with 5 nodes, and 9 links), as well as using 12 real-life (large-scale) dynamic networks, seem to indicate that:

i) The proposed Backward Dijkstra (time dependent) algorithms always find the correct departure time at the source node “i” that will guarantee to arrive at the destination node “j” at the specified/given arrival time.

ii) For FIFO dynamic networks, the computed paths correspond to the shortest paths, and the solution is unique.

iii) For certain NON-FIFO dynamic networks, the computed paths often correspond to the shortest paths, although SP is not a requirement for the type of time-dependent problems considered in this work.

iv) Depending on the particular NON-FIFO dynamic network, the computed solution(s) might be unique or non-unique where multiple solutions do exist.

Acknowledgements

This paper was in part funded by Mid-Atlantic Transportation Sustainability University Transportation Center (MATS UTC, for the third author), and by the NSF grant#1440673 (for the last author).

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Orda, A., and Rom R. (1990) Shortest Path and Minimum Delay Algorithms in Networks with Time-Dependent Edge Length. J. ACM, 37, 607-625. http://dx.doi.org/10.1145/79147.214078
[2]	Daganzo, C.F. (2002) Reversibility of the Time-Dependent Shortest Path Problem. Transportation Research Part B: Methodological, 36, 665-668. http://dx.doi.org/10.1016/S0191-2615(01)00012-1
[3]	Chabini, I. and Ganugapati, S. (2002) Parallel Algorithms for Dynamic Shortest Path Problems. International Transactions in Operational Research, 9, 279-302. http://dx.doi.org/10.1111/1475-3995.00356
[4]	Luo, W.M. and Han, P.Y. (2007) Study on Non-FIFO Arc in Time-Dependent Networks. Eighth ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing. http://dx.doi.org/10.1109/SNPD.2007.445
[5]	Ding, B., Yu, J.X. and Qin, L. (2008) Finding Time-Dependent Shortest Paths over Large Graphs. EDBT’2008 Proceedings of the 11th International Conference on Extending Database Technology: Advances in Database Technology, 205-216. http://dx.doi.org/10.1145/1353343.1353371
[6]	Nannicini, G. (2009) Point-to-Point Shortest Paths on Dynamic Time-Dependent Road Networks. Ph.D. Dissertation, Ecole Poly-technique, France.
[7]	Allen, S.E. (2013) Parallel Implementations of the Frank-Wolfe Algorithms for the Traffic Assignment Problem. M.Sc. Thesis, MSVE Department, Old Dominion University, Norfolk, USA.