آمار
| تعداد نشریات | 7 |
| تعداد شمارهها | 102 |
| تعداد مقالات | 1,139 |
| تعداد مشاهده مقاله | 1,046,612 |
| تعداد دریافت فایل اصل مقاله | 865,417 |
Approximation Solutions for Time-Varying Shortest Path Problem | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 5، دوره 2، شماره 2، آذر 2017، صفحه 139-147 اصل مقاله (439.64 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2017.25850.1047 | ||
| نویسندگان | ||
| Gholam Hassan Shirdel* 1؛ Hassan Rezapour2 | ||
| 1University of Qom | ||
| 2Unuversity of Qom | ||
| چکیده | ||
| Time-varying network optimization problem, which is NP-complete in the ordinary sense, are traditionally solved by specialized algorithms. This paper considers the time-varying shortest path problem, which can be optimally solved in $O\big(T(m+n)\big)$ time, where $T$ is a given integer. For this problem with arbitrary waiting times, we propose an approximate algorithm, which can find an acceptable solution of the problem with $O\big(\frac{T(m+n)}{k}\big)$ time complexity such that it evaluates only a subset of the values for $t \in \{0, 1,\ldots,T\}$. | ||
| کلیدواژهها | ||
| Time-Varying Optimization؛ Approximation solutions؛ Shortest Path Problem | ||
| مراجع | ||
|
[1] R.K. Ahuja, J.B. Orlin, S. Pallottino, and M.G. Scutell`a, Dynamic shortest paths minimizing travel times and costs, Networks 41 (2003), no. 4, 197–205.
[2] Y. Aneja and K. Nair, The constrained shortest path problem, Naval Res. Logist. 25 (1978), no. 3, 549–555.
[3] X. Cai, T. Kloks, and C.K. Wong, Time-varying shortest path problems with constraints, Networks 29 (1997), no. 3, 141–149.
[4] X. Cai, D. Sha, and C.K. Wong, Time-varying network optimization, Springer New York, 2007. [5] I. Chabini, Discrete dynamic shortest path problems in transportation applications: complexity and algorithms with optimal run time, Transportation Research Record 1645 (1998), 170–175.
[6] L. Cooke and E. Halsey, Shortest route through a network with time-dependent internodal transit times, J. Math. Anal. Appl. 14 (1966), no. 3, 492–498.
[7] J. Halpern, Shortest route with time-dependent length of edges and limited delay possibilities in nodes, Math. Methods Oper. Res. 21 (1977), no. 3, 117–124.
[8] G.Y. Handler and I. Zang, A dual algorithm for the constrained shortest path proglem, Networks 10 (1980), no. 4, 293–309.
[9] S.M. Hashemi, Sh. Mokarami, and E. Nasrabadi, Dynamic shortest path problems with time-varying costs, Optim. Lett. 4 (2010), no. 1, 147–156.
[10] M.M.D. Hassan, Network reduction for the acyclic constrained shortest path problem, European J. Oper. Res. 63, no. 1.
[11] I. Ioachim, S. Gelinas, F. Soumis, and J. Desrosiers, A dynamic programming algorithm for the shortest path problem with time windows and linear node costs, Networks 31 (1998), no. 3, 193–204.
[12] H.C. Joksch, The shortest route probelm with constraints, J. Math. Anal. Appl. 14 (1966), no. 2, 191–197.
[13] R. Koch and E. Nasrabadi, Continuos-time dynamic shortest path problems with negative transit times, SIAM J. Control Optim. 52 (2014), no. 4, 2449–2481.
[14] A. Orda and R. Rom, Shortest-path and minimum-delay algorithms in networks with time-dependent edge length, Journal of the ACM 37 (1990), no. 3, 607–625.
[15] A.B. Philpott, Continuous-time shortest path problems and linear programming, SIAM J. Control Optim. 32 (1994), no. 2, 538–552.
[16] H. Rezapour and Gh. Shirdel, K-objective time-varying shortest path problem with zero waiting times at vertices, Trends in Applied Sciences Research 10 (2015), no. 5, 278–285.
[17] H. Rezapour and Gh. Shirdel, The arbitrary waiting times in the time-aarying shortest path with triangular fuzzy costs, Adv. Appl. Math. Sci. 15 (2016), no. 2, 75–85.
[18] H. Rezapour and Gh. Shirdel, Dynamic network flows with uncertain costs belonging to interval, Appl. Appl. Math. 11 (2016), no. 1, 285 – 299.
[19] H. Rezapour and Gh. Shirdel, Time-varying maximum capacity path problem with zero waiting times and fuzzy capacities, SpringerPlus 5 (2016), 981–990.
[20] H. Rezapour and Gh. Shirdel, The time-varying shortest path problem with fuzzy transit costs and speedup, Acta Univ. Sapientiae Math. 8 (2016), no. 1, 166–173.
[21] C.C. Skiscim and B.L. Golden, Solving k-shortest and constrained shortest path problems efficiently, Ann. Oper. Res. 20 (1989), no. 1, 249–282.
[22] A. Ziliaskopoulos and H. Mahmassani, A time-dependent shortest path algorithm for real-time intelligent vehicle highway system applications, Transportation Research Record 1408 (1993), 94–104. | ||
|
آمار تعداد مشاهده مقاله: 1,353 تعداد دریافت فایل اصل مقاله: 994 |
||