The Algorithm of the Time-Dependent Shortest Path Problem with Time Windows

Affiliation(s)

^{1}
Mathematics Department, Faculty of Science, Al-Azhar University, Cairo, Egypt.

^{2}
Mathematics Department, Faculty of Applied Medical Science, Taif University, Turabah, KSA.

ABSTRACT

In this paper, we present a new algorithm of the time-dependent shortest path problem with time windows. Give a directed graph , where*V* is a set of nodes, *E* is a set of edges with a non-negative transit-time function . For each node , a time window within which the node may be visited and , is non-negative of the service and leaving time of the node. A source node *s*, a destination node *d* and a departure time *t*_{0}, the time-dependent shortest path problem with time windows asks to find an s, d-path that leaves a source node s at a departure time *t*_{0}; and minimizes the total arrival time at a destination node *d*. This formulation generalizes the classical shortest path problem in which *c*_{e} are constants. Our algorithm of the time windows gave the generalization of the ALT algorithm and *A** algorithm for the classical problem according to Goldberg and Harrelson [1], Dreyfus [2] and Hart et al. [3].

In this paper, we present a new algorithm of the time-dependent shortest path problem with time windows. Give a directed graph , where

Cite this paper

El-Sherbeny, N. (2014) The Algorithm of the Time-Dependent Shortest Path Problem with Time Windows.*Applied Mathematics*, **5**, 2764-2770. doi: 10.4236/am.2014.517264.

El-Sherbeny, N. (2014) The Algorithm of the Time-Dependent Shortest Path Problem with Time Windows.

References

[1] Goldberg, A. and Harrelson, C. (2005) Computing the Shortest Path: A* Search Meets Graph Theory.

http://research.microsoft.com/pubs/154937/soda05.pdf

[2] Dreyfus, S. (1969) An Appraisal of Some Shortest-Path Algorithms. Operations Research, 17, 395-412.

http://dx.doi.org/10.1287/opre.17.3.395

[3] Hart, P., Nilsson, N. and Raphael, B. (1968) A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions Systems Science and Cybernetics, 4, 100-107.

http://dx.doi.org/10.1109/TSSC.1968.300136

[4] Ahuja, R., Magnanti, T. and Orlin, J. (1993) Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Upper Saddle River.

[5] El-Sherbeny, N. (2001) Resolution of a Vehicle Routing Problem with Multiobjective Simulated Annealing Method. Ph.D. Dissertation of Faculty of Science, Mons University, Mons.

[6] El-Sherbeny, N. and Tuyttens, D. (2001) Optimization Multicriteria of Routing Problem. Troisieme Journee de Travail sur la Programming Mathematique Multi-Objective, Faculte Polytechnique de Mons, Mons.

[7] Tuyttens, D., Teghem, J. and El-Sherbeny, N. (2004) A Particular Multiobjective Vehicle Routing Problem Solved by Simulated Annealing. Lecture Notes in Economics and Mathematical Systems, 535, 133-152.

http://dx.doi.org/10.1007/978-3-642-17144-4_5

[8] El-Sherbeny, N. (2011) Imprecision and Flexible Constraints in Fuzzy Vehicle Routing Problem. American Journal of Mathematical and Management Sciences, 31, 55-71.

http://dx.doi.org/10.1080/01966324.2011.10737800

[9] Cook, K. and Halsey, E. (1966) The Shortest Route through a Network with Time-Dependent Intermodal Transit. Journal of Mathematical Analysis and Applications, 14, 493-498.

http://dx.doi.org/10.1016/0022-247X(66)90009-6

[10] Halpern, H. (1977) Shortest Route with Time Dependent Length of Edges and Limited Delay Possibilities in Nodes. Operations Research, 21, 117-124.

[11] Kaufman, D. and Smith, R. (1993) Fastest Paths in Time-Dependent Networks for Intelligent Vehicle-Highway Systems Application. Journal of Intelligent Transportation Systems, 1, 1-11.

[12] Orda, A. and Rom, R. (1990) Shortest-Path and Minimum-Delay Algorithms in Networks with Time-Dependent Edge-Length. Journal of the ACM, 37, 607-625.

http://dx.doi.org/10.1145/79147.214078

[13] Sherali, H., Ozbay, K. and Subramanian, S. (1998) The Time-Dependent Shortest Pair of Disjoint Paths Problem: Complexity, Models, and Algorithms. Networks, 31, 259-272.

http://dx.doi.org/10.1002/(SICI)1097-0037(199807)31:4<259::AID-NET6>3.0.CO;2-C

[14] Dean, B. (1999) Continuous-Time Dynamic Shortest Path Algorithms. Master’s Thesis, MIT.

[15] Ding, B., Xu, J. and Qin, L. (2008) Finding Time-Dependent Shortest Paths over Large Graphs. Proceedings of the 11th International Conference on Extending Database Technology, 25-30 March 2008, 205-216.

[16] Kanoulse, E., Du, Y., Xia, T. and Zhang, D. (2006) Finding Fastest Paths on a Road Network with Speed Patterns. Proceedings of the 22nd International Conference on Data Engineering, Atlanta, 3-7 April 2006, 10-19.

[17] Wagner, D. and Willhalm, T. (2007) Speed-Up Techniques for Shortest-Path Computations. Lecture Notes in Computer Science, 4393, 23-36.

http://dx.doi.org/10.1007/978-3-540-70918-3_3

[1] Goldberg, A. and Harrelson, C. (2005) Computing the Shortest Path: A* Search Meets Graph Theory.

http://research.microsoft.com/pubs/154937/soda05.pdf

[2] Dreyfus, S. (1969) An Appraisal of Some Shortest-Path Algorithms. Operations Research, 17, 395-412.

http://dx.doi.org/10.1287/opre.17.3.395

[3] Hart, P., Nilsson, N. and Raphael, B. (1968) A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions Systems Science and Cybernetics, 4, 100-107.

http://dx.doi.org/10.1109/TSSC.1968.300136

[4] Ahuja, R., Magnanti, T. and Orlin, J. (1993) Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Upper Saddle River.

[5] El-Sherbeny, N. (2001) Resolution of a Vehicle Routing Problem with Multiobjective Simulated Annealing Method. Ph.D. Dissertation of Faculty of Science, Mons University, Mons.

[6] El-Sherbeny, N. and Tuyttens, D. (2001) Optimization Multicriteria of Routing Problem. Troisieme Journee de Travail sur la Programming Mathematique Multi-Objective, Faculte Polytechnique de Mons, Mons.

[7] Tuyttens, D., Teghem, J. and El-Sherbeny, N. (2004) A Particular Multiobjective Vehicle Routing Problem Solved by Simulated Annealing. Lecture Notes in Economics and Mathematical Systems, 535, 133-152.

http://dx.doi.org/10.1007/978-3-642-17144-4_5

[8] El-Sherbeny, N. (2011) Imprecision and Flexible Constraints in Fuzzy Vehicle Routing Problem. American Journal of Mathematical and Management Sciences, 31, 55-71.

http://dx.doi.org/10.1080/01966324.2011.10737800

[9] Cook, K. and Halsey, E. (1966) The Shortest Route through a Network with Time-Dependent Intermodal Transit. Journal of Mathematical Analysis and Applications, 14, 493-498.

http://dx.doi.org/10.1016/0022-247X(66)90009-6

[10] Halpern, H. (1977) Shortest Route with Time Dependent Length of Edges and Limited Delay Possibilities in Nodes. Operations Research, 21, 117-124.

[11] Kaufman, D. and Smith, R. (1993) Fastest Paths in Time-Dependent Networks for Intelligent Vehicle-Highway Systems Application. Journal of Intelligent Transportation Systems, 1, 1-11.

[12] Orda, A. and Rom, R. (1990) Shortest-Path and Minimum-Delay Algorithms in Networks with Time-Dependent Edge-Length. Journal of the ACM, 37, 607-625.

http://dx.doi.org/10.1145/79147.214078

[13] Sherali, H., Ozbay, K. and Subramanian, S. (1998) The Time-Dependent Shortest Pair of Disjoint Paths Problem: Complexity, Models, and Algorithms. Networks, 31, 259-272.

http://dx.doi.org/10.1002/(SICI)1097-0037(199807)31:4<259::AID-NET6>3.0.CO;2-C

[14] Dean, B. (1999) Continuous-Time Dynamic Shortest Path Algorithms. Master’s Thesis, MIT.

[15] Ding, B., Xu, J. and Qin, L. (2008) Finding Time-Dependent Shortest Paths over Large Graphs. Proceedings of the 11th International Conference on Extending Database Technology, 25-30 March 2008, 205-216.

[16] Kanoulse, E., Du, Y., Xia, T. and Zhang, D. (2006) Finding Fastest Paths on a Road Network with Speed Patterns. Proceedings of the 22nd International Conference on Data Engineering, Atlanta, 3-7 April 2006, 10-19.

[17] Wagner, D. and Willhalm, T. (2007) Speed-Up Techniques for Shortest-Path Computations. Lecture Notes in Computer Science, 4393, 23-36.

http://dx.doi.org/10.1007/978-3-540-70918-3_3